Fecha actual Jue Ago 22, 2019 8:34 am

Código C para LZW (Manish Kumar Srivastva)

El lugar para llevar a cabo minería en código que nos parezca altamente interesante, sin la obligación de poder llegar a completar el análisis de inmediato, de equivocarse, o de sobrecargarse con la tarea inicialmente innecesaria e impráctica de mantener estándares de documentación formales. Esto es minería pura, y con toda seguridad va a ser un trabajo sucio, y nos vamos a ensuciar en esta mina de código para extraer grandes tesoros.


Usuarios leyendo este tema: Ninguno

Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 7:50 am

Estado: Análisis Inicial y Estudiando la Documentación
++++++++++++++++++++++++++++++++++++++++++++++

Este código lo encontré aquí:

Looking for library which implements LZW compression/decompression

Este tiene varios errores de sintaxis y advertencias del compilador. Así que he desactivado y reemplazado 2 líneas comentándolas por ahora, así que este código no se puede considerar completo:

Código: Seleccionar todo
    *buffer++ = append_character/code/;
    code=prefix_code/code/;


Para este, dado el contexto en el que append_character y prefix_code son punteros a arreglos, y que estas líneas están dentro de un IF que limita hasta un valor de 255, la parte que dice /code/ más probablemente debería ser un índice dentro del arreglo:

Código: Seleccionar todo
    *buffer++ = append_character[ code ];
    code=prefix_code[ code ];


Claro, se ve la relación, dado que tanto en StackOverflow como en este foro (y en la mayoría de los otros), escribir simplemente [code] puede confundir al intérprete de BBCode (principalmente si esta "etiqueta" o en este caso realmente un índice dentro de un arreglo, no está ya dentro de un bloque inicial y final de una etiqueta idéntica [code]).



Además, sin tener un mínimo de conceptos de LZW, no podemos entender este código (al menos no tan fácil ni rápidamente).

NOTA: Al final, usé el código fuente original y corregido que está en:

LZW Data Compression

Código: Seleccionar todo
/********************************************************************
**
** Copyright (c) 1989 Mark R. Nelson
**
** LZW data compression/expansion demonstration program.
**
** April 13, 1989
**
** Minor mods made 7/19/2006 to conform with ANSI-C - prototypes, casting,
** and argument agreement.
**
*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BITS 12                   /* Setting the number of bits to 12, 13*/
#define HASHING_SHIFT (BITS-8)    /* or 14 affects several constants.    */
#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to   */
#define MAX_CODE MAX_VALUE - 1    /* compile their code in large model if*/
                                  /* 14 bits are selected.               */
#if BITS == 14
  #define TABLE_SIZE 18041        /* The string table size needs to be a */
#endif                            /* prime number that is somewhat larger*/
#if BITS == 13                    /* than 2**BITS.                       */
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                  /* This is the code value array        */
unsigned int *prefix_code;        /* This array holds the prefix codes   */
unsigned char *append_character;  /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */

/*
 * Forward declarations
 */
void compress(FILE *input,FILE *output);
void expand(FILE *input,FILE *output);
int find_match(int hash_prefix,unsigned int hash_character);
void output_code(FILE *output,unsigned int code);
unsigned int input_code(FILE *input);
unsigned char *decode_string(unsigned char *buffer,unsigned int code);

/********************************************************************
**
** This program gets a file name from the command line.  It compresses the
** file, placing its output in a file named test.lzw.  It then expands
** test.lzw into test.out.  Test.out should then be an exact duplicate of
** the input file.
**
*************************************************************************/

main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];

/*
**  The three buffers are needed for the compression phase.
*/
  code_value=(int*)malloc(TABLE_SIZE*sizeof(int));
  prefix_code=(unsigned int *)malloc(TABLE_SIZE*sizeof(unsigned int));
  append_character=(unsigned char *)malloc(TABLE_SIZE*sizeof(unsigned char));
  if (code_value==NULL || prefix_code==NULL || append_character==NULL)
  {
    printf("Fatal error allocating table space!\n");
    exit(-1);
  }
/*
** Get the file name, open it up, and open up the lzw output file.
*/
  if (argc>1)
    strcpy(input_file_name,argv[1]);
  else
  {
    printf("Input file name? ");
    scanf("%s",input_file_name);
  }
  input_file=fopen(input_file_name,"rb");
  lzw_file=fopen("test.lzw","wb");
  if (input_file==NULL || lzw_file==NULL)
  {
    printf("Fatal error opening files.\n");
    exit(-1);
  };
