Compresión y Descompresión RLE

Como ya sabemos, la memoria disponible para datos en el Spectrum es bastante limitada. A los 48KB de memoria base (si no usamos la técnica de paginación de memoria de los modelos de 128KB) hay que restarles los casi 7KB de la VideoRAM (el área de memoria que representa lo que vemos en pantalla), el espacio de pila y, finalmente, el espacio ocupado por nuestro programa (el código binario del mismo). El resultado de esta operación nos dejará con una cantidad determinada de memoria en la que deben entrar los datos del programa (gráficos, sonidos, músicas, tablas, áreas temporales, etc).

Ante esta tesitura, no nos queda otro remedio que aprovechar al límite el espacio disponible, y una de las formas de hacerlo es mediante compresión de datos.

La compresión sin pérdida de datos consiste en coger unos datos de un determinado tamaño (gráficos, sonido, una pantalla de carga, etc) y aplicarle un algoritmo que produzca como salida unos datos de un tamaño menor que el inicial. Estos datos resultantes deben de permitir obtener a partir de ellos, aplicando una transformación a los mismos en tiempo real, los datos iniciales.

Este proceso de compresión lo realizamos durante el desarrollo de nuestra aplicación o programa (por ejemplo, en un PC), y utilizamos los “datos comprimidos” directamente en nuestro programa en lugar de utilizar los “datos en crudo” o descomprimidos.

El resultado es, por ejemplo, que una pantalla gráfica de 7KB se reduzca a 2KB dentro de nuestro “ejecutable”, y que podamos “descomprimirla” al vuelo sobre la VideoRAM desde los datos comprimidos. De esta manera, ahorramos 5KB de memoria en una única pantalla.

En resumen:

• Proceso de compresión:
  
  Datos (7KB) → COMPRESION EN PC → Datos_comprimidos (2KB)

• Proceso de descompresión:
  
  Datos_comprimidos (2KB) → DESCOMPRESION AL VUELO → Datos (7KB).

Los procesos de COMPRESION y DESCOMPRESION son funciones que reciben como entrada los datos en crudo o los datos comprimidos (respectivamente) y producen como salida los datos comprimidos o los datos originales.

Hay infinidad de algoritmos de compresión, es decir, una gran variedad de transformaciones diferentes sobre los datos originales y que producen datos comprimidos. En este capítulo veremos la compresión RLE, una de las más básicas y que produce excelentes resultados con determinados tipos de datos (por ejemplo, los gráficos que cumplan unas ciertas condiciones).

La compresión RLE o Run Lenght Encoding se basa en la sustitución de elementos repetidos por “comandos” que indican que un elemento está repetido, y cuántas veces lo está.

Lo que haremos será sustituir secuencias consecutivas de bytes por “bytes de repetición” seguidos del byte a repetir.

Supongamos la siguiente secuencia de datos:

1, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 5, 6

Esta serie de 20 dígitos nos ocuparía en memoria 20 bytes. Pero si nos fijamos adecuadamente en los datos repetidos, es posible comprimirla como la siguiente secuencia:

1, 2, 0, 3, "12 CEROS", 3, 4, 5, 6

Es decir, si sustituimos los doce ceros consecutivos por algún tipo de marcador que indique “esto son doce ceros”, podemos ahorrar mucha memoria.

Un primer vistazo al problema podría sugerir el siguiente flujo de datos comprimidos:

1, 2, 0, 3, 12, 0, 3, 4, 5, 6

En este ejemplo, el 12 previo al cero nos indicaría que debemos repetir el cero un total de doce veces. Pero … ¿cómo distinguirá nuestra rutina descompresora si ese número 12 es un dato en sí mismo o un indicador de repetición? La respuesta es, no puede saberlo, a menos que marquemos ese 12 de alguna forma especial. Debemos pues determinar un marcador para que nuestro descompresor distinga los “datos” de los “bytes de repetición”.

1, 2, 0, 3, *12*, 0, 3, 4, 5, 6

Ahora bien … ¿qué tipo de marcador podemos utilizar?

En el algoritmo RLE se utilizan como marcadores de repetición los 2 bits superiores del dato. Estos bits, el número 7 y el número 6, tienen el siguiente valor:

Bit 7 + Bit 6 = 128 + 64 = 192.

Así pues, nuestro “comando de repetición” será cualquier byte que tenga los bits 6 y 7 activos (con valor mayor o igual que 192). Los bits del 0 al 5 nos indicará el número de veces que representa al elemento repetido.

Por ejemplo, en nuestro bloque de datos anterior:

1, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 5, 6

Si sustituimos los 12 ceros por su “byte repetidor” seguido del dato a repetir, quedaría:

1, 2, 0, 3, 204, 0, 3, 4, 5, 6

¿De dónde ha salido ese 204? Pues es “192+12”, es decir, es un byte que tiene activos los bits 6 y 7 y que en los bits 0 a 5 contiene el valor “12” (el número de repeticiones). Y al dato 204 le sigue el “0”, que es el dato que hay que repetir 12 veces.

