Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

byte[] array pattern search

Anyone know a good and effective way to search/match for a byte pattern in an byte[] array and then return the positions.

For example

byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};

byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}
like image 339
Anders R Avatar asked Nov 12 '08 09:11

Anders R


2 Answers

May I suggest something that doesn't involve creating strings, copying arrays or unsafe code:

using System;
using System.Collections.Generic;

static class ByteArrayRocks
{    
    static readonly int[] Empty = new int[0];

    public static int[] Locate (this byte[] self, byte[] candidate)
    {
        if (IsEmptyLocate(self, candidate))
            return Empty;

        var list = new List<int>();

        for (int i = 0; i < self.Length; i++)
        {
            if (!IsMatch(self, i, candidate))
                continue;

            list.Add(i);
        }

        return list.Count == 0 ? Empty : list.ToArray();
    }

    static bool IsMatch (byte[] array, int position, byte[] candidate)
    {
        if (candidate.Length > (array.Length - position))
            return false;

        for (int i = 0; i < candidate.Length; i++)
            if (array[position + i] != candidate[i])
                return false;

        return true;
    }

    static bool IsEmptyLocate (byte[] array, byte[] candidate)
    {
        return array == null
            || candidate == null
            || array.Length == 0
            || candidate.Length == 0
            || candidate.Length > array.Length;
    }

    static void Main()
    {
        var data = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
        var pattern = new byte[] { 12, 3, 5, 76, 8, 0, 6, 125 };

        foreach (var position in data.Locate(pattern))
            Console.WriteLine(position);
    }
}

Edit (by IAbstract) - moving contents of post here since it is not an answer

Out of curiosity, I've created a small benchmark with different answers.

Here are the results for a million iterations:

solution [Locate]:            00:00:00.7714027
solution [FindAll]:           00:00:03.5404399
solution [SearchBytePattern]: 00:00:01.1105190
solution [MatchBytePattern]:  00:00:03.0658212
like image 116
Jb Evain Avatar answered Oct 14 '22 08:10

Jb Evain


Use LINQ Methods.

public static IEnumerable<int> PatternAt(byte[] source, byte[] pattern)
{
    for (int i = 0; i < source.Length; i++)
    {
        if (source.Skip(i).Take(pattern.Length).SequenceEqual(pattern))
        {
            yield return i;
        }
    }
}

Very simple!

like image 36
YujiSoftware Avatar answered Oct 14 '22 07:10

YujiSoftware