Fecha actual Jue Ago 22, 2019 5:32 pm

Flujo 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW 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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Vie Ene 04, 2013 10:54 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 <<







En este punto, ahora partimos teniendo un descompresor GIF con capacidades mayormente estáticas y limitadas para decodificar las imágenes GIF más simples y pequeñas, más que todo los GIF87a.

Como sabemos, tenemos 4 pasos mayores de nuestro descompresor:

  1. A partir de los datos del archivo: Obtención, lectura y desempacado de códigos (con aumentos de tamaño programados).

  2. A partir de los códigos desempacados: Generación del diccionario LZW (para la descompresión).

  3. A partir del diccionario LZW: Sustitución de códigos por frases del diccionario para efectivamente descomprimir.

  4. A partir de los datos descomprimidos: Despliegue en pantalla o almacenamiento en disco de los datos descomprimidos de pixeles indexados.

Como vemos, podemos perfecta y fácilmente implementar estos pasos por separado, y al paso actual implementado, agregarle el siguiente paso.

En este log de instrucciones humanas, reimplementaremos un desempacador de códigos LZW (el primero de los pasos del proceso de descompresión), no solo capaz de aumentar el tamaño de los código como hemos logrado hasta ahora, sino también capaz de llegar al número máximo de código de 12 bits (y de reiniciarse al tamaño mínimo de forma acorde), además de capaz de concatenar correctamente los bits de tantos bytes como sea necesario (no solo 2 bytes), de forma iterativa y reanudable entre corridas de bucles finalizadas, y sin importar que haya bytes de cuenta de por medio en cualquier combinación posible.
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Vie Ene 04, 2013 11:44 pm

Para esta tarea, necesito un archivo GIF con abundancia de códigos interrumpidos entre bytes por bytes de cuenta de nuevas porciones intercalados.

sample_1.gif con hack de porciones de 1 byte


Sé que sería difícil encontrar una imagen ideal que me permita probar mi función de desempacado de códigos al extremo. Por eso modifiqué manualmente la misma imagen de muestra que hemos estado usando, y en lugar de contener un único bloque de códigos empacados de 22 bytes, ahora contiene 22 bytes de códigos empacados, con porciones de 1 byte.

Es decir que ahora todos los bytes con los códigos empacados tienen de por medio un byte de nueva cuenta.

Esta es una situación ideal para comprobar que puedo concatenar los diferentes bytes de manera correcta incluso con esta situación extrema que requiere reanudar la concatenación para prácticamente todos los códigos (todos lo que están almacenados en más de 1 byte).


Ahora tengo estos archivos:

Cabecera del GIF de muestra

Código fuente de datos LZW hackeados del GIF de muestra

Código binario compilado de datos LZW hackeados del GIF de muestra

Nueva imagen de prueba con datos LZW hackeados


Debo no solo asegurarme de poder concatenar de forma reanudable los datos de esta imagen (que después de todo, siguen teniendo un máximo de 2 bytes, que no es lo más que podrían llegar a tener), sino que también asegurarme de generalizar absolutamente mi código, para poder concatenar correctamente los bits de un código desde tantos bytes como sea necesario, de forma iterativa, estable y autoajustable (con comprobación de erores de overrun/underrun/etc., más adelante).
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Sab Ene 05, 2013 1:08 am

Las primera o primeras funciones de los 4 pasos son las más importantes para validar los límites desde el principio, y asegurarse que después de que estas procesen sus tareas, sea imposible trabajar subsecuentemente con datos con errores de límites de overrun/underrun o similares, en los offsets de datos. con los que realmente contamos.
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Dom Ene 06, 2013 2:37 pm

Ahora debemos comenzar con una función, siempre con 2 bucles.

El bucle externo lee las cuentas de bytes, para cada byte de los datos de la imagen, los códigos empacados.

El bucle interno recorre todos los bytes de la porción actual de (cuenta)(datos de cuenta).
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Dom Ene 06, 2013 2:45 pm

Viendo el problema a un alto nivel, de forma intuitiva y sin mayor esfuerzo, ya que tenemos una imagen con porciones con cuentas de 1 byte, el bucle interno solo correrá una vez, y necesitaremos reanudar constantemente la concatenación de bits de varios bytes.

A este alto nivel no importa mucho el tamaño actual de los códigos sino más bien la manera en la que podremos concatener códigos de tamaño arbitrario.

