Algoritmo Move-to-Front

Programando el Amstrad en Ensamblador.
Reglas del Foro
Debido a que hay varios temas pidiendo ayuda para programar en ensamblador máquinas distintas al Amstrad CPC, con micro distinto al Z80 y que incluso dependen del sistema operativo, nos vemos en la necesidad de poner por escrito que estos posts son bienvenidos pero que no es el lugar adecuado ya que por estos lares nos dedicamos más al ensamblador del Z80, un microprocesador de 8 bits que tuvo su gran auge en ordenadores y consolas de los años 80.

De todas formas, esto no quita que alguien que sepa del asunto pueda postear alguna respuesta pero es más fácil encontrar foros dedicados a programar en ensamblador en Windows o MS-DOS que ayudarán más que nosotros:
http://www.lawebdelprogramador.com/news ... nsamblador
Urusergi
Megaforero
Megaforero
Mensajes: 301
Registrado: Sab 25 Feb , 2006 5:45 pm

Algoritmo Move-to-Front

Mensajepor Urusergi » Dom 09 Sep , 2012 10:49 pm

Muy buenas,

Como comenté en el hilo -Snippets Z80: borrado de pantalla- estaba investigando algunas técnicas que supuestamente mejoran la capacidad de los compresores, y hay una que me llamó la atención por su simplicidad... es la llamada "Move-to-Front Transform".

Como ahora no tengo tiempo para seguir trasteando voy a publicar las fuentes del codec. Como curiosidad decir que si se utiliza en orden inverso (primero el decoder y luego el encoder) se sigue obteniendo la imagen original pero con un efecto "scrambler" más acusado ( y aun más si se aplican dos decodificaciones y dos codificaciones seguidas).

El decoder está implementado siguiendo el algoritmo oficial pero existe una forma de mejorarlo en velocidad a costa de complicarlo bastante (puntero flotante usando dos funciones según sea el dato del stream mayor de 127 o menor de 128).

El encoder tiene una optimización respecto al algoritmo oficial que consiste en ir moviendo los bytes del buffer al mismo tiempo que se está realizando la búsqueda del byte actual del stream.

Código: Seleccionar todo

ORG &8000

encoder   LD DE,&C000      ;Puntero inicio del stream
   LD HL,&9000      ;Puntero tabla de 256 bytes en &90xx

rep1   LD (HL),L      ;Generador de la tabla
   INC L
   JR NZ,rep1

   LD B,L         ;B=0 valor inicial primera posicion tabla
rep2   LD A,(DE)
   CP B         ;Compara Byte del stream con primer Byte de la tabla
   JR Z,zero
   LD (HL),A      ;Move-to-Front
   
rep3   INC L
   LD C,(HL)
   LD (HL),B
   LD B,C
   CP B
   JR NZ,rep3

zero   LD A,L         ;L contiene el byte codificado
   LD L,0         ;HL apunta de nuevo a la primera posicion de la tabla
   LD (DE),A
   INC E
   JR NZ,rep2
   INC D
   JR NZ,rep2
   RET

Código: Seleccionar todo

ORG &8050

decoder   LD DE,&C000      ;Puntero inicio del stream codificado
   LD HL,&9000      ;Puntero tabla de 256 bytes en &90xx

rep4   LD (HL),L      ;Generador de la tabla
   INC L
   JR NZ,rep4

   LD B,L         ;B=0 valor inicial primera posicion tabla
rep5   LD A,(DE)
   CP L         ;Index es 0?
   JR Z,cero

rep6   INC L
   LD C,(HL)
   LD (HL),B
   LD B,C
   CP L
   JR NZ,rep6

   LD L,0
   LD (HL),B      ;Move-to-Front del byte decodificado

cero   LD A,B
   LD (DE),A
   INC E
   JR NZ,rep5
   INC D
   JR NZ,rep5
   RET


Si encontrais alguna optimización en velocidad no dudéis en decirlo, please.

Un saludo.
Última edición por Urusergi el Dom 14 Oct , 2012 11:23 pm, editado 3 veces en total.

Avatar de Usuario
Artaburu
Trasteador
Trasteador
Mensajes: 6582
Registrado: Vie 07 Oct , 2005 6:18 pm
Ubicación: En tu pantalla

Re: Algoritmo Move-to-Front

Mensajepor Artaburu » Lun 10 Sep , 2012 12:33 am

Pero qué interesante, Urusergi. No tenía ni idea de estas técnicas me voy a informar un poco y hacer alguna prueba a ver.
Muchas gracias por compartirlo.
Salu2,
Arta

Avatar de Usuario
6128
Moderador
Moderador
Mensajes: 6302
Registrado: Lun 12 Dic , 2005 6:08 pm

Re: Algoritmo Move-to-Front

Mensajepor 6128 » Lun 10 Sep , 2012 12:45 pm

Creo que entiendo el concepto pero... ¿nos podéis explicar con palabras simples a los que no sabemos del tema qué es lo que hace exactamente el algoritmo?

Avatar de Usuario
Artaburu
Trasteador
Trasteador
Mensajes: 6582
Registrado: Vie 07 Oct , 2005 6:18 pm
Ubicación: En tu pantalla

Re: Algoritmo Move-to-Front

Mensajepor Artaburu » Lun 10 Sep , 2012 3:29 pm

