Rutina decompresora exomizer mejorada

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

Moderador: Sir Cilve Sinclair

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Mar Ene 17, 2012 10:20 am

antoniovillena escribió:Hola Metalbrain

Ya están listas las 4 rutinas descompresoras, las tienes aquí:

http://antoniovillena.es/imagenes_foros/deexo_v4.zip


Excelente, a ver si esta tarde las propago por ahí... también me encargaré yo de hacer las versiones que van hacia detrás.

antoniovillena escribió:También habría que cambiar exoopt para meter el marker bit en el primer byte (el primer byte contendría 7 bits).


Osea, que se pierde un bit en la optimización, pasando de ahorrar 2 bits a 1. Si tenemos varios bloques comprimidos, en cuanto el tamaño deje de reducirse en alguno de ellos por culpa de ese bit, ya no merece la pena. Y si deja de reducirse en más de uno, sería contraproducente. No me gusta nada.

Pero... ¿para la versión normal también habría que cambiar algo, o sería todo igual? Esa es posible que sí nos valga.
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
antoniovillena
Nonamed
Mensajes: 1164
Registrado: Dom Ene 09, 2011 8:55 am

Re: Rutina decompresora exomizer mejorada

Mensaje por antoniovillena » Mar Ene 17, 2012 11:27 am

Metalbrain escribió:
Osea, que se pierde un bit en la optimización, pasando de ahorrar 2 bits a 1. Si tenemos varios bloques comprimidos, en cuanto el tamaño deje de reducirse en alguno de ellos por culpa de ese bit, ya no merece la pena. Y si deja de reducirse en más de uno, sería contraproducente. No me gusta nada.

Pero... ¿para la versión normal también habría que cambiar algo, o sería todo igual? Esa es posible que sí nos valga.


No, la versión normal aceptaría directamente la salida de exomizer como antes. Como valer sí que vale. El problema que veo es que al salir de la rutina HL apunta al último byte del stream actual y no al siguiente. Yo prefiero que apunte al siguiente pero vamos la decisión es tuya.

En cuanto a la versión optimizada estoy de acuerdo contigo. El ahorro realmente no es de un byte sino de 7 bits, o dicho de otra forma, el 87.5% de las veces habrá un ahorro de un byte y el 12.5% restante no. Lo peor es que hay que modificar el exoopt y no sería compatible con los streams procesados con el exoopt antiguo.

Edito: Acabo de comprobarlo y no funcionaría en ninguno de los dos casos porque se altera el stream de literales (LDI y LDIR) así que perdona por sugerirte algo sin haberlo comprobado.
Imagen

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Mar Ene 17, 2012 12:08 pm

antoniovillena escribió:El ahorro realmente no es de un byte sino de 7 bits, o dicho de otra forma, el 87.5% de las veces habrá un ahorro de un byte y el 12.5% restante no. Lo peor es que hay que modificar el exoopt y no sería compatible con los streams procesados con el exoopt antiguo.


Y esto si solo hay un bloque de datos comprimidos, si hay dos solo se ahorra el byte el 76,5625% de las veces (y además el 1,5625% de las veces perderíamos un byte), y conforme añadimos más bloques comprimidos, más empeoran las probabilidades. Pero vamos, que esto es tontería discutirlo porque ya se ha visto que no funciona :mrgreen:
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Mar Ene 17, 2012 6:28 pm

Metalbrain escribió:Tampoco es que tenga una web dedicada, tengo el archivo "exo_v3.zip" y supongo que podría hacer un "exo_v4.zip" con las optimizaciones. Para esto habría que incluir las optimizaciones en todas las versiones. Ahora mismo, la que has cambiado es la optimizada simple, ¿no? También sería conveniente hacer las versiones hacia atrás de las rutinas normales (no optimizadas) para mandarselas a Magnus Lind y que las incluya en la siguiente versión oficial.


Ya están listas (son las mismas, pero con mi formato original, incluyendo los comentarios del principio y sin usar hexadecimal, más que nada para que sea más compatible):
http://www.speccy.org/metalbrain/exo_v4.zip

Y le he mandado a Magnus las versiones normales (incluyendo con backwards).
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
antoniovillena
Nonamed
Mensajes: 1164
Registrado: Dom Ene 09, 2011 8:55 am

Re: Rutina decompresora exomizer mejorada

Mensaje por antoniovillena » Mar Ene 17, 2012 7:10 pm

Metalbrain escribió:Ya están listas (son las mismas, pero con mi formato original, incluyendo los comentarios del principio y sin usar hexadecimal, más que nada para que sea más compatible):
http://www.speccy.org/metalbrain/exo_v4.zip

Y le he mandado a Magnus las versiones normales (incluyendo con backwards).


Gracias por incluirme en los créditos. Te destrocé todas las tabulaciones pero al menos corregí los ADDs que tenían un sólo operando :D

Edito: He visto los fuentes y tienes mezclados espacios y tabuladores, y creo que son los mismos espacios que yo introduje.
Imagen

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Mié Jul 25, 2012 8:56 pm

