Compressão
De ROMHackingWiki
| Este artigo é somente um esboço e seu conteúdo ainda pode ser melhorado. Você pode ajudar a ROMHackingWiki melhorando-o. |
| Este artigo necessita de uma revisão. Você pode ajudar a ROMHackingWiki revisando-o agora mesmo. |
| Este é um artigo avançado sobre o ROMHacking, leia-o com bastante atenção! |
Tabela de conteúdo |
Introdução
Algoritmos matemáticos que trabalham sobre a possibilidade de redução do tamanho de determinado conjunto de dados. Representam o conjunto de uma outra forma, mais reduzida. Pode perder alguma informação (compressão jpeg, mpeg layer 3, mpeg, etc) ou não perder nenhuma (RLE, LZ, FLACC, etc).
Objetivos
Seu principal uso está na redução do espaço utilizado. Imagine que um dia, o espaço se acabará e você precisará de mais espaço! Aqui, estamos tratando do armazenamento de dados em específico. A compressão é sua principal arma para "combater" essa situação.
Mas não é apenas de espaço que se trata a compressão, ela também ajuda você a planejar melhor suas estratégias! Lembrando a frase do general Shin Tzu: conquistar para dividir, cargas menores são mais fáceis e eficientes de manipular e de utilizar.
Como o enfoque aqui é ROMHacking, a compressão é importante porque todo o jogo (códigos, textos, imagens, vídeos, sons) deve caber na memória do cartucho, do CD, do DVD, etc.
Algoritmos de Compressão
Sem perda de dados
Compressão pelo uso tiles
Tile, aqui, se refere a um caractere, que é normalmente representado por um byte (um número de 0 a 255). Entretanto, nada impede que os algoritmos citados adiante sejam utilizados para comprimir gráficos ou qualquer outro tipo de dados.
Dual Tile Encode (DTE)
Codificação de Dupla de Tiles. O DTE é uma forma inteligente de ganhar espaço na ROM através da tabela de codificação de caracteres (ex: ASCII): em vez de um BYTE representar um único valor na tabela (uma letra, por exemplo), ele significa dois caracteres ou dois tiles. Essa forma é usada para aproveitar os valores excedentes de bytes.
Vamos supor um jogo em inglês. O alfabeto só precisa de 26 letras (em dobro para maiúsculas e minúsculas), mais alguns de pontuação (digamos que sejam quatro) e o espaço. Um byte pode ter 256 valores distintos, e cada byte representa um caractere. No entanto, só precisamos de usar a faixa de valores de 0 a (26)+(26)+(4)+(1)-1=55 [0,56]... Podemos, então, aproveitar os valores [57,255] para representar duplas de caracteres.
Exemplo:
00=os
01=as
02=ei
03=ba
04=be
05=bi
06=bo
07=bu
...
5F= (espaço)
...
68=h
69=i
6A=j
6B=k
6C=l
6D=m
6E=n
...
Então, o texto "minhas belas meias", que ocuparia 18 bytes (contém 18 letras), poderia utilizar essa tabela e ter seu comprimento reduzido para 13 bytes: (m, i, n, h, as, , be, l, as, , m, ei, as) = 6D 69 6E 68 01 5F 04 6C 01 5F 6D 02 01
Essa técnica foi muito utilizada nas traduções (oficiais e não-oficiais) de jogos em japonês para o inglês, devido ao fato de um texto em inglês ocupar muito mais espaço em bytes do que um em japonês.
Multiple Tile Encode (MTE)
Codificação Múltipla de Tiles. Parecido com o DTE, é apenas um ou mais BYTEs na tabela que apontam para muitos caracteres, palavras ou até frases inteiras! Se você entendeu o DTE, não há o que temer desta "variação"!
Exemplo:
00=bola
01=cachorro
AF02=inconstitucionalissimamente
FF03=Meu tio matou um cara!
...
Existem algumas ferramentas muito úteis para a manipulação de MTE's, especialmente focadas para tradutores que precisam modificar os valores de sua tabela para economizar espaço. Uma das mais utilizadas é a "MTE Optimizer", de autoria de Morpher, que pode ser encontrada neste link.
Há uma determinada confusão entre DTE/MTE e ponteiros por óbvias razões, já que a definição de ponteiro é muito EXTENSA e engloba tal situação!
Mas no romhacking, vamos colocar assim: ponteiros representam valores que são variáveis, como o nome de um personagem em um jogo de RPG que permite renomeá-lo, enquanto DTE/MTE representam constantes (valores da ROM)!
Run Length Encoding (RLE) e Variantes
Run Length Encoding, Codificação de Largura "Corrida". O RLE é, talvez, a compressão mais simples que você pode achar na sua vida! Basicamente, ela lida com a constante repetição de um determinado BYTE! Por exemplo: vendo tudo por um editor hexadecimal, geralmente, no final da ROM temos espaços "em branco", preenchidos por vários 0xFFs ou 0x00s!
| endereço | valores |
|---|---|
| 0xFFFFA0 | 0000000000000000 |
| 0xFFFFB0 | 0000000000000000 |
| 0xFFFFC0 | 0000000000000000 |
| ... | ... |
A funcionalidade do RLE está em diminuir o número desses BYTEs iguais guardados em seqüência, preservando espaço para dados mais importantes! Você raramente ou nunca vai encontrar RLE em jogos de CDs e DVDs, pelo óbvio motivo que eles tem espaço o suficiente para armazenar dados. Existem compressões baseadas na filosofia do RLE que lidam com seqüências complexas de BYTEs e não apenas um por vez, mas ainda assim seqüências!
Modelos de RLE
- RLE Simples - é o princípio fundamental discutido aqui, a constante repetição de um BYTE! Simplesmente, o caractere repetido mais o número de vezes que ele deve ser repetido. Vamos exemplificar em uma visualização dos dados, imaginando que tanto o caractere quanto o número de vezes esteja codificado em ASCII (1 BYTE por caractere):
| ORIGINAL | Número de BYTEs (ORIGINAL) | CODIFICADO | Número de BYTEs (CODIFICADO) |
|---|---|---|---|
| AA | 2 | A2 | 2 |
| AAAAAAAAAA | 10 | A10 | 3 |
| AAAAAAAAAAAAAAAAAAAA | 20 | A20 | 3 |
Como dá para perceber, quanto mais BYTEs iguais, menos BYTEs!
Lempel-Ziv e Variantes
Abraham Lempel e Jacob Ziv (Lempel-Ziv ou LZ) foram os criadores desse popular tipo de compressão, em 1977 (77!). A compressão Lempel-Ziv é denominada "compresão de texto utilizando um dicionário", onde o texto seria o código a ser comprimido e o dicionário é o que fará o texto ser comprimido e descomprimido. O formato básico da utilização deste dicionário seria lembrar onde está o texto repetido e quantos caracteres do mesmo jeito que visto mais a frente, em um arquivo, sendo o dicionário inicialmente implantado como um endereço que aponta para outro anterior do arquivo. Complicado?
Vamos verificar, no nosso arquivo A.BIN temos esta determinada seqüência de dados no endereço 0x00 (convenientemente escolhido): "AAAAAAAAAAAAA", estes dados são armazenados em um BUFFER (no nosso querido PC, a memória RAM como exemplo) e são comparados até se achar outro texto igual. A partir do endereço 0xFF, temos o seguinte texto: "AAAAAAAAAAAAA", opa! É o mesmo texto, então aí começa a compressão: o texto "AAAAAAAAAAAAA" poderia ser substituído por "0013", onde "00" seria o endereço onde o texto apareceu antes e "13" o tamanho do texto repetido em "00", nesse caso, o caractere "A"! Só lembrando mais uma vez, "13" é o numero de caracteres para contar a partir do endereço "00", e não o número de vezes repetido, para não confundir com RLE!
Essa é a idéia básica! Veremos agora um exemplo com seqüências complexas antes de entrarmos no dicionário.
Lempel-Ziv 77(LZ77)
...
Lempel-Ziv 78(LZ78)
...
Lempel-Ziv-Storer-Szymanski(LZSSzxwwere)
...
Lempel-Ziv-Welch(LZW)
...
Lempel-Ziv-Huffman(LZH)
...
Huffman
...
Shanon-Fano
...
Com perda de dados
Considerações Finais
...
