Results 1 to 6 of 6

Thread: UNWHAP-like decompression or LZW reincarnation

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    OK, just recalled an old trick with an LZW decoder.

    Instead of do some shamanic things to build-up a correct LZW dictionary at decompression we may do a LZ77-like approach – keep pointers and phrase lengths in a special structure and during decoding just copy N bytes from P.

    An example:
    [code]
    TNode {
    int pos; // position of a phrase in a buffer
    int len; // length of this phrase
    };

    // ...

    while ((code = getcode()) != EOF) {
    int p = tab[code].pos;
    int l = tab
    Code:
    .len; 
     
      tab[num].pos = i; // add a new phease 
      tab[num].len = l + 1; 
      if (++num >= TABSIZE) 
        num = 256; 
     
      if (p >= 256) { 
        while (--l >= 0) 
          buf[i++] = buf[p++]; 
      } 
      else 
        buf[i++] = p; 
    }

    More info:
    http://www.ross.net/compression/down.../old_lzrw5.txt


  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Actual code:
    Code:
     
    static void decode() { 
      int n = 256; 
      int i = 0; 
     
      unsigned short s; 
      while (fread(&s, 1, sizeof(s), input) > 0) { 
        if (s >= 256) { 
          int p = tab[s].pos; 
          int l = tab[s].len; 
     
          tab[n].pos = i; 
          tab[n].len = l + 1; 
          if (++n == TABSIZE) 
            n = 256; 
     
          while (--l >= 0) 
            buf[i++] = buf[p++]; 
        } 
        else { 
          tab[n].pos = i; 
          tab[n].len = 2; 
          if (++n == TABSIZE) 
            n = 256; 
     
          buf[i++] = s; 
        } 
      } 
     
      fwrite(&buf, 1, i, output); 
    }


  3. #3
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    And encode() source code?

  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by Nania Francesco Antonio
    And encode() source code?
    encode() is a generic LZW with fixed code size (16-bit).

    OK, check out some source code which I wrote back in 2002...

    <div class=""jscript""><pre>
    #define HTABSIZE 69001
    #define BUFFSIZE 65281

    #define INITCODE 256
    #define LASTCODE 65535

    static long htab[HTABSIZE][3];
    static long buff[BUFFSIZE];

    static FILE *infile;
    static FILE *outfile;

    static void outcode(const long code) {
    register long lobyte = (code & 0xff);
    register long hibyte = ((code >> & 0xff);

    fputc(lobyte, outfile);
    fputc(hibyte, outfile);
    }

    static void encode(void) {
    register long code = -1;
    register long hash;
    register long symb = fgetc(infile);
    register long size;
    register long disp;

    for (size = 0; size < HTABSIZE; size++) {
    htab[size][2] = -1;
    }
    size = INITCODE;

    while (symb != EOF) {
    if (code != -1) {
    hash = ((symb << ^ code);

    if (hash != 0) {
    disp = (HTABSIZE - hash);
    } else {
    disp = 1;
    }

    while ((htab[hash][2] != -1) && ((htab[hash][0] != code)
    || (htab[hash][1] != symb))) {
    if ((hash -= disp) < 0) {
    hash += HTABSIZE;
    }
    }
    } else {
    hash = symb;
    }

    if ((code != -1) && (htab[hash][2] == -1)) {
    outcode(code);

    htab[hash][0] = code;
    htab[hash][1] = symb;
    htab[hash][2] = size;

    if (size++ == LASTCODE) {
    for (size = 0; size < HTABSIZE; size++) {
    htab[size][2] = -1;
    }
    size = INITCODE;
    }
    code = -1;
    } else {
    if (code != -1) {
    code = htab[hash][2];
    } else {
    code = hash;
    }
    symb = fgetc(infile);
    }
    }

    if (code != -1) {
    outcode(code);
    }
    }
    [/code]


    Draft, and school-boy like... However, thats what Im starting with... And it works even today...

  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    The benefit of such simple compression in a small and simple decoder. For example, I rewritten the decoder using Delphi and added it to my EXE-packer. A file packed with my EXE-packer can be found here:
    mptrack.exe (787 KB)


  6. #6
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Thanks Encode!

Similar Threads

  1. LZW, LZMW and LZAP comparison
    By encode in forum Data Compression
    Replies: 14
    Last Post: 3rd August 2017, 16:34
  2. LZW with unbounded dictionary
    By encode in forum Data Compression
    Replies: 34
    Last Post: 28th September 2010, 04:30
  3. LZW v0.2 is here!
    By encode in forum Forum Archive
    Replies: 6
    Last Post: 8th February 2008, 23:53
  4. LZW v0.1 is here!
    By encode in forum Forum Archive
    Replies: 20
    Last Post: 2nd February 2008, 14:46
  5. New LZW variant
    By encode in forum Forum Archive
    Replies: 14
    Last Post: 28th January 2008, 22:33

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •