source: vendor/gzip/1.3.11/unlzh.c@ 3408

Last change on this file since 3408 was 3325, checked in by bird, 18 years ago

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