Programemos un juego en C (VI): Compresión de datos, cambios de base

---

Índice de entradas sobre programación de juegos en C

---

Exploremos ahora una técnica de compresión bastante sencilla de implementar y bastante eficiente en cuanto a ocupación, basada en los cambios de base de numeración.

En nuestro juego usaremos 7 elementos diferentes que son " ", "#", "$", "@", ".", "*" y "|". Si en lugar de representar cada uno con un carácter de 8 bits, usamos un número entero sin signo, para almacenar un número entre 0 y 6 solo necesitamos 3 bits, por lo que desaprovechamos 5 bits de cada byte realmente, eso es mas del 50%, un despilfarro. Hay dos técnicas que se usan habitualmente, el BDC y el cambio de base.

BDC es acrónico en inglés de Decimal Codificado en Binario, como con 4 bits podemos almacenar un número del 0 al 16, en este sistema se usan 4 bits para almacenar un solo dígito del 0 al 9, y cada byte almacena dos números en su interior, uno en los 4 bits superiores y otro en los inferiores. De esta forma para almacenar un número como el 78, como 7 en binario es 0111 y 8 es 1000, si los ponemos juntos formarían el número binario 01111000, y en un solo byte tenemos almacenados dos números de forma sencilla. El número almacenado se lee igual en hexadecimal que en decimal codificado en este formato, una ventaja del sistema en base 16.

Los procesadores suelen disponer de instrucciones adecuadas para manipular número en este formato y operar con ellos, y es muy sencillo mostrar estos dígitos en un display de 7 segmentos usando un chip codificador BDC.

Si usamos esta técnica, debemos convertir los datos a números, así asociamos un número a cada elemento, por ejemplo: 0 = " ", 1 = "#", 2 = "$", 3 = "@", 4 = ".", 5 = "*", 6 = "|".

Mediante un programa debemos convertir las cadenas de caracteres con los datos a BDC, e ir almacenándolas en variables enteras sin signo de 8 bits, para eso en C se usa el tipo unsigned char, lo mejor es hacer un programa para convertirlo, es sencillo y práctico. Si en un nivel al final hay un número impar de dígitos, rellenamos con un cero al final, que no hará nada. Los dos primeros niveles del juego quedarían así en hexadecimal, que el C puede tratar directamente sin problemas:

00h,00h,11h,11h,16h,00h,00h,10h,00h,16h,00h,00h,12h,00h,16h,
00h,11h,10h,02h,11h,60h,01h,00h,20h,20h,16h,11h,10h,10h,11h,
01h,00h,01h,11h,11h,16h,10h,00h,10h,11h,01h,11h,11h,00h,44h,
16h,10h,20h,02h,00h,00h,00h,00h,00h,44h,16h,11h,11h,10h,11h,
10h,13h,11h,00h,44h,16h,00h,00h,10h,00h,00h,11h,11h,11h,11h,
16h,00h,00h,11h,11h,11h,16h 

11h,11h,11h,11h,11h,11h,61h,44h,00h,10h,00h,00h,11h,16h,14h,
40h,01h,02h,00h,20h,01h,61h,44h,00h,12h,11h,11h,00h,16h,14h,
40h,00h,03h,01h,10h,01h,61h,44h,00h,10h,10h,02h,01h,16h,11h,
11h,11h,01h,12h,02h,01h,60h,01h,02h,00h,20h,20h,20h,16h,00h,
10h,00h,01h,00h,00h,01h,60h,01h,11h,11h,11h,11h,11h,16h

Solo de esta sencilla manera hemos conseguir reducir a la mitad la ocupación de los 10.492 bytes que teníamos ya sin espacios no necesarios, y dejarlos en 5.246 bytes.

Pero analizando los datos hay una posible mejora, para almacenar un valor del 0 al 7 solo hacen falta 3 bits, con lo que en un byte puedo almacenar dos números y dos tercios, casi tres, una pena que nos falte solo un bit, pero si ese bit fuera siempre cero o uno ya no hace falta que lo almacenemos. Usaremos un pequeño truco, sabemos que la mayoría de los valores a almacenar son huecos o paredes, si le asignamos un número bajo la mayoría de las veces los elementos comenzarán siempre por cero.

Como tenemos 8 posibles valores con 3 bits y usamos 7, vamos a poner en marcha un truco. Los valores que vamos a almacenar van a ser 8, añadimos uno nulo que representa que es un hueco a saltarse, por lo que cuando decodificamos ese valor cero nos lo saltamos directamente. Ese valor lo usaremos solo cuando tengamos que almacenar un elemento en la posición alta del byte cuyo primer bit deba ser un uno. De esta forma aunque el 90% de las veces no hace falta, por poner una cifra diré que solo el 50% de las veces lo uso, por lo que el otro 50% de las veces almacenaré un tercer valor en un byte, o lo que es lo mismo guardo 2.5 valores en cada byte, y reduzco los 10.492 bytes a ocupar solo entre 4.197 y 3.617 bytes, la ganancia es muy grande.

