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

Todo sobre la creación, diseño y programación de nuevo software para
nuestro Spectrum

Moderador: Sir Cilve Sinclair

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

Notapor sromero el Sab Abr 04, 2009 11:56 am

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.
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor Boriel el Sab Abr 04, 2009 1:28 pm

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. :P
Boriel
Sabreman
 
Mensajes: 351
Registrado: Lun May 28, 2007 9:55 am
Ubicación: Tenerife

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

Notapor sromero el Sab Abr 04, 2009 1:32 pm

Boriel escribió: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. :P


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!
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor winston el Sab Abr 04, 2009 5:06 pm

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 :oops: )
Tarjeta ethernet para el Spectrum - http://spectrum.alioth.net/doc

Debemos practicar un quirkafleeg
Avatar de Usuario
winston
Sabreman
 
Mensajes: 469
Registrado: Mar Ago 19, 2008 4:17 pm
Ubicación: Isla de Man

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

Notapor Metalbrain el Sab Abr 04, 2009 5:43 pm

winston escribió: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 :oops: )


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.
SevenuP se escribe con u minúscula y P mayúscula.
Avatar de Usuario
Metalbrain
Freddy Hardest
 
Mensajes: 588
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla

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

Notapor ZXevious el Lun Abr 06, 2009 12:07 pm

Muy bueno Sromero, claro y sencillo de seguir.

Un saludo.
ZXevious
Jack The Nipper
 
Mensajes: 101
Registrado: Vie Abr 11, 2008 5:37 pm

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

Notapor sromero el Lun Abr 06, 2009 12:13 pm

ZXevious escribió: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 :)
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor AlbertoOM el Vie Jul 24, 2009 2:55 pm

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.
AlbertoOM
rst 0
 
Mensajes: 1
Registrado: Mie Dic 31, 2008 2:16 pm

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

Notapor sromero el Vie Jul 24, 2009 4:54 pm

AlbertoOM escribió: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.
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor decicoder el Mie Dic 09, 2009 8:46 pm

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
xor a
ld R,a
b1 in f,(c)
jp pe , b1
ld a,R
Avatar de Usuario
decicoder
Jack The Nipper
 
Mensajes: 176
Registrado: Jue Jul 19, 2007 10:37 am

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

Notapor sromero el Jue Dic 10, 2009 11:20 am

decicoder escribió: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!
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor decicoder el Dom Dic 13, 2009 11:27 am

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
xor a
ld R,a
b1 in f,(c)
jp pe , b1
ld a,R
Avatar de Usuario
decicoder
Jack The Nipper
 
Mensajes: 176
Registrado: Jue Jul 19, 2007 10:37 am

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

Notapor Z80user el Lun Ene 18, 2010 2:33 am

He leido el articulo del RLE, he reescrito el codigo de la rutina descompresora y he creado la rutina compresora. :roll:
He realizado la compresion de la rom de 48K, y posterior descompresion y salen identicas.
:idea: 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                     ;
Si vas a tirar Hardware, primero pregunta si alguien lo puede recuperar.
No abandones un ordenador en un vertedero, donalo a alguien.
Z80user
Manic Miner
 
Mensajes: 215
Registrado: Vie Jun 08, 2007 9:42 am
Ubicación: En un lugar de la mancha

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

Notapor sromero el Lun Ene 18, 2010 9:36 am

Z80user escribió:He leido el articulo del RLE, he reescrito el codigo de la rutina descompresora y he creado la rutina compresora. :roll:
He realizado la compresion de la rom de 48K, y posterior descompresion y salen identicas.
:idea: 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!
NoP / Compiler
Avatar de Usuario
sromero
Nonamed
 
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia

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

Notapor Z80user el Lun Ene 18, 2010 11:27 pm

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
Si vas a tirar Hardware, primero pregunta si alguien lo puede recuperar.
No abandones un ordenador en un vertedero, donalo a alguien.
Z80user
Manic Miner
 
Mensajes: 215
Registrado: Vie Jun 08, 2007 9:42 am
Ubicación: En un lugar de la mancha

Siguiente

Volver a Programación y nuevos desarrollos

¿Quién está conectado?

Usuarios navegando este Foro: No hay usuarios registrados visitando el Foro y 4 invitados