La secuencia más básica sería la siguiente:


Nuestras variables iniciales más importantes son:
Código: Seleccionar todo
tamaño_codigo=tamaño_actual;
bits_leídos=0;
bits_restantes=0;
byte_anterior=0;

codigo_LZW_actual=-1;



  1. Entramos al bucle externo para leer el primer byte de cuenta.

  2. Ahora entramos al bucle interno para procesar el número de bytes indicados por la cuenta.

  3. En el bucle interno, leemos el byte actual y lo ponemos en byte_anterior.

  4. Ahora vemos si bits_restantes es mayor a 0:
    No (estado inicial, y significa que es la primera vez que extraemos bits del byte actual para concatenar en el código LZW actual):

    1. Incrementamos la posición del código LZW actual en 1 (porque si bits_restantes es menor o igual a 0, eso significa que estamos recuperando los bits para el siguiente código LZW).

    2. Leer la cantidad de bits de tamaño_codigo en nuestro código LZW actual.

    3. Guardar dicha cantidad de bits en el valor de nuestro código LZW actual, desde la posicón de bit 0

    4. Guardar el resultado de bits restantes en bits_restantes.

    5. Guardar el resultado de bits leídos en bits_leídos, el cual está dado por sumarlo acumulativamente en esta rama positiva del IF, con (tamaño_actual-bits_restantes-bits_leidos)

  5. Sí:

    1. Leer la cantidad de bits de tamaño_codigo en nuestro código LZW actual.

    2. Mover estos bits la cantidad de bits especificada por bits_leídos hacia la izquierda, y concatenar este valor con el el valor ya existente de nuestro código LZW actual, desde la posicón de bit especificada por bits_leídos.

    3. Guardar el resultado de cantidad de bits restantes en bits_restantes.

    4. Guardar el resultado de cantidad de bits leídos en bits_leídos, el cual está dado por sumarlo acumulativamente en esta rama positiva del IF, con (tamaño_actual-bits_restantes-bits_leidos)
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Dom Ene 06, 2013 6:47 pm

El mismo algortimo expresado de forma más concisa sería el siguiente.


Una vez más, nuestras variables iniciales más importantes son:
Código: Seleccionar todo
tamaño_codigo=tamaño_actual;
bits_leídos=0;
bits_restantes=0;
codigo_LZW_actual=-1;



  1. Entramos al bucle externo para leer el primer byte de cuenta.

  2. Si hubo un error en leer este byte, salimos con un error.

  3. Ahora entramos al bucle interno para procesar el número de bytes indicados por la cuenta.

  4. En el bucle interno, leemos el byte actual y lo ponemos en valor_byte.

  5. Si hubo un error en leer este byte, salimos con un error.

  6. Si bits_restantes es menor o igual a 0, incrementamos la posición del código LZW actual en 1 (porque si bits_restantes es menor o igual a 0, eso significa que estamos recuperando los bits para el siguiente código LZW); también tenemos que inicializar a 0 el valor de este nuevo código LZW, y poner a 0 las variables de bits leídos y bits restantes.

  7. Si nuestro tamaño actual de código es 12 bits y hemos excedido el número de códigos contiguos que podemos contener en 12 bits que sería 2 elevado a la 12, que serían 4096, debemos devolver el tamaño de código a su tamaño mínimo inicial (este paso puede ser en sí un error, o el que esté colocado físicamente en este punto puede ser un error, así que necesitamos imágenes bastante grandes que pongan a prueba este punto del algoritmo).

  8. Leer la cantidad de bits de tamaño_codigo en nuestro código LZW actual.

  9. Mover estos bits la cantidad de bits especificada por bits_leídos hacia la izquierda, y concatenar este valor con el el valor ya existente de nuestro código LZW actual, desde la posicón de bit especificada por bits_leídos.

  10. Guardar el resultado de bits restantes en bits_restantes.

  11. Guardar el resultado de bits leídos en bits_leídos, el cual está dado por sumarlo acumulativamente con (tamaño_actual-bits_restantes-bits_leidos).
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 12:12 am