/*
** Compress the file.
*/
  compress(input_file,lzw_file);
  fclose(input_file);
  fclose(lzw_file);
  free(code_value);
/*
** Now open the files for the expansion.
*/
  lzw_file=fopen("test.lzw","rb");
  output_file=fopen("test.out","wb");
  if (lzw_file==NULL || output_file==NULL)
  {
    printf("Fatal error opening files.\n");
    exit(-2);
  };
/*
** Expand the file.
*/
  expand(lzw_file,output_file);
  fclose(lzw_file);
  fclose(output_file);

  free(prefix_code);
  free(append_character);
}

/*
** This is the compression routine.  The code should be a fairly close
** match to the algorithm accompanying the article.
**
*/

void compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;

  next_code=256;              /* Next code is the next available string code*/
  for (i=0;i<TABLE_SIZE;i++)  /* Clear out the string table before starting */
    code_value[i]=-1;

  i=0;
  printf("Compressing...\n");
  string_code=getc(input);    /* Get the first code                         */
/*
** This is the main loop where it all happens.  This loop runs util all of
** the input has been exhausted.  Note that it stops adding codes to the
** table after all of the possible codes have been defined.
*/
  while ((character=getc(input)) != (unsigned)EOF)
  {
    if (++i==1000)                         /* Print a * every 1000    */
    {                                      /* input characters.  This */
      i=0;                                 /* is just a pacifier.     */
      printf("*");
    }
    index=find_match(string_code,character);/* See if the string is in */
    if (code_value[index] != -1)            /* the table.  If it is,   */
      string_code=code_value[index];        /* get the code value.  If */
    else                                    /* the string is not in the*/
    {                                       /* table, try to add it.   */
      if (next_code <= MAX_CODE)
      {
        code_value[index]=next_code++;
        prefix_code[index]=string_code;
        append_character[index]=character;
      }
      output_code(output,string_code);  /* When a string is found  */
      string_code=character;            /* that is not in the table*/
    }                                   /* I output the last string*/
  }                                     /* after adding the new one*/
/*
** End of the main loop.
*/
  output_code(output,string_code); /* Output the last code               */
  output_code(output,MAX_VALUE);   /* Output the end of buffer code      */
  output_code(output,0);           /* This code flushes the output buffer*/
  printf("\n");
}

/*
** This is the hashing routine.  It tries to find a match for the prefix+char
** string in the string table.  If it finds it, the index is returned.  If
** the string is not found, the first available index in the string table is
** returned instead.
*/

int find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;

  index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
  if (index == 0)
    offset = 1;
  else
    offset = TABLE_SIZE - index;
  while (1)
  {
    if (code_value[index] == -1)
      return(index);
    if (prefix_code[index] == hash_prefix &&
        append_character[index] == hash_character)
      return(index);
    index -= offset;
    if (index < 0)
      index += TABLE_SIZE;
  }
}

/*
**  This is the expansion routine.  It takes an LZW format file, and expands
**  it to an output file.  The code here should be a fairly close match to
**  the algorithm in the accompanying article.
*/

void expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;

  next_code=256;           /* This is the next available code to define */
  counter=0;               /* Counter is used as a pacifier.            */
  printf("Expanding...\n");

  old_code=input_code(input);  /* Read in the first code, initialize the */
  character=old_code;          /* character variable, and send the first */
  putc(old_code,output);       /* code to the output file                */
/*
**  This is the main expansion loop.  It reads in characters from the LZW file
**  until it sees the special code used to inidicate the end of the data.
*/
  while ((new_code=input_code(input)) != (MAX_VALUE))
  {
    if (++counter==1000)   /* This section of code prints out     */
    {                      /* an asterisk every 1000 characters   */
      counter=0;           /* It is just a pacifier.              */
      printf("*");
    }
/*
** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
** case which generates an undefined code.  It handles it by decoding
** the last code, and adding a single character to the end of the decode string.
*/
    if (new_code>=next_code)
    {
      *decode_stack=character;
      string=decode_string(decode_stack+1,old_code);
    }
/*
** Otherwise we do a straight decode of the new code.
*/
    else
      string=decode_string(decode_stack,new_code);
/*
** Now we output the decoded string in reverse order.
*/
    character=*string;
    while (string >= decode_stack)
      putc(*string--,output);
/*
** Finally, if possible, add a new code to the string table.
*/
    if (next_code <= MAX_CODE)
    {
      prefix_code[next_code]=old_code;
      append_character[next_code]=character;
      next_code++;
    }
    old_code=new_code;
  }
  printf("\n");
}

