Fecha actual Lun Ago 19, 2019 4:45 am

Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Formatos de Archvo Gráficos. Usados para mostrar imágenes principalmente estáticas en pantalla, impresión u otros medios visuales.


Usuarios leyendo este tema: Ninguno

Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 8:30 pm

<<Paso Anterior

NOTA: Para ver el resultado final de todo este esfuerzo, ver lo siguiente:
>> Explicador de GIFs, desde la versión 2013-07-25, 22:24 <<







Necesito determinar la mejor forma para recuperar los valores de los datos de imagen.

Lo primero que debo hacer es evaluar si sería adecuado crear y llenar un arreglo con los valores de la imagen, sin el contenido de los datos protocolares, como son el byte inicial con el tamaño inicial mínimo de código, y los bytes de porción (valores 1 a 255) y final de imagen (valor 0).
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 8:33 pm

He escrito los valores descomprimidos de índices (bytes de color indexado) para nuestra imagen de muestra:
Código: Seleccionar todo
db 1,1,1,1,1, 2,2,2,2,2
db 1,1,1,1,1, 2,2,2,2,2
db 1,1,1,1,1, 2,2,2,2,2
db 1,1,1,0,0, 0,0,2,2,2
db 1,1,1,0,0, 0,0,2,2,2
db 2,2,2,0,0, 0,0,1,1,1
db 2,2,2,0,0, 0,0,1,1,1
db 2,2,2,2,2, 1,1,1,1,1
db 2,2,2,2,2, 1,1,1,1,1
db 2,2,2,2,2, 1,1,1,1,1

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 8:36 pm

Los bytes comprimidos de imagen con la información protocolar GIF son:
Código: Seleccionar todo
MinCodeSize db 2h

NumBytes00000000 db 22
db 0x8C, 0x2D, 0x99, 0x87, 0x2A, 0x1C, 0xDC, 0x33
db 0xA0, 0x02, 0x75, 0xEC, 0x95, 0xFA, 0xA8, 0xDE
db 0x60, 0x8C, 0x04, 0x91, 0x4C, 0x01

db 0x00



En base a estos, podría perfectamente crear un simple programa de decodificar con estos datos codificados estáticamente (y crear una versión de JavaScript generada por el Explicador de GIFs).

Al explicador de GIFs debería configurarlo para que devuelva los valores no protocolares de bytes en formato binario, más que en formato hexadecimal, para poder distinguir fácilmente la manera de separar los códigos comprimidos, durante esta etapa inicial de análisis.

La siguiente instrucción a ejecutar es obtener los códigos no protocolares anteriores en formato binario de bytes.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 8:47 pm

OK

Código: Seleccionar todo
MinCodeSize db 2h

NumBytes00000000 db 22
db 10001100b, 00101101b, 10011001b, 10000111b
db 00101010b, 00011100b, 11011100b, 00110011b
db 10100000b, 00000010b, 01110101b, 11101100b
db 10010101b, 11111010b, 10101000b, 11011110b
db 01100000b, 10001100b, 00000100b, 10010001b
db 01001100b, 00000001b

db 0x00



Ahora quiero darle seguimiento a estos datos para descomprimirlos, por lo menos los primeros 1 a 4 bytes, para ver si concuerdan con los datos originales.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 9:10 pm

Tenemos un tamaño de código mínimo de 2 bits:
Código: Seleccionar todo
MinCodeSize db 2h



Pero por lo que sabemos por todo lo que hemos leído hasta ahora de diferentes fuentes, debemos sumarle 1 a este valor, para tener el tamaño real de bits que usremos.

Así que nuestro tamaño mínimo inicial de código es de 3 bits.

Así que leeremos los primeros 3 bits, del primer byte.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 9:12 pm

Marcamos con asteriscos los 3 bytes a leer:
Código: Seleccionar todo
MinCodeSize db 2h

NumBytes00000000 db 22
db 10001***b, 00101101b, 10011001b, 10000111b
db 00101010b, 00011100b, 11011100b, 00110011b
db 10100000b, 00000010b, 01110101b, 11101100b
db 10010101b, 11111010b, 10101000b, 11011110b
db 01100000b, 10001100b, 00000100b, 10010001b
db 01001100b, 00000001b

db 0x00



Obtenemos el valor 100b, que es 4 en binario.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 10:03 pm

[0000 - No confirmado]

El primer código en el flujo de códigos de los datos de imagen es el código clear, que en este caso es 4.

Por ahora estoy asumiendo lo siguiente para lograr una buena implementación inicial:

Eso significaría que los valores 0 a 3 deben ser los índices de los colores de la paleta.

También significa que el código de fin de datos debe ser el código con valor 5 (valor 5 binario contenido entre 3 y 12 bits).
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 10:22 pm

Necesitamos los pasos de descompresión.

Pasos de descompresión
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Sab Dic 29, 2012 10:46 pm

Ejecutaremos el Paso 0, en virtud de leer el primer código, que es el código clear de 3 bits, 100b (4).

Esto significa que inicializaremos por primera vez nuestra tabla, con los índices de los colores de la paleta, el código clear y el código de fin de información:

Código: Seleccionar todo
TablaIdx[0]=0;
TablaIdx[1]=1;
TablaIdx[2]=2;
TablaIdx[3]=3;
TablaIdx[4]=4;  //Código Clear
TablaIdx[5]=5;  //Código de Fin de Información


Como vemos, tal como en el LZW estándar, los primeros valores de la tabla son siempre el "alfabeto" original de "caracteres ASCII individuales" de nuestros datos.

Tal vez la intención de usar una paleta de 256 colores es no solo comprimir adicionalmente los datos, de 3 bytes por pixel a solo 1, sino también emular dichos caracteres ASCII individuales para nuestro diccionario inicial, y más aún parcialmente si la paleta tiene menos de 256 posiciones.

Para el contexto de nuestra imagen GIF, dicho "alfabeto" son los valores de la paleta de colores (posible desde 0 hasta 255, en potencias de 2) y los código clear y de fin de información.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 3:14 pm

Ahora ejecutaremos el Paso 1. Ya que el primer código que leímos era el código clear, ahora leeremos los siguientes 3 bits, y así podríamos seguir sucesivamente leyendo de 3 bits en 3 bits.

No sé si para avanzar el número de bits se necesita construir la tabla, o si esta solo serviría para descomprimir, pero una vez que sabemos cómo leer los bits en grupos, lo siguiente es saber cómo avanzar el número de bits.

Lo más conveniente en este momento sería determinar en qué momento exactamente y bajo qué condiciones debemos avanzar el número de bits.

Voy a crear un programa simple de muestra que no hará nada más que leer los bits de 3 en 3, y veremos en qué punto esto deja de coincidir con la tabla de nuestro artículo. Aunque desafortunadamente la tabla de dicho artículo debería ser completada con esta información, ya que solo tenemos hasta la tabla 6 para mostrar cómo funciona esto.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 3:32 pm

Aparentemente, el primer código de nuestro flujo de índices, el primero después del código clear será un índice simple, uno que simple y sencillamente hará referencia a un color de forma directa, de un índice individual.

Subsiguientes pasos se volverán más complicados pero dependen de este pequeño paso inicial; aunque estoy trabajando en entenderlos, y estoy avanzando rápidamente en este momento.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 5:20 pm

Nuestros datos de imagen comprimidos se convertirían en los siguientes bits, si no tomamos en cuenta el incremento de bits (que obviamente no debería ser el estado final de estos datos):
Código: Seleccionar todo
MinCodeSize db 2h

NumBytes00000000 db 22
db 10001***b, 00101101b, 10011001b, 10000111b
db 00101010b, 00011100b, 11011100b, 00110011b
db 10100000b, 00000010b, 01110101b, 11101100b
db 10010101b, 11111010b, 10101000b, 11011110b
db 01100000b, 10001100b, 00000100b, 10010001b
db 01001100b, 00000001b

db 0x00




