Consistent Overhead Byte Stuffing

<h2 id="packet-framing-and-stuffing">Packet framing and stuffing</h2>
<p>When packetized data is sent over any serial medium, some <a href="/facts/Communications_protocol/5uady7cB">protocol</a> is required to demarcate packet boundaries. This is done by using a framing marker, a special bit-sequence or character value that indicates where the boundaries between packets fall. Data stuffing is the process that transforms the packet data before transmission to eliminate all occurrences of the framing marker, so that when the receiver detects a marker, it can be certain that the marker indicates a boundary between packets.
</p><p>COBS transforms an arbitrary string of bytes in the range [0,255] into bytes in the range [1,255]. Having eliminated all zero bytes from the data, a zero byte can now be used to unambiguously mark the end of the transformed data. This is done by appending a zero byte to the transformed data, thus forming a packet consisting of the COBS-encoded data (the <i><a href="/facts/Payload_(computing)/zN2Pgfq6">payload</a></i>) to unambiguously mark the end of the packet.
</p><p>(Any other byte value may be reserved as the packet delimiter, but using zero simplifies the description.)
</p>

<p>There are two equivalent ways to describe the COBS encoding process:
</p>
Prefixed block description
To encode some bytes, first append a zero byte, then break them into groups of either 254 non-zero bytes, or 0–253 non-zero bytes followed by a zero byte.  Because of the appended zero byte, this is always possible.
Encode each group by deleting the trailing zero byte (if any) and prepending the number of non-zero bytes, plus one.  Thus, each encoded group is the same size as the original, except that 254 non-zero bytes are encoded into 255 bytes by prepending a byte of 255.
As a special exception, if a packet ends with a group of 254 non-zero bytes, it is not necessary to add the trailing zero byte.  This saves one byte in some situations.
Linked list description
First, insert a zero byte at the beginning of the packet, and after every run of 254 non-zero bytes.  This encoding is obviously reversible.  It is not necessary to insert a zero byte at the end of the packet if it happens to end with exactly 254 non-zero bytes.
Second, replace each zero byte with the offset to the next zero byte, or the end of the packet.  Because of the extra zeros added in the first step, each offset is guaranteed to be at most 255.
<h2 id="encoding-examples">Encoding examples</h2>
<p>These examples show how various data sequences would be encoded by the COBS algorithm. In the examples, all bytes are expressed as <a href="/facts/Hexadecimal/02ohQW22">hexadecimal</a> values, and encoded data is shown with text formatting to illustrate various features:
</p>
<ul><li>Bold indicates a data byte which has not been altered by encoding. All non-zero data bytes remain unaltered.</li>
<li>Green indicates a zero data byte that was altered by encoding. All zero data bytes are replaced during encoding by the offset to the following zero byte (i.e. one plus the number of non-zero bytes that follow).  It is effectively a pointer to the next packet byte that requires interpretation: if the addressed byte is non-zero then it is the following group header byte zero data byte that points to the next byte requiring interpretation; if the addressed byte is zero then it is the end of packet.</li>
<li>Red is an overhead byte which is also a group header byte containing an offset to a following group, but does not correspond to a data byte.  These appear in two places: at the beginning of every encoded packet, and after every group of 254 non-zero bytes.</li>
<li>A blue zero byte appears at the end of every packet to indicate end-of-packet to the data receiver. This packet delimiter byte is not part of COBS proper; it is an additional framing byte that is appended to the encoded output.</li></ul>
<table><tbody><tr><th>Example</th><th>Unencoded data (hex)</th><th>Encoded with COBS (hex)</th></tr><tr><td>1</td><td>00</td><td>01 01 00</td></tr><tr><td>2</td><td>00 00</td><td>01 01 01 00</td></tr><tr><td>3</td><td>00 11 00</td><td>01 02  11 01  00</td></tr><tr><td>4</td><td>11 22 00 33</td><td>03 11 22 02 33 00</td></tr><tr><td>5</td><td>11 22 33 44</td><td>05 11 22 33 44 00</td></tr><tr><td>6</td><td>11 00 00 00</td><td>02 11 01 01 01 00</td></tr><tr><td>7</td><td>01 02 03 ... FD FE</td><td>FF 01 02 03 ... FD FE 00</td></tr><tr><td>8</td><td>00 01 02 ... FC FD FE</td><td>01 FF 01 02 ... FC FD FE 00</td></tr><tr><td>9</td><td>01 02 03 ... FD FE FF</td><td>FF 01 02 03 ... FD FE 02 FF 00</td></tr><tr><td>10</td><td>02 03 04 ... FE FF 00</td><td>FF 02 03 04 ... FE FF 01 01 00</td></tr><tr><td>11</td><td>03 04 05 ... FF 00 01</td><td>FE 03 04 05 ... FF 02 01 00</td></tr></tbody></table><p>
Below is a diagram using example 4 from above table, to illustrate how each modified data byte is located, and how it is identified as a data byte or an end of frame byte.</p>   [OHB]                                : Overhead byte (Start of frame)
     3+ -------------->|                : Points to relative location of first zero symbol
                       2+-------->|     : Is a zero data byte, pointing to next zero symbol
                                  [EOP] : Location of end-of-packet zero symbol.
     0     1     2     3     4    5     : Byte Position
     03    11    22    02    33   00    : COBS Data Frame
           11    22    00    33         : Extracted Data
     
OHB = Overhead Byte (Points to next zero symbol)
EOP = End Of Packet

