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.4 2006/11/20 08:40:34 eggert 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 */
72 #define NPT (1 << TBIT)
74 /* local ush left[2 * NC - 1]; */
75 /* local ush right[2 * NC - 1]; */
78 #if NC > (1<<(BITS-2))
79 error cannot overlay left+right and prev
82 /* local uch c_len[NC]; */
85 error cannot overlay c_len and outbuf
88 local uch pt_len[NPT];
89 local unsigned blocksize;
90 local ush pt_table[256];
92 /* local ush c_table[4096]; */
94 #if (DIST_BUFSIZE-1) < 4095
95 error cannot overlay c_table and d_buf
98 /***********************************************************
100 ***********************************************************/
103 local unsigned subbitbuf;
106 local void fillbuf(n) /* Shift bitbuf n bits left, read n bits */
110 while (n > bitcount) {
111 bitbuf |= subbitbuf << (n -= bitcount);
112 subbitbuf = (unsigned)try_byte();
113 if ((int)subbitbuf == EOF) subbitbuf = 0;
116 bitbuf |= subbitbuf >> (bitcount -= n);
119 local unsigned getbits(n)
124 x = bitbuf >> (BITBUFSIZ - n); fillbuf(n);
128 local void init_getbits()
130 bitbuf = 0; subbitbuf = 0; bitcount = 0;
134 /***********************************************************
135 maketbl.c -- make table for decoding
136 ***********************************************************/
138 local void make_table(nchar, bitlen, tablebits, table)
144 ush count[17], weight[17], start[18], *p;
145 unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
147 for (i = 1; i <= 16; i++) count[i] = 0;
148 for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
151 for (i = 1; i <= 16; i++)
152 start[i + 1] = start[i] + (count[i] << (16 - i));
153 if ((start[17] & 0xffff) != 0)
154 gzip_error ("Bad table\n");
156 jutbits = 16 - tablebits;
157 for (i = 1; i <= (unsigned)tablebits; i++) {
158 start[i] >>= jutbits;
159 weight[i] = (unsigned) 1 << (tablebits - i);
162 weight[i] = (unsigned) 1 << (16 - i);
166 i = start[tablebits + 1] >> jutbits;
169 while (i != k) table[i++] = 0;
173 mask = (unsigned) 1 << (15 - tablebits);
174 for (ch = 0; ch < (unsigned)nchar; ch++) {
175 if ((len = bitlen[ch]) == 0) continue;
176 nextcode = start[len] + weight[len];
177 if (len <= (unsigned)tablebits) {
178 if ((unsigned) 1 << tablebits < nextcode)
179 gzip_error ("Bad table\n");
180 for (i = start[len]; i < nextcode; i++) table[i] = ch;
183 p = &table[k >> jutbits];
187 right[avail] = left[avail] = 0;
190 if (k & mask) p = &right[*p];
196 start[len] = nextcode;
200 /***********************************************************
201 huf.c -- static Huffman
202 ***********************************************************/
204 local void read_pt_len(nn, nbit, i_special)
215 for (i = 0; i < nn; i++) pt_len[i] = 0;
216 for (i = 0; i < 256; i++) pt_table[i] = c;
220 c = bitbuf >> (BITBUFSIZ - 3);
222 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
223 while (mask & bitbuf) { mask >>= 1; c++; }
225 gzip_error ("Bad table\n");
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);