Curso ASM Z80 (X): "Compresión y Descompresión RLE"

[sromero]

Hola a todos,

Acabo de publicar en el Wiki de Speccy.org un nuevo capítulo del Curso de Ensamblador de Z80 de Compiler Software.

En esta entrega, el artículo habla sobre Compresión y descompresión RLE, con rutinas y ejemplos para comprimir datos de todo tipo (especialmente gráficos) en vuestros programas en C y ASM para Spectrum.

El enlace directo al artículo es este:

Curso ASM Z80: Compresión y descompresión RLE

Cualquier comentario, sugerencia o corrección lo podéis hacer en este hilo.

Un saludo y espero que os resulte útil.

[Boriel]

Excelente artículo La verdad es que está muy clarito. En serio, me ha encantado.
De hecho, ahora quiero poner las rutinas de RLE, Huffman y LZ en la librería del BASIC.

[sromero]

Excelente artículo La verdad es que está muy clarito. En serio, me ha encantado.
De hecho, ahora quiero poner las rutinas de RLE, Huffman y LZ en la librería del BASIC.

Gracias. Puedes tomar la rutina de Descompresión si quieres, y si ves forma de optimizarla (que seguro que la hay xD), pues adelante, me lo comentas y edito el artículo del wiki añadiéndola.

Lo que no tengo es rutina de compresión en ASM porque no la he necesitado (comprimo "en el PC").

Si mientras programas las de Huffman y LZ quieres escribir alguna reseña y/o rutina para añadirla al curso, ya sabes mi email. Aunque no haya explicación teórica de por medio, puede ser interesante tener un capítulo final de recopilación de funciones útiles, y Huffman_Compress, Huffman_Decompress, LZ_Compress y LZ_Decompress con sus ".c" para PC (compresores) puede ser más que útil (ya te digo, incluso sin escribir teoría sobre ello).

Bueno, y si quieres contribuir con un RLE_Compress en ASM, pues lo mismo

Saludos!

[winston]

Tengo una pregunta - ¿cúal es la diferencia entre LZ y LZW? (Hace años, yo escribí rutinas compresión/descompresión de LZW, pero para IBM AIX... mi rutinas fueron muy lento )

[Metalbrain]

Tengo una pregunta - ¿cúal es la diferencia entre LZ y LZW? (Hace años, yo escribí rutinas compresión/descompresión de LZW, pero para IBM AIX... mi rutinas fueron muy lento )

Son algoritmos diferentes, LZ fue publicado en 1977 y LZW en 1978. El LZ se basa en distinguir entre bytes literales y parejas de valores que indican un bloque previo de tantos bytes a tanta distancia de la posición actual. El LZW creo que va construyendo poco a poco un diccionario con ocurrencias anteriores, y se usa este diccionario para referenciar cada repetición (o algo así, tampoco lo he estudiado en profundidad). Creo que en general el algoritmo LZ es mejor, se puede afinar de múltiples formas para mejorar la compresión y adaptarla a distintas situaciones. Y al ser en general más sencillo, no necesita ninguna memoria extra como el LZW (en la cual ir almacenando el diccionario), y la velocidad de descompresión también es bastante superior. El único interés que veo yo en el algoritmo LZW es que se utilizaba en el formato GIF. Y desde luego para sistemas de 8 bits, creo que la decisión está clara entre uno y otro.

[ZXevious]

Muy bueno Sromero, claro y sencillo de seguir.

Un saludo.

[sromero]

Muy bueno Sromero, claro y sencillo de seguir.

Gracias.

He intentado además dejar la rutina ASM y C/Z88DK lista para usar, así como el compresor.

Así si alguien no quiere usar el "uncrunch" que circula por ahí o consigue mejor ratio de compresión con RLE, pues ala, adelante con los caballos, el código es GPL

[AlbertoOM]

Muy buen artículo.
Lo que me he fijado es que el compresor (rlezx.exe) falla con algunas imágenes (.scr) en algunos casos me ha dado un error la propia aplicación de compresión y en otros lo que hace es que no descomprime corectamente por lo que me imagino que el problema es del compresor.

[sromero]

Muy buen artículo.
Lo que me he fijado es que el compresor (rlezx.exe) falla con algunas imágenes (.scr) en algunos casos me ha dado un error la propia aplicación de compresión y en otros lo que hace es que no descomprime corectamente por lo que me imagino que el problema es del compresor.

Es posible ... si quieres pásame alguna de las imágenes que te da error y hago algo de debug, aunque no dispongo de mucho tiempo libre ahora mismo ...

Saludos.

[decicoder]

Enhorabuena por el articulo.
Me ha parecido tan esclarecedor que me he animado a introducime en el proceloso mundo de los descompresores.
Creo que el método rle puede ser adecuado para aplicarlo para las ultracargas.
1º porque la rutina de descompresión es muy corta
2º es rápido descomprimiendo (resultaría paradójico ganar tiempo de carga para luego perderlo en la descompresión)

Se me han ocurrido dos mejoras que pueden incrementar los ratios de compresión
1º Hacer que el 192 no sea fijo sino un parámetro. Se buscará el parametro que mejor ratio dé.
2º En un juego real seguro que hay mucho FF o FE que perjucicaría la compresión RLE. Antes de comprimir se suma a cada byte una constante y luego en la descompresión se resta.
Por ejemplo si sumamos $02 los $ff y $fe serán $01 y $00 y los $00 y $01 quedarán como $02 y $03 , que no son gravosos para el rle.

