Engenharia reversa no GBA: Onde está o tilemap na ROM? — Parte 4
Essa postagem faz parte da série intitulada Engenharia Reversa num jogo de Gameboy Advance. Leia a introdução aqui. Leia a postagem anterior aqui.
Me siga no Twitter para acompanhar mais computarias 🐦
No capítulo anterior conseguimos localizar onde o tilemap é armazenado na Slow WRAM. Legal!
Mas de onde que ele provém os dados? Considerando que não há nenhuma outra “WRAM” a mais além da Slow e Fast, um bom palpite seria que a fonte de dados dela seria o próprio cartucho do jogo, isto é, a ROM!
Se essa hipótese se confirmar, isso seria especialmente importante e útil para nós, pois precisamos ter um arquivo com esses dados para plotar o tilemap na ferramenta. No caso, devemos extrair usando o IDA, pois, diferente do no$gba, o IDA tem uma feature que possibilita extrair para um arquivo os dados da memória.
Assim sendo, vamos continuar o fluxo que estávamos fazendo: partindo de B para encontrar a origem A! Os fluxos estão mais ou menos assim:
Filosoficamente falando, esse fluxo é infinito para ambos os lados. Poderíamos esticar à esquerda incluindo a eletrônica do cartucho ou o pensamento do level designer que projetou tal fase, assim como poderíamos esticar à direita com o jogador visualizando à fase. Porém, esse subset é o suficiente para o nosso caso.
Desse modo, precisamos localizar onde a fase é armazena na ROM — e entender de que modo é armazenada! Afinal, provavelmente ela deve estar comprimida, pois os desenvolvedores costumam comprimir os assets do jogo.
Conversando com alguns colegas, eles sempre diziam que seria um desafio lidar com a compressão do tilemap, pois eu precisaria, além de identificar onde está o tilemap comprimido, descobrir qual algoritmo de compressão foi usado, pois precisaria reproduzi-lo ao extrair o dado da ROM e também na ferramenta de edição de fases.
Bem… Mas o IDA mostra um interessante gráfico do uso da memória no cartucho, e algo que me chamou atenção foi que havia uma boa parte ociosa. Assim pensei “Opa, será que o tilemap nem estaria comprimido? Afinal, tem bastante armazenamento ocioso…”.
Para confirmar essa hipótese, copiei uma parte do tilemap que via no no$gba e fui pesquisá-lo na memória da ROM no IDA, usando a feature Sequence of bytes (Alt+B).
E infelizmente, não localizei. Bem, então ele realmente deve estar comprimido… e usando algum algoritmo de compressão que ainda não sei qual seria…
O mais perto que chegamos da fonte do tilemap é a Slow WRAM, e que os tiles daquela nossa ponte fica em 02008432. Okay, então vamos usar o nosso olhômetro para inferir onde começa o tilemap na Slow WRAM (tal como já explanei, um tilemap apresenta uma estrutura bem característica: é espaçado por vários zeros, apresenta um pequeno conjunto de bytes diferentes e vários bytes de mesmo valores repetidos em sequência). Com isso, deu para inferir que ele começa em 020039EB, ou em algum endereço próximo desse.
Assim, vamos continuar no nosso clássico e entediante debug step by step… Dessa vez precisamos começar uma fase no jogo e encontrar quando enfim o tilemap começa a ser escrito.
Efetuando isso, cheguei à importante instrução no endereço 08051440: swi 0x11. Logo após ela, uma parte do tilemap é escrito:
Lembra do swi? Eu já cheguei a falar brevemente dessa instrução anteriormente, e agora vou precisar explicá-la em mais detalhes, pois a usaremos bastante a partir de agora.
“swi” é a abreviação para software interrupts (que também é chamado de BIOS calls) — isso já da uma dica para que serve, certo?
O Gameboy Advance tem uma BIOS. Em termos de arquitetura de computares de um modo em geral, a BIOS é um firmware que tem como objetivo inicializar os componentes físicos do sistema da qual está vinculando, além de também mapeá-los ao sistema que operará o dispositivo.
Esses ditos “componentes físicos” podem ser, por exemplo, teclado e mouse. Porém, o dispositivo pode ser composto por outros hardwares mais especializados, que são expostos como “funções” para o sistema, sendo elas bem otimizadas, uma vez que estão bem próximas ao metal.
No caso do GBA, que é um hardware voltado para jogos, a BIOS expõe várias funções frequentemente usada em jogos, como controle da música e cálculo de arco tangente… e dentre essas funções expostas, também inclui compressão e descompressão de dados! Cada função tem um código numérico associado, da qual deve ser usado como parâmetro na instrução swi.
No caso, a instrução swi 0x11 expõe o algoritmo de descompressão lz77, que é muito útil quando há porções de dados repetidos (e em um tilemap nós temos exatamente isso!). É bem curioso pensar que o GBA, um console relativamente pequeno e barato, já tinha desde o começo dos anos 2000 poderosos algoritmos de compressão sendo executado a nível de hardware.
A forma para “passar parâmetros” e “obter o retorno da função” para as instruções swi é bem peculiar: basicamente, é a partir dos registradores. Veja um exemplo de como é na função div (swi 0x06):
Input:
- R0: numerador
- R1: denominador
Output:
- R0: numerador / denominador
- R1: numerador % denominador
- R2: abs(numerador / denominador)
Caso queira ter uma visão mais geral a respeito do swi, pode ler esse capítulo num manual do GBA.
Diante de toda essa explanação, vamos analisar aquela instrução que localizamos: swi 0x11
Conforme uma spec do GBA, 0x11 refere-se a LZ77UnCompWram.
O endereço de onde recolherá os dados que serão descomprimido é definido no R0, enquanto o retorno para onde escreverá o resultado é o endereço apontado por R1.
As peças do quebra-cabeça começa a se encaixar ao ver quais são os valores desses registradores logo antes de executar o swi 0x11:
O valor de R1 (o endereço de output da descompressão) é bem próximo do que havíamos dito que era o começo do tilemap, 020039CC de 020039EB!
Mas agora precisamos entender de onde veio o input dos dados, endereço apontado por R0: 0200F698…
Vendo o assembly, algo que me chamou bastante atenção foi a linha um pouco acima da swi 0x11, a instrução swi 0x13:
Vendo na spec, o swi 0x13 refere-se a HuffUnComp, tratando-se assim da descompressão usando por outro algoritmo: huffman. Ele também usa R0 como endereço de input e R1 como endereço de output.
E colocando um break point nele, veja só: ele escreve exatamente onde a outra instrução swi lerá logo depois! Além disso, ele pega os dados diretamente na ROM, no endereço 0x81B27FC!!
Ou seja: os desenvolvedores desse jogo decidiram comprimir a fase usando dois algoritmos de compressão, e entre a execução de um e do outro usa-se um buffer temporário.
Estudando e conversando com outras pessoas, a combinação do huffman e lz77 é algo bem popular. Enquanto o lz77 remove a recorrência numa porção de dados, o huffman reduz a quantidade de símbolos numa sequência proporcional à frequência dela. Essa resposta no Stack Overflow esclarece a razão dos desenvolvedores usarem ambas no jogo do Klonoa.
Inclusive, há um algoritmo bem popular que aborda exatamente o uso desses dois algoritmos em conjunto, o deflate. Esse algoritmo é usado em formatos de arquivos como o zip e png.
Okay. Então vamos para o endereço na ROM onde serve de fonte para descompressão do tilemap, isto é, o endereço 0x81B27FC.
Perceba que o IDA tem uma análise estática muito boa, tanto que basta deixar o cursor em uma das linhas do assembly, ou em um dos bytes do endereço quando está no modo Hex View, que ele já diz até onde vai esse dump de memória. E facilmente conseguimos extrair isso para um arquivo, usando a ferramenta Export data (shift+e)!
Mas não tem muita vantagem em só ter o binário com o tilemap comprimido, certo? Então precisamos arranjar uma forma de descomprimi-lo!
A primeira ideia que me veio em mente para realizar isso foi em buscar estudar os dois algoritmos de compressão utilizados… e… bem… fiquei tontin só de tentar entendê-los… e então imagina só quando for pra implementar essa porra toda?? E além disso, o GBA pode usar uma versão diferente de tais algoritmos, o que complicaria mais ainda…
E então pensei em uma ideia melhor: vamos usufruir de uma das maiores vantagens de estarmos desenvolvendo algo usando um console bem popular, a comunidade!
Então parti para pesquisar se alguém já havia desenvolvido algum projeto que fizesse a compressão/descompressão de dados usando os algoritmos do GBA… e veja só, não é que alguém já fez isso mesmo?
Um cara fez em 2011~2012 um código open source escrito em C com os diferentes algoritmos de compressão/descompressão do GBA, bastando passar o filepath do arquivo comprimido para um executável que ele será sobrescrito com a versão descomprimida dele. Fantástico, não? Então vamos usá-lo!
Precisamos reproduzir exatamente os mesmos passos feito no jogo: primeiro descomprimir usando o huffman, e depois usando o lz77.
Quando fui descomprimir o binário usando ./huffman.exe -d dump, recebi a mensagem “WARNING: unexpected end of encoded file!”… bem… nesse primeiro momento, apenas a ignorei, vamos em frente para ver no que dá.
Quando fui descomprimir o lz77, percebi que tinha vários executáveis correlatos: lze, lzss e lzx. Como fiquei meio em dúvida em qual seria o correto, testei a descompressão com todos, e só com o lzss deu certo (creio que seja lzss = lz seven-seven = lz77) usando o comando ./lzss.exe -d dump, mas novamente recebi aquele mesmo alerta: “WARNING: unexpected end of encoded file!”
Novamente recebi a mensagem dizendo que encontrou um fim inesperado… e vendo o arquivo com o resultado da descompressão, apesar de correto, estava incompleto: armazenava corretamente o começo do tilemap da fase, mas não a tinha completa.
Juntando esse fato com as mensagens de warning recebidas, fica bem claro que é porque está faltando mais dados para descomprimir, mas isso é estranho, pois eu havia extraído toda a porção que o IDA selecionava automaticamente!! Será que precisava extrair um pouco mais? Custa nada testar essa hipótese, então vamos lá!
Tal como já descrevi, ao colocar o breakpoint na instrução swi 0x11, conseguia ver quando começava a descomprimir o tilemap. E aqui vai um detalhe adicional: essa instrução era chamada mais de uma vez.
Então certamente havia mais um dump na ROM que precisávamos extrair. Então usei o IDA para extrair junto daquela região auto-selecionada em 0x81B27FC toda a porção auto-selecionada abaixo dela.
Extraindo essas duas regiões da memória, deu para rodar os executáveis da descompressão sem receber nenhum alerta!
E agora, comparando o binário com o que vejo na memória do no$gba, o tilemap está completamente extraído!!
Isso é completamente fantástico, pois agora conseguimos extrair da ROM o tilemap, além de entendermos como ele funciona!!! Agora estamos mais perto do que nunca de plotar o tilemap em nossa ferramenta de criar fases customizadas! Mas sempre lembre-se: tudo começou com uma pergunta bem singela, “como esticar essa ponte?”
Claro, ainda temos várias perguntas para responder, como por exemplo “temos um dump ‘linear’ da memória, então como vamos plotar o tilemap, que é um plano 2D?” e também uma pergunta bem mais óbvia de vim em mente, “de que maneira vamos plotar tudo isso?”.
Vamos responder todas essas perguntas no nosso próxima capítulo!
Próxima postagem: Faça-se o tilemap!
Fonte das imagens bases usadas na colagem do gráfico do fluxo:
- gameboy: unixtitan.net/explore/gameboy-vector-old/
- memória: flaticon.com/free-icon/ram_173754
- cartucho: iconfinder.com/icons/1531694/cart_cartridge_chip_game_nintendo_retro_snes_icon
