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

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);

Answer 2

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 3

There actually are various ways to solve your question, the simplest idea is detect double 126(0x7e), and doesn't matter other things such like CRC.

The basic implemention of this concept would be like this

• Code as simple

  var list=new List<byte[]>();
  int i=0, j=0;
  for(; i<data.Length; ++i)
      if(i>0&&0x7e==data[i]&&0x7e==data[i-1]) {
          list.Add(data.Skip(j).Take(i-j).ToArray());
          j=i;
      }
  list.Add(data.Skip(j).Take(i-j).ToArray());
  

Base on my old answer of Konami Code in C#, and it even used to solve this question: Double characters shown when typing special characters while logging keystrokes in c#.

• Code with a sequence detector

  public partial class TestClass {
      public static void TestMethod() {
          var data=(
              new[] { 
                      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 
                  }).Select(x => (byte)x).ToArray();
  
          var list=new List<List<byte>>();
  
          foreach(var x in data) {
              if(list.Count<1||SequenceCapturer.Captured((int)x))
                  list.Add(new List<byte>());
  
              list.Last().Add(x);
          }
  
          foreach(var byteList in list)
              Debug.Print("{0}", byteList.Select(x => x.ToString("x2")).Aggregate((a, b) => a+"\x20"+b));
      }
  }
  
  public class SequenceCapturer {
      public int Count {
          private set;
          get;
      }
  
      public int[] Sequence {
          set;
          get;
      }
  
      public bool Captures(int value) {
          for(var i=Sequence.Length; i-->0; ) {
              if(Sequence[i]!=value) {
                  if(0==i)
                      Count=0;
  
                  continue;
              }
  
              if(Count!=i)
                  continue;
  
              ++Count;
              break;
          }
  
          var x=Sequence.Length==Count;
          Count=x?0:Count;
          return x;
      }
  
      public SequenceCapturer(int[] newSequence) {
          Sequence=newSequence;
      }
  
      public SequenceCapturer()
          : this(new[] { 0x7e, 0x7e }) {
      }
  
      public static bool Captured(int value) {
          return Instance.Captures(value);
      }
  
      public static SequenceCapturer Instance=new SequenceCapturer();
  }
  

Or if you would like to write it full in Linq, you might want to try the following. You even don't need to use List, packetArray gives you an array of byte arrays directly.

The lets are intended to break the code into lines, otherwise it would be an extreme long statement in one line. If you consider one line is the best, then I will.

• Code of packetArray

  var packetArray=(
      from sig in new[] { new byte[] { 0x7e, 0x7e } }
      let find=new Func<byte[], int, IEnumerable<byte>>((x, i) => x.Skip(i).Take(sig.Length))
      let isMatch=new Func<IEnumerable<byte>, bool>(sig.SequenceEqual)
      let filtered=data.Select((x, i) => 0==i||isMatch(find(data, i-1))?i:~0)
      let indices=filtered.Where(i => ~0!=i).Concat(new[] { data.Length }).ToArray()
      from index in Enumerable.Range(1, indices.Length-1)
      let skipped=indices[index-1]
      select data.Skip(skipped).Take(indices[index]-skipped).ToArray()).ToArray();
  

• Code for output

  foreach(var byteArray in packetArray)
      Debug.Print("{0}", byteArray.Select(x => x.ToString("x2")).Aggregate((a, b) => a+"\x20"+b));
  

However, even in the same concept of solution, there would be various ways as I mentioned before. I'd strongly recommend that don't involve additional conditions like something about CRC, which might make things more complicated.

Answer 4

Since you're looking for the last packet, it's much easier to reverse the byte[] and look for the first packet. Your two packet delimiters are not just 126. They are 126, 69 for the start and 126, 126 for the end unless the end of the packet is the last byte recieved, which makes the end delimiter 126.

I would suggest using a method simular to this:

public static byte[] GetMessage(byte[] msg)
    {
        //Set delimiters
        byte delimit = 126;
        byte startDelimit = 69;

        //Reverse the msg so we can find the last packet
        List<byte> buf = msg.Reverse().ToList();

        //set indices to impossible values to check for failures
        int startIndex = -1;
        int endIndex = -1;
        //loop through the message
        for (int i = 0; i < buf.Count - 1; i++)
        {
            //find either a double 126, or 126 as the last byte (message just ended)
            if (buf[i] == delimit && (buf[i + 1] == delimit || i == 0))
            {
                if (i == 0)
                {
                    startIndex = i;
                    i++;
                }
                else
                {
                    startIndex = i + 1;
                    i += 2;
                }
                continue;
            }
            //Only process if we've found the start index
            if (startIndex != -1)
            {
                //check if the byte is 69 followed by 126
                if (buf[i] == startDelimit && buf[i + 1] == delimit)
                {
                    endIndex = i + 1;
                    break;
                }
            }
        }
        //make sure we've found a message
        if (!(startIndex == -1 || endIndex==-1))
        {
            //get the message and reverse it to be the original packet
            byte[] revRet = new byte[endIndex - startIndex];
            Array.Copy(buf.ToArray(), startIndex, revRet, 0, endIndex - startIndex);

            return revRet.Reverse().ToArray();
        }
        return new byte[1];
    }

I'm not totally sure if the indices of the copy are completely correct, but this should be the jist of it.

Answer 5

since you may receive incomplete data, you must store the last incomplete buffer.

this is sample case, First Receive :

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

the second stream :

69,  0,   0 , 1,   0,  2,   2,   34,  6,   0, 126

and the code:

    List<byte> lastBuf = new List<byte>();

    List<byte[]> Extract(byte[] data, byte delim)
    {
        List<byte[]> result = new List<byte[]>();

        for (int i = 0; i < data.Length; i++)
        {
            if (lastBuf.Count > 0)
            {
                if(data[i] == delim)
                {
                    result.Add(lastBuf.ToArray());
                    lastBuf.Clear();
                }
                else
                {
                    lastBuf.Add(data[i]);
                }
            }
            else 
            { 
                if(data[i] != 126)
                {
                    lastBuf.Add(data[i]);
                }
            }
        }

        return result;
    }

result :