Solamente he podido hacer concordar los siguientes bits con las primeras cuatro entradas de flujos de códigos, porque la siguiente no concuerda para nuestro número de bits, y no sé cómo aumentar un bit más en este caso, así que esto es lo que debería probablemente entender a continuación (si es que no hay algún otro detalle no obvio en medio):
Código: Seleccionar todo
MinCodeSize db 2h

NumBytes00000000 db 22
db 10)(001)***b, 0(010)(110)(1b,



Que se traduce a:
001b -- 1
110b -- 6
110b -- 6
010b -- 2
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 7:25 pm

OK

Determinar el número de bits actualmente requeridos para el código y saber cuándo aumentar el número de bits es un gran ejemplo de una situación en la que hay un algoritmo preestablecido, fijo y conocido de antemano para tomar esa decisión, que no está indicado en los datos porque es siempre el mismo algoritmo.






Para calcular el número de bits necesarios, sabemos que comenzamos leyendo el primer byte del flujo de datos gráficos y le sumamos 1.

Pero para saber cuándo aumentarlos, necesitamos simplemente elevar 2 por el número de bits originales (sin sumarle 1).

Una vez que leemos ese número de paquetes de bits, aumentamos la cuenta de bits requeridos actuales, y elevamos 2 por esta nueva potencia, la cual será el número de códigos de grupos de bits a leer antes de volver a aumentar la cuenta de bits, y determinar el número de paquetes/códigos de N bits nuevamente.
____________________________________________

Es decir que si el primer byte de nuestros datos gráficos nos indica que comenzamos con un mínimo de 2 bits, tenemos que elevar 2 a la potencia 2 (que es 4). Estos significa que tendremos que aumentar la cuenta de bits una vez que hayamos procesado 4 códigos, de 3 bits cada uno.

Ahora pasamos a sumarle 1 a la cuenta inicial de bits (que ahora será 3). Para saber cuántos códigos debemos leer antes de aumentar nuevamente el número de bits por código, elevamos 2 a la 3 (que es 8), lo que significa que aumentaremos el tamaño en bits después de leer 8 códigos, de 4 bits cada uno.

La cuenta de códigos incluye el primer código, que es el código clear así que hay que tener eso en cuenta y leer el código clear normalmente, o intentar saltarlo en el código (tal vez después de asegurarse que está allí).
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 8:13 pm

Lo siguiente que debo hacer es determinar qué significa descomprimir estos primeros 4 códigos que hemos obtenido, para desde aquí generalizar finalmente todo o una primera parte de nuestro código de descompresión de LZW para GIF:

Código: Seleccionar todo
001b -- 1
110b -- 6
110b -- 6
010b -- 2

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 9:10 pm

Creamos un programa de viruta para nuestra imagen de muestra escrito en JavaScript:

LZW de GIF a Pixeles Indexados (a Índices de los Códigos del Diccionario LZW)
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 9:28 pm

El código más simple posible para comenzar, es este. Este código no está completo, está incompleto y no lo usaremos al final así como está, sino que solo muestra la idea básica de lo que necesitamos hacer para recorrer y procesar los diferentes bytes de nuestros datos de imagen, al nivel más fundamental posible:

Código: Seleccionar todo
//Obtener los datos gráficos de una imagen GIF individual:
///
 var imgDataArr=new Array(
 2,
 22, parseInt("10001100b",2), parseInt("101101b",2), parseInt("10011001b",2), parseInt("10000111b",2), parseInt("101010b",2), parseInt("11100b",2), parseInt("11011100b",2), parseInt("110011b",2), parseInt("10100000b",2), parseInt("10b",2), parseInt("1110101b",2), parseInt("11101100b",2), parseInt("10010101b",2), parseInt("11111010b",2), parseInt("10101000b",2), parseInt("11011110b",2), parseInt("1100000b",2), parseInt("10001100b",2), parseInt("100b",2), parseInt("10010001b",2), parseInt("1001100b",2), parseInt("1b",2),
 0
 );


//Obtener el tamaño inicial de los códigos en bits:
///
 var initCodeSZ=imgDataArr[0];


//Generar el número actual de bits que
//usaremos para calcular una potencia y usarlo como el número
//de códigos del tamaño actual que leeremos antes de
//aumentar el tamaño en bits de nuestros códigos:
///
 var CodeSZ=initCodeSZ;



//Convertir el tamaño inicial del número de bits
//que usaremos realmente para generar los
//códigos de descompresión:
///
 var ourCodeSZ=initCodeSZ+1;


//Convertir nuestro tamaño de código en el número de
//códigos de "ourCodeSZ" bits que leeremos antes de
//aumentar el número de bits por código:
///
 var numCodes=Math.pow(2, CodeSZ);










//Esta función convertirá los códigos "empacados"
//que ocupan más de 1 byte, en códigos individuales
//de hasta 12 bits en un nuevo arreglo:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Crear el arreglo a devolver:
  ///
   var toRet=new Array();


  //Apuntar justo después del byte que contiene
  //el tamaño mínimo de código en bits:
  ///
   var i=1;



  //Ahora necesitamos un bucle (con un bucle anidado)
  //para leer la cuenta de bytes y procesar los bytes
  //de esa cuenta, y detenernos cuando el byte de cuenta de bytes sea 0,
  //de acuerdo a la especificación GIF:
  ///
   var c=0;
   while( (c=imgStream[i]) != 0 )
   {
    i++;
     while(c--)
     {
      i++;
     }
   }



  return toRet;
 }

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mar Ene 01, 2013 9:58 pm

Ahora agregamos una nueva función para obtener bits y determinar si deberíamos seguir leyendo byts de otro(s) byte(s), y también constantes con máscaras de bits para evitar tener que calcular dichas máscaras con funciones:

Código: Seleccionar todo
//Cachearemos las máscaras de bits necesarias para que podamos saber
//cómo preservar hasta 12 bits:
///
 var _bm=new Array();
     _bm[0]  = parseInt("000000000000b", 2);
     _bm[1]  = parseInt("000000000001b", 2);
     _bm[2]  = parseInt("000000000011b", 2);
     _bm[3]  = parseInt("000000000111b", 2);
     _bm[4]  = parseInt("000000001111b", 2);
     _bm[5]  = parseInt("000000011111b", 2);
     _bm[6]  = parseInt("000000111111b", 2);
     _bm[7]  = parseInt("000001111111b", 2);
     _bm[8]  = parseInt("000011111111b", 2);
     _bm[9]  = parseInt("000111111111b", 2);
     _bm[10] = parseInt("001111111111b", 2);
     _bm[11] = parseInt("011111111111b", 2);
     _bm[12] = parseInt("111111111111b", 2);














//Esta función devuelve un arreglo de 2 elementos.
//El primer elemento del arreglo es el valor de los
//bits especificados, como si estuvieran ubicados
//desde el bit 0; y el segundo elemento del arreglo, si no es 0,
//es el número de bits que deberíamos leer del
//siguiente byte o bytes.
//
//Los bytes pueden estar ordenados como en Big Endian
//o como en Little Endian para que esta función de lectura de bytes
//funcione correctamente, byte por byte, y depende de
//código externo el leer los bytes en su orden correcto:
///
 function getByteBits(ourByte, startBit, bitCount)
 {
  var toRet=new Array();

  //Preservar solo los primeros 3 bits de startBit,
  //porque solo podemos especificar los bits 0-7 para StartBit:
  ///
   startBit&=parseInt("00000111b", 2);
   bitCount&=parseInt("00000111b", 2);

  //Preservar solo los primeros 8 bits de ourByte,
  //porque solo debemos usar los bits 0-7:
  ///
   ourByte&=parseInt("11111111b", 2);


  //Moveremos tantos bits a la derecha
  //como startBit nos indica:
  ///
   ourByte>>=startBit;


  //Ahora preservar solo el número de bits que
  //bitCountMask nos indica:
  ///
   ourByte&=_bm[bitCount];
   toRet[0]=ourByte;


  //Determinar si no hemos guardado todos los bits, o
  //si terminamos:
  ///
   toRet[1]=0;
   var cc=startBit+bitCount;
   if(cc>7)          //Ver en qué posición de bits deberíamos empezar
   toRet[1]=cc-8;    //Si excedemos 0-7, restamos 8 para obtener nuestros bits restantes;
                     //si no lo excede, simplemente devolmemos 0.


  return toRet;
 }

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mié Ene 02, 2013 9:56 am

