Konsistente Overhead-Byte-Füllung (COBS)

10

Ich bin überrascht, dass dies noch nicht gepostet wurde!

Der COBS-Algorithmus ( Consistent Overhead Byte Stuffing ) wird zum Abgrenzen von Byteströmen verwendet.

Wir wählen einen Frame-Marker (wir verwenden 0x00) und wo immer 0x00 im Stream vorkommt, wird er durch die Anzahl der Bytes ersetzt, bis der nächste 0x00 eintritt (wir nennen dies einen Meilenstein). Dadurch wird der Wertebereich von 0..255 auf 1..255 reduziert, sodass 0x00 Frames im Stream eindeutig abgrenzen kann.
Wenn bei einem Meilenstein der nächste 255B nicht 0x00 enthält, überschreitet dies die maximale Meilensteinlänge - der Algorithmus muss bei 255B "stehen bleiben" und einen weiteren Meilenstein setzen. Dies ist der "konsistente Overhead".
Das erste Byte ist der erste Meilenstein, der letzte Meilenstein ist die Anzahl der Bytes bis zur Rahmenmarkierung.

Einige Beispiele aus Wikipedia (lesen Sie am besten den Artikel, in dem sie farbig sind):

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

Herausforderung: dies im kürzesten Programm umzusetzen.

  • Die Eingabe ist ein nicht codierter Byte-Stream / Array, die Ausgabe ist ein codierter Byte-Stream / Array
  • Verwenden Sie eine beliebige Art von binärem Standardeingang / -ausgang
  • Die endgültige Rahmenmarkierung ist nicht erforderlich
  • Das Programm kann ein übergroßes Array zurückgeben
  • Für einen Stream, der mit 254 Bytes ungleich Null endet, ist die nachfolgende 0x00 nicht erforderlich

Anmerkungen

  • Die Rückgabelänge im ungünstigsten Fall ist numBytes + (numBytes / 254) + 1

Beispiel

Wir haben das Byte-Array

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

Für jeden müssen 0x00wir (in einem Meilenstein) angeben, wo der nächste gewesen 0x00wäre.

[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
quelle
3
Sie sollten dies wahrscheinlich in die Spezifikation aufnehmen: Als besondere Ausnahme ist es nicht erforderlich, das nachfolgende Null-Byte hinzuzufügen, wenn ein Paket mit einer Gruppe von 254 Bytes ungleich Null endet. Dies spart in einigen Situationen ein Byte. (zitiert Wikipedia)
Arnauld
3
@ LuisMendo Einverstanden. Nachdem ich alle Testfälle durchlaufen habe, kann ich bestätigen, dass dies derzeit etwas unterbestimmt ist.
Arnauld
@Arnauld, ich habe angegeben, dass der Endrahmenhersteller sowieso nicht notwendig ist :)
Patrick
In dem Beispiel sollte das erste Ausgabebyte 0x03 sein, nicht 0x02, es sei denn, ich irre mich ...
Olivier Grégoire
1
@Arnauld bezüglich des Sonderfalls, mit 254 Bytes ungleich Null zu enden: stimme zu, und dies ist ein separates Problem zur endgültigen Rahmenmarkierung. Aus diesem Grund hat das sechste Beispiel kein nachfolgendes Beispiel, aber das neunte enthält 01zwei 01s (wobei 254 Bytes ungleich Null gefolgt von einer Null vorhanden sind).
Nick Kennedy

Antworten:

2

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

Probieren Sie es online aus!

Olivier Grégoire
quelle
1

Gelee , 27 Bytes

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

Probieren Sie es online aus!

Eine monadische Verbindung, die ein nicht codiertes Byte-Array als Eingabe verwendet und das codierte Byte-Array zurückgibt. Gemäß den Regeln wird die endgültige Rahmenmarkierung weggelassen.

Erläuterung

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
quelle
0

J , 103 Zeichen

Beachten Sie, dass sich das Ergebnis des letzten Testfalls von Wiki und anderen Sprachen unterscheidet. Dies liegt an diesem Zeiger auf das 254. Null-Byte an der Grenze. Es wird viel einfacher, wenn dies nicht als Sonderfall behandelt wird.

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

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

Probieren Sie es online aus

Zhe Hu
quelle
Sie können es um 1 Byte reduzieren, indem Sie den nachgestellten Leerzeichen am Ende der letzten Zeile entfernen.
Ouflak