Nuestra primera versión de la nueva función es la siguiente:

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;

   var curReadBits=0;

   var remainingBits=0;

   var numCode=-1;

   var byteValue=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  )
        {
             if(remainingBits<1)
             {
              numCode++;
              toRet[numCode]=0;
              doneCodeSZ=0;
              remainingBits=_ourCodeSZ;
              curReadBits=0;
             }

             rr=getByteBits(imgStream[i], sB, remainingBits);


             //The number of bits already read by us
             //is given by the full code size minus
             //the bits we haven't read yet:
             ///
              byteValue=rr[0];
              toRet[numCode]|=(byteValue<<doneCodeSZ);
              remainingBits=rr[1];
              curReadBits=(_ourCodeSZ-remainingBits-doneCodeSZ);
              doneCodeSZ+=(_ourCodeSZ-remainingBits-doneCodeSZ);

             startBit+=curReadBits;
             sB+=curReadBits;

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

             c-=curReadBits;


             if(remainingBits<1)
              _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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 1:12 am

Y la misma función, mucho más comentada:
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();


  //Cache of several important values (these should be made
  //into function parameters to be able to break and resume
  //this function in a much more flexible, useable way):
  ///
   var _ourCodeSZ=ourCodeSZ;   //Number of bits in code (count mode)
   var _CodeSZ=CodeSZ;         //Number of bits in code (addressing mode)
   var _numCodes=numCodes;     //Number of possible codes for the current code bit size


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

   var startBit_0_N=0;
   var startBit_0_7=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 count_in_bits=0;
   var count_in_bytes=0;

  //Initialize this structure for cleanliness:
  ///
   var LZW_code_fragment=new Array(0,0);

  //The number of bits we have  cumulatively read from
  //the current code (up to the total size of bits
  //for this code size in bits):
  ///
   var doneCodeSZ=0;

  //Number of read bits for the very current iteration:
  ///
   var curReadBits=0;

  //The number of bits that we still need to read from
  //the current code at its current size in bits:
  ///
   var remainingBits=0;

  //The initial value of numCode will be -1
  //because it must be incremented to the
  //valid value of 0 at first, given that
  //the code increments it when remainingBits
  //is 0, which will be the case at code startup,
  //from the first iteration:
  //
   var numCode=-1;

  //The value of the byte we are reading:
  ///
   var byteValue=0;


  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (count_in_bits=imgStream[byteOffset]) != 0 )
   {
    //Since we have just read the count byte,
    //now we will advance to the next byte, which
    //would contain the first data byte of this chunk:
    ///
     byteOffset++;

       //Iterate through all bytes of this run:
       ///

       //Before entering the inner loop, we will
       //initialize this start bit variable to 0 (HIGHLY LIKELY TO BE DELETED???):
       ///
        startBit_0_N=0;

       //The intention of this would be to eventually pass
       //more parameters to this function, and limits, for
       //being able to return from this function before
       //reading all data available, and still being able
       //to resume everything easily:
       ///
        baseAddr=byteOffset;

       //Get the number of bytes here for this chunk:
       ///
       count_in_bytes=count_in_bits;

       //Get the number of bits here for this chunk:
       ///
        count_in_bits=(count_in_bits*8)-startBit_0_N;






       //Iterate through all bytes of this run:
       ///
        while(  count_in_bytes>0  )
        {
            //This will always run at the very
            //first iteration with all freshly initialized.
            //Here we will adjust values whenever we have
            //processed all remaining bits we should have read
            //for the current LZW code:
            ///
             if(remainingBits<1)
             {
              numCode++;                //Advance to the next, new, LZW code slot
              toRet[numCode]=0;         //Initialize new code to 0
              doneCodeSZ=0;             //Initialize the number of bits read to 0
              remainingBits=_ourCodeSZ; //This number must initially be the size of our code in bits
              curReadBits=0;            //How many bits we have read in this iteration
             }

             //Here we perform the read of the new bits for
             //this run.
             //
             //We read from the current byte offset of the image data,
             //start at some bits marked from 0 to 7, and read up to
             //the number of possible remaining bits for the current
             //code:
             ///
              LZW_code_fragment=getByteBits(imgStream[byteOffset], startBit_0_7, remainingBits);





             //Store the values of the bits we have just read
             //in a temporary "byte":
             ///
              byteValue=LZW_code_fragment[0];

             //For the current LZW code, concatenate the
             //bits we already have with the bits we have
             //just read, shifted left the number of bits
             //that we have already read. Concatenate
             //both values of up to 12 bits, using OR:
             ///
              toRet[numCode]|=(byteValue<<doneCodeSZ);

             //Save the new number of remaining bits after
             //reading the new chunk:
             ///
              remainingBits=LZW_code_fragment[1];

             //The number of bits already read by us
             //is given by the full code size minus
             //the bits we haven't read yet. We need
             //both the current value for this run,
             //as well as the accumulated value to know
             //when we have read the whole code already:
             ///
              curReadBits=(_ourCodeSZ-remainingBits-doneCodeSZ);
              doneCodeSZ+=(_ourCodeSZ-remainingBits-doneCodeSZ);


             //Increment the starting bit positions by
             //the number of bits we have really just read
             //in this iteration:
             ///
              startBit_0_N+=curReadBits;
              startBit_0_7+=curReadBits;


             //If we have exceeded the number of bits in a byte,
             //or if there are no more bits in this count chunk stream,
             //we must advance several values:
             ///
              if(startBit_0_7>7 || count_in_bits<=0)
              {
               startBit_0_7&=7;    //Adjust this variable to a cycle of 0 to 7
               count_in_bytes--;   //Discount one less byte
               byteOffset++;       //If more than 7 bits, then go to the next byte (obvious)
              }


            //We will accumulate and count the number of
            //bits we have just read so far for this
            //chunk of 1 to 255 bytes:
            ///
             count_in_bits-=curReadBits;


            //IMPORTANT NEW TRICK: We will only discount the number
            //of codes processed before incrementing in 1 the size
            //of the LZW code in bits, only if we have truly read
            //all of the bits for all of the codes of the current size,
            //and never before, which would make no sense and would
            //make us skip bits and get all data wrong:
            ///
             if(remainingBits<1)
               _numCodes--;

            //If the number of codes of the current bit size
            //has become 0, it means that we must increase the
            //size and the count of codes for the new codes' bit size.
            ///
             if(_numCodes==0)
             {
              _ourCodeSZ++;                    //Increment number of bits (count mode)
              _CodeSZ++;                       //Increment number of bits (addressing mode)
              _numCodes=Math.pow(2, _CodeSZ);  //Get the number of possible codes for this bit size
             }

        }






   }

  //Return the stream of unpacked codes:
  ///
   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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 1:23 am

