🕧 🧔 👩🏾‍🤝‍👨🏽 Introducción a la ingeniería inversa: formato de datos de juegos de piratería 🦅 🐑 👩🏽‍🔬

Introduccion

La ingeniería inversa de un archivo de datos desconocido puede describirse como un proceso de comprensión gradual. En muchos sentidos, se asemeja a un método científico, solo aplicado a objetos abstractos creados por el hombre, y no al mundo natural. Comenzamos recolectando datos y luego usamos esta información para presentar una o más hipótesis. Probamos las hipótesis y aplicamos los resultados de estas pruebas para aclararlas. Si es necesario, repita el proceso.

Desarrollar habilidades de ingeniería inversa es básicamente una cuestión de práctica. Al ganar experiencia, construye una comprensión intuitiva de lo que necesita explorar en primer lugar, qué patrones debe buscar y qué herramientas son más convenientes de usar.

En este artículo, hablaré en detalle sobre el proceso de los archivos de datos de ingeniería inversa de un viejo juego de computadora para demostrar cómo se hace esto.

Un poco de historia

Todo comenzó cuando intenté recrear el Chip's Challenge en Linux.

El Chip's Challenge se lanzó originalmente en 1989 para la ahora olvidada consola portátil Atari Lynx. Para ese momento, Atari Lynx era un automóvil impresionante, pero salió al mismo tiempo que el Nintendo Game Boy, que finalmente capturó el mercado.

Chip's Challenge es un juego de rompecabezas con una vista superior y un mapa en mosaico. Como con la mayoría de estos juegos, el objetivo de cada nivel es llegar a la salida. En la mayoría de los niveles, la salida está protegida por un conector para el chip, que solo se puede omitir mediante la recopilación de un cierto número de chips de computadora.

Video: Atari Lynx en acción , tutorial de nivel uno .

Un nuevo juego comienza desde el primer nivel bajo el nombre "LECCIÓN 1". Además de chips y una ranura para un chip, aparecen llaves y puertas. En otros niveles, surgen obstáculos como trampas, bombas, agua y criaturas que (con mayor frecuencia) se mueven a lo largo de rutas predecibles. Una amplia gama de objetos y dispositivos le permite crear muchos rompecabezas y límites de tiempo. Para completar el juego debes pasar por más de 140 niveles.

Aunque Lynx finalmente fracasó, el Chip's Challenge demostró ser bastante popular y fue portado a muchas otras plataformas, apareciendo finalmente en Microsoft Windows, donde se generalizó. Alrededor del juego, se formó una pequeña pero dedicada base de fanáticos, y con el tiempo, se escribió un editor de niveles que permitía a los jugadores crear innumerables niveles.

Y aquí es donde comienza mi historia. Decidí que quería crear una versión del motor de juego básico de código abierto para poder jugar Chip's Challenge en Linux y Windows, y facilitar la ejecución de todos los niveles creados por los fanáticos.

La existencia del editor de niveles resultó ser un milagro para mí, porque pude explorar las características ocultas de la lógica del juego, creando mis propios niveles y realizando pruebas. Desafortunadamente, no había un editor de niveles para el juego Lynx original; apareció solo en el puerto más conocido en Windows.

El puerto de Windows no fue creado por los desarrolladores originales, por lo que aparecieron muchos cambios en la lógica del juego (y no todos fueron intencionales). Cuando comencé a escribir mi motor, quería recrear en él la lógica del juego original en Lynx y la versión más conocida para Windows. Pero la falta de un editor de niveles en Lynx limitó seriamente mi capacidad de estudiar el juego original en detalle. El puerto de Windows tenía una ventaja: los niveles se almacenaban en un archivo de datos separado, lo que simplificaba su detección e ingeniería inversa. El juego para Lynx se distribuyó en cartuchos ROM que contenían imágenes de sprites, efectos de sonido y código de máquina, así como datos de nivel que se ejecutaron todos juntos. No hay ninguna pista sobre dónde se encuentran los datos en este volcado de 128 kilobytes de la ROM, o cómo se ve, y sin este conocimiento, no podría crear un editor de niveles para la versión Lynx.

Una vez, en un lento proceso de investigación, me encontré con una copia del puerto de Chip's Challenge en MS-DOS. Al igual que con la mayoría de los primeros puertos del juego, su lógica estaba más cerca del original que en la versión de Windows. Cuando miré los datos del programa para averiguar cómo se almacenan, me sorprendió descubrir que los datos de nivel se asignaron en un directorio separado, y cada nivel se almacenó en su propio archivo. Teniendo tan convenientemente separados los datos de nivel, sugerí que no sería demasiado difícil realizar ingeniería inversa en los archivos de datos de nivel. Y esto te permitirá escribir un editor de niveles para la versión del juego en MS-DOS. Decidí que esta era una oportunidad interesante.

Pero luego otro miembro de la comunidad de Chip's Challenge me advirtió de un hecho interesante. El contenido de los archivos de nivel para MS-DOS resultó ser un volcado de bytes de ROM Lynx. Esto significaba que si podía decodificar los archivos de MS-DOS, podría utilizar este conocimiento para leer y cambiar los niveles dentro del volcado de Lynx ROM. Luego puedes crear un editor de niveles directamente para el juego original en Lynx.

De repente, mi principal prioridad eran los archivos de nivel de ingeniería inversa para MS-DOS.

Archivos de datos

Aquí hay un enlace al directorio tarball que contiene todos los archivos de datos. Lo doy en caso de que quiera repetir después de mí todos los pasos descritos en este artículo, o intente decodificar los archivos de datos usted mismo.

Es legal? Buena pregunta Dado que estos archivos son solo una pequeña parte del programa para MS-DOS, y por sí mismos son inútiles, y dado que los publico solo con fines educativos, creo que esto cae dentro de los requisitos de uso justo. Espero que todas las partes interesadas estén de acuerdo conmigo. (Sin embargo, si recibo una carta amenazadora de abogados, puedo cambiar el artículo para presentar los archivos de datos de una manera divertida y luego declarar que es una parodia).

Prerrequisitos

Asumiré que conoce el cálculo hexadecimal, incluso si no conoce la decodificación de los valores hexadecimales, y también que está un poco familiarizado con el shell de Unix. La sesión de shell que se muestra en este artículo se ejecuta en un sistema Linux estándar, pero los comandos casi utilizados son utilidades comunes de Unix y se distribuyen ampliamente en otros sistemas similares a Unix.

Primer vistazo

Aquí hay una lista del directorio que contiene los archivos de datos del puerto en MS-DOS:

  Niveles de $ ls
 all_full.pak cake_wal.pak eeny_min.pak iceberg.pak lesson_5.pak mulligan.pak playtime.pak southpol.pak totally_.pak
 alphabet.pak castle_m.pak elementa.pak ice_cube.pak lección_6.pak nice_day.pak potpourr.pak special.pak traffic_.pak
 amsterda.pak catacumba.pak fireflie.pak icedeath.pak lección_7.pak nightmar.pak problems.pak spirals.pak trinity.pak
 apartmen.pak cellbloc.pak firetrap.pak icehouse.pak lección_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak
 arcticfl.pak chchchip.pak floorgas.pak invincib.pak langosta_.pak nueces_y.pak reverse_.pak steam.pak undergro.pak
 bolas_o_.pak enfriador.pak forzado_e.pak i.pak lock_blo.pak on_the_r.pak rink.pak stripes.pak up_the_b.pak
 beware_o.pak chipmine.pak force_fi.pak i_slide.pak loop_aro.pak oorto_ge.pak roadsign.pak suicide.pak vanishin.pak
 blink.pak citybloc.pak force_sq.pak jailer.pak memory.pak open_que.pak sampler.pak telebloc.pak victim.pak
 blobdanc.pak colony.pak fortune_.pak jumping_.pak metastab.pak oversea_.pak scavenge.pak telenet.pak vortex.pak
 blobnet.pak corridor.pak four_ple.pak kablam.pak mind_blo.pak pain.pak scoundre.pak t_fair.pak wars.pak
 block_fa.pak cypher.pak four_squ.pak knot.pak mishmesh.pak paranoia.pak vista_s.pak the_last.pak escritores_.pak
 block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak partial_.pak short_ci.pak the_mars.pak yorkhous.pak
 block_n_.pak deepfree.pak goldkey.pak lemmings.pak mixed_nu.pak pentagra.pak shrinkin.pak the_pris.pak
 block_ou.pak digdirt.pak go_with_.pak lesson_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak
 block.pak digger.pak grail.pak lección_2.pak monster_.pak pier_sev.pak slide_st.pak time_lap.pak
 bounce_c.pak doublema.pak hidden_d.pak lección_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak
 brushfir.pak drawn_an.pak hunt.pak lesson_4.pak mugger_s.pak playhous.pak socialis.pak tossed_s.pak

Como puede ver, todos los archivos terminan en .pak . .pak es el permiso estándar para el archivo de datos de la aplicación, y esto, desafortunadamente, no nos brinda ninguna información sobre su estructura interna. Los nombres de archivo son los primeros ocho caracteres del nombre del nivel, con algunas excepciones. (Por ejemplo, en los nombres de los archivos de nivel "BLOCK BUSTER" y "BLOCK BUSTER II" se omite la palabra "buster" para que no coincidan).

  Niveles de $ ls |  wc
      17 148 1974

Hay 148 archivos de datos en el directorio, y el juego en realidad tiene exactamente 148 niveles, por lo que aquí todo es igual.

