Remplissage cohérent d'octets (COBS)

10

Je suis surpris que cela n'ait pas été publié auparavant!

L' algorithme COBS ( Overhead Byte Stuffing ) est utilisé pour délimiter les flux d'octets.

Nous choisissons un marqueur de trame (nous utiliserons 0x00) et partout où 0x00 se produit dans le flux, il est remplacé par le nombre d'octets jusqu'à ce que le prochain 0x00 se produise (nous appellerons cela un jalon). Cela réduit la plage de valeurs de 0..255 à 1..255, permettant à 0x00 de délimiter sans ambiguïté les trames dans le flux.
À un jalon, si le 255B suivant ne contient pas 0x00, cela dépasse la longueur maximale du jalon - l'algorithme doit «caler» à 255B et mettre un autre jalon. Il s'agit du «surcoût constant».
Le premier octet sera le premier jalon, le jalon final sera le nombre d'octets jusqu'au marqueur de trame.

Quelques exemples de Wikipédia (mieux lire l'article où ils sont colorés):

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

Défi: mettre cela en œuvre dans le programme le plus court.

  • L'entrée est un flux / tableau d'octets non codé, la sortie est un flux / tableau d'octets codés
  • Utilisez n'importe quelle sorte d'entrée / sortie standard binaire
  • Le marqueur d'image final n'est pas nécessaire
  • Le programme peut renvoyer un tableau surdimensionné
  • Un flux se terminant par 254 octets non nuls ne nécessite pas la fin 0x00

Remarques

  • La longueur de retour dans le pire des cas est numBytes + (numBytes / 254) + 1

Exemple

Nous avons le tableau d'octets

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

Pour chacun, 0x00nous devons indiquer (dans un jalon) où 0x00aurait été le suivant.

[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.
code-golf array-manipulation algorithm Patrick
la source
3
Vous devriez probablement l'inclure dans la spécification: à titre d'exception spéciale, si un paquet se termine par un groupe de 254 octets non nuls, il n'est pas nécessaire d'ajouter l'octet zéro final. Cela permet d'économiser un octet dans certaines situations. (citant Wikipedia)
Arnauld
3
@LuisMendo a accepté. Maintenant que j'ai parcouru tous les cas de test, je peux confirmer que c'est actuellement un peu sous-spécifié.
Arnauld
@Arnauld, j'ai déclaré que le fabricant de cadres de fin n'était pas nécessaire de toute façon :)
Patrick
Dans l'exemple, le premier octet de sortie doit être 0x03, pas 0x02, sauf erreur de ma part ...
Olivier Grégoire
1
@Arnauld concernant le cas particulier de la fin avec 254 octets non nuls: d'accord, et ceci est un problème distinct pour le marqueur de trame final. C'est pourquoi le sixième exemple n'a pas de fin 01mais il y a deux 01s dans le neuvième (où il y a 254 octets non nuls suivis d'un zéro).
Nick Kennedy

Réponses:

2

Java (JDK) , 143 octets

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

Essayez-le en ligne!

Olivier Grégoire
la source
1

Python 2 , 125 octets

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]

Essayez-le en ligne!

TFeld
la source
1

Gelée , 27 octets

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

Essayez-le en ligne!

Un lien monadique qui prend en entrée un tableau d'octets non codé et renvoie le tableau d'octets codés. Conformément aux règles, le marqueur de trame final est omis.

Explication

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
la source
0

J , 103 caractères

Notez que le résultat du dernier cas de test est différent du wiki et des autres langues. Cela est dû à ce pointeur sur le 254-ème octet zéro à la frontière. Les choses deviennent beaucoup plus faciles si cela n'est pas traité comme un cas spécial.

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

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

Essayez-le en ligne

Zhe Hu
la source
Vous pouvez le supprimer d' un octet en supprimant l'espace de fin à la fin de la dernière ligne.
ouflak