🤲🏽 💇🏾 ▪️ Introdução à engenharia reversa: pirataria no formato de dados do jogo 👩🏿‍💼 🎩 🤾🏾

1. Introdução

A engenharia reversa de um arquivo de dados desconhecido pode ser descrita como um processo de entendimento gradual. De muitas maneiras, assemelha-se a um método científico, aplicado apenas a objetos abstratos criados pelo homem, e não ao mundo natural. Começamos coletando dados e depois usamos essas informações para apresentar uma ou mais hipóteses. Testamos as hipóteses e aplicamos os resultados desses testes para esclarecê-las. Se necessário, repita o processo.

Desenvolver habilidades de engenharia reversa é basicamente uma questão de prática. Ao adquirir experiência, você constrói um entendimento intuitivo do que precisa explorar antes de tudo, quais padrões precisa procurar e quais ferramentas são mais convenientes para usar.

Neste artigo, falarei em detalhes sobre o processo de arquivos de dados de engenharia reversa de um jogo de computador antigo para demonstrar como isso é feito.

Um pouco de fundo

Tudo começou quando tentei recriar o Desafio do Chip no Linux.

O Desafio do Chip foi lançado originalmente em 1989 para o agora esquecido console portátil Atari Lynx. Naquela época, o Atari Lynx era um carro impressionante, mas saiu ao mesmo tempo que o Nintendo Game Boy, que acabou conquistando o mercado.

Chip's Challenge é um jogo de quebra-cabeça com uma vista superior e um mapa de peças. Como na maioria dos jogos, o objetivo de cada nível é chegar à saída. Na maioria dos níveis, a saída é protegida por um conector para o chip, que pode ser ignorado apenas pela coleta de um determinado número de chips de computador.

Vídeo: Atari Lynx em ação , passo a passo de nível um .

Um novo jogo começa no primeiro nível, com o nome "LIÇÃO 1". Além de chips e um slot para um chip, chaves e portas aparecem nele. Em outros níveis, surgem obstáculos como armadilhas, bombas, água e criaturas que (na maioria das vezes) se movem ao longo de rotas previsíveis. Uma ampla variedade de objetos e dispositivos permite criar muitos quebra-cabeças e prazos. Para completar o jogo, você precisa passar por mais de 140 níveis.

Embora o Lynx eventualmente tenha falhado, o Chip's Challenge provou ser bastante popular e foi portado para muitas outras plataformas, aparecendo no Microsoft Windows, onde se espalhou. Ao redor do jogo, uma pequena mas dedicada base de fãs se formou e, com o tempo, foi escrito um editor de níveis que permitia aos jogadores criar inúmeros níveis.

E é aí que a minha história começa. Decidi que queria criar uma versão do mecanismo básico de jogos de código aberto para poder jogar o Desafio do Chip no Linux e Windows e facilitar a execução de todos os níveis criados pelos fãs.

A existência do editor de níveis acabou sendo um milagre para mim, porque eu pude explorar os recursos ocultos da lógica do jogo, criando meus próprios níveis e realizando testes. Infelizmente, não havia um editor de níveis para o jogo original do Lynx; ele apareceu apenas na porta mais conhecida do Windows.

A porta do Windows não foi criada pelos desenvolvedores originais, surgiram muitas alterações na lógica do jogo (e nem todas foram intencionais). Quando comecei a escrever meu mecanismo, queria recriar nele a lógica do jogo original no Lynx e a versão mais conhecida do Windows. Mas a falta de um editor de níveis no Lynx limitou seriamente minha capacidade de estudar o jogo original em detalhes. A porta do Windows tinha uma vantagem: os níveis foram armazenados em um arquivo de dados separado, o que simplificou sua detecção e engenharia reversa. O jogo para Lynx foi distribuído em cartuchos de ROM contendo imagens de sprites, efeitos sonoros e código de máquina, além de dados de nível que foram executados todos juntos. Não há dicas sobre onde os dados estão localizados neste despejo de 128 kilobytes da ROM, ou como eles se parecem, e sem esse conhecimento, não pude criar um editor de níveis para a versão do Lynx.

Certa vez, em um processo de pesquisa, me deparei com uma cópia da porta do Chip's Challenge no MS-DOS. Como na maioria das portas iniciais do jogo, sua lógica estava mais próxima do original do que na versão para Windows. Quando examinei os dados do programa para descobrir como eles são armazenados, fiquei surpreso ao descobrir que os dados do nível estavam alocados em um diretório separado e cada nível foi armazenado em seu próprio arquivo. Tendo dados de nível tão convenientemente separados, sugeri que não seria muito difícil fazer a engenharia reversa dos arquivos de dados de nível. E isso permitirá que você escreva um editor de níveis para a versão do jogo no MS-DOS. Decidi que essa era uma oportunidade interessante.

Mas outro membro da comunidade do Chip's Challenge me alertou sobre um fato interessante. O conteúdo dos arquivos de nível do MS-DOS acabou sendo um despejo de bytes do ROM Lynx. Isso significava que, se eu pudesse decodificar os arquivos do MS-DOS, poderia usar esse conhecimento para ler e alterar os níveis dentro do despejo de ROM do Lynx. Em seguida, você pode criar um editor de níveis diretamente para o jogo original no Lynx.

De repente, minha principal prioridade era arquivos de nível de engenharia reversa para o MS-DOS.

Arquivos de dados

Aqui está um link para o diretório tarball que contém todos os arquivos de dados. Dou-o no caso de você querer repetir depois de mim todas as etapas descritas neste artigo ou tentar decodificar os arquivos de dados você mesmo.

Isso é legal? Boa pergunta Como esses arquivos são apenas uma pequena parte do programa para MS-DOS e, por si só, são inúteis, e como eu os publico apenas para fins educacionais, acredito que isso se enquadre nos requisitos de uso justo. Espero que todas as partes interessadas concordem comigo. (Se, no entanto, receber uma carta ameaçadora de advogados, posso alterar o artigo para apresentar os arquivos de dados de uma maneira engraçada e depois declarar que é uma paródia.)

Pré-requisitos

Assumirei que você conhece o cálculo hexadecimal, mesmo que não saiba a decodificação de valores hexadecimais, e também que você está um pouco familiarizado com o shell Unix. A sessão do shell mostrada neste artigo é executada em um sistema Linux padrão, mas os comandos quase usados são utilitários comuns do Unix e são amplamente distribuídos em outros sistemas semelhantes ao Unix.

Primeiro olhar

Aqui está uma lista do diretório que contém os arquivos de dados da porta no MS-DOS:

  Níveis de $ ls
 all_full.pak cake_wal.pak eeny_min.pak iceberg.pak lição_5.pak mulligan.pak playtime.pak southpol.pak totally_.pak
 alphabet.pak castle_m.pak elementa.pak ice_cube.pak lição_6.pak nice_day.pak potpourr.pak special.pak traffic_.pak
 amsterda.pak catacomb.pak fireflie.pak icedeath.pak lição_7.pak pesadelo.pak problemas.pak spirals.pak trinity.pak
 apartmen.pak cellbloc.pak firetrap.pak icehouse.pak lição_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak
 arcticfl.pak chchchip.pak floorgas.pak invincib.pak lagosta_.pak nozes_e.pak reverse_.pak steam.pak unders.pak
 Bolas_o_.pak chiller.pak forçado_e.pak i.pak lock_blo.pak em_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 vítima.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 vendo_s.pak the_last.pak writers_.pak
 block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak parcial_.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 lição_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak
 block.pak digger.pak grail.pak lição_2.pak monstro_.pak pier_sev.pak slide_st.pak time_lap.pak
 bounce_c.pak doublema.pak hidden_d.pak lição_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak
 brushfir.pak drawn_an.pak hunt.pak lição_4.pak mugger_s.pak playhous.pak socialis.pak tossed_s.pak