/*
** This routine simply decodes a string from the string table, storing
** it in a buffer.  The buffer can then be output in reverse order by
** the expansion program.
*/

unsigned char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;

  i=0;
  while (code > 255)
  {
    *buffer++ = append_character[code];
    code=prefix_code[code];
    if (i++>=MAX_CODE)
    {
      printf("Fatal error during code expansion.\n");
      exit(-3);
    }
  }
  *buffer=code;
  return(buffer);
}

/*
** The following two routines are used to output variable length
** codes.  They are written strictly for clarity, and are not
** particularyl efficient.
*/

unsigned int input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;

  while (input_bit_count <= 24)
  {
    input_bit_buffer |=
        (unsigned long) getc(input) << (24-input_bit_count);
    input_bit_count += 8;
  }
  return_value=input_bit_buffer >> (32-BITS);
  input_bit_buffer <<= BITS;
  input_bit_count -= BITS;
  return(return_value);
}

void output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;

  output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
  output_bit_count += BITS;
  while (output_bit_count >= 8)
  {
    putc(output_bit_buffer >> 24,output);
    output_bit_buffer <<= 8;
    output_bit_count -= 8;
  }
}
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 9:22 am

Capa de Nombres de Identificadores

Constantes Globales
BITS
HASHING_SHIFT
MAX_VALUE
MAX_CODE

TABLE_SIZE



Variables Globales
prefix_code
append_character
decode_stack



Funciones Globales
compress
expand
find_match
output_code
input_code
decode_string



________________________________________________________
________________________________________________________
________________________________________________________
________________________________________________________


Variables de la Función compress
input
output
______________________
next_code
character
string_code
index




Variables de la Función find_match
hash_prefix
hash_character
________________________________
index
offset





Variables de la Función expand
input
output
________________________________
next_code
new_code
old_code
character
counter
string




Variables de la Función decode_string
buffer
code
________________________________
i





Variables de la Función input_code
input
________________________________
return_value
input_bit_count
input_bit_buffer





Variables de la Función output_code
output
code
________________________________
output_bit_count
output_bit_buffer



Variables de la Función main
argc
argv
________________________________
input_file
output_file
lzw_file
input_file_name
command






.
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 10:34 am

Capa de Descripción Verbal Superficial de Operaciones Llevadas A Cabo


Función main
0.
Primero reservamos tres bloques de memoria de TABLE_SIZE elementos, y cada elemento es del tamaño de un int para la primera, de un unsigned int para la segunda, y de un unsigned char para la tercera.

1.
Luego de usar las funciones de reserva de memoria, verificamos que de hecho ahora cada bloque apunta a una región válida de memoria (valor diferente de NULL). Si cualquiera de estos bloques es inválido, salimos del programa con un error.

2.
Recordemos lo siguiente: en C, un programa con una función main con argc y argv siempre tiene al menos 1 argumento de línea de comandos (la ruta completa del archivo del programa); así que los argumentos pasados por el usuario comienzan en el segundo elemento del arreglo de cadenas argv.

3.
Ahora vamos a obtener el nombre de archivo de entrada de la línea de comandos. Para esto, verificamos que haya al menos 2 argumentos de línea de comandos (separados por espacios en blanco).

4.
Tomamos el segundo argumento, y lo utilizamos como el nombre del archivo de entrada. Si recibimos menos de 2 argumentos de línea de comandos, entonces le pedimos al usuario que ingrese un nombre de archivo en la consola.

5.
Ahora intentamos abrir el archivo en modo binario, para obtener un manejador a este, y también aprovechamos a crear un archivo binario llamado "test.lzw".

6.
Verificamos que ambos archivos han sido accedidos correctamente, y si alguno de sus manejadores es un valor de error (NULL) salimos del programa con un error.

7.
Vemos si el identificador de la acción a llevar a cabo es 'r'. De ser así, comprimimos el archivo de entrada que teníamos antes y lo guardamos en "test.lzw". Luego cerramos nuestro archivo de entrada, nuestro archivo "test.lzw", y liberamos la memoria de la primera tabla que reservamos en el Paso 0.