Nótese que nuestros datos en crudo ocupaban 20 bytes, y los datos comprimidos ocupan sólo 10 bytes. Es una compresión del 50%. Si todos nuestros datos fueran de características similares, podríamos poner en nuestro programa o juego el doble de niveles, de gráficos o de músicas. Obviamente no todos los bloques de datos son susceptibles de ser comprimidos, pero la mayoría de gráficos, por ejemplo, lo son. Y poder meter más datos en nuestro programa es algo que agradeceremos en muchas ocasiones.

Estos datos comprimidos (y no los originales) serían los que incluiríamos en nuestro programa, así:

Datos_comprimidos:
                    DEFB 1, 2, 0, 3, 204, 0, 3, 4, 5, 6

Después, nuestro programa debería ser capaz de descomprimirlos allá donde vayamos a usarlos, es decir, coger los datos comprimidos, y desempaquetarlos obteniendo los datos originales previos a la compresión. La descompresión puede hacerse nada más arrancar el programa (sobre bancos de memoria, zonas de trabajo, etc), o directamente en el momento de necesitarlos (intros, pantallas finales de juegos, etc).

Para la descompresión sólo tenemos que asegurarnos de, byte a byte, copiar los datos “normales” y de “repetir N veces” los datos comprimidos RLE. Distinguiremos los datos “comprimidos” porque son mayores de 192 (tienen los bits 6 y 7 activos).

Así, la rutina de descompresión se basaría en:

  * Desde I=0 hasta LONGITUD_DATOS
     * DATO = Datos[i]
     * Si dato < 192   -> Es un dato normal
         * A datos_comprimidos añado "dato".
     * Si dato >= 192  -> Es un dato comprimido
         * Repeticiones = dato - 192
         * Dato_Real = al siguiente valor a Dato[i]
         * A datos_comprimidos añado "Repeticiones" veces Dato_Real
  * Fin_Desde

En el ejemplo anterior, la rutina de descompresión leería datos uno a uno y vería:

Comprimido = (1, 2, 0, 3, 204, 0, 3, 4, 5, 6)
Descomprimido = (vacío inicialmente)

• 1 → (<192) = No está comprimido
  → El 1 lo copio en Descomprimido.

• 2 → (<192) = No está comprimido
  → El 2 lo copio en Descomprimido.

• 0 → (<192) = No está comprimido
  → El 0 lo copio en Descomprimido.

• 3 → (<192) = No está comprimido
  → El 3 lo copio en Descomprimido.

• 204 → (>=192) = Sí está comprimido
  → Calculo REPETICIONES = 204-192 = 12
  → Leo el siguiente dato (un 0).
  → Copio a “Descomprimido” 12 ceros.

• 0 → (<192) = No está comprimido
  → El 0 lo copio en Descomprimido.

• 3 → (<192) = No está comprimido
  → El 3 lo copio en Descomprimido.

• 4 → (<192) = No está comprimido
  → El 4 lo copio en Descomprimido.

• 5 → (<192) = No está comprimido
  → El 5 lo copio en Descomprimido.

• 6 → (<192) = No está comprimido
  → El 6 lo copio en Descomprimido.

Nótese que dado que utilizamos los bits 0 al 5 para indicar el número de repeticiones (puesto que el 6 y el 7 son marcadores RLE), eso quiere decir que un dato “comprimido” sólo puede representar un máximo de 63 repeticiones.

O, lo que es lo mismo, que 63 ceros seguidos se codificarían como 255, 0 (ya que 255-192 son 63).

Si tuvieramos que codificar 70 ceros, sería mediante 2 bloques RLE, es decir, codificaríamos 63 ceros en un conjunto RLE, y los 7 restantes en otro:

255, 0, 199, 0

La pregunta es … ¿qué pasa si nos encontramos con datos REALES en el array a comprimir que sean ya de por sí (sin ser bytes de repetición) de valor 192 o superior?

Supongamos el siguiente flujo de datos:

0, 1, 200, 2

El valor 193 es, por sí mismo, un valor RLE (>=192), por lo que debemos encontrar una forma de indicar a nuestra rutina descompresora que ese dato no es un dato comprimido, para evitar que (en el ejemplo anterior), repita el siguiente valor, el 2, un total de 8 veces (200-192).

La solución es muy sencilla: cuando realicemos la compresión, codificaremos los valores mayores o iguales de 192 como un bloque RLE de longitud uno:

0, 1, 200, 2     ->   0, 1, 193, 200, 2

Nótese cómo se ha codificado el valor 200 como un RLE de 2 bytes: 193, 200. Esto implica, en nuestra rutina de compresión, que los datos comprimidos han acabado ocupando 1 byte más que los originales.

El aumento del tamaño de los datos comprimidos sólo ocurre cuando el dato a comprimir es mayor que 192, y además no está repetido, ya que si está repetido también nos beneficiaremos de la compresión RLE:

0, 1, 200, 200, 200, 200, 200, 200, 200, 2    ->   0, 1, 199, 200, 2

En el ejemplo anterior, los 7 datos 200 se han codificado como 199, 200, pasando de ocupar 7 bytes a ocupar 2.

Es decir, sólo perderemos ratio de compresión en aquellos datos que sean mayores que 192 y que no estén repetidos de forma consecutiva. En el resto de casos nos mantendremos iguales (si no hay repeticiones) o ganaremos espacio (en el caso de las repeticiones).

Obviamente, hay que seleccionar el mejor tipo de compresión para nuestros datos. La compresión RLE vendrá muy bien, por ejemplo, para todas aquellas imágenes que tengan muchos colores iguales repetidos (imágenes rellenadas con colores planos, por ejemplo), pero será nefasta en imágenes con mucha variación entre cada pixel y el siguiente, si éstos valores son mayores o iguales que 192.

En una imagen de pantalla de Spectrum (aprox. 7KB) que tenga bastantes colores planos, podemos pasar a obtener ratios de compresión que dejen la imagen comprimida en 2-3KB o a veces incluso menos. Las fuentes de letras y los sprites también son en ocasiones buenos candidatos para la compresión.

Obviamente, podemos provocar mejoras en la compresión a la hora de diseñar las pantallas… si el dibujar una determinada zona con un color de tinta o papel determinado produce valores mayores que 192, basta con dibujar la misma zona invirtiendo la tinta y el papel (y los valores de los bits) para que esa zona no produzca valores de compresión RLE.

Eso quiere decir que un bloque de 8 píxeles de valor 1111000 sin repetición se convertirá en 2 bytes (el 193 de repetición, por ser mayor de 192, seguido de 1111000). Pero si invertimos tinta y papel en ese recuadro y lo dibujamos como 00001111 ya no se producirán 2 bytes por este dato a comprimir.

Nada nos impide tampoco el comprimir aquello que produzca un buen ahorro, y dejar sin comprimir lo que no.

Antes de ver el pseudocódigo y las rutinas descompresoras y compresoras, vamos a resumir lo visto hasta ahora.

• La compresión es un proceso que convierte una serie de datos de tamaño N en otra serie de datos de tamaño M (siendo M menor que N), mediante un determinado algoritmo de procesado de los datos originales.

• Los datos a comprimir pueden ser cualquier tipo: una pantalla de imagen de 6912 bytes, un sprite o conjunto de sprites, música… En general se puede comprimir cualquier cosa que se pueda representar como una “ristra” de bytes (es decir, todo).

• El algoritmo de compresión sin pérdida es un mecanismo de transformación de los datos que debe ser reversible. Es decir, a partir de los datos comprimidos debemos ser capaces de obtener los datos originales.

• El ratio de compresión nos indica el ahorro de memoria obtenido. Si una secuencia de 2000 bytes se comprime en 1000 bytes, diremos que hemos obtenido un ratio de compresión del 50%. El ratio de compresión variará según los datos a comprimir y el algoritmo de compresión empleado. En el caso de RLE, obtendremos grandes ratios de compresión con series de datos que contengan muchos valores repetidos y malos ratios con datos que contengan muchos valores mayores de 192 sin repeticiones.

• La descompresión es un proceso que obtiene, desde los datos comprimidos, la secuencia de datos originales, mediante un determinado algoritmo de procesado.

• El algoritmo de descompresión es el mecanismo de transformación de los datos comprimidos que nos permite obtener los datos originales.

• La compresión RLE es un algoritmo de compresión basado en la repetición de los datos. Consiste en agrupar los datos consecutivos repetidos mediante un “marcador RLE” que indica el número de repeticiones del siguiente dato de la secuencia.

• La descompresión RLE es un algoritmo de descompresión que, a partir de unos datos comprimidos con RLE, obtiene los datos originales mediante la “expansión” de los datos “de repetición” formados por “Marcador RLE con número de repeticiones”, y “Dato a repetir”.

A continuación vamos a ver el pseudocódigo y funciones ensamblador y C de descompresión RLE y compresión RLE. Pero antes, es importante destacar la forma en que usaremos estas funciones:

• Compresión: La compresión RLE de los datos (imágenes, sonido, o cualquier otro tipo de datos) se realiza en nuestro PC. Es decir, cogeremos un .SCR con una pantalla de 6912 bytes, o un .BIN con los datos gráficos de un Sprite (o cualquier otro tipo de datos), y los comprimiremos con un programa que nos dará como salida un fichero binario de datos comprimidos de (generalmente) mucho menor tamaño que el original. El programa compresor no es, pues, un programa para Spectrum, sino para el sistema en que estamos desarrollando de forma cruzada el juego. Así pues, la rutina de compresión la programaremos (o la descargaréis) en C o como fichero ejecutable para Windows, MAC o Linux.

