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