8.
Ahora nos disponemos a probar la funcionalidad de descompresión. Para esto abrimos nuevamente nuestro archivo comprimido "test.lzw" pero ahora en formato de lectura binaria. Y también creamos el archivo binario "test.out", en el que descomprimiremos nuevamente nuestro archivo comprimido "test.lzw" (los contenidos del archivo de entrada y de "test.out" deberían ser totalmente idénticos, o tendríamos un error absolutamente).

Para esto, simplemente tomamos el archivo, ahora de entrada, "test.lzw", lo descomprimimos, y lo guardamos en el archivo de salida "test.out". Luego siemplemente cerramos el archivo "test.lzw", el archivo "test.out", y liberamos la segunda y la tercera tabla que reservamos en el Paso 0.

Con esto terminamos las tareas de nuestra función main.
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función compress
0.
Inicializamos el contador del siguiente código disponible en 256, ya que como recordamos, el algoritmo LZW inicializa los primeros 256 códigos de su diccionario a los valores ASCII desde 0 hasta 255.

Luego, llenamos todos los elementos de la primera tabla reservada en el Paso 0 de main, con el valor -1.


1.
Ahora usamos int getc ( FILE * stream );

Leemos el primer carácter de nuestros datos de entrada.


2.0.
Ahora queremos entrar en un bucle, en el que permaneceremos mientras el carácter que leamos de nuestros datos de entrada no sea la marca de EOF.


2.1.
Dentro del bucle tenemos un contador. Este originalmente es naturalmente 0, pero lo incrementamos en 1 por cada carácter que leemos. Cada vez que el contador alcanza 1000, imprimimos un asterisco * y lo ponemos nuevamente a cero. Esto es simplemente para demostrarle al usuario que el programa no está en un bucle infinito sino que está trabajando.


2.2.
Ahora buscamos una coincidencia en base al carácter actual que leímos en el Paso 1, y que seguiremos leyendo dentro de este bucle. También en base al carácter actual. Es decir, buscamos el carácter actual para ver si no fue agregado ya (recordemos que esto puede tener que ver con el hecho de que el diccionario LZW siempre comienza inicializándose con los valores de todos los caracteres ASCII de 8 bits). En esto nos ayudará nuestra función find_match, la cual devolverá el índice del elemento de carácter de valor entero, o -1 si no fue encontrado en nuestra tabla/diccionario.


2.3.
Ahora vemos si el código de la cadena fue encontrado. Si ese es el caso, tomamos el valor del la cuenta del siguiente código del diccionario de la cadena en el índice encontrado, en la primera tabla que reservamos en el Paso 0 de main.

Si el código de la cadena no se encontró, intentamos agregarlo. Para esto, vemos si no hemos alcanzado todavía el límite máximo de códigos en nuestra tabla de códigos.

Si todavía estamos por debajo de este límite, agregamos la cuenta del código al índice, para la primera tabla, e incrementamos dicha cuenta (lo que no entiendo es que en este caso, entonces agregaríamos al índice -1, y eso sería un error). Para la segunda tabla (código prefijo), colocamos el valor del carácter que leímos en el Paso 2.2 (considerado el "carácter anterior"). Para la tercera tabla, agregamos el "carácter adjunto" en el índice, que leemos de los datos de entrada en cada iteración, y que por lo tanto podemos considerar el "carácter actual".

Hacemos esto hasta el final de los datos.


2.4.
Una vez que estamos fuera del bucle (que dejará sobrado al último carácter aparentemente), colocamos el código de salida para dicho útlimo carácter, y luego el código para el código del final del búfer, basado en el valor de MAX_VALUE. Finalmente, hacemos flush al búfer de salida. En este programa de C, esto se hizo usando un printf que imprime una nueva línea "\n".


__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función find_match
0.
Calculamos el índice en base a un "prefijo de hash" (el carácter anterior) y un "carácter de hash" (el carácter actual).

Efectuamos un desplazamiento del carácter de hash y a esto le aplicamos XOR con el prefijo de hash:
indice=(caracter_hash<<DESPLAZAMIENTO_HASHING)^prefijo_hash;


1.
Si el índice es 0 después de esto, establecemos nuestro offset a 1. De lo contrario, nuestro offset es TAMANO_TABLA-indice.


2.
Ahora entramos en un bucle infinito, que solo se detiene al ejecutar return.

Si el valor de código de nuestro índice no está inicializado (-1), devolvemos este valor de índice.

Si el código de prefijo en el índice concuerda con el prefijo de hash, y si el carácter adjuntado concuerda con el carácter de hash, devolvemos este índice (parece que podríamos unir todas estas condiciones y las de la línea anterior en un único caso).

