Compressão LZSS (Bahamut Lagoon)

Bom, vamos tentar compreender a compressão LZSS do jogo Bahamut Lagoon, vejamos se consigo explicar.

INDICADORES

Comecemos com a imagem do começo do texto do jogo, onde você pode ver também o Offset  do  inicio do texto no jogo,  eu aconselho  que  tenha um  editor  hexadecimal aberto e vá olhando nele enquanto explico.
Bem, se você olhar a palavra Prologue no editor, ela aparece como Pr<80>ologue, este byte que nós encontramos no meio do texto não modifica em nada o texto (Como você pode observar na imagem do jogo)  vamos chamá-lo de indicador. Não sei se o nome técnico realmente é esse, mas vou me referir a ele com esse nome.


O que o indicador faz é indicar, o que vem a frente, que é o texto sem compressão e onde há um ponteiro LZSS, que é o texto comprimido.

E como isso nos “indica”? Pois bem, se passarmos esse byte, <80> para binário com a calculadora do Windows, teremos:
80 em hexadecimal = 10000000 bits (em binário)

Lembre-se que um byte são 8 bits, se a calculadora nos mostrar “1001”, para nós será “00001001”, digamos que tem 8 dígitos.
Pois bem, temos que ler esse número da direita para a esquerda, de modo que inicialmente temos 7 zeros e depois um 1, isso quer dizer que os 7 bytes seguintes são letras sem compressão e o oitavo byte é um ponteiro LZSS. Vamos ao editor para contarmos e comprovarmos.

O sétimo byte é como se fosse texto, em concreto é o pulo de linha, mas não é nenhum ponteiro ou algo por do tipo.

IMPORTANTE: Os ponteiros LZSS apesar de serem de dois bytes, são registrados como se fossem apenas um!

Logo abaixo explicaremos como funciona um ponteiro LZSS, antes vamos compreender sobre os indicadores.

Bem, a cada 8 bytes, SEMPRE, haverá um indicador para saber se os 8 bytes seguintes são textos descomprimidos ou ponteiro LZSS.

Se você olhar, depois do oitavo byte, verá outro indicador, neste caso é o <00>. Se o passarmos para binário será 00000000. Ou seja, os 8 bytes seguintes são textos descomprimidos, sem nenhum ponteiro. Vejamos:

Viu? A cada 8 bytes há um indicador que diz que o que vem em seguida.


PONTEROS LZSS

Bem, agora vamos explicar o que são ponteiros LZSS. O primeiro ponteiro LZSS que nós encontramos não é um bom exemplo para se explicar, é que ele aponta para antes de onde começa o texto, embora sua função seja a mesma, a única coisa que ele faz é copiar alguns “espaços” seguidos para manter centralizada a palavra Prologue no jogo. Vamos para o ponteiro seguinte, como sabemos que á um ponteiro? Porque nos indica o indicador “xD”, se continuarmos por onde estávamos antes…
O indicador <02> passado para binário é “00000010”,  mas lembre-se que deve  lê-lo da direita para esquerda, portanto há um primeiro byte que é o texto e em seguida um ponteiro LZSS que embora seja composto por dois bytes, deve ser considerado como se fosse apenas um, em seguida outros 6 bytes de texto para o próximo indicador. Agora vamos analisar esse ponteiro LZSS.
Onde deveria aparecer (segundo o jogo) "King Kahna" aparecem esses códigos no editor hexadecimal:

Kin<02>g<12><30>:

Já sabemos o que o indicador faz. Agora os dois bytes do ponteiro LZSS possuem a seguinte função:

O primeiro <12> faz referencia a quantos bytes para trás deve-se retornar para buscar o texto que indica esse ponteiro, 12 em hexadecimal,  passaremos para decimal para poder contar com maior facilidade  são 18 em decimal, a partir do ponteiro <12> contaremos para trás 18 bytes. MAS É IMPORTANTE TER EM MENTE: Que quando se conta para trás não se contam os indicadores que estão no meio das palavras e sim devemos ignorar os ponteiros LZSS, contando como se o texto já estivesse descomprimido! Vamos comprovar:
Bem, chegamos a posição correta, o que deve ser copiado com o ponteiro LZSS para que seja coerente com o que aparece no jogo é “_Kahna”. Mas como sabemos quantas letras devem ser copiadas? Porque tem que copiar 6 e não 8?
Bem, essa indicação é dada pelo segundo byte do ponteiro LZSS.


O segundo byte do ponteiro LZSS <30> deve-se inverter os caracteres do byte, ou seja, se temos <30> inverteremos para <03> que se convertermos para decimal será “3”.
IMPORTANTE: A este valor que obtivemos, temos SEMPRE que somar +3. Por quê? Porque se um texto for menor que 3 caracteres, não tem sentido fazer a compressão, bastava escrever o texto diretamente e pronto.
Então temos 3 + 3 = 6, iremos copiar o byte em que nós posicionamos (O marcado com 18 na figura) e os 5 seguintes, 6 no total. É como se estivéssemos copiando apenas “_Kahna” que efetivamente é o que irá aparecer.


COM ISTO, JÁ SABEMOS TUDO, MAS VAMOS FAZER UM EXEMPLO MAIS COMPLEXO PARA QUE NÃO SOBRE DÚVIDAS.

Agora vamos a um ponteiro que aparece um pouco mais adiante. Aqui não irei explicar tanto, tente compreender com o que eu já havia explicado anteriormente.

O ponteiro LZSS <71><70>

<71> => buscará texto 113 (O “113” esta em decimal e o 71 esta em hexadecimal) bytes para trás, saltando os indicadores (assinalados em azul) e contando os ponteiros LZSS como se estivessem descomprimidos, ou seja, se o segundo byte do ponteiro fosse <20>, invertendo teríamos 02 bytes e somando +3 teríamos 5 bytes ( <20> (inverte)  <02> = 2 +3 = 5 )

<70> => Copiará 10 bytes (<70> (inverte) <07> = 7 + 3 = 10)
Se você fizer com atenção comprovará que o primeiro ponteiro marca o primeiro espaço de “_of_Kahna_” e o segundo ponteiro dirá para copiar 10 bytes, esses 10 bytes são contados igual aos outros, pulando os indicadores e considerando os ponteiros LZSS que encontra pelo caminho como texto já descomprimido.

AGRADECIMENTOS: Este tutorial não teria sido possível se não fosse a ajuda vinda de SkyBladeCloud, que me ajudou a compreender a compressão deste jogo.

Créditos:
Autor: Darke (Cena Hispânica)
Grupo: Nenhum
Tradução: Quil
Grupo: Nintendo BR
Observações: --