• Inclusión de los datos: Los datos resultantes de la compresión serán los que incluiremos en nuestro programa, en lugar de los originales. Es decir, nuestra pantalla de fondo ya no serán los 6912 bytes del .SCR original sino los (por ejemplo) 3102 bytes resultantes de la compresión. Los datos los incluiremos con la directiva INCBIN de pasmo, o bien convirtiéndolos a ristras de bytes con bin2code o similar.

• Descompresión de los datos: La descompresión de los datos la realizamos en nuestro programa de Spectrum, mediante una rutina programada en ensamblador de Z80 o C para Z88DK. La rutina es pequeña y rápida, por lo que nos permitirá desempaquetar nuestra pantalla de 3102 bytes directamente sobre la VideoRAM (por ejemplo). Los 3102 bytes de nuestra pantalla de ejemplo, expandidos, serán los 6912 bytes originales del SCR inicial. Se dice pues que la rutina de descompresión trabaja al vuelo o en tiempo real.

La rutina descompresora de RLE debe recibir como parámetros los siguientes valores:

• Los datos comprimidos con RLE a descomprimir: Los recibiremos en forma de “puntero” o “dirección de memoria” apuntando al principio de los datos.
• El tamaño de los datos comprimidos (necesario para el bucle de descompresión).
• Un puntero o dirección de memoria apuntando a dónde queremos descomprimir los datos.

La rutina deberá ir cogiendo cada byte del bloque de datos comprimido y decidir si es un dato “sin comprimir” (<192) o un dato comprimido (>=192). Si es un dato sin comprimir lo copiará a la dirección de memoria destino, y si está comprimido cogerá el siguiente byte y decidirá cuántas veces debe repetirlo.

Por ejemplo:

Así pues, nuestra rutina de descompresión debe hacer lo siguiente:

  M = 0
  N = 0
  Desde N=0 hasta N=TAMAÑO_DATOS_COMPRIMIDOS

    Cogemos valor=Comprimidos[N]
    N = N + 1

    # Si no es un dato comprimido, simplemente lo copiamos
    Si valor < 192 
    Entonces
       Descomprimidos[M] = valor
       M = M + 1
    Fin Si

    # Si es un dato comprimido, lo descomprimimos:
    Si valor >= 192 
    Entonces
       repeticiones = valor - 192
       dato_a_repetir = Comprimidos[N]
      
       Repetir "repeticiones" veces:
          Descomprimidos[M] = dato_a_repetiro
          M = M + 1
       Fin Repetir
    Fin Si

  Fin Desde

Empezaremos viendo la rutina en versión C, ya que en este formato es bastante comprensible y apenas ocupa unas 20 líneas:

//-------------------------------------------------------------------------------------
void RLE_decompress_C( unsigned char *src, unsigned char *dst, int length )
{
  int i;
  unsigned char b1, b2, j;
 
  for( i=0; i<length; i++)
  {
     b1 = *src++;
     if( b1 > 192 )                    // byte comprimido?
     {
        b2 = *src++;
        i++;
        for( j=0; j<(b1 & 63); j++ )   // sí, descomprime y escribe
            *dst++ = b2;
     }
     else
        *dst++ = b1;                   // no, es un byte de dato (escribe)
  }
}

Nótese cómo:

• Usamos los punteros src y dst para leer y escribir en memoria (operador de indirección * ).
• Cogemos un valor desde src y analizamos si está comprimido o no (>= 192).
• Si no está comprimido, es que es un dato a guardar, de modo que lo escribimos directamente en dst.
• Si está comprimido, no es un dato a guardar sino un dato RLE. Obtenemos el número de repeticiones reales (b1 en el ejemplo) y leemos el siguiente dato desde src. Ese dato (b2) tiene que ser escrito b1 veces.

Ahora trasladamos esa rutina a ensamblador de Z80, y nos queda lo siguiente:

;;
;; RLE_decompress
;; Descomprime un bloque de datos RLE de memoria a memoria.
;;
;; Entrada a la rutina:
;;
;; HL = dirección origen de los datos RLE.
;; DE = destino donde descomprimir los datos.
;; BC = tamaño de los datos comprimidos.
;;
RLE_decompress:
 
RLE_dec_loop:
   LD A,(HL)                          ; leemos un byte
 
   CP 192
   JP NC, RLE_dec_compressed          ; si byte > 192 = está comprimido
   LD (DE), A                         ; si no está comprimido, escribirlo
   INC DE
   INC HL
   DEC BC
 
RLE_dec_loop2:
   LD A,B
   OR C
   JR NZ, RLE_dec_loop
   RET                                 ; miramos si hemos acabado
 
RLE_dec_compressed:                    ; bucle para descompresión
   PUSH BC  
   AND 63                              ; cogemos el numero de repeticiones
   LD B, A                             ; lo salvamos en B
   INC HL                              ; y leemos otro byte (dato a repetir)
   LD A, (HL)
 