En este punto ya deberíamos haber regresado, pero sino, le restamos el valor del offset, calculado en el Paso 1, a nuestro valor de índice.

Ahora vemos si el índice es menor a 0. Si es así, le agregamos a nuestro valor de índice, el valor de TAMANO_TABLA.

Continuamos con el bucle en todo este Paso 2.


__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función expand
0.
Debido a que el diccionario LZW tiene inicializadas sus primeras 256 entradas a los caracteres ASCII (0 a 255), inicializamos un contador a 256. También inicializamos una variable de contador a 0.


expand_1.


2.
También inicializamos nuestra variable "carácter" al "código antiguo" que acabamos de obtener en el Paso 1. Finalmente, colocamos este "carácter antiguo" en nuestro archivo de salida.


3.0.
Ahora entramos en un bucle, en el que continuaremos mientras el "código nuevo" basado en el "código de entrada" sea diferente de MAX_VALUE (que simplemente es el máximo valor que puede contener nuestro paquete de bits con todos sus bits a 1).


3.1.
Primero, tenemos un IF en el que la variable de contador se incrementa en 1 cada 1000 bytes. En ese caso, imprimimos un asterisco y ponemos a 0 el contador nuevamente, solo para indicarle al usuario que el programa está trabajando.


3.2.
Ahora usamos otro IF, en el que verificamos si el "nuevo código" es mayor o igual que el "código siguiente". Si es así, colocamos el valor del carácter obtenido en el Paso 2 en nuestra "pila de decodificación" (que mantiene una cadena decodificada de 4000 bytes).

Luego, obtenemos en la variable de "cadena" una "cadena decodificada" basándonos en la posición siguiente (+1) de la "pila de decodificación" y el "código antiguo". Para esto nos valemos de la función decode_string.


3.2.0.
Sino, si el "nuevo código" no es mayor o igual que el "código siguiente", basamos nuestra variable de "cadena" en la posición actual de la "pila de decodificación" y el "código antiguo". Nos valemos de la función decode_string.


3.3.
Ahora guardamos la cadena decodificada en orden inverso y la colocamos en nuestro archivo de salida, carácter por carácter.

Para esto, nuestra variable "carácter" apunta al valor en la posición actual de nuestra variable "cadena".

Luego, en un bucle, iteramos mientras la posición de nuestra cadena sea mayor o igual que nuestra "pila de decodificación".


3.4.
Finalmente, tratamos de agregar un código nuevo a la tabla de cadenas.

Para esto, vemos si el "siguiente código" es menor o igual a MAX_CODE, y si es así, agregamos el "código antiguo" a la posición apuntada por el "siguiente código" a nuestra segunda tabla reservada en main (el "código prefijo").

Luego, colocamos la variable "carácter" en la posición apuntada por el "siguiente código" a nuestra tercera tabla ("carácter adjunto") que reservamos en main.

Luego, incrementamos en 1 el "siguiente código".


3.5.
Ahora, colocamos el valor del "código nuevo" en la variable del "código antiguo". Terminamos el bucle y hacemos flush en el búfer de datos imprimiendo una nueva línea.


__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función decode_string
0.
Nos basamos en un "búfer de datos" y en un "código" entero sin signo. Establecemos un índice i a 0.


1.0.
Entramos en un bucle, en el que permaneceremos mientras el "código" sea mayor a 255.


1.1.
En la posición actual del "búfer de datos", colocamos el "carácter adjunto" apuntado por el "código". E incrementamos el puntero del "búfer".


1.2.
Ahora, el "código" lo ponemos al valor del "código prefijo" apuntado por el "código" actual él mismo.


1.3.
Ahora vemos, si el índice i es mayor o igual a MAX_CODE, salimos del programa con un error fatal con valor de -3. Luego de la comprobación del índice i, lo aumentamos en 1.


2.
En este punto estamos fuera del bucle. Colocamos el valor del "código" en la posición actualmente apuntada por el "búfer".


3.
Luego de esto, devolvemos el "búfer", como valor de puntero (simplemente la variable buffer).


__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función input_code
0.
Nos basamos en los datos de un archivo de entrada.


1.
Establecemos una variable de "cuenta de bits de entrada" a 0. Hacemos lo mismo con una variable de "búfer de bits de entrada".


2.0.
Entramos en un bucle, mientras la "cuenta de bits de entrada" sea menor o igual a 24.


