/* unlzh.c -- decompress files in SCO compress -H (LZH) format. * The code in this file is directly derived from the public domain 'ar002' * written by Haruhiko Okumura. */#ifdef RCSIDstatic char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";#endif#include <stdio.h>#include "tailor.h"#include "gzip.h"#include "lzw.h" /* just for consistency checking *//* decode.c */local unsigned  decode  OF((unsigned count, uch buffer[]));local void decode_start OF((void));/* huf.c */local void huf_decode_start OF((void));local unsigned decode_c     OF((void));local unsigned decode_p     OF((void));local void read_pt_len      OF((int nn, int nbit, int i_special));local void read_c_len       OF((void));/* io.c */local void fillbuf      OF((int n));local unsigned getbits  OF((int n));local void init_getbits OF((void));/* maketbl.c */local void make_table OF((int nchar, uch bitlen[],			  int tablebits, ush table[]));#define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */#define DICSIZ ((unsigned) 1 << DICBIT)#ifndef CHAR_BIT#  define CHAR_BIT 8#endif#ifndef UCHAR_MAX#  define UCHAR_MAX 255#endif#define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))/* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines * for which short is not on 16 bits (Cray). *//* encode.c and decode.c */#define MAXMATCH 256    /* formerly F (not more than UCHAR_MAX + 1) */#define THRESHOLD  3    /* choose optimal value *//* huf.c */#define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)	/* alphabet = {0, 1, 2, ..., NC - 1} */#define CBIT 9  /* $\lfloor \log_2 NC \rfloor + 1$ */#define CODE_BIT  16  /* codeword length */#define NP (DICBIT + 1)#define NT (CODE_BIT + 3)#define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */#define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */#if NT > NP# define NPT NT#else# define NPT NP#endif/* local ush left[2 * NC - 1]; *//* local ush right[2 * NC - 1]; */#define left  prev#define right head#if NC > (1<<(BITS-2))    error cannot overlay left+right and prev#endif/* local uch c_len[NC]; */#define c_len outbuf#if NC > OUTBUFSIZ    error cannot overlay c_len and outbuf#endiflocal uch pt_len[NPT];local unsigned blocksize;local ush pt_table[256];/* local ush c_table[4096]; */#define c_table d_buf#if (DIST_BUFSIZE-1) < 4095    error cannot overlay c_table and d_buf#endif/***********************************************************        io.c -- input/output***********************************************************/local ush       bitbuf;local unsigned  subbitbuf;local int       bitcount;local void fillbuf(n)  /* Shift bitbuf n bits left, read n bits */    int n;{    bitbuf <<= n;    while (n > bitcount) {	bitbuf |= subbitbuf << (n -= bitcount);	subbitbuf = (unsigned)try_byte();	if ((int)subbitbuf == EOF) subbitbuf = 0;	bitcount = CHAR_BIT;    }    bitbuf |= subbitbuf >> (bitcount -= n);}local unsigned getbits(n)    int n;{    unsigned x;    x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);    return x;}local void init_getbits(){    bitbuf = 0;  subbitbuf = 0;  bitcount = 0;    fillbuf(BITBUFSIZ);}/***********************************************************	maketbl.c -- make table for decoding***********************************************************/local void make_table(nchar, bitlen, tablebits, table)    int nchar;    uch bitlen[];    int tablebits;    ush table[];{    ush count[17], weight[17], start[18], *p;    unsigned i, k, len, ch, jutbits, avail, nextcode, mask;    for (i = 1; i <= 16; i++) count[i] = 0;    for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;    start[1] = 0;    for (i = 1; i <= 16; i++)	start[i + 1] = start[i] + (count[i] << (16 - i));    if ((start[17] & 0xffff) != 0)	error("Bad table\n");    jutbits = 16 - tablebits;    for (i = 1; i <= (unsigned)tablebits; i++) {	start[i] >>= jutbits;	weight[i] = (unsigned) 1 << (tablebits - i);    }    while (i <= 16) {	weight[i] = (unsigned) 1 << (16 - i);	i++;    }    i = start[tablebits + 1] >> jutbits;    if (i != 0) {	k = 1 << tablebits;	while (i != k) table[i++] = 0;    }    avail = nchar;    mask = (unsigned) 1 << (15 - tablebits);    for (ch = 0; ch < (unsigned)nchar; ch++) {	if ((len = bitlen[ch]) == 0) continue;	nextcode = start[len] + weight[len];	if (len <= (unsigned)tablebits) {	    for (i = start[len]; i < nextcode; i++) table[i] = ch;	} else {	    k = start[len];	    p = &table[k >> jutbits];	    i = len - tablebits;	    while (i != 0) {		if (*p == 0) {		    right[avail] = left[avail] = 0;		    *p = avail++;		}		if (k & mask) p = &right[*p];		else          p = &left[*p];		k <<= 1;  i--;	    }	    *p = ch;	}	start[len] = nextcode;    }}/***********************************************************        huf.c -- static Huffman***********************************************************/local void read_pt_len(nn, nbit, i_special)    int nn;    int nbit;    int i_special;{    int i, c, n;    unsigned mask;    n = getbits(nbit);    if (n == 0) {	c = getbits(nbit);	for (i = 0; i < nn; i++) pt_len[i] = 0;	for (i = 0; i < 256; i++) pt_table[i] = c;    } else {	i = 0;	while (i < n) {	    c = bitbuf >> (BITBUFSIZ - 3);	    if (c == 7) {		mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);		while (mask & bitbuf) {  mask >>= 1;  c++;  }	    }	    fillbuf((c < 7) ? 3 : c - 3);	    pt_len[i++] = c;	    if (i == i_special) {		c = getbits(2);		while (--c >= 0) pt_len[i++] = 0;	    }	}	while (i < nn) pt_len[i++] = 0;	make_table(nn, pt_len, 8, pt_table);    }}local void read_c_len(){    int i, c, n;    unsigned mask;    n = getbits(CBIT);    if (n == 0) {	c = getbits(CBIT);	for (i = 0; i < NC; i++) c_len[i] = 0;	for (i = 0; i < 4096; i++) c_table[i] = c;    } else {	i = 0;	while (i < n) {	    c = pt_table[bitbuf >> (BITBUFSIZ - 8)];	    if (c >= NT) {		mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);		do {		    if (bitbuf & mask) c = right[c];		    else               c = left [c];		    mask >>= 1;		} while (c >= NT);	    }	    fillbuf((int) pt_len[c]);	    if (c <= 2) {		if      (c == 0) c = 1;		else if (c == 1) c = getbits(4) + 3;		else             c = getbits(CBIT) + 20;		while (--c >= 0) c_len[i++] = 0;	    } else c_len[i++] = c - 2;	}	while (i < NC) c_len[i++] = 0;	make_table(NC, c_len, 12, c_table);    }}local unsigned decode_c(){    unsigned j, mask;    if (blocksize == 0) {	blocksize = getbits(16);	if (blocksize == 0) {	    return NC; /* end of file */	}	read_pt_len(NT, TBIT, 3);	read_c_len();	read_pt_len(NP, PBIT, -1);    }    blocksize--;    j = c_table[bitbuf >> (BITBUFSIZ - 12)];    if (j >= NC) {	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);	do {	    if (bitbuf & mask) j = right[j];	    else               j = left [j];	    mask >>= 1;	} while (j >= NC);    }    fillbuf((int) c_len[j]);    return j;}local unsigned decode_p(){    unsigned j, mask;    j = pt_table[bitbuf >> (BITBUFSIZ - 8)];    if (j >= NP) {	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);	do {	    if (bitbuf & mask) j = right[j];	    else               j = left [j];	    mask >>= 1;	} while (j >= NP);    }    fillbuf((int) pt_len[j]);    if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));    return j;}local void huf_decode_start(){    init_getbits();  blocksize = 0;}/***********************************************************        decode.c***********************************************************/local int j;    /* remaining bytes to copy */local int done; /* set at end of input */local void decode_start(){    huf_decode_start();    j = 0;    done = 0;}/* Decode the input and return the number of decoded bytes put in buffer */local unsigned decode(count, buffer)    unsigned count;    uch buffer[];    /* The calling function must keep the number of       bytes to be processed.  This function decodes       either 'count' bytes or 'DICSIZ' bytes, whichever       is smaller, into the array 'buffer[]' of size       'DICSIZ' or more.       Call decode_start() once for each new file       before calling this function.     */{    local unsigned i;    unsigned r, c;    r = 0;    while (--j >= 0) {	buffer[r] = buffer[i];	i = (i + 1) & (DICSIZ - 1);	if (++r == count) return r;    }    for ( ; ; ) {	c = decode_c();	if (c == NC) {	    done = 1;	    return r;	}	if (c <= UCHAR_MAX) {	    buffer[r] = c;	    if (++r == count) return r;	} else {	    j = c - (UCHAR_MAX + 1 - THRESHOLD);	    i = (r - decode_p() - 1) & (DICSIZ - 1);	    while (--j >= 0) {		buffer[r] = buffer[i];		i = (i + 1) & (DICSIZ - 1);		if (++r == count) return r;	    }	}    }}/* =========================================================================== * Unlzh in to out. Return OK or ERROR. */int unlzh(in, out)    int in;    int out;{    unsigned n;    ifd = in;    ofd = out;    decode_start();    while (!done) {	n = decode((unsigned) DICSIZ, window);	if (!test && n > 0) {	    write_buf(out, (char*)window, n);	}    }    return OK;}