How to read data from serial port into packets?

[P1X3]

I need a simple sniffer (for now) that reads data from serial port and parses it into packets. Each packet is has following structure:

[src] [size] [dest] [data] [xor checksum]

Here are the issues I have with this task

1. There are no start or end identifiers, therefore I can't wait for specific byte before beginning packet parse process.
2. Data comes in chunks which creates multiple issues:
   1. Need for a buffer, which then can be used to parse packets from.
   2. Program can start receiving data in middle of chunk/packet.

 

What can I do in this situation? 

[wpirobotbuilder]

We need more information than that. Is this being done on a PC or a microprocessor?

 

What is the structure of src?

 

Also, why is there no start/end identifier for the serial protocol? Is the process synchronous?

[WanderingFool]

Well there is probably an actual proper way of doing this, but my stopgap type of solution would be to exploit the xor checksum (Assuming your packets are the same size)

 

(This is probably effective in the event that the packets will always be sent with the bytes aligned correctly so you don't have to bit shift from your input data)

 

say you read in [src as byte] [des as byte] [checksum as byte] just look at the first 3 bytes you get and see if they are valid...if not move one byte over and keep going until you find a valid one...keep checking the data though (e.g. collect enough for 4 or 5 valid packets in the data, then keep shifting until there is only one shift that fits...if there are multiple shifts possible then keep collecting more packet data until only one is possible)

e.g.

Sending 8 7 (15 is the checksum) then 15 240 (255 checksum), 15 15 0, 8 7 15

00001000 00000111 00001111 00001111 11110000 11111111 00001111 00001111 00000000 00001000 00000111 00001111

   

Assume you start reading at 00001111 (the third byte) (shift of 0 at the moment) 00001111 00001111 11110000 11111111 00001111 00001111 00000000 00001000 00000111 00001111

shift 0: 00001111 00001111 11110000 (Checksum doesn't match)

shift 1: 00001111 11110000 11111111 (Valid) <-- if this is truly valid shift 4, 7, 10, 13, etc... should be valid as well..this is ultimately the answer (each packet is 3 bytes long, so +3 to each shift to get next valid packet)

shift 2: 11110000 11111111 00001111 (valid) <-- if this is truly valid shift 5, 8, 11, 14, etc... should be valid as well

shift 4: 00001111 00001111 00000000 (valid) (shift 1 is not broken)

shift 5: 00001111 00000000 00001000 (invalid) (since this is invalid shift 2 cannot be valid)

 

So in this example when you started to read you could resolve the problem with only receiving 3.333 packets (since you started reading half way through the first packet).  If you keep finding valid packets you would just have to keep reading in the continuous stream until you can deduce where the starting point is correctly.  Probably should note this is guaranteed not to miss a valid packet...but this is not guaranteed to find a valid packet (you could craft an example which could have 2 or more potentially valid packets constantly no matter how big of sample size you choose)

 

Anyways that is just my 2 cents on this situation, there is probably a way to synchronize your data better though....but in theory this could work (again this assumes after you start getting data it is a constant stream).

 

In the event the packet sizes could change, then I would recommend giving more information as this method will not necessarily work

 

[P1X3]

Well there is probably an actual proper way of doing this, but my stopgap type of solution would be to exploit the xor checksum (Assuming your packets are the same size)

 

(This is probably effective in the event that the packets will always be sent with the bytes aligned correctly so you don't have to bit shift from your input data)

 

say you read in [src as byte] [des as byte] [checksum as byte] just look at the first 3 bytes you get and see if they are valid...if not move one byte over and keep going until you find a valid one...keep checking the data though (e.g. collect enough for 4 or 5 valid packets in the data, then keep shifting until there is only one shift that fits...if there are multiple shifts possible then keep collecting more packet data until only one is possible)

e.g.

Sending 8 7 (15 is the checksum) then 15 240 (255 checksum), 15 15 0, 8 7 15

00001000 00000111 00001111 00001111 11110000 11111111 00001111 00001111 00000000 00001000 00000111 00001111

   

Assume you start reading at 00001111 (the third byte) (shift of 0 at the moment) 00001111 00001111 11110000 11111111 00001111 00001111 00000000 00001000 00000111 00001111

shift 0: 00001111 00001111 11110000 (Checksum doesn't match)

shift 1: 00001111 11110000 11111111 (Valid) <-- if this is truly valid shift 4, 7, 10, 13, etc... should be valid as well..this is ultimately the answer (each packet is 3 bytes long, so +3 to each shift to get next valid packet)

shift 2: 11110000 11111111 00001111 (valid) <-- if this is truly valid shift 5, 8, 11, 14, etc... should be valid as well

shift 4: 00001111 00001111 00000000 (valid) (shift 1 is not broken)

shift 5: 00001111 00000000 00001000 (invalid) (since this is invalid shift 2 cannot be valid)

 

So in this example when you started to read you could resolve the problem with only receiving 3.333 packets (since you started reading half way through the first packet).  If you keep finding valid packets you would just have to keep reading in the continuous stream until you can deduce where the starting point is correctly.  Probably should note this is guaranteed not to miss a valid packet...but this is not guaranteed to find a valid packet (you could craft an example which could have 2 or more potentially valid packets constantly no matter how big of sample size you choose)

 

Anyways that is just my 2 cents on this situation, there is probably a way to synchronize your data better though....but in theory this could work (again this assumes after you start getting data it is a constant stream).

 

In the event the packet sizes could change, then I would recommend giving more information as this method will not necessarily work

 

Sadly packets vary in size.

 

Source, size, destination, and xor are 4 different bytes. Size is the size of data/payload + size of destination and size of xor. So In packet with 1 byte payload, the size will be 3 bytes, however the size of whole packet will be 5 bytes. This is somewhat irrelevant, but figured I would post.

 

The hardest part is to find first packet, after that it pretty straight on. I am a bit confused about what you are suggesting, but it gave me an idea.

 

Source and destination are pre-defined, so I can take first byte and check if it's in the list. If not then assume packet starts at 2nd byte, and do same check.

If above mentioned condition is met, then assume byte after that is the size, and byte after size is destination. So check if destination byte is in the list. If not then go back to statement above.

If first and third bytes are in the list of valid sources&destinations, then it's semi-safe to assume that byte in between is size of data. Therefore proceed to read the data and checking xor checksum. If xor checksum is correct then first valid packet is found, proceed to parse other packets (catch up with buffer).

If xor is not valid then shift start offset, until last statement is true.

 

It just might work. However I wonder what I should use for this buffer.

 

Queue? Can peek at elements, and pop top byte if shift is needed, but unsure what to do when program is half way through reading packet and rest of the packet hasnt arrived yet.

 

 

Edit;

Here is the monstrosity.

        private void ProcessQueue()        {            if (!packetFound)            {                // Minumum packet size is 5                if (readQueue.Count > 5)                {                    // Check if top byte is defined as a valid module                    if (Enum.IsDefined(typeof(CarModules), readQueue.Peek()) && Enum.IsDefined(typeof(CarModules), readQueue.ElementAt(2)))                    {                        byte length = readQueue.ElementAt(1);                        //Maximum alloved size is 32                        if (length <= 32)                        {                            // If expecting more data than what there is then return                            if (length > readQueue.Count)                                return;                            byte xorTest = 0;                            xorTest ^= readQueue.Peek();                            xorTest ^= length;                            xorTest ^= readQueue.ElementAt(2);                            for (int i = 0; i < length - 2; i++)                            {                                xorTest ^= readQueue.ElementAt(3 + i);                            }                            byte xor = readQueue.ElementAt(length + 1);                            if (xor == xorTest)                            {                                packetFound = true;                                ParsePacket();                                return;                            }                        }                    }                    readQueue.Dequeue();                }            }            else            {                ParsePacket();            }        }        private void ParsePacket()        {            IBusDataPacket packet = new IBusDataPacket();            byte xorTest = 0;            packet.source = (CarModules)readQueue.Dequeue();            packet.length = readQueue.Dequeue();            packet.destination = (CarModules)readQueue.Dequeue();            xorTest ^= (byte)packet.source;            xorTest ^= packet.length;            xorTest ^= (byte)packet.destination;            packet.data = new byte[packet.length - 2];            for (int i = 0; i < packet.length - 2; i++)            {                packet.data[i] = readQueue.Dequeue();                xorTest ^= packet.data[i];            }            packet.xor = readQueue.Dequeue();            if (xorTest == packet.xor)            {                packets.Add(packet);            }            else            {                packetFound = false;            }        }

If this does work then I will have to run parsing in separate process maybe.

[random314]

So do you want something like this

private void NextByte() {	readQueue.pop();	ProcessQueue();}private void WaitOnQueue(int minimumBytes){	while(readQueue.Count < minimumBytes) 	{		// Maybe sleep the thread here or something	}}private void ProcessQueue(){	if (packetFound) {		ParsePacket();	}		if (!IsValidSource(readQueue.Peek()) {		NextByte();	}		// Minumum packet size is 5	WaitOnQueue(5);	// Check if top byte is defined as a valid module	if (Enum.IsDefined(typeof(CarModules), readQueue.Peek()) && Enum.IsDefined(typeof(CarModules), readQueue.ElementAt(2)))	{		byte length = readQueue.ElementAt(1);		//Maximum allowed size is 32		if (length > 32)		{			NextByte();		}				// If expecting more data than what there is then return		if (length > readQueue.Count) {			WaitOnQueue(readQueue.Count - length);		}		byte xorTest = 0;		xorTest ^= readQueue.Peek();		xorTest ^= length;		xorTest ^= readQueue.ElementAt(2);		for (int i = 0; i < length - 2; i++)		{			xorTest ^= readQueue.ElementAt(3 + i);		}		byte xor = readQueue.ElementAt(length + 1);		if (xor == xorTest)		{			packetFound = true;			ParsePacket();			return;		} else {			NextByte();		}	}	readQueue.Dequeue();		}

Essentially you should do two things

• If you encounter a condition where there aren't enough bytes in the queue you should wait until there are enough bytes (exactly how you do this I have no idea). 
• If you encounter a condition where the packet appears to be malformed, pop the current byte off the queue and try to process the queue again

It should be noted that if you do this, you have no way to detect packets that are actually malformed

Edited September 25, 2013 by random314

[P1X3]

So do you want something like this

private void NextByte() {	readQueue.pop();	ProcessQueue();}private void WaitOnQueue(int minimumBytes){	while(readQueue.Count < minimumBytes) 	{		// Maybe sleep the thread here or something	}}private void ProcessQueue(){	if (packetFound) {		ParsePacket();	}		if (!IsValidSource(readQueue.Peek()) {		NextByte();	}		// Minumum packet size is 5	WaitOnQueue(5);	// Check if top byte is defined as a valid module	if (Enum.IsDefined(typeof(CarModules), readQueue.Peek()) && Enum.IsDefined(typeof(CarModules), readQueue.ElementAt(2)))	{		byte length = readQueue.ElementAt(1);		//Maximum allowed size is 32		if (length > 32)		{			NextByte();		}				// If expecting more data than what there is then return		if (length > readQueue.Count) {			WaitOnQueue(readQueue.Count - length);		}		byte xorTest = 0;		xorTest ^= readQueue.Peek();		xorTest ^= length;		xorTest ^= readQueue.ElementAt(2);		for (int i = 0; i < length - 2; i++)		{			xorTest ^= readQueue.ElementAt(3 + i);		}		byte xor = readQueue.ElementAt(length + 1);		if (xor == xorTest)		{			packetFound = true;			ParsePacket();			return;		} else {			NextByte();		}	}	readQueue.Dequeue();		}

Essentially you should do two things

• If you encounter a condition where there aren't enough bytes in the queue you should wait until there are enough bytes (exactly how you do this I have no idea). 
• If you encounter a condition where the packet appears to be malformed, pop the current byte off the queue and try to process the queue again

It should be noted that if you do this, you have no way to detect packets that are actually malformed

 

Yup something like that. I ended up testing more optimized version since I will be running this in smallest arduino board. (Of course I will rewrite it in C++)

Can't believe a thing that seemed so complicated at first can be worked out so simply. Also turns out circular queue buffer array thing that I did in college is actually useful in my case.

Kudos to my Data structures professor.