cursos:ensamblador:compresion_rle

Action disabled: source

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).

También veremos cómo utilizar la compresión ZX0, un algoritmo de compresión de propósito general que es eficiente no sólo con los gráficos sino con otros tipos de datos. En el caso del algoritmo ZX0, al contrario que con RLE (donde entraremos más en detalle), nos centraremos simplemente en cómo usar el la herramienta compresora y descompresora disponible.


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:

7 6 5 4 3 2 1 0
128 64 32 16 8 4 2 1

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.

7 6 5 4 3 2 1 0
RLE RLE Número de repeticiones

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:

Datos leídos del array Significado del dato
10 Es menor de 192 → Es un dato sin compresión → 10
193, 200 Es mayor que 192, se repite 193-192=1 veces el 200 → 200
230, 5 Es mayor que 192, se repite 230-192=37 veces el 4 → 5, 5, 5, 5, 5 (…)
219, 240 Es mayor que 192, se repite 219-192=16 veces el 240 → 240, 240, 240 (…)

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 %00111111                 ; 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 son correctos. Cuidado (mem-smashing).
    dec bc
    jr rle_dec_loop2
    ret


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 de Sokoban desempaquetada en VRAM

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/DEFB 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 35000
 
    ; 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, ($fe)
    or %11100000
    inc a
    jr z, Wait_For_Keys_Pressed
    ret                          ; Fin del programa
 
; Aquí incluiremos el código de la rutina RLE_decompress
;; --- RLE_decompress ---
 
; 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 35000


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
//-------------
 
RLE_descompress:
rle_dec_loop:
          ld a, (hl)                     ; Leemos 1 byte
          cp a, 192
          jr nc, rle_dec                 ; si byte > 192 = está comprimido
rle_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, rle_test_end             ; Si 192,  es dato en crudo
          push bc
          ld b, a                        ; B= numero de repeticiones
          ld a, (hl)
rle_bucle:
          ld (de), a                     ; \
          inc de                         ;  Bucle de escritura B veces
          djnz rle_bucle                 ; /
          pop bc
          dec bc                         ; Ajustamos el contador al usar RLE
          jr rle_test_end                ; Copiamos 1 byte mas
 
 
//---------------
RLE_Comprimir:
rle_byte_1:
          ld e, (ix+$00)                 ; leer byte
          inc ix                         ; incrementar posicion
          dec bc                         ; descontar contador
          ld a, e
rle_byte_2:
          cp a, #C0                      ; Si es un codigo RLE
          jr nc, rle_compress            ;  tratar como RLE
          call rle_get_byte              ; tomar el 2º byte
          jr z, rle_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
rle_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 l                          ;  \ 
rle_byte_simple:                         ;   / escribir valor RLE
          ld (hl), e                     ;  /
          inc hl                         ; /
          ld e, a                        ; Recuperar el ultimo byte distinto
          jr rle_byte_2                      ; seguir comprimiendo
rle_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


ZX0 es un algoritmo RLE supervitaminado basado en el formato de compresión “LZ77/LZSS” con unas rutinas de descompresión muy rápidas y de tamaño muy reducido, que a cambio nos proporcionan un muy buen ratio de compresión (superior normalmente al que conseguiríamos con RLE).

RLE puede ser muy eficiente con gráficos porque en los gráficos suele haber zonas consecutivas con el mismo valor (“rellenos”), pero no es tan bueno con otros tipos de datos donde ZX0 sí que lo es.

La potencia de ZX0 se basa en el su compresor, que podemos descargar de su web, y que podemos utilizar para comprimir cualquier binario (datos gráficos, sonido o incluso código) mediante:

zx0 fichero.ext

Lo cual generará un fichero llamado “fichero.ext.zx0”.

Por ejemplo, con la pantalla de carga de Sokoban:

$ zx0.exe ../sokoban.scr
MESA-INTEL: warning: Haswell Vulkan support is incomplete
ZX0 v2.2: Optimal data compressor by Einar Saukas
[...............................................]
File compressed from 6912 to 1383 bytes! (delta 2)

Pasamos de 6912 bytes a sólo 1383 bytes, una reducción espectacular que nos produce un fichero sokoban.scr.zx0 listo para usar.

Este fichero puede ser incluído después en nuestro programa con INCBIN o introducido en un TAP para ser cargado como un bloque de datos con LOAD “” CODE.