RLE_dec_loop3:
   LD (DE),A                           ; bucle de escritura del dato B veces
   INC DE
   DJNZ RLE_dec_loop3
   INC HL
   POP BC                              ; recuperamos BC
   DEC BC                              ; Este DEC BC puede hacer BC=0 si los datos
                                       ; RLE no correctos. Cuidado (mem-smashing).
   DEC BC
   JR RLE_dec_loop2
   RET 

Finalmente, para aquellos que utilizan ASM de Z80 integrado en el compilador Z88DK, veamos la rutina descompresora integrada con el paso de parámetros de Z88DK:

int RLE_decompress_ASM( unsigned char *, unsigned char *, int );
 
 
//---------------------------------------------------------------------------
// RLE_decompress_ASM( src, dst, longitud );
//---------------------------------------------------------------------------
int RLE_decompress_ASM( unsigned char *src, unsigned char *dst, int length )
{
 
#asm
   ld hl,2
   add hl,sp
 
   ld c, (hl)
   inc hl
   ld b, (hl)
   inc hl                              // BC = lenght
 
   ld e, (hl)
   inc hl
   ld d, (hl)
   inc hl                              // de = dst
   push de
 
   ld e, (hl)
   inc hl
   ld d, (hl)
   inc hl                              // de = src
 
   ex de, hl                           
   pop de                              // now de = dst and hl = src
 
   // After this:  HL = source, DE = destination, BC = lenght of RLE data
 
.RLE_dec_loop
   ld a,(hl)                          // leemos un byte
 
   cp 192
   jp nc, RLE_dec_compressed          // si byte > 192 = está comprimido
   ld (de), a                         // si no está comprimido, escribirlo
   inc de
   inc hl
   dec bc
 
.RLE_dec_loop2
   ld a,b
   or c
   jr nz, RLE_dec_loop
   ret                                 // miramos si hemos acabado
 
.RLE_dec_compressed                    // bucle para descompresión
   push bc  
   and 63                              // cogemos el numero de repeticiones
   ld b, a                             // lo salvamos en B
   inc hl                              // y leemos otro byte (dato a repetir)
   ld a, (hl)
 
.RLE_dec_loop3
   ld (de),a                           // bucle de escritura del dato B veces
   inc de
   djnz RLE_dec_loop3
   inc hl
   pop bc                              // recuperamos BC
   dec bc                              // Este DEC BC puede hacer BC=0 si los datos
                                       // RLE no correctos. Cuidado (mem-smashing).
   dec bc
   jr RLE_dec_loop2
   ret
 
#endasm
 
}

El algoritmo de compresión se basa en agrupar bytes repetidos iguales en “bloques comprimidos”, dejando sin comprimir los datos cuando los siguientes bytes no son iguales a él.

La rutina de compresión recibe los siguientes parámetros:

• Los datos descomprimidos a comprimir: Los recibiremos en forma de “puntero” o “dirección de memoria” apuntando al principio de los datos.
• El tamaño de los datos descomprimidos.
• Un puntero o dirección de memoria apuntando a dónde queremos dejar los datos comprimidos.

La descripción “en lenguaje natural” para la compresión RLE es la siguiente:

  M = 0
  N = 0
  Desde N=0 hasta N=TAMAÑO_DATOS_DESCOMPRIMIDOS

    Cogemos valor=Descomprimidos[N]
    N = N + 1

    Siguiente_valor = Descomprimidos[N]

    # No se puede comprimir el dato porque el siguiente no es igual:
    Si valor != Siguiente_valor 
    Entonces

       # Si es menor que 192, lo copiamos al destino:
       Si valor < 192
          Comprimidos[M] = valor
          M = M + 1
       Fin Si

       # Si es mayor/igual que 192, lo copiamos a destino como
       # dato comprimido de repetición 1 (193):
       Si valor >= 192
          Comprimidos[M] = 192+1
          M = M + 1
          Comprimidos[M] = valor
          M = M + 1
       Fin Si
    Fin Si

    # Hemos encontrado repeticion de datos:
    Si valor == Siguiente_valor 
    Entonces
       repeticiones = Contar cuantas veces está repetido el byte
                      desde Descomprimidos[M] hasta un máximo de 63.
          Comprimidos[M] = 192 + repeticiones
          M = M + 1
          Comprimidos[M] = valor
          M = M + 1
    Fin Si
  Fin Desde

La rutina en C es la siguiente:

unsigned int RLE_compress( unsigned char *, unsigned char *, 
                           char, unsigned int);
 
 
