1. Forum
  2. Usenet
  3. COMP.COMPRESSION

  • lzw is not as complicated as everyone thinks

    From dowuikgu@gmail.com@21:1/5 to All on Tue Aug 4 19:24:46 2020
    /* unix uncompress */

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

    unsigned char *Character; /* character dictionary */
    int charactersz;

    void growcharacter(int n)
    {
    for(charactersz = 100000; charactersz <= n; charactersz = charactersz / 5 * 8);
    if(Character = realloc(Character, charactersz * sizeof(*Character)), Character == 0) err(1, "character dictionary resize error");
    }

    int *String; /* string dictionary */
    int stringsz;

    void growstring(int n)
    {
    for(stringsz = 10000; stringsz <= n; stringsz = stringsz / 5 * 8);
    if(String = realloc(String, stringsz * sizeof(*String)), String == 0) err(1, "string dictionary resize error");
    }

    int Buffer; /* bit stream */
    int buffersz;

    int readbits(int n)
    {
    while(buffersz < n) {
    int a = getc(stdin); if(a == EOF) return EOF;
    Buffer += a << buffersz;
    buffersz += 8;
    }
    int b = Buffer;
    Buffer >>= n;
    buffersz -= n;
    return b & ((1 << n) - 1);
    }

    int main(void)
    {
    if(!(getc(stdin) == 0x1f && getc(stdin) == 0x9d)) errx(1, "not a compressed file");

    int maxbits = getc(stdin) & 0x1f;
    if(!(maxbits >= 9 && maxbits <= 16)) errx(1, "dictionary bits error");

    int characterp = 0; /* current position in character dictionary */
    int stringp = 256; /* current position in string dictionary */
    int bits = 9; /* current size of code in bits */

    int code;
    while(code = readbits(bits), code != EOF) {

    if(!(code >= 0 && code <= stringp)) errx(1, "code bounds error -- invalid compressed data");

    if(stringp >= stringsz) growstring(stringp);
    String[stringp++] = characterp;

    if(code < 256) { /* character */
    if(characterp >= charactersz) growcharacter(characterp);
    Character[characterp++] = code;

    } else if(code > 256) { /* string */
    int a = String[code - 1];
    int b = String[code - 0];
    while(a <= b) {
    if(characterp >= charactersz) growcharacter(characterp);
    Character[characterp++] = Character[a++];
    }

    } else { /* flush entire dictionary */
    while(stringp % 8 != 0) { readbits(bits); stringp++; } /* what? */

    if(fwrite(Character, characterp, 1, stdout) != 1) err(1, "write error");
    characterp = 0; stringp = 256; bits = 9; /* initial state */
    }

    if(stringp == (1 << bits) && bits < maxbits) bits++; /* increase code size */
    }
    if(fwrite(Character, characterp, 1, stdout) != 1) err(1, "write error");
    if(fflush(stdout) != 0) err(1, "flush error");

    return 0;
    }

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)