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.
11 #include "lzw.h" /* just for consistency checking */
15 local unsigned decode (unsigned count, uch buffer[]);
16 local void decode_start (void);
19 local void huf_decode_start (void);
20 local unsigned decode_c (void);
21 local unsigned decode_p (void);
22 local void read_pt_len (int nn, int nbit, int i_special);
23 local void read_c_len (void);
26 local void fillbuf (int n);
27 local unsigned getbits (int n);
28 local void init_getbits (void);
32 local void make_table (int nchar, uch bitlen[],
33 int tablebits, ush table[]);
36 #define DICBIT 13 /* 12(-lh4-) or 13(-lh5-) */
37 #define DICSIZ ((unsigned) 1 << DICBIT)
44 # define UCHAR_MAX 255
47 #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
48 /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
49 * for which short is not on 16 bits (Cray).
52 /* encode.c and decode.c */
54 #define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */
55 #define THRESHOLD 3 /* choose optimal value */
59 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
60 /* alphabet = {0, 1, 2, ..., NC - 1} */
61 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
62 #define CODE_BIT 16 /* codeword length */
64 #define NP (DICBIT + 1)
65 #define NT (CODE_BIT + 3)
66 #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
67 #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
68 #define NPT (1 << TBIT)
70 /* local ush left[2 * NC - 1]; */
71 /* local ush right[2 * NC - 1]; */
74 #if NC > (1<<(BITS-2))
75 error cannot overlay left+right and prev
78 /* local uch c_len[NC]; */
81 error cannot overlay c_len and outbuf
84 local uch pt_len[NPT];
85 local unsigned blocksize;
86 local ush pt_table[256];
88 /* local ush c_table[4096]; */
90 #if (DIST_BUFSIZE-1) < 4095
91 error cannot overlay c_table and d_buf
94 /***********************************************************
96 ***********************************************************/
99 local unsigned subbitbuf;
102 local void fillbuf(n) /* Shift bitbuf n bits left, read n bits */
106 while (n > bitcount) {
107 bitbuf |= subbitbuf << (n -= bitcount);
108 subbitbuf = (unsigned)try_byte();
109 if ((int)subbitbuf == EOF) subbitbuf = 0;
112 bitbuf |= subbitbuf >> (bitcount -= n);
115 local unsigned getbits(n)
120 x = bitbuf >> (BITBUFSIZ - n); fillbuf(n);
124 local void init_getbits()
126 bitbuf = 0; subbitbuf = 0; bitcount = 0;
130 /***********************************************************
131 maketbl.c -- make table for decoding
132 ***********************************************************/
134 local void make_table(nchar, bitlen, tablebits, table)
140 ush count[17], weight[17], start[18], *p;
141 unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
143 for (i = 1; i <= 16; i++) count[i] = 0;
144 for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
147 for (i = 1; i <= 16; i++)
148 start[i + 1] = start[i] + (count[i] << (16 - i));
149 if ((start[17] & 0xffff) != 0)
150 gzip_error ("Bad table\n");
152 jutbits = 16 - tablebits;
153 for (i = 1; i <= (unsigned)tablebits; i++) {
154 start[i] >>= jutbits;
155 weight[i] = (unsigned) 1 << (tablebits - i);
158 weight[i] = (unsigned) 1 << (16 - i);
162 i = start[tablebits + 1] >> jutbits;
165 while (i != k) table[i++] = 0;
169 mask = (unsigned) 1 << (15 - tablebits);
170 for (ch = 0; ch < (unsigned)nchar; ch++) {
171 if ((len = bitlen[ch]) == 0) continue;
172 nextcode = start[len] + weight[len];
173 if (len <= (unsigned)tablebits) {
174 if ((unsigned) 1 << tablebits < nextcode)
175 gzip_error ("Bad table\n");
176 for (i = start[len]; i < nextcode; i++) table[i] = ch;
179 p = &table[k >> jutbits];
183 right[avail] = left[avail] = 0;
186 if (k & mask) p = &right[*p];
192 start[len] = nextcode;
196 /***********************************************************
197 huf.c -- static Huffman
198 ***********************************************************/
200 local void read_pt_len(nn, nbit, i_special)
211 for (i = 0; i < nn; i++) pt_len[i] = 0;
212 for (i = 0; i < 256; i++) pt_table[i] = c;
216 c = bitbuf >> (BITBUFSIZ - 3);
218 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
219 while (mask & bitbuf) { mask >>= 1; c++; }
221 gzip_error ("Bad table\n");
223 fillbuf((c < 7) ? 3 : c - 3);
225 if (i == i_special) {
227 while (--c >= 0) pt_len[i++] = 0;
230 while (i < nn) pt_len[i++] = 0;
231 make_table(nn, pt_len, 8, pt_table);
235 local void read_c_len()
243 for (i = 0; i < NC; i++) c_len[i] = 0;
244 for (i = 0; i < 4096; i++) c_table[i] = c;
248 c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
250 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
252 if (bitbuf & mask) c = right[c];
257 fillbuf((int) pt_len[c]);
260 else if (c == 1) c = getbits(4) + 3;
261 else c = getbits(CBIT) + 20;
262 while (--c >= 0) c_len[i++] = 0;
263 } else c_len[i++] = c - 2;
265 while (i < NC) c_len[i++] = 0;
266 make_table(NC, c_len, 12, c_table);
270 local unsigned decode_c()
274 if (blocksize == 0) {
275 blocksize = getbits(16);
276 if (blocksize == 0) {
277 return NC; /* end of file */
279 read_pt_len(NT, TBIT, 3);
281 read_pt_len(NP, PBIT, -1);
284 j = c_table[bitbuf >> (BITBUFSIZ - 12)];
286 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
288 if (bitbuf & mask) j = right[j];
293 fillbuf((int) c_len[j]);
297 local unsigned decode_p()
301 j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
303 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
305 if (bitbuf & mask) j = right[j];
310 fillbuf((int) pt_len[j]);
311 if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
315 local void huf_decode_start()
317 init_getbits(); blocksize = 0;
320 /***********************************************************
322 ***********************************************************/
324 local int j; /* remaining bytes to copy */
325 local int done; /* set at end of input */
327 local void decode_start()
334 /* Decode the input and return the number of decoded bytes put in buffer
336 local unsigned decode(count, buffer)
339 /* The calling function must keep the number of
340 bytes to be processed. This function decodes
341 either 'count' bytes or 'DICSIZ' bytes, whichever
342 is smaller, into the array 'buffer[]' of size
344 Call decode_start() once for each new file
345 before calling this function.
353 buffer[r] = buffer[i];
354 i = (i + 1) & (DICSIZ - 1);
355 if (++r == count) return r;
363 if (c <= UCHAR_MAX) {
365 if (++r == count) return r;
367 j = c - (UCHAR_MAX + 1 - THRESHOLD);
368 i = (r - decode_p() - 1) & (DICSIZ - 1);
370 buffer[r] = buffer[i];
371 i = (i + 1) & (DICSIZ - 1);
372 if (++r == count) return r;
379 /* ===========================================================================
380 * Unlzh in to out. Return OK or ERROR.
392 n = decode((unsigned) DICSIZ, window);
393 if (!test && n > 0) {
394 write_buf(out, (char*)window, n);