En este punto, he comprobado que esta función, que representa el Paso 1 del descompresor de GIF, es la función más importante en el sentido que es en esta función en la que tengo que llevar a cabo toda la comprobación de errores posibles, como cuentas erróneas o límites sobrepasados, y regresar con error si estos se dan.

También necesito ser capaz de detener y reanudar esta función, usando verdaderos offsets arbitrarios de archivo, parámetros de punto inicial de bits, de tamaño mínimo y "actual" de código, y otros relacionados, que por ahora son variables internas a la función.

Con esto podré llamar a la función sobre datos parciales, lo que me permitiría usar menos memoria, por ejemplo.

Pero creo que en este momento ya no puedo hacer mucho más sin experimentar realmente con datos GIF más grandes.

Así que solamente terminaré este flujo de instrucciones comprobando que realmente puedo recuperar correctamente los códigos incluso si cada uno de ellos están separados por bytes de cuenta con valor de 1, para nuestra imagen de muestra original.

Y también colocaré instrucciones de regreso de errores, no muy robusta o utilizable, pero que demuestra el ´punto en el que hay que regresar en caso de errores de límites.
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 1:33 am

Sí funcionó, lo que significa que nuestra nueva función es más robusta que la original, como se puede ver aquí:

Nuevo ejemplo con desempacador de códigos mejorado