Ahora he completado adicionalmente la función que desempaca los códigos de los datos de imagen.

Lo que esta función hace ahora es tener la estructura correcta de bucle que le permite determinar qué bits debe leer, y cuándo avanzar el byte actual (no lo avanza a menos que se haya posicionado en todos los grupos de bits de los códigos de ese byte).

La función es capaz de leer la cuenta de bytes para un grupo de bytes, capaz de aumentar y recalcular el número de bits requeridos para los códigos, recorrer todos los bytes del grupo, y detenerse cuando se llega a un byte de cuenta con valor de 0.

Lo que este código todavía no puede hacer es unir bits entre 2 o más bytes, y menos si dichos bytes están separados por un byte de cuenta. Tampoco puede reiniciar el número de bits cuando se alcanza el límite de valor de 12 bits, reiniciando todo.

Así que la función no está completa, pero empieza a funcionar al menos para imágenes pequeñas y simples.

Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes-1;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=_ourCodeSZ;



  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;

       //Iterate through all bytes of this run:
       ///
        while(  c!=0  )
        {
             rr=getByteBits(imgStream[i], startBit, _ourCodeSZ);
             toRet[toRet.length]=rr[0];

             startBit+=_ourCodeSZ;
             startBit&=_bm[_ourCodeSZ];

             if(startBit>7 || (c-_ourCodeSZ)<=0)
             {
              c--;
              i++;
             }

             startBit&=7;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }
        }
   }

  return toRet;
 }


Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mié Ene 02, 2013 5:29 pm

La siguiente es otra versión de la misma función, pero que también toma en cuenta el número de bits que ha procesado. Parece más completa pero no sabemos si tiene más de lo necesario, haciéndola más ineficiente e inexacta; así que necesitamos eventualmente decidirnos por esta variación de la función o por la anterior, y desde allí tomar un camino.

Pero creo que voy a empezar por esta última:
Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;



  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;
    c--; //Convert from count mode to addressing mode

       //Iterate through all bytes of this run:
       ///
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
//             rr=getByteBits(imgStream[i], startBit, _ourCodeSZ);
//             toRet[toRet.length]=rr[0];
             toRet[toRet.length]=startBit;


             startBit+=_ourCodeSZ;
             startBit&=_bm[_ourCodeSZ];

             if(startBit>7)
             {
              startBit&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }
        }
   }
  return toRet;
 }


Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mié Ene 02, 2013 5:52 pm

Aquí tengo una tercera versión de la misma función, que ha duplicado la intención de la variable startByte en la nueva variable sB.

La intención es llevar un control correcto de los límites de bits en bytes con sB, pero al mismo tiempo simplemente llevar un número de bit desde 0 hasta N>7 para luego simplemente calcular fácilmente el byte que contiene el bit inicial a leer para un nuevo código.

En este punto, después de 3 intentos de función, se puede ver que leer bits arbitrariamente de esta forma es usualmente muy fácil, pero los GIFs son un caso más complicado y que requiere un algoritmo diferente, porque debemos recordar que cada 255 bytes de datos de códigos empacados, hay 1 byte de por medio, así que no podemos simplemente usar este algoritmo para calcular bytes a partir de números acumulados de bits mayores a 8.

Aun si contabilizáramos los 8 bits de las cuentas de bytes cada 255 bytes, ¿cómo determinaríamos eficientemente y fácil de leer y mantener, una manera de leer 2 o más bytes con bits empacados para un mismo código, pero que tienen un byte de cuenta entre ellos?

Ese es exactamente el problema que en este momento no nos deja consolidar el resto de nuestras ideas, y que por lo tanto es lo que tenemos que resolver a pequeña escala para después integrarlo en esta función.

Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;



  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;
    c--; //Convert from count mode to addressing mode

       //Iterate through all bytes of this run:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
//             rr=getByteBits(imgStream[i], startBit, _ourCodeSZ);
//             toRet[toRet.length]=rr[0];
             toRet[toRet.length]=startBit;


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;
             sB&=_bm[_ourCodeSZ];

             if(sB>7)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }
        }
   }
  return toRet;
 }


Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mié Ene 02, 2013 6:18 pm

OK

Tenemos los 2 siguientes problemas:

  • Determinar la posición de bits para cada grupo de 255 bytes (de 0 a 2039).

  • Leer códigos empacados con un byte de cuenta de por medio.

Para el primer problema: En 255 bytes tenemos hasta 2040 bits posibles. Lo que podemos hacer es poner a 0 la variable startBit (la que usamos ahora para direccionar los 2040 bits), ponerla a 0 cada vez que salimos del bucle interno (que significa ponerla a 0 cada 255 bytes y cada vez que leamos una nueva cuenta).

Entonces, este valor de bits lo convertiremos a su vez en un valor de offset de byte a leer y también en un valor de bit inicial a leer desde este byte. Y a este valor de bytes, le agregaremos la dirección/offset global en que estamos actualmente en el archivo, justo después del último byte de cuenta leído actualmente.

Para el segundo problema: Necesitamos hacer uso correcto de nuestra función getByteBits(), que es capaz de decirnos si es necesario que sigamos leyendo y agregando bits a un mismo código (al último código LZW), y esto lo hace diciéndonos cuántos bits restantes no nos devolvió, después de devolvernos todos los bytes posibles del byte actual.

Debemos usar este valor de forma tal que podamos seguir leyendo bits de bytes subsiguientes, tanto de bytes contiguos como de bytes con bytes de cuenta y reanudar la incluso después de dos corridas del bucle más interno.

Y también necesitamos ser capaces de evitar leer erróneamente más allá del final de los datos válidos en caso de que el último código existente en la imagen actual use menos bits que los que normalmente debería para su tamaño de bits.

___________________________________________________________
___________________________________________________________
___________________________________________________________
___________________________________________________________
También debemos recordar que todavía necesitamos saber cómo resetear todo de forma correcta cuando encontramos un código clear, y también cuando llegamos al valor límite de 12 bits (puede que necesitemos crear imágenes GIF considerablemente grandes para probar estos casos).
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Mié Ene 02, 2013 7:19 pm

Con todo lo que hemos hecho hasta ahora, nos hemos dado cuenta que no es necesario expandir el contenido de los códigos de nuestro diccionario LZW, para poder extraerlos a todos correctamente, en forma de índices de dicho diccionario, de nuestros datos de imagen.

Así que primero resolvimos el problema de aumentar el tamaño de los bits, avanzar los bytes solo cuando hemos recuperado todos los bits del byte actual; y es ahora cuando necesitamos resolver el problema de de hecho desempacar los bits, y no solo calcular los bits a leer (pero sin hacerlo).

También, ahora que hemos definido hasta 3 caminos posibles para nuestra función de desempacado de códigos LZW y que hemos identificado varios detalles a resolver e implementar, debemos insistir más fuertemente en este momento en lograr extraer los códigos de manera sostenida, comenzando por los códigos de nuestra imagen simple, con pocos problemas a resolver de inmediato, de los que ya mencionamos.

Así que ahora que puedo aumentar el tamaño de los códigos en bits, insistiré en continuar hasta lograr extraer correctamente los primeros 4 códigos, y desde ahí ver si puedo seguir de forma estable, y corregir de forma acorde.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Jue Ene 03, 2013 10:10 pm

Ahora que tengo bastantes detalles identificados, lo siguiente que debo hacer es devolver los códigos en el arreglo de la función de desempacado de códigos LZW.

Pero como hemos visto, a veces, casi siempre, es necesario tomar bits de más de 1 byte.

Eso significa que voy a empezar por recuperar los bits que estén solo en el byte actual.

El resto los voy a ignorar en el momento en que sume y sobrepase cualquier otro bit que no esté en ese byte, efectivamente truncando los bits de mayor peso del código.

Pero si logro obtener los bits de menor peso de forma correcta, entonces habré puesto las bases para el código capaz de unir los bits restantes a añadir desde otro byte.

