sábado, 12 de octubre de 2013

Algoritmo de descompresión LZS

Por ahora no tengo mucho tiempo para escribir en el blog pero quiero compartir con ustedes unas cuantas líneas de código que programé recientemente. Se trata de un programa para descomprimir datos comprimidos con el algoritmo LZS que se describe en este paper:

http://masters.donntu.edu.ua/2003/fvti/boykov/library/lzs.pdf

El programa tiene algunos errores, como que si los datos descomprimidos son mayores a 2048 bytes va a dar overflow... Pero lo bueno es que funciona y para mi propósito eso es suficiente. En fin, ahi se los dejo.


/*
 * unlzs.c
 *
 *  Created on: 10/10/2013
 *      Author: alguien
 */

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

char get_bit(char *data, int *offset, int *index) {
 char abyte;
 abyte = (data[*index] & (1 << (7 - *offset))) >> (7 - *offset);
 (*offset)++;
 if (*offset == 8) {
  (*index)++;
  *offset = 0;
 }
 return abyte;
}

char *get_nbits(int nbits, char *data, int *offset, int *index) {
 char *bytes;
 int nbytes = (nbits % 8) ? nbits / 8 + 1 : nbits / 8;
 int boffset = (nbits % 8) ? 8 - nbits % 8 : 0;
 int bindex = 0;

 bytes = malloc(sizeof(char) * nbytes);
 bzero(bytes, sizeof(char) * nbytes);

 int i;
 char bit;
 for (i = 0; i < nbits; i++) {
  bit = get_bit(data, offset, index);

  bytes[bindex] = bytes[bindex] | ((bit << 7) >> boffset);
  boffset++;
  if (boffset == 8) {
   bindex++;
   boffset = 0;
  }
 }

 return bytes;
}

int is_endmarker(char *data, int *offset, int *index) {
 int end = 0;
 int offset_tmp = *offset, index_tmp = *index;
 char *bytes = get_nbits(2, data, offset, index);

 if (bytes[0] == (char) 3) {
  bytes = get_nbits(7, data, offset, index);

  if (bytes[0] == (char) 0) {
   end = 1;
  }
 }

 *offset = offset_tmp;
 *index = index_tmp;
 return end;
}

char *uncompress_lzs(char *data) {
 int data_offset = 0, data_index = 0;
 char abyte, *bytes;

 char *history = malloc(sizeof(char) * 2048);
 int hindex = 0;

 bzero(history, sizeof(char) * 2048);

 while (1) {
  abyte = get_bit(data, &data_offset, &data_index);

  if (abyte == (char) 0) {
   // raw pattern
   bytes = get_nbits(8, data, &data_offset, &data_index);
   history[hindex] = bytes[0];
   hindex++;

  } else {
   // string pattern

   int sp_offset = 0;

   abyte = get_bit(data, &data_offset, &data_index);

   if (abyte == (char) 0) {
    // offset > 127
    bytes = get_nbits(11, data, &data_offset, &data_index);
    sp_offset = *((short *) bytes);
    sp_offset = ((sp_offset << 8) & 0xff00)
      | ((sp_offset >> 8) & 0x00ff);

   } else {
    // offset <= 127
    bytes = get_nbits(7, data, &data_offset, &data_index);
    sp_offset = (int) bytes[0];
   }

   int sp_length = 0;

   bytes = get_nbits(2, data, &data_offset, &data_index);
   if (bytes[0] != 3) {
    // length <= 4
    sp_length = ((int) bytes[0]) + 2;
   } else {
    bytes = get_nbits(2, data, &data_offset, &data_index);

    if (bytes[0] != 3) {
     // length <= 7
     sp_length = ((int) bytes[0]) + 5;
    } else {
     // length > 7
     int n = 0;
     while (1) {
      bytes = get_nbits(4, data, &data_offset, &data_index);
      if (bytes[0] == (char) 15) {
       n++;
      } else {
       break;
      }
     }
     sp_length = (n * 15) + ((int) bytes[0]) + 8;
    }
   }

   // copy pattern
   int count = 0;
   for (count = 0; count < sp_length; count++) {
    history[hindex] = history[hindex - sp_offset];
    hindex++;
   }
  }

  if (is_endmarker(data, &data_offset, &data_index) == 1) {
   // end marker
   break;
  }

 }

 return history;
}

int main(int argc, char **argv) {

 if (argc == 0) {
  printf("Modo de uso: %s <data.hex>\n", argv[0]);
  return -1;
 }

 FILE *file = NULL;

 file = fopen(argv[1], "rb");
 if (!file) {
  printf("Error. No se puede abrir el archivo.\n");
  return -1;
 }

 char *data = malloc(sizeof(char) * 2048);
 fread(data, sizeof(char), 2048, file);
 fclose(file);

 char *uncompress = uncompress_lzs(data);
 int count;
 for (count = 0; count < 2048; count++) {
  printf("%c", uncompress[count]);
 }

 return 0;
}

Un saludo.

2 comentarios:

  1. Buuu.... Vago, arregla el overflow, si es obvio! Jajaja

    ResponderEliminar
  2. Jajaja ya sé que es obvio... pero me da flojera pe! xD Además asi como está ya funciona :P

    ResponderEliminar