En pocas palabras (no me da par más, jeje) lo que hace es coger una ristra de datos (bytes) e ir haciendo una tabla ordenada según las apariciones de esos bytes. Sin entrar en descripciones rarunas, si fuese una cadena de texto basada en el alfabeto, lo que hace es recorrerla y según las letras van a apareciendo, va ordenando el alfabeto y, en la cadena de texto, apunta a la nueva posición de la letra en el alfabeto.

alfabeto inicial: abcd
cadena de texto "abbbacdd" -> 01110233, según la posición de las letras en el alfabeto

a: Posición 0
Alfabeto nuevo: abcd
b: Posición 1
Alfabeto nuevo: bacd
b: Posición 0:
Alfabeto nuevo: bacd
b: Posición 0:
Alfabeto nuevo: bacd
a: Posición 1:
Alfabeto nuevo: abcd
c: Posición 2:
Alfabeto nuevo: cabd
d: Posición 3:
Alfabeto nuevo: dcab
d: Posición 0:
Alfabeto nuevo: dcab

Con esto entonces, el resultado es:
01001230
que traducido al último alfabeto es: "dcddcabd"

Esta cadena numérica parece que consigue que mejores ratios de compresión en algunos casos.

Igual me he colado en lo que entiendo que hace el algoritmo move to front, que he estado mirando algunos ejemplos en internet y es posible que no haya entendido bien :D
Salu2,

Arta

Avatar de Usuario
6128
Moderador
Moderador
Mensajes: 6302
Registrado: Lun 12 Dic , 2005 6:08 pm

Re: Algoritmo Move-to-Front

Mensajepor 6128 » Lun 10 Sep , 2012 3:41 pm

Gracias por la explicación, Arta.

Urusergi
Megaforero
Megaforero
Mensajes: 301
Registrado: Sab 25 Feb , 2006 5:45 pm

Re: Algoritmo Move-to-Front

Mensajepor Urusergi » Lun 10 Sep , 2012 11:38 pm

Si señor, la explicación es correcta.

Lo primero que se nota es que la nueva ristra de datos casi siempre contendrá mayor cantidad de numeros bajos, de modo que si programamos un compresor que tenga en cuenta ese detalle logrará compactar mas que antes de aplicar el algoritmo.

Algunos sistemas de compresión se pueden beneficiar de esta técnica, como pueden ser los basados en códigos gamma-delta-omega, huffman, d-gap, rle, golomb, etc
Sin embargo los compresores "serios" basados en las técnicas más modernas y complejas les ocurre lo contrario, incluso llega a empeorar la compresión :-k

En resumidas cuentas los algoritmos Move-to-Front y Burrows–Wheeler sirven para que los compresores más modestos puedan "dar la talla" :-s

Urusergi
Megaforero
Megaforero
Mensajes: 301
Registrado: Sab 25 Feb , 2006 5:45 pm

Re: Algoritmo Move-to-Front

Mensajepor Urusergi » Lun 15 Oct , 2012 12:13 am

Muy buenas!

Aquí estoy de vuelta con un par de rutinillas referentes a la compresión de pantallas...

La primera está relacionada con el extraño sistema de ordenación de lineas del CPC. Siempre tuve la sensación de que los compresores tendrían más efectividad si ponemos las lineas en orden... y sí, después de hacer una cuantas pruebas puedo confirmar que se logra mayor compresión, hasta el punto de merecer la pena aunque tengamos que incorporar la rutina de codificación pertinente.

Código: Seleccionar todo

ORG &5F00

decoder   LD HL,&C000
   LD DE,&6000
   LD A,25

rep1   LD BC,&0050

   LDIR

   LD BC,&07B0
   ADD HL,BC
   JR NC,rep1
   LD BC,&C050
   ADD HL,BC
   DEC A
   JR NZ,rep1

   RET

Código: Seleccionar todo

ORG &5F50

encoder   LD HL,&C000
   LD DE,&6000
   LD A,25

rep2   LD BC,&0050
   EX DE,HL
   LDIR
   EX DE,HL
   LD BC,&07B0
   ADD HL,BC
   JR NC,rep2
   LD BC,&C050
   ADD HL,BC
   DEC A
   JR NZ,rep2

   RET


Y en segundo lugar pensé en el no menos extraño orden de los bits cuando nos encontramos en el mode 0... ¿se lograría mayor compresión si colocamos los bits en nibble alto=pixel 0 y nibble bajo=pixel 1? pues va a ser que [-X no se logra mayor compresión, pero de todas formas pongo el código por si pudiera interesar a alguien:

Código: Seleccionar todo

ORG &8000

   LD HL,&C000
   XOR A

rep   LD B,A
   LD A,(HL)
   ADD A,A
   JR NC,$+4
   SET 4,B
   ADD A,A
   JR NC,$+4
   SET 0,B
   ADD A,A
   JR NC,$+4
   SET 6,B
   ADD A,A
   JR NC,$+4
   SET 2,B
   ADD A,A
   JR NC,$+4
   SET 5,B
   ADD A,A
   JR NC,$+4
   SET 1,B
   ADD A,A
   JR NC,$+4
   SET 7,B
   ADD A,A
   JR NC,$+4
   SET 3,B
   LD (HL),B
   INC L
   JR NZ,rep
   INC H
   JR NZ,rep
   RET


Un saludo.


Volver a “Ensamblador”

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro

La Comunidad Española
ESP Soft, juegos para tu CPC Foro de Amstrad CPC Todos los juegos para CPC en un CD El portal del CPC Web dedicada al Amstrad CPC (utilidades) Información útil para el CPC (talleres) El sitio del Amstrad CPC Mundo CPC Pree Play then any Key CPC Basic