//-------------------------------------------------------------------------
unsigned int RLE_compress( unsigned char *src, unsigned char *dst, 
                           char scanline_width, unsigned int length )
{
  unsigned int offset, dst_pointer;
  unsigned int bytecounter, width;
  unsigned char b1, b2, data;
 
  dst_pointer = offset = 0;
  bytecounter = 1;
  width = 0;
 
  b1 = src[offset++];
 
  do 
  {
     b2 = src[offset++];
     width++;
 
     while ((b2 == b1) &&
            (bytecounter < scanline_width-1 ) &&
            (width < scanline_width-1))
     {
         bytecounter++;
         b2 = src[offset++];
         width++;
     }
     if (width >= scanline_width)
     {
        offset += scanline_width-width;
        width = 0;
     }
     if (bytecounter != 1)
     {
        data = RLE_LIMIT+bytecounter;
        dst[dst_pointer++] = data;
        dst[dst_pointer++] = b1;
     }
 
     if (bytecounter == 1)
     {
        if (b1 < RLE_LIMIT) 
        {
          dst[dst_pointer++] = b1;
        }
        else
        {
          data = RLE_LIMIT+1;
          dst[dst_pointer++] = data;
          dst[dst_pointer++] = b1;
        }
     }
 
     bytecounter = 1;
     b1 = b2;
  } 
  while (offset <= length);
 
  return(dst_pointer);
}

No necesitaréis la rutina de compresión en versión C de Spectrum ni Z80 de Spectrum, puesto que esta rutina la debéis utilizar en vuestro entorno de desarrollo (PC, MAC) para comprimir los datos e incorporarlos en vuestro programa.

Lo normal durante el desarrollo del juego será “descomprimir” esos datos, no comprimirlos.

En la sección de Ficheros y Enlaces tenéis disponible el compresor y descompresor “rlezx” para Linux y Windows (con su código fuente). Con él se pueden comprimir y descomprimir bloques de datos para incorporarlos en nuestros programas.

Vamos a agrupar todo lo visto hasta ahora en un ejemplo completo comentado. En este ejemplo haremos lo siguiente:

• Comprimir con un compresor RLE propio la pantalla SCR de carga de SOKOBAN.
• Incluir ese fichero RLE resultante en nuestros programas.
• Hacer un programa descompresor del RLE obtenido directamente sobre videoram.

Pantalla de carga del Sokoban

Veamos los diferentes pasos del proceso:

Descargamos la pantalla SCR de carga de Sokoban desde su ficha en World Of Spectrum. Como toda pantalla de carga de Spectrum, ésta ocupará un total de 6912 bytes (256*192 pixeles en formato 8×1, y sus 32*24 bytes de atributos):

[sromero@compiler:rlezx]$ ls -l sokoban.scr
-rw-r--r-- 1 sromero sromero 6912 2009-04-03 12:56 sokoban.scr

A continuación comprimimos la pantalla SCR con el compresor RLE, utilizando la opción “a” (comprimir):

[sromero@compiler:rlezx]$ ./rlezx a sokoban.scr sokoban.rle
Output size: 2571

Tras el proceso de compresión comparamos el tamaño de la imagen comprimida con el tamaño sin comprimir:

[sromero@compiler:rlezx]$ ls -l sokoban.scr sokoban.rle 
-rw-r--r-- 1 sromero sromero 2571 2009-04-03 12:56 sokoban.rle
-rw-r--r-- 1 sromero sromero 6912 2009-04-03 12:56 sokoban.scr

Como vemos, el tamaño de la pantalla ha pasado de 6912 bytes a 2571, lo que supone un ratio de compresión del 63%. La imagen ha ocupado finalmente casi 1/3 del tamaño original. Un ahorro de este tipo puede suponer gran cantidad de espacio aprovechable a partir de las pantallas de presentación, introducción, menúes, game-over o finales de juegos.

Ahora que ya tenemos el fichero binario de datos RLE comprimidos (sokoban.rle), debemos incluirlo dentro de nuestro programa. Podemos hacerlo de 2 formas:

• Método INCBIN: Incluyendo el binario directamente en PASMO con la directiva “INCBIN”, asociándole una etiqueta para poder hacer referencia a él:
  

  Datos_Comprimidos:
     INCBIN "fichero.rle"

  
  En este caso es importante no colocar los datos binarios en una zona de memoria que vaya a ser ejecutada. Lo normal es ubicarlos al final del fichero, como en el ejemplo que veremos a continuación.

• Método BIN2CODE: Convirtiendo los datos binarios a “texto” con una utilidad como BIN2C o BIN2CODE (las tenéis disponibles como descargas en la sección de ficheros). Estas utilidades para PC (Linux, MAC, DOS/Windows) toman un fichero binario y lo convierten a datos listos para incluir en nuestros programas:
  

  [sromero@compiler:~rlezx]$ bin2code sokoban.rle datos.asm a
  BIN2CODE v1.0             By NoP of Compiler SoftWare
  
  2571 bytes from file sokoban.rle converted to datos.asm.
  
  
  [sromero@compiler:~rlezx]$ cat datos.asm
  ;  File created with  BIN2CODE  v1.0  by  NOP of Compiler SoftWare 
  
  BINDATASIZE   EQU   2571
  
  BINDATA LABEL BYTE
     DB   255,255,193,255,255,255,193,255,239,255,193,248,7,206,255,193
     DB   255,204,255,128,3,193,248,43,193,248,62,0,7,215,255,193
     DB   240,198,0,82,120,127,202,255,193,255,255,255,193,255,255,255
     DB   193,255,239,255,193,224,3,206,255,193,255,203,255,193,254,0
     DB   1,193,248,0,193,240,62,52,1,215,255,193,240,128,193,250
     DB   0,127,193,255,0,42,72,63,202,255,193,255,255,255,193,255
     (etc...)