Como você pode ver, todos os arquivos terminam em .pak . .pak é a permissão padrão para o arquivo de dados do aplicativo e, infelizmente, não nos fornece nenhuma informação sobre sua estrutura interna. Os nomes dos arquivos são os oito primeiros caracteres do nome do nível, com algumas exceções. (Por exemplo, nos nomes dos arquivos de nível “BLOCK BUSTER” e “BLOCK BUSTER II”, a palavra “buster” é omitida para que não correspondam.)

  níveis de $ ls |  wc
      17 148 1974

Existem 148 arquivos de dados no diretório, e o jogo tem exatamente 148 níveis, então tudo é o mesmo aqui.

Agora vamos examinar o que esses arquivos são. xxd é um utilitário padrão para descarregar dados hexadecimais (hexdump). Vamos ver como é a lição 1.

  Níveis de $ xxd / lição_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

O que é um utilitário hexdump? Um despejo hexadecimal é uma maneira padrão de exibir os bytes exatos de um arquivo binário. A maioria dos valores de bytes não pode ser associada a caracteres ASCII imprimíveis ou eles têm uma aparência incompreensível (como um caractere de tabulação). Em um dump hexadecimal, bytes individuais são emitidos como valores numéricos. Os valores são exibidos em hexadecimal, daí o nome. No exemplo acima, 16 bytes são exibidos em uma linha de saída. A coluna mais à esquerda mostra a posição da linha no arquivo, também em hexadecimal, para que o número em cada linha seja aumentado em 16. Os bytes são exibidos em oito colunas e dois bytes em cada coluna. O hexdump à direita mostra a aparência dos bytes quando exibidos por caracteres, apenas todos os valores ASCII não imprimíveis são substituídos por pontos. Isso facilita a localização de strings que podem ser incorporadas em um arquivo binário.

Obviamente, a engenharia reversa desses arquivos não se resume apenas a navegar pelo conteúdo e explorar o que é visível lá. Até o momento, nada nos diz que funções os dados executam.

O que esperamos ver?

Vamos dar um passo atrás e esclarecer a situação: que dados específicos esperamos encontrar nesses arquivos de dados?

O mais óbvio é um certo "mapa" do nível: dados indicando as posições de paredes e portas, bem como tudo o mais, o que torna o nível único.

(Felizmente para nós, os fãs do jogo fizeram um trabalho minucioso e coletaram mapas completos para todos os 148 níveis, para que possamos usá-los para saber o que deve estar em cada mapa.)

Além do mapa, cada nível deve ter vários outros atributos. Por exemplo, você pode perceber que cada nível tem um nome, por exemplo, "LIÇÃO 1", "JOGO PERFEITO", "DRAWN AND QUARTERED" e assim por diante. Níveis diferentes também têm limites de tempo diferentes, portanto, podemos assumir que essas informações também estão contidas nos dados. Além disso, cada nível tem seu próprio número de chips montados. (Podemos supor que esse número simplesmente corresponda ao número de chips no nível, mas acontece que em alguns níveis há mais chips do que o necessário para abrir o conector do chip. Pelo menos para esses níveis, o número mínimo deve ser indicado de forma explícita.)

Outro dado que esperamos encontrar nos dados de nível é o texto da dica. Em alguns níveis, há um "botão de dica" - um grande ponto de interrogação no chão. Quando o Chip aparece nele, um texto de dica de ferramenta é exibido. O botão de dica está em cerca de 20 níveis.

Finalmente, cada nível tem uma senha - uma sequência de quatro letras que permite ao jogador continuar o jogo a partir deste nível. (Essa senha é necessária porque o Lynx não possui um armazenamento de dados. Era impossível salvar jogos no console, para que você pudesse continuar o jogo depois de ligá-lo usando senhas.)

Então, aqui está a nossa lista de dados relevantes:

Mapa de nível
Nome do nível
Nível de senha
Prazo
Número de fichas
Texto da dica de ferramenta

Vamos estimar aproximadamente o tamanho total dos dados. A maneira mais fácil de determinar o limite de tempo e o número de fichas. Esses dois parâmetros podem ter valores no intervalo de 0 a 999; portanto, eles provavelmente são armazenados como valores inteiros com um tamanho total de 4 bytes. A senha sempre consiste em quatro letras, portanto é mais provável que seja armazenada como mais quatro bytes, ou seja, apenas 8 bytes. A duração dos nomes dos níveis varia de quatro a dezenove caracteres. Se supusermos que precisamos de outro byte para completar a linha, isso significa vinte bytes, ou seja, o subtotal é 28 bytes. O texto mais longo da dica de ferramenta tem mais de 80 bytes de tamanho; se arredondar esse valor para 90, obteremos 118 bytes no total.

E o esquema de níveis? A maioria dos níveis tem um tamanho de 32 × 32 peças. Níveis maiores não existem. Alguns níveis são mais baixos, mas seria lógico supor que eles são simplesmente incorporados a uma placa 32 × 32. Se assumirmos que um byte é necessário para um bloco, 1024 bytes são necessários para o circuito completo. Ou seja, em geral, obtemos uma estimativa aproximada de 1142 bytes por nível. Obviamente, essa é apenas uma estimativa inicial aproximada. É possível que alguns desses elementos sejam armazenados de maneira diferente ou não sejam armazenados em arquivos de nível. Ou eles podem conter outros dados que não notamos ou que não conhecemos. Mas até agora estabelecemos uma boa base.

Tendo decidido o que esperamos ver nos arquivos de dados, voltemos ao estudo do que eles realmente contêm.

O que existe e o que não é

Embora à primeira vista o arquivo de dados pareça completamente incompreensível, você ainda pode notar alguns pontos nele. Em primeiro lugar, é isso que não vemos. Por exemplo, não vemos o nome do nível ou o texto das dicas. Você pode entender que isso não é uma coincidência, tendo estudado outros arquivos:

  Níveis de strings $ / * |  menos
 : !!; #
 &> '' :: 4 #
 . ,,!
 -54 ";
 / & 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
 linhas 1-24 / 1544 (mais)

Nada é visível aqui, exceto fragmentos arbitrários de lixo ASCII.

Presumivelmente, em algum lugar nesses arquivos há nomes e dicas de nível, mas eles não são armazenados em ASCII ou passaram por alguma transformação (por exemplo, devido à compactação).

Também é importante notar o seguinte: o arquivo mal atinge 256 bytes de tamanho. Isso é muito pequeno, considerando que inicialmente estimamos seu tamanho em mais de 1140 bytes.

A opção -S classifica os arquivos em ordem decrescente de tamanho.

  Níveis $ ls -lS |  cabeça
 592 total
 -rw-r - r-- 1 breadbox breadbox 680 jun 23 2015 mulligan.pak
 -rw-r - r-- 1 breadbox breadbox 675 jun 23 2015 shrinkin.pak
 -rw-r - r-- 1 breadbox breadbox 671 23 de junho de 2015 balls_o_.pak
 -rw-r - r-- 1 breadbox breadbox 648 jun 23 2015 cake_wal.pak
 -rw-r - r-- 1 breadbox breadbox 647 jun 23 2015 citybloc.pak
 -rw-r - r-- 1 breadbox breadbox 639 jun 23 2015 four_ple.pak
 -rw-r - r-- 1 breadbox breadbox 636 jun 23 2015 trust_me.pak
 -rw-r - r-- 1 breadbox breadbox 625 jun 23 2015 block_n_.pak
 -rw-r - r-- 1 breadbox breadbox 622 jun 23 2015 mix_up.pak

O arquivo maior ocupa apenas 680 bytes, e isso não é muito. E qual será o menor?

A opção -r diz ao ls para reverter a ordem.

  Níveis $ ls -lSr |  cabeça
 592 total
 -rw-r - r-- 1 breadbox breadbox 206 jun 23 2015 kablam.pak
 -rw-r - r-- 1 breadbox breadbox 214 jun 23 2015 fortune_.pak
 -rw-r - r-- 1 breadbox breadbox 219 jun 23 2015 digdirt.pak
 -rw-r - r-- 1 breadbox breadbox 226 jun 23 2015 lesson_2.pak
 -rw-r - r-- 1 breadbox breadbox 229 jun 23 2015 lesson_8.pak
 -rw-r - r-- 1 breadbox breadbox 237 jun 23 2015 parcial_.pak
 -rw-r - r-- 1 breadbox breadbox 239 jun 23 2015 knot.pak
 -rw-r - r-- 1 breadbox breadbox 247 jun 23 2015 cellbloc.pak
 -rw-r - r-- 1 breadbox breadbox 248 jun 23 2015 torturec.pak

O arquivo menor ocupa apenas 206 bytes, que é três vezes menor que o maior. Essa é uma faixa bastante ampla, levando em consideração o fato de que esperávamos aproximadamente os mesmos tamanhos de nível.

Em nossa avaliação inicial, assumimos que o cartão precisaria de um byte por bloco e apenas 1024 bytes. Se cortarmos essa estimativa pela metade, ou seja, cada bloco exigirá apenas 4 bits (ou dois blocos por byte), o cartão ainda ocupará 512 bytes. 512 é menor que 680, mas ainda maior que a maioria dos níveis. E de qualquer forma - 4 bits fornecerão apenas 16 valores diferentes e, no jogo, há muito mais objetos diferentes.

Ou seja, é óbvio que os cartões não são armazenados nesses arquivos em formato aberto. Eles usam codificação mais complexa, fornecendo uma descrição mais eficiente e / ou são de alguma forma compactados. Por exemplo, no nível "LIÇÃO 1", podemos ver como as entradas ausentes para blocos "vazios" reduzirão significativamente o tamanho geral dos dados do mapa.

Podemos ver os mapas dos maiores arquivos:

Mapa de nível 57: STRANGE MAZE

Cartão de nível 98: SHRINKING

e compare-os com os mapas dos menores arquivos:

Cartão de nível 106: KABLAM

Carta de nível 112: FORTUNE FAVORECE O

Essa comparação apoia nossa ideia de que pequenos arquivos de dados correspondem a níveis mais simples ou contêm mais redundância. Por exemplo, se os dados forem compactados por algum tipo de codificação de duração da execução, isso pode explicar facilmente os intervalos de tamanho de arquivos diferentes.

Se os arquivos forem realmente criptografados, provavelmente teremos que descriptografar a compactação antes de decodificar os dados do cartão.

Estudamos vários arquivos ao mesmo tempo

Nosso breve estudo do primeiro arquivo de dados nos permitiu fazer algumas suposições, mas não encontrou nada concreto. Como próximo passo, começaremos a explorar os padrões de vários arquivos de dados. Por enquanto, assumimos que todos os 148 arquivos usam o mesmo esquema de pedidos para codificar dados, portanto, procurar padrões duplicados nesses arquivos nos ajudará a começar.

Vamos começar do começo dos ladrilhos. A parte superior do arquivo provavelmente é usada para armazenar "metadados" que nos informam sobre o conteúdo do arquivo. Observando apenas a primeira linha do dump hexadecimal, podemos realizar uma comparação simples e rápida dos 16 primeiros bytes e procurar por padrões de destaque neles:

  $ para f em níveis / *;  xxd $ f |  sed -n 1p;  feito |  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 & ...............
 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 ...
 linhas 1-24 / 148 (mais)

Olhando para esse despejo, você pode ver que em cada coluna há alguns valores semelhantes.

Começando com o primeiro byte, logo percebemos que seu valor está em um intervalo muito limitado de valores, no intervalo hexadecimal de 40 (ou aproximadamente 20–60 em decimal). Este é um recurso bastante específico.

Ainda mais interessante é que o segundo byte de cada arquivo é sempre zero, sem exceções. O segundo byte provavelmente não é usado ou é um espaço reservado. No entanto, há outra possibilidade - esses dois primeiros bytes juntos representam um valor de 16 bits armazenado em ordem little-endian.

O que é little-endian? Ao armazenar um valor numérico com mais de um byte, você deve primeiro selecionar a ordem em que os bytes serão armazenados. Se você primeiro armazenar um byte representando a parte menor do número, isso será chamado de ordem direta ( little-endian ); se você primeiro armazenar bytes que denotam a maior parte do número, essa é a ordem inversa ( big-endian ). Por exemplo, escrevemos os valores decimais em ordem inversa (big-endian): a linha "42" significa "quarenta e dois", não "quatro e vinte". Little-endian é uma ordem natural para muitas famílias de microprocessadores, por isso geralmente é mais popular, com exceção dos protocolos de rede, que geralmente exigem big-endian.

Se continuarmos a análise, veremos em breve que o terceiro byte no arquivo não é semelhante aos dois anteriores: seu valor varia em uma ampla faixa. No entanto, o quarto byte é sempre 00 , 01 ou 02 e 01 é o mais comum. Isso também nos sugere que esses dois bytes constituem outro valor de 16 bits, aproximadamente no intervalo de valores decimais de 0 a 700. Essa hipótese também pode ser confirmada pelo fato de que o valor do terceiro byte é geralmente baixo se o valor do quarto byte for 02 e, geralmente, grande se o quarto byte for 00 .

A propósito, vale a pena notar que esse é parcialmente o motivo pelo qual o formato de despejo hexadecimal exibe bytes em pares por padrão - isso facilita a leitura de uma sequência de números inteiros de 16 bits. O formato hexadecimal foi padronizado quando computadores de 16 bits estavam em uso. Tente substituir xxd por xxd -g1 para desativar completamente o agrupamento, e você perceberá que reconhecer pares de bytes no meio de uma linha é muito trabalhoso. Este é um exemplo simples de como as ferramentas usadas para estudar dados desconhecidos tendem a nos fazer perceber certos tipos de padrões. É bom que o xxd destaque esse padrão por padrão, porque é muito comum (ainda hoje, quando computadores de 64 bits são usados em todos os lugares). Mas é útil saber como alterar esses parâmetros se eles não ajudarem.

Vamos continuar a exploração visual e ver se esse padrão é preservado dos valores inteiros de 16 bits. O quinto byte geralmente possui valores muito baixos: 02 e 03 são encontrados com mais frequência e o valor máximo parece ser 05 . O sexto byte de um arquivo é muitas vezes igual a zero - mas às vezes contém valores muito maiores, por exemplo 32 ou 2C . Nesse par, nossa suposição sobre os valores distribuídos no intervalo não é particularmente confirmada.

Estudamos cuidadosamente os valores iniciais

Podemos testar nosso palpite usando od para gerar um dump hexadecimal. O utilitário od é semelhante ao xxd , mas fornece uma seleção muito maior de formatos de saída. Podemos usá-lo para despejar a saída como números inteiros decimais de 16 bits:

A opção -t para o utilitário od especifica o formato de saída. Nesse caso, u representa números decimais não assinados e 2 representa dois bytes por registro. (Você também pode especificar esse formato usando a opção -d .)

  $ para f em níveis / *;  do od -tu2 $ f |  sed -n 1p;  feito |  menos
 0000000 35 476 3 1024 257 778 2819 8995
 0000000 45 447 3 5376 257 802 10499 8738
 0000000 43 417 259 1281 0 262 1794 1285
 0000000 29 211 2 768 257 516 1282 513
 0000000 45 378 3 1536 5140 263 2305 771
 0000000 49 520 2 768 257 517 1538 4883
 0000000 26 183 2 768 1 517 1538 257
 0000000 26 262 3 1280 256 262 1793 771
 0000000 32 378 2 768 514 260 1281 10240
 0000000 58 164 2 768 10280 10244 1282 771
 0000000 38 218 3 1024 1797 265 2561 771
 0000000 36 240 3 1024 771 1029 1796 257
 0000000 42 495 3 1280 257 5126 1792 771
 0000000 44 396 3 1024 771 5 1793 257
 0000000 42 256 3 1024 771 261 1793 1028
 0000000 27365 2 768 257 517 1538 768
 0000000 30 279 2 768 514 260 1281 4864
 0000000 50 494 15 5376 257 3879 10511 5140
 0000000 42 347 3 1280 771 262 1793 5140
 0000000 44 394 2 768 514 260 1281 771
 0000000 29 156 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
 linhas 1-24 / 148 (mais)