Y como vemos a continuación, comprobamos el código inicialmente y hasta ahora, con porciones con una cuenta de bytes de 1, lo que no es usual pero sirve para hacer que todos los códigos grandes estén divididos y separados con 1 byte "extraño" de cuenta de por medio. Si aun así la rutina funcionó correctamente, significa que estamos muy bien encaminados:
Código: Seleccionar todo
//Get a single GIF image graphical data:
///
 var imgDataArr=new Array(
 2,
 1,
 parseInt("10001100b",2),
 1,
 parseInt("101101b",2),
 1,
 parseInt("10011001b",2),
 1,
 parseInt("10000111b",2),
 1,
 parseInt("101010b",2),
 1,
 parseInt("11100b",2),
 1,
 parseInt("11011100b",2),
 1,
 parseInt("110011b",2),
 1,
 parseInt("10100000b",2),
 1,
 parseInt("10b",2),
 1,
 parseInt("1110101b",2),
 1,
 parseInt("11101100b",2),
 1,
 parseInt("10010101b",2),
 1,
 parseInt("11111010b",2),
 1,
 parseInt("10101000b",2),
 1,
 parseInt("11011110b",2),
 1,
 parseInt("1100000b",2),
 1,
 parseInt("10001100b",2),
 1,
 parseInt("100b",2),
 1,
 parseInt("10010001b",2),
 1,
 parseInt("1001100b",2),
 1,
 parseInt("1b",2),
 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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 2:50 am

Aquí tengo una nueva versión de esta función, capaz de reiniciar correctamente (aparentemente) el tamaño del código en bits si encuentra un Código Clear.

Esto lo logré gracias al hecho de haber tratado de descomprimir una imagen más grande, específicamente el logo de este foro, de este sitio, como se ve aquí:

/tmp/gif2src/debris/0001/gif_lzw_to_indexed_0005.html



Aquí está la 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();


  //Cache of several important values (these should be made
  //into function parameters to be able to break and resume
  //this function in a much more flexible, useable way):
  ///
   var _ourCodeSZ=ourCodeSZ;   //Number of bits in code (count mode)
   var _CodeSZ=CodeSZ;         //Number of bits in code (addressing mode)
   var _numCodes=numCodes;     //Number of possible codes for the current code bit size


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

   var startBit_0_N=0;
   var startBit_0_7=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 count_in_bits=0;
   var count_in_bytes=0;

  //Initialize this structure for cleanliness:
  ///
   var LZW_code_fragment=new Array(0,0);

  //The number of bits we have  cumulatively read from
  //the current code (up to the total size of bits
  //for this code size in bits):
  ///
   var doneCodeSZ=0;

  //Number of read bits for the very current iteration:
  ///
   var curReadBits=0;

  //The number of bits that we still need to read from
  //the current code at its current size in bits:
  ///
   var remainingBits=0;

  //The initial value of numCode will be -1
  //because it must be incremented to the
  //valid value of 0 at first, given that
  //the code increments it when remainingBits
  //is 0, which will be the case at code startup,
  //from the first iteration:
  //
   var numCode=-1;

  //The value of the byte we are reading:
  ///
   var byteValue=0;


  //We need to calculate the positions and
  //then the values of the Clear Code and
  //the End of Information Code.
  //
  //This is EXTREMELY IMPORTANT, because if we
  //find the Clear Code, not only at the stage
  //where we are filling the LZW dictionary,
  //BUT ALSO HERE WHILE WE ARE RETRIEVING THE LZW
  //CODES, we must reset the code sizes and counts
  //immediately to their starting values.
  //
  //The Clear Code always comes before the number
  //of entries specified by the first byte in the
  //image stream plus 1. So, we just need to take
  //that original value of that first byte of the
  //image stream, convert it into that exact number
  //of binary bits set to 1, and to that value we
  //add 1.
  //
  //That's the position and value of the Clear Code.
  //The End of Information Code (EOI) always is 1 position
  //after the Clear Code, and it is the same as adding
  //1 to the Clear Code value, and we are done:
  ///
   var _ClearCode = _bm[_CodeSZ]+1;
   var _EOICode   = _ClearCode+1;




  //Get the byte count for this section, and loop
  //for each byte:
  ///
   while( (count_in_bits=imgStream[byteOffset]) != 0 )
   {
    if(count_in_bits==undefined){toRet[0]=-1;return;}



    //Since we have just read the count byte,
    //now we will advance to the next byte, which
    //would contain the first data byte of this chunk:
    ///
     byteOffset++;

       //Iterate through all bytes of this run:
       ///

       //Before entering the inner loop, we will
       //initialize this start bit variable to 0 (TESTED NECESSARY BECAUSE
       //THIS BIT COUNT OBVIOUSLY APPLIES ONLY TO THE FIRST COUNT,
       //ONLY FOR THE BITS THAT ARE BETWEEN 1 AN 255 BYTES, AND AS WE SEE,
       //IT GETS SET BEFORE THE INNER LOOP, AND IS USEFUL TO STOP SUCH INNER LOOP):
       ///
        startBit_0_N=0;

       //The intention of this would be to eventually pass
       //more parameters to this function, and limits, for
       //being able to return from this function before
       //reading all data available, and still being able
       //to resume everything easily:
       ///
        baseAddr=byteOffset;

       //Get the number of bytes here for this chunk:
       ///
       count_in_bytes=count_in_bits;

       //Get the number of bits here for this chunk:
       ///
        count_in_bits=(count_in_bits*8)-startBit_0_N;






       //Iterate through all bytes of this run:
       ///
        while(  count_in_bytes>0  )
        {
            //This will always run at the very
            //first iteration with all freshly initialized.
            //Here we will adjust values whenever we have
            //processed all remaining bits we should have read
            //for the current LZW code:
            ///
             if(remainingBits<1)
             {
              numCode++;                //Advance to the next, new, LZW code slot
              toRet[numCode]=0;         //Initialize new code to 0
              doneCodeSZ=0;             //Initialize the number of bits read to 0
              remainingBits=_ourCodeSZ; //This number must initially be the size of our code in bits
              curReadBits=0;            //How many bits we have read in this iteration
             }

             //Here we perform the read of the new bits for
             //this run.
             //
             //We read from the current byte offset of the image data,
             //start at some bits marked from 0 to 7, and read up to
             //the number of possible remaining bits for the current
             //code:
             ///
              if(imgStream[byteOffset]==undefined){toRet[0]=-1;return;}
              LZW_code_fragment=getByteBits(imgStream[byteOffset], startBit_0_7, remainingBits);





             //Store the values of the bits we have just read
             //in a temporary "byte":
             ///
              byteValue=LZW_code_fragment[0];

             //For the current LZW code, concatenate the
             //bits we already have with the bits we have
             //just read, shifted left the number of bits
             //that we have already read. Concatenate
             //both values of up to 12 bits, using OR:
             ///
              toRet[numCode]|=(byteValue<<doneCodeSZ);

             //Save the new number of remaining bits after
             //reading the new chunk:
             ///
              remainingBits=LZW_code_fragment[1];

             //The number of bits already read by us
             //is given by the full code size minus
             //the bits we haven't read yet. We need
             //both the current value for this run,
             //as well as the accumulated value to know
             //when we have read the whole code already:
             ///
              curReadBits=(_ourCodeSZ-remainingBits-doneCodeSZ);
              doneCodeSZ+=(_ourCodeSZ-remainingBits-doneCodeSZ);


             //Increment the starting bit positions by
             //the number of bits we have really just read
             //in this iteration:
             ///
              startBit_0_N+=curReadBits;
              startBit_0_7+=curReadBits;


            //Here we must check whether we have just read the current
            //LZW code in its entirety, and if so, we must check whether
            //this is the Clear Code.
            //
            //If that happens to be the case, we MUST immediately
            //reset the size of the codes we will be reading, as well as
            //the number of total codes that correspond to that code size in bits:
            ///
             if(doneCodeSZ==_ourCodeSZ && toRet[numCode]==_ClearCode)
             {
              _ourCodeSZ=ourCodeSZ;            //Reset number of bits (count mode)
              _CodeSZ=CodeSZ;                  //Reset number of bits (addressing mode)
              _numCodes=Math.pow(2, _CodeSZ);  //Reset the number of possible codes for this bit size
             }

             //If we have exceeded the number of bits in a byte,
             //or if there are no more bits in this count chunk stream,
             //we must advance several values:
             ///
              if(startBit_0_7>7 || count_in_bits<=0)
              {
               startBit_0_7&=7;    //Adjust this variable to a cycle of 0 to 7
               count_in_bytes--;   //Discount one less byte
               byteOffset++;       //If more than 7 bits, then go to the next byte (obvious)
              }


            //We will accumulate and count the number of
            //bits we have just read so far for this
            //chunk of 1 to 255 bytes:
            ///
             count_in_bits-=curReadBits;


            //IMPORTANT NEW TRICK: We will only discount the number
            //of codes processed before incrementing in 1 the size
            //of the LZW code in bits, only if we have truly read
            //all of the bits for all of the codes of the current size,
            //and never before, which would make no sense and would
            //make us skip bits and get all data wrong:
            ///
             if(remainingBits<1)
               _numCodes--;

            //If the number of codes of the current bit size
            //has become 0, it means that we must increase the
            //size and the count of codes for the new codes' bit size.
            ///
             if(_numCodes==0)
             {
              _ourCodeSZ++;                    //Increment number of bits (count mode)
              _CodeSZ++;                       //Increment number of bits (addressing mode)
              _numCodes=Math.pow(2, _CodeSZ);  //Get the number of possible codes for this bit size
             }

        }






   }

  //Return the stream of unpacked codes:
  ///
   return toRet;
 }



