[Notas Romhacking] Compresión de Golomb-Rice de 4 bits

En este artículo documentaré como funciona la codificación de Golomb, esto se hace con la intención de compartir conocimientos con la comunidad de romhack hispana.

Esta codificación se hace presente de la desarrolladora Imagineering Inc. específicamente en los siguientes títulos de NES:

• Barbie
• Home Alone 2
• Ren & Stimpy Show, The
• Simpsons Bart vs Space Mutants
• Simpsons Bart vs The World
• Simpsons Bartman Meet Radiactive Man

Para entender como funciona primero debemos entender la diferencia entre 1 byte y 1 bit. Recordemos un 1 byte esta conformado por una cadena binaria conformada por 8 bits, tal y como muestra la imágen de abajo.

Si ocupamos las mates, con potencias de 2 tenemos que 2^8 = 256 combinaciones, y los bytes pueden representarse en formato hexagecimal del 0x00 al 0xFF.

Bien para la codificación de estos juegos se han ocupado 4 bits, osea la mitad de un byte, si ocupamos mates nuevamente, 2^4 = 16 combinaciones, no es mucho, ya que el alfabeto consta de 26 letras (sin contar caracteres de puntuación, etc), sin embargo como solución podemos sacrificar un espacio y asignarle un "byte flag", de esta manera podemos crear otro alfabeto de 16 espacios, y cuantos queramos sacrificando siempre un espacio en el primer diccionario.

Para ver esto de mejor forma tomare como ejemplo el juego: "The Ren & Stimpy Show - Buckeroo$!" de NES. Si analizamos su tabla de caracteres (char map):

Como podemos ver en la imágen en la parte seleccionada, este juego ocupa 49 caracteres, a su derecha los tenemos en ASCII. Bien si hacemos los calculos: 49 / 16 = 3,0625, (aproximamos al entero siguiente) o sea necesitaremos 4 diccionarios para poder llenar todos los caracteres. Ahora, ¿cuántos caracteres caén en el primer diccionario?, Si pensaste en 13 estas en lo correcto, pues debemos sacrificar 3 espacio para ocuparlos como flag para apuntar a los otros diccionarios.

La siguiente tabla resume lo anterior:

Algo importante de mencionar es que orden de los caracteres están basado es su frecuencia de aparición, lo que quiere decir que los caracteres de la columna 0 seŕan los que tienen mayor probabilidad de aparecer y por lo tanto al no requerir de un "flag" ocuparan solo 4 bits , por el contrario los de la demas columnas( 1, 2 y 3) ocuparán 8 bits.

Ahora solo debemos encontrar donde esta el texto(no explicaré esto aquí) y tomar todos los valores hexagecimales y dividirlos en 2 partes cada byte, por ejemplo el byte "D0", nos quedaría "D" y "0", si lo pasamos a decimal "13" "0", a esto se le llamarán "nybbles", y abajo tenemos un extracto del texto en nybbles.

Ahora, solo debemos interpretar lo números como si fueran coordenadas, y ocupar la tabla de más arriba, recuerden ocuparemos por defecto la fila 0, si es que llegamos a un flag, cambiamos de diccionario y  ocupamos el "nybble" siguiente, para ejemplificar mejor ocuparemos la región que está encerrada.

5 = N, 6 = I,

13 (flag para ir al diccionario 1) -> 0 = C, 

13 (flag para ir al diccionario 1) -> 12 = K,

1 = E, 12 = L, 2 = O, 10 = D, 1 = E, 2 = O , 5 = N, 11 = {0D}

Así nos queda la cadena de texto:

NICKELODEON{0D}

Bien, ya decodificamos el texto, y esto corresponde a la intro del juego, la primera línea específicamente:

Ahora, solo queda hacer una herramienta que haga esto automáticamente, y bueno hacer lo contrario, osea comprimir de texto, para eso debemos también crear nuevos diccionarios, basados en la frecuencia de aparición de cada caracter, para comprimir con la misma eficacia. Y por último y no menos importante manejar los punteros de los textos.

Herramienta disponible aquí.

Hasta pronto en otra nota de romhacking.