2.1.
Aplicamos OR al "búfer de bits de entrada" leyendo un carácter de la entrada y desplazándolo a la izquierda (24-cuenta_bits_entrada) posiciones:
bufer_bits_entrada|=getc(entrada)<<(24-cuenta_bits_entrada);


2.2.
Agregamos 8 a la cuenta de bits de entrada (8 bits es igual a 1 byte, o carácter de entrada).


3.
En este punto estamos fuera del bucle. Calculamos una variable de "valor de retorno" desplazando la variable de "búfer de bits de entrada" (32-BITS) posiciones a la derecha:
valor_retorno=bufer_bits_entrada>>(32-BITS);


4.
Ahora el "búfer de bits de entrada" lo desplazamos BITS posiciones hacia la izquierda.


5.
Ahora a la "cuenta de bits de entrada" le restamos BITS.


6.
Devolvemos el valor de retorno, el cual en C es una variable entera sin signo.


__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Función output_code
0.
Nos basamos en un archivo de salida, al cual escribiremos, y a un "código" entero sin signo. Colocamos las variables de "cuenta de bits de salida" y de "búfer de bits de salida" a 0.


1.
Al "búfer de bits de salida" le aplicamos OR a la operación de desplazar el valor del "código" (32-bits-cuenta_bits_salida) posiciones a la izquierda:
bufer_bits_salida|=codigo<<(32-bits-cuenta_bits_salida);


2.
Le sumamos el valor de BITS a la "cuenta de bits de salida".


2.0.
Entramos en un bucle, mientras la "cuenta de bits de salida" sea mayor o igual a 8.


2.1.
Escribimos el valor del "búfer de bits de salida" desplazado 24 bits a la derecha, a nuestro archivo de salida.


2.2.
Desplazamos nuestro "búfer de bits de salida" 8 bits a la izquierda.


2.3.
Le restamos 8 (8 bits de 1 byte, o carácter) a la "cuenta de bits de salida".

Con esto termina todo el programa.
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 10:35 am

Capa de Descripción Mediante Especificación de Operaciones Llevadas A Cabo

Para esto lo más conveniente será:

  • Leer el documento que acompaña a este programa, y traducirlo, así como procesar los comentarios de los usuarios en ese blog para ese programa, para entenderlo al máximo en el menor tiempo posible.

  • Si sentimos que es necesario, leer el documento técnico original para el algoritmo LZW, por Welch.

Nuestros tutoriales:
http://marknelson.us/1989/10/01/lzw-data-compression/
http://marknelson.us/2011/11/08/lzw-revisited/


Hemos cacheado las páginas para nuestro primer tutorial de LZW, que corresponde al código fuente anterior:
LZW Data Compression
LZW Revisited


Y los traduciremos en las siguientes direcciones. Esto me servirá en lo personal para procesar al máximo y en el menor tiempo posible la información contenida en estos tutoriales, obtener su esencia, poder estudiar y traducir la especificación en cuestión comprendiéndola de mucha mejor manera, estudiar otras implementaciones de código y al final crear mi implementación de LZW con licencia de dominio público:
Compresión de Datos LZW
LZW Revisitado
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 11:07 am

Capa de Trucos Sintácticos


Funció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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Sab Nov 17, 2012 11:08 am

Capa de Recodificación Manual de Todo el Código


[code][/code]
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Dom Nov 18, 2012 7:13 am

Capa de Consideraciones Finales

Si usamos un archivo de entrada de 1 byte, siempre obtenemos compresión negativa y un archivo de 4 bytes.

Probablemente obtendremos compresión negativa para un archivo de hasta 256 bytes, en los que ningún carácter está repetido, y en general probablemente más aún si dichos caracteres están dispuestos de forma totalmente aleatoria.

ERROR: Si usamos un archivo vacío como entrada, si lo descomprimimos con este programa obtenemos un archivo con 1 byte con el valor 0xFF.

Necesitaremos una versión del programa que trabaje de forma pausada, y muestre visualmente todas las operaciones para cada carácter o bloque de entrada, para que así podamos entender mucho mejor el funcionamiento del algoritmo. Podemos empezar con entradas de 0, 1, 2, 3 y 4 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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Jue Nov 22, 2012 3:51 pm

NOTA: Este programa usa una función de hashing de tipo XOR, la cual no fue explicada; así que tendremos que estudiar y documentar muchos algoritmos e ideas generales de hashing de tipo XOR, para poder comprender de mejor forma, entre otros tipos de hashing eficiente para un programa como este y ser usadas como direcciones de arreglo.
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: Código C para LZW (Manish Kumar Srivastva)

