Using LINQ to search a byte array for all subarray

Question

I'm dealing with a COM port application and we have a defined variable-length packet structure that I'm talking to a micro-controller with. The packet has delimiters for the start and stop bytes. The trouble is that sometimes the read buffer can contain extraneous characters. It seems like I'll always get the whole packet, just some extra chatter before/after the actual data. So I have a buffer that I append data to whenever new data is received from the COM port. What is the best way to search this buffer for any possible occurrences of my packet? For example:

Say my packet delimiter is 0xFF and I have an array as such

{ 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 }

How can I create a function/LINQ-statment that returns all subarrays that start and end with the delimiter (almost like a sliding-correlator with wildcards)?

The sample would return the following 3 arrays:

{0xFF, 0x02, 0xDA, 0xFF}, {0xFF, 0x55, 0xFF}, and
{0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF}

Answer 1

You could do this using a Linq aggregator, but it's much less straightforward than the other solutions suggested here, also had to add a special case to cover extending already completed arrays as you suggested above.

byte[] myArray = new byte[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
var arrayList = myArray.Aggregate(
                new { completedLists = new List<List<byte>>(), 
                      activeList = new List<byte>() },
                (seed, s) =>
                {
                    if (s == 0xFF)
                    {
                        if (seed.activeList.Count == 0)
                        {
                            seed.activeList.Add(s);
                        }
                        else
                        {
                            seed.activeList.Add(s);
                            var combinedLists = new List<List<byte>>();

                            foreach (var l in seed.completedLists)
                            {
                                var combinedList = new List<byte>(l);
                                combinedList.AddRange(seed.activeList.Skip(1));
                                combinedLists.Add(combinedList);
                            }
                            seed.completedLists.AddRange(combinedLists);
                            seed.completedLists.Add(new List<byte>(seed.activeList));
                            seed.activeList.Clear();
                            seed.activeList.Add(s);
                        }
                    }
                    else
                    {
                        if (seed.activeList.Count > 0)
                            seed.activeList.Add(s);
                    }
                    return seed;
                }).completedLists;

Answer 2

While Trystan's answer is technically correct, he's making lots of copies of the original array all at once. If the starting array is large and has a bunch of delimiters, that gets huge quickly. This approach avoids the massive memory consumption by using only the original array and an array for the current segment being evaluated.

public static List<ArraySegment<byte>> GetSubArrays(this byte[] array, byte delimeter)
{
    if (array == null) throw new ArgumentNullException("array");

    List<ArraySegment<byte>> retval = new List<ArraySegment<byte>>();

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == delimeter)
        {
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[j] == delimeter)
                {
                    retval.Add(new ArraySegment<byte>(array, i + 1, j - i - 1));
                }
            }
        }
    }

    return retval;
}

Can be used as such:

static void Main(string[] args)
{
    byte[] arr = new byte[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
    List<ArraySegment<byte>> retval = GetSubArrays(arr, 0xFF);

    // this also works (looks like LINQ):
    //List<ArraySegment<byte>> retval = arr.GetSubArrays(0xFF);

    byte[] buffer = new byte[retval.Select(x => x.Count).Max()];
    foreach (var x in retval)
    {
        Buffer.BlockCopy(x.Array, x.Offset, buffer, 0, x.Count);
        Console.WriteLine(String.Join(", ", buffer.Take(x.Count).Select(b => b.ToString("X2")).ToArray()));
    }


    Console.ReadLine();
}

Answer 3

I wouldn't try to do this with linq so here's a regular method that returns the same output as you wanted.

public List<byte[]> GetSubArrays(byte[] array, byte delimeter)
{
  if (array == null) throw new ArgumentNullException("array");

  List<byte[]> subArrays = new List<byte[]>();

  for (int i = 0; i < array.Length; i++)
  {
    if (array[i] == delimeter && i != array.Length - 1)
    {
      List<byte> subList = new List<byte>() { delimeter };

      for (int j = i+1; j < array.Length; j++)
      {
        subList.Add(array[j]);
        if (array[j] == delimeter)
        {
          subArrays.Add(subList.ToArray());
        }
      }
    }
  }

  return subArrays;
}

If it must be an in-place lambda expression, then just change the first line to (byte[] array, byte delimeter) => (without the method modifiers and name) and call it that way.

Answer 4

Here's how you can do this using LINQ ...

int[] list = new int[] { 0x00, 0xFF, 0x02, 0xDA, 0xFF, 0x55, 0xFF, 0x04 };
int MAXLENGTH = 10;

var windows = list.Select((element, i) => list.Skip(i).Take(MAXLENGTH));
var matched = windows.Where(w => w.First() == 0xFF);
var allcombinations = matched.SelectMany(m => Enumerable.Range(1, m.Count())
          .Select(i => m.Take(i)).Where(x => x.Count() > 2 && x.Last() == 0xFF));

Or using indexes:

int length = list.Count();
var indexes = Enumerable.Range(0, length)
              .SelectMany(i => Enumerable.Range(3, Math.Min(length-i, MAXLENGTH))
              .Select(count => new {i, count}));
var results = indexes.Select(index => list.Skip(index.i).Take(index.count))
              .Where(x => x.First() == 0xFF && x.Last() == 0xFF);

Answer 5

Although the delimiter structure seems a bit vague, I would not use linq and do something like below (no extensive tests performed). It will return all subsets (of bytes surrounded by the delimiter), without including the delimiter (it's a given anyway, why include it?). It also does not return the union of the results, but that can always be assembled manually.

public IEnumerable<byte[]> GetArrays(byte[] data, byte delimiter)
{
    List<byte[]> arrays = new List<byte[]>();
    int start = 0;
    while (start >= 0 && (start = Array.IndexOf<byte>(data, delimiter, start)) >= 0)
    {
        start++;
        if (start >= data.Length - 1)
        {
            break;
        }

        int end = Array.IndexOf<byte>(data, delimiter, start);
        if (end < 0)
        {
            break;
        }

        byte[] sub = new byte[end - start];
        Array.Copy(data, start, sub, 0, end - start);
        arrays.Add(sub);
        start = end;
    }

    return arrays;
}

Answer 6

If you really want to use LINQ, this should work quite fast (even if not as fast as a good-old for loop):

public static IEnumerable<T[]> GetPackets<T>(this IList<T> buffer, T delimiter)
{
    // gets delimiters' indexes
    var delimiterIdxs = Enumerable.Range(0, buffer.Count())
                                  .Where(i => buffer[i].Equals(delimiter))
                                  .ToArray();

    // creates a list of delimiters' indexes pair (startIdx,endIdx)
    var dlmtrIndexesPairs = delimiterIdxs.Take(delimiterIdxs.Count() - 1)
                                         .SelectMany(
                                                     (startIdx, idx) => 
                                                     delimiterIdxs.Skip(idx + 1)
                                                                  .Select(endIdx => new { startIdx, endIdx })
                                                    );
    // creates array of packets
    var packets = dlmtrIndexesPairs.Select(p => buffer.Skip(p.startIdx)
                                                      .Take(p.endIdx - p.startIdx + 1)
                                                      .ToArray())
                                   .ToArray();

    return packets;
}