Voy a devolver dichos valores en forma de cadenas binarias, de 1's y 0's, para comparar si los bits que vaya obteniendo son correctos, y no pasaré a hacer otra cosa hasta que logre comenzar por recuperar la primera parte de los códigos.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Jue Ene 03, 2013 10:51 pm

Con el código más actual que tenemos, solo puedo recuperar correctamente los primeros 4 códigos, pero no los siguientes, que es el momento en el que aumento el número de bits para cada código LZW.

Este obviamente es un problemna en el que el momento en el que reajusto el tamaño del código y otras variables no es adecuado para el momento en el que intento leer de hecho los bits del código actual, y el resultado es que una vez que aumento el tamaño del código, los bits que recupero ya no son correctos desde ese punto.

Ahora tengo que reordenar el código para que todos estos detalles funcionen como deben, y para poder determinar correctamente los bits subsiguientes a leer, tanto en ubicación como en número.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Jue Ene 03, 2013 11:00 pm

Básicamente, desde el punto de vista de descuento de códigos y de lectura del código, tenemos este bucle:

Código: Seleccionar todo
while(---)
{
 arregloIndices[final]=obtenerBitsCodigo(byteActual, bitInicial, tamañoCod);

 bitInicial+=tamañoCodigo;
 bitInicial&=mascarabits[tamañoCodigo];
 if(bitInicial>7)
 {
  bitInicial&=7;
  byteActu++;
 }



 numCodigos--;
 if(numCodigos==0)
 {
  tamañoCodigo++;
  numCodigos=Math.pow(2, tamañoCodigo);
 }
}

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 5:18 am

OK

La siguiente es la función de desempacado de bits corregida y reordenada no solo para avanzar a través de los bytes, sino que para obtener la parte inicial de nuestro código LZW (aunque todavía no nos sirve para combinar los bits de otro(s) byte(s) en caso de que el código LZW esté usando bits de más de un byte).

Nota: en este momento, tal como este código muestra con la siguiente línea de código:

Código: Seleccionar todo

//    c--; //Convertir de modo de cuenta a modo de direccionamiento



Todavía no sabemos cómo descartar o incluir el último código. Para eso, tal vez necesitamos construir de hecho la tabla de códigos, o tal vez en caso de que tengamos menos bits que los necesarios para el último código.

Pero en este punto, la intuición me dice que, siempre y cuando no sobrepase el límite de los datos, agregar un último código potencialmente espúreo al final de la tabla (que obviamente nunca será usado en lugar de ser realmente espúreo) no tendrá ningún efecto adverso desde el punto de vista estrictamente funcional para la descompresión.


Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;


  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;
//    c--; //Convert from count mode to addressing mode

       //Iterate through all bytes of this run:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
//             rr=getByteBits(imgStream[i], startBit, _ourCodeSZ);
//             toRet[toRet.length]=rr[0];
//             toRet[toRet.length]=startBit;
//             toRet[toRet.length]=sB;
             toRet[toRet.length]=getByteBits(imgStream[i], sB, _ourCodeSZ)[0].toString(2);


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;
             //sB&=7;

             if(sB>7 || c<=0)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }
        }
   }
  return toRet;
 }

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 6:26 am

El siguiente paso que hemos resuelto es unir los códigos de hasta 2 bytes (contiguos), y para eso hemos una variable llamada doneCodeSZ que en estas condiciones calcula correctamente el número de bits restantes a leer, que obviamente luego de leer algunos bits del código LZW parcial, no siempre es 3.

Lo siguiente que necesitamos hacer es calcular correctamente la posición del bit inicial para el siguiente bit, ya que este nuevo código así como está solo funciona mientras no haya cambios "sustanciales" en el tamaño de los códigos en bits:

Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;


  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;

   var rr=new Array(0,0);

   var doneCodeSZ=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;

       //Iterate through all bytes of this run:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
             doneCodeSZ=_ourCodeSZ;
             rr=getByteBits(imgStream[i], sB, _ourCodeSZ);
             toRet[toRet.length]=rr[0];
             doneCodeSZ=_ourCodeSZ-rr[1];
             if(rr[1])
             {
//              rr=getByteBits(imgStream[i+1], 0, 1);
////              toRet[toRet.length-1]|=(rr[0]<<(rr[1]|7));
////              toRet[toRet.length-1]|=(rr[0]<<_ourCodeSZ);
////              toRet[toRet.length-1]|=(rr[0]<<_CodeSZ);
////              toRet[toRet.length-1]=(rr[0]);
//              toRet[toRet.length-1]|=(rr[0]<<2);

              rr=getByteBits(imgStream[i+1], 0, doneCodeSZ);
              toRet[toRet.length-1]|=(rr[0]<<2);
             }


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;

             if(sB>7 || c<=0)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }

        }
   }
  return toRet;
 }

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 7:08 am

Esta función actualizada puede extraer correctamente la mayoría de los códigos:
Código: Seleccionar todo
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;


  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;

   var rr=new Array(0,0);

   var doneCodeSZ=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;

       //Iterate through all bytes of this run:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
             doneCodeSZ=_ourCodeSZ;
             rr=getByteBits(imgStream[i], sB, _ourCodeSZ);
             toRet[toRet.length]=rr[0];

            //The number of bits already read by us
            //is given by the full code size minus
            //the bits we haven't read yet:
            ///
             doneCodeSZ=_ourCodeSZ-rr[1];
             if(rr[1])
             {
              rr=getByteBits(imgStream[i+1], (sB+doneCodeSZ)&7, doneCodeSZ);

              //The number of bits to move left the
              //new bits to concatenate from the other
              //byte should be the bits we had already read.
              ///
               toRet[toRet.length-1]|=(rr[0]<<doneCodeSZ);
//               toRet[toRet.length-1]&=_bm[_ourCodeSZ];
             }


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;

             if(sB>7 || c<=0)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }

        }
   }
  return toRet;
 }


Pero los siguientes son los códigos correctos que deberíamos obtener. Los códigos que se devuelven erróneamente por la función anterior están marcados con un asterisco, así que necesitamos identificar dónde está el error o los errores. Los códigos con doble asterisco se devuelven erróneamente incluso si intentamos poner a 0 con AND los bits que están más allá del tamaño de nuestro código:
Código: Seleccionar todo
0.  100    4  (0,2) ? - 3
1.  001    1  (3,5) A - 3
2.  110    6  (6,0) B - 3
3.  110    6  (1,3) C - 3
4.  0010   2  (4,7) D - 4
5.  1001   9  (0,3) E - 4
6.  1001   9  (4,7) F - 4
7.  0111   7  (0,3) G - 4
8.  1000   8  (4,7) H - 4
9.  1010   10 (0,3) I - 4
10. 0010   2  (4,7) J - 4
11. 1100   12 (0,3) K - 4
12. 00001  1  (4,0) L - 5*
13. 01110  14 (1,5) M - 5
14. 01111  15 (6,2) N - 5
15. 00110  6  (3,7) O - 5
16. 00000  0  (0,4) P - 5
17. 10101  21 (5,1) Q - 5
18. 00000  0  (2,6) R - 5
19. 01010  10 (7,3) S - 5**
20. 00111  7  (4,0) T - 5*
21. 10110  22 (1,5) U - 5
22. 10111  23 (6,2) V - 5**
23. 10010  18 (3,7) W - 5
24. 11010  26 (0,4) X - 5
25. 00111  7  (5,1) Y - 5
26. 01010  10 (2,6) Z - 5
27. 11101  29 (7,3) a - 5**
28. 001101 13 (4,1) b - 6
29. 011000 24 (2,7) c - 6
30. 001100 12 (0,5) d - 6
31. 010010 18 (6,3) e - 6**
32. 010000 16 (4,1) f - 6
33. 100100 36 (2,7) g - 6
34. 001100 12 (0,5) h - 6
35. 000101 5  (6,3) i - 6
36. --0000 0  (4-7) j - 6