Ahora examinemos qué son estos archivos. xxd es una utilidad estándar para descargar datos hexadecimales (hexdump). Veamos cómo se ve dentro de la LECCIÓN 1.

  $ xxd niveles / lección_1.pak
 00000000: 1100 cb00 0200 0004 0202 0504 0407 0505 ................
 00000010: 0807 0709 0001 0a01 010b 0808 0d0a 0a11 ................
 00000020: 0023 1509 0718 0200 2209 0d26 0911 270b. # ...... ".. & .. '.
 00000030: 0b28 0705 291e 0127 2705 020d 0122 0704. (..) ..''.... "..
 00000040: 0902 090a 0215 0426 0925 0111 1502 221d ....... &.% .... ".
 00000050: 0124 011d 0d01 0709 0020 001b 0400 1a00. $ ....... ......
 00000060: 2015 2609 1f00 3300 2911 1522 2302 110d. & ... 3.) .. "# ...
 00000070: 0107 2609 1f18 2911 1509 181a 0223 021b .. & ...) ...... # ..
 00000080: 0215 2201 1c01 1c0d 0a07 0409 0201 0201 .. ".............
 00000090: 2826 0123 1505 0902 0121 1505 220a 2727 (&. # .....! .. ". ''
 000000a0: 0b05 0400 060b 0828 0418 780b 0828 0418 ....... (.. x .. (..
 000000b0: 700b 0828 0418 6400 1710 1e1e 1a19 0103 p .. (.. d .........
 000000c0: 000e 1a17 1710 0e1f 010e 1314 1b29 1f1a .............) ..
 000000d0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................
 000000e0: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-.  ....
 000000f0: 1024 291f 1a01 1a1b 1019 000f 1a1a 1d1e. $) .............
 00000100: 2d02

¿Qué es una utilidad hexdump? Un volcado hexadecimal es una forma estándar de mostrar los bytes exactos de un archivo binario. La mayoría de los valores de bytes no se pueden asociar con caracteres ASCII imprimibles, o tienen una apariencia incomprensible (como un carácter de tabulación). En un volcado hexadecimal, los bytes individuales se emiten como valores numéricos. Los valores se muestran en hexadecimal, de ahí el nombre. En el ejemplo anterior, se muestran 16 bytes en una línea de salida. La columna más a la izquierda muestra la posición de la línea en el archivo, también en hexadecimal, por lo que el número en cada línea aumenta en 16. Los bytes se muestran en ocho columnas y se muestran dos bytes en cada columna. El hexdump de la derecha muestra cómo se verían los bytes cuando se muestran con caracteres, solo todos los valores ASCII no imprimibles se reemplazan por puntos. Esto facilita la búsqueda de cadenas que se pueden incrustar en un archivo binario.

Obviamente, la ingeniería inversa de estos archivos no se reducirá a solo explorar los contenidos y explorar lo que está visible allí. Hasta ahora, no hay nada que nos diga qué funciones realizan los datos.

¿Qué esperamos ver?

Retrocedamos y aclaremos la situación: ¿qué datos específicos esperamos encontrar en estos archivos de datos?

Lo más obvio es un cierto "mapa" del nivel: datos que indican las posiciones de paredes y puertas, así como todo lo demás, lo que hace que el nivel sea único.

(Afortunadamente para nosotros, los fanáticos del juego hicieron un trabajo minucioso y recolectaron mapas completos para los 148 niveles, por lo que podemos usarlos para saber qué debería estar en cada mapa).

Además del mapa, cada nivel debe tener varios otros atributos. Por ejemplo, puede observar que cada nivel tiene un nombre, por ejemplo, "LECCIÓN 1", "PARTIDO PERFECTO", "SORTEADO Y CUARTRADO", y así sucesivamente. Los diferentes niveles también tienen límites de tiempo diferentes, por lo que podemos suponer que esta información también está contenida en los datos. Además, cada nivel tiene su propio número de chips ensamblados. (Podríamos suponer que este número simplemente corresponde al número de chips en el nivel, pero resulta que en algunos niveles hay más chips de los necesarios para abrir el conector del chip. Al menos para estos niveles, el número mínimo debe indicarse en forma explícita).

Otro dato que esperamos encontrar en los datos de nivel es el texto de la sugerencia. En algunos niveles hay un "botón de sugerencia": un gran signo de interrogación tirado en el suelo. Cuando el Chip se levanta, se muestra un texto de información sobre herramientas. El botón de pista está a unos 20 niveles.

Finalmente, cada nivel tiene una contraseña, una secuencia de cuatro letras que le permite al jugador continuar el juego desde este nivel. (Esta contraseña es necesaria porque Lynx no tiene un almacén de datos. Era imposible guardar juegos en la consola, por lo que podría seguir jugando después de encender la consola usando contraseñas).

Así que aquí está nuestra lista de datos relevantes:

Mapa de nivel
Nombre de nivel
Nivel de contraseña
Límite de tiempo
Numero de chips
Texto de información sobre herramientas

Vamos a estimar aproximadamente el tamaño total de los datos. La forma más fácil de determinar el límite de tiempo y la cantidad de fichas. Ambos parámetros pueden tener valores en el rango de 0 a 999, por lo que probablemente se almacenan como valores enteros con un tamaño total de 4 bytes. La contraseña siempre consta de cuatro letras, por lo que probablemente se almacena como cuatro bytes más, es decir, solo 8 bytes. La longitud de los nombres de los niveles varía de cuatro a diecinueve caracteres. Si suponemos que necesitamos otro byte para completar la línea, entonces esto es veinte bytes, es decir, el subtotal es 28 bytes. El texto de información sobre herramientas más largo tiene más de 80 bytes de tamaño; Si redondeamos este valor a 90, obtendremos 118 bytes en total.

¿Qué pasa con el esquema de nivel? La mayoría de los niveles tienen un tamaño de 32 × 32 fichas. Los niveles más grandes no existen. Algunos niveles son más bajos, pero sería lógico suponer que simplemente están incrustados en una tarjeta de 32 × 32. Si asumimos que se requiere un byte para un mosaico, entonces se necesitan 1024 bytes para el circuito completo. Es decir, en general, obtenemos una estimación aproximada de 1142 bytes por nivel. Por supuesto, esto es solo una estimación inicial aproximada. Es posible que algunos de estos elementos se almacenen de manera diferente, o que no se almacenen en absoluto dentro de los archivos de nivel. O pueden contener otros datos que no notamos o que no conocemos. Pero hasta ahora hemos sentado una buena base.

Habiendo decidido lo que esperamos ver en los archivos de datos, volvamos a estudiar lo que realmente contienen.

¿Qué hay y qué no?

Aunque a primera vista el archivo de datos parece completamente incomprensible, aún puede notar un par de puntos en él. En primer lugar, esto es lo que no vemos. Por ejemplo, no vemos el nombre del nivel o el texto de los consejos. Puedes entender que esto no es una coincidencia, habiendo estudiado otros archivos:

  $ niveles de cadenas / * |  menos
 : !!; #
 &> '' :: 4 #
 . ,,!
 -54 ";
 / Y 67
 !) 60
 <171
 * (0 *
 82> '= /
 8> <171 &&
 9> # 2 ') (
 ,) 9
  0hX
 `@PX
 ) "" *
 24 ** 5
 ;)) <
 B777: .. 22C1
 E ,, F
 -GDED
 EGFF16G ;; H <
 IECJ
 9K444
 = MBBB >> N9 "O" 9P3? Q
 líneas 1-24 / 1544 (más)

Aquí no se ve nada excepto fragmentos arbitrarios de basura ASCII.

Presumiblemente, en algún lugar de estos archivos hay nombres de nivel y sugerencias, pero no están almacenados en ASCII o han sufrido alguna transformación (por ejemplo, debido a la compresión).

También vale la pena señalar lo siguiente: el archivo apenas alcanza los 256 bytes de tamaño. Esto es bastante pequeño, considerando que inicialmente estimamos su tamaño en más de 1140 bytes.

La opción -S ordena los archivos en orden descendente de tamaño.

  $ ls -lS niveles |  cabeza
 total 592
 -rw-r - r-- 1 breadbox breadbox 680 23 de junio de 2015 mulligan.pak
 -rw-r - r-- 1 breadbox breadbox 675 23 de junio de 2015 shrinkin.pak
 -rw-r - r-- 1 breadbox breadbox 671 23 de junio de 2015 balls_o_.pak
 -rw-r - r-- 1 breadbox breadbox 648 23 de junio de 2015 cake_wal.pak
 -rw-r - r-- 1 breadbox breadbox 647 23 de junio de 2015 citybloc.pak
 -rw-r - r-- 1 breadbox breadbox 639 23 de junio de 2015 four_ple.pak
 -rw-r - r-- 1 breadbox breadbox 636 23 de junio de 2015 trust_me.pak
 -rw-r - r-- 1 breadbox breadbox 625 23 de junio de 2015 block_n_.pak
 -rw-r - r-- 1 breadbox breadbox 622 23 jun. 2015 mix_up.pak

El archivo más grande toma solo 680 bytes, y esto no es mucho. ¿Y cuál será el más pequeño?

La opción -r le dice a ls que invierta el orden.

  $ ls -lSr niveles |  cabeza
 total 592
 -rw-r - r-- 1 breadbox breadbox 206 23 de junio de 2015 kablam.pak
 -rw-r - r-- 1 breadbox breadbox 214 23 de junio de 2015 fortune_.pak
 -rw-r - r-- 1 breadbox breadbox 219 23 de junio de 2015 digdirt.pak
 -rw-r - r-- 1 breadbox breadbox 226 23 de junio de 2015 lección_2.pak
 -rw-r - r-- 1 breadbox breadbox 229 23 de junio de 2015 lección_8.pak
 -rw-r - r-- 1 breadbox breadbox 237 23 de junio de 2015 partial_.pak
 -rw-r - r-- 1 breadbox breadbox 239 23 de junio de 2015 knot.pak
 -rw-r - r-- 1 breadbox breadbox 247 23 de junio de 2015 cellbloc.pak
 -rw-r - r-- 1 breadbox breadbox 248 23 de junio de 2015 torturec.pak

El archivo más pequeño ocupa solo 206 bytes, que es más de tres veces más pequeño que el más grande. Este es un rango bastante amplio, teniendo en cuenta el hecho de que esperábamos aproximadamente los mismos tamaños de nivel.

En nuestra evaluación inicial, asumimos que la tarjeta necesitaría un byte por mosaico y solo 1024 bytes. Si reducimos esta estimación a la mitad, es decir, cada mosaico requerirá solo 4 bits (o dos mosaicos por byte), entonces la tarjeta seguirá ocupando 512 bytes. 512 es más pequeño que 680, pero aún más grande que la mayoría de los niveles. Y en cualquier caso, 4 bits proporcionarán solo 16 valores diferentes, y en el juego hay muchos más objetos diferentes.

Es decir, es obvio que las tarjetas no se almacenan en estos archivos en forma abierta. Utilizan una codificación más compleja, que proporciona una descripción más eficiente, y / o de alguna manera están comprimidos. Por ejemplo, en el nivel "LECCIÓN 1", podemos ver cómo las entradas faltantes para los mosaicos "vacíos" reducirán significativamente el tamaño general de los datos del mapa.

Podemos ver mapas de los archivos más grandes:

Nivel 57 Mapa: EXTRAÑO MAZE

Tarjeta de nivel 98: RESTRICCIÓN

y luego compárelos con mapas de los archivos más pequeños:

Tarjeta de nivel 106: KABLAM

Tarjeta de nivel 112: FORTUNE FAVORECE LA

Esta comparación respalda nuestra idea de que los archivos de datos pequeños corresponden a niveles más simples o contienen más redundancia. Por ejemplo, si los datos están comprimidos por algún tipo de codificación de longitud de ejecución, esto puede explicar fácilmente los intervalos de tamaño de diferentes archivos.

Si los archivos están realmente encriptados, lo más probable es que tengamos que descifrar la compresión antes de proceder a descifrar los datos de la tarjeta.

Estudiamos varios archivos al mismo tiempo.

Nuestro breve estudio del primer archivo de datos nos permitió hacer algunas suposiciones, pero no encontramos nada concreto. Como siguiente paso, comenzaremos a explorar los patrones de varios archivos de datos. Por ahora, suponemos que los 148 archivos usan el mismo esquema de orden para codificar datos, por lo que buscar patrones duplicados en estos archivos nos ayudará a comenzar.

Comencemos desde el comienzo de los mosaicos. Lo más probable es que la parte superior del archivo se use para almacenar "metadatos" que nos informan sobre el contenido del archivo. Al observar solo la primera línea del volcado hexadecimal, podemos realizar una comparación simple y rápida de los primeros 16 bytes y buscar patrones prominentes en ellos:

  $ para f en niveles / *;  hacer xxd $ f |  sed -n 1p;  hecho |  menos
 00000000: 2300 dc01 0300 0004 0101 0a03 030b 2323 # ............. ##
 00000000: 2d00 bf01 0300 0015 0101 2203 0329 2222 -... "..)"
 00000000: 2b00 a101 0301 0105 0000 0601 0207 0505 + ...............
 00000000: 1d00 d300 0200 0003 0101 0402 0205 0102 ................
 00000000: 2d00 7a01 0300 0006 1414 0701 0109 0303 -.z .............
 00000000: 3100 0802 0200 0003 0101 0502 0206 1313 1 ...............
 00000000: 1a00 b700 0200 0003 0100 0502 0206 0101 ................
 00000000: 1a00 0601 0300 0005 0001 0601 0107 0303 ................
 00000000: 2000 7a01 0200 0003 0202 0401 0105 0028 .z ............ (
 00000000: 3a00 a400 0200 0003 2828 0428 0205 0303: ....... ((. (....
 00000000: 2600 da00 0300 0004 0507 0901 010a 0303 y ...............
 00000000: 2400 f000 0300 0004 0303 0504 0407 0101 $ ...............
 00000000: 2a00 ef01 0300 0005 0101 0614 0007 0303 * ...............
 00000000: 2c00 8c01 0300 0004 0303 0500 0107 0101, ...............
 00000000: 2a00 0001 0300 0004 0303 0501 0107 0404 * ...............
 00000000: 1b00 6d01 0200 0003 0101 0502 0206 0003 ..m .............
 00000000: 1e00 1701 0200 0003 0202 0401 0105 0013 ................
 00000000: 3200 ee01 0f00 0015 0101 270f 0f29 1414 2 ......... '..) ..
 00000000: 2a00 5b01 0300 0005 0303 0601 0107 1414 *. [.............
 00000000: 2c00 8a01 0200 0003 0202 0401 0105 0303, ...............
 00000000: 1d00 9c00 0216 1604 0000 0516 0107 0205 ................
 00000000: 2000 e100 0200 0003 0101 0402 0205 0303 ...............
 00000000: 2000 2601 0300 0004 0303 0502 0207 0101. & .............
 00000000: 1f00 f600 0132 0403 0000 0532 3206 0404 ..... 2 ..... 22 ...
 líneas 1-24 / 148 (más)

Al observar este volcado, puede ver que en cada columna hay algunos valores similares.

Comenzando con el primer byte, pronto nos damos cuenta de que su valor está en un rango muy limitado de valores, en el rango de hexadecimal 40 (o aproximadamente 20–60 en decimal). Esta es una característica bastante específica.

Aún más interesante es que el segundo byte de cada archivo siempre es cero, sin excepciones. El segundo byte probablemente no se usa o es un marcador de posición. Sin embargo, existe otra posibilidad: estos dos primeros bytes juntos representan un valor de 16 bits almacenado en orden little endian.

¿Qué es little endian? Al almacenar un valor numérico que es más de un byte, primero debe seleccionar el orden en que se almacenarán los bytes. Si primero almacena un byte que representa la parte más pequeña del número, esto se llama orden directo ( little-endian ); si primero almacena bytes que denotan la mayor parte del número, entonces este es el orden inverso ( big-endian ). Por ejemplo, escribimos los valores decimales en orden inverso (big-endian): la línea "42" significa "cuarenta y dos", no "cuatro y veinte". Little-endian es un orden natural para muchas familias de microprocesadores, por lo que suele ser más popular, con la excepción de los protocolos de red, que generalmente requieren big-endian.

Si continuamos el análisis, pronto veremos que el tercer byte en el archivo no es similar a los dos anteriores: su valor varía en un amplio rango. Sin embargo, el cuarto byte siempre es 00 , 01 o 02 , y 01 es el más común. Esto también nos sugiere que estos dos bytes constituyen otro valor de 16 bits, que está aproximadamente en el rango de valores decimales 0-700. Esta hipótesis también puede confirmarse por el hecho de que el valor del tercer byte suele ser bajo si el valor del cuarto byte es 02 , y generalmente grande si el cuarto byte es 00 .

Por cierto, vale la pena señalar que esta es en parte la razón por la que el formato de volcado hexadecimal muestra bytes en pares de forma predeterminada, esto facilita la lectura de una secuencia de números enteros de 16 bits. El formato de volcado hexadecimal se estandarizó cuando se usaban computadoras de 16 bits. Intente reemplazar xxd con xxd -g1 para deshabilitar por completo la agrupación, y notará que reconocer pares de bytes en el medio de una línea es mucho trabajo. Este es un ejemplo simple de cómo las herramientas utilizadas para estudiar datos desconocidos tienden a hacernos notar ciertos tipos de patrones. Es bueno que xxd resalte este patrón de forma predeterminada porque es muy común (incluso hoy, cuando las computadoras de 64 bits se usan en todas partes). Pero es útil saber cómo cambiar estos parámetros si no ayudan.

Continuemos la exploración visual y veamos si este patrón se conserva de los valores enteros de 16 bits. El quinto byte generalmente tiene valores muy bajos: 02 y 03 encuentran con mayor frecuencia, y el valor máximo parece ser 05 . El sexto byte de un archivo es a menudo cero, pero a veces contiene valores mucho más grandes, como 32 o 2C . En este par, nuestra suposición sobre los valores distribuidos en el intervalo no está particularmente confirmada.

Estudiamos cuidadosamente los valores iniciales.

Podemos probar nuestra suposición utilizando od para generar un volcado hexadecimal. La utilidad od es similar a xxd , pero proporciona una selección mucho mayor de formatos de salida. Podemos usarlo para volcar la salida como enteros decimales de 16 bits:

La opción -t de la utilidad od especifica el formato de salida. En este caso, u representa números decimales sin signo y 2 representa dos bytes por registro. (También puede especificar este formato utilizando la opción -d ).

  $ para f en niveles / *;  do od -tu2 $ f |  sed -n 1p;  hecho |  menos
 0000000 35 476 3 1024 257 778 2819 8995
 0000000 45447 3 5376 257 802 10499 8738
 0000000 43417259 1281 0262 1794 1285
 0000000 29211 2 768 257 516 1282 513
 0000000 45378 3 1536 5140 263 2305 771
 0000000 49 520 2 768 257 517 1538 4883
 0000000 26183 2768 1517 1538257
 0000000 26262 3 1280 256 262 1793 771
 0000000 32378 2 768 514 260 1281 10240
 0000000 58164 2768 10280 10244 1282 771
 0000000 38218 3224 1797265 2561 771
 0000000 36240 3 1024771 1029 1796 257
 0000000 42495 3 1280 257 5126 1792 771
 0000000 44396 3 1024 771 5 1793 257
 0000000 42256 3 1024 771 261 1793 1028
 0000000 27 365 2 768 257 517 1538 768
 0000000 30279 2768514260 1281 4864
 0000000 50494 15 5376 257 3879 10511 5140
 0000000 42347 3 1280771262 1793 5140
 0000000 44394 2 768 514 260 1281 771
 0000000 29156 5634 1046 0 5637 1793 1282
 0000000 32 225 2 768 257 516 1282 771
 0000000 32 294 3 1024 771 517 1794 257
 0000000 31246 12801 772 0 12805 1586 1028
 líneas 1-24 / 148 (más)

Este resultado muestra que nuestras suposiciones sobre los primeros bytes fueron correctas. Vemos que el primer valor de 16 bits está en el rango decimal de 20–70, y el segundo valor de 16 bits está en el rango decimal de 100–600. Sin embargo, los valores posteriores no se comportan tan bien. Ciertos patrones aparecen en ellos (por ejemplo, en la cuarta posición, sorprendentemente a menudo 1024), pero no tienen la repetibilidad inherente a los primeros valores del archivo.

Por lo tanto, supongamos primero que los primeros cuatro bytes del archivo son especiales y consisten en dos valores de 16 bits. Como están al comienzo del archivo, es probable que sean metadatos y ayudan a determinar cómo leer el resto del archivo.

De hecho, el segundo intervalo de valores (100–600) está bastante cerca del intervalo de tamaño de archivo que notamos anteriormente (208–680). Tal vez esto no es una coincidencia? Presentemos una hipótesis: el valor de 16 bits almacenado en el tercer y cuarto bytes del archivo se correlaciona con el tamaño total del archivo. Ahora que tenemos una hipótesis, podemos probarla. Veamos si los archivos grandes en este lugar realmente tienen valores grandes en todo momento, y los pequeños tienen valores pequeños.

Para mostrar el tamaño del archivo en bytes sin ninguna otra información, puede usar wc con la opción -c . Del mismo modo, puede agregar opciones a od que le permitan mostrar solo los valores que nos interesan. Luego podemos usar la sustitución de comandos para escribir estos valores en las variables de shell y mostrarlos juntos:

La opción -An de la utilidad od deshabilita la columna más a la izquierda, que muestra el desplazamiento en el archivo, y -N4 le dice a od detenga después de los primeros 4 bytes del archivo.

  $ para f en niveles / *;  hacer tamaño = $ (wc -c <$ f);  datos = $ (od -tuS -An -N4 $ f);  echo "$ tamaño: $ datos";  hecho |  menos
 585: 35 476
 586: 45 447
 550: 43,417
 302: 29,211
 517: 45 378
 671: 49 520
 265: 26 183
 344: 26,262
 478: 32,378
 342: 58 164
 336: 38 218
 352: 36,240
 625: 42 495
 532: 44,396
 386: 42,256
 450: 27 365
 373: 30 279
 648: 50 494
 477: 42 347
 530: 44,394
 247: 29 156
 325: 32,225
 394: 32,294
 343: 31,246

Mirando esta salida, puede ver que los valores están aproximadamente correlacionados. Los archivos más pequeños generalmente tienen valores más bajos en la segunda posición, y los archivos más grandes tienen valores más grandes. Sin embargo, la correlación no es precisa y vale la pena señalar que el tamaño del archivo siempre es significativamente mayor que el valor almacenado en él.

Además, el primer valor de 16 bits también suele ser más grande con archivos de gran tamaño, pero la coincidencia tampoco es completa y puede encontrar fácilmente ejemplos de archivos de tamaño mediano con valores relativamente grandes en la primera posición. Pero tal vez si sumamos estos dos valores, ¿su suma estará mejor correlacionada con el tamaño del archivo?

Podemos usar readpara extraer dos números de la salida oden variables separadas, y luego usar la aritmética de shell para encontrar su suma:

comando de Shellreadno se puede usar en el lado derecho de la barra vertical, porque los comandos transferidos a la tubería se ejecutan en un procesador de comandos secundario (subshell) que, cuando sale, lleva sus variables de entorno al receptor de bits. Por lo tanto, en su lugar, debemos usar la función de sustitución del proceso bashy dirigir la salida oda un archivo temporal, que luego se puede redirigir al comando read.

$ para f en niveles / *; hacer tamaño = $ (wc -c <$ f); lea v1 v2 << (od -tuS -An -N4 $ f); suma = $ (($ v1 + $ v2));
    echo "$ tamaño: $ v1 + $ v2 = $ suma"; hecho | menos
585: 35 + 476 = 511
586: 45 + 447 = 492
550: 43 + 417 = 460
302: 29 + 211 = 240
517: 45 + 378 = 423
671: 49 + 520 = 569
265: 26 + 183 = 209
344: 26 + 262 = 288
478: 32 + 378 = 410
342: 58 + 164 = 222
336: 38 + 218 = 256
352: 36 + 240 = 276
625: 42 + 495 = 537
532: 44 + 396 = 440
386: 42 + 256 = 298
450: 27 + 365 = 392
373: 30 + 279 = 309
648: 50 + 494 = 544
477: 42 + 347 = 389
530: 44 + 394 = 438
247: 29 + 156 = 185
325: 32 + 225 = 257
394: 32 + 294 = 326
343: 31 + 246 = 277
líneas 1-24 / 148 (más)

La suma de los dos números también se correlaciona aproximadamente con el tamaño del archivo, pero aún no coinciden. ¿Qué tan diferentes son? Demostremos su diferencia:

$ para f en niveles / *; hacer tamaño = $ (wc -c <$ f); lea v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ tamaño - $ v1 - $ v2));
    echo "$ tamaño = $ v1 + $ v2 + $ diff"; hecho | menos
585 = 35 + 476 + 74
586 = 45 + 447 + 94
550 = 43 + 417 + 90
302 = 29 + 211 + 62
517 = 45 + 378 + 94
671 = 49 + 520 + 102
265 = 26 + 183 + 56
344 = 26 + 262 + 56
478 = 32 + 378 + 68
342 = 58 + 164 + 120
336 = 38 + 218 + 80
352 = 36 + 240 + 76
625 = 42 + 495 + 88
532 = 44 + 396 + 92
386 = 42 + 256 + 88
450 = 27 + 365 + 58
373 = 30 + 279 + 64
648 = 50 + 494 + 104
477 = 42 + 347 + 88
530 = 44 + 394 + 92
247 = 29 + 156 + 62
325 = 32 + 225 + 68
394 = 32 + 294 + 68
343 = 31 + 246 + 66
lines 1-24/148 (more)

La diferencia, o el valor "restante", se muestra en el lado derecho de la salida. Este valor no cae dentro del patrón constante, pero parece permanecer aproximadamente en un rango limitado de 40-120. Y de nuevo, cuanto más grandes son los archivos, generalmente más de su valor residual. Pero a veces los archivos pequeños también tienen valores residuales grandes, por lo que esto no es tan constante como nos gustaría.

Sin embargo, vale la pena señalar que los valores de los residuos nunca son negativos. Por lo tanto, la idea de que estos dos valores de metadatos indican subsecciones de un archivo sigue siendo atractiva.

(Si eres lo suficientemente cuidadoso, ya has visto algo que da una pista sobre una conexión que aún no se ha notado. Si no lo has hecho, continúa leyendo; el secreto pronto será revelado).

Grandes comparaciones entre archivos

En este punto, sería bueno poder realizar una comparación cruzada de más de 16 bytes a la vez. Para esto necesitamos un tipo diferente de visualización. Uno de los buenos enfoques es crear una imagen en la que cada píxel denote un byte separado de uno de los archivos, y el color denote el valor de este byte. Una imagen puede mostrar una porción de los 148 archivos a la vez si cada archivo de datos se indica mediante una sola fila de píxeles de imagen. Como todos los archivos son de diferentes tamaños, tomamos los primeros 200 bytes de cada uno para construir una imagen rectangular.

La forma más fácil es construir una imagen en escala de grises, en la que el valor de cada byte corresponde a diferentes niveles de gris. Es muy sencillo crear un archivo PGM con nuestros datos, porque el encabezado PGM consta de solo texto ASCII:

 $ echo P5 200 148 255 >hdr.pgm

PGM? PGM, «portable graymap» (« ») — , : ASCII, . — PBM («portable bitmap», « »), 8 , PPM («portable pixmap», « »), 3 .

P5Es la firma inicial para el formato de archivo PGM. Los siguientes dos números, 200y 148, especifican el ancho y la altura de la imagen, y el último 255, indica el valor máximo por píxel. El encabezado PGM termina con una nueva línea seguida de datos de píxeles. (Vale la pena señalar que el encabezado PGM a menudo se divide en tres líneas de texto separadas, pero el estándar PGM solo requiere que los elementos estén separados por algún carácter de espacio en blanco).

Podemos usar la utilidad headpara extraer los primeros 200 bytes de cada archivo:

$ para f en niveles / *; hacer cabeza -c200 $ f; hecho> out.pgm

Luego podemos concatenarlos con un encabezado y crear una imagen visualizada:

xvieweste es un antiguo programa X para mostrar imágenes en una ventana. Puede reemplazarlo con su visor de imágenes favorito, por ejemplo, una utilidad displayde ImageMagick, pero tenga en cuenta que sorprendentemente hay muchos visores de imágenes que no aceptan un archivo de imagen redirigido a la entrada estándar.

$ cat hdr.pgm out.pgm | xview / dev / stdin

Si le resulta difícil ver los detalles en una imagen oscura, puede elegir un esquema de color diferente. Use la utilidad pgmtoppmde ImageMagick para convertir píxeles a un rango diferente de colores. Esta versión creará una imagen "negativa":

$ cat hdr.pgm out.pgm | pgmtoppm blanco-negro | xview / dev / stdin

Y esta versión hace que los valores bajos sean amarillos y los valores altos azules:

$ cat hdr.pgm out.pgm | pgmtoppm amarillo-azul | xview / dev / stdin

La visibilidad de los colores es una pregunta muy subjetiva, por lo que puede experimentar y elegir cuál es el mejor para usted. Sea como fuere, la imagen de 200 × 148 es bastante pequeña, por lo que es mejor aumentar la visibilidad aumentando su tamaño:

$ cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

La imagen es oscura, y esto significa que la mayoría de los bytes contienen valores pequeños. Una franja notable de píxeles en su mayoría brillantes más cerca del borde izquierdo contrasta con él. Esta tira se encuentra en el tercer byte del archivo, que, como dijimos anteriormente, varía en el rango completo de valores.

Y aunque no hay muchos valores altos fuera del tercer byte, cuando aparecen, a menudo consisten en series, creando rayas cortas y brillantes en la imagen. Algunas de estas series se interrumpen periódicamente, creando un efecto de línea discontinua. (Quizás, con la selección de color correcta, será posible notar tales secuencias en colores más oscuros).

Con un estudio cuidadoso de la imagen, se puede entender que principalmente en la parte izquierda dominan pequeñas rayas verticales. Estas bandas nos informan sobre cierta repetibilidad en la mayoría de los archivos. Pero no en todos los archivos, de vez en cuando hay líneas de píxeles donde se interrumpen las bandas, pero esto es más que suficiente para determinar la presencia de un patrón real. Este patrón desaparece en el lado derecho de la imagen, el fondo oscuro de las rayas da paso a algo más ruidoso e indefinido. (Parece que también faltan las rayas en la parte izquierda de la imagen, pero, repito, es posible que al usar un esquema de color diferente, pueda ver que comienzan más cerca del borde izquierdo de lo que parece aquí).

Las franjas consisten en líneas finas de píxeles ligeramente más brillantes sobre un fondo de píxeles ligeramente más oscuros. Por lo tanto, este patrón gráfico debe correlacionarse con el patrón de los archivos de datos en los que valores ligeramente más grandes están igualmente dispersos entre los valores de bytes ligeramente más pequeños. Parece que las rayas se agotan aproximadamente en el medio de la imagen. Como muestra los primeros 200 bytes de archivos, debe esperar que el patrón de bytes finalice después de aproximadamente 100 bytes.

El hecho de que estos patrones cambien en diferentes archivos de datos debería llevarnos a la pregunta: ¿cómo serán los archivos después de los primeros 200 bytes? Bueno, podemos reemplazar fácilmente la utilidad con una headutilidad taily ver cómo se ven los últimos 200 bytes:

$ para f en niveles / *; hacer cola -c200 $ f; done> out.pgm; gato hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

Inmediatamente vemos que esta área de archivos de datos es muy diferente. Aquí, los bytes son mucho más comunes, especialmente hacia el final del archivo. (Sin embargo, como antes, prefieren agruparse, cubriendo la imagen con franjas horizontales brillantes.) Parece que la frecuencia de los valores de bytes altos aumenta casi hasta el final, donde se rompe abruptamente y se reemplaza por valores bajos en aproximadamente diez a doce bytes. Y el patrón aquí tampoco es universal, pero es demasiado estándar para ser una coincidencia.

Quizás en el medio de los archivos puede haber otras áreas que aún no hemos considerado. Lo siguiente que queremos hacer es examinar los archivos completos de esta manera. Pero dado que todos los archivos tienen diferentes tamaños, no se pueden colocar en una hermosa matriz rectangular de píxeles. Podemos llenar el final de cada línea con píxeles negros, pero sería mejor cambiarles el tamaño para que todas las líneas tengan el mismo ancho y las áreas proporcionales de los diferentes archivos coincidan más o menos.

Y en realidad podemos hacer esto con un poco más de esfuerzo. Puede usar Python y su biblioteca para trabajar con imágenes PIL("Pillow"):

archivo showbytes.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a grayscale image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('L', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() for x in range(linewidth): linepixels[x,0] = ord(data[x]) # Stretch the line out to fit the final image, and paste it into place. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Cuando llamamos a este script, usando la lista completa de archivos de datos como argumentos, creará una imagen completa y la mostrará en una ventana separada:

 $ python showbytes.py niveles / *

Desafortunadamente, aunque esta imagen está completa, no nos muestra nada nuevo. (Pero en realidad se muestra aún menos, porque el cambio de tamaño destruyó el patrón de las franjas). Probablemente, para estudiar todo el conjunto de datos, necesitamos un mejor proceso de visualización.

Caracterizar los datos.

Con esto en mente, detengámonos por un momento y completemos un censo completo de datos. Necesitamos saber si los archivos de datos dan preferencia a ciertos valores de bytes. Por ejemplo, si cada valor suele estar igualmente duplicado, esto será una fuerte evidencia de que los archivos están realmente comprimidos.

Para

reescribir completamente los valores, solo unas pocas líneas en Python son suficientes: El archivo census.py:

 import sys data = sys.stdin.read() for c in range(256): print c, data.count(chr(c))

Después de haber insertado todos los datos en una variable, podemos calcular la frecuencia de aparición de cada valor de byte.

$ niveles de gato / * | python ./census.py | menos
0 2458
1 2525
2 1626
3 1768
4 1042
5 1491
6 1081
7 1445
8 958
9 1541
10 1279
11 1224
12,845
13 908
14 859
15 1022
16 679
17 1087
18,881
19 1116
20 1007
21 1189
22 1029
23,733
líneas 1-24 / 256 (más)

Vemos que con mayor frecuencia hay valores de bytes 0 y 1, los siguientes en frecuencia son 2 y 3, después de lo cual el número continúa disminuyendo (aunque con menos constancia). Para visualizar mejor estos datos, podemos transferir la salida gnuploty convertir este censo en un histograma:

la opción de -putilidad gnuplotordena no cerrar la ventana con el gráfico después de completar el trabajo gnuplot.

$ niveles de gato / * | python ./census.py | gnuplot -p -e 'plot "-" con cajas'

Es muy notable que los primeros valores de byte son mucho más comunes que todos los demás. Varios de los siguientes valores también son bastante comunes, y luego las frecuencias de valores de aproximadamente 50 comienzan a disminuir a lo largo de una curva de probabilidad suave. Sin embargo, hay un subconjunto de valores altos que se separan uniformemente entre sí, cuya frecuencia parece bastante estable. Al observar la salida original, podemos asegurarnos de que este subconjunto esté formado por valores que pueden ser divisibles por ocho.

Estas diferencias en el número de valores sugieren que hay varias "clases" diferentes de valores de bytes, por lo que será lógico ver cómo se distribuyen estas clases. El primer grupo de valores de bytes serán los valores más bajos: 0, 1, 2 y 3. Luego, el segundo grupo puede tener valores de 4 a 64. Y el tercer grupo tendrá valores superiores a 64, que son divisibles por 8. Sin dejar rastro, todo lo demás, incluido no divisible por 8 valores mayores que 64 será el cuarto y último grupo.

Con todo esto en mente, podemos cambiar el último script de generación de imágenes escrito. En lugar de mostrar los valores reales de cada byte en un color separado, vamos a mostrar a qué grupo pertenece cada byte. Puede asignar un color único a cada uno de los cuatro grupos, y esto nos ayudará a ver si ciertos valores realmente aparecen en ciertos lugares.

Archivo Showbytes2.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a color image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('RGB', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() # Determine which group each byte belongs to and assign it a color. for x in range(linewidth): byte = ord(data[x]) if byte < 0x04: linepixels[x,0] = (255, 0, 0) elif byte < 0x40: linepixels[x,0] = (0, 255, 0) elif byte % 8 == 0: linepixels[x,0] = (0, 0, 255) else: linepixels[x,0] = (255, 255, 255) # Paste the line of pixels into the final image, stretching to fit. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Asignamos cuatro grupos rojo, verde, azul y blanco. (Nuevamente, puede intentar elegir otros colores que se adapten a sus preferencias).

 $ python showbytes2.py niveles / *

Gracias a esta imagen, podemos confirmar previamente la exactitud de la separación de los archivos de datos en cinco partes:

El encabezado de cuatro bytes que encontramos anteriormente.
, , (.. ).
, (. 64).
, .
, .

Gracias a estos colores, está claro que en la cuarta parte, donde prevalecen los valores de byte alto, como se puede ver en la imagen en escala de grises, prevalecen especialmente los valores de byte alto, dividiendo entre 8.

De la imagen anterior sabemos que la segunda parte, es decir, la parte con rayas se extiende sobre un área casi completamente roja. De hecho, en una de las primeras imágenes vimos que la parte con rayas, que va de izquierda a derecha, se ilumina lentamente en promedio.

Vemos nuevamente que los píxeles verdes de la tercera parte principal forman patrones punteados de píxeles verdes y rojos intermitentes (ya sea azul o blanco) de vez en cuando. Sin embargo, este patrón no es particularmente regular y puede ser imaginario.

Por supuesto, esta división del archivo en cinco partes es muy arbitraria. Una cuarta parte con valores de bytes altos divisibles por ocho puede resultar ser solo el final de la tercera parte. O puede resultar que es mejor dividir una tercera parte grande en varias partes que aún no hemos determinado. En esta etapa, el descubrimiento de piezas nos ayuda más a encontrar lugares para futuras investigaciones. Por ahora, es suficiente para nosotros saber que hay partes en las que cambia la composición general de los valores de bytes, y una idea aproximada de su tamaño nos ayudará a continuar nuestra investigación.

Búsqueda de estructura

¿Qué debemos buscar a continuación? Bueno, como antes, la forma más fácil de comenzar es desde la parte superior del archivo. O más bien, cerca de la cima. Como ya hemos identificado con bastante confianza la primera parte como un encabezado de cuatro bytes, echemos un vistazo más de cerca a lo que viene a continuación: el área que llamamos la segunda parte, o parte de las bandas. Estas bandas son el indicio más fuerte de la existencia de la estructura, por lo tanto, es mejor buscar nuevas evidencias de la presencia del patrón aquí.

(Por el momento, suponemos que el patrón de tira comienza inmediatamente después de los primeros cuatro bytes. Visualmente, esto no es obvio, pero parece probable, y examinar los valores de los bytes debería mostrarnos rápidamente la verdad).

Volvamos al volcado hexadecimal, esta vez centrándonos en la segunda parte. Recuerde que esperamos encontrar un patrón repetitivo de valores ligeramente más altos distribuidos uniformemente entre valores ligeramente más bajos.

La opción -s4ordena xxdomitir los primeros 4 bytes del archivo.

$ para f en niveles / *; do xxd -s4 $ f | sed -n 1p; hecho | menos
00000004: 0200 0003 0202 0401 0105 0303 0700 0108 ................
00000004: 0201 0104 0000 0504 0407 0202 0902 010a ................
00000004: 0300 0004 0303 0504 0407 0505 0801 0109 ................
00000004: 0300 0009 0202 1203 0313 0909 1401 0115 ................
00000004: 0203 0305 0000 0602 0207 0505 0901 010a ................
00000004: 0203 0304 0000 0502 0206 0404 0901 010a ................
00000004: 0300 0005 022a 0602 2907 0303 0902 000a ..... * ..) .......
00000004: 0203 0305 0000 0605 0507 0101 0802 0209 ................
00000004: 0300 0007 0303 0901 010a 0707 0b09 090c ................
00000004: 0300 0004 0101 0903 030e 0404 1609 0920 ...............
00000004: 0200 0003 1313 0402 0205 0013 0701 0109 ................
00000004: 0500 0006 0505 0701 0109 0606 0e07 070f ................
00000004: 0100 0003 0101 0a03 030b 0a0a 0e32 3216 .............22.
00000004: 0300 0004 0705 0903 030a 0606 0b08 080c ................
00000004: 0200 0003 0701 0402 0209 0501 0a08 080b ................
00000004: 0200 0003 0202 0901 010a 0303 0b05 010d ................
00000004: 0200 0003 0202 0403 0305 0101 0904 040a ................
00000004: 0300 0007 0303 0f01 0115 0707 2114 1422 ............!.."
00000004: 0200 0003 0202 0403 0309 0101 0a04 040b ................
00000004: 0231 3103 0202 0500 0006 0303 0701 0109 .11.............
00000004: 0200 0003 0202 0b32 320c 0303 0e08 0811 .......22.......
00000004: 0201 0103 0000 0902 020a 0303 0b09 090c ................
00000004: 0200 0003 0202 0a01 010b 0303 0d0b 0b0f ................
00000004: 0300 0005 0303 0701 0109 0001 0b05 051b ................
lines 27-50/148 (more)

Al observar cuidadosamente la secuencia de bytes en la cadena, podemos ver un patrón en el que los bytes primero, cuarto, séptimo y décimo son más grandes que sus vecinos más cercanos. Este patrón es imperfecto, tiene excepciones, pero definitivamente es lo suficientemente estable como para crear la repetibilidad visual de las bandas que se ven en todas las imágenes. (Y es suficiente para confirmar nuestra suposición de que el patrón de rayas comienza inmediatamente después del encabezado de cuatro bytes). La

constancia de este patrón implica claramente que esta parte del archivo es una matriz o tabla, y cada registro en la matriz tiene una longitud de tres bytes.

Puede configurar el formato de volcado hexadecimal para que sea más fácil ver la salida como una serie de tripletes:

la opción -g3establece la agrupación por tres bytes en lugar de dos. Opcion-c18 establece 18 bytes (un múltiplo de 3) por línea en lugar de 16.

$ para f en niveles / *; do xxd -s4 -g3 -c18 $ f | sed -n 1p; hecho | menos
00000004: 050000 060505 070101 090606 0e0707 0f0001 ..................
00000004: 010000 030101 0a0303 0b0a0a 0e3232 161414 ............. 22 ...
00000004: 030000 040705 090303 0a0606 0b0808 0c0101 ..................
00000004: 020000 030701 040202 090501 0a0808 0b0101 ..................
00000004: 020000 030202 090101 0a0303 0b0501 0d0302 ..................
00000004: 020000 030202 040303 050101 090404 0a0302 ..................
00000004: 030000 070303 0f0101 150707 211414 221313 ............! .. "..
00000004: 020000 030202 040303 090101 0a0404 0b0001 ..................
00000004: 023131 030202 050000 060303 070101 090505 .11 ...............
00000004: 020000 030202 0b3232 0c0303 0e0808 110b0b ....... 22 .........
00000004: 020101 030000 090202 0a0303 0b0909 0c0a0a ..................
00000004: 020000 030202 0a0101 0b0303 0d0b0b 0f2323 ................##
00000004: 030000 050303 070101 090001 0b0505 1b0707 ..................
00000004: 022323 030000 040202 050303 030101 070505 .##...............
00000004: 031414 050000 060303 070505 080101 090707 ..................
00000004: 030000 050202 060303 070505 080101 090606 ..................
00000004: 030202 040000 050303 070404 080005 090101 ..................
00000004: 030202 040000 050303 090404 1d0101 1f0909 ..................
00000004: 020000 050303 060101 070202 0f0300 110505 ..................
00000004: 050000 070101 0c0505 0d0007 110c0c 120707 ..................
00000004: 030202 050000 060303 070505 080101 090606 ..................
00000004: 020000 030101 050202 060505 070100 080303 ..................
00000004: 020000 030202 050303 090101 0a0505 0b0302 ..................
00000004: 022c2c 030000 040202 020303 050101 060202 .,,...............
lines 38-61/148 (more)

En un volcado formateado de esta forma, algunas otras características de este patrón comienzan a aparecer. Como antes, el primer byte de cada triplete suele ser mayor que los bytes que lo rodean. También puede notar que los bytes segundo y tercero de cada triplete a menudo están duplicados. Al bajar la primera columna, veremos que la mayoría de los valores del segundo y tercer bytes son iguales 0000. Pero los valores distintos de cero también se encuentran a menudo en pares, por ejemplo, 0101o 2323. Este patrón también es imperfecto, pero tiene demasiado en común como para ser una coincidencia. Y mirando la columna ASCII a la derecha, veremos que cuando tenemos valores de bytes que corresponden al carácter ASCII imprimible, a menudo se encuentran en pares.

Otro patrón digno de mención que no se nota de inmediato: el primer byte de cada triple aumenta de izquierda a derecha. Aunque este patrón es menos notable, su estabilidad es alta; Necesitamos mirar muchas líneas antes de encontrar el primer desajuste. Y los bytes generalmente aumentan en valores pequeños, pero no representan ningún patrón regular.

Al estudiar la imagen original, notamos que la parte con las rayas termina en cada archivo no en el mismo lugar. Hay una transición de crear una franja de patrón a la izquierda a ruido aleatorio a la derecha, pero esta transición ocurre para cada fila de píxeles en diferentes puntos. Esto implica que debe haber algún marcador para que el programa que lee el archivo de datos pueda comprender dónde termina la matriz y comienza otro conjunto de datos.

Volvamos al volcado solo el primer nivel para examinar todo el archivo:

 $ xxd -s4 -g3 -c18 niveles / lección_1.pak
00000004: 020000 040202 050404 070505 080707 090001 ..................
00000016: 0a0101 0b0808 0d0a0a 110023 150907 180200 ........... # ......
00000028: 22090d 260911 270b0b 280705 291e01 272705 ".. & .. '.. (..) ..' '.
0000003a: 020d01 220704 090209 0a0215 042609 250111 ... "......... &.% ..
0000004c: 150222 1d0124 011d0d 010709 002000 1b0400 .. ".. $ ....... ....
0000005e: 1a0020 152609 1f0033 002911 152223 02110d ... & ... 3.) .. "# ...
00000070: 010726 091f18 291115 09181a 022302 1b0215 .. & ...) ...... # ....
00000082: 22011c 011c0d 0a0704 090201 020128 260123 "............. (&. #
00000094: 150509 020121 150522 0a2727 0b0504 00060b .....! .. ".''......
000000a6: 082804 18780b 082804 18700b 082804 186400 .(..x..(..p..(..d.
000000b8: 17101e 1e1a19 010300 0e1a17 17100e 1f010e ..................
000000ca: 13141b 291f1a 001210 1f011b 0c1e1f 011f13 ...)..............
000000dc: 10010e 13141b 001e1a 0e1610 1f2d00 201e10 .............-. ..
000000ee: 011610 24291f 1a011a 1b1019 000f1a 1a1d1e ...$).............
00000100: 2d02

Al estudiar la secuencia de tripletes, podemos suponer tentativamente que la parte con bandas en estos datos termina después de 17 tripletes, por desplazamiento 00000036. Esto no es exacto, pero el primer byte de cada triplete aumenta constantemente su valor y luego disminuye en el decimoctavo triplete. Una prueba más: en el decimoctavo triplete, el segundo byte tiene el mismo significado que el primero. Todavía no nos hemos dado cuenta de esto, pero si volvemos y miramos, veremos que el primer byte nunca es igual al segundo o tercer byte.

Si nuestra teoría de marcadores es correcta, entonces hay dos posibilidades. En primer lugar, es posible que después de la parte de la tira haya un valor de byte especial (justo después del decimoséptimo triplete). En segundo lugar, es probable que exista un valor almacenado en algún lugar que sea igual al tamaño de la parte con franjas. Este tamaño puede ser igual a 17 (es decir, indica el número de tripletes), o 51 (indica el número total de bytes en una parte), o 55 (51 más 4, es decir, el desplazamiento del archivo donde termina esta parte).

Para la primera opción, un valor de doble byte puede ser un marcador para el final de la parte (dado que dicha secuencia nunca ocurre en la segunda parte). Sin embargo, el estudio cuidadoso de varios otros archivos de datos contradice esta idea, porque ese patrón no aparece en ningún otro lugar.

Para la segunda opción, obviamente buscará el indicador de tamaño en la primera parte. He aquí, el primer valor de 16 bits en el encabezado del archivo de cuatro bytes es 17:

 $ od -An -tuS -N4 niveles / lección_1.pak
    17 203

Si nuestra teoría es correcta, entonces este valor no determina el tamaño de la parte con franjas, sino el número de registros de tres bytes. Para probar esta idea, volvamos a la informática, donde comparamos la suma de dos valores enteros de 16 bits con el tamaño del archivo. Esta vez multiplicamos el primer número por tres para obtener el tamaño real en bytes:

$ para f en niveles / *; hacer tamaño = $ (wc -c <$ f); lea v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ tamaño - 3 * $ v1 - $ v2));
    echo "$ tamaño = 3 * $ v1 + $ v2 + $ diff"; hecho | menos
585 = 3 * 35 + 476 + 4
586 = 3 * 45 + 447 + 4
550 = 3 * 43 + 417 + 4
302 = 3 * 29 + 211 + 4
517 = 3 * 45 + 378 + 4
671 = 3 * 49 + 520 + 4
265 = 3 * 26 + 183 + 4
344 = 3 * 26 + 262 + 4
478 = 3 * 32 + 378 + 4
342 = 3 * 58 + 164 + 4
336 = 3 * 38 + 218 + 4
352 = 3 * 36 + 240 + 4
625 = 3 * 42 + 495 + 4
532 = 3 * 44 + 396 + 4
386 = 3 * 42 + 256 + 4
450 = 3 * 27 + 365 + 4
373 = 3 * 30 + 279 + 4
648 = 3 * 50 + 494 + 4
477 = 3 * 42 + 347 + 4
530 = 3 * 44 + 394 + 4
247 = 3 * 29 + 156 + 4
325 = 3 * 32 + 225 + 4
394 = 3 * 32 + 294 + 4
343 = 3 * 31 + 246 + 4
lines 1-24/148 (more)

Si! Después de este cambio, la cantidad total del encabezado siempre es exactamente cuatro menos que el tamaño de todo el archivo de datos. Y dado que cuatro es también el número de bytes en el encabezado, es obvio que esto no es una coincidencia. El primer número nos da el número de entradas de tres bytes en la tabla, y el segundo número nos da el número de bytes que componen el resto del archivo de datos.

Encontramos una fórmula constante, lo que significa que ahora entendemos completamente lo que significan los números en la primera parte.

(Por cierto, aquí está el patrón muy secreto que los lectores atentos podrían notar. Un estudio cuidadoso de las ecuaciones deja en claro que cuando los archivos tienen el mismo primer número, obtienen la misma diferencia residual. Esto sucede porque la diferencia siempre es dos veces el valor primer número. Este es un patrón no obvio, pero un observador minucioso o exitoso podría notarlo.)

Entonces, podemos decir que el archivo tiene tres partes principales:

encabezado de cuatro bytes;
tabla de registros de tres bytes; y
el resto del archivo, que supuestamente contiene la mayoría de los datos.

(En consecuencia, las otras partes que hemos determinado aproximadamente anteriormente deberían ser subsecciones de la tercera parte).

Interpretar metadatos

Dado este esquema, sería lógico suponer que las entradas en la tabla de la segunda parte son algunos metadatos necesarios para interpretar los datos de la tercera parte.

Pero, ¿qué tipo de metadatos contiene esta tabla?

Notamos anteriormente que hay un par de signos de que el archivo de datos puede estar comprimido. (Ahora, esto parece aún más plausible, porque sabemos que la tercera parte de cada archivo, que supuestamente contiene datos de cada nivel, tiene un tamaño de solo 100-600 bytes). Si es así, es muy posible que la tabla que precede a los datos principales contenga metadatos de compresión. - un diccionario utilizado durante el desempaquetado. Por ejemplo, antes de los datos codificados por el algoritmo Huffman, generalmente hay un diccionario que asigna los valores de bytes originales a secuencias de bits. Aunque no esperamos que estos archivos sean codificados por el algoritmo Huffman (dado que los datos muestran patrones claros en el nivel de bytes, es decir, apenas son un flujo de bits), sería prudente intentar interpretar esta tabla como un diccionario de descompresión.

(Por supuesto, no todos los tipos de compresión usan un diccionario almacenado. Por ejemplo, el algoritmo de desinflado utilizado gzipy le zlibpermite recrear el diccionario directamente desde el flujo de datos. Pero estos casos son la excepción en lugar de la regla).

Por lo general, la entrada del diccionario consta de dos partes: la clave y valores Por supuesto, a veces se implica una clave, por ejemplo, cuando se ordena no en una tabla de búsqueda, sino en una matriz. Sin embargo, ya notamos que los registros de tres bytes parecen constar de dos partes, en particular, el primer byte de cada registro sigue un patrón que es claramente diferente del patrón del segundo y tercer bytes. Con esto en mente, una primera hipótesis razonable sería considerar el primer byte como la clave y los dos bytes restantes como el valor.

Si este es el caso, entonces una de las formas más simples de interpretar la parte de la tira es que el primer byte es el valor del byte que debe reemplazarse en los datos comprimidos, y el segundo y el tercer bytes son el valor que debe reemplazarse. El resultado creado por este esquema definitivamente será mayor, aunque no está claro cuánto. Sea como fuere, esta es una hipótesis lógica, y es bastante fácil de verificar. Podemos escribir un programa corto en Python que implemente este esquema de descompresión:

Archivo decompress.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section. for n in range(0, len(table), 3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Ahora podemos verificar este script usando un archivo de datos de ejemplo:

$ python ./decompress.py <levels/lesson_1.pak | xxd 00000000: 0b0b 0b0b 0404 0000 0a0a 0109 0d05 0502 ................ 00000010: 0200 0100 0000 0101 0100 0009 0702 0209 ................ 00000020: 1100 0125 0100 2309 0700 0009 0d1d 0124 ...%..#........$ 00000030: 011d 0a0a 0105 0500 0100 2000 1b02 0200 .......... ..... 00000040: 1a00 2009 0709 1100 011f 0033 001e 0100 .. ........3.... 00000050: 2309 0709 0d23 0000 0023 0a0a 0105 0509 #....#...#...... 00000060: 1100 011f 0200 1e01 0023 0907 0001 0200 .........#...... 00000070: 1a00 0023 0000 1b00 0009 0709 0d01 1c01 ...#............ 00000080: 1c0a 0a01 0105 0502 0200 0100 0001 0000 ................ 00000090: 0107 0509 1101 2309 0704 0400 0100 0001 ......#......... 000000a0: 2109 0704 0409 0d01 010b 0b0b 0b08 0804 !............... 000000b0: 0402 0200 0608 0807 0707 0502 0202 0078 ...............x 000000c0: 0808 0707 0705 0202 0200 7008 0807 0707 ..........p..... 000000d0: 0502 0202 0064 0017 101e 1e1a 1901 0300 .....d.......... 000000e0: 0e1a 1717 100e 1f01 0e13 141b 1e01 1f1a ................ 000000f0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................ 00000100: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-. .... 00000110: 1024 1e01 1f1a 011a 1b10 1900 0f1a 1a1d .$.............. 00000120: 1e2d 0000

Sin embargo, los resultados no son notables. Por supuesto, el flujo de datos resultante se ha desplegado más que el original, pero no mucho. Definitivamente no es suficiente para contener todos los datos que esperamos encontrar. Obviamente, este esquema de desempaquetado es un poco más simple de lo necesario.

Si examinamos cuidadosamente la salida resultante, pronto veremos que comienza con muchos bytes repetidos. 0b, 04, 00, 0a- todos ellos se presentan en pares. Mirando el original comprimido, veremos que todos estos pares han surgido debido a un reemplazo del diccionario. Pero en el proceso, notamos de inmediato que todos estos significados duplicados también corresponden a entradas en el diccionario. Es decir, si volvemos a aplicar el diccionario, los datos se expandirán nuevamente. ¿Quizás no estamos desempacando lo suficiente?

Nuestra primera suposición puede ser realizar una segunda pasada, aplicando cada entrada del diccionario por segunda vez para expandir los datos aún más. La segunda suposición puede ser realizar múltiples pases con el diccionario, repitiendo el proceso hasta que se reemplacen todos los bytes similares a las claves del diccionario. Sin embargo, si observamos más de cerca la estructura del diccionario, nos damos cuenta de que simplemente aplicamos las entradas del diccionario de derecha a izquierda , y no de izquierda a derecha, cuando todos nuestros valores se expanden en una sola pasada.

Tomando esta hipótesis, podemos ver la estructura de un algoritmo de compresión más plausible. El programa toma los datos de origen y los escanea, buscando las secuencias de doble byte más comunes. Luego reemplaza la secuencia de dos bytes con un valor de un byte que no se encuentra en los datos. Luego, repite el proceso y continúa hasta que los datos contengan más de dos repeticiones de secuencias de doble byte. De hecho, dicho algoritmo de compresión tiene un nombre: se conoce como compresión "volver a emparejar", que es la abreviatura de "pares recursivos".

(Y esto puede explicar algunos patrones que vemos en el diccionario. Durante la compresión, el diccionario se construye de izquierda a derecha, por lo que al desempacarlo se debe aplicar de derecha a izquierda. Dado que las entradas del diccionario a menudo se refieren a entradas anteriores, es lógico que el segundo y el tercer bytes a menudo sean más pequeño que el primero.)

Aunque la compresión de emparejamiento no produce resultados muy impresionantes, tiene una ventaja: el descompresor se puede implementar con un mínimo de código. Yo mismo usé volver a emparejar en algunas situaciones en las que necesitaba minimizar el tamaño total de los datos comprimidos y el código de descompresión.

Entonces, podemos hacer un cambio en una línea del programa Python para aplicar el diccionario de derecha a izquierda:

Archivo decompress2.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section in reverse order. for n in range(len(table) - 3, -3, -3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Si probamos esta versión, la salida será mucho mayor:

 $ python ./decompress2.py <levels/lesson_1.pak | xxd | less
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 ................
00000110: 0101 0101 0100 0000 0000 0000 0000 0000 ................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 ................
00000130: 0100 0000 0100 0000 0000 0000 0000 0000 ................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 ............#..%
00000150: 0100 2300 0100 0000 0000 0000 0000 0000 ..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 ...............$
00000170: 011d 0101 0101 0100 0000 0000 0000 0000 ................
líneas 1-24 / 93 (más)

Vemos muchos bytes nulos en esta salida, pero esto puede corresponder a una tarjeta casi vacía. Los bytes distintos de cero parecen estar agrupados uno al lado del otro. Como esperamos encontrar una tarjeta de 32 × 32, reformateemos la salida a 32 bytes por línea:

$ python ./decompress2.py <niveles / lección_1.pak | xxd -c32 | menos
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 0101 0101 0100 0000 0000 0000 0000 0000 ................................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 0100 0000 0100 0000 0000 0000 0000 0000 ................................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 0100 2300 0100 0000 0000 0000 0000 0000 ............#..%..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 011d 0101 0101 0100 0000 0000 0000 0000 ...............$................
00000180: 0000 0000 0000 0000 0100 2000 1b00 0000 0000 1a00 2000 0100 0000 0000 0000 0000 .......... ......... ...........
000001a0: 0000 0000 0000 0000 0100 2300 011f 0033 001e 0100 2300 0100 0000 0000 0000 0000 ..........#....3....#...........
000001c0: 0000 0000 0000 0000 0101 0101 0123 0000 0023 0101 0101 0100 0000 0000 0000 0000 .............#...#..............
000001e0: 0000 0000 0000 0000 0100 2300 011f 0000 001e 0100 2300 0100 0000 0000 0000 0000 ..........#.........#...........
00000200: 0000 0000 0000 0000 0100 0000 1a00 0023 0000 1b00 0000 0100 0000 0000 0000 0000 ...............#................
00000220: 0000 0000 0000 0000 0101 0101 0101 1c01 1c01 0101 0101 0100 0000 0000 0000 0000 ................................
00000240: 0000 0000 0000 0000 0000 0000 0100 0001 0000 0100 0000 0000 0000 0000 0000 0000 ................................
00000260: 0000 0000 0000 0000 0000 0000 0100 2301 2300 0100 0000 0000 0000 0000 0000 0000 ..............#.#...............
00000280: 0000 0000 0000 0000 0000 0000 0100 0001 2100 0100 0000 0000 0000 0000 0000 0000 ................!...............
000002a0: 0000 0000 0000 0000 0000 0000 0101 0101 0101 0100 0000 0000 0000 0000 0000 0000 ................................
000002c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000002e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
lines 1-24/47 (more)

Después de observar cuidadosamente los patrones de valores distintos de cero, veremos que el mapa es claramente visible en la salida. De hecho, podemos hacer que este patrón sea más visible utilizando la herramienta de volcado "coloreada", que asigna un color a cada valor de byte, simplificando la búsqueda de patrones de valores repetidos:

xcdes una herramienta no estándar, pero puede descargarla desde aquí . Tenga en cuenta la opción de -rutilidad less, que le indica que borre las secuencias de control.

Compare esto con un mapa de primer nivel dibujado por un fan:

Sin duda, vemos los datos del mapa de nivel. Puede estar bastante seguro de que hemos determinado correctamente el algoritmo de desempaquetado.

Interpretación de datos

Al comparar los valores de bytes con la imagen del mapa, podemos determinar qué 00codifica un mosaico vacío, 01codifica un muro y 23denota un chip. 1Adenota una puerta roja, 1Buna puerta azul, y así sucesivamente. Podemos asignar valores exactos a las fichas, llaves, puertas y todas las demás fichas que componen el mapa de nivel completo.

Ahora podemos pasar al siguiente nivel y encontrar los valores de byte para los objetos que aparecen allí. Y continúe con los siguientes niveles hasta que obtengamos una lista completa de los valores de bytes y los objetos del juego que codifican.

Como sugerimos inicialmente, la tarjeta termina exactamente después de 1024 bytes (en el desplazamiento 000003FF).

Esta vez, para eliminar las primeras 32 líneas del volcado, usamossed. Como tenemos 32 bytes por línea, omitiremos los primeros 1024 bytes.

Inmediatamente después de los datos del mapa hay una secuencia de 384 bytes (cuyos valores están en el intervalo 00000400- 0000057F), casi todos iguales a cero, pero los valores distintos de cero también se encuentran entre ellos. Después de esto viene un patrón de bytes completamente diferente, por lo que sería lógico suponer que esta secuencia de 384 bytes es una parte separada.

Si observamos algunos niveles más, notamos rápidamente el patrón. La parte de 384 bytes en realidad consta de tres subsecciones, cada una de 128 bytes de longitud. Cada subsección comienza con unos pocos bytes distintos de cero seguidos de ceros que llenan el resto de la subsección.

Algunos niveles contienen muchos datos; para otros (por ejemplo, para el primer nivel) solo el mínimo. Al comparar los niveles con sus tarjetas, pronto notaremos que la cantidad de datos en esta parte del archivo está directamente relacionada con el número de "mobs" por nivel. En este caso, el número de "mobs" incluye todas las criaturas en el nivel, bloques de tierra (que no se mueven independientemente, pero pueden ser empujados) y el personaje principal Chip (jugador). Es decir, los mobs no están indicados en el mapa en sí, sino que están codificados en estos tres buffers.

Después de que supimos que estas tres subsecciones contienen datos sobre las turbas en el nivel, no será muy difícil averiguar qué contiene cada una de las subsecciones.

La primera subsección de 128 bytes es una lista de valores de bytes que determinan el tipo de mafia. Por ejemplo, los búferes de segundo nivel se ven así:

 $ python ./decompress2.py <levels/lesson_2.pak | xxd | less
00000400: 0608 1c1c 0808 0000 0000 0000 0000 0000 ................
00000410: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000420: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000470: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000480: a870 98a0 6868 0000 0000 0000 0000 0000 .p..hh..........
00000490: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000500: 6060 6060 5868 0000 0000 0000 0000 0000 ````Xh..........
00000510: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000520: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000570: 0000 0000 0000 0000 0000 0000 0000 0000 ................
líneas 64-87 / 93 (más)

Compare esto con un mapa de nivel:

En este nivel, hay seis mobs: tres errores, dos bloques y un Chip. La primera subclave de 128 bytes contiene un byte 06, tres bytes 08y dos bytes 1C. Sería razonable concluir qué 06significa Chip 08: un error y 1Cun bloque.

(Continuando con la comparación de archivos de datos a partir de los niveles de las tarjetas y de relleno en el diccionario turbas, rápidamente encontró una falla en esta teoría: El chip puede ser referido a cuatro valores diferentes, a saber 04, 05, 06o07. Este conjunto de anotaciones en realidad contiene todas las turbas. Cuando estudiemos cuidadosamente los diferentes valores, eventualmente entenderemos que el valor 0, 1, 2 o 3 se agrega al valor de byte que indica el tipo, que indica la dirección inicial de la mafia: norte, este, sur u oeste. Es decir, por ejemplo, un valor de byte 06denota un Chip mirando hacia el sur).

La importancia de las otras dos subsecciones es menos obvia. Pero habiendo estudiado los valores repetidos en estas subsecciones y comparando las tarjetas para estos mobs, entenderemos que los bytes en la segunda subsección almacenan la coordenada X de cada mafia, y los bytes en la tercera subsección almacenan la coordenada Y de cada mafia. La comprensión de esta decisión se ve obstaculizada por el hecho de que las coordenadas almacenadas en estas subsecciones en realidad se desplazan 3 bits hacia la izquierda, es decir. multiplicado por 8. Este pequeño hecho explica el grupo "azul", que encontramos en el censo de valores. (Las razones por las que se realizó este cambio no están claras, pero lo más probable es que los tres bits inferiores se usen para representar la animación cuando se mueven los mobs.)

Habiendo tratado esta parte, ahora podemos ver cuántos archivos de datos solo quedan unos pocos bytes después:

Nota quexxdacepta un -svalor hexadecimal para la opción .

$ para f en niveles / *; do python ./decompress2.py <$ f | xxd -s 0x580 | sed -n 1p; hecho | menos
00000580: 9001 0c17 1701 1120 1717 00 ....... ...
00000580: 0000 0c17 1b13 0c0d 101f 011e 1a20 1b00 ............. ..
00000580: f401 0c18 1e1f 101d 0f0c 1800 ............
00000580: 2c01 0c1b 0c1d 1f18 1019 1f00, ...........
00000580: 9001 0c1d 0e1f 140e 1117 1a22 00 ............ "
00000580: 2c01 0d0c 1717 1e01 1a01 1114 1d10 00, ..............
00000580: 2c01 0d10 220c 1d10 011a 1101 0d20 1200, ... "........ ..
00000580: 5802 0d17 1419 1600 X .......
00000580: 0000 0d17 1a0d 0f0c 190e 1000 ............
00000580: f401 0d17 1a0d 1910 1f00 ..........
00000580: f401 0d17 1a0e 1601 110c 0e1f 1a1d 2400 .............. $.
00000580: ee02 0d17 1a0e 1601 0d20 1e1f 101d 0114 ......... ......
00000580: 5802 0d17 1a0e 1601 1901 1d1a 1717 00 X..............
00000580: 5e01 0d17 1a0e 1601 1a20 1f00 ^........ ..
00000580: c201 0d17 1a0e 1601 0d20 1e1f 101d 00 ......... .....
00000580: 2c01 0d1a 2019 0e10 010e 141f 2400 ,... .......$.
00000580: 5000 0d1d 201e 1311 141d 1000 P... .......
00000580: e703 0e0c 1610 0122 0c17 1600 ......."....
00000580: 5802 0e0c 1e1f 1710 0118 1a0c 1f00 X.............
00000580: 8f01 0e0c 1f0c 0e1a 180d 1e00 ............
00000580: 0000 0e10 1717 0d17 1a0e 1610 0f00 1b1d ................
00000580: 2c01 0e13 0e13 0e13 141b 1e00 ,...........
00000580: 8f01 0e13 1417 1710 1d00 ..........
00000580: bc02 0e13 141b 1814 1910 00 ...........
lines 1-24/148 (more)

Examinar el primer par de bytes en el resto rápidamente nos sugiere que contienen otro valor entero de 16 bits. Si los tomamos así, la mayoría de los valores aparecen en notación decimal como números redondos:

el comando odusa en su -jlugar para moverse al desplazamiento original -s. También vale la pena señalar el comando printf: además de proporcionar formato, es una forma conveniente de mostrar texto sin una nueva línea colgando al final.

$ para f en niveles / *; hacer printf "% -20s" $ f; python ./decompress2.py <$ f | od -An -j 0x580 -tuS -N2; hecho | menos
niveles / all_full.pak 400
niveles / alfabeto.pak 0
niveles / amsterda.pak 500
niveles / apartmen.pak 300
niveles / arcticfl.pak 400
niveles / bolas_o_.pak 300
niveles / beware_o.pak 300
niveles / blink.pak 600
niveles / blobdanc.pak 0
niveles / blobnet.pak 500
niveles / block_fa.pak 500
niveles / block_ii.pak 750
niveles / block_n_.pak 600
niveles / block_ou.pak 350
niveles / block.pak 450
niveles / bounce_c.pak 300
niveles / brushfir.pak 80
niveles / cake_wal.pak 999
niveles / castle_m.pak 600
niveles / catacomb.pak 399
niveles / cellbloc.pak 0
niveles / chchchip.pak 300
niveles / chiller.pak 399
niveles / chipmine.pak 700
líneas 1-24 / 148 (más)

Si volvemos a la lista, creada originalmente a partir de los datos que esperábamos encontrar en los archivos, nos damos cuenta de que este número es el momento de pasar el nivel (si el valor es cero, entonces no hay límite de tiempo en el nivel).

Después de estos dos bytes, los datos se vuelven más volátiles. El hecho de que para la mayoría de los niveles quedan aproximadamente diez bytes en el archivo limita seriamente su contenido:

$ python ./decompress2.py <niveles / all_full.pak | xxd -s 0x0582
00000582: 0c17 1701 1120 1717 00 ..... ...

Por ejemplo, solo quedan nueve bytes en este nivel. Tomamos en cuenta este tamaño limitado, así como el hecho de que estos nueve bytes contienen cuatro ocurrencias del valor 17, recopilados en dos pares. Notaremos de inmediato que el patrón de números 17corresponde al patrón de letras Len el nombre del nivel "TODO COMPLETO". El nombre tiene ocho caracteres de longitud, por lo que el byte nulo al final es probablemente el carácter de final de línea. Después de descubrir esto, puedes mirar trivialmente todos los demás niveles y usar sus nombres para crear una lista completa de personajes:

`00`	fin de línea
`01`	barra espaciadora
`02` - `0B`	dígitos 0-9
`0C` - `25`	letras AZ
`26` - `30`	signos de puntuación

Para la mayoría de los niveles, el archivo de datos termina aquí. Sin embargo, un par de docenas del nombre todavía tiene datos. Si echamos un vistazo a la lista, veremos que hay niveles con botones de sugerencia, y estos datos restantes contienen el texto de la línea de sugerencia de nivel codificada con el mismo conjunto de caracteres que los nombres de nivel.

Después de eso, llegamos al final de todos los archivos. Ahora tenemos una descripción completa del esquema de estos niveles. Nuestra tarea está completa.

Asuntos pendientes

Un lector atento puede notar que inicialmente esperábamos encontrar dos elementos más en estos archivos que nunca conocimos. Explicaremos la ausencia de ambos:

el primer elemento es el número de chips, es decir El número total de fichas que un jugador debe recolectar para pasar a través del conector de fichas. Como dijimos inicialmente, a menudo es igual al número total de fichas en un nivel, pero esto no siempre sucede. Por lo tanto, estos datos deben obtenerse de alguna manera. La respuesta se puede encontrar estudiando tarjetas de aquellos niveles en los que hay fichas adicionales. Resulta que dos valores diferentes se utilizan para indicar chips. El valor 23que encontramos inicialmente, pero el valor también se usa.31denota un chip que no afecta la cantidad total requerida para abrir el conector del chip. (Sin embargo, desde el punto de vista del juego, ambos tipos de fichas son iguales. Si hay un tipo de ficha 31en el nivel, entonces en el nivel no puedes recoger ninguna cantidad de fichas).

El segundo elemento es la contraseña de nivel de cuatro letras. No está oculto en ningún lugar de los datos de nivel. Desafortunadamente, este problema no puede resolverse mediante una investigación adicional del archivo de datos. Nos vemos obligados a concluir que las contraseñas simplemente se almacenan en otro lugar. La explicación más probable: están codificadas en algún lugar del programa. Sin embargo, más tarde quedó claro que las contraseñas no se almacenan directamente. De personas familiarizadas con el código en sí, aprendí que las contraseñas se generan dinámicamente usando un generador de números pseudoaleatorios inicializado con una secuencia específica. Por lo tanto, las contraseñas a niveles no se pueden cambiar directamente, esto solo se puede hacer cambiando el código del ensamblador.

Epílogo

Una vez completada la ingeniería inversa completa de los datos en los archivos de nivel, podría comenzar a escribir un programa capaz de codificar y decodificar los datos de nivel. Gracias a ella, pude crear el tan esperado editor de niveles para la versión de Chip's Challenge para Lynx, y la presencia de esta herramienta aumentó enormemente mi capacidad de estudiar la lógica del juego, y también mejoró la calidad de su emulación.

Pero ... debo admitir que personalmente hice el desarrollo inverso de los archivos de datos de una manera no descrita anteriormente. Comencé desde el otro extremo, con la definición de datos de cadena. Comencé a estudiar los archivos de los primeros ocho niveles. Como se llaman de "LECCIÓN 1" a "LECCIÓN 8", busqué los datos de las subcadenas idénticas en ellos. Y tuve suerte: ninguno de los nombres de estos niveles estaba comprimido, por lo que los ocho nombres se almacenan en los archivos de datos en su forma original. Por supuesto, me daba vergüenza que estas líneas no estuvieran almacenadas en caracteres ASCII, pero la doble S en el nombre me ayudó a detectar un patrón que se repitió en los ocho archivos de datos. Y al encontrar el nombre, reconocí la codificación de caracteres de letras, números y el espacio. Luego apliqué esta codificación al resto del archivo, y justo después del nombre vi líneas de aviso, y comencé a observar las anomalías:

Una gran utilidad trfacilita la conversión de su propio conjunto de caracteres de archivos de datos a ASCII.

$ tr '\ 001- \ 045' '0-9A-Z' <niveles / lección_1.pak | xxd
00000000: 4600 cb00 3000 0032 3030 3332 3235 3333 F ... 0..200322533
00000010: 3635 3537 0020 3820 2039 3636 4238 3846 6557. 8 966B88F
00000020: 0058 4a37 354d 3000 5737 4226 3746 2739 .XJ75M0.W7B y 7F'9
00000030: 3928 3533 2953 2027 2733 3042 2057 3532 9 (53) S '' 30B W52
00000040: 3730 3738 304a 3226 375a 2046 4a30 5752 70780J2 y 7Z FJ0WR
00000050: 2059 2052 4220 3537 0055 0050 3200 4f00 Y RB 57.U.P2.O.
00000060: 554a 2637 5400 3300 2946 4a57 5830 4642 UJ y 7T.3.) FJWX0FB
00000070: 2035 2637 544d 2946 4a37 4d4f 3058 3050 5 & 7TM) FJ7MO0X0P
00000080: 304a 5720 5120 5142 3835 3237 3020 3020 0JW Q QB85270 0
00000090: 2826 2058 4a33 3730 2056 4a33 5738 2727 (& XJ370 VJ3W8''
000000a0: 3933 3200 3439 3628 324d 7839 3628 324d 932.496(2Mx96(2M
000000b0: 7039 3628 324d 6400 4c45 5353 4f4e 2031 p96(2Md.LESSON 1
000000c0: 0043 4f4c 4c45 4354 2043 4849 5029 544f .COLLECT CHIP)TO
000000d0: 0047 4554 2050 4153 5420 5448 4520 4348 .GET PAST THE CH
000000e0: 4950 0053 4f43 4b45 542d 0055 5345 204b IP.SOCKET-.USE K
000000f0: 4559 2954 4f20 4f50 454e 0044 4f4f 5253 EY)TO OPEN.DOORS
00000100: 2d30 -0

Por ejemplo, en el texto de ayuda hay dos lugares donde la secuencia de S y el espacio se reemplazan por el corchete derecho. Estas anomalías me dieron suficiente evidencia para calcular deductivamente la presencia de compresión y obtener información sobre su naturaleza. Más tarde, asocié valores de bytes anormales con sus ocurrencias más cerca del comienzo del archivo de datos. (Por ejemplo, en el volcado de desplazamiento hexadecimal que se muestra arriba 00000035hay un corchete derecho, seguido de una S mayúscula y un espacio). A partir de esto, calculé el esquema de compresión de manera similar al proceso descrito en el artículo. Todo lo demás era bastante simple.

Me parece que se puede extraer una lección de esto: no hay una forma única de examinar un archivo de datos desconocido. Cualquier herramienta que le convenga son las herramientas adecuadas para la ingeniería inversa.

Introducción a la ingeniería inversa: formato de datos de juegos de piratería