Metalbrain escribió:Ya están listas (son las mismas, pero con mi formato original, incluyendo los comentarios del principio y sin usar hexadecimal, más que nada para que sea más compatible):
http://www.speccy.org/metalbrain/exo_v4.zip


Ops! :oops:

Metí la pata al volver a meter los comentarios, incluyendo en la rutina normal (no simple) una línea de la versión antigua que jode toda la descompresión. Ya está corregido, os lo podeis volver a bajar en el mismo enlace.
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
antoniovillena
Nonamed
Mensajes: 1164
Registrado: Dom Ene 09, 2011 8:55 am

Re: Rutina decompresora exomizer mejorada

Mensaje por antoniovillena » Mié Nov 14, 2012 3:05 pm

Urusergi y yo hemos hecho algunas optimizaciones, por lo en breve habrá otra versión. Más información en castellano aquí:
http://www.amstrad.es/forum/viewtopic.php?f=6&t=2608

Y un resumen de los cambios, en inglés, aquí:
http://www.worldofspectrum.org/forums/s ... hp?t=41523
Imagen

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Re: Rutina decompresora exomizer mejorada

Mensaje por na_th_an » Lun Dic 17, 2012 1:56 pm

Una pregunta cuya respuesta creo que será "va a ser que no". Pero a ver si hay suerte:

¿Sería posible comprimir todo un mapa con exomizer y luego descomprimir sólo una pantalla en concreto, sin tener que descomprimir todo el mapa?

Un mapa no es más que una ristra de pantallas, y cada pantalla (descomprimida) son 75 bytes correlativos. ¿Es posible, de alguna forma, generar algún tipo de índice y luego descomprimir sólo los 75 bytes enésimos, siendo "n" el número de pantalla que se quiere obtener?

Haciéndolo a mano (aunque no lo he probado) se me ocurría tener un binario con cada pantalla (muchos binarios de 75 bytes), comprimirlos todos, y pegar luego los binarios comprimidos generando una especie de índice, pero me temo que un binario de 75 bytes por sí solo no comprima demasiado bien, no hay sitio para patrones de repetición .

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Lun Dic 17, 2012 2:10 pm

na_th_an escribió:Una pregunta cuya respuesta creo que será "va a ser que no". Pero a ver si hay suerte:

¿Sería posible comprimir todo un mapa con exomizer y luego descomprimir sólo una pantalla en concreto, sin tener que descomprimir todo el mapa?

Un mapa no es más que una ristra de pantallas, y cada pantalla (descomprimida) son 75 bytes correlativos. ¿Es posible, de alguna forma, generar algún tipo de índice y luego descomprimir sólo los 75 bytes enésimos, siendo "n" el número de pantalla que se quiere obtener?


Efectivamente, la respuesta es NO. La compresión es del tipo LZ, lo cual significa que hay referencias a partes anteriores del archivo. Como mucho podrías hackear el descompresor para que parase antes de tiempo, sin descomprimir los bytes posteriores a los que necesitas. Pero al llegar a la última pantalla, ya necesitarías el buffer completo.

na_th_an escribió:Haciéndolo a mano (aunque no lo he probado) se me ocurría tener un binario con cada pantalla (muchos binarios de 75 bytes), comprimirlos todos, y pegar luego los binarios comprimidos generando una especie de índice, pero me temo que un binario de 75 bytes por sí solo no comprima demasiado bien, no hay sitio para patrones de repetición .


Si los comprimes uno a uno, exomizer no es el compresor más adecuado, ya que tiene una tabla fija (creo recordar que de 26 bytes) al comienzo de cada archivo, para generar tablas de longitudes. En archivos así de pequeños, hay mucha más posibilidad de compresión usando aPLib (pero claro, también es posible que ninguno consiga comprimir si no hay redundancias en el archivo).
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Re: Rutina decompresora exomizer mejorada

Mensaje por na_th_an » Lun Dic 17, 2012 2:17 pm

Perfecto, es la respuesta que necesitaba :) Creo que para lo que quiero hacer mejor me vale con usar una compresión que no necesite tablas. Además, teniendo en cuenta que los datos tienen poca entropía, creo que me sobra con algún tipo de RLE.

Gracias.

Avatar de Usuario
antoniovillena
Nonamed
Mensajes: 1164
Registrado: Dom Ene 09, 2011 8:55 am

Re: Rutina decompresora exomizer mejorada

Mensaje por antoniovillena » Lun Dic 17, 2012 3:07 pm

Desgraciadamente no se puede, a no ser que te pongas a hace malabares. Lo ideal es que el compresor aceptase como entrada una ventana de datos. Se lo propuse hace tiempo a Magnus, pero me dijo que de momento no lo iba a implementar, pero que lo tendría en cuenta. El problema es que los primeros bytes de cada archivo no tienen ventana o diccionario hacia atrás, por lo que se comprimen muy mal. También como te ha señalado Metalbrain no sería óptimo para cada trozo, ya que se emplearía la misma tabla para todos los trozos.