db BBAAA???b, DDDDCCCBb, FFFFEEEEb, HHHHGGGGb
db JJJJIIIIb, LLLLKKKKb, NNMMMMMLb, OOOOONNNb
db QQQPPPPPb, SRRRRRQQb, TTTTSSSSb, VVUUUUUTb
db WWWWWVVVb, YYYXXXXXb, aZZZZZYYb, bbbbaaaab
db ccccccbbb, eeddddddb, ffffeeeeb, ggggggffb
db iihhhhhhb, jjjjiiiib

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 8:09 am

OK

Finalmente he logrado concatenar los bits de hasta 2 bytes, siempre y cuando estos sean contiguos (sin un byte de cuenta entre ellos).

Como se puede ver, tuve que agregar el bloque de depuración DEBUG0, y también agregar varios comentarios para especificar de forma no confusa y obvia los varios detalles de posiciones y cuentas de bits que necesitaba resolver.

Ahora contamos con esta función, que es capaz de recuperar códigos divididos entre hasta 2 bytes diferentes, y siempre y cuando los códigos estén contenidos entre hasta 255 bytes.


Código: Seleccionar todo

//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
//This function will convert the "packed" codes
//which span more than 1 byte, into individual,
//up-to-12-bits codes in a new array:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Create the array to return:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Point right after the byte that contains
  //the minimum code size in bits:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;


  //Now we need a loop (with a nested loop)
  //to read the byte counts and process the bytes
  //of that count, and stop when the byte count of the count byte is 0,
  //as per the GIF specification:
  ///
   var c=0;
   var d=0;

   var rr=new Array(0,0);

   var doneCodeSZ=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;

       //Iterate through all bytes of this run:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
             doneCodeSZ=_ourCodeSZ;
             rr=getByteBits(imgStream[i], sB, _ourCodeSZ);
             toRet[toRet.length]=rr[0];

            //The number of bits already read by us
            //is given by the full code size minus
            //the bits we haven't read yet:
            ///
             doneCodeSZ=_ourCodeSZ-rr[1];



var dbg=toRet.length-1;
var DEBUG0=true;
if(DEBUG0 && (dbg==12 || dbg==19 || dbg==20 || dbg==22 || dbg==27 || dbg==31))
{
 alert(
       "DEBUG0 ("+(toRet.length-1)+"):\n_____\n"+"toRet[toRet.length-1]: "+toRet[toRet.length-1].toString(2)+"\n"+
       "rr[1]: "+rr[1]+"\n"+
       "i: "+i+"\n"+
       "sB: "+sB+"\n"+
       "_ourCodeSZ: "+_ourCodeSZ+"\n"+
       "doneCodeSZ: "+doneCodeSZ
      );
}



             if(rr[1])
             {
              //Here we must read the number of bits specified
              //by the previous amount of non-read bits:
              ///
               var prevrr1=rr[1];
               rr=getByteBits(imgStream[i+1], (sB+doneCodeSZ)&7, prevrr1);

              //The number of bits to move left the
              //new bits to concatenate from the other
              //byte should be the bits we had already read.
              ///
               toRet[toRet.length-1]|=(rr[0]<<doneCodeSZ);
             }


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;

             if(sB>7 || c<=0)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }

        }
   }
  return toRet;
 }

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 8:24 am

Nota: Sobre la forma de saber cuándo dejar de leer códigos, simplemente debemos detectar que el código que acabamos de leer completamente (no parcialmente) es el código de Fin de Información (EOI). Eso significa que no hay nada más que leer en los flujos de índices, de códigos, ni nada más de eso para esta imagen.




Ahora que hemos terminado esta etapa y que hemos descubierto que es totalmente posible leer y desempacar los códigos (el flujo de códigos) e incrementar correctamente el tamaño del código en bits, e incluso detectar el final del flujo de códigos sin tener que descomprimir el flujo de índices (los datos de imagen en cuestión), lo que debemos pasar a hacer ahora es comenzar a descubrir cómo descomprimir realmente los códigos y generar así el diccionario LZW completo, además del flujo de índices (por separado, para hacer todo más fácil y claro, y aunque probablemente menos "eficiente" pero más escalable), para finalmente escribirlo a este a la pantalla, de acuerdo a una paleta.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 9:04 am

Lo primero que debemos recordar para comenzar a generar la tabla, o más bien dicho, el diccionario LZW inicial (que contiene en este punto solo el "alfabeto LZW" para nuestros datos), es que el valor de los códigos especiales (que son los primeros 2 códigos justo después de la paleta indexada de colores) depende del tamaño mínimo de código LZW (especificado en el primer byte de los datos de la imagen, como ya hemos visto varias veces).

Tamaños de tabla de códigos inicial e índices de códigos especiales
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 9:13 am

Tengo una sospecha de que hay algunos códigos del diccionario LZW que son "clave", y que sirven para derivar otros códigos (aunque el primer código de datos de pixeles, justo después del código clear, sin duda alguna es clave para siquiera empezar a descomprimir todo el resto de códigos).

Puede que sea posible guardar solo estos códigos (o eventualmente recalcularlos constantemente y no guardar nada realmente) y así regenerar los datos descomprimidos que necesite, pero esto puede ser una tarea mucho más avanzada que simplemente generar la tabla normalmente, que es lo que debo hacer en este momento.
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 9:43 am

Lo primero que se necesita para comenzar a generar nuestro diccionario LZW es una función para inicializarlo a un estado inicial, en el que solo se conoce inicialmente un alfabeto compuesto por los índices posibles de nuestra paleta, y los 2 códigos especiales (clear y EOI):

Código: Seleccionar todo

//This function will allow us to initialize
//our LZW dictionary to its initial state,
//as many times as we like:
///
function GIF_LZW_InitDecompressDictionary(minCodeSZ, codeIdxArr)
{
 //This is the LZW dictionary we will return:
 ///
  var dict=new Array();

 //Determine the number of color slots
 //(which can all be used or not) in our
 //palette:
 ///
  var nPal=_bm[minCodeSZ]+1;

  var x=0;

 //Generate the entries for the colors,
 //and also for the Clear Code and for the
 //End Of Information Code, which will be
 //the last 2 codes in the table (that's why
 //we add 2 to nPal - to make room for those
 //last 2 codes):
 ///
  for(x=0;x<nPal+2;x++)
  {
   dict[x]=new Array();

   //The values of the dictionary entries for the colors
   //always are exactly the same as their index,
   //0 to 255:
   ///
    dict[x][0]=x;
  }

 return dict;
}

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 10:13 am

Necesitamos ver la tabla completa de códigos, para determinar de forma más simple cómo implementar la siguiente parte del algoritmo, después de la inicialización de dicha tabla. También necesitamos nuevamente los pasos del algoritmo de descompresión.

Para esta operación, solamente descubriremos si es posible ejecutar únicamente los pasos en negrita, y dejar los pasos que envían la salida a la pantalla hasta el final.

Tabla completa de códigos para la imagen de muestra


Pasos de descompresión GIF LZW
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

OK OK OK OK!!!: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 1:16 pm

OK OK OK OK!!!



Una vez que hemos sido capaces de desempacar los códigos, generar el diccionario LZW es relativamente fácil, como demuestra el hecho de que hemos necesitado solo unos 3 mensajes de instrucciones humanas en este foro y unas 8 horas para implementar la función que genera dicho diccionario:
Código: Seleccionar todo

