¡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 0x00
necesitamos indicar (en un hito) dónde 0x00
habrí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.
fuente
01
pero hay dos01
s en el noveno (donde hay 254 bytes distintos de cero seguidos de un cero).Respuestas:
JavaScript (Node.js) , 114 bytes
Pruébalo en línea!
fuente
Java (JDK) , 143 bytes
Pruébalo en línea!
fuente
Python 2 , 125 bytes
Pruébalo en línea!
fuente
Jalea , 27 bytes
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
fuente
Elixir , 109 bytes
Pruébalo en línea!
fuente
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.
Pruébalo en línea
fuente