Notapor ~ » Lun Dic 17, 2012 10:48 pm

Para familiarizarnos más con este programa, he eliminado todo el código de compresión para crear a unlzw.c, que funciona así:

unlzw entrada.lzw salida.bin

Es decir que este código solo sirve para descomprimir archivos comprimidos con LZW.

El problema que veo es que si no sabemos cuántos bits se usaron para la compresión, esta resultará en la generación de basura.

Por ejemplo, traté de descomprimir los datos gráficos crudos (sin cuentas de cadenas LZW ni nada más) de un GIF, y al intentar descomprimir, no obtuve el tamaño esperado (sino la mitad de este) y valores erróneos.

Es decir que los GIF puede que usen menos de 12 bits, tal vez 8 bits por palabra.

Pero la cuestión es que este programa, así como está, parece no poder descomprimir datos GIF.

Código: Seleccionar todo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BITS 12                         /* Establece el número de bits a 12, 13   */
#define DESPLAZAMIENTO_HASHING (BITS-8) /* o 14 para afectar varias constantes.   */
#define VALOR_MAXIMO (1 << BITS) - 1    /* Nota que las máquinas MS-DOS necesitan */
#define CODIGO_MAXIMO VALOR_MAXIMO - 1  /* compilar su código en modo large si se */
                                        /* seleccionan 14 bits.                   */
#if BITS == 14
  #define TAMANO_TABLA 18041     /* El tamaño de la tabla de cadenas necesita ser */
#endif                           /* un número primo que sea un tanto mayor        */
#if BITS == 13                   /* que 2**BITS.                                  */
  #define TAMANO_TABLA 9029
#endif
#if BITS <= 12
  #define TAMANO_TABLA 5021
#endif

void *malloc();

int *valor_codigo;                       /* Este es arreglo de valores de código          */
unsigned int *codigo_prefijo;            /* Este arreglo mantiene los códigos prefijos    */
unsigned char *caracter_adjunto;         /* Este arreglo mantiene los caracteres adjuntos */
unsigned char pila_decodificacion[4000]; /* Este arreglo mantiene la cadena decodificada  */

/*
 * Declaraciones hacia adelante
 */
void comprimir(FILE *entrada, FILE *salida);
void expandir(FILE *entrada, FILE *salida);
unsigned int codigo_entrada(FILE *entrada);
unsigned char *decodificar_cadena(unsigned char *buffer, unsigned int codigo);

/********************************************************************
**
** Este programa obtiene el nombre de archivo desde la línea de comandos.
** Comprime el archivo, colocando su salida en un archivo llamado prueba.lzw.
** Luego expande prueba.lzw en prueba.out. Prueba.out entonces debería ser un
** duplicado exacto del archivo de entrada.
**
*************************************************************************/

main(int argc, char *argv[])
{
FILE *archivo_entrada;
FILE *archivo_salida;
FILE *archivo_lzw;
char nombre_archivo_entrada[81];
char nombre_archivo_salida[81];

/*
**  Los tres búferes se necesitan para la fase de compresión.
*/
  valor_codigo=(int*)malloc(TAMANO_TABLA*sizeof(int));
  codigo_prefijo=(unsigned int *)malloc(TAMANO_TABLA*sizeof(unsigned int));
  caracter_adjunto=(unsigned char *)malloc(TAMANO_TABLA*sizeof(unsigned char));
  if (valor_codigo==NULL || codigo_prefijo==NULL || caracter_adjunto==NULL)
  {
    printf("Error fatal reservando espacio de tabla\n");
    exit(-1);
  }

/*
** Obtiene el nombre de archivo, lo abre, y abre el archivo de salida LZW.
*/
  if (argc>2)
  {
   strcpy(nombre_archivo_entrada, argv[1]);
   strcpy(nombre_archivo_salida, argv[2]);
  }


  else
  {
    printf("Nombre de archivo de entrada? ");
    scanf("%s", nombre_archivo_entrada);

    printf("Nombre de archivo de salida? ");
    scanf("%s", nombre_archivo_salida);
  }




/*
** Ahora abrir los archivos para ña expansión.
*/
  archivo_entrada=fopen(nombre_archivo_entrada, "rb");
  archivo_salida=fopen(nombre_archivo_salida, "wb");
  if (archivo_entrada==NULL)
  {
    printf("(1) Error fatal abriendo archivo de entrada.\n");
    exit(-1);
  }

  if(archivo_salida==NULL)
  {
    printf("(1) Error fatal abriendo archivo de salida.\n");
    exit(-1);
  }



/*
** Expandir el archivo.
*/
  expandir(archivo_entrada, archivo_salida);
  fclose(archivo_entrada);
  fclose(archivo_salida);

  free(codigo_prefijo);
  free(caracter_adjunto);
}





