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