I'm surprised this hasn't been posted before!
The Consistent Overhead Byte Stuffing (COBS) algorithm is used to delimit byte streams.
We choose a frame marker (we'll use 0x00) and wherever 0x00 occurs in the stream it is replaced with the number of bytes until the next 0x00 occurs (we'll call this a milestone). This reduces the range of values from 0..255 to 1..255, enabling 0x00 to unambiguously delimit frames in the stream.
At a milestone, if the next 255B does not contain 0x00 this exceeds the maximum milestone length - the algorithm must 'stall' at 255B and put another milestone. This is the 'consistent overhead'.
The first byte will be the first milestone, the final milestone will be the number of bytes until the frame marker.
Some examples from Wikipedia (best to read the article where they are coloured):
0x00 as frame marker
Unencoded data (hex) Encoded with COBS (hex)
00 01 01 00
00 00 01 01 01 00
11 22 00 33 03 11 22 02 33 00
11 22 33 44 05 11 22 33 44 00
11 00 00 00 02 11 01 01 01 00
01 02 03 ... FD FE FF 01 02 03 ... FD FE 00
00 01 02 ... FC FD FE 01 FF 01 02 ... FC FD FE 00
01 02 03 ... FD FE FF FF 01 02 03 ... FD FE 02 FF 00
02 03 04 ... FE FF 00 FF 02 03 04 ... FE FF 01 01 00
03 04 05 ... FF 00 01 FE 03 04 05 ... FF 02 01 00
Challenge: to implement this in the shortest program.
- Input is an unencoded byte stream/array, output is an encoded byte stream/array
- Use any sort of binary standard input/output
- The final frame marker is not necessary
- The program can return an oversized array
- A stream ending with 254 non-zero bytes does not require the trailing 0x00
Notes
- The worst-case return length is
numBytes + (numBytes / 254) + 1
Example
We have the byte array
[0] 0x01
[1] 0x02
[2] 0x00
[3] 0x03
[4] 0x04
[5] 0x05
[6] 0x00
[7] 0x06
For each 0x00
we need to state (in a milestone) where the next 0x00
would have been.
[0] 0x03 #Milestone. Refers to the original [2] - "The next 0x00 is in 3B"
[1] 0x01 #Original [0]
[2] 0x02 #Original [1]
[3] 0x04 #Milestone. Refers to the original [6] - "The next 0x00 is in 4B"
[4] 0x03 #
[5] 0x04 #
[6] 0x05 # Originals [3..5]
[7] 0x02 #Milestone. Refers to the end frame marker
[8] 0x06 #Original [7]
[9] 0x00 #Optional. End frame marker.
01
but there are two01
s in the ninth one (where there are 254 non-zero bytes followed by a zero). \$\endgroup\$