Isian Overhead Konsisten Overhead (COBS)

10

Saya terkejut ini belum pernah diposting sebelumnya!

The Konsisten Overhead Byte Stuffing (tongkol) algoritma yang digunakan untuk membatasi byte stream.

Kami memilih penanda bingkai (kami akan menggunakan 0x00) dan di mana pun 0x00 terjadi dalam aliran itu diganti dengan jumlah byte hingga 0x00 berikutnya terjadi (kami akan menyebutnya tonggak sejarah). Ini mengurangi rentang nilai dari 0..255 ke 1..255, memungkinkan 0x00 untuk membatasi bingkai di aliran secara jelas.
Pada tonggak sejarah, jika 255B berikutnya tidak mengandung 0x00 ini melebihi panjang tonggak maksimum - algoritma harus 'berhenti' di 255B dan meletakkan tonggak lain. Ini adalah 'overhead yang konsisten'.
Byte pertama akan menjadi tonggak pertama, tonggak terakhir akan menjadi jumlah byte sampai penanda bingkai.

Beberapa contoh dari Wikipedia (terbaik untuk membaca artikel di mana mereka diwarnai):

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

Tantangan: untuk mengimplementasikan ini dalam program terpendek.

  • Input adalah byte stream / array yang tidak di-encode, output adalah byte stream / array yang di-encode
  • Gunakan segala macam input / output standar biner
  • Penanda bingkai akhir tidak perlu
  • Program dapat mengembalikan array yang terlalu besar
  • Aliran yang diakhiri dengan 254 byte bukan nol tidak memerlukan 0x00 tambahan

Catatan

  • Panjang pengembalian terburuk adalah numBytes + (numBytes / 254) + 1

Contoh

Kami memiliki array byte

[0] 0x01
[1] 0x02
[2] 0x00
[3] 0x03
[4] 0x04
[5] 0x05
[6] 0x00
[7] 0x06

Untuk masing-masing 0x00kita perlu menyatakan (dalam tonggak sejarah) di mana yang berikutnya 0x00akan.

[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.
Patrick
sumber
3
Anda mungkin harus memasukkan ini dalam spesifikasi: Sebagai pengecualian khusus, jika sebuah paket berakhir dengan sekelompok 254 byte bukan nol, tidak perlu menambahkan trailing zero byte. Ini menghemat satu byte dalam beberapa situasi. (mengutip Wikipedia)
Arnauld
3
@LuisMendo Setuju. Sekarang saya telah melewati semua test case, saya dapat mengonfirmasi bahwa ini saat ini sedikit kurang ditentukan.
Arnauld
@Arnauld, saya sudah menyatakan pembuat bingkai akhir tidak perlu :)
Patrick
Dalam contoh, byte keluaran pertama harus 0x03, bukan 0x02, kecuali jika saya salah ...
Olivier Grégoire
1
@Arnauld tentang kasus khusus yang diakhiri dengan 254 byte tidak-nol: setuju, dan ini adalah masalah terpisah untuk penanda bingkai akhir. Itulah sebabnya contoh keenam tidak memiliki trailing 01tetapi ada dua 01s di yang kesembilan (di mana ada 254 byte non-nol diikuti oleh nol).
Nick Kennedy

Jawaban:

2

Java (JDK) , 143 byte

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;}

Cobalah online!

Olivier Grégoire
sumber
1

Python 2 , 125 byte

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]

Cobalah online!

TFeld
sumber
1

Jelly , 27 byte

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

Cobalah online!

Tautan monadik yang mengambil larik byte yang tidak dilodekan sebagai input dan mengembalikan larik byte yang disandikan. Sesuai aturan, penanda bingkai akhir dihilangkan.

Penjelasan

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
Nick Kennedy
sumber
1

Elixir , 109 byte

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

Cobalah online!

Kirill L.
sumber
0

J , 103 karakter

Perhatikan hasil dari test case terakhir berbeda dari wiki dan bahasa lainnya. Ini disebabkan oleh penunjuk ini ke 254 byte nol di batas. Banyak hal menjadi lebih mudah, jika ini tidak diperlakukan sebagai kasus khusus.

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

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

Cobalah secara Online

Zhe Hu
sumber
Anda dapat menghapusnya 1 byte dengan menghapus spasi tambahan di akhir baris terakhir.
ouflak