lzw is not as complicated as everyone thinks

[dowu...@gmail.com]

/* 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;
}