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.
7 static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
15 #include "lzw.h" /* just for consistency checking */
19 local unsigned decode OF((unsigned count, uch buffer[]));
20 local void decode_start OF((void));
23 local void huf_decode_start OF((void));
24 local unsigned decode_c OF((void));
25 local unsigned decode_p OF((void));
26 local void read_pt_len OF((int nn, int nbit, int i_special));
27 local void read_c_len OF((void));
30 local void fillbuf OF((int n));
31 local unsigned getbits OF((int n));
32 local void init_getbits OF((void));
36 local void make_table OF((int nchar, uch bitlen[],
37 int tablebits, ush table[]));
40 #define DICBIT 13 /* 12(-lh4-) or 13(-lh5-) */
41 #define DICSIZ ((unsigned) 1 << DICBIT)
48 # define UCHAR_MAX 255
51 #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
52 /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
53 * for which short is not on 16 bits (Cray).
56 /* encode.c and decode.c */
58 #define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */
59 #define THRESHOLD 3 /* choose optimal value */
63 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
64 /* alphabet = {0, 1, 2, ..., NC - 1} */
65 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
66 #define CODE_BIT 16 /* codeword length */
68 #define NP (DICBIT + 1)
69 #define NT (CODE_BIT + 3)
70 #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
71 #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
78 /* local ush left[2 * NC - 1]; */
79 /* local ush right[2 * NC - 1]; */
82 #if NC > (1<<(BITS-2))
83 error cannot overlay left+right and prev
86 /* local uch c_len[NC]; */
89 error cannot overlay c_len and outbuf
92 local uch pt_len[NPT];
93 local unsigned blocksize;
94 local ush pt_table[256];
96 /* local ush c_table[4096]; */
98 #if (DIST_BUFSIZE-1) < 4095
99 error cannot overlay c_table and d_buf
102 /***********************************************************
104 ***********************************************************/
107 local unsigned subbitbuf;
110 local void fillbuf(n) /* Shift bitbuf n bits left, read n bits */
114 while (n > bitcount) {
115 bitbuf |= subbitbuf << (n -= bitcount);
116 subbitbuf = (unsigned)try_byte();
117 if ((int)subbitbuf == EOF) subbitbuf = 0;
120 bitbuf |= subbitbuf >> (bitcount -= n);
123 local unsigned getbits(n)
128 x = bitbuf >> (BITBUFSIZ - n); fillbuf(n);
132 local void init_getbits()
134 bitbuf = 0; subbitbuf = 0; bitcount = 0;
138 /***********************************************************
139 maketbl.c -- make table for decoding
140 ***********************************************************/
142 local void make_table(nchar, bitlen, tablebits, table)
148 ush count[17], weight[17], start[18], *p;
149 unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
151 for (i = 1; i <= 16; i++) count[i] = 0;
152 for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
155 for (i = 1; i <= 16; i++)
156 start[i + 1] = start[i] + (count[i] << (16 - i));
157 if ((start[17] & 0xffff) != 0)
158 error("Bad table\n");
160 jutbits = 16 - tablebits;
161 for (i = 1; i <= (unsigned)tablebits; i++) {
162 start[i] >>= jutbits;
163 weight[i] = (unsigned) 1 << (tablebits - i);
166 weight[i] = (unsigned) 1 << (16 - i);
170 i = start[tablebits + 1] >> jutbits;
173 while (i != k) table[i++] = 0;
177 mask = (unsigned) 1 << (15 - tablebits);
178 for (ch = 0; ch < (unsigned)nchar; ch++) {
179 if ((len = bitlen[ch]) == 0) continue;
180 nextcode = start[len] + weight[len];
181 if (len <= (unsigned)tablebits) {
182 for (i = start[len]; i < nextcode; i++) table[i] = ch;
185 p = &table[k >> jutbits];
189 right[avail] = left[avail] = 0;
192 if (k & mask) p = &right[*p];
198 start[len] = nextcode;
202 /***********************************************************
203 huf.c -- static Huffman
204 ***********************************************************/
206 local void read_pt_len(nn, nbit, i_special)
217 for (i = 0; i < nn; i++) pt_len[i] = 0;
218 for (i = 0; i < 256; i++) pt_table[i] = c;
222 c = bitbuf >> (BITBUFSIZ - 3);
224 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
225 while (mask & bitbuf) { mask >>= 1; c++; }
227 fillbuf((c < 7) ? 3 : c - 3);
229 if (i == i_special) {
231 while (--c >= 0) pt_len[i++] = 0;
234 while (i < nn) pt_len[i++] = 0;
235 make_table(nn, pt_len, 8, pt_table);
239 local void read_c_len()
247 for (i = 0; i < NC; i++) c_len[i] = 0;
248 for (i = 0; i < 4096; i++) c_table[i] = c;
252 c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
254 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
256 if (bitbuf & mask) c = right[c];
261 fillbuf((int) pt_len[c]);
264 else if (c == 1) c = getbits(4) + 3;
265 else c = getbits(CBIT) + 20;
266 while (--c >= 0) c_len[i++] = 0;
267 } else c_len[i++] = c - 2;
269 while (i < NC) c_len[i++] = 0;
270 make_table(NC, c_len, 12, c_table);
274 local unsigned decode_c()
278 if (blocksize == 0) {
279 blocksize = getbits(16);
280 if (blocksize == 0) {
281 return NC; /* end of file */
283 read_pt_len(NT, TBIT, 3);
285 read_pt_len(NP, PBIT, -1);
288 j = c_table[bitbuf >> (BITBUFSIZ - 12)];
290 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
292 if (bitbuf & mask) j = right[j];
297 fillbuf((int) c_len[j]);
301 local unsigned decode_p()
305 j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
307 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
309 if (bitbuf & mask) j = right[j];
314 fillbuf((int) pt_len[j]);
315 if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
319 local void huf_decode_start()
321 init_getbits(); blocksize = 0;
324 /***********************************************************
326 ***********************************************************/
328 local int j; /* remaining bytes to copy */
329 local int done; /* set at end of input */
331 local void decode_start()
338 /* Decode the input and return the number of decoded bytes put in buffer
340 local unsigned decode(count, buffer)
343 /* The calling function must keep the number of
344 bytes to be processed. This function decodes
345 either 'count' bytes or 'DICSIZ' bytes, whichever
346 is smaller, into the array 'buffer[]' of size
348 Call decode_start() once for each new file
349 before calling this function.
357 buffer[r] = buffer[i];
358 i = (i + 1) & (DICSIZ - 1);
359 if (++r == count) return r;
367 if (c <= UCHAR_MAX) {
369 if (++r == count) return r;
371 j = c - (UCHAR_MAX + 1 - THRESHOLD);
372 i = (r - decode_p() - 1) & (DICSIZ - 1);
374 buffer[r] = buffer[i];
375 i = (i + 1) & (DICSIZ - 1);
376 if (++r == count) return r;
383 /* ===========================================================================
384 * Unlzh in to out. Return OK or ERROR.
396 n = decode((unsigned) DICSIZ, window);
397 if (!test && n > 0) {
398 write_buf(out, (char*)window, n);