#ifndef lint static char sccsid[] = "@(#)uncompress.c 1.3 88/12/21"; #endif #include "cbratp.h" #define FIRST 257 /* first free entry */ #define CLEAR 256 /* table clear output code */ #define INIT_BITS 9 /* initial number of bits/code */ #define BITS 12 #define HSIZE 5003 /* 80% occupancy */ #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) static int n_bits = INIT_BITS; /* number of bits/code */ static int maxbits = BITS; /* user settable max # bits/code */ static int maxcode = MAXCODE(INIT_BITS); /* maximum code, given n_bits */ static int maxmaxcode = 1 << BITS; /* should NEVER generate this */ static int free_ent = FIRST; /* first unused entry */ static u_char rmask[9] = { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff }; static int clear_flg = 0; static u_short tab_prefix[HSIZE]; static u_char tab_suffix[HSIZE] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31, 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47, 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63, 64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79, 80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95, 96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111, 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127, 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159, 160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175, 176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191, 192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207, 208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223, 224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239, 240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255, /* zero fill rest of table */ }; /* * Algorithm from "A Technique for High Performance Data Compression", * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19. * * Algorithm: * Modified Lempel-Ziv method (LZW). Basically finds common * substrings and replaces them with a variable size code. This is * deterministic, and can be done on the fly. Thus, the decompression * procedure needs no input table, but tracks the way the table was built. */ static u_char *compressbuf; static int compressbufsize; static int compressbufindex; static int getcode_offset; static int getcode_size; static int finchar; static int oldcode; /* compresses onto inbuf so inbuf needs to be large enough to * contain the worse case compression. fortunately the buffer * was large enough to compress the data in the first place */ uncompress(ibuf, ibufsize) u_char *ibuf; /* (compressed) input buffer */ int ibufsize; /* (compressed) input data size */ { u_char obuf[MAXPKTSIZE]; u_char de_stack[MAXPKTSIZE]; register u_char *stackp = de_stack; register int code; register int incode; register int dbytes_out; getcode_offset = 0; getcode_size = 0; compressbuf = ibuf; compressbufsize = ibufsize; compressbufindex = 0; dbytes_out = 0; code = oldcode = getcode(); while (code >= 256) { *stackp++ = tab_suffix[code]; code = tab_prefix[code]; } *stackp++ = finchar = tab_suffix[code]; do obuf[dbytes_out++] = *--stackp; while (stackp > de_stack); while ((code = getcode()) > -1) { if (code == CLEAR) { bzero((char *) tab_prefix, 256 * sizeof(tab_prefix[0])); clear_flg = 1; free_ent = FIRST - 1; if ((code = getcode()) == -1) break; } incode = code; /* * Special case for KwKwK string. */ if (code >= free_ent) { *stackp++ = finchar; code = oldcode; } /* * Generate output characters in reverse order */ while (code >= 256) { *stackp++ = tab_suffix[code]; code = tab_prefix[code]; } *stackp++ = finchar = tab_suffix[code]; /* * And put them out in forward order */ do { obuf[dbytes_out++] = *--stackp; } while (stackp > de_stack); /* * Generate the new entry. */ if ((code = free_ent) < maxmaxcode) { tab_prefix[code] = (u_short) oldcode; tab_suffix[code] = finchar; free_ent = code + 1; } /* * Remember previous code. */ oldcode = incode; } bcopy((char *) obuf, (char *) ibuf, dbytes_out); return(dbytes_out); } /* * Read one code from the compressed string. If EOF, return -1. * Inputs: * string * Outputs: * code or -1 is returned. */ int getcode() { static u_char buf[BITS]; register int code; register int r_off; register int bits; register u_char *bp = buf; if (clear_flg > 0 || getcode_offset >= getcode_size || free_ent > maxcode) { /* * If the next entry will be too big for the current code * size, then we must increase the size. This implies reading * a new buffer full, too. */ if (free_ent > maxcode) { n_bits++; if (n_bits == maxbits) maxcode = maxmaxcode; /* won't get any bigger now */ else maxcode = MAXCODE(n_bits); } if (clear_flg > 0) { maxcode = MAXCODE(n_bits = INIT_BITS); clear_flg = 0; } getcode_size = getcodes((char *) buf, n_bits); if (getcode_size <= 0) return -1; /* end of file */ getcode_offset = 0; /* Round size down to integral number of codes */ getcode_size = (getcode_size << 3) - (n_bits - 1); } r_off = getcode_offset; bits = n_bits; /* * Get to the first byte. */ bp += (r_off >> 3); r_off &= 7; /* Get first part (low order bits) */ code = (*bp++ >> r_off); bits -= (8 - r_off); r_off = 8 - r_off; /* now, offset into code word */ /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ if (bits >= 8) { code |= *bp++ << r_off; r_off += 8; bits -= 8; } /* high order bits. */ code |= (*bp & rmask[bits]) << r_off; getcode_offset += n_bits; return code; } getcodes(buf, n) register char *buf; register int n; { register int i; for (i = 0; i < n; i++) { if (compressbufindex >= compressbufsize) break; *buf++ = compressbuf[compressbufindex++]; } return i; }