Esta saída mostra que nossas suposições sobre os primeiros bytes estavam corretas. Vemos que o primeiro valor de 16 bits está no intervalo decimal de 20 a 70 e o segundo valor de 16 bits está no intervalo decimal de 100 a 600. No entanto, os valores subsequentes não se comportam tão bem. Certos padrões aparecem neles (por exemplo, na quarta posição, surpreendentemente frequentemente 1024), mas eles não têm a repetibilidade inerente aos primeiros valores do arquivo.

Portanto, vamos primeiro assumir que os quatro primeiros bytes do arquivo são especiais e consistem em dois valores de 16 bits. Como eles estão no início do arquivo, eles provavelmente são metadados e ajudam a determinar como ler o restante do arquivo.

De fato, o segundo intervalo de valores (100-600) está bem próximo do intervalo de tamanho de arquivo que observamos anteriormente (208-680). Talvez isso não seja uma coincidência? Vamos apresentar uma hipótese: o valor de 16 bits armazenado no terceiro e quarto bytes do arquivo se correlaciona com o tamanho total do arquivo. Agora que temos uma hipótese, podemos testá-la. Vamos ver se os arquivos grandes neste local realmente têm valores grandes o tempo todo e os pequenos têm valores pequenos.

Para exibir o tamanho do arquivo em bytes sem nenhuma outra informação, você pode usar wc com a opção -c . Da mesma forma, você pode adicionar ao od opções que permitem exibir apenas os valores de seu interesse. Em seguida, podemos usar a substituição de comandos para escrever esses valores para projetar variáveis e exibi-los juntos:

A opção -An do utilitário od desativa a coluna mais à esquerda, que exibe o deslocamento no arquivo, e -N4 diz od parar após os primeiros 4 bytes do arquivo.

  $ para f em níveis / *;  faça tamanho = $ (wc -c <$ f);  data = $ (od-tuS-An -N4 $ f);  eco "$ size: $ data";  feito |  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

Olhando para esta saída, você pode ver que os valores estão aproximadamente correlacionados. Arquivos menores geralmente têm valores mais baixos na segunda posição e arquivos grandes têm valores maiores. No entanto, a correlação não é precisa e vale a pena notar que o tamanho do arquivo é sempre significativamente maior que o valor armazenado nele.

Além disso, o primeiro valor de 16 bits também é geralmente maior com tamanhos grandes de arquivo, mas a correspondência também não é completa e você pode facilmente encontrar exemplos de arquivos de tamanho médio com valores relativamente grandes na primeira posição. Mas talvez, se somarmos esses dois valores, a soma deles será melhor correlacionada com o tamanho do arquivo?

Podemos usar readpara extrair dois números da saída odem variáveis separadas e, em seguida, usar a aritmética do shell para encontrar sua soma:

comando Shellreadnão pode ser usado no lado direito da barra vertical, porque os comandos transferidos para o pipeline são executados em um processador de comandos filho (subshell), que, ao sair, leva suas variáveis de ambiente para o receptor de bits. Portanto, em vez disso, precisamos usar a função de substituição de processo bashe direcionar a saída odpara um arquivo temporário, que pode ser redirecionado para o comando read.

$ para f em níveis / *; faça tamanho = $ (wc -c <$ f); leia v1 v2 << (od -tuS -An -N4 $ f); soma = $ (($ v1 + $ v2));
    eco "$ size: $ v1 + $ v2 = $ sum"; feito | 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
linhas 1-24 / 148 (mais)

A soma dos dois números também se correlaciona aproximadamente com o tamanho do arquivo, mas eles ainda não coincidem. Quão diferentes eles são? Vamos demonstrar sua diferença:

$ para f em níveis / *; faça tamanho = $ (wc -c <$ f); leia v1 v2 << (od -tuS -An -N4 $ f); diff = $ ((tamanho $ - $ v1 - $ v2));
    echo "$ size = $ v1 + $ v2 + $ diff"; feito | 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)

A diferença, ou o valor "restante", é exibida no lado direito da saída. Esse valor não se enquadra no padrão constante, mas parece permanecer aproximadamente em um intervalo limitado de 40 a 120. E, novamente, quanto maiores os arquivos, geralmente o valor residual é maior. Mas, às vezes, arquivos pequenos também têm grandes valores residuais; portanto, isso não é tão constante quanto gostaríamos.

No entanto, vale ressaltar que os valores dos resíduos nunca são negativos. Portanto, a ideia de que esses dois valores de metadados indicam subseções de um arquivo permanece atraente.

(Se você for cuidadoso o suficiente, você já viu algo dando uma dica sobre uma conexão que ainda não foi notada. Se você não tiver, continue lendo; o segredo será revelado em breve.)

Comparações maiores entre arquivos

Nesse momento, seria bom poder comparar mais de 16 bytes por vez. Para isso, precisamos de um tipo diferente de visualização. Uma boa abordagem é criar uma imagem na qual cada pixel denota um byte separado de um dos arquivos, e a cor denota o valor desse byte. Uma imagem pode mostrar uma fatia de todos os 148 arquivos por vez, se cada arquivo de dados for indicado por uma única linha de pixels da imagem. Como todos os arquivos têm tamanhos diferentes, usamos os primeiros 200 bytes de cada um para criar uma imagem retangular.

A maneira mais fácil é criar uma imagem em escala de cinza, na qual o valor de cada byte corresponde a diferentes níveis de cinza. É muito simples criar um arquivo PGM com nossos dados, porque o cabeçalho PGM consiste apenas em texto ASCII:

 $ echo P5 200 148 255 >hdr.pgm

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

P5É a assinatura inicial para o formato de arquivo PGM. Os próximos dois números 200e 148especificam a largura e a altura da imagem e o último 255,, indica o valor máximo por pixel. O cabeçalho PGM termina com uma nova linha seguida por dados de pixel. (É importante notar que o cabeçalho PGM geralmente é dividido em três linhas de texto separadas, mas o padrão PGM exige apenas que os elementos sejam separados por algum caractere de espaço em branco.)

Podemos usar o utilitário headpara extrair os primeiros 200 bytes de cada arquivo:

$ para f em níveis / *; faça -c200 $ f; done> out.pgm

Em seguida, podemos concatená-los com um cabeçalho e criar uma imagem exibida:

xview- este é um programa X antigo para exibir imagens em uma janela. Você pode substituí-lo pelo seu visualizador de imagens favorito, por exemplo, um utilitário displaydo ImageMagick, mas lembre-se de que existem surpreendentemente muitos visualizadores de imagens que não aceitam um arquivo de imagem redirecionado para a entrada padrão.

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

Se for difícil considerar os detalhes em uma imagem escura, você poderá escolher um esquema de cores diferente. Use o utilitário pgmtoppmImageMagick para converter pixels em um intervalo diferente de cores. Esta versão criará uma imagem "negativa":

$ cat hdr.pgm out.pgm | pgmtoppm branco-preto | xview / dev / stdin

E esta versão torna os valores baixos em amarelo e os valores altos em azul:

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

A visibilidade das cores é uma questão muito subjetiva, para que você possa experimentar e escolher qual é o melhor para você. Seja como for, a imagem 200 × 148 é bastante pequena, portanto, é melhor aumentar a visibilidade aumentando seu tamanho:

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

A imagem está escura e isso significa que a maioria dos bytes contém valores pequenos. Uma faixa perceptível de pixels principalmente brilhantes próximos à borda esquerda contrasta com ela. Essa faixa está localizada no terceiro byte do arquivo, que, como dissemos acima, varia em toda a faixa de valores.

E embora não existam muitos valores altos fora do terceiro byte, quando eles aparecem, eles geralmente consistem em séries, criando pequenas faixas brilhantes na imagem. Algumas dessas séries são interrompidas periodicamente, criando um efeito de linha tracejada. (Talvez, com a seleção de cores correta, seja possível notar essas seqüências em cores mais escuras.)

