Consistent Overhead Byte Stuffing: Difference between revisions

Consistent Overhead Byte Stuffing (COBS) is an algorithm for encoding data bytes that results in efficient, reliable, unambiguous packet framing regardless of packet content, thus making it easy for receiving applications to recover from malformed packets. It employs a particular byte value, typically zero, to serve as a packet delimiter. When zero is used as a delimiter, the algorithm replaces each zero byte with a value equal to one plus the number of non-zero bytes that follow.

Byte stuffing is a process that transforms a sequence of data bytes that may contain 'illegal' or 'reserved' values into a potentially longer sequence that contains no occurrences of those values. The extra length of the transformed sequence is typically referred to as the overhead of the algorithm. The COBS algorithm tightly bounds the worst-case overhead, limiting it to no more than one byte in 254. The algorithm is computationally inexpensive and its average overhead is low compared to other unambiguous framing algorithms.

Packet framing and stuffing

When packet data is sent over any serial medium, a protocol is needed by which to demarcate packet boundaries. This is done by using a special bit-sequence or character value to indicate where the boundaries between packets fall. Data stuffing is the process that transforms the packet data before transmission to eliminate any accidental occurrences of that special framing marker, so that when the receiver detects the marker, it knows, without any ambiguity, that it does indeed indicate a boundary between packets.

COBS takes an input consisting of bytes in the range [0,255] and produces an output consisting of bytes only in the range [1,255]. Having eliminated all zero bytes from the data, a zero byte can now be used unambiguously to mark boundaries between packets. This allows the receiver to synchronize reliably with the beginning of the next packet, even after an error. It also allows new listeners, which might join a broadcast stream at any time, to reliably detect the beginning of the first complete packet in the received byte stream.

With COBS, all 0-terminated packets up to 254 bytes in length are encoded with an overhead of exactly one byte (frame marker). If the packet does not terminate with a 0-byte, the overhead is two bytes (leading count byte, trailing frame marker). For packets over 254 bytes in length the overhead is at most one byte for every 254 bytes of non-zero packet data. The maximum overhead is therefore roughly 0.4% of the packet size, rounded up to a whole number of bytes. COBS encoding has low overhead (on average 0.23% of the packet size, rounded up to a whole number of bytes) and furthermore, for packets of any given length, the amount of overhead is constant regardless of packet content.

Encoding examples

These examples show how various data sequences would be encoded by the COBS algorithm. In the examples, all bytes are expressed as hexadecimal values, and encoded data is shown with text formatting to illustrate various features:

• An overhead byte appears at the beginning of every encoded packet. This byte does not correspond to a data byte; it is an additional byte that is prepended to the encoded output, with a value equal to one plus the number of non-zero bytes that follow.
• Bold indicates a data byte that has not been altered by encoding. All non-zero data bytes remain unaltered.
• Green indicates a data byte that was altered by encoding. All zero data bytes are replaced during encoding, by one plus the number of non-zero bytes that follow.
• A zero byte appears at the end of every packet to indicate end-of-packet to the data receiver.

Example	Unencoded data (hex)	Encoded with COBS (hex)
1	00	01 00
2	00 00	01 01 00
3	11 22 00 33	03 11 22 02 33 00
4	11 00 00 00	02 11 01 01 00
5	01 02 ... FE	FF 01 02 ... FE 00

Implementation

The following code implements a COBS encoder and decoder in the C programming language:

/*
 * StuffData byte stuffs "length" bytes of
 * data at the location pointed to by "ptr",
 * writing the output to the location pointed
 * to by "dst".
 */

#define FinishBlock(X) (*code_ptr = (X), code_ptr = dst++, code = 0x01)

void StuffData(const unsigned char *ptr,
unsigned long length, unsigned char *dst)
{
  const unsigned char *end = ptr + length;
  unsigned char *code_ptr = dst++;
  unsigned char code = 0x01;

  while (ptr < end)
  {
    if (*ptr == 0)
      FinishBlock(code);
    else
    {
      *dst++ = *ptr;
      if (++code == 0xFF)
        FinishBlock(code);
    }
    ptr++;
  }

  FinishBlock(code);
}

/*
 * UnStuffData decodes "length" bytes of
 * data at the location pointed to by "ptr",
 * writing the output to the location pointed
 * to by "dst".
 */

void UnStuffData(const unsigned char *ptr,
unsigned long length, unsigned char *dst)
{
  const unsigned char *end = ptr + length;
  while (ptr < end)
  {
    int i, code = *ptr++;
    for (i=1; i<code; i++)
      *dst++ = *ptr++;
    if (code < 0xFF)
      *dst++ = 0;
  }
}

/*
 * Defensive UnStuffData, which prevents poorly
 * conditioned data at *ptr from over-running
 * the available buffer at *dst.
 */

void UnStuffData(const unsigned char *ptr,
unsigned long length, unsigned char *dst)
{
  const unsigned char *end = ptr + length;
  while (ptr < end)
  {
    int i, code = *ptr++;
    for (i=1; ptr<end && i<code; i++)
      *dst++ = *ptr++;
    if (code < 0xFF)
      *dst++ = 0;
  }
}

External links

• Python implementation
• Alternate C implementation
• Another implementation in C