Es decir: el método 1 hace que PASMO incluya el binario directamente dentro de nuestro programa, y el método 2 lo convierte a directivas de datos “DB” para que lo incluyamos con sentencias INCLUDE o copiándolas y pegandolas dentro del código.

Finalmente, sólo tenemos que juntar todas las piezas (esqueleto de programa básico, rutina de descompresión, datos RLE comprimidos) y añadirle una espera de pulsación a tecla para hacer nuestro ejemplo completo.

El programa siguiente, ejemplo_rle.asm, toma la pantalla gráfica comprimida con RLE (sokoban.rle, de 2571 bytes), y llama a la rutina de descompresión RLE indicando como dirección de descompresión la ubicación de la VIDEORAM (16384), con lo que estamos desempaquetando nuestros datos comprimidos directamente sobre la pantalla. Tras eso, espera a la pulsación de una tecla y vuelve al BASIC.

  ; Prueba de descompresion RLE 
  ; Desempaquetamos un SCR comprimido con RLE sobre la pantalla
  ORG 32768
 
  ; Cargamos los datos y preparamos nuestra rutina
  LD HL, Pantalla_Comprimida
  LD DE, 16384
  LD BC, 2571
  CALL RLE_decompress
 
 
Wait_For_Keys_Pressed:         ; Bucle para esperar pulsación de tecla
  XOR A
  IN A, (254)
  OR 224
  INC A
  JR Z, Wait_For_Keys_Pressed
 
  RET                          ; Fin del programa
 
 
;;
;; RLE_decompress
;; Descomprime un bloque de datos RLE de memoria a memoria.
;;
;; Entrada a la rutina:
;;
;; HL = dirección origen de los datos RLE.
;; DE = destino donde descomprimir los datos.
;; BC = tamaño de los datos comprimidos.
;;
RLE_decompress:
 
RLE_dec_loop:
   LD A, (HL)                         ; leemos un byte
 
   CP 192
   JP NC, RLE_dec_compressed          ; si byte > 192 = está comprimido
   LD (DE), A                         ; si no está comprimido, escribirlo
   INC DE
   INC HL
   DEC BC
 
RLE_dec_loop2:
   LD A,B
   OR C
   JR NZ, RLE_dec_loop
   RET                                 ; miramos si hemos acabado
 
RLE_dec_compressed:                    ; bucle para descompresión
   PUSH BC  
   AND 63                              ; cogemos el numero de repeticiones
   LD B, A                             ; lo salvamos en B
   INC HL                              ; y leemos otro byte (dato a repetir)
   LD A, (HL)
 
RLE_dec_loop3:
   LD (DE),A                           ; bucle de escritura del dato B veces
   INC DE
   DJNZ RLE_dec_loop3
   INC HL
   POP BC                              ; recuperamos BC
   DEC BC                              ; Este DEC BC puede hacer BC=0 si los datos
                                       ; RLE no correctos. Cuidado (mem-smashing).
   DEC BC
   JR RLE_dec_loop2
   RET
 
 
; Aquí viene nuestra pantalla comprimida con RLE.
; Hay que darse cuenta de que está fuera de todo
; código ejecutable, es decir, el RET de la rutina
; principal y el RET de las subrutina de RLE_Decompress
; hacen que nunca se llegue a este punto para ejecución.
 
Pantalla_Comprimida:
  INCBIN sokoban.rle
 
  END 32768

Ensamblamos el programa con pasmo –tapbas ejemplo_rle.asm ejemplo_rle.tap y veremos que, al ejecutarlo, aparece la pantalla de carga de Sokoban, que no es más que el bloque de datos RLE descomprimidos directamente sobre la dirección de memoria en que empieza la videoram.

El usuario Z80user, en los foros oficiales de Speccy.org, nos aporta una modificación de nuestra rutina original y una rutina compresora nativa:

He leído el articulo del RLE, he reescrito el codigo de la rutina descompresora y he creado la rutina compresora. He realizado la compresion de la rom de 48K, y posterior descompresión y salen identicas. He utilizado un pequeño truquito con el LDI y el RET PO (un flash no muy usado, pero que usa LDI para indicar BC=#0000) y me he ahorrado algunos bytes (compresora 62 bytes, descompresora 26 bytes).

;; Creada por Z80user
;; Compresor / Descompresor RLE
;; Comprime y Descomprime un bloque de datos RLE de memoria a memoria.
;;
;; Entrada a la rutina COMPRESORA:
;; HL = destino de los datos RLE.
;; IX = datos a comprimir
;; BC = tamaño de los datos a comprimir.
;; Salida
;; AF,DE   desconocido
;; HL = HL+longitud de los datos comprimidos
;; IX = IX+BC
;;
;; Entrada a la rutina DESCOMPRESORA:
;; HL = dirección origen de los datos RLE.
;; DE = destino donde descomprimir los datos.
;; BC = tamaño de los datos a comprimir.
;; Salida
;; AF,DE   desconocido
;; HL = HL+longitud de los datos descomprimidos
;; DE = DE+BC
;; 26 + 62 = 88
//-------------
           org 16384
RLE_descompress
RLE_dec_loop
          LD   A,[HL]         ; Leemos 1 byte
          CP   A,192
          JR   NC,RLE_dec     ; si byte > 192 = está comprimido
test_end  LDI                 ; Copiamos 1 byte en crudo
          RET   PO            ; Volvemos si hemos terminado
          JR   RLE_dec_loop   ; Repetimos el bucle
RLE_dec                          ; bucle para descompresión RLE
          INC   HL            ; Nos colocamos en el valor
          AND   A,#3F
          JR   Z,test_end     ; Si 192, es dato en crudo
          PUSH   BC
          LD   B,A             ; B= numero de repeticiones
          LD   A,[HL]
bucle     LD   [DE],A         ; \
          INC   DE             ;  Bucle de escritura B veces
          DJNZ   bucle        ; /
          POP   BC
          DEC   BC             ; Ajustamos el contador al usar RLE
          JR   test_end        ; Copiamos 1 byte mas
 
 
//---------------
RLE_Comprimir
byte_1    
          LD   E,[IX+#00]        ; leer byte
          INC   IX                ; incrementar posicion
          DEC   BC                ; descontar contador
          LD   A,E                ;
byte_2    
          CP   A,#C0             ; Si es un codigo RLE
          JR   NC,RLE_compress   ;  tratar como RLE
          CALL   get_byte        ; tomar el 2º byte
          JR   Z,ultimo_byte     ; falta escribir el ultimo byte
          CP   A,E                ;
          JR   Z,RLE_compress2   ; usar compresion RLE si son identicos
          LD   [HL],E             ; son distintos, escribir el byte anterior
          INC   HL                ;
          LD   E,A                ; recuperar el ultimo byte leido
          JR   byte_2             ; continuar con la compresion
ultimo_byte   LD   [HL],E        ; escribir el ultimo byte
          INC   HL                ;
          RET         ; salir
RLE_compress2   
          LD   D,#C1              ; eran identicos, empezar, con 2
          JR   RLE_Repetido
RLE_compress   
          LD   D,#C0              ; era un valor RLE original
RLE_Repetido   
          CALL   get_byte         ; Obtener otro byte
          JR   Z,RLE_distinto     ; Escribir el valor RLE si no hya mas bytes
          CP   A,E                ; Comprobar si es identico
          JR   NZ,RLE_distinto    ; Se encontro un byte distinto
          INC   D                  ; incrementar el contador de repeticiones
          JR   NZ,RLE_Repetido    ; Otro byte identico
          DEC   D                 ; Se acabo el contador de repeticiones
RLE_distinto   
          LD   [HL],D              ; \
          INC   HL                 ;  \ escribir valor RLE
byte_simple   
          LD   [HL],E              ;  /
          INC   HL                 ; /
          LD   E,A                 ; Recuperar el ultimo byte distinto
          JR   byte_2              ; seguir comprimiendo
get_byte   
          LD   A,B                 ; \
          OR   A,C                 ;  Comprobar si es el ultimo byte
          RET   Z                  ; /
          DEC   BC                 ; descontar contador
          LD   A,[IX+#00]          ; leer byte
          INC   IX                 ; incrementar posicion
          RET           

Agradecemos a Z80user su aportación, y aunque advertimos a los lectores que no podemos certificar el código, lo listamos para quien le pueda resultar de interés.

• rlezx.c: Código fuente del Compresor / Descompresor rlezx.
  (Compilar con make rlezx).
• RLEZX_WIN32.zip : Compresor/Descompresor versión DOS/Windows.
• bin2code.c : Convertidor de ficheros binarios a C, ASM, o PASCAL.
• bin2code.exe : Convertidor de ficheros binarios versión DOS/Windows.
• bin2.c : Otro convertidor de binarios a texto.
• Pantalla de carga de SOKOBAN sin comprimir (SCR) y comprimida (RLE).
• Ejemplo_rle : Programa de ejemplo (ASM, TAP y RLE).

Hemos visto los fundamentos de la compresión y descompresión RLE, así como rutinas C y ASM para implementarlos en nuestros programas. Mediante lo visto en este capítulo, podemos obtener un gran ahorro de memoria en nuestros programas, pudiendo introducir más cantidad de gráficos en el mismo espacio. También permite que pueda caber más código, más sonido o más texto, ya que aunque no apliquemos la compresión sobre este tipo de datos, podremos aprovechar el espacio que dejen libre nuestros gráficos comprimidos.

Santiago Romero
Abril 2009
Wiki Speccy.org