Searching for a byte sequence in a byte array


I needed to find a sequence of bytes in a byte array. There’s the .IndexOf() extension method but this finds only one byte. What I want is a .Contains() extension method for byte arrays which is able accept an array of bytes as a parameter (the needle) representing the byte sequence to find in the array (the haystack).

Here’s an implementation…

In this case the extension method returns true if the needle is found in the haystack and the offset of the end of the sequence is return in the [out] position parameter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Usage
int position = 0;
byte[] myNeedle = new byte[] {1,2,3};
if (myHaystack.Contains(ref myNeedle, out position))
{
    Console.Writeline("Found at: {0}", position);
}
 
/// <summary>
/// Finds a sequence of bytes in an array
/// </summary>
/// <param name="buffer">The haystack</param>
/// <param name="sequence">The needle</param>
/// <param name="position"> The position of the needle in the haystack if the needle is found </param>
/// <returns>True if the needle is found</returns>
public static bool Contains(this byte[] buffer, ref byte[] sequence, out int position)
{
    int currOffset = 0;
 
    for (position = 0; position < buffer.Length; position++)
    {
        byte b = buffer[position];
        if (b == sequence[currOffset])
        {
            if (currOffset == sequence.Length - 1) return true;
            currOffset++;
            continue;
        }
 
        // Fixup the offset to the byte after the beginning of the abortive sequence
        if (currOffset == 0) continue;
        position -= currOffset;
        currOffset = 0;
    }
 
    return false;
}
// Usage
int position = 0;
byte[] myNeedle = new byte[] {1,2,3};
if (myHaystack.Contains(ref myNeedle, out position))
{
	Console.Writeline("Found at: {0}", position);
}

/// <summary>
/// Finds a sequence of bytes in an array
/// </summary>
/// <param name="buffer">The haystack</param>
/// <param name="sequence">The needle</param>
/// <param name="position"> The position of the needle in the haystack if the needle is found </param>
/// <returns>True if the needle is found</returns>
public static bool Contains(this byte[] buffer, ref byte[] sequence, out int position)
{
	int currOffset = 0;

	for (position = 0; position < buffer.Length; position++)
	{
		byte b = buffer[position];
		if (b == sequence[currOffset])
		{
			if (currOffset == sequence.Length - 1) return true;
			currOffset++;
			continue;
		}

		// Fixup the offset to the byte after the beginning of the abortive sequence
		if (currOffset == 0) continue;
		position -= currOffset;
		currOffset = 0;
	}

	return false;
}

Information and Links

Join the fray by commenting, tracking what others have to say, or linking to it from your blog.


Other Posts

Write a Comment

Take a moment to comment and tell us what you think. Some basic HTML is allowed for formatting.

Reader Comments

Be the first to leave a comment!