Después, en nuestro programa, sólo tenemos que utilizar una de las rutinas descompresoras disponibles para desempaquetar los datos comprimidos en la zona de memoria deseada.

Hablamos de “rutinas descompresoras”, en plural, porque existen 4 rutinas:


Rutina Tamaño en bytes Velocidad
“Standard” 68 bytes -
“Turbo” 126 bytes ~21% más rápida que la “Standard”
“Fast” 187 bytes 25% más rápida que la “Standard”
“Mega” 673 bytes 28% más rápida que la “Standard”


Hay 4 rutinas para que se podamos elegir la que más nos convenga según si necesitamos que la rutina sea lo más rápida posible (aunque la rutina descompresora ocupe 673 bytes), o si no nos importa que tarde un 28% más, pero a cambio la rutina ocupa sólo 68 bytes. Nótese que hablamos del tamaño de la rutina de descompresión, ya que los datos comprimidos siempre ocuparán lo mismo.

Así pues, elegimos una de las rutinas disponibles de la Web de ZX0, la incluímos en nuestro programa en una dirección determinada, y podemos descomprimir los datos ZX0 pasando como parámetros los datos comprimidos en HL y el destino de la descompresión en DE:

    ld    hl, scr_datos_zx0    ; origen = datos comprimidos
    ld    de, 16384            ; destino = pantalla
    call  decompress_zx0

Personalmente, encuentro las rutinas “Standard” y “Turbo” como las 2 mejores elecciones (una u otra según las necesidades que se tengan), ya que en mi opinión, el aumento de tamaño para conseguir una pequeña ganancia de un 7% de velocidad no justifica pasar de 126 a 673 bytes (salvo que nos sobre memoria y nuestro objetivo sea descomprimir datos al vuelo)

Las rutinas de descompresión, están disponibles en las siguientes ubicaciones:

Veamos cómo usar una de las rutinas en nuestros programas:

    ORG 33500
 
    ld hl, pantalla_comprimida   ; datos comprimidos
    ld de, 16384                 ; destino compresion
    call dzx0_standard           ; descomprimir
 
loop:
    jr loop                      ; bucle para no volver a BASIC
 
    INCLUDE "dzx0_standard.asm"
 
pantalla_comprimida:
    INCBIN "pantalla.scr.zx0"
 
    END 33500

Este es el tamaño del TAP resultante (cargador, rutina de descompresión y pantalla completa incluída):

1583 bytes - testzx0.tap

Y este es el resultado de ejecutar dicho TAP:


Pantalla de carga de Sokoban desempaquetada en VRAM

También tenemos disponibles en la web de ZX0 rutinas que descomprimen al revés en memoria, denominadas dzx0_standard_back y dzx0_turbo_back.

La utilidad de las rutinas “back” es la de descomprimir los datos en una posición de memoria que solape con el área de datos que estamos descomprimiendo. Es decir, machacamos los datos comprimidos con los descomprimidos (con lo que evidentemente no podremos volver a utilizarlos) para escenarios donde tenemos poco espacio en memoria donde desempaquetar.

Para hacer esto, la última dirección de los datos comprimidos debe de estar “delta” bytes más arriba en memoria que la última dirección que ocuparán los datos descomprimidos. El valor exacto de “delta” lo reporta el compresor zx0 en el momento de comprimir los datos. La siguiente figura de la web de ZX0 aclara qué es exáctamente delta y por qué tenemos un ahorro parcial de memoria para la descompresión:

                       |------------------|    compressed data
    |---------------------------------|       decompressed data
  start >>                            <--->
                                      delta

Un apunte muy importante es que hay 2 versiones de ZX0 (zx0 v1 y zx0 v2). Es importante que utilicemos compresor y descompresor de la misma versión (preferentemente de la versión 2). Para asegurarnos de que compresor y descompresor coinciden en versión, lo más seguro es tener actualizado tanto el compresor como las rutinas descompresoras con las últimas versiones disponibles en la web del autor.

A día de hoy, ZX0 es una herramienta imprescindible para hacer programas y juegos de Spectrum, ya que los ratios de compresión son muy buenos y el uso de datos comprimidos (gráficos, textos, e incluso código) supone una enorme diferencia en tiempos de carga y cantidad de recursos que podemos poner en nuestros juegos.



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.


[ | | ]

  • cursos/ensamblador/compresion_rle.txt
  • Última modificación: 19-01-2024 12:35
  • por sromero