//This function is one step behind actually
//creating the decompressed output of our
//compressed input data. What this does is
//generate the "dictionary" that will later allow
//us to substitute LZW codes by the specified byte
//values, effectively decompressing the image data to
//its original, useable, displayable, state:
///
function GIF_LZW_GenerateDecompressDictionary(minCodeSZ, codeIdxArr, dict)
{
 //Determine the number of color slots
 //(which can all be used or not) in our
 //palette:
 ///
  var nPal=_bm[minCodeSZ]+1;


 //Generate the codes for the rest of the
 //entries (this is where a big part of
 //the GIF LZW decompression algorithm
 //comes into play):
 ///
  var x=0;

 //Skip the clear code (it should be made dynamic later)
 ///
  x++;

 //Skip the very first code (it should be dynamic too);
 ///
  x++;

  var K=0;
  for(;x<codeIdxArr.length;x++)
  {
   if(codeIdxArr[x]==nPal+1)break;
     if(dict[codeIdxArr[x]]==undefined)
     {
      K=dict[codeIdxArr[x-1]][0];
      //All elements of the dictionary should in turn
      //be sub-arrays themselves, simply because the
      //entries in the LZW substitution dictionary (which match the
      //number of indexes in the LZW code table including
      //the pallete entries, plus the 2 special codes)
      //can have more than a single "character":
      ///
       dict[dict.length]=new Array();
       for(var j=0; j<dict[codeIdxArr[x-1]].length; j++)
        dict[dict.length-1][j]=dict[codeIdxArr[x-1]][j];
        dict[dict.length-1][j]=K;
     }
      else
      {
       K=dict[codeIdxArr[x]][0];
       dict[dict.length]=new Array();
       for(var j=0; j<dict[codeIdxArr[x-1]].length; j++)
        dict[dict.length-1][j]=dict[codeIdxArr[x-1]][j];
        dict[dict.length-1][j]=K;
      }
  }



 return dict;
}




Entonces, lo único que necesitamos es llamar nuestras 2 últimas funciones en una secuencia como la siguiente:
Código: Seleccionar todo

var dict=GIF_LZW_InitDecompressDictionary(2, LZW_codeIndex);

dict=GIF_LZW_GenerateDecompressDictionary(2, LZW_codeIndex, dict);








Nótese que todas las funciones que tenemos solamente manejan los casos de imágenes más fundamentales.

Eso significa que en este punto ya tenemos lo necesario para descomprimir los datos, y debemos fortalecer y completar nuestro código intentando decodificar archivos GIF más grandes y complejos, hasta que nuestro código falle, y entonces corregirlo y completarlo de forma acorde.

Pero antes de eso, voy a consolidar mi código actual para agregar manualmente los datos de la paleta, y una demostración de cómo dibujar nuestros datos, lo que por supuesto significa que necesitamos crear una función más, capaz de leer nuestro diccionario LZW y sustituir el flujo de códigos LZW por sus datos descomprimidos, para usarlos como índices de la paleta, que son los colores RGB sin compresión que dibujaremos pixel por pixel (para lo que también necesitamos la anchura y la altura de la imagen, obviamente).
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 4:10 pm

Como podemos ver, entre más arriba esté la capa de desarrollo de nuestro código, es más fácil implementar las funciones.

Ahora hemos creado una función capaz de tomar un flujo de códigos ya desempacados, además del diccionario LZW ya completado, y que es capaz de descomprimir sin problemas un flujo de códigos completo (de 255 bytes).

Sin embargo, esta función asume que el primer código del flujo es un código clear, y se lo salta, así que esta función debe ser reemplazada por una más completa, capaz de tratar el código clear (procesándolo o regresando), y llevar a cabo otras tareas.

Por ahora, lo más "avanzado" que puede hacer esta función es reconocer el código de fin de información, y detenerse inmediatamente después de encontrarlo, para dejar de emitir pixeles indexados de 1 byte que va a devolver.



Código: Seleccionar todo

function GIF_LZW_DecompressData(lzwdict, codeStream, codeIdx, minCodeSZ)
{
 var decompress=new Array();
 var _code=0;

 //Determine the number of color slots
 //(which can all be used or not) in our
 //palette:
 ///
  var nPal=_bm[minCodeSZ]+1;


 for(var x=codeIdx; x<codeStream.length; x++)
 {
  _code=codeStream[x];
  if(_code==nPal+1)break;

  for(var y=0; y<lzwdict[_code].length; y++)
  {
   decompress[decompress.length]=lzwdict[_code][y];
  }
 }



 return decompress;
}




Esta es la salida, que resultó ser correcta para nuestra imagen al primer intento de implementación:
Código: Seleccionar todo

1,1,1,1,1,2,2,2,2,2,
1,1,1,1,1,2,2,2,2,2,
1,1,1,1,1,2,2,2,2,2,
1,1,1,0,0,0,0,2,2,2,
1,1,1,0,0,0,0,2,2,2,
2,2,2,0,0,0,0,1,1,1,
2,2,2,0,0,0,0,1,1,1,
2,2,2,2,2,1,1,1,1,1,
2,2,2,2,2,1,1,1,1,1,
2,2,2,2,2,1,1,1,1,1

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 4:23 pm

Ahora agregamos estáticamente la paleta de nuestra imagen de muestra actual:

Código: Seleccionar todo
var palette=new Array();
    palette[0]=new Array(255,255,255);
    palette[1]=new Array(255,0,0);
    palette[2]=new Array(0,0,255);
    palette[3]=new Array(0,0,0);


También necesitamos la altura y la anchura de la imagen de muestra:
Código: Seleccionar todo
var width  = 10;
var height = 10;
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 4:27 pm

Ahora agregamos un objeto Canvas a nuestro código de HTML5, para intentar reconstruir y comprobar visualmente que los datos descomprimidos finales que acabamos de generar con GIF_LZW_DecompressData() son realmente correctos y corresponden a nuestra imagen original.

Código: Seleccionar todo

<body bgcolor="#aaaaaa">
<canvas id="img" style="background-color:#fedcba" width="640" height="480"></canvas>
</body>

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 5:09 pm

Un primer intento de nuestra rutina de dibujado, la cual es capaz de dibujar nuestra sencilla imagen de ejemplo usando HTML5 Canvas, está a continuación:
Código: Seleccionar todo

function GIF_putimage_decompressed(pixdata, palette, width, height, left, top)
{
 var screen=document.getElementById("img");


 //Get a "handle" to our HTML5Canvas on-screen-only "frame buffer":
 ///
  var HTML5_monitor_framebuffer=screen.getContext("2d");


  var _glyph=HTML5_monitor_framebuffer.createImageData(width, height);
  var glyph=_glyph.data;

  var px=0;

  for(var y=0; y<height; y++)
  {
     for(var x=0; x<width; x++)
     {
      glyph[ (y*(width<<2))+(x<<2)+0 ] = palette[pixdata[px]][0];
      glyph[ (y*(width<<2))+(x<<2)+1 ] = palette[pixdata[px]][1];
      glyph[ (y*(width<<2))+(x<<2)+2 ] = palette[pixdata[px]][2];
      glyph[ (y*(width<<2))+(x<<2)+3 ] = 0x255;
      px++;
     }
  }




  HTML5_monitor_framebuffer.putImageData(_glyph, left, top);

}




Llamamos a esta función de esta manera:
Código: Seleccionar todo

GIF_putimage_decompressed(decomp, palette, width, height, 35, 35);

Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm

Re: Flujo de Instrucciones Humanas para implementar un descompresor básico de LZW de GIF

Notapor ~ » Vie Ene 04, 2013 5:18 pm

Aquí está nuevamente nuestro programa de viruta ya terminado, con el HTML5 Canvas mostrando el resultado de redibujar manualmente nuestra imagen GIF de muestra, después de haber desempacado sus códigos LZW de los datos de la imagen, y de haber reconstruido el diccionario LZW, obviamente específico para esta imagen particular:


>> Descargar todo en un ZIP <<

LZW de GIF a Pixeles Indexados (a Índices de los Códigos del Diccionario LZW)


Y el código fuente completo de nuestro HTML/JavaScript. Ahora que hemos terminado este proceso de ejecución de instrucciones humanas y como resultado tenemos un código de descompresor extremadamente básico, lo que queda por hacer es iniciar un nuevo log de instrucciones separado para hacer que este código sea más general, intentando decodificar todo tipo de GIFs, y mejorar el código hasta que pueda decodificar todos los GIFs existentes así como detectar errores y detenerse ante estos (importante en extremo para cuando implementemos el mismo código en C, RealC y Ensamblador):

Código: Seleccionar todo

<html>

<body bgcolor="#aaaaaa">
Imagen generada manualmente por nosotros<br />
sobre un HTML5 Canvas:<br />
<canvas id="img" style="background-color:#fedcba" width="640" height="480"></canvas>
</body>






