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