10
\$\begingroup\$

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.
|improve this question
\$\endgroup\$
  • 3
    \$\begingroup\$ You probably should include this in the spec: 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. (quoting Wikipedia) \$\endgroup\$ – Arnauld Apr 3 '19 at 12:08
  • 3
    \$\begingroup\$ @LuisMendo Agreed. Now that I've walked through all test cases, I can confirm that this is currently a bit underspecified. \$\endgroup\$ – Arnauld Apr 3 '19 at 12:11
  • \$\begingroup\$ @Arnauld, I've stated the end frame maker is not necessary anyway :) \$\endgroup\$ – Patrick Apr 3 '19 at 12:41
  • \$\begingroup\$ In the example, the first output byte should be 0x03, not 0x02, unless I'm mistaken... \$\endgroup\$ – Olivier Grégoire Apr 3 '19 at 13:04
  • 1
    \$\begingroup\$ @Arnauld regarding special case of ending with 254 non-zero bytes: agree, and this is a separate issue to the final frame marker. It is why the sixth example doesn’t have a trailing 01 but there are two 01s in the ninth one (where there are 254 non-zero bytes followed by a zero). \$\endgroup\$ – Nick Kennedy Apr 4 '19 at 8:23
2
\$\begingroup\$

JavaScript (Node.js), 114 bytes

a=>(g=([v,...a])=>1/v?[v||a.indexOf(0)+1,...g(a)]:[])([0,...a,0].flatMap((v,j)=>1/a[j]&&(i=v&&i+1)>253?[v,i=0]:v))

Try it online!

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

Java (JDK), 143 bytes

a->{int l=a.length,r[]=new int[l+2],i=0,j=1,x=1,z=0;for(;i<l;){if(a[i]>0)r[j++]=a[i];if(a[i++]<1||++x>254){r[z]=x;z=j++;x=1;}}r[z]=x;return r;}

Try it online!

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 125 bytes

def f(a):
 r=[[]]
 for v in a:r+=[[]]*((len(r[-1])>253)+(v<1));r[-1]+=[v]*(v>0)
 return sum([[len(x)+1]+x for x in r],[])+[0]

Try it online!

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 27 bytes

Oµ=0ks€254Ẏḟ€0L‘;Ɗ€F;Ṫ¬x`ƊỌ

Try it online!

A monadic link that takes an unencoded byte array as input and returns the encoded byte array. As per the rules, the final frame marker is omitted.

Explanation

Oµ                          | Convert to integer and start a new monadic chain
  =0k                       | Split after zeros
     s€254                  | Split each list into length 254 lists
          Ẏ                 | Tighten (reduce list depth by 1)
           ḟ€0              | Filter zeros out from each list
              L‘;Ɗ€         | Prepend the list length plus one to each list
                   F        | Flatten
                    ;Ṫ¬x`Ɗ  | Append an additional 1 if the original list ended with zero
                          Ọ | Convert back to bytes
|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Elixir, 109 bytes

&Regex.replace~r/(^|(?<=([^\0]{254}))(?!$)|\0)((?2)|[^\0]*?(?=\0|$))/,&1,fn _,_,_,x-><<1+byte_size x>><>x end

Try it online!

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

J, 103 chars

Notice the result from the last test case is different from wiki and other languages. This is due to this pointer to 254-th zero byte at the boundary. Things get a lot easier, if this isn't treated as a special case. 

f =: 3 : 0
  k =. I. (y,0)=0
  s =. - 2 (-/) \ k
  (>: y i. 0), s (}:k) } y
 )

 f2 =: 3 : 0
   f each _254 <\ y
 )

Try It Online

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ You can take it down 1 byte by removing the trailing space at the end of the last line. \$\endgroup\$ – ouflak Nov 7 '19 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.