Ahora tengo problemas en las funciones de los niveles subsiguientes, ya que no sé si están generando correctamente las salidas que deberían generar, pero creo que si logro descomprimir esta imagen, podré descomprimir la enorme mayoría de GIFs (que por lo menos, no contengan errores ni sean entrelazados, ni tengan características más avanzadas).
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 4:20 am

Por ahora puedo generar aparentemente los códigos desempacados absolutamente en cualquier condición que se me presente (este es el Paso 1 en el que este flujo de instrucciones se centró).

Ahora también puedo generar correctamente un diccionario y puedo descomprimir correctamente, pero única y exclusivamente para el primer bloque de datos. Una vez que aparece un Código Clear o un Código EOI, ya no puedo descomprimir correctamente, como se ve en el siguiente ejemplo:

/tmp/gif2src/debris/0001/gif_lzw_to_indexed_0003.html

En realidad el código anterior tiene todo lo necesario para lograr descomprimir la imagen, pero tengo que hacerlo paso a paso, y ser capaz de reanudar, lo que implicaría modificar bastante el código para que las funciones sean reanudables.






Ya que hasta este punto de este flujo de instrucciones no he modificado nada más que la función del Paso 1, del desempacado de códigos (que yo también debería hacer que sea reanudable incluso a nivel de bits), esto refleja que esa es la función más importante.

