caminando a través de la descompresión manualmente
Estoy tratando de entender cómo funciona la compresión “deflate”. Para eso, pensé en intentar decodificar una cadena codificada con “deflate” manualmente, siguiendo lo que dice el RFC1951: Especificación del formato de datos comprimidos DEFLATE versión 1.3. Generé la cadena codificada de la siguiente manera:
$result = gzdeflate('A<em>DEAD</em>DAD<em>CEDED</em>A<em>BAD</em>BABE<em>A</em>BEADED<em>ABACA</em>BED');
echo bin2hex($result);
Eso me dio esto:
1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e
Según el RFC1951, sección 3.2.3, Detalles del formato de bloque:
Cada bloque de datos comprimidos comienza con 3 bits de encabezado que contienen los siguientes datos:
- El primer bit: BFINAL
- Los siguientes 2 bits: BTYPE
…
BFINAL se establece si y solo si este es el último bloque de los datos.
BTYPE especifica cómo se comprimen los datos de la siguiente manera:
- 00: sin compresión
- 01: comprimido con códigos de Huffman fijos
- 10: comprimido con códigos de Huffman dinámicos
- 11: reservado (error)
0x15 es 0b00010101 en bits. Los primeros 3 bits son 000, lo que hace que BFINAL sea 0 y BTYPE sea 00 (sin compresión).
Según más adelante en el RFC1951, sección 3.2.3, Detalles del formato de bloque:
Si se almacena sin compresión:
- Saltar cualquier bit restante en el byte parcialmente procesado actual.
- Leer LEN y NLEN (ver siguiente sección).
- Copiar LEN bytes de datos en la salida.
Según RFC1951, sección 3.2.4, Bloques no comprimidos (BTYPE=00):
Se ignoran los bits de entrada hasta el siguiente límite de byte.
El resto del bloque consiste en la siguiente información:
0 1 2 3 4...
+---+---+---+---+================================+
| LEN | NLEN |... LEN bytes de datos literales...|
+---+---+---+---+================================+
LEN es el número de bytes de datos en el bloque. NLEN es el complemento a uno de LEN.
Entonces, de acuerdo a todo eso, avanzo al siguiente byte – 0x89, que es 0b10001001 en bits. Los primeros dos bits (LEN) son 10 y los próximos dos bits son NLEN (00). Pero aquí radica el problema. 00 no es el complemento a uno de 10 – 01 lo es.
Además, ¿qué pasaría si quisieras tener un bloque no comprimido con 0xFF como primer byte? ¿Es eso simplemente imposible?
davy.ai
Deflate es un algoritmo de compresión de datos que utiliza una combinación del algoritmo LZ77 y la codificación Huffman. El algoritmo divide los datos en bloques y comprime cada bloque de forma independiente. Los datos comprimidos comienzan con 3 bits que contienen las señales BFINAL (bloque final) y BTYPE (tipo de compresión).
En el ejemplo dado, la cadena de entrada “A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED” fue comprimida utilizando la función gzdeflate() en PHP, lo que resultó en una cadena comprimida “1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e”.
Para decodificar los datos comprimidos, necesitamos seguir las especificaciones dadas en RFC1951. Los primeros tres bits en la cadena comprimida (0x15) corresponden a BFINAL=0 y BTYPE=00 (sin compresión). El siguiente byte (0x89) representa LEN=10 y NLEN=01. Sin embargo, hay un error ya que NLEN debería ser el complemento de LEN, que en este caso debería ser 0xEF.
Para responder a la segunda pregunta, es posible tener un bloque sin comprimir con 0xFF como primer byte. Sin embargo, dado que deflate utiliza 3 bits para especificar el encabezado del bloque, los primeros tres bits de 0xFF indicarían las señales BFINAL y BTYPE. Por lo tanto, para representar un byte literal 0xFF, debemos incluirlo en un bloque comprimido utilizando códigos de Huffman fijos o dinámicos.