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)