Y en este contexto, lo segundo más importante es hacer que las funciones, así como están de simples, sean reanudables iterativamente. Con esto puedo lograr manejar aparentemente cualquier imagen GIF.

Así que ahora que tengo todos estos datos y estos nuevos descubrimientos, sé que lo siguiente que debo hacer es modificar todas las funciones para que sean reanudables desde un bucle principal (un bucle de una función de dibujado en la pantalla o de guardado de los datos crudos finales en un archivo de imagen final, o en varios archivos, que contengan los diccionarios, los códigos descomprimidos, y la imagen final, y tal vez los contenidos parciales de imagen en pequeños archivos que correspondan a cada porción antes de encontrar cada Código Clear).
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Lun Ene 07, 2013 5:15 am

Después de un primer intento, el siguiente código es la modificación más simple que puedo llevar a cabo para hacer que el código actual, prácticamente así como está, sea capaz de procesar los GIF de forma completa, incluso si hay muchas porciones de por medio:

/tmp/gif2src/debris/0001/gif_lzw_to_indexed_0005.html

Por supuesto, lo que queda por hacer ahora es emplear algunos GIFs más de prueba, que sean más complejos que el del ejemplo anterior y, una vez que esto funcione bien así como está, solo me quedará formalizar y flexibilizar las funciones de LZW para GIF, al estilo de una API muy completa y versátil para ese propósito, que sea capaz de consumir tan poca memoria como sea posible, y pausarse y reanudarse iterativamente según se necesite, además de tener definiciones de parámetros y de valores de retorno muy robustos, portables, escalables, entendibles y eficientes en todas las condiciones.
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 1 de Instrucciones Humanas para completar la implementación del desempacador de códigos LZW GIF

Notapor ~ » Mié Ene 09, 2013 11:47 pm

Esta es la última versión del código que he logrado crear, y la última de este flujo de instrucciones humanas:

/tmp/gif2src/debris/0001/gif_lzw_to_indexed_0008.html

La anterior, por supuesto, por ser la última versión, es actualmente disfuncional y no hace nada visible.

Para ver la última versión capaz de dibujar un GIF enorme, ver esta página de muestra:


/tmp/gif2src/debris/0001/gif_lzw_to_indexed_0007.html

Me he dado cuenta de que el desempacador de códigos tiene una falla fundamental, porque requiere generar los códigos del diccionario. Hasta donde he logrado entender, esto es vital para determinar cuándo aumentar el tamaño de los códigos.

Hasta ahora no he logrado implementar esta nueva variedad de lógica de desempacador, y parece no poder descomprimir nada, cuando mi lógica normal, de aumentar el tamaño de los códigos simplemente después de escribir el número especificado de códigos para el tamaño de código actual, por lo menos lograba descomprimir varias líneas.

Así que ahora voy a comenzar un nuevo flujo de instrucciones, para unificar todos estos aspectos del código y lograr descomprimir los códigos, desempacando y aumentando los códigos de acuerdo al tamaño del diccionario.

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 20 invitados


cron