gpxe/contrib/compressor/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