Com um estudo cuidadoso da imagem, pode-se entender que principalmente na parte esquerda predominam pequenas faixas verticais. Essas bandas nos falam sobre repetibilidade na maioria dos arquivos. Mas nem todos os arquivos - de tempos em tempos, existem linhas de pixels nas quais as bandas são interrompidas - mas isso é mais do que suficiente para determinar a presença de um padrão real. Esse padrão desaparece no lado direito da imagem, o fundo escuro das faixas dá lugar a algo mais barulhento e indefinido. (Parece que as listras também estão faltando na parte esquerda da imagem, mas, repito, é possível que ao usar um esquema de cores diferente, você possa ver que elas começam mais perto da borda esquerda do que parece aqui.)

As faixas consistem em linhas finas de pixels levemente mais brilhantes contra um fundo de pixels levemente mais escuros. Portanto, esse padrão gráfico deve se correlacionar com o padrão de arquivos de dados nos quais valores ligeiramente maiores são igualmente dispersos entre valores de bytes ligeiramente menores. Parece que as listras estão vazias no meio da imagem. Como mostra os primeiros 200 bytes de arquivos, você deve esperar que o padrão de bytes termine após cerca de 100 bytes.

O fato de esses padrões mudarem em diferentes arquivos de dados deve nos levar à pergunta: como serão os arquivos após os primeiros 200 bytes. Bem, podemos facilmente substituir o utilitário por um headutilitário taile ver como são os últimos 200 bytes:

$ para f em níveis / *; faça tail -c200 $ f; done> out.pgm; gato hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

Vimos imediatamente que essa área de arquivos de dados é muito diferente. Aqui, os bytes são muito mais comuns, especialmente no final do arquivo. (No entanto, como antes, eles preferem agrupar, cobrindo a imagem com faixas horizontais brilhantes.) Parece que a frequência de valores altos de bytes aumenta quase até o fim, onde é interrompida abruptamente e é substituída por valores baixos nos últimos dez a doze bytes. E o padrão aqui também não é universal, mas é padrão demais para ser uma coincidência.

Talvez no meio dos arquivos possam haver outras áreas que ainda não consideramos. A próxima coisa que queremos fazer é examinar todos os arquivos dessa maneira. Mas como todos os arquivos têm tamanhos diferentes, eles não podem ser colocados em uma bela matriz retangular de pixels. Podemos preencher o final de cada linha com pixels pretos, mas seria melhor redimensioná-los para que todas as linhas tenham a mesma largura e as áreas proporcionais de arquivos diferentes correspondam mais ou menos.

E podemos realmente fazer isso com um pouco mais de esforço. Você pode usar o Python e sua biblioteca para trabalhar com imagens PIL(“Pillow”):

Arquivo 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()

Quando chamamos esse script, usando a lista completa de arquivos de dados como argumentos, ele cria uma imagem completa e a exibe em uma janela separada:

 Níveis $ python showbytes.py / *

Infelizmente, embora esta imagem esteja completa, ela não nos mostra nada de novo. (Mas, na verdade, mostra menos ainda, porque o redimensionamento destruiu o padrão das faixas.) Provavelmente, para estudar todo o conjunto de dados, precisamos de um melhor processo de visualização.

Caracterizar os dados

Com isso em mente, vamos parar por um momento e concluir um censo completo de dados. Precisamos saber se os arquivos de dados dão preferência a determinados valores de bytes. Por exemplo, se cada valor geralmente for igualmente duplicado, será uma forte evidência de que os arquivos estão realmente compactados.

Para

reescrever completamente os valores, basta algumas linhas no Python: O arquivo census.py:

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

Tendo colocado todos os dados em uma variável, podemos calcular a frequência de ocorrência de cada valor de byte.

$ cat levels / * | 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
linhas 1-24 / 256 (mais)

Vemos que, na maioria das vezes, existem valores de bytes 0 e 1, os seguintes em frequência são 2 e 3, após o qual o número continua a diminuir (embora com menos constância). Para visualizar melhor esses dados, podemos transferir a saída gnuplote transformar esse censo em um histograma:

A opção de -putilitário gnuplotordena que não feche a janela com o gráfico após a conclusão do trabalho gnuplot.

$ cat levels / * | python ./census.py | gnuplot -p -e 'plot "-" com caixas'

É muito perceptível que os primeiros valores de bytes são muito mais comuns que todos os outros. Vários dos seguintes valores também são bastante comuns e, em seguida, as frequências de valores de cerca de 50 começam a diminuir ao longo de uma curva de probabilidade suave. No entanto, há um subconjunto de valores altos que são uniformemente separados um do outro, cuja frequência parece bastante estável. Observando a saída original, podemos garantir que esse subconjunto consista em valores que podem ser divisíveis por oito.

Essas diferenças no número de valores sugerem que existem várias "classes" diferentes de valores de bytes, portanto, será lógico ver como essas classes são distribuídas. O primeiro grupo de valores de bytes será o valor mais baixo: 0, 1, 2 e 3. Em seguida, o segundo grupo pode ter valores de 4 a 64. E o terceiro grupo terá valores acima de 64, que são divisíveis por 8. Qualquer outra coisa, incluindo não divisível por 8 valores maiores que 64 será o quarto e último grupo.

Com tudo isso em mente, podemos alterar o último script de geração de imagem escrito. Em vez de exibir os valores reais de cada byte em uma cor separada, vamos apenas mostrar a qual grupo cada byte pertence. Você pode atribuir uma cor exclusiva a cada um dos quatro grupos, e isso nos ajudará a ver se determinados valores realmente aparecem em determinados lugares.

Arquivo 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()

Atribuímos quatro grupos vermelho, verde, azul e branco. (Novamente, você pode tentar escolher outras cores para atender às suas preferências.)

 Níveis $ python showbytes2.py / *

Graças a esta imagem, podemos pré-confirmar a correção da separação dos arquivos de dados em cinco partes:

O cabeçalho de quatro bytes que encontramos anteriormente.
, , (.. ).
, (. 64).
, .
, .

Graças a essas cores, fica claro que na quarta parte, onde prevalecem valores altos de bytes, como pode ser visto na imagem em tons de cinza, valores altos de bytes, dividindo por 8, principalmente, prevalecem 8.

Na imagem anterior, sabemos que a segunda parte, ou seja, a parte com listras estende-se por uma área quase completamente vermelha. De fato, em uma das primeiras imagens, vimos que a parte com listras, indo da esquerda para a direita, brilha lentamente em média.

Vimos novamente que os pixels verdes da terceira parte principal formam padrões pontilhados de pixels verdes e vermelhos intermitentes (azuis ou brancos) de tempos em tempos. No entanto, esse padrão não é particularmente regular e pode ser imaginário.

Obviamente, essa divisão do arquivo em cinco partes é muito arbitrária. Uma quarta parte com altos valores de bytes divisíveis por oito pode acabar sendo apenas o final da terceira parte. Ou pode ser melhor dividir uma terceira parte grande em várias partes que ainda não determinamos. Nesta fase, a descoberta de peças nos ajuda a encontrar mais lugares para pesquisas adicionais. Por enquanto, basta que saibamos que existem partes nas quais a composição geral dos valores de bytes é alterada, e uma ideia aproximada do seu tamanho nos ajudará a continuar nossa pesquisa.

Pesquisa de estrutura

O que devemos procurar a seguir? Bem, como antes, a maneira mais fácil de começar é do topo do arquivo. Ou melhor, perto do topo. Como já identificamos com bastante confiança a primeira parte como um cabeçalho de quatro bytes, vamos dar uma olhada no que vem a seguir - a área que chamamos de segunda parte ou parte das bandas. Essas bandas são a dica mais forte da existência da estrutura; portanto, é melhor procurar novas evidências da presença do padrão aqui.

(Por enquanto, assumimos que o padrão de faixa começa imediatamente após os primeiros quatro bytes. Visualmente, isso não é óbvio, mas parece provável, e o exame dos valores de bytes deve nos mostrar rapidamente a verdade.)

Vamos voltar ao hex dump, desta vez focando na segunda parte. Lembre-se de que esperamos encontrar um padrão repetitivo de valores um pouco mais altos distribuídos igualmente entre valores um pouco mais baixos.

