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.