Páginas

27 junio 2014

Compresión RLE SMS Wonder Boy

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 en dos bytes: número de repeticiones y valor.

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 los 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 del estilo y técnica usada en la creación de la imagen, y si contiene los valores debidamente ordenados. Me refiero a que la relación entre el color de tinta y fondo con el patrón, no se invierta muy a menudo, si son los mismos colores. Esto se puede conseguir si la herramienta que utilicemos para crear nuestros gráficos, tengamos control de que colores usamos para la tinta o fondo, o en el caso de un conversor, este ordene los datos. 

Continuando con el RLE básico, cuando se trata de comprimir la información de los patrones, este sistema rara vez resulta efectivo, ya que la información es más variada y no se suelen repetir muchos valores. Esto provoca que por cada valor se gasten dos bytes, con lo que se obtendría un resultado de mayor tamaño.

Otra de las ventajas que tiene, es que es muy rápido y a la hora de utilizarlo es un poco más simple que la función de volcado (LDIRVM), ya que no necesitaremos averiguar e indicar el tamaño del bloque de datos.

Pero volviendo al principio de este post, buscando sobre este tema, encontré en la WEB SMS Power, un artículo donde se describen diferentes sistemas RLE 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 pero modificando algunas cosas. 

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, entonces indica 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.
Se ha eliminado el código de control ($FF), para los casos de una solo repetición (dos valores), ya que usar un segundo código de control no ofrece un beneficio claro (o al menos en las pruebas que he realizado).

Resumiendo un poco: los datos que no se repitan sólo ocupan un valor excepto cuando sea igual al valor asignado como control que se usarán dos, pero en los casos que si se repitan, se gastarán 3 Bytes, 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.

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.