/*
** Esta es la rutina de expansión. Este toma un archivo en formato LZW, y lo
** expande a un archivo de salida. El código aquí debería ser una coincidencia
** bastante cercana al algoritmo que acompaña el artículo.
*/

void expandir(FILE *entrada, FILE *salida)
{
 unsigned int siguiente_codigo;
 unsigned int nuevo_codigo;
 unsigned int codigo_antiguo;
 int caracter;
 int contador;
 unsigned char *cadena;

  siguiente_codigo=256;       /* Este es el siguiente código disponible a definir */
  contador=0;                 /* Contador usado como un pacificador.              */
  printf("Expandiendo...\n");

  codigo_antiguo=codigo_entrada(entrada); /* Leer el primer código, inicializar la    */
  caracter=codigo_antiguo;                /* variable de carácter, y enviar el primer */
  putc(codigo_antiguo, salida);           /* código al archivo de salida              */

 /*
 ** Este es el bucle de expansión principal. Este lee los caracteres desde
 ** el archivo LZW de entrada hasta que mira el código especial usado para
 ** indicar el final de los datos.
 */
  while ((nuevo_codigo=codigo_entrada(entrada)) != (VALOR_MAXIMO))
  {
    if (++contador==1000)  /* Esta sección de código imprime     */
    {                      /* un asterisco cada 1000 caracteres. */
      contador=0;          /* No es más que un pacificador.      */
      printf("*");
    }

   /*
   ** Este código verifica el caso especial CADENA+CARACTER+CADENA+CARACTER+CADENA
   ** el cual genera un código indefinido. Lo maneja al decodificar
   ** el último código, y agregando un carácter individual al final de la cadena
   ** decodificada.
   */
    if (nuevo_codigo>=siguiente_codigo)
    {
      *pila_decodificacion=caracter;
      cadena=decodificar_cadena(pila_decodificacion+1, codigo_antiguo);
    }

   /*
   ** De lo contrario efectuamos una decodificación directa del nuevo código.
   */
    else
      cadena=decodificar_cadena(pila_decodificacion, nuevo_codigo);

   /*
   ** Ahora devolvemos la cadena decodificada en orden inverso.
   */
    caracter=*cadena;
    while (cadena >= pila_decodificacion)
      putc(*cadena--, salida);

   /*
   ** Finalmente, si es posible, agregamos un nuevo código a la tabla de cadenas.
   */
    if (siguiente_codigo <= CODIGO_MAXIMO)
    {
      codigo_prefijo[siguiente_codigo]=codigo_antiguo;
      caracter_adjunto[siguiente_codigo]=caracter;
      siguiente_codigo++;
    }
    codigo_antiguo=nuevo_codigo;
  }
  printf("\n");
}




/*
** Esta rutina simplemente decodifica una cadena desde la tabla de cadenas,
** almacenándola en un búfer. El búfer entonces puede devolverse en orden
** inverso por el programa de expansión.
*/
unsigned char *decodificar_cadena(unsigned char *buffer, unsigned int codigo)/***/
{
int i;

  i=0;
  while (codigo > 255)
  {
    *buffer++ = caracter_adjunto[codigo];
    codigo=codigo_prefijo[codigo];
    if (i++>=CODIGO_MAXIMO)
    {
      printf("Error fatal durante la expansión del código.\n");
      exit(-3);
    }
  }
  *buffer=codigo;
  return(buffer);
}




/*
** Las siguientes dos rutinas se usan para devolver códigos de
** longitud variable. Están escritas estrictamente para ser claras, y no
** son particularmente eficientes.
*/
unsigned int codigo_entrada(FILE *entrada)/***/
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;

  while (input_bit_count <= 24)
  {
    input_bit_buffer |=
        (unsigned long) getc(entrada) << (24-input_bit_count);
    input_bit_count += 8;
  }
  return_value=input_bit_buffer >> (32-BITS);
  input_bit_buffer <<= BITS;
  input_bit_count -= BITS;
  return(return_value);
}
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 La Cantera del Código

¿Quién está conectado?

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


cron