home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1998 September / PCO_0998.ISO / filesbbs / dos / sbbs_src.exe / SBBS / SMB / LZH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-13  |  19.9 KB  |  785 lines
  1. /* LZH.C */
  2.  
  3. /* Rob Swindell's conversion of 1988 LZH (LHarc) encoding functions     */
  4. /* Based on Japanese version 29-NOV-1988                                */
  5. /* LZSS coded by Haruhiko Okumura                                        */
  6. /* Adaptive Huffman Coding coded by Haruyasu Yoshizaki                    */
  7.  
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13. #ifndef __WATCOMC__
  14.     #include <alloc.h>
  15. #endif
  16. #include "lzh.h"
  17.  
  18. /****************************************************************************/
  19. /* Memory allocation macros for various compilers and environments            */
  20. /* MALLOC is used for allocations of 64k or less                            */
  21. /* FREE is used to free buffers allocated with MALLOC                        */
  22. /* LMALLOC is used for allocations of possibly larger than 64k                */
  23. /* LFREE is used to free buffers allocated with LMALLOC                     */
  24. /* REALLOC is used to re-size a previously MALLOCed or LMALLOCed buffer     */
  25. /****************************************************************************/
  26. #if defined(__COMPACT__) || defined(__LARGE__) || defined(__HUGE__)
  27.     #if defined(__TURBOC__)
  28.         #define REALLOC(x,y) farrealloc(x,y)
  29.         #define LMALLOC(x) farmalloc(x)
  30.         #define MALLOC(x) farmalloc(x)
  31.         #define LFREE(x) farfree(x)
  32.         #define FREE(x) farfree(x)
  33.     #elif defined(__WATCOMC__)
  34.         #define REALLOC realloc
  35.         #define LMALLOC(x) halloc(x,1)    /* far heap, but slow */
  36.         #define MALLOC malloc            /* far heap, but 64k max */
  37.         #define LFREE hfree
  38.         #define FREE free
  39.     #else    /* Other 16-bit Compiler */
  40.         #define REALLOC realloc
  41.         #define LMALLOC malloc
  42.         #define MALLOC malloc
  43.         #define LFREE free
  44.         #define FREE free
  45.     #endif
  46. #else        /* 32-bit Compiler or Small Memory Model */
  47.     #define REALLOC realloc
  48.     #define LMALLOC malloc
  49.     #define MALLOC malloc
  50.     #define LFREE free
  51.     #define FREE free
  52. #endif
  53.  
  54.  
  55.  
  56. /* LZSS Parameters */
  57.  
  58. #define LZH_N            4096    /* Size of string buffer */
  59. #define LZH_F            60        /* Size of look-ahead buffer */
  60. #define LZH_THRESHOLD    2
  61. #define LZH_NIL         LZH_N    /* End of tree's node  */
  62.  
  63. #ifdef LZH_DYNAMIC_BUF
  64.  
  65. unsigned char *lzh_text_buf;
  66. short int    lzh_match_position, lzh_match_length,
  67.       *lzh_lson, *lzh_rson, *lzh_dad;
  68.  
  69. #else
  70.  
  71. unsigned char lzh_text_buf[LZH_N + LZH_F - 1];
  72. short int      lzh_match_position, lzh_match_length,
  73.         lzh_lson[LZH_N + 1], lzh_rson[LZH_N + 257], lzh_dad[LZH_N + 1];
  74.  
  75. #endif
  76.  
  77.  
  78. void lzh_init_tree(void)  /* Initializing tree */
  79. {
  80.     short int  i;
  81.  
  82.     for (i = LZH_N + 1; i <= LZH_N + 256; i++)
  83.         lzh_rson[i] = LZH_NIL;            /* root */
  84.     for (i = 0; i < LZH_N; i++)
  85.         lzh_dad[i] = LZH_NIL;            /* node */
  86. }
  87.  
  88. /******************************/
  89. /* Inserting node to the tree */
  90. /* Only used during encoding  */
  91. /******************************/
  92. void lzh_insert_node(short int r)
  93. {
  94.     short int  i, p, cmp;
  95.     unsigned char  *key;
  96.     unsigned c;
  97.  
  98.     cmp = 1;
  99.     key = lzh_text_buf+r;
  100.     p = LZH_N + 1 + key[0];
  101.     lzh_rson[r] = lzh_lson[r] = LZH_NIL;
  102.     lzh_match_length = 0;
  103.     for ( ; ; ) {
  104.         if (cmp >= 0) {
  105.             if (lzh_rson[p] != LZH_NIL)
  106.                 p = lzh_rson[p];
  107.             else {
  108.                 lzh_rson[p] = r;
  109.                 lzh_dad[r] = p;
  110.                 return;
  111.             }
  112.         } else {
  113.             if (lzh_lson[p] != LZH_NIL)
  114.                 p = lzh_lson[p];
  115.             else {
  116.                 lzh_lson[p] = r;
  117.                 lzh_dad[r] = p;
  118.                 return;
  119.             }
  120.         }
  121.         for (i = 1; i < LZH_F; i++)
  122.             if ((cmp = key[i] - lzh_text_buf[p + i]) != 0)
  123.                 break;
  124.         if (i > LZH_THRESHOLD) {
  125.             if (i > lzh_match_length) {
  126.                 lzh_match_position = ((r - p) & (LZH_N - 1)) - 1;
  127.                 if ((lzh_match_length = i) >= LZH_F)
  128.                     break;
  129.             }
  130.             if (i == lzh_match_length) {
  131.                 if ((c = ((r - p) & (LZH_N - 1)) - 1) < lzh_match_position) {
  132.                     lzh_match_position = c;
  133.                 }
  134.             }
  135.         }
  136.     }
  137.     lzh_dad[r] = lzh_dad[p];
  138.     lzh_lson[r] = lzh_lson[p];
  139.     lzh_rson[r] = lzh_rson[p];
  140.     lzh_dad[lzh_lson[p]] = r;
  141.     lzh_dad[lzh_rson[p]] = r;
  142.     if (lzh_rson[lzh_dad[p]] == p)
  143.         lzh_rson[lzh_dad[p]] = r;
  144.     else
  145.         lzh_lson[lzh_dad[p]] = r;
  146.     lzh_dad[p] = LZH_NIL;  /* remove p */
  147. }
  148.  
  149. void lzh_delete_node(short int p)  /* Deleting node from the tree */
  150. {
  151.     short int  q;
  152.  
  153.     if (lzh_dad[p] == LZH_NIL)
  154.         return;            /* unregistered */
  155.     if (lzh_rson[p] == LZH_NIL)
  156.         q = lzh_lson[p];
  157.     else
  158.     if (lzh_lson[p] == LZH_NIL)
  159.         q = lzh_rson[p];
  160.     else {
  161.         q = lzh_lson[p];
  162.         if (lzh_rson[q] != LZH_NIL) {
  163.             do {
  164.                 q = lzh_rson[q];
  165.             } while (lzh_rson[q] != LZH_NIL);
  166.             lzh_rson[lzh_dad[q]] = lzh_lson[q];
  167.             lzh_dad[lzh_lson[q]] = lzh_dad[q];
  168.             lzh_lson[q] = lzh_lson[p];
  169.             lzh_dad[lzh_lson[p]] = q;
  170.         }
  171.         lzh_rson[q] = lzh_rson[p];
  172.         lzh_dad[lzh_rson[p]] = q;
  173.     }
  174.     lzh_dad[q] = lzh_dad[p];
  175.     if (lzh_rson[lzh_dad[p]] == p)
  176.         lzh_rson[lzh_dad[p]] = q;
  177.     else
  178.         lzh_lson[lzh_dad[p]] = q;
  179.     lzh_dad[p] = LZH_NIL;
  180. }
  181.  
  182. /* Huffman coding parameters */
  183.  
  184. #define LZH_N_CHAR        (256 - LZH_THRESHOLD + LZH_F)
  185.                     /* character code (= 0..LZH_N_CHAR-1) */
  186. #define LZH_T        (LZH_N_CHAR * 2 - 1)    /* Size of table */
  187. #define LZH_R        (LZH_T - 1)         /* root position */
  188. #define MAX_FREQ    0x8000
  189.                     /* update when cumulative frequency */
  190.                     /* reaches to this value */
  191.  
  192. /*
  193.  * Tables for encoding/decoding upper 6 bits of
  194.  * sliding dictionary pointer
  195.  */
  196. /* encoder table */
  197. uchar lzh_p_len[64] = {
  198.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  199.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  200.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  201.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  202.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  203.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  204.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  205.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  206. };
  207.  
  208. uchar lzh_p_code[64] = {
  209.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  210.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  211.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  212.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  213.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  214.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  215.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  216.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  217. };
  218.  
  219. /* decoder table */
  220. uchar lzh_d_code[256] = {
  221.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  222.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  223.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  224.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  225.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  226.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  227.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  228.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  229.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  230.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  231.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  232.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  233.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  234.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  235.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  236.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  237.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  238.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  239.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  240.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  241.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  242.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  243.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  244.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  245.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  246.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  247.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  248.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  249.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  250.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  251.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  252.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  253. };
  254.  
  255. uchar lzh_d_len[256] = {
  256.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  257.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  258.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  259.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  260.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  261.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  262.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  263.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  264.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  265.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  266.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  267.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  268.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  269.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  270.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  271.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  272.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  273.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  274.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  275.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  276.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  277.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  278.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  279.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  280.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  281.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  282.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  283.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  284.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  285.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  286.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  287.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  288. };
  289.  
  290. #ifdef LZH_DYNAMIC_BUF
  291.  
  292. unsigned short *lzh_freq=NULL;     /* cumulative freq table */
  293.  
  294. /*
  295.  * pointing parent nodes.
  296.  * area [LZH_T..(LZH_T + LZH_N_CHAR - 1)] are pointers for leaves
  297.  */
  298. short int *lzh_prnt=NULL;
  299.  
  300. /* pointing children nodes (son[], son[] + 1)*/
  301. short int *lzh_son=NULL;
  302.  
  303. #else    /* STATIC */
  304.  
  305. unsigned short lzh_freq[LZH_T + 1];   /* cumulative freq table */
  306. short int lzh_prnt[LZH_T + LZH_N_CHAR];
  307. short int lzh_son[LZH_T + 1];          /* bug fixed by Digital Dynamics */
  308.  
  309. #endif
  310.  
  311.  
  312. unsigned short lzh_getbuf = 0;        /* Was just "unsigned" fixed 04/12/95 */
  313. uchar lzh_getlen = 0;
  314.  
  315. int lzh_getbit(uchar *inbuf, long *incnt, long inlen)    /* get one bit */
  316. {
  317.     short int i;
  318.  
  319.     while (lzh_getlen <= 8) {
  320.         if((*incnt)>=inlen)
  321.             i=0;
  322.         else
  323.             i=inbuf[(*incnt)++];
  324.         lzh_getbuf |= i << (8 - lzh_getlen);
  325.         lzh_getlen += 8;
  326.     }
  327.     i = lzh_getbuf;
  328.     lzh_getbuf <<= 1;
  329.     lzh_getlen--;
  330.     return (i < 0);
  331. }
  332.  
  333. short int lzh_getbyte(uchar *inbuf, long *incnt, long inlen)   /* get a byte */
  334. {
  335.     unsigned short i;
  336.  
  337.     while (lzh_getlen <= 8) {
  338.         if((*incnt)>=inlen)
  339.             i=0;
  340.         else
  341.             i=inbuf[(*incnt)++];
  342.         lzh_getbuf |= i << (8 - lzh_getlen);
  343.         lzh_getlen += 8;
  344.     }
  345.     i = lzh_getbuf;
  346.     lzh_getbuf <<= 8;
  347.     lzh_getlen -= 8;
  348.     return i >> 8;
  349. }
  350.  
  351. unsigned lzh_putbuf = 0;
  352. uchar lzh_putlen = 0;
  353.  
  354. /* output c bits */
  355. void lzh_putcode(short int l, unsigned short c, uchar *outbuf, long *outlen)
  356. {
  357.     lzh_putbuf |= c >> lzh_putlen;
  358.     if ((lzh_putlen += l) >= 8) {
  359.         outbuf[(*outlen)++]=(lzh_putbuf >> 8);
  360.         if ((lzh_putlen -= 8) >= 8) {
  361.             outbuf[(*outlen)++]=lzh_putbuf;
  362.             lzh_putlen -= 8;
  363.             lzh_putbuf = c << (l - lzh_putlen);
  364.         } else {
  365.             lzh_putbuf <<= 8;
  366.         }
  367.     }
  368. }
  369.  
  370.  
  371. /* initialize freq tree */
  372.  
  373. void lzh_start_huff()
  374. {
  375.     short int i, j;
  376.  
  377. lzh_getbuf = 0;     /* Added by Digital Dynamics for repeating operations */
  378. lzh_getlen = 0;
  379. lzh_putbuf = 0;
  380. lzh_putlen = 0;
  381.  
  382.     for (i = 0; i < LZH_N_CHAR; i++) {
  383.         lzh_freq[i] = 1;
  384.         lzh_son[i] = i + LZH_T;
  385.         lzh_prnt[i + LZH_T] = i;
  386.     }
  387.     i = 0; j = LZH_N_CHAR;
  388.     while (j <= LZH_R) {
  389.         lzh_freq[j] = lzh_freq[i] + lzh_freq[i + 1];
  390.         lzh_son[j] = i;
  391.         lzh_prnt[i] = lzh_prnt[i + 1] = j;
  392.         i += 2; j++;
  393.     }
  394.     lzh_freq[LZH_T] = 0xffff;
  395.     lzh_prnt[LZH_R] = 0;
  396. }
  397.  
  398.  
  399. /* reconstruct freq tree */
  400.  
  401. void lzh_reconst()
  402. {
  403.     short int i, j, k;
  404.     unsigned short f, l;
  405.  
  406.     /* halven cumulative freq for leaf nodes */
  407.     j = 0;
  408.     for (i = 0; i < LZH_T; i++) {
  409.         if (lzh_son[i] >= LZH_T) {
  410.             lzh_freq[j] = (lzh_freq[i] + 1) / 2;
  411.             lzh_son[j] = lzh_son[i];
  412.             j++;
  413.         }
  414.     }
  415.     /* make a tree : first, connect children nodes */
  416.     for (i = 0, j = LZH_N_CHAR; j < LZH_T; i += 2, j++) {
  417.         k = i + 1;
  418.         f = lzh_freq[j] = lzh_freq[i] + lzh_freq[k];
  419.         for (k = j - 1; f < lzh_freq[k]; k--);
  420.         k++;
  421.         l = (j - k) * 2;
  422.         
  423.         /* movmem() is Turbo-C dependent
  424.            rewritten to memmove() by Kenji */
  425.         
  426.         /* movmem(&lzh_freq[k], &lzh_freq[k + 1], l); */
  427.         (void)memmove(lzh_freq+k+1,lzh_freq+k, l);
  428.         lzh_freq[k] = f;
  429.         /* movmem(&lzh_son[k], &lzh_son[k + 1], l); */
  430.         (void)memmove(lzh_son+k+1,lzh_son+k, l);
  431.         lzh_son[k] = i;
  432.     }
  433.     /* connect parent nodes */
  434.     for (i = 0; i < LZH_T; i++) {
  435.         if ((k = lzh_son[i]) >= LZH_T) {
  436.             lzh_prnt[k] = i;
  437.         } else {
  438.             lzh_prnt[k] = lzh_prnt[k + 1] = i;
  439.         }
  440.     }
  441. }
  442.  
  443. /* update freq tree */
  444.  
  445. void lzh_update(short int c)
  446. {
  447.     short int i, j, k, l;
  448.  
  449.     if (lzh_freq[LZH_R] == MAX_FREQ) {
  450.         lzh_reconst();
  451.     }
  452.     c = lzh_prnt[c + LZH_T];
  453.     do {
  454.         k = ++lzh_freq[c];
  455.  
  456.         /* swap nodes to keep the tree freq-ordered */
  457.         if (k > lzh_freq[l = c + 1]) {
  458.             while (k > lzh_freq[++l]);
  459.             l--;
  460.             lzh_freq[c] = lzh_freq[l];
  461.             lzh_freq[l] = k;
  462.  
  463.             i = lzh_son[c];
  464.             lzh_prnt[i] = l;
  465.             if (i < LZH_T) lzh_prnt[i + 1] = l;
  466.  
  467.             j = lzh_son[l];
  468.             lzh_son[l] = i;
  469.  
  470.             lzh_prnt[j] = c;
  471.             if (j < LZH_T) lzh_prnt[j + 1] = c;
  472.             lzh_son[c] = j;
  473.  
  474.             c = l;
  475.         }
  476.     } while ((c = lzh_prnt[c]) != 0);    /* do it until reaching the root */
  477. }
  478.  
  479. unsigned short lzh_code, lzh_len;
  480.  
  481. void lzh_encode_char(unsigned short c, uchar *outbuf, long *outlen)
  482. {
  483.     unsigned short i;
  484.     short int j, k;
  485.  
  486.     i = 0;
  487.     j = 0;
  488.     k = lzh_prnt[c + LZH_T];
  489.  
  490.     /* search connections from leaf node to the root */
  491.     do {
  492.         i >>= 1;
  493.  
  494.         /*
  495.         if node's address is odd, output 1
  496.         else output 0
  497.         */
  498.         if (k & 1) i += 0x8000;
  499.  
  500.         j++;
  501.     } while ((k = lzh_prnt[k]) != LZH_R);
  502.     lzh_putcode(j, i, outbuf, outlen);
  503.     lzh_code = i;
  504.     lzh_len = j;
  505.     lzh_update(c);
  506. }
  507.  
  508. void lzh_encode_position(unsigned short c, uchar *outbuf, long *outlen)
  509. {
  510.     unsigned short i;
  511.  
  512.     /* output upper 6 bits with encoding */
  513.     i = c >> 6;
  514.     lzh_putcode(lzh_p_len[i], (unsigned)lzh_p_code[i] << 8, outbuf, outlen);
  515.  
  516.     /* output lower 6 bits directly */
  517.     lzh_putcode(6, (c & 0x3f) << 10, outbuf, outlen);
  518. }
  519.  
  520. void lzh_encode_end(uchar *outbuf, long *outlen)
  521. {
  522.     if (lzh_putlen) {
  523.         outbuf[(*outlen)++]=(lzh_putbuf >> 8);
  524.     }
  525. }
  526.  
  527. short int lzh_decode_char(uchar *inbuf, long *incnt, long inlen)
  528. {
  529.     unsigned short c;
  530.  
  531.     c = lzh_son[LZH_R];
  532.  
  533.     /*
  534.      * start searching tree from the root to leaves.
  535.      * choose node #(lzh_son[]) if input bit == 0
  536.      * else choose #(lzh_son[]+1) (input bit == 1)
  537.      */
  538.     while (c < LZH_T) {
  539.         c += lzh_getbit(inbuf,incnt,inlen);
  540.         c = lzh_son[c];
  541.     }
  542.     c -= LZH_T;
  543.     lzh_update(c);
  544.     return c;
  545. }
  546.  
  547. short int lzh_decode_position(uchar *inbuf, long *incnt, long inlen)
  548. {
  549.     unsigned short i, j, c;
  550.  
  551.     /* decode upper 6 bits from given table */
  552.     i = lzh_getbyte(inbuf,incnt,inlen);
  553.     c = (unsigned)lzh_d_code[i] << 6;
  554.     j = lzh_d_len[i];
  555.  
  556.     /* input lower 6 bits directly */
  557.     j -= 2;
  558.     while (j--) {
  559.         i = (i << 1) + lzh_getbit(inbuf,incnt,inlen);
  560.     }
  561.     return c | i & 0x3f;
  562. }
  563.  
  564. /* Compression */
  565.  
  566. /* Encoding/Compressing */
  567. /* Returns length of outbuf */
  568. long LZHCALL lzh_encode(uchar *inbuf, long inlen, uchar *outbuf)
  569. {
  570.     short int  i, c, len, r, s, last_match_length;
  571.     long incnt,outlen; /* textsize=0; */
  572.  
  573. #ifdef LZH_DYNAMIC_BUF
  574.  
  575.     if((lzh_text_buf=(uchar *)MALLOC(LZH_N + LZH_F - 1))==NULL)
  576.         return(-1);
  577.     if((lzh_freq=(unsigned short*)MALLOC((LZH_T + 1)*sizeof(unsigned short)))==NULL) {
  578.         FREE(lzh_text_buf);
  579.         return(-1); }
  580.     if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
  581.         FREE(lzh_text_buf);
  582.         FREE(lzh_freq);
  583.         return(-1); }
  584.     if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
  585.         FREE(lzh_text_buf);
  586.         FREE(lzh_prnt);
  587.         FREE(lzh_freq);
  588.         return(-1); }
  589.     if((lzh_lson=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
  590.         FREE(lzh_text_buf);
  591.         FREE(lzh_prnt);
  592.         FREE(lzh_freq);
  593.         FREE(lzh_son);
  594.         return(-1); }
  595.     if((lzh_rson=(short *)MALLOC((LZH_N + 257)*sizeof(short)))==NULL) {
  596.         FREE(lzh_text_buf);
  597.         FREE(lzh_prnt);
  598.         FREE(lzh_freq);
  599.         FREE(lzh_son);
  600.         FREE(lzh_lson);
  601.         return(-1); }
  602.     if((lzh_dad=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
  603.         FREE(lzh_text_buf);
  604.         FREE(lzh_prnt);
  605.         FREE(lzh_freq);
  606.         FREE(lzh_son);
  607.         FREE(lzh_lson);
  608.         FREE(lzh_rson);
  609.         return(-1); }
  610. #endif
  611.  
  612.     incnt=0;
  613.     memcpy(outbuf,&inlen,sizeof(inlen));
  614.     outlen=sizeof(inlen);
  615.     if(!inlen) {
  616. #ifdef LZH_DYNAMIC_BUF
  617.         FREE(lzh_text_buf);
  618.         FREE(lzh_prnt);
  619.         FREE(lzh_freq);
  620.         FREE(lzh_son);
  621.         FREE(lzh_lson);
  622.         FREE(lzh_rson);
  623.         FREE(lzh_dad);
  624. #endif
  625.         return(outlen); }
  626.     lzh_start_huff();
  627.     lzh_init_tree();
  628.     s = 0;
  629.     r = LZH_N - LZH_F;
  630.     for (i = s; i < r; i++)
  631.         lzh_text_buf[i] = ' ';
  632.     for (len = 0; len < LZH_F && incnt<inlen; len++)
  633.         lzh_text_buf[r + len] = inbuf[incnt++];
  634.     /* textsize = len; */
  635.     for (i = 1; i <= LZH_F; i++)
  636.         lzh_insert_node(r - i);
  637.     lzh_insert_node(r);
  638.     do {
  639.         if (lzh_match_length > len)
  640.             lzh_match_length = len;
  641.         if (lzh_match_length <= LZH_THRESHOLD) {
  642.             lzh_match_length = 1;
  643.             lzh_encode_char(lzh_text_buf[r],outbuf,&outlen);
  644.         } else {
  645.             lzh_encode_char(255 - LZH_THRESHOLD + lzh_match_length
  646.                 ,outbuf,&outlen);
  647.             lzh_encode_position(lzh_match_position
  648.                 ,outbuf,&outlen);
  649.         }
  650.         last_match_length = lzh_match_length;
  651.         for (i = 0; i < last_match_length && incnt<inlen; i++) {
  652.             lzh_delete_node(s);
  653.             c=inbuf[incnt++];
  654.             lzh_text_buf[s] = c;
  655.             if (s < LZH_F - 1)
  656.                 lzh_text_buf[s + LZH_N] = c;
  657.             s = (s + 1) & (LZH_N - 1);
  658.             r = (r + 1) & (LZH_N - 1);
  659.             lzh_insert_node(r);
  660.         }
  661. /***
  662.         if ((textsize += i) > printcount) {
  663.             printf("%12ld\r", textsize);
  664.             printcount += 1024;
  665.         }
  666. ***/
  667.         while (i++ < last_match_length) {
  668.             lzh_delete_node(s);
  669.             s = (s + 1) & (LZH_N - 1);
  670.             r = (r + 1) & (LZH_N - 1);
  671.             if (--len) lzh_insert_node(r);
  672.         }
  673.     } while (len > 0);
  674.     lzh_encode_end(outbuf,&outlen);
  675. /*
  676.     printf("input: %ld (%ld) bytes\n", inlen,textsize);
  677.     printf("output: %ld bytes\n", outlen);
  678.     printf("output/input: %.3f\n", (double)outlen / inlen);
  679. */
  680.  
  681. #ifdef LZH_DYNAMIC_BUF
  682.     FREE(lzh_text_buf);
  683.     FREE(lzh_prnt);
  684.     FREE(lzh_freq);
  685.     FREE(lzh_son);
  686.     FREE(lzh_lson);
  687.     FREE(lzh_rson);
  688.     FREE(lzh_dad);
  689. #endif
  690.  
  691.     return(outlen);
  692. }
  693.  
  694. /* Decoding/Uncompressing */
  695. /* Returns length of outbuf */
  696. long LZHCALL lzh_decode(uchar *inbuf, long inlen, uchar *outbuf)
  697. {
  698.     short int  i, j, k, r, c;
  699.     unsigned long int  count;
  700.     long incnt,textsize;
  701.  
  702. #ifdef LZH_DYNAMIC_BUF
  703.  
  704.     if((lzh_text_buf=(uchar *)MALLOC((LZH_N + LZH_F - 1)*2))==NULL)
  705.         return(-1);
  706.     if((lzh_freq=(unsigned short *)MALLOC((LZH_T + 1)*sizeof(unsigned short)))
  707.         ==NULL) {
  708.         FREE(lzh_text_buf);
  709.         return(-1); }
  710.     if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
  711.         FREE(lzh_text_buf);
  712.         FREE(lzh_freq);
  713.         return(-1); }
  714.     if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
  715.         FREE(lzh_text_buf);
  716.         FREE(lzh_prnt);
  717.         FREE(lzh_freq);
  718.         return(-1); }
  719.  
  720. #endif
  721.  
  722.     incnt=0;
  723.     memcpy(&textsize,inbuf,sizeof(textsize));
  724.     incnt+=sizeof(textsize);
  725.     if (textsize == 0) {
  726. #ifdef LZH_DYNAMIC_BUF
  727.         FREE(lzh_text_buf);
  728.         FREE(lzh_prnt);
  729.         FREE(lzh_freq);
  730.         FREE(lzh_son);
  731. #endif
  732.         return(textsize); }
  733.     lzh_start_huff();
  734.     for (i = 0; i < LZH_N - LZH_F; i++)
  735.         *(lzh_text_buf+i) = ' ';
  736.     r = LZH_N - LZH_F;
  737.     for (count = 0; count < textsize; ) {
  738.         c = lzh_decode_char(inbuf,&incnt,inlen);
  739.         if (c < 256) {
  740.             outbuf[count]=c;
  741. #if 0
  742.             if(r>(LZH_N + LZH_F - 1) || r<0) {
  743.                 printf("Overflow! (%d)\n",r);
  744.                 getch();
  745.                 exit(-1); }
  746. #endif
  747.             *(lzh_text_buf+r) = c;
  748.             r++;
  749.             r &= (LZH_N - 1);
  750.             count++;
  751.         } else {
  752.             i = (r - lzh_decode_position(inbuf,&incnt,inlen) - 1)
  753.                 & (LZH_N - 1);
  754.             j = c - 255 + LZH_THRESHOLD;
  755.             for (k = 0; k < j && count<textsize; k++) {
  756.                 c = lzh_text_buf[(i + k) & (LZH_N - 1)];
  757.                 outbuf[count]=c;
  758. #if 0
  759.                 if(r>(LZH_N + LZH_F - 1) || r<0) {
  760.                     printf("Overflow! (%d)\n",r);
  761.                     exit(-1); }
  762. #endif
  763.                 *(lzh_text_buf+r) = c;
  764.                 r++;
  765.                 r &= (LZH_N - 1);
  766.                 count++;
  767.             }
  768.         }
  769.     }
  770. /***
  771.     printf("%12ld\n", count);
  772. ***/
  773.  
  774. #ifdef LZH_DYNAMIC_BUF
  775.     FREE(lzh_text_buf);
  776.     FREE(lzh_prnt);
  777.     FREE(lzh_freq);
  778.     FREE(lzh_son);
  779. #endif
  780.  
  781. return(count);
  782. }
  783.  
  784.  
  785.