Con unas optimizaciones, pensado que se va autilizaar el descompresor para descomprimir snapshot, la rutina queda en apenas 30 bytes.

Código: Seleccionar todo

 org $4000
  
  ld hl,$4aaa
  ld de,$57ff  ;prueba para descomprimir pantalla
  ld c, 192;
  jr mas  
  
descomp
   sub c
   ld b,a
   ld a,(hl)
   dec hl
   add a,0
repetir
   ld (de),a
   dec de
   djnz repetir
mas   
   ld a,(hl)
   dec hl
   cp c
   jr nc,descomp
   
   add a,0
   ld (de),a
   dec de
   jr  mas ; // ó jr $00

La estrategia para descomprimir snapshot, ya que llegará un momento que memoria descomprida-destino y memoria comrimida-origen entrarán en conflicto, es empezar a descomprimir desde el final y retroceder hasta que la propia rutina se machaque así misma y la ultima instrución se convierta en un jr $00 . Por eso aparentemente la rutina no tiene condición de salida.
Me pregunto si hay otras estrategias para snapshots comprimidos como colocar la rutina descompresora al final o inclso a la mitad de la memoria

[sromero]

Enhorabuena por el articulo.
Me ha parecido tan esclarecedor que me he animado a introducime en el proceloso mundo de los descompresores.

Me alegro de que le haya sido útil a alguien

Creo que el método rle puede ser adecuado para aplicarlo para las ultracargas.

(...)
Con unas optimizaciones, pensado que se va autilizaar el descompresor para descomprimir snapshot, la rutina queda en apenas 30 bytes.

Fantástico.

En principio, RLE resulta útil para bloques de bytes consecutivos iguales, por lo que no sé exáctamente qué ratio de compresión se conseguirá con él sobre las cargas ... ¿has hecho pruebas y las has comparado con otros algoritmos?

saludos!

[decicoder]

He hecho unas pruebas con, ¿como no?, el snapshot del Manic Miner. Y de 48k se pasa a unos 27000 bytes. Que me parece que está muy bien.
No lo he comparado con otros métodos. No he encontrado como en tu articulo un codigo en C de la parte compresora que es lo que me interesa.
La compresion RLE puede ser muy interesante para juegos sencillos que no ocupan toda la memoria. Estoy pensando en juegos de 16k como el Jumping Jak que no se puede convertir a ultracarga desde su versión .TAP porque tiene un sistema de carga anticopión, muy simple, que con el k7zx no se puede resolver automáticamente y no queda más remedio que hacer la conversión a partir de un snapshot.

Para más detalles sobre la compresión aplicada a cargas rápidas he escrito una entrada en la wiki:
http://code.google.com/p/otla/wiki/CuestionCompresion

[Z80user]

He leido 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 descompresion 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

Código: Seleccionar todo

;; 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      ; segir 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                     ;

[sromero]

He leido 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 descompresion 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

Sí, es posible que podáis realizar múltiples mejoras. Aunque el artículo es "reciente", el código de la rutina descompresora tiene ya 5 ó 6 años, y es un port "directo" del código que escribí hará casi 14 años en ASM de 80x86 para PC, así que seguro que es mejorable en muchos aspectos.

Gracias por postear la rutina, a ver si tengo tiempo de subirla al artículo o al wiki como aportación.

saludos!

[Z80user]

Tube la precaucion de probar la rutina, comprimiendo la ROM del spectrum 48K, el fichero 48k.rom que viene con el zx-spin 0.666, la compresion se realizo en #4C0C bytes, osea crecio y bastante.

He pensado en hacer una version del RLE, haciendo que se puedan incluir partes sin compresion, con los codigos inferiores al #C0, aunque ahora la mejora del RLE seria buscar cadenas de 3 bytes repetidos, ya que como hemos visto 2 bytes identicos, siempre repercute en 2 bytes comprimidos, y no ayuda mucho.

#00,#10,#20,#30,#40,#50,#60,#70,#80,#90,#A0,#B0,#C0,#D0,#E0,#F0 Original
#00,#10,#20,#30,#40,#50,#60,#70,#80,#90,#A0,#B0,#C0,#C0,#C0,#D0,#C0,#E0,#C0,#F0 comprimido con RLEv1
#16,#00,#10,#20,#30,#40,#50,#60,#70,#80,#90,#A0,#B0,#C0,#D0,#E0,#F0 Con RLEv2

#00,#00,#00,#40,#40,#30,#30,#30,#30 Original
#C3,#00,#C2,#40,#C4,#30 Comprimido con RLEv1
#C3,#00,#C2,#40,#C4,#30 Comprimido con RLEv2
La idea es hacer que los codigos inferiores al #C0 se comporten, como el numero de bytes en crudo que hay que copiar, esto nos permite emplear LDIR a discreccion , manteniendo la codificacion RLE original.
Otra idea, es variar el valor #C0 (el 192), por otro, segun la mayor longitud de caracteres repetidos, es un metodo de compresion a partir del cual se pueden llegar a optimizaciones, con tal de pensar un poco, viendo su sdefectos y virtudes.

El compresor que comento Metalbrain hace tiempo Exomizer, es mucho mejor, aunque requiere un PC para la compresion, creo que no hay version nativa, y el descompresor es de cierto tamaño, mas que el RLE, tambien le hize alguna optimizacion, algo mas rapido, aunque era destructivo, no se si llege a publicarlo, por lo que hacer este tipo de compresion teniendo el exomizer, que no creo que engorde tanto los ficheros como el RLE, un 18,8% mas usando la ROM del Spectrum