Extracting data packet out of byte buffer

Question

I have a buffer of length 256 that receives byte sequences from bluetooth. The actual packet that I need to extract is starting and ending with byte 126. I want to extract the latest packet in the buffer using LINQ.

What I am doing now is checking for last index of 126 and then count backward until I reach another 126. There are some pitfalls as well, for example, two adjacent packet can result in two bytes of 126 next to eachother.

Here is a sample of buffer:

126   6 0   5   232 125 93  126 126 69  0 
0   1   0   2   2   34  6   0   5   232 125 
93  126 126 69  0   0   1   0   2   2   34 
6   0   5   232 125 93  126 126 69  0   0 
1   0   2   2   34  6   0   5   232 125 93 
126 126 69  0   0

So the information I have is:

• Packet starts and ends with byte value of 126
• the next byte after the starting index does have value of 69
• the 3 last byte right befor the ending byte of 126 is a CRC of the whole packet that I know how to calculate, so after extracting a packet I can check this CRC to see if I have the right packet

So at the end I want to have an array or list that contains the correct packet. for example:

126 69  0  0   1   0   2   2   34  6   0   5   232 125 93 126

Can you give me a fast soloution of extracting this packet from buffer?

This is what I'v tried so far....it fails as it cant really return the correct packet I am looking for:

var data = ((byte[])msg.Obj).ToList(); //data is the buffer 

byte del = 126; //delimeter or start/end byte
var lastIndex = data.LastIndexOf(del);
var startIndex = 0;
List<byte> tos = new List<byte>(); //a new list to store the result (packet)    

//try to figure out start index                            
if(data[lastIndex - 1] != del)
{
    for(int i = lastIndex; i > 0; i--)
    {
        if(data[i] == del)
        {
            startIndex = i;
        }
    }

    //add the result in another list
    for(int i = 0; i <= lastIndex - startIndex; i++)
    {
        tos.Add(data[i]);
    }

    string shit = string.Empty;

    foreach (var b in tos)
        shit += (int)b + ", ";

   //print result in  a textbox
    AddTextToLogTextView(shit + "\r\n");
}

Answer 1

Solutions

I've prepared three possible solution of taking the last packet from input buffor:

Using LINQ

public static byte[] GetLastPacketUsingLINQ(byte[] input, byte delimiter)
{
    var part = input.Reverse()
                    .SkipWhile(i => i != delimiter)
                    .SkipWhile(i => i == delimiter)
                    .TakeWhile(i => i != delimiter)
                    .Reverse();

    return (new byte[] { delimiter }).Concat(part).Concat(new byte[] { delimiter }).ToArray();
}

Using string.Split

public static byte[] GetLastPacketUsingString(byte[] input, byte delimiter)
{
    var encoding = System.Text.Encoding.GetEncoding("iso-8859-1");
    string inputString = encoding.GetString(input);
    var parts = inputString.Split(new[] { (char)delimiter }, StringSplitOptions.RemoveEmptyEntries);

    return encoding.GetBytes((char)delimiter + parts[parts.Length - 2] + (char)delimiter);
}

Using while loop and indexers

public static byte[] GetLastPacketUsingIndexers(byte[] input, byte delimiter)
{
    int end = input.Length - 1;
    while (input[end--] != delimiter) ;

    int start = end - 1;
    while (input[start--] != delimiter) ;

    var result = new byte[end - start];
    Array.Copy(input, start + 1, result, 0, result.Length);
    return result;
}

Performance

I've also performed some very simple performance tests. Here are the results:

LINQ version result:
126 69 0 0 1 0 2 2 34 6 0 5 232 125 93 126

String version result:
126 69 0 0 1 0 2 2 34 6 0 5 232 125 93 126

Indexers version result:
126 69 0 0 1 0 2 2 34 6 0 5 232 125 93 126

LINQ version time: 64ms (106111 ticks)
String version time: 2ms (3422 ticks)
Indexers version time: 1ms (2359 ticks)

Conclusion

As you can see, the simplest one is also the best one here.

You may think that LINQ is an answer for every problem, but some time it's really better idea to write simpler solution manually instead of using LINQ methods.

Answer 2

Using LINQ this can be done in a single line of code if the following two rules can be applied to the buffer:

• The buffer contains at least one complete package surrounded by the given delimiter.
• Each packet contains at least one byte of data.

Here is the code:

var data = (byte[])msg.Obj;
byte delimiter = 126;

var packet = data.Reverse()
                 .SkipWhile(b => b != delimiter)
                 .SkipWhile(b => b == delimiter)
                 .TakeWhile(b => b != delimiter)
                 .Reverse();

(Ok, this was more than a single line because I splitted it into multiple lines for better readability.)

EDIT: Removed the call to Take(1) because that would always return an empty sequence. The result however doesn't contain delimiter this way.

---

And here is how it works:

Since we want to find the last packet we can reverse the data:

var reversed = data.Reverse();

The buffer can end with a packet which is not complete yet. So let's skip that:

reversed = reversed.SkipWhile(b => b != delimiter);

reversed is now either empty or it starts with delimiter. Since we assumed that the buffer always contains at least one complete packet we can already take the next byte for our result because we know it is the delimiter:

var packet = reversed.Take(1);

In the sequence we can now skip one byte. If the delimiter we found was actually the start of a new packet the remaining sequence will start with another delimiter so we have to skip that also:

reversed = reversed.Skip(1);
if (reversed.First() == delimiter)
{
    reversed.Skip(1);
}

Since we know that a packet can not be empty because it contains a 3 bytes CRC we could have written:

reversed = reversed.SkipWhile(b => b == delimiter);

Now the actual data follows:

packet = packet.Concat(reversed.TakeWhile(b => b != delimiter));
reversed = reversed.SkipWhile(b => b != delimiter);

The next byte is the delimiter which marks the start of the packet:

packet = packet.Concat(reversed.Take(1));

The last thing to do is to reverse the result again:

packet = packet.Reverse();

---

Maybe you want to put this into a method:

public IEnumerable<byte> GetPacket(byte[] data, byte delimiter)
{
    yield return delimiter;

    foreach (byte value in data.Reverse()
                               .SkipWhile(b => b != delimiter)
                               .SkipWhile(b => b == delimiter)
                               .TakeWhile(b => b != delimiter))
    {
        yield return value;
    }

    yield return delimiter;
}

You will have to call Reverse on the return value of this method.

---

If performance matters you can use the same algorithm on the underlying array. This way it will be about 20 times faster:

int end = data.Length - 1;
while (data[end] != delimiter)
    end--;

while (data[end] == delimiter)
    end--;

int start = end;
while (data[start] != delimiter)
    start--;

byte[] result = new byte[end - start + 2];  // +2 to include delimiters
Array.Copy(data, start, result, 0, result.Length);