A opção -s4ordena xxdpular os primeiros 4 bytes do arquivo.

$ para f em níveis / *; faça xxd -s4 $ f | sed -n 1p; feito | 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)

Observando atentamente a sequência de bytes na string, podemos ver um padrão no qual o primeiro, quarto, sétimo e décimo bytes são maiores que os vizinhos mais próximos. Esse padrão é imperfeito, possui exceções, mas é definitivamente estável o suficiente para criar a repetibilidade visual das bandas vistas em todas as imagens. (E é suficiente para confirmar nossa suposição de que o padrão de faixas começa imediatamente após o cabeçalho de quatro bytes.) A

constância desse padrão implica claramente que essa parte do arquivo é uma matriz ou tabela e cada registro na matriz possui um comprimento de três bytes.

Você pode configurar o formato de hex dump para facilitar a visualização da saída como uma série de trigêmeos:

A opção -g3define o agrupamento por três bytes em vez de dois. Opção-c18 define 18 bytes (um múltiplo de 3) por linha em vez de 16.

$ para f em níveis / *; faça xxd -s4 -g3 -c18 $ f | sed -n 1p; feito | 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)

Em um dump formatado dessa maneira, alguns outros recursos desse padrão começam a aparecer. Como antes, o primeiro byte de cada trigêmeo é geralmente maior que os bytes ao seu redor. Você também pode notar que o segundo e o terceiro bytes de cada trigêmeo são frequentemente duplicados. Descendo a primeira coluna, veremos que a maioria dos valores do segundo e terceiro bytes são iguais 0000. Mas valores diferentes de zero também são frequentemente encontrados em pares, por exemplo, 0101ou 2323. Esse padrão também é imperfeito, mas tem muito em comum para ser uma coincidência. Observando a coluna ASCII à direita, veremos que, quando temos valores de bytes que correspondem ao caractere ASCII imprimível, eles geralmente são encontrados em pares.

Outro padrão que vale a pena mencionar que não é percebido imediatamente: o primeiro byte de cada triplo aumenta da esquerda para a direita. Embora esse padrão seja menos perceptível, sua estabilidade é alta; precisamos examinar muitas linhas antes de encontrar a primeira incompatibilidade. E os bytes geralmente aumentam em valores pequenos, mas eles não representam nenhum padrão regular.

Ao estudar a imagem original, percebemos que a parte com as listras termina em cada arquivo e não no mesmo local. Há uma transição da criação de uma faixa de padrão à esquerda para ruído aleatório à direita, mas essa transição ocorre para cada linha de pixels em pontos diferentes. Isso implica que deve haver algum marcador para que o programa que está lendo o arquivo de dados possa entender onde a matriz termina e outro conjunto de dados começa.

Vamos voltar ao despejo apenas no primeiro nível para examinar o arquivo inteiro:

 $ xxd -s4 -g3 -c18 níveis / lição_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

Estudando a sequência de trigêmeos, podemos supor provisoriamente que a parte com faixas nesses dados termina após 17 trigêmeos, por deslocamento 00000036. Isso não é exato, mas o primeiro byte de cada trigêmeo aumenta constantemente seu valor e depois diminui no décimo oitavo trigêmeo. Mais uma prova: no décimo oitavo trigêmeo, o segundo byte tem o mesmo significado que o primeiro. Ainda não percebemos isso, mas, se voltarmos e olharmos, veremos que o primeiro byte nunca é igual ao segundo ou terceiro byte.

Se nossa teoria dos marcadores estiver correta, existem duas possibilidades. Em primeiro lugar, é possível que, após a parte da tira, exista algum valor de byte especial (logo após o décimo sétimo trigêmeo). Em segundo lugar, provavelmente existe um valor armazenado em algum lugar igual ao tamanho da peça com listras. Esse tamanho pode ser igual a 17 (ou seja, indica o número de trigêmeos) ou 51 (indica o número total de bytes em uma parte) ou 55 (51 mais 4, ou seja, o deslocamento do arquivo no qual essa parte termina).

Para a primeira opção, um valor de byte duplo pode ser um marcador para o final da parte (dado que essa sequência nunca ocorre na segunda parte). No entanto, o estudo cuidadoso de vários outros arquivos de dados contradiz essa idéia, porque esse padrão não aparece em nenhum outro lugar.

Para a segunda opção, obviamente procurará o indicador de tamanho na primeira parte. Eis que o primeiro valor de 16 bits no cabeçalho do arquivo de quatro bytes é 17:

 $ od -An -tuS -N4 levels / lição_1.pak
    17 203

Se nossa teoria estiver correta, esse valor não determina o tamanho da peça com faixas, mas o número de registros de três bytes. Para testar essa idéia, voltemos à computação, onde comparamos a soma de dois valores inteiros de 16 bits com o tamanho do arquivo. Desta vez, multiplicamos o primeiro número por três para obter o tamanho real em bytes:

$ para f em níveis / *; faça tamanho = $ (wc -c <$ f); leia v1 v2 << (od -tuS -An -N4 $ f); diff = $ ((tamanho $ - 3 * $ v1 - $ v2));
    echo "$ size = 3 * $ v1 + $ v2 + $ diff"; feito | 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)

Sim! Após essa alteração, o valor total do cabeçalho é sempre exatamente quatro a menos que o tamanho do arquivo de dados inteiro. E como quatro também é o número de bytes no cabeçalho, é óbvio que isso não é uma coincidência. O primeiro número nos fornece o número de entradas de três bytes na tabela e o segundo número nos fornece o número de bytes que compõem o restante do arquivo de dados.

Encontramos uma fórmula constante, o que significa que agora entendemos completamente o que significam os números na primeira parte.

(A propósito, aqui está o padrão muito secreto que os leitores atentos podem perceber. Um estudo cuidadoso das equações deixa claro que, quando os arquivos têm o mesmo primeiro número, eles obtêm a mesma diferença residual. Isso acontece porque a diferença é sempre duas vezes o valor Este é um padrão não óbvio, mas um observador meticuloso ou bem-sucedido pode notá-lo.)

Portanto, podemos dizer que o arquivo tem três partes principais:

cabeçalho de quatro bytes;
tabela de registros de três bytes; e
o restante do arquivo, que supostamente contém a maioria dos dados.

(Consequentemente, as outras partes que determinamos anteriormente anteriormente devem ser subseções da terceira parte.)

Interpretando Metadados

Dado esse esquema, seria lógico supor que as entradas na tabela da segunda parte sejam alguns metadados necessários para interpretar os dados da terceira parte.

Mas que tipo de metadados esta tabela contém?

Observamos acima que existem alguns sinais de que o arquivo de dados pode ser compactado. (Agora isso parece ainda mais plausível, porque sabemos que a terceira parte de cada arquivo, supostamente contendo dados de cada nível, tem apenas 100-600 bytes de tamanho.) Nesse caso, é bem possível que a tabela que precede os dados principais contenha metadados de compactação - um dicionário usado durante a descompactação. Por exemplo, antes dos dados codificados pelo algoritmo de Huffman, geralmente há um dicionário que mapeia os valores de bytes originais para sequências de bits. Embora não esperemos que esses arquivos sejam codificados pelo algoritmo Huffman (como os dados mostram padrões claros no nível de bytes, ou seja, dificilmente são um fluxo de bits), seria prudente tentar interpretar essa tabela como um dicionário de descompressão.

(É claro que nem todo tipo de compactação usa um dicionário armazenado. Por exemplo, o algoritmo de deflação usado no gzipe zlibpermite recriar o dicionário diretamente do fluxo de dados. Mas esses casos são a exceção e não a regra.)

Normalmente, a entrada do dicionário consiste em duas partes: a chave e valores. Obviamente, algumas vezes uma chave está implícita, por exemplo, quando é ordenada não em uma tabela de pesquisa, mas em uma matriz. No entanto, já observamos que os registros de três bytes parecem consistir em duas partes - em particular, o primeiro byte de cada registro segue um padrão claramente diferente do padrão do segundo e terceiro bytes. Com isso em mente, uma primeira hipótese razoável seria considerar o primeiro byte como a chave e os dois bytes restantes como o valor.

