Simplification of byte array comparison algorithm

Question

I have an algorithm that evaluates in input byte[] with a source byte[]. Several conditions can be encountered:

• Match found
• No match found
• End of input array
• End of source array
• Input wildcard (*) matches against any source byte

All of these conditions are dealt with in this algorithm. Having been my first pass at this algorithm, I know there are improvements that can be made. Not only am I looking for cleaner code and possibly refactoring to find re-usable bits, this needs to be as efficient as possible. Right now this will compare an 18 byte input array against an 1170 byte source array in 2ms.

Here is the current implementation of the algorithm:

private bool HasMatchBytes(byte[] bytes, out int length, ref int position) {
    var hasMatch = false;
    var isComplete = false;
    var b = position;
    var end = position;

    //   - this loop depends on internal advancement of the counter [v]
    for (var v = 0; v < bytes.Length; ) {
        var isMatch = false;

        //  - this loop depends on internal advancement of the counter [b]
        while (b < mByteStream.Length &&
               !isComplete) {

            //  wildcard doesn't care the value
            if (bytes[v] == '*') {
                isMatch = true;
            }
            else {
                isMatch = bytes[v] == mByteStream[b];
            }

            //  only advance positions if hasMatch is currently false
            if (isMatch && !hasMatch) {
                hasMatch = true;
                position = b++;
                ++v;
            }
            //  current position does not match and invalidates previous buffers
            else if (!isMatch && hasMatch) {
                hasMatch = false;
                //  reset v (bytes array)
                v = 0;
                //  advance b (stream array)
                ++b;
            }
            //  any other condition should advance b (stream array)
            //      and v (bytes array)
            else {
                //  advance v (bytes array)
                if (isMatch && hasMatch) {
                    ++v;
                }
                //  we could have reached the end of v
                if (v < bytes.Length) {
                    if (hasMatch) {
                        end = ++b;
                    }
                    else {
                        ++b;
                    }
                }
                //  if so, force completion
                else {
                    isComplete = true;
                }
            }
        }

        //  isMatch means the current byte indexes match
        //  assumptions:
        //      wherever the buffer position is, the results are
        //          true to the current start position.
        if (hasMatch && v < bytes.Length) {
            ++v;
            end = ++b;

            if (b >= mByteStream.Length) {
                hasMatch = false;
            }
        }

        //  with match and at end of bytes length algorithm is complete
        if (hasMatch &&
            v >= bytes.Length) {
            isComplete = true;
            end = ++b;
        }

        //  if end of source reached then shut down algorithm
        if (b >= mByteStream.Length) {
            v = bytes.Length;
            isComplete = true;
            end = mByteStream.Length;
        }

    }

    length = end - position;

    return hasMatch;
}

...using .Net 4.5 if that helps.

Edit per comment

In all cases, the algorithm will return true if the source sequence contains a match against the full input array sequence. Each byte must match specifically in sequence except where a wildcard (*) is specified.

This algorithm is intended to continue reading until end of the source array. If the end of the source array is reached before another full iterative match of the input array, the algorithm would return false. But the calling method uses the returned position plus the length of the input sequence to determine if there could possibly be another match in the source.

Here is the calling code:

    public IEnumerable<IMetaToken> Matches(IMatchToken matchToken) {
        var bytes = matchToken.GetValues();
        var length = 0;
        var position = 0;

        while ((position + bytes.Length) < mByteStream.Length) {
            if (HasMatchBytes(bytes, out length, ref position)) {
                var start = position;
                position += length;

                var token = new MetaToken(start, length);
                yield return token;
            }
            else {
                position += length;
            }
        }
    }

FWIW: This is part of a Regex-like class that handles expressions against byte arrays. First you have to create a format object and then have the ByteRegex class find Matches against the supplied source sequence.

---

I've decided to take @svick's advice ...well, somewhat. I've already worked on renaming the indexes, etc.

I have another class that manipulates a MemoryStream and I could use that to encapsulate this operation. At least the code would be in a class with the same order of operations.

I am also going to refactor this huge method into 2 static iterator methods: IterateNeedle(...) and IterateHaystack(...). Names are likely to be changed to protect the innocent but you get the idea. I'll post some code once I have it reworked.

UPDATE Iterators to the rescue
I don't know if I should post my refactors as an answer. Might be helpful for people to see implementation of the IEnumerator state machine. I'll post explanation as an answer. There is a lot of code though and it is specialized so I'm hesitant because it might draw a lot of questions that are off topic.

Answer 1

1. If I understand this correctly, your code doesn't work. This is because when some characters match and then you find a character that doesn't match, you can't continue checking with the current character, you need to go back to the second character of the current partial match.

   An example is mByteStream = new byte[] { 0, 0, 1 }, bytes = new byte[] { 0, 1 }. For this input, the correct result is true, but your code returns false.

2. It looks like this method is part of a type that does other things. I think it would be cleaner if it was in a separate type, taking both arrays as parameters.

3. When reading the code, it's very easy to confuse bytes and mByteStream, b and v. Those names don't mean anything. Much better names would be for example needle, haystack, needleIndex and haystackIndex. Having different variables names hasMatch and isMatch is also very confusing.

4. A method that's this complicated would benefit greatly from detailed XML documentation. That way, callers of the method don't need to read its code to know what it does.

Answer 2

@svick is right in suggesting separate classes/objects. These objects come in the form of custom iterator objects. There are two stacks that must be iterated:

1. a collection of mask tokens (each token really nothing more than byte[])
2. full sequence matches (i.e. a start/length of match)

For the mask tokens:

private struct MaskSequenceIterator : IMaskSequenceIterator

For the matches:

private struct MatchSequenceIterator : IMatchSequenceIterator

IMatchSequenceIterator does all the real work and quite easily. The magic is all in the MoveNext() method:

        public bool MoveNext() {
            // gets the next mask token
            var continueMatching = mMaskIterator.MoveNext();
            // determine if there is enough stream to keep matching
            if (continueMatching) {
                continueMatching &= mCurrentPosition + mMaskToken[mMaskIterator.Index].Length <= mRegex.mByteStream.Length;
            }

            // check to see if the sequence matches - nvm the out var atm
            var sequenceMatches = TryGetNextMatch(continueMatching, out mCurrent);

            // set iterator properties
            mIsSequenceMatch = sequenceMatches;
            mEndOfStream = mCurrentPosition >= mRegex.mByteStream.Length;

            // true if matches
            return sequenceMatches;
        }

This greatly simplified my outer logic in both a single Match method as well as the multiple Matches method:

        IMatchSequenceIterator matchIterator = new MatchSequenceIterator(this, maskToken, position);
        var sumLength = 0L;
        var isComplete = false;

        // Match
        while ((!isComplete) &&
               (hasMatch = matchIterator.MoveNext())) {
            // get the sum length
            sumLength += matchIterator.Current.Length;

            // MaskIterator is constructed by the MatchIterator
            if (matchIterator.MaskIterator.IsFirst()) {
                position = matchIterator.Current.Start;
            }

            // debug points
            var index = matchIterator.MaskIterator.Index;
            var isLast = matchIterator.MaskIterator.IsLast();

            isComplete = isLast || matchIterator.EndOfSequence;

        }

        //  this comparison tells us if we matched all sequences
        if (isComplete && matchIterator.MaskIterator.IsLast()) {
            return new MetaToken(position, sumLength);
        }

        // Matches
        while ((!isComplete) &&
               (hasMatch = matchIterator.MoveNext())) {
            sumLength += matchIterator.Current.Length;

            if (matchIterator.MaskIterator.IsFirst()) {
                position = matchIterator.Current.Start;
            }

            var index = matchIterator.MaskIterator.Index;
            var isLast = matchIterator.MaskIterator.IsLast();

            isComplete = matchIterator.EndOfSequence;

            if (!isComplete && isLast) {
                //  yield the current match meta data
                yield return new MetaToken(position, sumLength);
                //  reset counters;
                position += sumLength;
                sumLength = 0;
                //  we want to keep finding matches so reset the internal mask iterator
                matchIterator.MaskIterator.Reset();
                //  reset has match flag
                hasMatch = false;
            }

        }

Why my own custom iterator interfaces instead of implementing IEnumerable<T>
I felt this should be addressed in depth -- added as a matter of interest
The problem is iterating two sequences (seqA, a.k.a. Source and seqB, a.k.a. Mask)

• The Mask must be satisfied in whole (byte for byte in sequence)
• Reset Mask stack when matching fails on a sequence
• Increment the Mask stack as Source sequences match
• Stop matches if Source stack is at the end

This boils down to needing 2 state machines to handle the logic of iterating an inner set of conditions (a.k.a. maskTokens) for evaluation. A maskToken is then used to match against a specified Source sequence - which is iterated by the outer state machine.

I used interfaces to build two rudimentary state-machines implementing IEnumerator<T>. For the record, I am weighing the implementation of IEnumerable<T>; at the time of design I was not convinced of how intuitive the interface would be when considering the assumptions made while using an IEnumerable<T>.

The inner state machine - MaskIterator - doesn't really have any special logic but exposes some additional members:

//   `ControlChar` is a custom value type representing a byte[4]
interface IMaskSequenceIterator : IEnumerator<ControlChar> {

    #region properties

    ControlChar Current { get; }

    int Index { get; }

    IMaskToken MaskToken { get; }

    #endregion


    #region members

    void Dispose();

    bool IsFirst();

    bool IsLast();

    long Length();

    void MoveFirst();

    bool MoveNext();

    void Reset();

    #endregion

}

The outer state machine - MatchIterator - has quite a bit more logic:

A. Manipulate and Interpret MaskIterator properties
B. Find Match Sequence: logic black box

//   IMetaToken holds [start, length] info of sequence matches
interface IMatchSequenceIterator : IEnumerator<IMetaToken> {

    #region properties

    IMetaToken Current { get; }

    bool EndOfSequence { get; set; }

    bool IsSequenceMatch { get; }

    IMaskSequenceIterator MaskIterator { get; }

    #endregion


    #region members

    void Dispose();

    bool MoveNext();

    void Reset();

    #endregion
}

Basically, I am taking advantage of the state-machine characteristics of the IEnumerator (as a pattern, so to speak). The idea of this project is that I can build a mask, or sequence of bytes - say, 91-00-00-00; 16-00-00-00; 58-00-00-00 - and match a source byte stream looking for every occurrence of 91-00-00-00-16-00-00-00-58-00-00-00.

The mask formatter can use wildcards specifying a length so I can format something like: 91-00-00-00 42-42 42-42-16-00 58-00-00-00

... where 42 is *. The MatchIterator will return meta data for anything that matches the pattern 91-00-00-00-42-42-42-42-16-00-58-00-00-00 and 42 can be replaced by any byte.

Feedback is welcome!