Implementing UART data packets with Consistent Overhead Byte Stuffing (COBS)

[voltsandjolts]

I've started this thread to discuss implementations of Consistent Overhead Byte Stuffing (COBS) as described in this Cheshire & Baker paper:
http://www.stuartcheshire.org/papers/COBSforToN.pdf

COBS provides a method of transferring data messages containing arbitrary data; ascii, binary whatever.
The COBS encoding process removes all 0x00 bytes from within a message, which then allows the use of 0x00 to delimit the data frames on-the-wire.
The neat thing is the encoding process only adds a few extra bytes.
I'm interested in using it for PC to microcontroller communications over UART, with Python3 on the PC side and C on the microcontroller.

Let's start with some Python functions for encoding and decoding COBS with some test routines.

Typical overheads (not including 0x00 delimiting bytes) for random data messages:

Code: [Select]

Test            Message length          Encoded length          Overhead
0               1945                    1949                    4       (0.21%)
1               4075                    4085                    10      (0.25%)
2               414                     416                     2       (0.48%)
3               7096                    7115                    19      (0.27%)
4               3081                    3088                    7       (0.23%)
5               217                     218                     1       (0.46%)
6               9505                    9530                    25      (0.26%)
7               979                     982                     3       (0.31%)
8               1559                    1563                    4       (0.26%)
9               7096                    7114                    18      (0.25%)
10              533                     536                     3       (0.56%)
11              4740                    4750                    10      (0.21%)
12              5148                    5157                    9       (0.17%)
13              9959                    9981                    22      (0.22%)
14              9782                    9803                    21      (0.21%)
15              2078                    2084                    6       (0.29%)
16              8388                    8408                    20      (0.24%)
17              7608                    7627                    19      (0.25%)
18              37                      38                      1       (2.70%)
19              8280                    8300                    20      (0.24%)
20              7271                    7285                    14      (0.19%)
21              6456                    6472                    16      (0.25%)
22              9530                    9548                    18      (0.19%)
23              8600                    8620                    20      (0.23%)
24              8253                    8273                    20      (0.24%)
25              6490                    6505                    15      (0.23%)
26              2947                    2956                    9       (0.31%)
27              5484                    5500                    16      (0.29%)
28              3241                    3249                    8       (0.25%)
29              5194                    5206                    12      (0.23%)
30              4958                    4970                    12      (0.24%)
31              8748                    8766                    18      (0.21%)
32              2487                    2494                    7       (0.28%)
33              2422                    2429                    7       (0.29%)
34              4950                    4959                    9       (0.18%)
35              6797                    6811                    14      (0.21%)
36              1784                    1788                    4       (0.22%)
37              2195                    2201                    6       (0.27%)
38              214                     215                     1       (0.47%)
39              2231                    2237                    6       (0.27%)
40              5498                    5512                    14      (0.25%)
41              5569                    5584                    15      (0.27%)
42              3729                    3737                    8       (0.21%)
43              174                     175                     1       (0.57%)
44              485                     487                     2       (0.41%)
45              3633                    3640                    7       (0.19%)
46              6284                    6302                    18      (0.29%)
47              971                     974                     3       (0.31%)
48              9973                    9997                    24      (0.24%)
49              474                     476                     2       (0.42%)

Run the attached Python program to try this for yourself.

[voltsandjolts]

From the above post, we have tested the encoder and decoder routines but we need to add a few more things to get something useful.

We need to append a zero byte to seperate and 'frame' the encoded messages.
In fact we should add a zero byte both at the end and at the start of the message, to flush any noise-induced bytes on the comms line between packets.

We also need to add a CRC check to the message prior to COBS encoding, for data integrity checking at the reciever.
If your microcontroller has a hardware CRC unit, it would be worth using that.
Here, I'll use CRC16.

So, attached is a Python program which will:

Accept an input message and append CRC16
COBS encode it
Add zero byte at the start and end of the encoded message for framing
Send the frame out through the selected serialport
**** Loopback your serial port, such that TX is shorted to RX****
Decoder receives the framed message, decodes and verifies CRC16

Run the attached Python program to try this for yourself.

[voltsandjolts]

Now we have a simple Python loopback test on the PC, lets tackle the microcontroller next.