Se esse for o caso, uma das maneiras mais simples de interpretar a parte da faixa é que o primeiro byte é o valor do byte que precisa ser substituído nos dados compactados e o segundo e o terceiro bytes são o valor que precisa ser substituído. O resultado criado por esse esquema será definitivamente maior, embora não esteja claro quanto. Seja como for, essa é uma hipótese lógica e é bastante fácil de verificar. Podemos escrever um pequeno programa em Python que implementa esse esquema de descompressão:

File 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)

Agora podemos verificar esse script usando um exemplo de arquivo de dados:

$ 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

No entanto, os resultados não são dignos de nota. Obviamente, o fluxo de dados resultante tornou-se mais implantado que o original, mas não muito. Definitivamente, não é suficiente para conter todos os dados que esperamos encontrar. Obviamente, esse esquema de descompactação é um pouco mais simples que o necessário.

Se examinarmos cuidadosamente a saída resultante, veremos em breve que ela começa com muitos bytes repetidos. 0b, 04, 00, 0a- todos eles ocorrem em pares. Observando o original compactado, veremos que todos esses pares surgiram devido a uma substituição do dicionário. Mas, no processo, notamos imediatamente que todos esses significados duplicados também correspondem às entradas no dicionário. Ou seja, se aplicarmos novamente o dicionário, os dados serão expandidos novamente. Talvez não estejamos descompactando o suficiente?

Nosso primeiro palpite pode ser realizar uma segunda passagem, aplicando cada entrada do dicionário uma segunda vez para expandir ainda mais os dados. O segundo palpite pode ser executar várias passagens com o dicionário, repetindo o processo até que todos os bytes semelhantes às chaves do dicionário sejam substituídos. No entanto, se dermos uma olhada na estrutura do dicionário, percebemos que simplesmente aplicamos as entradas do dicionário da direita para a esquerda , e não da esquerda para a direita, quando todos os nossos valores são expandidos em uma única passagem.

Tomando essa hipótese, podemos ver a estrutura de um algoritmo de compressão mais plausível. O programa pega os dados de origem e os verifica, procurando as seqüências mais comuns de dois bytes. Em seguida, substitui a sequência de dois bytes por um valor de byte que não é encontrado nos dados. Em seguida, repete o processo, continuando-o até que os dados contenham mais de duas repetições de seqüências de byte duplo. De fato, esse algoritmo de compactação tem um nome: é conhecido como compactação "re-emparelhar", que é a abreviação de "pares recursivos".

(E isso pode explicar alguns padrões que vemos no dicionário. Durante a compactação, o dicionário é construído da esquerda para a direita, portanto, ao descompactar, ele deve ser aplicado da direita para a esquerda. Como as entradas do dicionário geralmente se referem às entradas anteriores, é lógico que o segundo e o terceiro bytes geralmente sejam menor que o primeiro.)

Embora a remontagem da compactação não produza resultados muito impressionantes, ela tem uma vantagem: o descompactador pode ser implementado com um mínimo de código. Eu próprio usei o emparelhamento em algumas situações em que precisei minimizar o tamanho total dos dados compactados e o código de descompressão.

Portanto, podemos fazer uma alteração em uma linha do programa Python para aplicar o dicionário da direita para a esquerda:

Arquivo 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)

Se tentarmos esta versão, a saída será muito maior:

 $ 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 ................
linhas 1-24 / 93 (mais)

Vemos muitos bytes nulos nesta saída, mas isso pode muito bem corresponder a um cartão quase vazio. Bytes diferentes de zero parecem estar agrupados um ao lado do outro. Como esperamos encontrar uma placa 32 × 32, reformate a saída para 32 bytes por linha:

$ python ./decompress2.py <levels / lição_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)

Tendo analisado cuidadosamente padrões de valores diferentes de zero, veremos que o mapa é claramente visível na saída. De fato, podemos tornar esse padrão mais visível usando a ferramenta de despejo “colorida”, que atribui uma cor a cada valor de byte, simplificando a pesquisa de padrões de valores repetidos:

xcdé uma ferramenta não padrão, mas você pode baixá-lo aqui . Observe a opção do -rutilitário less, que informa para limpar as seqüências de controle.

Compare isso com um mapa de primeiro nível desenhado por fãs:

Sem dúvida, vemos os dados do mapa de níveis. Você pode ter certeza de que determinamos corretamente o algoritmo de descompactação.

Interpretação de dados

Ao comparar os valores de bytes com a imagem do mapa, podemos determinar o que 00codifica um bloco vazio, 01codifica uma parede e 23indica um chip. 1Aindica uma porta vermelha, 1B- uma porta azul, e assim por diante. Podemos atribuir valores exatos às fichas, chaves, portas e todas as outras peças que compõem todo o mapa de níveis.

Agora podemos ir para o próximo nível e encontrar os valores de bytes para os objetos que aparecem lá. E continue com os próximos níveis até obter uma lista completa de valores de bytes e objetos de jogo que eles codificam.

Como sugerimos inicialmente, o cartão termina exatamente após 1024 bytes (no deslocamento 000003FF).

Desta vez, para remover as primeiras 32 linhas do despejo, usamossed. Como temos 32 bytes por linha, pularemos os primeiros 1024 bytes.

Imediatamente após os dados do mapa, há uma sequência de 384 bytes (cujos valores estão no intervalo 00000400- 0000057F), quase todos iguais a zero, mas valores diferentes de zero também ficam entre eles. Depois disso, surge um padrão de bytes completamente diferente, portanto, seria lógico supor que essa sequência de 384 bytes seja uma parte separada.

Se observarmos mais alguns níveis, notamos rapidamente o padrão. A parte de 384 bytes na verdade consiste em três subseções, cada uma com 128 bytes de comprimento. Cada subseção começa com alguns bytes diferentes de zero, seguidos de zeros que preenchem o restante da subseção.

Alguns níveis contêm muitos dados; para outros (por exemplo, para o primeiro nível) apenas o mínimo. Comparando os níveis com seus cartões, notamos em breve que a quantidade de dados nesta parte do arquivo está diretamente relacionada ao número de "mobs" por nível. Nesse caso, o número de "monstros" inclui todas as criaturas no nível, blocos de terra (que não se movem independentemente, mas podem ser empurrados) e o personagem principal, Chip (jogador). Ou seja, os mobs não são indicados no próprio mapa, mas são codificados nesses três buffers.

Depois que soubemos que essas três subseções contêm dados sobre os mobs no nível, não será muito difícil descobrir o que está contido em cada uma das subseções.

A primeira subseção de 128 bytes é uma lista de valores de bytes que determinam o tipo de mob. Por exemplo, os buffers de segundo nível têm a seguinte aparência:

 $ 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 ................
linhas 64-87 / 93 (mais)

Compare isso com um mapa de nível:

Nesse nível, existem seis monstros: três bugs, dois blocos e um chip. A primeira subchave de 128 bytes contém um byte 06, três bytes 08e dois bytes 1C. Seria razoável concluir o que 06Chip representa 08- um bug e 1C- um bloco.

(Continuando a comparar arquivos de dados a partir dos níveis dos cartões e preencha o nosso mobs dicionário, nós rapidamente encontrar uma falha nessa teoria: O chip pode ser referido quatro valores diferentes, ou seja 04, 05, 06ou07. Na verdade, esse conjunto de notações contém todos os mobs. Quando estudarmos cuidadosamente os diferentes valores, entenderemos eventualmente que o valor 0, 1, 2 ou 3 é adicionado ao valor do byte, indicando o tipo, indicando a direção inicial da multidão: norte, leste, sul ou oeste. Ou seja, por exemplo, um valor de byte 06indica um Chip olhando para o sul.)