<p>Examples 7 through 10 show how the overhead varies depending on the data being encoded for packet lengths of 255 or more.
</p>
<h2 id="implementation">Implementation</h2>
<p>The following code implements a COBS encoder and decoder in the C programming language, processing data byte by byte.
</p>
#include <stddef.h>
#include <stdint.h>
#include <assert.h>

/** COBS encode data to buffer
	@param data Pointer to input data to encode
	@param length Number of bytes to encode
	@param buffer Pointer to encoded output buffer
	@return Encoded buffer length in bytes
	@note Does not output delimiter byte
*/
size_t cobsEncode(const void *data, size_t length, uint8_t *buffer)
{
	assert(data && buffer);

uint8_t *encode = buffer; // Encoded byte pointer
	uint8_t *codep = encode++; // Output code pointer
	uint8_t code = 1; // Code value

for (const uint8_t *byte = (const uint8_t *)data; length--; ++byte)
	{
		if (*byte) // Byte not zero, write it
			*encode++ = *byte, ++code;

if (!*byte || code == 0xff) // Input is zero or block completed, restart
		{
			*codep = code, code = 1, codep = encode;
			if (!*byte || length)
				++encode;
		}
	}
	*codep = code; // Write final code value

return (size_t)(encode - buffer);
}

/** COBS decode data from buffer
	@param buffer Pointer to encoded input bytes
	@param length Number of bytes to decode
	@param data Pointer to decoded output data
	@return Number of bytes successfully decoded
	@note Stops decoding if delimiter byte is found
*/
size_t cobsDecode(const uint8_t *buffer, size_t length, void *data)
{
	assert(buffer && data);

const uint8_t *byte = buffer; // Encoded input byte pointer
	uint8_t *decode = (uint8_t *)data; // Decoded output byte pointer

for (uint8_t code = 0xff, block = 0; byte < buffer + length; --block)
	{
		if (block) // Decode block byte
			*decode++ = *byte++;
		else
		{
			block = *byte++;             // Fetch the next block length
			if (block && (code != 0xff)) // Encoded zero, write it unless it's delimiter.
				*decode++ = 0;
			code = block;
			if (!code) // Delimiter code found
				break;
		}
	}

return (size_t)(decode - (uint8_t *)data);
}

<p>A possibly faster encoder and decoder using standard library functions is presented below.
</p>
#include <stddef.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>

const char *strng = (const char *)data; // Data as string
	uint8_t *encode = buffer; // Encoded bytes pointer 
	uint8_t *codep = encode++; // Output code pointer

while (length)
	{
		size_t l = strnlen(strng, length);
		l = l > 0xfe ? 0xfe : l; // Clip output

if (codep)
			*codep = l + 1; codep = NULL; // Commit code

if (l)
		{
			memcpy(encode, strng, l), strng += l, encode += l; // Copy non-zero bytes
			if ((length -= l) && l == 0xfe)
				codep = encode++; // Restart block
		}
		else
		{
			++strng;
			if (--length)
				codep = encode++; // Prepare encoded zero
			else
				*encode++ = 1; // Trailing zero
		}
	}

return (size_t)(encode - buffer);
}

uint8_t *decode = (uint8_t *)data; // Decoded bytes pointer
	uint8_t block, code = 0xff; // Current block and code value

while (length && (block = *buffer++))
	{
		if (block > length)
			return 0; // Malformed buffer

if (code != 0xff)
			*decode++ = 0; // Decode zero
		code = block;
		length -= block;
		if (--block)
			memcpy(decode, buffer, block), buffer += block, decode += block; // Decode non-zero bytes
	}

return (size_t)(decode - (uint8_t *)data);
}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Bit_stuffing/y8UX3vI7">Bit stuffing</a></li>
<li><a href="/facts/Serial_Line_Internet_Protocol/oqUaoA0f">Serial Line Internet Protocol</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://pypi.python.org/pypi/cobs">Python implementation</a></li>
<li><a href="https://github.com/cmcqueen/cobs-c">Alternate C implementation</a></li>
<li><a href="https://web.archive.org/web/20180719005741/http://www.jacquesf.com/2011/03/consistent-overhead-byte-stuffing/">Another implementation in C</a></li>
<li><a href="https://pythonhosted.org/cobs/cobsr-intro.html">Consistent Overhead Byte Stuffing—Reduced (COBS/R)</a></li>
<li><a href="https://patents.google.com/patent/US9438411B1">A patent describing a scheme with a similar result but using a different method</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Cheshire, Stuart; Baker, Mary (April 1999). "Consistent Overhead Byte Stuffing" (PDF). IEEE/ACM Transactions on Networking. 7 (2): 159–172. CiteSeerX 10.1.1.108.3143. doi:10.1109/90.769765. S2CID 47267776. Retrieved November 30, 2015. <a href="/wiki/Stuart_Cheshire" target="_blank">/wiki/Stuart_Cheshire</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Cheshire, Stuart; Baker, Mary (17 November 1997). Consistent Overhead Byte Stuffing (PDF). ACM SIGCOMM '97. Cannes. Retrieved November 23, 2010. <a href="/wiki/Stuart_Cheshire" target="_blank">/wiki/Stuart_Cheshire</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Carlson, James; Cheshire, Stuart; Baker, Mary (November 1997). PPP Consistent Overhead Byte Stuffing (COBS). I-D draft-ietf-pppext-cobs-00.txt. <a href="/wiki/Stuart_Cheshire" target="_blank">/wiki/Stuart_Cheshire</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Consistent Overhead Byte Stuffing open-in-new

Consistent Overhead Byte Stuffing