<script>
//Cachearemos las máscaras de bits necesarias para que podamos saber
//cómo recuperar hasta 2 bits:
///
 var _bm=new Array();
     _bm[0]  = parseInt("000000000000b", 2);
     _bm[1]  = parseInt("000000000001b", 2);
     _bm[2]  = parseInt("000000000011b", 2);
     _bm[3]  = parseInt("000000000111b", 2);
     _bm[4]  = parseInt("000000001111b", 2);
     _bm[5]  = parseInt("000000011111b", 2);
     _bm[6]  = parseInt("000000111111b", 2);
     _bm[7]  = parseInt("000001111111b", 2);
     _bm[8]  = parseInt("000011111111b", 2);
     _bm[9]  = parseInt("000111111111b", 2);
     _bm[10] = parseInt("001111111111b", 2);
     _bm[11] = parseInt("011111111111b", 2);
     _bm[12] = parseInt("111111111111b", 2);














//Esta función devuelve un arreglo de 2 elementos.
//El primer elemento del arreglo es el valor de los
//bits especificados, como si estuvieran ubicados
//desde el bit 0; y el segundo elemento del arreglo, si no es 0,
//es el número de bits que deberíamos leer del
//siguiente byte o bytes.
//
//Los bytes pueden estar ordenados como en Big Endian
//o como en Little Endian para que esta función de lectura de bytes
//funcione correctamente, byte por byte, y depende de
//código externo el leer los bytes en su orden correcto:
///
 function getByteBits(ourByte, startBit, bitCount)
 {
  var toRet=new Array();

  //Preservar solo los primeros 3 bits de startBit,
  //porque solo podemos especificar los bits 0-7 para StartBit:
  ///
   startBit&=parseInt("00000111b", 2);
   bitCount&=parseInt("00000111b", 2);

  //Preservar solo los primeros 8 bits de ourByte,
  //porque solo debemos usar los bits 0-7:
  ///
   ourByte&=parseInt("11111111b", 2);


  //Moveremos tantos bits a la derecha
  //como startBit nos indica:
  ///
   ourByte>>=startBit;


  //Ahora preservar solo el número de bits que
  //bitCountMask nos indica:
  ///
   ourByte&=_bm[bitCount];
   toRet[0]=ourByte;


  //Determinar si no hemos guardado todos los bits, o
  //si terminamos:
  ///
   toRet[1]=0;
   var cc=startBit+bitCount;
   if(cc>7)          //Ver en qué posición de bits deberíamos empezar
   toRet[1]=cc-8;    //Si excedemos 0-7, restamos 8 para obtener nuestros bits restantes;
                     //si no lo excede, simplemente devolmemos 0.


  return toRet;
 }













//Obtener los datos gráficos de una imagen GIF individual:
///
 var imgDataArr=new Array(
 2,
 22, parseInt("10001100b",2), parseInt("101101b",2), parseInt("10011001b",2), parseInt("10000111b",2), parseInt("101010b",2), parseInt("11100b",2), parseInt("11011100b",2), parseInt("110011b",2), parseInt("10100000b",2), parseInt("10b",2), parseInt("1110101b",2), parseInt("11101100b",2), parseInt("10010101b",2), parseInt("11111010b",2), parseInt("10101000b",2), parseInt("11011110b",2), parseInt("1100000b",2), parseInt("10001100b",2), parseInt("100b",2), parseInt("10010001b",2), parseInt("1001100b",2), parseInt("1b",2),
 0
 );


//Obtener el tamaño inicial de los códigos en bits:
///
 var initCodeSZ=imgDataArr[0];


//Generar el número actual de bits que
//usaremos para calcular una potencia y usarlo como el número
//de códigos del tamaño actual que leeremos antes de
//aumentar el tamaño en bits de nuestros códigos:
///
 var CodeSZ=initCodeSZ;


//Convertir el tamaño inicial del número de bits
//que usaremos realmente para generar los
//códigos de descompresión:
///
 var ourCodeSZ=initCodeSZ+1;



//Convertir nuestro tamaño de código en el número de
//códigos de "ourCodeSZ" bits que leeremos antes de
//aumentar el número de bits por código:
///
 var numCodes=Math.pow(2, CodeSZ);










//Esta función convertirá los códigos "empacados"
//que ocupan más de 1 byte, en códigos individuales
//de hasta 12 bits en un nuevo arreglo:
///
 function GIF_imageStream2CodeStream(imgStream)
 {
  //Crear el arreglo a devolver:
  ///
   var toRet=new Array();

   var _ourCodeSZ=ourCodeSZ;
   var _CodeSZ=CodeSZ;
   var _numCodes=numCodes;


  //Apuntar justo después del byte que contiene
  //el tamaño de código mínimo en bytes:
  ///
   var i=1;

   var startBit=0;
   var sB=0;
   var baseAddr=0;


  //Ahora necesitamos un bucle (con un bucle anidado)
  //para leer las cuentas de bytes y procesar los bytes
  //de esa cuenta, y detenernos cuando la cuenta del byte sea 0,
  //de acuerdo a la especificación GIF:
  ///
   var c=0;
   var d=0;

   var rr=new Array(0,0);

   var doneCodeSZ=0;


  //Obtener la cuenta de bytes para esta sección, e iterar
  //para cada byte:
  ///
   while( (c=imgStream[i]) != 0 )
   {
    i++;

       //Iterar a través de todos los bytes de esta corrida:
       ///
        startBit=0;
        baseAddr=i;
        d=c;
        c=(c*8)-startBit;
        while(  d>0  )
        {
             doneCodeSZ=_ourCodeSZ;
             rr=getByteBits(imgStream[i], sB, _ourCodeSZ);
             toRet[toRet.length]=rr[0];

            //El número de byte que ya leímos
            //está dado por el tamaño completo de código menos
            //los bits que todavía no hemos leído:
            ///
             doneCodeSZ=_ourCodeSZ-rr[1];



var dbg=toRet.length-1;
var DEBUG0=true;
if(DEBUG0 && i>255 && (dbg==12 || dbg==19 || dbg==20 || dbg==22 || dbg==27 || dbg==31))
{
 alert(
       "DEBUG0 ("+(toRet.length-1)+"):\n_____\n"+"toRet[toRet.length-1]: "+toRet[toRet.length-1].toString(2)+"\n"+
       "rr[1]: "+rr[1]+"\n"+
       "i: "+i+"\n"+
       "sB: "+sB+"\n"+
       "_ourCodeSZ: "+_ourCodeSZ+"\n"+
       "doneCodeSZ: "+doneCodeSZ
      );
}



             if(rr[1])
             {
              //Aquí debemos leer el número de bits especificados
              //por la cantidad anterior de bits no leídos:
              ///
               var prevrr1=rr[1];
               rr=getByteBits(imgStream[i+1], (sB+doneCodeSZ)&7, prevrr1);

              //El número de bits a mover a la izquierda los
              //nuevos bits a concatenar del otro byte
              //debería ser los bits que ya hemos leído, acumulativamente.
              ///
               toRet[toRet.length-1]|=(rr[0]<<doneCodeSZ);
             }


             startBit+=_ourCodeSZ;
             sB+=_ourCodeSZ;

             if(sB>7 || c<=0)
             {
              sB&=7;
              d--;
              i++;
             }

             c-=_ourCodeSZ;



             _numCodes--;
             if(_numCodes==0)
             {
              _ourCodeSZ++;
              _CodeSZ++;
              _numCodes=Math.pow(2, _CodeSZ);
             }

        }
   }
  return toRet;
 }




var LZW_codeIndex=GIF_imageStream2CodeStream(imgDataArr);



var DEBUG1=false;

//En este bloque de depuración, verificaremos que
//hayamos obtenido todos los códigos LZW correctamente:
///
 if(DEBUG1)
 {
        alert(LZW_codeIndex.length);
        var u="";
        for(var x=0;x<LZW_codeIndex.length;x++)
        {
         u+=x+". "+LZW_codeIndex[x];
         if(x+1<LZW_codeIndex.length)u+="\n";
        }
        alert(u);
 }