Aunque te puedo decir que lo he usado en un proyecto de esa forma, como te he dicho antes, haciendo malabares. En concreto para la versión sin ROM de CargandoLeches. Se trataba de parchear la ROM 3 del +2A y emplearla en un modo de paginación especial donde el rango 0000-3fff fuese RAM. Cargar en cinta los 16K es muy lento, la versión comprimida es de 12K, también lento. Hacer un XOR con la ROM y comprimirlo ocupaba más de 4K. La mejor opción en ese caso era parchear exoopt, con lo que el tamaño total fue de menos de 1K. Al descomprimir tienes que copiar la ROM junto antes del puntero donde vas a descomprimir, para que lo tome como ventana. La clave del asunto es que para comprimir tienes que concatenar las dos ROMs, la original y la parcheada en un archivo de 32K. Luego con un parche en exoopt te quedas sólo con la parte comprimida que corresponde a los últimos 16K.

Ten en cuenta que para la aplicación que quieres hacer necesitas tener algo de ventana al descomprimir. Si el juego es secuencial puedes tener las 2 ó 3 últimas pantallas almacenadas, con 150-225 bytes hay ventana suficiente para que la compresión sea buena. Si el juego es aleatorio, es bastante más complicado, no te valdría un índice al bistream comprimido. Tendrías que descomprimir desde el principio en un buffer circular de 150-225 bytes hasta llegar a la pantalla en cuestión. Sería igual de lento que descomprimir todo el archivo hasta ese punto, pero usando justo la RAM que necesitas.
Imagen

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Dom Ene 27, 2013 11:48 am

antoniovillena escribió:Urusergi y yo hemos hecho algunas optimizaciones, por lo en breve habrá otra versión. Más información en castellano aquí:
http://www.amstrad.es/forum/viewtopic.php?f=6&t=2608

Y un resumen de los cambios, en inglés, aquí:
http://www.worldofspectrum.org/forums/s ... hp?t=41523


Bueno, pues ya (parece que) ha llegado a su culminación el gran proceso de optimización de exomizer comenzado por Urusergi, y continuado de forma grandiosa por Antonio Villena, con apenas algunas modestas contribuciones mías. Por una parte, los decompresores se han reducido de forma brutal y son un pelín más rápidos, y por otra se han generado versiones alternativas (no tan pequeñas) optimizadas en velocidad, de forma que podemos escoger entre 4 variantes (0 la más pequeña, 3 la más rápida). La variante 1 resulta especialmente atractiva, ya que al precio de entre 3 y 5 bytes, produce una ganancia del 14% de velocidad.

Aparte de eso, el programa optimizador (exoopt) ha sido reescrito desde cero por Antonio Villena, de forma que se le puede pasar como parámetro la velocidad (y dirección, que antes siempres se utilizaba hacia delante) deseada, y generará automáticamente el descompresor necesario (se le pueden incluso introducir varios archivos como parámetros, y generará la versión más simple si no aparecen cadenas de literales y la completa si aparecen). Este nuevo optimizador aparte de lo que hacía antes (invertir el orden de lectura de los bits, y quitar 2 bits redundantes) efectua otros cambios en los datos, que a veces pueden ser contraproducentes (aumenta un pelín el tamaño), pero permiten simplificar más aún los descompresores.

Las nuevas versiones se pueden encontrar aquí:
http://emuscriptoria.svn.sourceforge.ne ... ria/deexo/

y un exoopt ya compilado, aquí:
http://retrolandia.net/foro/showthread. ... =48&page=6
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Jue Feb 14, 2013 5:57 pm

¡Cuidadín! Se ha detectado un bug en las versiones oficiales (no optimizadas) de los descompresores. Magnus seguramente publicará una versión corregida (la 2.07) pronto, hasta entonces podeis pillar las rutinas actualizadas del repositorio:

http://emuscriptoria.svn.sourceforge.ne ... ria/deexo/

Más información aquí:
http://amstrad.es/forum/viewtopic.php?f ... &start=150
SevenuP se escribe con u minúscula y P mayúscula.

Avatar de Usuario
Metalbrain
Freddy Hardest
Mensajes: 592
Registrado: Lun May 07, 2007 8:17 am
Ubicación: Sevilla
Contactar:

Re: Rutina decompresora exomizer mejorada

Mensaje por Metalbrain » Mar Oct 04, 2016 6:39 pm

Hola a todos,

Acabamos de hacer una pequeña nueva release. El código no ha cambiado nada, pero tras ser consultado un par de veces sobre la licencia de las rutinas de descompresión, he decidido licenciarlas bajo la LGPL 2.1 . Los archivos actualizados y la licencia la podeis encontrar aquí:

https://sourceforge.net/p/emuscriptoria ... ree/deexo/
SevenuP se escribe con u minúscula y P mayúscula.

Responder

¿Quién está conectado?

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