+ private void rangeBasedMatching(Layer2Flow flow, PcapPacket newPacket) {
+ // TODO: For range-based matching, we only care about matching a range; therefore it is a matcher array.
+ if (mPerFlowRangeMatcher.get(flow) == null) {
+ // If this is the first time we encounter this flow, we need to set up a sequence matcher.
+ // All sequences of the cluster have the same length, so we only need to compute the length of the
+ // arrays once. We want to make room for a cluster matcher in each state, including the initial empty state
+ // but excluding the final "full match" state (as there is no point in keeping a terminated sequence matcher
+ // around), so the length of the array is simply the sequence length.
+ Layer2RangeMatcher[] matcher = new Layer2RangeMatcher[mCluster.get(0).size()];
+ // Prepare a "state 0" sequence matcher.
+ matcher[0] = new Layer2RangeMatcher(mCluster.get(0), mCluster.get(1), mInclusionTimeMillis, mEps);
+ // Associate the new sequence matcher table with the new flow.
+ mPerFlowRangeMatcher.put(flow, matcher);
+ }
+ // Fetch table that contains sequence matchers for this flow.
+ Layer2RangeMatcher[] matcher = mPerFlowRangeMatcher.get(flow);
+ // Present packet to the sequence matcher.
+ for (int j = matcher.length - 1; j >= 0; j--) {
+ Layer2RangeMatcher sm = matcher[j];
+ if (sm == null) {
+ // There is currently no sequence matcher that has managed to match j packets.
+ continue;
+ }
+ boolean matched = sm.matchPacket(newPacket);
+ if (matched) {
+ if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
+ // Sequence matcher has a match. Report it to observers.
+ mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
+ // Remove the now terminated sequence matcher.
+ matcher[j] = null;
+ } else {
+ // Sequence matcher advanced one step, so move it to its corresponding new position iff the
+ // packet that advanced it has a later timestamp than that of the last matched packet of the
+ // sequence matcher at the new index, if any. In most traces, a small amount of the packets
+ // appear out of order (with regards to their timestamp), which is why this check is required.
+ // Obviously it would not be needed if packets where guaranteed to be processed in timestamp
+ // order here.
+ if (matcher[j+1] == null ||
+ newPacket.getTimestamp().isAfter(matcher[j+1].getLastPacket().getTimestamp())) {
+ matcher[j+1] = sm;
+ }
+ }
+ // We always want to have a sequence matcher in state 0, regardless of if the one that advanced
+ // from state zero completed its matching or if it replaced a different one in state 1 or not.
+ if (sm.getMatchedPacketsCount() == 1) {
+ matcher[j] = new Layer2RangeMatcher(sm.getTargetLowerBound(), sm.getTargetUpperBound(),
+ mInclusionTimeMillis, mEps);
+ }
+ }
+ }
+ }