Fixed Redundancy Byte Insertion

When packetized data is transmitted over any serial channel, a protocol is needed to distinguish between frames / packets. This is done using a frame marker, a special bit sequence, or a character value that indicates where the boundaries between packets are located. Replacing data is a process that converts data packets before transmission in order to eliminate all occurrences of frame separators, so if a separator is detected by the receiver, it can be guaranteed that the separator points to the boundary between the packets.

The COBS algorithm converts an arbitrary string of bytes in the range [0.255] into bytes in the range [1,255]. After eliminating all null bytes from the data, a null value can be used to uniquely indicate the end of the converted data. This is done by adding null bytes to the converted data, thus forming a packet consisting of COBS-encoded data ( payload ) to uniquely indicate the end of the packet.

(Any other byte values ​​may be reserved as a packet delimiter; using zero makes the description simpler.)

There are two equivalent ways to describe the COBS coding process:

Prefixed Block Description

To encode some bytes, first add a null byte, then break them into groups of 254 non-null bytes, or 0-253 non-null bytes ending with a null byte. Due to the addition of a null byte, this is always possible.

Encode each group by removing the terminating null byte (if any) and adding the number of nonzero bytes, plus one to the beginning. Thus, each encoded group is the same size as the original, except that a group of 254 non-zero bytes is encoded in 255 bytes with a header byte of 255.

As a special exception, if a packet ends with a group of 254 non-zero bytes, you do not need to add a terminating null 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 254 non-zero bytes. Such an encoding is obviously reversible. There is no need to insert a null byte at the end of the packet if there are exactly 254 nonzero bytes to the end.

Secondly, replace each null byte with an offset to the next null byte, or to the end of the packet. Due to the extra zeros added in the first stage, each offset is guaranteed no more than 255.

These examples show the coding of various data sequences by the COBS algorithm. In the examples, all bytes are expressed as hexadecimal values, and the encoded data is displayed by text formatting that illustrates various functions:

• Bold indicates a byte of data that has been modified by encoding. All nonzero data bytes remain unchanged.
• Green indicates a zero byte of data that has been changed by encoding. All null data bytes will be replaced when encoding with an offset to the next null byte (i.e. 1+ the number of subsequent non-zero bytes). This is actually a pointer to the next byte of the packet that requires processing: if the addressed byte is nonzero, then these are the following header groups of data bytes, a byte that indicates the next byte to be interpreted; if the byte is zero, then this is the end of the packet.
• Red is a byte, which is also the byte of the group header, containing an offset by the next group, but does not match the data byte. They appear in two places: at the beginning of each encoded packet, and after each group of 254 non-zero bytes.
• a blue zero byte appears at the end of each packet to indicate the end of the data packet to the receiver. This packet byte separator is not part of the COBS sequence; this is an optional framing byte that is added to the encoded output.

Below is a diagram, for example 3 from the above table, to show how each changed data byte is located, and how it is treated as a data byte or end-of-frame byte.

  [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

Examples 7 through 10 show how the overhead varies depending on the data encoded for packet lengths of 255 or more.

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".
 *
 * Returns the length of the encoded data.
 * /
 #include <stdint.h> 
 #include <stddef.h> 

 #define StartBlock () (code_ptr = dst ++, code = 1)
 #define FinishBlock () (* code_ptr = code)

 size_t StuffData ( const uint8_t * ptr , size_t length , uint8_t * dst )
 {
	 const uint8_t * start = dst , * end = ptr + length ;
	 uint8_t code , * code_ptr ;  / * Where to insert the leading count * /

	 StartBlock ();
	 while ( ptr < end ) {
		 if ( code ! = 0xFF ) {
			 uint8_t c = * ptr ++ ;
			 if ( c ! = 0 ) {
				 * dst ++ = c ;
				 code ++ ;
				 continue ;
			 }
		 }
		 FinishBlock ();
		 StartBlock ();
	 }
	 FinishBlock ();
	 return dst - start ;
 }

 / *
 * UnStuffData decodes "length" bytes of data at
 * the location pointed to by "ptr", writing the
 * output to the location pointed to by "dst".
 *
 * Returns the length of the decoded data
 * (which is guaranteed to be <= length).
 * /
 size_t UnStuffData ( const uint8_t * ptr , size_t length , uint8_t * dst )
 {
	 const uint8_t * start = dst , * end = ptr + length ;
	 uint8_t code = 0xFF , copy = 0 ;

	 for (; ptr < end ; copy - ) {
		 if ( copy ! = 0 ) {
			 * dst ++ = * ptr ++ ;
		 } else {
			 if ( code ! = 0xFF )
				 * dst ++ = 0 ;
			 copy = code = * ptr ++ ;
			 if ( code == 0 )
				 break ;  / * Source length too long * /
		 }
	 }
	 return dst - start ;
 }

• Python implementation
• Alternative implementation with
• Another implementation in C
• Another C implementation
• Reduced COBS (COBS / R)
• Patent with a description of a circuit with a similar result, but using a different method