home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / uucp / auucp+-1.02 / fuucp_plus_src.lzh / uucplib / lzhuf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-12  |  27.7 KB  |  939 lines
  1. /*----------------------------------------------------------------------*/
  2. /*  zhuf.c : Encoding/Decoding module for LHarc                         */
  3. /*                                                                      */
  4. /*  LZSS Algorithm      Haruhiko.Okumura                                */
  5. /*  Adaptic Huffman Encoding  1989.05.27  Haruyasu.Yoshizaki            */
  6. /*                                                                      */
  7. /*                                                                      */
  8. /*  Modified for UNIX LHarc V0.01       1989.05.28  Y.Tagawa            */
  9. /*  Modified for UNIX LHarc V0.02       1989.05.29  Y.Tagawa            */
  10. /*  Modified for UNIX LHarc V0.03       1989.07.02  Y.Tagawa            */
  11. /*----------------------------------------------------------------------*/
  12.  
  13. #include <string.h>
  14. #include "uucpbase.h"
  15. #include "uucpproto.h"
  16. #include "buffer.h"
  17.  
  18. #ifndef SELFMAIN
  19. #include "lhio.h"
  20. #else
  21. #define EXIT_SUCCESS    0
  22. #define EXIT_FAILURE    1
  23. #endif
  24.  
  25.  
  26.  
  27. FILE *infile, *outfile;
  28. long textsize, codesize;
  29.  
  30.  
  31. #define INDICATOR_THRESHOLD     4096L
  32. #define MAX_INDICATOR_COUNT     78
  33. long indicator_count;
  34. long indicator_threshold;
  35.  
  36. #ifdef SELFMAIN
  37. int quiet = 0;
  38. #else
  39. extern int quiet;
  40. extern int output_to_test;
  41. #endif
  42.  
  43.  
  44. #ifdef SELFMAIN
  45. #define SETUP_PUTC_CRC(fp)      /* nothing */
  46. #define SETUP_GETC_CRC(fp)      /* nothing */
  47. #define PUTC_CRC(c)             putc((c),(outfile))
  48. #define GETC_CRC()              getc(infile)
  49. #define END_PUTC_CRC()
  50. #define END_GETC_CRC()
  51. #else
  52. #define SETUP_PUTC_CRC(fp)      crc_outfile = fp
  53. #define SETUP_GETC_CRC(fp)      crc_infile = fp
  54. #define PUTC_CRC(c)             putc_crc(c)
  55. #define GETC_CRC()              getc_crc()
  56. #define END_PUTC_CRC()
  57. #define END_GETC_CRC()
  58. #endif
  59.  
  60.  
  61.  
  62.  
  63. #ifdef SELFMAIN
  64. void Error (message)
  65.         char *message;
  66. {
  67.         printf("\n%s\n", message);
  68.         exit(EXIT_FAILURE);
  69. }
  70. #endif
  71.  
  72. /*----------------------------------------------------------------------*/
  73. /*                                                                      */
  74. /*              LZSS ENCODING                                           */
  75. /*                                                                      */
  76. /*----------------------------------------------------------------------*/
  77.  
  78. #define N               4096    /* buffer size */
  79. #define F               60      /* pre-sence buffer size */
  80. #define THRESHOLD       2
  81. #define NIL             N       /* term of tree */
  82.  
  83. unsigned char    __far text_buf[N + F - 1];
  84. unsigned int     match_position, match_length;
  85. int              __far lson[N + 1], rson[N + 1 + N], dad[N + 1];
  86. unsigned char    __far same[N + 1];
  87.  
  88.  
  89. /* Initialize Tree */
  90. InitTree ()
  91. {
  92.         register int *p, *e;
  93.  
  94.         for (p = rson + N + 1, e = rson + N + N; p <= e; )
  95.                 *p++ = NIL;
  96.         for (p = dad, e = dad + N; p < e; )
  97.                 *p++ = NIL;
  98. }
  99.  
  100.  
  101. /* Insert to node */
  102. InsertNode (r)
  103.         register int r;
  104. {
  105.         register int            p;
  106.         int                     cmp;
  107.         register unsigned char  *key;
  108.         register unsigned int   c;
  109.         register unsigned int   i, j;
  110.  
  111.         cmp = 1;
  112.         key = &text_buf[r];
  113.         i = key[1] ^ key[2];
  114.         i ^= i >> 4;
  115.         p = N + 1 + key[0] + ((i & 0x0f) << 8);
  116.         rson[r] = lson[r] = NIL;
  117.         match_length = 0;
  118.         i = j = 1;
  119.         for ( ; ; ) {
  120.                 if (cmp >= 0) {
  121.                         if (rson[p] != NIL) {
  122.                                 p = rson[p];
  123.                                 j = same[p];
  124.                         } else {
  125.                                 rson[p] = r;
  126.                                 dad[r] = p;
  127.                                 same[r] = i;
  128.                                 return;
  129.                         }
  130.                 } else {
  131.                         if (lson[p] != NIL) {
  132.                                 p = lson[p];
  133.                                 j = same[p];
  134.                         } else {
  135.                                 lson[p] = r;
  136.                                 dad[r] = p;
  137.                                 same[r] = i;
  138.                                 return;
  139.                         }
  140.                 }
  141.  
  142.                 if (i > j) {
  143.                         i = j;
  144.                         cmp = key[i] - text_buf[p + i];
  145.                 } else
  146.                 if (i == j) {
  147.                         for (; i < F; i++)
  148.                                 if ((cmp = key[i] - text_buf[p + i]) != 0)
  149.                                         break;
  150.                 }
  151.  
  152.                 if (i > THRESHOLD) {
  153.                         if (i > match_length) {
  154.                                 match_position = ((r - p) & (N - 1)) - 1;
  155.                                 if ((match_length = i) >= F)
  156.                                         break;
  157.                         } else
  158.                         if (i == match_length) {
  159.                                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  160.                                         match_position = c;
  161.                                 }
  162.                         }
  163.                 }
  164.         }
  165.         same[r] = same[p];
  166.         dad[r] = dad[p];
  167.         lson[r] = lson[p];
  168.         rson[r] = rson[p];
  169.         dad[lson[p]] = r;
  170.         dad[rson[p]] = r;
  171.         if (rson[dad[p]] == p)
  172.                 rson[dad[p]] = r;
  173.         else
  174.                 lson[dad[p]] = r;
  175.         dad[p] = NIL;  /* remove p */
  176. }
  177.  
  178.  
  179. link (n, p, q)
  180.         int n, p, q;
  181. {
  182.         register unsigned char *s1, *s2, *s3;
  183.         if (p >= NIL) {
  184.                 same[q] = 1;
  185.                 return;
  186.         }
  187.         s1 = text_buf + p + n;
  188.         s2 = text_buf + q + n;
  189.         s3 = text_buf + p + F;
  190.         while (s1 < s3) {
  191.                 if (*s1++ != *s2++) {
  192.                         same[q] = s1 - 1 - text_buf - p;
  193.                         return;
  194.                 }
  195.         }
  196.         same[q] = F;
  197. }
  198.  
  199.  
  200. linknode (p, q, r)
  201.         int p, q, r;
  202. {
  203.         int cmp;
  204.  
  205.         if ((cmp = same[q] - same[r]) == 0) {
  206.                 link(same[q], p, r);
  207.         } else if (cmp < 0) {
  208.                 same[r] = same[q];
  209.         }
  210. }
  211.  
  212. DeleteNode (p)
  213.         register int p;
  214. {
  215.         register int  q;
  216.  
  217.         if (dad[p] == NIL)
  218.                 return;                 /* has no linked */
  219.         if (rson[p] == NIL) {
  220.                 if ((q = lson[p]) != NIL)
  221.                         linknode(dad[p], p, q);
  222.         } else
  223.         if (lson[p] == NIL) {
  224.                 q = rson[p];
  225.                 linknode(dad[p], p, q);
  226.         } else {
  227.                 q = lson[p];
  228.                 if (rson[q] != NIL) {
  229.                         do {
  230.                                 q = rson[q];
  231.                         } while (rson[q] != NIL);
  232.                         if (lson[q] != NIL)
  233.                                 linknode(dad[q], q, lson[q]);
  234.                         link(1, q, lson[p]);
  235.                         rson[dad[q]] = lson[q];
  236.                         dad[lson[q]] = dad[q];
  237.                         lson[q] = lson[p];
  238.                         dad[lson[p]] = q;
  239.                 }
  240.                 link(1, dad[p], q);
  241.                 link(1, q, rson[p]);
  242.                 rson[q] = rson[p];
  243.                 dad[rson[p]] = q;
  244.         }
  245.         dad[q] = dad[p];
  246.         if (rson[dad[p]] == p)
  247.                 rson[dad[p]] = q;
  248.         else
  249.                 lson[dad[p]] = q;
  250.         dad[p] = NIL;
  251. }
  252.  
  253. /*----------------------------------------------------------------------*/
  254. /*                                                                      */
  255. /*              HUFFMAN ENCODING                                        */
  256. /*                                                                      */
  257. /*----------------------------------------------------------------------*/
  258.  
  259. #define N_CHAR          (256 - THRESHOLD + F) /* {code : 0 .. N_CHAR-1} */
  260. #define T               (N_CHAR * 2 - 1)        /* size of table */
  261. #define R               (T - 1)                 /* root position */
  262. #define MAX_FREQ        0x8000  /* tree update timing from frequency */
  263.  
  264. typedef unsigned char uchar;
  265.  
  266.  
  267.  
  268. /* TABLE OF ENCODE/DECODE for upper 6bits position information */
  269.  
  270. /* for encode */
  271. uchar p_len[64] = {
  272.         0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  273.         0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  274.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  275.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  276.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  277.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  278.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  279.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  280. };
  281.  
  282. uchar p_code[64] = {
  283.         0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  284.         0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  285.         0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  286.         0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  287.         0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  288.         0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  289.         0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  290.         0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  291. };
  292.  
  293. /* for decode */
  294. uchar d_code[256] = {
  295.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  296.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  297.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  298.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  299.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  300.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  301.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  302.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  303.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  304.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  305.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  306.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  307.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  308.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  309.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  310.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  311.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  312.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  313.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  314.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  315.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  316.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  317.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  318.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  319.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  320.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  321.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  322.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  323.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  324.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  325.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  326.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  327. };
  328.  
  329. uchar d_len[256] = {
  330.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  331.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  332.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  333.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  334.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  335.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  336.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  337.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  338.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  339.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  340.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  341.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  342.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  343.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  344.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  345.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  346.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  347.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  348.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  349.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  350.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  351.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  352.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  353.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  354.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  355.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  356.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  357.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  358.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  359.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  360.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  361.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  362. };
  363.  
  364. unsigned freq[T + 1];    /* frequency table */
  365.  
  366. int prnt[T + N_CHAR];    /* points to parent node */
  367. /* notes :
  368.    prnt[T .. T + N_CHAR - 1] used by
  369.    indicates leaf position that corresponding to code */
  370.  
  371. int son[T];              /* points to son node (son[i],son[i+]) */
  372.  
  373. unsigned getbuf = 0;
  374. uchar getlen = 0;
  375.  
  376.  
  377. /* get one bit */
  378. /* returning in Bit 0 */
  379. int GetBit ()
  380. {
  381.         register unsigned int dx = getbuf;
  382.         register unsigned int c;
  383.  
  384.         if (getlen <= 8)
  385.                 {
  386.                         c = getc (infile);
  387.                         if ((int)c < 0) c = 0;
  388.                         dx |= c << (8 - getlen);
  389.                         getlen += 8;
  390.                 }
  391.         getbuf = dx << 1;
  392.         getlen--;
  393.         return (dx & 0x8000) ? 1 : 0;
  394. }
  395.  
  396. /* get one byte */
  397. /* returning in Bit7...0 */
  398. int GetByte ()
  399. {
  400.         register unsigned int dx = getbuf;
  401.         register unsigned c;
  402.  
  403.         if (getlen <= 8) {
  404.                 c = getc (infile);
  405.                 if ((int)c < 0) c = 0;
  406.                 dx |= c << (8 - getlen);
  407.                 getlen += 8;
  408.         }
  409.         getbuf = dx << 8;
  410.         getlen -= 8;
  411.         return (dx >> 8) & 0xff;
  412. }
  413.  
  414. /* get N bit */
  415. /* returning in Bit(N-1)...Bit 0 */
  416. int GetNBits (n)
  417.         register unsigned int n;
  418. {
  419.         register unsigned int dx = getbuf;
  420.         register unsigned int c;
  421.         static int mask[17] = {
  422.                 0x0000,
  423.                 0x0001, 0x0003, 0x0007, 0x000f,
  424.                 0x001f, 0x003f, 0x007f, 0x00ff,
  425.                 0x01ff, 0x03ff, 0x07ff, 0x0fff,
  426.                 0x1fff, 0x3fff, 0x0fff, 0xffff };
  427.         static int shift[17] = {
  428.                 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
  429.  
  430.         if (getlen <= 8)
  431.                 {
  432.                         c = getc (infile);
  433.                         if ((int)c < 0) c = 0;
  434.                         dx |= c << (8 - getlen);
  435.                         getlen += 8;
  436.                 }
  437.         getbuf = dx << n;
  438.         getlen -= n;
  439.         return (dx >> shift[n]) & mask[n];
  440. }
  441.  
  442. unsigned putbuf = 0;
  443. uchar putlen = 0;
  444.  
  445. /* output C bits */
  446. Putcode (l, c)
  447.         register int l;
  448.         register unsigned int c;
  449. {
  450.         register len = putlen;
  451.         register unsigned int b = putbuf;
  452.         b |= c >> len;
  453.         if ((len += l) >= 8) {
  454.                 putc (b >> 8, outfile);
  455.                 if ((len -= 8) >= 8) {
  456.                         putc (b, outfile);
  457.                         codesize += 2;
  458.                         len -= 8;
  459.                         b = c << (l - len);
  460.                 } else {
  461.                         b <<= 8;
  462.                         codesize++;
  463.                 }
  464.         }
  465.         putbuf = b;
  466.         putlen = len;
  467. }
  468.  
  469.  
  470. /* Initialize tree */
  471.  
  472. StartHuff ()
  473. {
  474.         register int i, j;
  475.  
  476.         for (i = 0; i < N_CHAR; i++) {
  477.                 freq[i] = 1;
  478.                 son[i] = i + T;
  479.                 prnt[i + T] = i;
  480.         }
  481.         i = 0; j = N_CHAR;
  482.         while (j <= R) {
  483.                 freq[j] = freq[i] + freq[i + 1];
  484.                 son[j] = i;
  485.                 prnt[i] = prnt[i + 1] = j;
  486.                 i += 2; j++;
  487.         }
  488.         freq[T] = 0xffff;
  489.         prnt[R] = 0;
  490.         putlen = getlen = 0;
  491.         putbuf = getbuf = 0;
  492. }
  493.  
  494.  
  495. /* reconstruct tree */
  496. reconst ()
  497. {
  498.         register int i, j, k;
  499.         register unsigned f;
  500.  
  501.         /* correct leaf node into of first half,
  502.            and set these freqency to (freq+1)/2       */
  503.         j = 0;
  504.         for (i = 0; i < T; i++) {
  505.                 if (son[i] >= T) {
  506.                         freq[j] = (freq[i] + 1) / 2;
  507.                         son[j] = son[i];
  508.                         j++;
  509.                 }
  510.         }
  511.         /* build tree.  Link sons first */
  512.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  513.                 k = i + 1;
  514.                 f = freq[j] = freq[i] + freq[k];
  515.                 for (k = j - 1; f < freq[k]; k--);
  516.                 k++;
  517.                 {       register unsigned *p, *e;
  518.                         for (p = &freq[j], e = &freq[k]; p > e; p--)
  519.                                 p[0] = p[-1];
  520.                         freq[k] = f;
  521.                 }
  522.                 {       register int *p, *e;
  523.                         for (p = &son[j], e = &son[k]; p > e; p--)
  524.                                 p[0] = p[-1];
  525.                         son[k] = i;
  526.                 }
  527.         }
  528.         /* link parents */
  529.         for (i = 0; i < T; i++) {
  530.                 if ((k = son[i]) >= T) {
  531.                         prnt[k] = i;
  532.                 } else {
  533.                         prnt[k] = prnt[k + 1] = i;
  534.                 }
  535.         }
  536. }
  537.  
  538.  
  539. /* update given code's frequency, and update tree */
  540.  
  541. update (c)
  542.         unsigned int    c;
  543. {
  544.         register unsigned *p;
  545.         register int i, j, k, l;
  546.  
  547.         if (freq[R] == MAX_FREQ) {
  548.                 reconst();
  549.         }
  550.         c = prnt[c + T];
  551.         do {
  552.                 k = ++freq[c];
  553.  
  554.                 /* swap nodes when become wrong frequency order. */
  555.                 if (k > freq[l = c + 1]) {
  556.                         for (p = freq+l+1; k > *p++; ) ;
  557.                         l = p - freq - 2;
  558.                         freq[c] = p[-2];
  559.                         p[-2] = k;
  560.  
  561.                         i = son[c];
  562.                         prnt[i] = l;
  563.                         if (i < T) prnt[i + 1] = l;
  564.  
  565.                         j = son[l];
  566.                         son[l] = i;
  567.  
  568.                         prnt[j] = c;
  569.                         if (j < T) prnt[j + 1] = c;
  570.                         son[c] = j;
  571.  
  572.                         c = l;
  573.                 }
  574.         } while ((c = prnt[c]) != 0);   /* loop until reach to root */
  575. }
  576.  
  577. /* unsigned code, len; */
  578.  
  579. EncodeChar (c)
  580.         unsigned c;
  581. {
  582.         register int *p;
  583.         register unsigned long i;
  584.         register int j, k;
  585.  
  586.         i = 0;
  587.         j = 0;
  588.         p = prnt;
  589.         k = p[c + T];
  590.  
  591.         /* trace links from leaf node to root */
  592.         do {
  593.                 i >>= 1;
  594.  
  595.                 /* if node index is odd, trace larger of sons */
  596.                 if (k & 1) i += 0x80000000;
  597.  
  598.                 j++;
  599.         } while ((k = p[k]) != R) ;
  600.         if (j > 16) {
  601.                 Putcode(16, (unsigned int)(i >> 16));
  602.                 Putcode(j - 16, (unsigned int)i);
  603.         } else {
  604.                 Putcode(j, (unsigned int)(i >> 16));
  605.         }
  606. /*      code = i; */
  607. /*      len = j; */
  608.         update(c);
  609. }
  610.  
  611. EncodePosition (c)
  612.         unsigned c;
  613. {
  614.         unsigned i;
  615.  
  616.         /* output upper 6bit from table */
  617.         i = c >> 6;
  618.         Putcode((int)(p_len[i]), (unsigned int)(p_code[i]) << 8);
  619.  
  620.         /* output lower 6 bit */
  621.         Putcode(6, (unsigned int)(c & 0x3f) << 10);
  622. }
  623.  
  624. EncodeEnd ()
  625. {
  626.         if (putlen) {
  627.                 putc(putbuf >> 8, outfile);
  628.                 codesize++;
  629.         }
  630. }
  631.  
  632. int DecodeChar ()
  633. {
  634.         register unsigned c;
  635.  
  636.         c = son[R];
  637.  
  638.         /* trace from root to leaf,
  639.            got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
  640.         while (c < T) {
  641.                 c += GetBit();
  642.                 c = son[c];
  643.         }
  644.         c -= T;
  645.         update(c);
  646.         return c;
  647. }
  648.  
  649. int DecodePosition ()
  650. {
  651.         unsigned i, j, c;
  652.  
  653.         /* decode upper 6bit from table */
  654.         i = GetByte();
  655.         c = (unsigned)d_code[i] << 6;
  656.         j = d_len[i];
  657.  
  658.         /* get lower 6bit */
  659.         j -= 2;
  660.         return c | (((i << j) | GetNBits (j)) & 0x3f);
  661. }
  662.  
  663.  
  664. Encode ()
  665. {
  666.         register int  i, c, len, r, s, last_match_length;
  667.  
  668.         if (textsize == 0)
  669.                 return;
  670.  
  671.         textsize = 0;
  672.         StartHuff();
  673.         InitTree();
  674.         s = 0;
  675.         r = N - F;
  676.         for (i = s; i < r; i++)
  677.                 text_buf[i] = ' ';
  678.         for (len = 0; len < F && (c = GETC_CRC()) != EOF; len++)
  679.                 text_buf[r + len] = c;
  680.         textsize = len;
  681.         for (i = 1; i <= F; i++)
  682.                 InsertNode(r - i);
  683.         InsertNode(r);
  684.         do {
  685.                 if (match_length > len)
  686.                         match_length = len;
  687.                 if (match_length <= THRESHOLD) {
  688.                         match_length = 1;
  689.                         EncodeChar(text_buf[r]);
  690.                 } else {
  691.                         EncodeChar(255 - THRESHOLD + match_length);
  692.                         EncodePosition(match_position);
  693.                 }
  694.                 last_match_length = match_length;
  695.                 for (i = 0; i < last_match_length &&
  696.                                 (c = GETC_CRC()) != EOF; i++) {
  697.                         DeleteNode(s);
  698.                         text_buf[s] = c;
  699.                         if (s < F - 1)
  700.                                 text_buf[s + N] = c;
  701.                         s = (s + 1) & (N - 1);
  702.                         r = (r + 1) & (N - 1);
  703.                         InsertNode(r);
  704.                 }
  705.  
  706.                 textsize += i;
  707.                 if ((textsize > indicator_count) && !quiet) {
  708.                         putchar (BALL);
  709.                         fflush (stdout);
  710.                         indicator_count += indicator_threshold;
  711.                 }
  712.                 while (i++ < last_match_length) {
  713.                         DeleteNode(s);
  714.                         s = (s + 1) & (N - 1);
  715.                         r = (r + 1) & (N - 1);
  716.                         if (--len) InsertNode(r);
  717.                 }
  718.         } while (len > 0);
  719.         EncodeEnd();
  720.         END_GETC_CRC ();
  721. }
  722.  
  723. Decode ()
  724. {
  725.         register int    i, j, k, r, c;
  726.         register long   count;
  727.  
  728. #ifdef SELFMAIN
  729.         if (textsize == 0)
  730.                 return;
  731. #endif
  732.         StartHuff();
  733.         for (i = 0; i < N - F; i++)
  734.                 text_buf[i] = ' ';
  735.         r = N - F;
  736.         for (count = 0; count < textsize; ) {
  737.                 c = DecodeChar();
  738.                 if (c < 256) {
  739.                         PUTC_CRC (c);
  740.                         text_buf[r++] = c;
  741.                         r &= (N - 1);
  742.                         count++;
  743.                 } else {
  744.                         i = (r - DecodePosition() - 1) & (N - 1);
  745.                         j = c - 255 + THRESHOLD;
  746.                         for (k = 0; k < j; k++) {
  747.                                 c = text_buf[(i + k) & (N - 1)];
  748.                                 PUTC_CRC (c);
  749.                                 text_buf[r++] = c;
  750.                                 r &= (N - 1);
  751.                                 count++;
  752.                         }
  753.                 }
  754.  
  755.                 if (!quiet && (count > indicator_count)) {
  756.                         putchar (BALL);
  757.                         fflush (stdout);
  758.                         indicator_count += indicator_threshold;
  759.                 }
  760.         }
  761.         END_PUTC_CRC ();
  762. }
  763.  
  764. /*----------------------------------------------------------------------*/
  765. /*                                                                      */
  766. /*              Global Entries for Archiver Driver                      */
  767. /*                                                                      */
  768. /*----------------------------------------------------------------------*/
  769.  
  770.  
  771. start_indicator (name, size, msg)
  772.         char *name;
  773.         long size;
  774.         char *msg;
  775. {
  776.         long    i;
  777.         int     m;
  778.  
  779.         if (quiet)
  780.                 return;
  781.  
  782. #ifdef ANSI
  783.         m = MAX_INDICATOR_COUNT;
  784. #else
  785.         m = MAX_INDICATOR_COUNT - strlen (name);
  786. #endif
  787.         if (m < 0)
  788.                 m = 3;          /* (^_^) */
  789.  
  790. #ifdef ANSI
  791.         printf ("\r%s - %s:\n", name, msg);
  792. #else
  793.         printf ("\r%s - %s :  ", name, msg);
  794. #endif
  795.  
  796.         indicator_threshold =
  797.                 ((size  + (m * INDICATOR_THRESHOLD - 1)) /
  798.                  (m * INDICATOR_THRESHOLD) *
  799.                  INDICATOR_THRESHOLD);
  800.         i = ((size + (indicator_threshold - 1)) / indicator_threshold);
  801.         while (i--)
  802.                 putchar (DOT);
  803.         indicator_count = 0;
  804. #ifdef ANSI
  805.         printf ("\r%s%s - %s:\n", CURSORUP, name, msg);
  806. #else
  807.         printf ("\r%s - %s :  ", name, msg);
  808. #endif
  809.         fflush (stdout);
  810. }
  811.  
  812. finish_indicator2 (name, msg, pcnt)
  813.         char *name;
  814.         char *msg;
  815.         int pcnt;
  816. {
  817.         if (quiet)
  818.                 return;
  819.  
  820.         if (pcnt > 100) pcnt = 100;     /* (^_^) */
  821. #ifdef ANSI
  822.         printf ("\r%s%s - %s(%d%%)\n%s", CURSORUP, name, msg, pcnt, ERASEEOL);
  823. #else
  824.         printf ("\r%s - %s(%d%%)\n", name, msg, pcnt);
  825. #endif
  826.         fflush (stdout);
  827. }
  828.  
  829. finish_indicator (name, msg)
  830.         char *name;
  831.         char *msg;
  832. {
  833.         if (quiet)
  834.                 return;
  835.  
  836. #ifdef ANSI
  837.         printf ("\r%s%s - %s\n%s", CURSORUP, name, msg, ERASEEOL);
  838. #else
  839.         printf ("\r%s - %s\n", name, msg);
  840. #endif
  841.         fflush (stdout);
  842. }
  843.  
  844.  
  845. #ifndef SELFMAIN
  846. int encode_lzhuf (infp, outfp, size, original_size_var, packed_size_var, name)
  847.         FILE *infp;
  848.         FILE *outfp;
  849.         long size;
  850.         long *original_size_var;
  851.         long *packed_size_var;
  852.         char *name;
  853. {
  854.         infile = infp;
  855.         outfile = outfp;
  856.         SETUP_GETC_CRC(infp);
  857.         textsize = size;
  858.         codesize = 0;
  859.         init_crc ();
  860.         start_indicator (name, size, "Freezing");
  861.         Encode ();
  862.         finish_indicator2 (name, "Frozen",
  863.                            (int)((codesize * 100L) / crc_size));
  864.         *packed_size_var = codesize;
  865.         *original_size_var = crc_size;
  866.         return crc_value;
  867. }
  868.  
  869. int decode_lzhuf (infp, outfp, original_size, name)
  870.         FILE *infp;
  871.         FILE *outfp;
  872.         long original_size;
  873.         char *name;
  874. {
  875.         infile = infp;
  876.         outfile = outfp;
  877.         SETUP_PUTC_CRC(outfp);
  878.         textsize = original_size;
  879.         init_crc ();
  880.         start_indicator (name, original_size,
  881.                          (output_to_test ? "Testing" : "Melting"));
  882.         Decode ();
  883.         finish_indicator (name, (output_to_test ? "Tested  " : "Melted  "));
  884.         return crc_value;
  885. }
  886.  
  887. #ifdef SELFMAIN
  888. int main (argc, argv)
  889.         int argc;
  890.         char *argv[];
  891. {
  892.         char  *s;
  893.         int i;
  894.  
  895.         indicator_count = 0;
  896.         indicator_threshold = 1024;
  897.         textsize = codesize = 0;
  898.         if (argc != 4) {
  899.                 printf ("\
  900. usage: lzhuf e in_file out_file (packing)\n\
  901.        lzhuf d in_file out_file (unpacking)\n");
  902.                 return EXIT_FAILURE;
  903.         }
  904.         if ((s = argv[1], ((*s != 'e') && (*s != 'd')) || s[1] != '\0') ||
  905.             (s = argv[2], (infile  = fopen(s, "rb")) == NULL) ||
  906.             (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  907.                 printf("??? %s\n", s);
  908.                 return EXIT_FAILURE;
  909.         }
  910.         if (argv[1][0] == 'e') {
  911.                 /* Get original text size and output it */
  912.                 fseek(infile, 0L, 2);
  913.                 textsize = ftell(infile);
  914.                 rewind (infile);
  915.                 if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  916.                         Error("cannot write");
  917.  
  918.                 start_indicator (argv[2], textsize, "Freezing");
  919.                 Encode();
  920.                 finish_indicator2 (argv[2], "Frozen",
  921.                                    (int)((codesize * 100L) / textsize));
  922.  
  923.                 printf("input : %ld bytes\n", textsize);
  924.                 printf("output: %ld bytes\n", codesize);
  925.         } else {
  926.                 /* Read original text size */
  927.                 if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  928.                         Error("cannot read");
  929.  
  930.                 start_indicator (argv[2], textsize, "Melting");
  931.                 Decode();
  932.                 finish_indicator (argv[2], "Melted  ");
  933.         }
  934.         fclose(infile);
  935.         fclose(outfile);
  936.         return EXIT_SUCCESS;
  937. }
  938. #endif
  939.