Capítulo 02
Formatos y gramáticas
Cómo se construyen los formatos, cómo los describen una gramática y unas restricciones, y cómo leer un archivo de control byte a byte.
Un formato es un acuerdo entre quien escribe los bytes y quien los lee. Dice qué partes existen, en qué orden y cómo encontrar sus límites. Antes de probar un parser, ayuda saber leer su entrada por tu cuenta.
Cuatro formas habituales
Bloques
PNG, WAV y MP4 son secuencias de bloques que se describen a sí mismos. Cada bloque empieza con una longitud y un tipo, así que un lector puede saltarse los bloques que no entiende. PNG añade una suma de comprobación CRC a cada bloque. Las cajas MP4 pueden contener otras cajas, así que la estructura es un árbol.
Desplazamientos y directorios
ZIP guarda al final del archivo un directorio central que apunta a cada entrada. PDF mantiene una tabla de referencias cruzadas con el desplazamiento en bytes de cada objeto. Un lector salta de un sitio a otro del archivo en lugar de leerlo de principio a fin, lo que significa que a los mismos bytes se puede llegar por más de un camino.
Árboles de texto
SVG es XML: elementos, atributos y anidamiento. El parser construye un árbol antes de que nada más lo examine.
Líneas y tokens
HTTP/1.1, ASCII PLY y ASCII PNM son texto. HTTP tiene una línea inicial y líneas de cabecera que terminan en CRLF. PNM es una lista de números separados por espacios. PLY tiene una cabecera que declara cuántos registros vienen después. Los formatos de texto parecen sencillos, pero también llevan recuentos y longitudes que el parser tiene que comprobar.
Gramáticas y restricciones
Una gramática describe la forma de las entradas válidas. Esta es una gramática aproximada de un archivo PNG:
<png> ::= <sig> <ihdr> <chunk>* <iend> <sig> ::= 89 50 4E 47 0D 0A 1A 0A <chunk> ::= <length:4> <type:4> <data> <crc:4>
La gramática recoge el orden de las partes, pero no las relaciones entre ellas. Faltan dos reglas: el campo de longitud debe coincidir con el tamaño de los datos, y el CRC debe coincidir con la suma de comprobación del tipo y los datos. Estas son restricciones. La mayoría de los formatos reales necesitan ambas cosas: una gramática para la estructura y restricciones para longitudes, recuentos, sumas de comprobación y desplazamientos.
Esto importa al probar. Si cambias bytes al azar en un PNG, casi siempre romperás un CRC, y un decodificador estricto rechazará el archivo en el primer bloque. El código interesante que hay detrás de esa comprobación nunca se alcanza. Los generadores que conocen la gramática y las restricciones, como Fandango, pueden producir entradas que superan estas comprobaciones y aun así variar las partes que importan.
Lee los controles
Cada formato de Parsarium tiene archivos de control pequeños y válidos. Elige uno abajo, mira los bytes resaltados y responde a la pregunta. La respuesta muestra lo que devolvió un parser real con ese archivo.
Ideas clave
- Los formatos tienen unas pocas formas: bloques, desplazamientos y directorios, árboles de texto, y líneas de tokens.
- Una gramática describe el orden y el anidamiento de las partes. Las restricciones describen cómo se relacionan: longitudes, recuentos, sumas de comprobación, desplazamientos.
- Las mutaciones aleatorias suelen romper una restricción, así que un parser estricto rechaza la entrada antes de llegar al código interesante.
- Los generadores que conocen la gramática y las restricciones pueden producir entradas que superan estas comprobaciones y aun así variar lo que importa.
Comprueba lo que sabes
Responde a las cinco para ver tu resultado
En un bloque PNG, ¿qué bytes cubre el CRC?
- La longitud, el tipo y los datos
- El tipo y los datos
- Solo los datos
La especificación de PNG calcula el CRC sobre el tipo y los datos del bloque. El campo de longitud no se incluye.
¿Por qué cambiar bytes al azar rara vez llega al código profundo de un decodificador PNG?
- La mayoría de los cambios rompen un CRC, y un decodificador estricto rechaza el bloque.
- Los decodificadores PNG ignoran los bytes modificados.
- Los archivos PNG son demasiado pequeños para mutarlos.
Un solo byte cambiado en un bloque invalida su suma de comprobación. El decodificador se detiene en la primera comprobación, y el código que viene después nunca se ejecuta.
¿Cuál de estas cosas no puede expresar una gramática por sí sola?
- El orden de las partes
- Que un campo de longitud sea igual al tamaño de los datos que le siguen
- Qué partes pueden repetirse
El orden, el anidamiento y la repetición son lo que las gramáticas hacen bien. Las relaciones entre valores, como longitudes y sumas de comprobación, necesitan restricciones.
¿Qué formato se suele leer empezando por el final?
- WAV
- ZIP
- ASCII PNM
Un lector de ZIP busca el registro de fin de directorio central al final del archivo y lo sigue hasta el directorio central y las entradas.
Un archivo ASCII PNM empieza por P3 2 1 255. ¿Qué significan el 2 y el 1?
- Ancho y alto
- Canales y profundidad de bits
- Versión principal y secundaria
P3 indica RGB en ASCII; después vienen el ancho y el alto, luego el valor máximo de muestra y por último las muestras.
Ejercicios
Ejercicio 2.1Calentamiento
Responde a las diez preguntas del inspector de bytes de arriba, una por formato. En cada una, localiza los bytes resaltados en el volcado hexadecimal y di a qué parte del formato pertenecen.
Pista
La columna ASCII a la derecha del volcado suele hacer más visible la estructura, sobre todo en los formatos de texto y en los tipos de bloque.
Solución
Las respuestas aparecen en el inspector. Lo que importa del ejercicio es el segundo paso: saber decir, para cada formato, dónde empieza su estructura y qué le dice al lector cuánto tiene que leer a continuación.
Ejercicio 2.2Práctica
Cambia el ancho del control PNG de 2 a 3. Haz dos versiones: una que mantenga el CRC antiguo y otra con el CRC corregido. Después pasa las dos por Pillow.
python3 - <<'EOF'
import os, struct, zlib
data = bytearray(open(os.path.join(os.environ["PARSARIUM"], "controls/png/red-green.png"), "rb").read())
data[16:20] = struct.pack(">I", 3) # ancho de IHDR: 2 -> 3
open("wide-old-crc.png", "wb").write(data)
data[29:33] = struct.pack(">I", zlib.crc32(data[12:29])) # CRC sobre tipo + datos
open("wide-new-crc.png", "wb").write(data)
EOF
$ parsarium run png python pillow wide-old-crc.png --results runs/wide-old $ parsarium run png python pillow wide-new-crc.png --results runs/wide-new
Compara stdout_tail y stderr_tail en los dos registros. ¿Qué comprobación detuvo el primer archivo? ¿Hasta dónde llegó el segundo?
Pista
IHDR empieza en el desplazamiento 8: cuatro bytes de longitud, cuatro de tipo (desplazamientos 12 a 15), trece de datos (16 a 28) y cuatro de CRC (29 a 32). El ancho son los cuatro primeros bytes de datos.
Solución
El primer archivo no supera la suma de comprobación de IHDR, así que un decodificador estricto se detiene ahí. El segundo supera esa comprobación y llega a los datos de la imagen, donde encuentra menos píxeles de los que promete la cabecera. Lo que pasa después lo decide el decodificador: informar de un error, rellenar los píxeles que faltan o devolver una imagen parcial. El registro muestra qué hace Pillow. Guarda wide-new-crc.png; en el capítulo 6 lo enviamos a todos los parsers de PNG.
Ejercicio 2.3Reto
Escribe una gramática y las restricciones de ASCII PNM en forma P3, con la precisión suficiente para que un generador pueda producir archivos válidos a partir de ellas. Después enumera tres formas de romper una restricción sin dejar de cumplir la gramática.
Pista
Parte del control: P3, ancho, alto, valor máximo y después las muestras. Piensa en cuántas muestras tiene que haber y qué rango puede tomar cada una.
Solución
<pnm> ::= "P3" <ws> <width> <ws> <height> <ws> <maxval> (<ws> <sample>)+ <ws>? <width> ::= <digits> <height> ::= <digits> <maxval> ::= <digits> <sample> ::= <digits>
Restricciones: el número de muestras es igual a 3 × ancho × alto; cada muestra es como mucho maxval; maxval está entre 1 y 65535. Entradas que cumplen la gramática pero rompen una restricción: una muestra de menos o de más; una muestra mayor que maxval; un ancho y un alto cuyo producto desborda un entero de 32 bits. Cada una pone a prueba una comprobación que el parser debería hacer.