//Esta función nos permitirá inicializar
//nuestro diccionario LZW a su estado inicial,
//tantas veces como lo deseemos:
///
function GIF_LZW_InitDecompressDictionary(minCodeSZ, codeIdxArr)
{
 //Este es el diccionario LZW que devolveremos:
 ///
  var dict=new Array();

 //Determinar el número de posiciones de color
 //(que pueden estar todas usadas o no) en nuestra
 //paleta:
 ///
  var nPal=_bm[minCodeSZ]+1;

  var x=0;

 //Generatar las entradas para los colores,
 //y también para el Código Clear y para el de
 //Final de Información, que serán los
 //últimos 2 códigos en la tabla de color (por eso
 //agregamos 2 a nPal - para hacer lugar para esos 2
 //últimos códigos):
 ///
  for(x=0;x<nPal+2;x++)
  {
   dict[x]=new Array();

   //Los valores de las entradas de diccionario para los colores
   //siempre son exactamente el de sus índices, 0 a 255:
   ///
    dict[x][0]=x;
  }

 return dict;
}









//Esta función está un paso atrás de crear
//la salida descomprimida final de nuestros datos
//de entrada comprimidos. Lo que esto hace es
//generar el "diccionario" que más tarde nos permitirá
//sustituir los códigos LZW por los valores de byte
//especificados, efectivamente descomprimiendo los datos de imagen
//a su estado original, usable y desplegable:
///
function GIF_LZW_GenerateDecompressDictionary(minCodeSZ, codeIdxArr, dict)
{
 //Determinar el número de posiciones de color
 //(que pueden estar todas usadas o  no) en nuestra
 //paleta:
 ///
  var nPal=_bm[minCodeSZ]+1;


 //Generar los códigos para el resto de las
 //entradas (aquí es donde una gran parte del algoritmo
 //de descompresión GIF LZW entra en juego):
 ///
  var x=0;

 //Saltarse el código clear (esto debería hacerse dinámicamente en el futuro)
 ///
  x++;

 //Saltarse el primer código (esto también debería ser dinámico);
 ///
  x++;

  var K=0;
  for(;x<codeIdxArr.length;x++)
  {
   if(codeIdxArr[x]==nPal+1)break;
     if(dict[codeIdxArr[x]]==undefined)
     {
      K=dict[codeIdxArr[x-1]][0];
      //Todos los elementos del diccionario deberían a su vez
      //ser sub-arreglos, simplemente porque las entradas
      //en el diccionario de sustitución LZW (las cuales concuerdan
      //con el número de índices en la tabla de códigos LZW incluyendo
      //las entradas de paleta más los 2 códigos especiales)
      //pueden tener más de un "carácter" individual:
      ///
       dict[dict.length]=new Array();
       for(var j=0; j<dict[codeIdxArr[x-1]].length; j++)
        dict[dict.length-1][j]=dict[codeIdxArr[x-1]][j];
        dict[dict.length-1][j]=K;
     }
      else
      {
       K=dict[codeIdxArr[x]][0];
       dict[dict.length]=new Array();
       for(var j=0; j<dict[codeIdxArr[x-1]].length; j++)
        dict[dict.length-1][j]=dict[codeIdxArr[x-1]][j];
        dict[dict.length-1][j]=K;
      }
  }



 return dict;
}













var dict=GIF_LZW_InitDecompressDictionary(2, LZW_codeIndex);

dict=GIF_LZW_GenerateDecompressDictionary(2, LZW_codeIndex, dict);




var DEBUG2=false;

if(DEBUG2)
{
        var rd="";
        for(var x=0;x<dict.length;x++)
        {
         rd+=x+". "+dict[x];
         if(x+1<dict.length)
         rd+="\n";
        }
         alert(dict.length);
         alert(rd);
}


function GIF_LZW_DecompressData(lzwdict, codeStream, codeIdx, minCodeSZ)
{
 var decompress=new Array();
 var _code=0;

 //Determinar el número de posiciones de color
 //(que pueden estar todas usadas o no) en nuestra
 //paleta:
 ///
  var nPal=_bm[minCodeSZ]+1;


 for(var x=codeIdx; x<codeStream.length; x++)
 {
  _code=codeStream[x];
  if(_code==nPal+1)break;

  for(var y=0; y<lzwdict[_code].length; y++)
  {
   decompress[decompress.length]=lzwdict[_code][y];
  }
 }



 return decompress;
}









var decomp=GIF_LZW_DecompressData(dict, LZW_codeIndex, 1, 2);










var DEBUG3=false;

if(DEBUG3)
{
 alert(decomp);
}





var palette=new Array();
    palette[0]=new Array(255,255,255);
    palette[1]=new Array(255,0,0);
    palette[2]=new Array(0,0,255);
    palette[3]=new Array(0,0,0);


var width  = 10;
var height = 10;





function GIF_putimage_decompressed(pixdata, palette, width, height, left, top)
{
 var screen=document.getElementById("img");


 //Obtener un "manejador" a nuestr "frame buffer" de HTML5Canvas:
 ///
  var HTML5_monitor_framebuffer=screen.getContext("2d");


  var _glyph=HTML5_monitor_framebuffer.createImageData(width, height);
  var glyph=_glyph.data;

  var px=0;

  for(var y=0; y<height; y++)
  {
     for(var x=0; x<width; x++)
     {
      glyph[ (y*(width<<2))+(x<<2)+0 ] = palette[pixdata[px]][0];
      glyph[ (y*(width<<2))+(x<<2)+1 ] = palette[pixdata[px]][1];
      glyph[ (y*(width<<2))+(x<<2)+2 ] = palette[pixdata[px]][2];
      glyph[ (y*(width<<2))+(x<<2)+3 ] = 0x255;
      px++;
     }
  }




  HTML5_monitor_framebuffer.putImageData(_glyph, left, top);

}



GIF_putimage_decompressed(decomp, palette, width, height, 35, 35);





</script>
</html>




Esto es todo lo que he logrado. Este es probablemente el código más básico, simple y fácil de entender posible para un descompresor de GIFs.

Todavía falta trabajo por hacer, pero muchos de los detalles más difíciles de lograr ya se implementaron (desempacar códigos de tamaño en bits variables, inicializar el diccionario con los códigos de reinicio del diccionario y fin de datos de imagen, generar el diccionario LZW, detenerse cuando se encuentra un código de fin de datos de imagen).

Esto es lo que contiene:

- Demostración del GIF dibujado con nuestra implementación JavaScript del descompresor GIF, sobre un HTML5 Canvas.
- Código fuente completo.
- Todos los archivos de código intermedios del proceso en un único ZIP.
- La explicación completa del proceso.

El código es lo más ordenado posible. A partir de los datos sin cabecera extraídos de una sección de imagen GIF, primero desempacamos los códigos que contiene (porque tienen número de bits variables y hay que unirlos usando los bits de varios bytes). Después generamos el diccionario LZW con el breve algoritmo de LZW, y finalmente descomprimimos (sustituimos) los códigos que desempacamos de los bytes por las "palabras" del diccionario LZW, efectivamente descomprimiendo la imagen.

Esta forma podría considerarse más paso a paso, y por lo tanto más fácil de entender y aprender, que otras explicaciones o implementaciones del descompresor GIF (aunque cuando el código esté realmente completo, va a ser un tanto más complejo).

Después simplemente podemos dibujar la imagen descomprimida en la pantalla, igual que si se tratara de un BMP.


Este mensaje es el resultado final de este milestone, pero se puede leer todo el proceso que se necesitó llevar a cabo para lograr descifrar la información técnica necesaria para haber implementado esto.

Paso Siguiente>>
Imagen
IP for hosts file (email udocproject@yahoo.com to get updates if website becomes offline):
Código: Seleccionar todo
190.150.9.244 archefire.org



See what I'm doing in real time:
Main Desktop 1
Main Desktop 2
Avatar de Usuario
~
Site Admin
 
Mensajes: 2958
Registrado: Sab Nov 10, 2012 1:04 pm


Volver a Gráficos

¿Quién está conectado?

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


cron