O significado das outras duas subseções é menos óbvio. Mas, tendo estudado os valores repetidos nessas subseções e comparando as placas para esses mobs, entenderemos que os bytes na segunda subseção armazenam a coordenada X de cada mob e os bytes na terceira subseção armazenam a coordenada Y de cada mob. A compreensão dessa decisão é prejudicada pelo fato de que as coordenadas armazenadas nessas subseções são na verdade deslocadas 3 bits para a esquerda, ou seja, multiplicado por 8. Esse pequeno fato explica o grupo "azul", encontrado no censo de valores. (As razões pelas quais essa alteração foi feita não são claras, mas é mais provável que os três bits inferiores sejam usados para representar a animação quando os mobs se movem.)

Depois de lidar com essa parte, agora podemos ver quantos arquivos de dados têm apenas alguns bytes restantes:

Nota o quexxdaceita um -svalor hexadecimal para a opção

$ para f em níveis / *; faça python ./decompress2.py <$ f | xxd -s 0x580 | sed -n 1p; feito | 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 o primeiro par de bytes no restante indica rapidamente que eles contêm outro valor inteiro de 16 bits. Se você contá-los de modo que a maioria dos valores em notação decimal é um número redondo:

comando odpara ir para o original deslocamento é usado -jem vez -s. Também vale a pena observar o comando printf: além de fornecer formatação, é uma maneira conveniente de exibir texto sem uma nova linha pendurada no final.

$ para f em níveis / *; imprimef "% -20s" $ f; python ./decompress2.py <$ f | od -An -j 0x580 -tuS -N2; feito | menos
levels / all_full.pak 400
levels / alphabet.pak 0
levels / amsterda.pak 500
níveis / apartmen.pak 300
níveis / arcticfl.pak 400
levels / balls_o_.pak 300
levels / beware_o.pak 300
níveis / blink.pak 600
levels / blobdanc.pak 0
levels / blobnet.pak 500
levels / block_fa.pak 500
levels / block_ii.pak 750
levels / block_n_.pak 600
levels / block_ou.pak 350
níveis / bloco.pak 450
levels / bounce_c.pak 300
levels / brushfir.pak 80
levels / cake_wal.pak 999
levels / castle_m.pak 600
níveis / catacomb.pak 399
levels / cellbloc.pak 0
níveis / chchchip.pak 300
níveis / chiller.pak 399
levels / chipmine.pak 700
linhas 1-24 / 148 (mais)

Se voltarmos à lista, criada originalmente a partir dos dados que esperávamos encontrar nos arquivos, perceberemos que esse número é o momento de concluir o nível (se o valor for zero, não haverá limite de tempo no nível).

Após esses dois bytes, os dados se tornam mais voláteis. O fato de que para a maioria dos níveis existem cerca de dez bytes restantes no arquivo limita seriamente seu conteúdo:

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

Por exemplo, apenas nove bytes permanecem nesse nível. Levamos em conta esse tamanho limitado e o fato de esses nove bytes conterem quatro ocorrências do valor 17, coletadas em dois pares. Notaremos imediatamente que o padrão de números 17corresponde ao padrão de letras Lno nome do nível "TUDO CHEIO". O nome tem oito caracteres, portanto o byte nulo no final provavelmente é o caractere de final de linha. Depois de descobrir isso, você pode examinar trivialmente todos os outros níveis e usar seus nomes para criar uma lista completa de caracteres:

`00`	fim de linha
`01`	barra de espaço
`02` - `0B`	dígitos de 0 a 9
`0C` - `25`	letras AZ
`26` - `30`	sinais de pontuação

Para a maioria dos níveis, o arquivo de dados termina aqui. No entanto, algumas dúzias do nome ainda têm dados. Se dermos uma olhada na lista, veremos que existem níveis com botões de dica, e esses dados restantes contêm o texto da linha de dica de nível codificada com o mesmo conjunto de caracteres que os nomes dos níveis.

Depois disso, chegamos ao final de todos os arquivos. Agora, temos uma descrição completa do esquema da camada de dados. Nossa tarefa está concluída.

Negócios inacabados

Um leitor atento pode perceber que, inicialmente, esperávamos encontrar mais dois elementos nesses arquivos que nunca encontramos. Explicaremos a ausência de ambos:

O primeiro elemento é o número de chips, ou seja, O número total de fichas que um jogador deve coletar para passar pelo conector do chip. Como dissemos inicialmente, geralmente é igual ao número total de fichas em um nível, mas isso nem sempre acontece. Portanto, esses dados devem ser obtidos de alguma maneira. A resposta pode ser encontrada estudando cartas dos níveis em que existem fichas extras. Acontece que dois valores diferentes são usados para indicar chips. O valor 23que encontramos inicialmente, mas o valor também é usado31denotando um chip que não afeta a quantidade total necessária para abrir o conector do chip. (No entanto, do ponto de vista da jogabilidade, os dois tipos de fichas são os mesmos. Se houver um tipo de ficha 31no nível, então no nível você não poderá coletar nenhum número de fichas.)

O segundo elemento é a senha de nível de quatro letras. Não está oculto em nenhum lugar nos dados de nível. Infelizmente, esse problema não pode ser resolvido por uma investigação mais aprofundada do arquivo de dados. Somos forçados a concluir que as senhas são simplesmente armazenadas em outro lugar. A explicação mais provável: eles são codificados em algum lugar do próprio programa. No entanto, mais tarde ficou claro que as senhas não são armazenadas diretamente. De pessoas familiarizadas com o próprio código, aprendi que as senhas são geradas dinamicamente usando um gerador de números pseudo-aleatórios inicializado com uma sequência específica. Portanto, as senhas para níveis não podem ser alteradas diretamente; isso só pode ser feito alterando o código do assembler.

Posfácio

Fazendo uma engenharia reversa completa dos dados nos arquivos de nível, eu poderia começar a escrever um programa que pode codificar e decodificar dados de nível. Graças a ela, eu pude criar o tão esperado editor de níveis para a versão do Chip's Challenge for Lynx, e a presença dessa ferramenta aumentou muito minha capacidade de estudar a lógica do jogo e também melhorou a qualidade de sua emulação.

Mas ... devo admitir que pessoalmente fiz o desenvolvimento reverso dos arquivos de dados de uma maneira não descrita acima. Comecei do outro lado - com a definição de dados de string. Comecei a estudar os arquivos dos oito primeiros níveis. Como eles são chamados de “LIÇÃO 1” a “LIÇÃO 8”, procurei os dados de substrings idênticos neles. E tive sorte: nenhum dos nomes desses níveis foi compactado; portanto, todos os oito nomes são armazenados nos arquivos de dados em sua forma original. Obviamente, fiquei envergonhado por essas linhas não terem sido armazenadas em caracteres ASCII, mas o duplo S no nome me ajudou a detectar um padrão que se repetia nos oito arquivos de dados. E, tendo encontrado o nome, reconheci a codificação de caracteres de letras, números e o caractere de espaço. Depois apliquei essa codificação no restante do arquivo e, logo após o nome, vi linhas de prompt e comecei a observar as anomalias:

Um ótimo utilitário trfacilita a conversão de seu próprio conjunto de caracteres de arquivos de dados para ASCII.

$ tr '\ 001- \ 045' '0-9A-Z' <níveis / lição_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 & 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 & 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 e 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 exemplo, no texto de ajuda, há dois lugares onde a sequência de S e o espaço são substituídos pelo colchete direito. Essas anomalias me deram evidências suficientes para calcular dedutivamente a presença de compressão e obter algumas informações sobre sua natureza. Mais tarde, associei valores anormais de bytes com suas ocorrências mais perto do início do arquivo de dados. (Por exemplo, no despejo de deslocamento hexadecimal mostrado acima, 00000035há um colchete direito, seguido por um capital S e um espaço.) A partir disso, calculei o esquema de compactação de maneira semelhante ao processo descrito no artigo. Tudo o resto era bem simples.

Parece-me que se pode tirar uma lição disso: não há uma maneira única de examinar um arquivo de dados desconhecido. Qualquer ferramenta adequada a você é a ferramenta certa para engenharia reversa.

Introdução à engenharia reversa: pirataria no formato de dados do jogo