Relleno de byte superior consistente (COBS)

10

¡Me sorprende que esto no haya sido publicado antes!

El algoritmo de relleno de bytes generales consistentes (COBS) se utiliza para delimitar flujos de bytes.

Elegimos un marcador de fotograma (usaremos 0x00) y siempre que ocurra 0x00 en la secuencia, se reemplazará con el número de bytes hasta que ocurra el siguiente 0x00 (lo llamaremos un hito). Esto reduce el rango de valores de 0..255 a 1..255, permitiendo que 0x00 delimite inequívocamente tramas en la secuencia.
En un hito, si el siguiente 255B no contiene 0x00, esto excede la longitud máxima del hito: el algoritmo debe 'detenerse' en 255B y poner otro hito. Esta es la "sobrecarga constante".
El primer byte será el primer hito, el hito final será el número de bytes hasta el marcador de cuadro.

Algunos ejemplos de Wikipedia (mejor leer el artículo donde están coloreados):

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

Reto: implementar esto en el programa más corto.

  • La entrada es una secuencia / matriz de bytes no codificada, la salida es una secuencia / matriz de bytes codificada
  • Utilice cualquier tipo de entrada / salida estándar binaria
  • El marcador de cuadro final no es necesario
  • El programa puede devolver una matriz de gran tamaño
  • Una secuencia que termina con 254 bytes distintos de cero no requiere el 0x00 final

Notas

  • La longitud de retorno en el peor de los casos es numBytes + (numBytes / 254) + 1

Ejemplo

Tenemos la matriz de bytes

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

Para cada uno 0x00necesitamos indicar (en un hito) dónde 0x00habría estado el siguiente .

[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.
Patricio
fuente
3
Probablemente debería incluir esto en la especificación: como excepción especial, si un paquete termina con un grupo de 254 bytes distintos de cero, no es necesario agregar el byte cero final. Esto ahorra un byte en algunas situaciones. (citando Wikipedia)
Arnauld
3
@LuisMendo De acuerdo. Ahora que he recorrido todos los casos de prueba, puedo confirmar que esto está un poco poco especificado.
Arnauld
@Arnauld, he dicho que el creador del marco final no es necesario de todos modos :)
Patrick
En el ejemplo, el primer byte de salida debería ser 0x03, no 0x02, a menos que me equivoque ...
Olivier Grégoire
1
@Arnauld con respecto al caso especial de terminar con 254 bytes distintos de cero: de acuerdo, y este es un tema separado para el marcador de cuadro final. Es por eso que el sexto ejemplo no tiene un final, 01pero hay dos 01s en el noveno (donde hay 254 bytes distintos de cero seguidos de un cero).
Nick Kennedy el

Respuestas:

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

Pruébalo en línea!

Olivier Grégoire
fuente
1

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]

Pruébalo en línea!

TFeld
fuente
1

Jalea , 27 bytes

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

Pruébalo en línea!

Un enlace monádico que toma una matriz de bytes no codificada como entrada y devuelve la matriz de bytes codificada. Según las reglas, se omite el marcador de cuadro final.

Explicación

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
fuente
1

Elixir , 109 bytes

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

Pruébalo en línea!

Kirill L.
fuente
0

J , 103 caracteres

Observe que el resultado del último caso de prueba es diferente del wiki y otros idiomas. Esto se debe a este puntero al 254º byte cero en el límite. Las cosas se vuelven mucho más fáciles si esto no se trata como un caso especial.

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

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

Pruébalo en línea

Zhe Hu
fuente
Puede bajarlo 1 byte eliminando el espacio final al final de la última línea.
ouflak