Codificamos así los elementos ahora 0 = nulo, 1 = " ", 2 = "#",  3 = "$", 4 = ".", 5 = "*", 6 = "|", 7 = "@" y codifico de binario, presento los dos primeros niveles e este formato, agrupo de tres en tres y destaco los ceros añadidos cuando un grupo empieza por uno o para completar los bytes. De los 310 caracteres codificados hemos añadido 14, un cuatro y medio por ciento.

001 001 001 - 001 010 010 - 010 010 010 - 000 110 001 - 001 001 001
010 001 001 - 001 010 110 - 001 001 001 - 001 010 011 - 001 001 010
000 110 001 - 001 010 010 - 010 001 001 - 011 010 010 - 000 110 001
001 010 001 - 001 011 001 - 011 001 010 - 000 110 010 - 010 010 001
010 001 010 - 010 001 010 - 001 001 001 - 010 010 010 - 010 010 010
000 110 010 - 001 001 001 - 010 001 010 - 010 001 010 - 010 010 010
010 001 001 - 000 100 100 - 010 110 010 - 001 011 001 - 001 011 001
001 001 001 - 001 001 001 - 001 001 001 - 000 100 100 - 010 110 010
010 010 010 - 010 001 010 - 010 010 001 - 010 111 010 - 010 001 001
000 100 100 - 010 110 001 - 001 001 001 - 010 001 001 - 001 001 001
010 010 010 - 010 010 010 - 010 010 010 - 000 110 001 - 001 001 001
010 010 010 - 010 010 010 - 010 000 000

010 010 010 - 010 010 010 - 010 010 010 - 010 010 010 - 000 110 010
000 100 100 - 001 001 010 - 001 001 001 - 001 001 010 - 010 010 110
010 100 100 - 001 001 010 - 001 011 001 - 001 011 001 - 001 010 110
010 100 100 - 001 001 010 - 011 010 010 - 010 010 001 - 001 010 110
010 100 100 - 001 001 001 - 001 111 001 - 010 010 001 - 001 010 110
010 100 100 - 001 001 010 - 001 010 001 - 001 011 001 - 010 010 110
010 010 010 - 010 010 010 - 001 010 010 - 011 001 011 - 001 010 110
001 001 010 - 001 011 001 - 001 011 001 - 011 001 011 - 001 010 110
001 001 010 - 001 001 001 - 001 010 001 - 001 001 001 - 001 010 110
001 001 010 - 010 010 010 - 010 010 010 - 010 010 010 - 010 010 000

Pasando los valores a decimal nos queda esta codificación:

73, 82, 146, 49, 73, 137, 86, 73, 83, 74, 49, 82, 137, 210, 49, 81, 89, 74, 50, 145, 138, 138, 73, 146, 146, 50, 73, 138, 138, 146, 137, 36, 178, 89, 89, 73, 73, 73, 36, 178, 146, 138, 145, 186, 137, 36, 177, 73, 137, 73, 146, 146, 146, 49, 73, 146, 146, 128

146, 146, 146, 146, 50, 36, 74, 73, 74, 150, 164, 74, 89, 89, 86, 164, 74, 210, 145, 86, 164, 73, 121, 145, 86, 164, 74, 81, 89, 150, 146, 146, 82, 203, 86, 74, 89, 89, 203, 86, 74, 73, 81, 73, 86, 74, 146, 146, 146, 144

El otro sistema sencillo de codificación es el cambio de base. Un número cualquiera lo podemos escribir como potencias de 10, así el 5.246₁₀ sería 5.10³ + 2.10² + 4.10¹ + 6.10⁰. De igual manera podemos escribir un número en base 7, cambiando el 10 por un 7. Si entendemos la lógica del sistema, veremos que en base 7 podemos escribir el número 546₇ sería 5.7² + 4.7¹ + 6.7⁰ = 279₁₀


El sistema seria convertir los números que vamos obteniendo a base 7, e ir montándolos en un número entero sin signo. si usamos dos bytes podemos almacenar 5 números en base 7 en su interior, contra el sistema BDC que almacenábamos solo 4. Un poco mas, pero los 10.492 bytes de partida quedan como 4.197 bytes, ganamos casi 1K con este sistema. Pasar de uno a otro es cuestión de multiplicar y dividir nada mas, lo malo de este sistema es que las divisiones  son operaciones lentas para los ordenadores, por lo que aunque es un buen y sencillo sistema, en nuestro caso no es el mas recomendable tampoco.