[unix-history] / gnu / usr.bin / gzip / unlzh.c

/* 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 RCSID
static 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
#endif

local 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;
}
Commit	Line	Data
caed0dfe NW	1	/* unlzh.c -- decompress files in SCO compress -H (LZH) format.
	2	* The code in this file is directly derived from the public domain 'ar002'
	3	* written by Haruhiko Okumura.
	4	*/
	5
e32dd11d NW	6	#ifdef RCSID
	7	static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
	8	#endif
	9
caed0dfe NW	10	#include <stdio.h>
	11
	12	#include "tailor.h"
	13	#include "gzip.h"
	14	#include "lzw.h" /* just for consistency checking */
	15
	16	/* decode.c */
	17
	18	local unsigned decode OF((unsigned count, uch buffer[]));
	19	local void decode_start OF((void));
	20
	21	/* huf.c */
	22	local void huf_decode_start OF((void));
	23	local unsigned decode_c OF((void));
	24	local unsigned decode_p OF((void));
e32dd11d NW	25	local void read_pt_len OF((int nn, int nbit, int i_special));
e32dd11d NW	26	local void read_c_len OF((void));
caed0dfe NW	27
	28	/* io.c */
	29	local void fillbuf OF((int n));
	30	local unsigned getbits OF((int n));
	31	local void init_getbits OF((void));
	32
e32dd11d NW	33	/* maketbl.c */
	34
	35	local void make_table OF((int nchar, uch bitlen[],
	36	int tablebits, ush table[]));
	37
	38
caed0dfe NW	39	#define DICBIT 13 /* 12(-lh4-) or 13(-lh5-) */
	40	#define DICSIZ ((unsigned) 1 << DICBIT)
	41
	42	#ifndef CHAR_BIT
	43	# define CHAR_BIT 8
	44	#endif
	45
	46	#ifndef UCHAR_MAX
	47	# define UCHAR_MAX 255
	48	#endif
	49
	50	#define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
	51	/* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
	52	* for which short is not on 16 bits (Cray).
	53	*/
	54
	55	/* encode.c and decode.c */
	56
	57	#define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */
	58	#define THRESHOLD 3 /* choose optimal value */
	59
	60	/* huf.c */
	61
	62	#define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
	63	/* alphabet = {0, 1, 2, ..., NC - 1} */
	64	#define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
	65	#define CODE_BIT 16 /* codeword length */
	66
	67	#define NP (DICBIT + 1)
	68	#define NT (CODE_BIT + 3)
	69	#define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
	70	#define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
	71	#if NT > NP
	72	# define NPT NT
	73	#else
	74	# define NPT NP
	75	#endif
	76
	77	/* local ush left[2 * NC - 1]; */
	78	/* local ush right[2 * NC - 1]; */
	79	#define left prev
	80	#define right head
e32dd11d	81	#if NC > (1<<(BITS-2))
caed0dfe NW	82	error cannot overlay left+right and prev
	83	#endif
	84
	85	/* local uch c_len[NC]; */
	86	#define c_len outbuf
	87	#if NC > OUTBUFSIZ
	88	error cannot overlay c_len and outbuf
	89	#endif
	90
	91	local uch pt_len[NPT];
	92	local unsigned blocksize;
	93	local ush pt_table[256];
	94
	95	/* local ush c_table[4096]; */
	96	#define c_table d_buf
e32dd11d	97	#if (DIST_BUFSIZE-1) < 4095
caed0dfe NW	98	error cannot overlay c_table and d_buf
	99	#endif
	100
e32dd11d NW	101	/***********************************************************
	102	io.c -- input/output
	103	***********************************************************/
	104
