Obsolete; not reference by anything.
[people/dverkamp/gpxe.git] / src / util / lzhuf.c
1 /*
2 ----------------------------------------------------------------------------
3
4 M. LZHuf Compression
5
6 This is the LZHuf compression algorithm as used in DPBOX and F6FBB.
7
8 ----------------------------------------------------------------------------
9 */
10 /**************************************************************
11     lzhuf.c
12     written by Haruyasu Yoshizaki 11/20/1988
13     some minor changes 4/6/1989
14     comments translated by Haruhiko Okumura 4/7/1989
15
16     minor beautifications and adjustments for compiling under Linux
17     by Markus Gutschke <gutschk@math.uni-muenster.de>
18                                                 1997-01-27
19
20     Modifications to allow use as a filter by  Ken Yap <ken_yap@users.sourceforge.net>.
21                                                 1997-07-01
22
23     Small mod to cope with running on big-endian machines
24     by Jim Hague <jim.hague@acm.org)
25                                                 1998-02-06
26
27     Make compression statistics report shorter
28     by Ken Yap <ken_yap@users.sourceforge.net>.
29                                                 2001-04-25
30 **************************************************************/
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <ctype.h>
35 #include <errno.h>
36
37 #ifndef VERBOSE
38 #define Fprintf(x)
39 #define wterr     0
40 #else
41 #define Fprintf(x) fprintf x
42 #if defined(ENCODE) || defined(DECODE)
43 static char wterr[] = "Can't write.";
44 #ifdef ENCODE
45 static unsigned long int codesize = 0;
46 #endif
47 static unsigned long int printcount = 0;
48 #endif
49 #endif
50
51 #ifndef MAIN
52 extern
53 #endif
54 FILE  *infile, *outfile;
55
56 #if defined(ENCODE) || defined(DECODE)
57 static unsigned long int  textsize = 0;
58
59 static __inline__ void Error(char *message)
60 {
61     Fprintf((stderr, "\n%s\n", message));
62     exit(EXIT_FAILURE);
63 }
64
65 /* These will be a complete waste of time on a lo-endian */
66 /* system, but it only gets done once so WTF. */
67 static unsigned long i86ul_to_host(unsigned long ul)
68 {
69     unsigned long res = 0;
70     int i;
71     union
72     {
73         unsigned char c[4];
74         unsigned long ul;
75     } u;
76
77     u.ul = ul;
78     for (i = 3; i >= 0; i--)
79         res = (res << 8) + u.c[i];
80     return res;
81 }
82
83 static unsigned long host_to_i86ul(unsigned long ul)
84 {
85     int i;
86     union
87     {
88         unsigned char c[4];
89         unsigned long ul;
90     } u;
91
92     for (i = 0; i < 4; i++)
93     {
94         u.c[i] = ul & 0xff;
95         ul >>= 8;
96     }
97     return u.ul;
98 }
99 #endif
100
101 /********** LZSS compression **********/
102
103 #define N       4096    /* buffer size */
104 /* Attention: When using this file for f6fbb-type compressed data exchange,
105    set N to 2048 ! (DL8HBS) */
106 #define F       60  /* lookahead buffer size */
107 #define THRESHOLD   2
108 #define NIL     N   /* leaf of tree */
109
110 #if defined(ENCODE) || defined(DECODE)
111 static unsigned char
112         text_buf[N + F - 1];
113 #endif
114
115 #ifdef ENCODE
116 static int     match_position, match_length,
117                lson[N + 1], rson[N + 257], dad[N + 1];
118
119 static void InitTree(void)  /* initialize trees */
120 {
121     int  i;
122
123     for (i = N + 1; i <= N + 256; i++)
124         rson[i] = NIL;          /* root */
125     for (i = 0; i < N; i++)
126         dad[i] = NIL;           /* node */
127 }
128
129 static void InsertNode(int r)  /* insert to tree */
130 {
131     int  i, p, cmp;
132     unsigned char  *key;
133     unsigned c;
134
135     cmp = 1;
136     key = &text_buf[r];
137     p = N + 1 + key[0];
138     rson[r] = lson[r] = NIL;
139     match_length = 0;
140     for ( ; ; ) {
141         if (cmp >= 0) {
142             if (rson[p] != NIL)
143                 p = rson[p];
144             else {
145                 rson[p] = r;
146                 dad[r] = p;
147                 return;
148             }
149         } else {
150             if (lson[p] != NIL)
151                 p = lson[p];
152             else {
153                 lson[p] = r;
154                 dad[r] = p;
155                 return;
156             }
157         }
158         for (i = 1; i < F; i++)
159             if ((cmp = key[i] - text_buf[p + i]) != 0)
160                 break;
161         if (i > THRESHOLD) {
162             if (i > match_length) {
163                 match_position = ((r - p) & (N - 1)) - 1;
164                 if ((match_length = i) >= F)
165                     break;
166             }
167             if (i == match_length) {
168                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
169                     match_position = c;
170                 }
171             }
172         }
173     }
174     dad[r] = dad[p];
175     lson[r] = lson[p];
176     rson[r] = rson[p];
177     dad[lson[p]] = r;
178     dad[rson[p]] = r;
179     if (rson[dad[p]] == p)
180         rson[dad[p]] = r;
181     else
182         lson[dad[p]] = r;
183     dad[p] = NIL;  /* remove p */
184 }
185
186 static void DeleteNode(int p)  /* remove from tree */
187 {
188     int  q;
189
190     if (dad[p] == NIL)
191         return;         /* not registered */
192     if (rson[p] == NIL)
193         q = lson[p];
194     else
195     if (lson[p] == NIL)
196         q = rson[p];
197     else {
198         q = lson[p];
199         if (rson[q] != NIL) {
200             do {
201                 q = rson[q];
202             } while (rson[q] != NIL);
203             rson[dad[q]] = lson[q];
204             dad[lson[q]] = dad[q];
205             lson[q] = lson[p];
206             dad[lson[p]] = q;
207         }
208         rson[q] = rson[p];
209         dad[rson[p]] = q;
210     }
211     dad[q] = dad[p];
212     if (rson[dad[p]] == p)
213         rson[dad[p]] = q;
214     else
215         lson[dad[p]] = q;
216     dad[p] = NIL;
217 }
218 #endif
219
220 /* Huffman coding */
221
222 #define N_CHAR      (256 - THRESHOLD + F)
223                 /* kinds of characters (character code = 0..N_CHAR-1) */
224 #define T       (N_CHAR * 2 - 1)    /* size of table */
225 #define R       (T - 1)         /* position of root */
226 #define MAX_FREQ    0x8000      /* updates tree when the */
227                     /* root frequency comes to this value. */
228 typedef unsigned char uchar;
229
230 /* table for encoding and decoding the upper 6 bits of position */
231
232 /* for encoding */
233
234 #ifdef ENCODE
235 static uchar p_len[64] = {
236     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
237     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
238     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
239     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
240     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
241     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
242     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
243     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
244 };
245
246 static uchar p_code[64] = {
247     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
248     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
249     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
250     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
251     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
252     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
253     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
254     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
255 };
256 #endif
257
258 #ifdef DECODE
259 /* for decoding */
260 static uchar d_code[256] = {
261     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
262     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
263     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
264     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
265     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
266     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
267     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
268     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
269     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
270     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
271     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
272     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
273     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
274     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
275     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
276     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
277     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
278     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
279     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
280     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
281     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
282     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
283     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
284     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
285     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
286     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
287     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
288     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
289     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
290     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
291     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
292     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
293 };
294
295 static uchar d_len[256] = {
296     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
297     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
298     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
299     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
300     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
301     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
302     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
303     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
304     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
305     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
306     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
307     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
308     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
309     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
310     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
311     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
312     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
313     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
314     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
315     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
316     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
317     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
318     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
319     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
320     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
321     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
322     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
323     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
324     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
325     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
326     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
327     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
328 };
329 #endif
330
331 #if defined(ENCODE) || defined(DECODE)
332 static unsigned freq[T + 1];   /* frequency table */
333
334 static int prnt[T + N_CHAR];   /* pointers to parent nodes, except for the */
335             /* elements [T..T + N_CHAR - 1] which are used to get */
336             /* the positions of leaves corresponding to the codes. */
337
338 static int son[T];     /* pointers to child nodes (son[], son[] + 1) */
339 #endif
340
341 #ifdef DECODE
342 static unsigned getbuf = 0;
343 static uchar getlen = 0;
344
345 static int GetBit(void)    /* get one bit */
346 {
347     int i;
348
349     while (getlen <= 8) {
350         if ((i = getc(infile)) < 0) i = 0;
351         getbuf |= i << (8 - getlen);
352         getlen += 8;
353     }
354     i = getbuf;
355     getbuf <<= 1;
356     getlen--;
357     return ((signed short)i < 0);
358 }
359
360 static int GetByte(void)   /* get one byte */
361 {
362     unsigned short i;
363
364     while (getlen <= 8) {
365         if ((signed short)(i = getc(infile)) < 0) i = 0;
366         getbuf |= i << (8 - getlen);
367         getlen += 8;
368     }
369     i = getbuf;
370     getbuf <<= 8;
371     getlen -= 8;
372     return i >> 8;
373 }
374 #endif
375
376 #ifdef ENCODE
377 static unsigned putbuf = 0;
378 static uchar putlen = 0;
379
380 static void Putcode(int l, unsigned c)     /* output c bits of code */
381 {
382     putbuf |= c >> putlen;
383     if ((putlen += l) >= 8) {
384         if (putc(putbuf >> 8, outfile) == EOF) {
385             Error(wterr);
386         }
387         if ((putlen -= 8) >= 8) {
388             if (putc(putbuf, outfile) == EOF) {
389                 Error(wterr);
390             }
391 #ifdef VERBOSE
392             codesize += 2;
393 #endif
394             putlen -= 8;
395             putbuf = c << (l - putlen);
396         } else {
397           putbuf <<= 8;
398 #ifdef VERBOSE
399           codesize++;
400 #endif
401         }
402     }
403 }
404 #endif
405
406 /* initialization of tree */
407
408 #if defined(ENCODE) || defined(DECODE)
409 static void StartHuff(void)
410 {
411     int i, j;
412
413     for (i = 0; i < N_CHAR; i++) {
414         freq[i] = 1;
415         son[i] = i + T;
416         prnt[i + T] = i;
417     }
418     i = 0; j = N_CHAR;
419     while (j <= R) {
420         freq[j] = freq[i] + freq[i + 1];
421         son[j] = i;
422         prnt[i] = prnt[i + 1] = j;
423         i += 2; j++;
424     }
425     freq[T] = 0xffff;
426     prnt[R] = 0;
427 }
428
429 /* reconstruction of tree */
430
431 static void reconst(void)
432 {
433     int i, j, k;
434     unsigned f, l;
435
436     /* collect leaf nodes in the first half of the table */
437     /* and replace the freq by (freq + 1) / 2. */
438     j = 0;
439     for (i = 0; i < T; i++) {
440         if (son[i] >= T) {
441             freq[j] = (freq[i] + 1) / 2;
442             son[j] = son[i];
443             j++;
444         }
445     }
446     /* begin constructing tree by connecting sons */
447     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
448         k = i + 1;
449         f = freq[j] = freq[i] + freq[k];
450         for (k = j - 1; f < freq[k]; k--);
451         k++;
452         l = (j - k) * 2;
453         memmove(&freq[k + 1], &freq[k], l);
454         freq[k] = f;
455         memmove(&son[k + 1], &son[k], l);
456         son[k] = i;
457     }
458     /* connect prnt */
459     for (i = 0; i < T; i++) {
460         if ((k = son[i]) >= T) {
461             prnt[k] = i;
462         } else {
463             prnt[k] = prnt[k + 1] = i;
464         }
465     }
466 }
467
468 /* increment frequency of given code by one, and update tree */
469
470 static void update(int c)
471 {
472     int i, j, k, l;
473
474     if (freq[R] == MAX_FREQ) {
475         reconst();
476     }
477     c = prnt[c + T];
478     do {
479         k = ++freq[c];
480
481         /* if the order is disturbed, exchange nodes */
482         if (k > freq[l = c + 1]) {
483             while (k > freq[++l]);
484             l--;
485             freq[c] = freq[l];
486             freq[l] = k;
487
488             i = son[c];
489             prnt[i] = l;
490             if (i < T) prnt[i + 1] = l;
491
492             j = son[l];
493             son[l] = i;
494
495             prnt[j] = c;
496             if (j < T) prnt[j + 1] = c;
497             son[c] = j;
498
499             c = l;
500         }
501     } while ((c = prnt[c]) != 0);   /* repeat up to root */
502 }
503 #endif
504
505 #ifdef ENCODE
506 #if 0
507 static unsigned code, len;
508 #endif
509
510 static void EncodeChar(unsigned c)
511 {
512     unsigned i;
513     int j, k;
514
515     i = 0;
516     j = 0;
517     k = prnt[c + T];
518
519     /* travel from leaf to root */
520     do {
521         i >>= 1;
522
523         /* if node's address is odd-numbered, choose bigger brother node */
524         if (k & 1) i += 0x8000;
525
526         j++;
527     } while ((k = prnt[k]) != R);
528     Putcode(j, i);
529 #if 0
530     code = i;
531     len = j;
532 #endif
533     update(c);
534 }
535
536 static void EncodePosition(unsigned c)
537 {
538     unsigned i;
539
540     /* output upper 6 bits by table lookup */
541     i = c >> 6;
542     Putcode(p_len[i], (unsigned)p_code[i] << 8);
543
544     /* output lower 6 bits verbatim */
545     Putcode(6, (c & 0x3f) << 10);
546 }
547
548 static void EncodeEnd(void)
549 {
550     if (putlen) {
551         if (putc(putbuf >> 8, outfile) == EOF) {
552             Error(wterr);
553         }
554 #ifdef VERBOSE
555         codesize++;
556 #endif
557     }
558 }
559 #endif
560
561 #ifdef DECODE
562 static int DecodeChar(void)
563 {
564     unsigned c;
565
566     c = son[R];
567
568     /* travel from root to leaf, */
569     /* choosing the smaller child node (son[]) if the read bit is 0, */
570     /* the bigger (son[]+1} if 1 */
571     while (c < T) {
572         c += GetBit();
573         c = son[c];
574     }
575     c -= T;
576     update(c);
577     return c;
578 }
579
580 static int DecodePosition(void)
581 {
582     unsigned i, j, c;
583
584     /* recover upper 6 bits from table */
585     i = GetByte();
586     c = (unsigned)d_code[i] << 6;
587     j = d_len[i];
588
589     /* read lower 6 bits verbatim */
590     j -= 2;
591     while (j--) {
592         i = (i << 1) + GetBit();
593     }
594     return c | (i & 0x3f);
595 }
596 #endif
597
598 #ifdef ENCODE
599 /* compression */
600
601 void Encode(void)  /* compression */
602 {
603     int  i, c, len, r, s, last_match_length;
604     unsigned long tw;
605
606     fseek(infile, 0L, 2);
607     textsize = ftell(infile);
608 #ifdef VERBOSE
609     if ((signed long)textsize < 0)
610       Fprintf((stderr, "Errno: %d", errno));
611 #endif
612     tw = host_to_i86ul(textsize);
613     if (fwrite(&tw, sizeof tw, 1, outfile) < 1)
614         Error(wterr);   /* output size of text */
615     if (textsize == 0)
616         return;
617     rewind(infile);
618     textsize = 0;           /* rewind and re-read */
619     StartHuff();
620     InitTree();
621     s = 0;
622     r = N - F;
623     for (i = s; i < r; i++)
624         text_buf[i] = ' ';
625     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
626         text_buf[r + len] = c;
627     textsize = len;
628     for (i = 1; i <= F; i++)
629         InsertNode(r - i);
630     InsertNode(r);
631     do {
632         if (match_length > len)
633             match_length = len;
634         if (match_length <= THRESHOLD) {
635             match_length = 1;
636             EncodeChar(text_buf[r]);
637         } else {
638             EncodeChar(255 - THRESHOLD + match_length);
639             EncodePosition(match_position);
640         }
641         last_match_length = match_length;
642         for (i = 0; i < last_match_length &&
643                 (c = getc(infile)) != EOF; i++) {
644             DeleteNode(s);
645             text_buf[s] = c;
646             if (s < F - 1)
647                 text_buf[s + N] = c;
648             s = (s + 1) & (N - 1);
649             r = (r + 1) & (N - 1);
650             InsertNode(r);
651         }
652         if ((textsize += i) > printcount) {
653 #if defined(VERBOSE) && defined(EXTRAVERBOSE)
654             Fprintf((stderr, "%12ld\r", textsize));
655 #endif
656             printcount += 1024;
657         }
658         while (i++ < last_match_length) {
659             DeleteNode(s);
660             s = (s + 1) & (N - 1);
661             r = (r + 1) & (N - 1);
662             if (--len) InsertNode(r);
663         }
664     } while (len > 0);
665     EncodeEnd();
666 #ifdef  LONG_REPORT
667     Fprintf((stderr, "input size    %ld bytes\n", codesize));
668     Fprintf((stderr, "output size   %ld bytes\n", textsize));
669     Fprintf((stderr, "input/output  %.3f\n", (double)codesize / textsize));
670 #else
671     Fprintf((stderr, "input/output = %ld/%ld = %.3f\n", codesize, textsize,
672                 (double)codesize / textsize));
673 #endif
674 }
675 #endif
676
677 #ifdef DECODE
678 void Decode(void)  /* recover */
679 {
680     int  i, j, k, r, c;
681     unsigned long int  count;
682     unsigned long tw;
683
684     if (fread(&tw, sizeof tw, 1, infile) < 1)
685         Error("Can't read");  /* read size of text */
686     textsize = i86ul_to_host(tw);
687     if (textsize == 0)
688         return;
689     StartHuff();
690     for (i = 0; i < N - F; i++)
691         text_buf[i] = ' ';
692     r = N - F;
693     for (count = 0; count < textsize; ) {
694         c = DecodeChar();
695         if (c < 256) {
696             if (putc(c, outfile) == EOF) {
697                 Error(wterr);
698             }
699             text_buf[r++] = c;
700             r &= (N - 1);
701             count++;
702         } else {
703             i = (r - DecodePosition() - 1) & (N - 1);
704             j = c - 255 + THRESHOLD;
705             for (k = 0; k < j; k++) {
706                 c = text_buf[(i + k) & (N - 1)];
707                 if (putc(c, outfile) == EOF) {
708                     Error(wterr);
709                 }
710                 text_buf[r++] = c;
711                 r &= (N - 1);
712                 count++;
713             }
714         }
715         if (count > printcount) {
716 #if defined(VERBOSE) && defined(EXTRAVERBOSE)
717             Fprintf((stderr, "%12ld\r", count));
718 #endif
719             printcount += 1024;
720         }
721     }
722     Fprintf((stderr, "%12ld\n", count));
723 }
724 #endif
725
726 #ifdef MAIN
727 int main(int argc, char *argv[])
728 {
729     char  *s;
730     FILE  *f;
731     int    c;
732
733     if (argc == 2) {
734         outfile = stdout;
735         if ((f = tmpfile()) == NULL) {
736             perror("tmpfile");
737             return EXIT_FAILURE;
738         }
739         while ((c = getchar()) != EOF)
740             fputc(c, f);
741         rewind(infile = f);
742     }
743     else if (argc != 4) {
744         Fprintf((stderr, "'lzhuf e file1 file2' encodes file1 into file2.\n"
745                 "'lzhuf d file2 file1' decodes file2 into file1.\n"));
746         return EXIT_FAILURE;
747     }
748     if (argc == 4) {
749         if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
750           || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
751           || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
752             Fprintf((stderr, "??? %s\n", s));
753             return EXIT_FAILURE;
754         }
755     }
756     if (toupper(*argv[1]) == 'E')
757         Encode();
758     else
759         Decode();
760     fclose(infile);
761     fclose(outfile);
762     return EXIT_SUCCESS;
763 }
764 #endif