/* 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 */#include "bsdebug.h"//#define _DEBUG_UNLZH_C_#ifdef DBGPrintfi#undef DBGPrintfi#endif#ifdef DBGPrintfo#undef DBGPrintfo#endif#if defined(_TRACEHELPER_DEBUG_ALL_)  #define DBGPrintfi(a) DbgPrintfi a;  #define DBGPrintfo(a) DbgPrintfo a;#elif defined(_DEBUG_UNLZH_C_) && defined(_TRACEHELPER_DEBUG_EACH_OF_FILE_)  #define DBGPrintfi(a) DbgPrintfi a;  #define DBGPrintfo(a) DbgPrintfo a;#else  #define DBGPrintfi(a)  #define DBGPrintfo(a)#endif/* 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 int read_pt_len      OF((int nn, int nbit, int i_special));local int 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 int 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;{  DBGPrintfi(("fillbuf(In)\r\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);  }  DBGPrintfo(("fillbuf(out)\r\n"));}local unsigned getbits(n)    int n;{  DBGPrintfi(("getbits(In)\r\n"));  {    unsigned x;    x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);        DBGPrintfo(("getbits(out1)\r\n"));    return  x;  }}local void init_getbits(){  DBGPrintfi(("init_getbits(In)\r\n"));  {    bitbuf = 0;  subbitbuf = 0;  bitcount = 0;    fillbuf(BITBUFSIZ);  }  DBGPrintfo(("init_getbits(out)\r\n"));}/***********************************************************	maketbl.c -- make table for decoding***********************************************************/local int make_table(nchar, bitlen, tablebits, table)    int nchar;    uch bitlen[];    int tablebits;    ush table[];{  DBGPrintfi(("make_table(In)\r\n"));  {    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");		DBGPrintfo(("make_table(out1)\r\n"));		return -1;	}    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;    }  }  DBGPrintfo(("make_table(out)\r\n"));  return 0;}/***********************************************************        huf.c -- static Huffman***********************************************************/local int read_pt_len(nn, nbit, i_special)    int nn;    int nbit;    int i_special;{  DBGPrintfi(("read_pt_len(In)\r\n"));  {    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;	if ( make_table(nn, pt_len, 8, pt_table) < 0 )	{		DBGPrintfo(("read_pt_len(out1)\r\n"));		return -1;	}    }  }  DBGPrintfo(("read_pt_len(out)\r\n"));  return 0;}local int read_c_len(){  DBGPrintfi(("read_c_len(In)\r\n"));  {    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;	if ( make_table(NC, c_len, 12, c_table) < 0 )	{		DBGPrintfo(("read_c_len(out1)\r\n"));		return -1;	}    }  }  DBGPrintfo(("read_c_len(out)\r\n"));  return 0;}local unsigned decode_c(){  DBGPrintfi(("decode_c(In)\r\n"));  {    unsigned j, mask;    if (blocksize == 0) {	blocksize = getbits(16);	if (blocksize == 0) {	    DBGPrintfo(("decode_c(out1)\r\n"));    	return  NC; /* end of file */	}	if ( read_pt_len(NT, TBIT, 3) < 0 )	{		DBGPrintfo(("decode_c(out11)\r\n"));		return -1;	}	read_c_len();	if ( read_pt_len(NP, PBIT, -1) < 0)	{		DBGPrintfo(("decode_c(out11)\r\n"));		return -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]);        DBGPrintfo(("decode_c(out2)\r\n"));    return  j;  }}local unsigned decode_p(){  DBGPrintfi(("decode_p(In)\r\n"));  {    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));        DBGPrintfo(("decode_p(out1)\r\n"));    return  j;  }}local void huf_decode_start(){  DBGPrintfi(("huf_decode_start(In)\r\n"));  {    init_getbits();  blocksize = 0;  }  DBGPrintfo(("huf_decode_start(out)\r\n"));}/***********************************************************        decode.c***********************************************************/local int j;    /* remaining bytes to copy */local int done; /* set at end of input */local void decode_start(){  DBGPrintfi(("decode_start(In)\r\n"));  {    huf_decode_start();    j = 0;    done = 0;  }  DBGPrintfo(("decode_start(out)\r\n"));}/* 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.     */{  DBGPrintfi(("decode(In)\r\n"));  {    local unsigned i;    unsigned r, c;    r = 0;    while (--j >= 0) {	buffer[r] = buffer[i];	i = (i + 1) & (DICSIZ - 1);	if (++r == count) {                   	 DBGPrintfo(("decode(out1)\r\n"));                  	 return  r;                   	}    }    for ( ; ; ) {	c = decode_c();	if ( c == -1)	{		DBGPrintfo(("decode(out20)\r\n"));		return -1;	}	if (c == NC) {	    done = 1;	        	DBGPrintfo(("decode(out2)\r\n"));    	return  r;	}	if (c <= UCHAR_MAX) {	    buffer[r] = c;	    if (++r == count) {                       	 DBGPrintfo(("decode(out3)\r\n"));                      	 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) {                   		 DBGPrintfo(("decode(out4)\r\n"));                  		 return  r;                   		}	    }	}    }  }}/* =========================================================================== * Unlzh in to out. Return OK or ERROR. */int unlzh(in, out)    int in;    int out;{  DBGPrintfi(("unlzh(In)\r\n"));  {    unsigned n;    ifd = in;    ofd = out;    decode_start();    while (!done) {	n = decode((unsigned) DICSIZ, window);	if ( n == -1 )	{		DBGPrintfo(("unlzh(out10)\r\n"));		return -1;	}	if (!test && n > 0) {	    write_buf(out, (char*)window, n);	}    }    DBGPrintfo(("unlzh(out1)\r\n"));    return  OK;  }}