The aim here is to get some code running in the microcontroller which will decode COBS frames from the PC,
verify the CRC, then send the same message back. We can then use the Python loopback test (in previous post) to check the microcontroller code.

I am using STMCube + free Keil for STM32L053, source code attached.

UART data from PC is received by DMA directly into a circular RAM buffer.
The background code polls the circular buffer for new bytes and pushes them through the COBS decoder.
When a complete frame has been received, the message CRC is checked.
If the CRC is OK, the message data is copied out and then COBS encoded and sent back to the PC.

The bulk of the code is in msgrx.c and msgtx.c
It should be fairly easy to port MCU of your choice.

Note about RAM Buffer Requirements

Receiving and decoding COBS is quite simple. You just need a RAM buffer big enough to store the decoded message (+CRC bytes).

Transmitting COBS is a little more tricky because you need to replace zero bytes with the distance to the next zero byte.
If the distance is more than 254 bytes, insert 0xFF, meaning the next COBS control byte is 255 bytes ahead.
I suppose there are three ways to handle this in RAM;

1/ Simplest way - have a buffer large enough to store the encoded message. Populate it and send with DMA or interrupt. For larger messages 4kB,8kB... maybe this gets too RAM hungry.

2/ Use a ringbuffer of at least 256 bytes. Populate the buffer with a bit of the message, send it, then continue encoding next bit of message etc. until whole message has been sent.

3/ Minimal RAM method would use more CPU time. Scan forward in the message to find the first zero, thats tells you the first COBS byte and then send the data up to that first zero. Then scan forward for next zero etc.

Edit:
2/ To save RAM, the message could be COBS encoded in-place, in it's own buffer. If the message started, say, 20 bytes into the buffer, the encoded frame could be built starting at the beginning of the buffer, then overwriting the message as you go.

Might be an interesting exercise to implement a minimal RAM COBS transmitter, hmm.

[voltsandjolts]

The above is minimal code just to demonstrate COBS in action.

What can you do with it?

Well, I think it's a great basis for creating your own UART control protocols.
If you like ASCII control commands, fine, just pass that to the COBS encoder to packetise it for you.
Want to use binary, thats fine too. Mix ASCII and binary if you like.
COBS just provides a nice transport layer - you are freed from the packet delimiter problems, so you can just concentrate on your protocol format.

On the Python side, the 'struct' module is a great help for converting Python variables to/from byte streams that can be sent over COBS.

[dietert1]

Thanks, very interesting.
For me the link to the original paper in your first message did not resolve well - let's try again:
http://www.stuartcheshire.org/papers/COBSforToN.pdf

Regards, Dieter

[GeorgeOfTheJungle]

It has already happened to me several times that in serial streams the Rx errors appear in the form of 0x00 characters, I don't know how or if this could affect the protocol but just in case I wanted to comment it.

[voltsandjolts]

2/ To save RAM, the message could be COBS encoded in-place, in it's own buffer. If the message started, say, 20 bytes into the buffer, the encoded frame could be built starting at the beginning of the buffer, then overwriting the message as you go.

Actually, this works, just a trivial change in the buffer declaration allows the tx message to be encoded in its own buffer. Saves quite a bit of RAM.
So now the 'cost' of using COBS for transmission and reception is just a handful of RAM bytes and some processor time.

In msgtx.c:

Code: [Select]

uint8_t msgtx_buf_dma[MAX_TX_MSG_LEN + MSG_FOOTER_LEN + COBS_FRAME_OVERHEAD]; /* COBS encoded message is in here for DMA transmission */
uint8_t *msgtx_buf = &msgtx_buf_dma[COBS_FRAME_OVERHEAD]; /* User puts message in here (gets overwritten with COBS encoded message) */

[TomS_]

It has already happened to me several times that in serial streams the Rx errors appear in the form of 0x00 characters, I don't know how or if this could affect the protocol but just in case I wanted to comment it.

I think this would be fine, especially if you are appending something like a CRC. Each time you encounter a 0, you would calculate the CRC of the received message, and if it doesn't match then you can discard.

If a single message has been broken up into multiple parts due to errors, the protocol will be able to eventually recover when the next full message comes through intact with a valid CRC.