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