caed0dfe NW	105	local ush bitbuf;
	106	local unsigned subbitbuf;
	107	local int bitcount;
	108
	109	local void fillbuf(n) /* Shift bitbuf n bits left, read n bits */
	110	int n;
	111	{
	112	bitbuf <<= n;
	113	while (n > bitcount) {
	114	bitbuf \|= subbitbuf << (n -= bitcount);
	115	subbitbuf = (unsigned)try_byte();
	116	if ((int)subbitbuf == EOF) subbitbuf = 0;
	117	bitcount = CHAR_BIT;
	118	}
	119	bitbuf \|= subbitbuf >> (bitcount -= n);
	120	}
	121
	122	local unsigned getbits(n)
	123	int n;
	124	{
	125	unsigned x;
	126
	127	x = bitbuf >> (BITBUFSIZ - n); fillbuf(n);
	128	return x;
	129	}
	130
	131	local void init_getbits()
	132	{
	133	bitbuf = 0; subbitbuf = 0; bitcount = 0;
	134	fillbuf(BITBUFSIZ);
	135	}
	136
	137	/***********************************************************
	138	maketbl.c -- make table for decoding
	139	***********************************************************/
	140
	141	local void make_table(nchar, bitlen, tablebits, table)
	142	int nchar;
	143	uch bitlen[];
	144	int tablebits;
	145	ush table[];
	146	{
	147	ush count[17], weight[17], start[18], *p;
	148	unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
	149
	150	for (i = 1; i <= 16; i++) count[i] = 0;
e32dd11d	151	for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
caed0dfe NW	152
	153	start[1] = 0;
	154	for (i = 1; i <= 16; i++)
	155	start[i + 1] = start[i] + (count[i] << (16 - i));
e32dd11d	156	if ((start[17] & 0xffff) != 0)
caed0dfe NW	157	error("Bad table\n");
	158
	159	jutbits = 16 - tablebits;
e32dd11d	160	for (i = 1; i <= (unsigned)tablebits; i++) {
caed0dfe NW	161	start[i] >>= jutbits;
	162	weight[i] = (unsigned) 1 << (tablebits - i);
	163	}
	164	while (i <= 16) {
	165	weight[i] = (unsigned) 1 << (16 - i);
	166	i++;
	167	}
	168
	169	i = start[tablebits + 1] >> jutbits;
e32dd11d	170	if (i != 0) {
caed0dfe NW	171	k = 1 << tablebits;
	172	while (i != k) table[i++] = 0;
	173	}
	174
	175	avail = nchar;
	176	mask = (unsigned) 1 << (15 - tablebits);
e32dd11d	177	for (ch = 0; ch < (unsigned)nchar; ch++) {
caed0dfe NW	178	if ((len = bitlen[ch]) == 0) continue;
caed0dfe NW	179	nextcode = start[len] + weight[len];
e32dd11d	180	if (len <= (unsigned)tablebits) {
caed0dfe NW	181	for (i = start[len]; i < nextcode; i++) table[i] = ch;
	182	} else {
	183	k = start[len];
	184	p = &table[k >> jutbits];
	185	i = len - tablebits;
	186	while (i != 0) {
	187	if (*p == 0) {
	188	right[avail] = left[avail] = 0;
	189	*p = avail++;
	190	}
	191	if (k & mask) p = &right[*p];
	192	else p = &left[*p];
	193	k <<= 1; i--;
	194	}
	195	*p = ch;
	196	}
	197	start[len] = nextcode;
	198	}
	199	}
	200
	201	/***********************************************************
	202	huf.c -- static Huffman
	203	***********************************************************/
	204
	205	local void read_pt_len(nn, nbit, i_special)
	206	int nn;
	207	int nbit;
	208	int i_special;
	209	{
	210	int i, c, n;
	211	unsigned mask;
	212
	213	n = getbits(nbit);
	214	if (n == 0) {
	215	c = getbits(nbit);
	216	for (i = 0; i < nn; i++) pt_len[i] = 0;
	217	for (i = 0; i < 256; i++) pt_table[i] = c;
	218	} else {
	219	i = 0;
	220	while (i < n) {
	221	c = bitbuf >> (BITBUFSIZ - 3);
	222	if (c == 7) {
	223	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
	224	while (mask & bitbuf) { mask >>= 1; c++; }
	225	}
	226	fillbuf((c < 7) ? 3 : c - 3);
	227	pt_len[i++] = c;
	228	if (i == i_special) {
	229	c = getbits(2);
	230	while (--c >= 0) pt_len[i++] = 0;
	231	}
	232	}
	233	while (i < nn) pt_len[i++] = 0;
	234	make_table(nn, pt_len, 8, pt_table);
	235	}
	236	}
	237
	238	local void read_c_len()
	239	{
	240	int i, c, n;
	241	unsigned mask;
	242
	243	n = getbits(CBIT);
	244	if (n == 0) {
245	c = getbits(CBIT);
246	for (i = 0; i < NC; i++) c_len[i] = 0;
247	for (i = 0; i < 4096; i++) c_table[i] = c;
248	} else {
249	i = 0;
250	while (i < n) {
251	c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
252	if (c >= NT) {
253	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
254	do {
255	if (bitbuf & mask) c = right[c];
256	else c = left [c];
257	mask >>= 1;
258	} while (c >= NT);
259	}
260	fillbuf((int) pt_len[c]);
261	if (c <= 2) {
262	if (c == 0) c = 1;
263	else if (c == 1) c = getbits(4) + 3;
264	else c = getbits(CBIT) + 20;
265	while (--c >= 0) c_len[i++] = 0;
266	} else c_len[i++] = c - 2;
267	}
268	while (i < NC) c_len[i++] = 0;
269	make_table(NC, c_len, 12, c_table);
270	}
271	}
272
273	local unsigned decode_c()
274	{
275	unsigned j, mask;
276
277	if (blocksize == 0) {
278	blocksize = getbits(16);
279	if (blocksize == 0) {
280	return NC; /* end of file */
281	}
282	read_pt_len(NT, TBIT, 3);
283	read_c_len();
284	read_pt_len(NP, PBIT, -1);
285	}
286	blocksize--;
287	j = c_table[bitbuf >> (BITBUFSIZ - 12)];
288	if (j >= NC) {
289	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
290	do {
291	if (bitbuf & mask) j = right[j];
292	else j = left [j];
293	mask >>= 1;
294	} while (j >= NC);
295	}
296	fillbuf((int) c_len[j]);
297	return j;
298	}
299
300	local unsigned decode_p()
301	{
302	unsigned j, mask;
303
304	j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
305	if (j >= NP) {
306	mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
307	do {
308	if (bitbuf & mask) j = right[j];
309	else j = left [j];
310	mask >>= 1;
311	} while (j >= NP);
312	}
313	fillbuf((int) pt_len[j]);
314	if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
315	return j;
316	}
317
318	local void huf_decode_start()
319	{
320	init_getbits(); blocksize = 0;
321	}
322
323	/***********************************************************
324	decode.c
325	***********************************************************/
326
327	local int j; /* remaining bytes to copy */
328	local int done; /* set at end of input */
329
330	local void decode_start()
331	{
332	huf_decode_start();
333	j = 0;
334	done = 0;
335	}
336
337	/* Decode the input and return the number of decoded bytes put in buffer
338	*/
339	local unsigned decode(count, buffer)
340	unsigned count;
341	uch buffer[];
342	/* The calling function must keep the number of
343	bytes to be processed. This function decodes
344	either 'count' bytes or 'DICSIZ' bytes, whichever
345	is smaller, into the array 'buffer[]' of size
346	'DICSIZ' or more.
347	Call decode_start() once for each new file
348	before calling this function.
349	*/
350	{
351	local unsigned i;
352	unsigned r, c;
353
354	r = 0;
355	while (--j >= 0) {
356	buffer[r] = buffer[i];
357	i = (i + 1) & (DICSIZ - 1);
358	if (++r == count) return r;
359	}
360	for ( ; ; ) {
361	c = decode_c();
362	if (c == NC) {
363	done = 1;
364	return r;
365	}
366	if (c <= UCHAR_MAX) {
367	buffer[r] = c;
368	if (++r == count) return r;
369	} else {
370	j = c - (UCHAR_MAX + 1 - THRESHOLD);
371	i = (r - decode_p() - 1) & (DICSIZ - 1);
372	while (--j >= 0) {
373	buffer[r] = buffer[i];
374	i = (i + 1) & (DICSIZ - 1);
375	if (++r == count) return r;
376	}
377	}
378	}
379	}
380
381
382	/* ===========================================================================
383	* Unlzh in to out. Return OK or ERROR.
384	*/
385	int unlzh(in, out)
386	int in;
387	int out;
388	{
389	unsigned n;
390	ifd = in;
391	ofd = out;
392
393	decode_start();
394	while (!done) {
395	n = decode((unsigned) DICSIZ, window);
396	if (!test && n > 0) {
397	write_buf(out, (char*)window, n);
398	}
399	}
400	return OK;
401	}