Consistent Overhead Byte Stuffing (COBS)

The purpose of byte stuffing is to convert data packets into a form suitable for transmission over a serial medium, UART in the KiNOS case. When packets are sent over a serial medium there needs to be some way to tell where one packet ends and the next begins, particularly after errors, and this is typically done by using a special reserved value to indicate packet boundaries.

Byte stuffing ensures, at the cost of a potential increase in packet size, that this reserved value does not inadvertently appear in the body of any transmitted packet. In general, some overhead (additional bytes transmitted over the serial medium) is inevitable if we are to perform byte stuffing without loss of information.

A little effort to minimize the worst-case overhead has been made in this algorithm called “Consistent Overhead Byte Stuffing (COBS)“. Refer to Draft-ietf-pppext-cobs-00 for more detailed information.

In KiNOS stack the special reserved value is 0x00 byte and it is used as UART frame start delimiter. COBS algorithm first takes its input data and logically appends a single zero byte at the end (it is not necessary that the encoding routine actually adds this zero byte to the end of the packet in the memory, it simply has to behave as if the added zero were there).

Then COBS locates all the zero bytes in the frame (including the added one), and divides the packet at these boundaries into zero-terminated chunks. Every zero-terminated chunk contains one zero byte and it is always at the end of the chunk (trailing zero). A chunk may be as short as one byte (i.e. a chunk containing just a solitary zero byte) or as long as an entire frame.

Finally, COBS encodes (replace) each zero-terminated chunk using one COBS code block followed by the chunk non-zero bytes and eliminates the zero byte. This method makes that all zero bytes contained in the frame disappear and then only a zero is added at the beginning as (special reserved value) start delimiter of the frame.  This encoding is totally reversible using a COBS decode function.

Apart from that, KiNOS stack also implements Zero-pair and Zero-run elimination (COBS extensions) in addition of the basic COBS to improve byte compression when two or more zeros are found together in the frame. So the COBS (ZPE-ZRE) code blocks used are: