27 junio 2014

Compresión RLE WB para MSX

Hace un tiempo, estuve investigando la compresión RLE (Run-Length Encoding), para utilizarlo en gráficos de MSX. Si no conoces el RLE, se puede resumir, diciendo que es un sistema muy simple, que se basa en reducir secuencias de valores repetidos.

Si hablamos del RLE más básico, en el modo gráfico de los MSX de primera generación (SC2), funciona muy bien con las tablas de colores, ya que es donde suele repetirse muchos bloques de datos. En muchos casos se puede conseguir más de un 70% de ganancia, dependiendo de la técnica creativa del dibujo y si la relación patrón/color(*1) esta correctamente ordenada.

Sin embargo, a la hora de comprimir los datos de los patrones, este sistema no suele ser efectivo, ya que los valores sufren más de variaciones que los colores. Esto provoca que por cada valor se gasten dos Bytes, por lo que en muchos casos obtendríamos el efecto contrario, un bloque de datos de mayor tamaño que el original.

Por otro lado, una de las ventajas que tiene, es que es muy rápido y a la hora de programar, es más simple que usar un función de volcado a VRAM (como la función de la BIOS LDIRVM), ya que no necesitaremos averiguar e indicar el tamaño del bloque de datos.

Pero volviendo al tema de este post, pensando en un sistema basado en RLE que no penalizará en los valores no repetidos, encontré en la WEB SMS Power, un artículo donde se describen diferentes sistemas utilizados en varios juegos de la Sega Master System. De entre todos, le vi posibilidades al del Wonder Boy, así que lo adapté para MSX, modificando algunas cosas ya que está adaptado a la forma de trabajar el modo gráfico de la Master System. 

Su funcionamiento es el siguiente:
  • Se utiliza un valor como control. He elegido el valor $80 ya que el 0 es un valor muy común y como veremos más adelante, cuando un valor coincida con el número de control se utilizarán 2 bytes. Con este pequeño cambio se obtiene mayor compresión. En una prueba de un tileset de 115 tiles, obtuve una ganancia de más de 70 Bytes.
  • Si el siguiente valor al control es 0, se utiliza para cuando el valor coincide con el de control y este no se repite. 
  • Si el siguiente valor al control es igual a 255, indicará que es el final.
  • Si el siguiente valor al control no es ni 0 ni 255, entonces indicará el número de repeticiones (entre 1 y 254), y habrá un tercer dato que contendrá el valor que se repite. Como 1 repetición no se utiliza, en el decodificador se incrementa uno para abarcar de 2 a 255 repeticiones. 
  • Si el primer valor no es igual al número asignado como control, será un dato que no se repite y se escribe directamente a la salida.

Forma resumida:
$80 nn dd     ;repite nn veces (de $1 a $FE) el valor dd
$80 $0        ;para cuando el valor a escribir es igual al                 dígito de control ($80) sin repetición
$80 $FF       ;final del bloque de datos
 dd (!=$80)   ;valor sin repetición

En definitiva, los datos que no se repitan sólo ocuparán un valor excepto cuando sea igual al valor de control que se usarán dos, pero en los casos que si se repitan, se gastarán 3 Bytes (dígito de control, numero de repeticiones y valor), uno más que el RLE básico.

Este sistema funciona muy bien con los datos de patrones, pero con los colores hay casos donde es más eficiente el RLE básico.

Adjunto la rutina descompresora a RAM y a VRAM, junto con un ejemplo:
En breve publicaré la utilidad MSXtiles devtool, donde se puede sacar a código y de forma independiente (patrones, colores y mapa), los diferentes tipos de datos que componen una pantalla de MSX (SC2) en RLE básico o el basado en WB.


Notas:

*1 - Si creamos una imagen utilizando un editor gráfico, al convertirlo a datos en formato MSX, puede que dependiendo del algoritmo de conversión, los valores de las lineas queden desordenados, lo cual penalizaría el ratio de compresión. Ejemplo:

  • Forma desordenada: $FA,$AF,$AF,$FA,$AF,$1F,$F1
  • Forma ordenada: $FA,$FA,$FA,$FA,$FA,$1F,$1F

4 comentarios:

theNestruo dijo...

Hola compañero!

Respecto a la hora de preprocesar los datos para mejorar la compresión, yo estuve haciendo algunos experimentos con el PCX2MSX. No enfocados explícitamente a RLE sino con el pensamiento de que, en general, a cualquier compresor le gustan los datos repetidos.
La idea era evitar cambios en la CLRTBL cuando había patrones FF o 00 en la CHRTBL. Por ejemplo, si vienes de tener los colores $F4 en la línea anterior y ahora tienes líneas completamente blancas, no tiene sentido poner $F0 o $FF sino que se puede mantener el $F4 que va a dar igual.
Tengo que echarle un vistazo porque no sé hasta qué punto llegué a desarrollarlo (ni siquiera recuerdo si está metido en el PCX2MSX que está publicado).

Otra cosa que he visto (y al RLE de Robsy le pasaba parecido, si no recuerdo mal) es que cuando hay bytes no repetidos "aprovechais" el de control. Sin haber experimentado realmente con ello, ¿no sería más conveniente que los 7 bits del caracter de control indicaran número de repeticiones O número de caracteres no repetidos a volcar? De forma esquemática:
byte = cnnnnnnn; if (c) then FILVRM(n bytes) else LDIRVM(n bytes).
Eso sí, habría que aumentar la complejidad del compresor porque dos bytes repetidos en medio de una secuencia de bytes diferentes convendría más dejarlos en la misma secuencia que ponerlos como repetición, etc.

Por último, una minioptimización en unRLEWBtoVRAM (sin probar):
no hagas el inc A antes del doRLE y mete un out adicional después del djnz. Ahorras el inc, dos nops y un djnz.

A ver si pudiera hacer unas pruebillas de algo de esto y mandarte un correo

mvac7 dijo...

Hola theNestruo.
Después de pasar muchas horas ordenando los datos a mano desde el nMSXtiles, desarrollé una función de optimización que hace lo que explicas, y lo añadí en la aplicación MSXtiles devtool (pronto la publicaré). Esta en VB.net pero no creo que te cueste mucho adaptarlo al lenguaje que utilices ya que es bastante sencilla.
Sobre el tema de compresión, realicé algo parecido, pero creo que no me resulto tan eficiente como el de WB. Si no recuerdo mal, es muy parecido al sistema que utiliza internamente el SDCC para comprimir cadenas (excepto las que son constantes). De todas formas estaría bien hacer una prueba con estos dos sistemas. Seguro que para determinados casos de mejores resultados.
Gracias por las ideas y por tu ayuda! :)

Dark Schneider dijo...

Hola, los enlaces no me funcionan. ¿Podrías arreglarlos?. Gracias.

mvac7 dijo...

Hola Dark Schneider
He cambiado los links. No se que han pasado con los ficheros. Han desaparecido de mi Drive!!!
Gracias por avisar.