home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 2 BBS / 02-BBS.zip / XGRP_000.SZH / GRPLZSS.C < prev    next >
C/C++ Source or Header  |  1991-08-21  |  21KB  |  793 lines
  1. #pragma optimize("",off)
  2.  
  3. /**************************************************************
  4.     lzhuf.c
  5.     written by Haruyasu Yoshizaki 1988/11/20
  6.     some minor changes 1989/04/06
  7.     comments translated by Haruhiko Okumura 1989/04/07
  8.     This stuff is pretty much the original article, but
  9.     M. Kimes hacked on it in June of 1990 (and again in May 1991)
  10.     Screwed with everything to work with XBBS msg bases
  11. **************************************************************/
  12.  
  13. #include "xgroup.h"
  14.  
  15. char * _fastcall unpack_msg (char **hold);
  16. char * _fastcall pack_msg (char *hold,XMSG *msg);
  17.  
  18. static int  _fastcall Encode (void);
  19. static int  _fastcall Decode (void);
  20. static int  _fastcall GetBit (void);
  21. static int  _fastcall GetByte (void);
  22. static void _fastcall InitTree (void);            /* initialize trees */
  23. static void _fastcall InsertNode (int r);         /* insert to tree */
  24. static void _fastcall DeleteNode (int p);         /* remove from tree */
  25. static void _fastcall StartHuff (void);           /* init tree */
  26. static void _fastcall EncodeChar (unsigned c);
  27. static void _fastcall EncodePosition (unsigned c);
  28. static void _fastcall EncodeEnd (void);
  29. static int  _fastcall DecodeChar (void);
  30. static int  _fastcall DecodePosition (void);
  31. static void _fastcall Putcode (int l, unsigned c);
  32. static void _fastcall Lupdate (int c);
  33. static int  _fastcall alloc_stuff (void);
  34. static void _fastcall free_stuff (void);
  35.  
  36. /********** LZSS compression **********/
  37.  
  38. #define N            4096        /* buffer size */
  39. #define F            60          /* lookahead buffer size */
  40. #define THRESHOLD    2
  41. #define NIL          N           /* leaf of tree */
  42.  
  43. static unsigned      getbuf;
  44. static uchar         getlen;
  45. static unsigned      putbuf;
  46. static uchar         putlen;
  47. static unsigned int  bytesdone, bytestodo;
  48. static int           match_position, match_length;
  49. static unsigned char *text_buf;
  50. static int           *lson;
  51. static int           *rson;
  52. static int           *dad;
  53. static char          *inbuf;
  54. static char          *outbuf;
  55. static unsigned int  textsize, codesize;
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63. int _fastcall Encode (void)  { /* compression */
  64.  
  65.     int  i, c, len, r, s, last_match_length;
  66.     unsigned int printcount = 0;
  67.  
  68.  
  69.     if(!alloc_stuff()) {
  70.         printf("\n **Error**  Couldn't allocate encode buffers\n");
  71.         return 0;
  72.     }
  73.     else printf("\x1b[s\x1b[1;1H\x1b[K");
  74.     codesize = bytesdone = textsize = 0;
  75.     StartHuff();
  76.     InitTree();
  77.     s = 0;
  78.     r = N - F;
  79.     for (i = s; i < r; i++) {
  80.         text_buf[i]=0x20;
  81.     }
  82.     for (len = 0; len < F; len++) {
  83.         c = *inbuf;
  84.         if(!c) break;
  85.         inbuf++;
  86.         bytesdone++;
  87.         if(bytesdone > bytestodo) break;
  88.         text_buf[r+len] = c;
  89.     }
  90.     textsize = len;
  91.     for (i = 1; i <= F; i++) InsertNode(r - i);
  92.     InsertNode(r);
  93.     do {
  94.         if (match_length > len)
  95.             match_length = len;
  96.         if (match_length <= THRESHOLD) {
  97.             match_length = 1;
  98.             EncodeChar(text_buf[r]);
  99.         } else {
  100.             EncodeChar(255 - THRESHOLD + match_length);
  101.             EncodePosition(match_position);
  102.         }
  103.         last_match_length = match_length;
  104.         for (i = 0; i < last_match_length; i++) {
  105.             c = *inbuf;
  106.             if(!c) break;
  107.             inbuf++;
  108.             bytesdone++;
  109.             if(bytesdone > bytestodo) break;
  110.             DeleteNode(s);
  111.             text_buf[s] = c;
  112.             if (s < F - 1)
  113.                 text_buf[s + N] = c;
  114.             s = (s + 1) & (N - 1);
  115.             r = (r + 1) & (N - 1);
  116.             InsertNode(r);
  117.         }
  118.         if ((textsize += i) > printcount) {
  119.             printf("\r %u",textsize);
  120.             printcount += 1023;
  121.         }
  122.         while (i++ < last_match_length) {
  123.             DeleteNode(s);
  124.             s = (s + 1) & (N - 1);
  125.             r = (r + 1) & (N - 1);
  126.             if (--len) InsertNode(r);
  127.         }
  128.     } while (len > 0);
  129.     EncodeEnd();
  130.     printf("\r %u bytes -> %u bytes\x1b[u",textsize,codesize);
  131.     free_stuff();
  132.     return 1;
  133. }
  134.  
  135.  
  136.  
  137.  
  138. int _fastcall Decode (void) { /* recover */
  139.  
  140.     int  i, j, k, r, c;
  141.     unsigned int count;
  142.     unsigned int printcount=0;
  143.  
  144.  
  145.     codesize = 0;
  146.     if (textsize < 1024) {
  147.         printf("\n **Error**  Textsize = %u\n",textsize);
  148.         return 0;
  149.     }
  150.  
  151.     if(!alloc_stuff()) {
  152.         printf("\n **Error**  Couldn't allocate decode buffers");
  153.         return 0;
  154.     }
  155.  
  156.     printf("\x1b[s\x1b[1;1H\x1b[K");
  157.  
  158.     StartHuff();
  159.     for (i = 0; i < N - F; i++) text_buf[i] = 0x20;
  160.     r = N - F;
  161.     for (count = 0; count < textsize; ) {
  162.         c = DecodeChar();
  163.         if (c < 256) {
  164.             *outbuf = c;
  165.             outbuf++;
  166.             text_buf[r++] = c;
  167.             r &= (N - 1);
  168.             count++;
  169.         }
  170.         else {
  171.             i = (r - DecodePosition() - 1) & (N - 1);
  172.             j = c - 255 + THRESHOLD;
  173.             for (k = 0; k < j; k++) {
  174.                 c = text_buf[(i + k) & (N - 1)];
  175.                 *outbuf = c;
  176.                 outbuf++;
  177.                 text_buf[r++] = c;
  178.                 r &= (N - 1);
  179.                 count++;
  180.             }
  181.         }
  182.         if (count > printcount) {
  183.             printf("\r %u",count);
  184.             printcount += 1023;
  185.         }
  186.     }
  187.     printf("\x1b[u");
  188.     free_stuff();
  189.     return 1;
  190. }
  191.  
  192.  
  193. static void _fastcall InitTree (void) { /* initialize trees */
  194.  
  195.     int  i;
  196.  
  197.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;    /* root */
  198.     for (i = 0; i < N; i++) dad[i] = NIL;                /* node */
  199. }
  200.  
  201.  
  202. static void _fastcall InsertNode (int r) { /* insert to tree */
  203.  
  204.     int  i, p, cmp;
  205.     unsigned char  *key;
  206.     unsigned c;
  207.  
  208.  
  209.     cmp = 1;
  210.     key = &text_buf[r];
  211.     p = N + 1 + key[0];
  212.     rson[r] = lson[r] = NIL;
  213.     match_length = 0;
  214.     for ( ; ; ) {
  215.         if (cmp >= 0) {
  216.             if (rson[p] != NIL) p = rson[p];
  217.             else {
  218.                 rson[p] = r;
  219.                 dad[r] = p;
  220.                 return;
  221.             }
  222.         }
  223.         else {
  224.             if (lson[p] != NIL) p = lson[p];
  225.             else {
  226.                 lson[p] = r;
  227.                 dad[r] = p;
  228.                 return;
  229.             }
  230.         }
  231.         for (i = 1; i < F; i++) {
  232.             if ((cmp = key[i] - text_buf[p + i]) != 0) break;
  233.         }
  234.         if (i > THRESHOLD) {
  235.             if (i > match_length) {
  236.                 match_position = ((r - p) & (N - 1)) - 1;
  237.                 if ((match_length = i) >= F) break;
  238.             }
  239.             if (i == match_length) {
  240.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  241.                     match_position = c;
  242.                 }
  243.             }
  244.         }
  245.     }
  246.     dad[r] = dad[p];
  247.     lson[r] = lson[p];
  248.     rson[r] = rson[p];
  249.     dad[lson[p]] = r;
  250.     dad[rson[p]] = r;
  251.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  252.     else lson[dad[p]] = r;
  253.     dad[p] = NIL; /* remove p */
  254. }
  255.  
  256.  
  257. static void _fastcall DeleteNode (int p) {  /* remove from tree */
  258.  
  259.     int  q;
  260.  
  261.  
  262.     if (dad[p] == NIL) return;         /* not registered */
  263.     if (rson[p] == NIL) q = lson[p];
  264.     else if (lson[p] == NIL) q = rson[p];
  265.     else {
  266.         q = lson[p];
  267.         if (rson[q] != NIL) {
  268.             do {
  269.                 q = rson[q];
  270.             } while (rson[q] != NIL);
  271.             rson[dad[q]] = lson[q];
  272.             dad[lson[q]] = dad[q];
  273.             lson[q] = lson[p];
  274.             dad[lson[p]] = q;
  275.         }
  276.         rson[q] = rson[p];
  277.         dad[rson[p]] = q;
  278.     }
  279.     dad[q] = dad[p];
  280.     if (rson[dad[p]] == p) rson[dad[p]] = q;
  281.     else lson[dad[p]] = q;
  282.     dad[p] = NIL;
  283. }
  284.  
  285. /* Huffman coding */
  286.  
  287. #define N_CHAR   (256 - THRESHOLD + F)
  288.                  /* kinds of characters (character code = 0..N_CHAR-1) */
  289. #define T        (N_CHAR * 2 - 1)    /* size of table */
  290. #define R        (T - 1)         /* position of root */
  291. #define MAX_FREQ 0x8000      /* updates tree when the */
  292.                  /* root frequency comes to this value. */
  293.  
  294.  
  295. /* table for encoding and decoding the upper 6 bits of position */
  296.  
  297. /* for encoding */
  298. uchar p_len[64] = {
  299.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  300.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  301.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  302.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  303.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  304.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  305.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  306.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  307. };
  308.  
  309. uchar p_code[64] = {
  310.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  311.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  312.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  313.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  314.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  315.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  316.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  317.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  318. };
  319.  
  320. /* for decoding */
  321. uchar d_code[256] = {
  322.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  323.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  324.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  325.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  326.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  327.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  328.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  329.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  330.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  331.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  332.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  333.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  334.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  335.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  336.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  337.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  338.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  339.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  340.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  341.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  342.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  343.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  344.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  345.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  346.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  347.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  348.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  349.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  350.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  351.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  352.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  353.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  354. };
  355.  
  356. uchar d_len[256] = {
  357.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  358.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  359.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  360.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  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.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  365.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  366.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  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.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  373.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  374.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  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.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  379.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  380.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  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.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  385.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  386.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  387.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  388.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  389. };
  390.  
  391. unsigned freq[T + 1]; /* frequency table */
  392.  
  393. int prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
  394.             /* elements [T..T + N_CHAR - 1] which are used to get */
  395.             /* the positions of leaves corresponding to the codes. */
  396.  
  397. int son[T]; /* pointers to child nodes (son[], son[] + 1) */
  398.  
  399.  
  400. static int _fastcall GetBit (void) {    /* get one bit */
  401.  
  402.     unsigned i;
  403.  
  404.     while (getlen <= 8) {
  405.         if ((int)(i = (int)*inbuf) < 0) i = 0;
  406.         inbuf++;
  407.         bytesdone++;
  408.         getbuf |= i << (8 - getlen);
  409.         getlen += 8;
  410.     }
  411.     i = getbuf;
  412.     getbuf <<= 1;
  413.     getlen--;
  414.     return ((i & 0x8000) >> 15);
  415. }
  416.  
  417. static int _fastcall GetByte (void) {   /* get one byte */
  418.  
  419.     unsigned i;
  420.  
  421.     while (getlen <= 8) {
  422.         if ((int)(i = (int)*inbuf) < 0) i = 0;
  423.         inbuf++;
  424.         bytesdone++;
  425.         getbuf |= i << (8 - getlen);
  426.         getlen += 8;
  427.     }
  428.     i = getbuf;
  429.     getbuf <<= 8;
  430.     getlen -= 8;
  431.     return ((i & 0xff00) >> 8);
  432. }
  433.  
  434.  
  435.  
  436. static void _fastcall Putcode (int l, unsigned c) {    /* output c bits of code */
  437.  
  438.     putbuf |= c >> putlen;
  439.     if ((putlen += l) >= 8) {
  440.         *outbuf = (putbuf >> 8);
  441.         outbuf++;
  442.         if ((putlen -= 8) >= 8) {
  443.             *outbuf = putbuf;
  444.             outbuf++;
  445.             codesize += 2;
  446.             putlen -= 8;
  447.             putbuf = c << (l - putlen);
  448.         }
  449.         else {
  450.             putbuf <<= 8;
  451.             codesize++;
  452.         }
  453.     }
  454. }
  455.  
  456.  
  457. /* initialization of tree */
  458.  
  459. static void _fastcall StartHuff (void) {
  460.  
  461.     int i, j;
  462.  
  463.     for (i = 0; i < N_CHAR; i++) {
  464.         freq[i] = 1;
  465.         son[i] = i + T;
  466.         prnt[i + T] = i;
  467.     }
  468.     i = 0; j = N_CHAR;
  469.     while (j <= R) {
  470.         freq[j] = freq[i] + freq[i + 1];
  471.         son[j] = i;
  472.         prnt[i] = prnt[i + 1] = j;
  473.         i += 2; j++;
  474.     }
  475.     freq[T] = 0xffff;
  476.     prnt[R] = 0;
  477.     putbuf = getbuf = 0;
  478.     putlen = getlen = 0;
  479. }
  480.  
  481.  
  482. /* reconstruction of tree */
  483.  
  484. static void _fastcall reconst (void) {
  485.  
  486.     int i, j, k;
  487.     unsigned f, l;
  488.  
  489.     /* collect leaf nodes in the first half of the table */
  490.     /* and replace the freq by (freq + 1) / 2. */
  491.     j = 0;
  492.     for (i = 0; i < T; i++) {
  493.         if (son[i] >= T) {
  494.             freq[j] = (freq[i] + 1) / 2;
  495.             son[j] = son[i];
  496.             j++;
  497.         }
  498.     }
  499.     /* begin constructing tree by connecting sons */
  500.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  501.         k = i + 1;
  502.         f = freq[j] = freq[i] + freq[k];
  503.         for (k = j - 1; f < freq[k]; k--);
  504.         k++;
  505.         l = (j - k) * 2;
  506.         memmove(&freq[k + 1], &freq[k], l);
  507.         freq[k] = f;
  508.         memmove(&son[k + 1], &son[k], l);
  509.         son[k] = i;
  510.     }
  511.     /* connect prnt */
  512.     for (i = 0; i < T; i++) {
  513.         if ((k = son[i]) >= T) {
  514.             prnt[k] = i;
  515.         }
  516.         else {
  517.             prnt[k] = prnt[k + 1] = i;
  518.         }
  519.     }
  520. }
  521.  
  522.  
  523. /* increment frequency of given code by one, and update tree */
  524.  
  525. static void _fastcall Lupdate (int c) {
  526.  
  527.     int i, j, k, l;
  528.  
  529.     if (freq[R] == MAX_FREQ) {
  530.         reconst();
  531.     }
  532.     c = prnt[c + T];
  533.     do {
  534.         k = ++freq[c];
  535.  
  536.         /* if the order is disturbed, exchange nodes */
  537.         if (k > freq[l = c + 1]) {
  538.             while (k > freq[++l]);
  539.             l--;
  540.             freq[c] = freq[l];
  541.             freq[l] = k;
  542.  
  543.             i = son[c];
  544.             prnt[i] = l;
  545.             if (i < T) prnt[i + 1] = l;
  546.  
  547.             j = son[l];
  548.             son[l] = i;
  549.  
  550.             prnt[j] = c;
  551.             if (j < T) prnt[j + 1] = c;
  552.             son[c] = j;
  553.  
  554.             c = l;
  555.         }
  556.     } while ((c = prnt[c]) != 0); /* repeat up to root */
  557. }
  558.  
  559. unsigned code, len;
  560.  
  561. static void _fastcall EncodeChar (unsigned c) {
  562.  
  563.     unsigned i;
  564.     int j, k;
  565.  
  566.     i = 0;
  567.     j = 0;
  568.     k = prnt[c + T];
  569.  
  570.     /* travel from leaf to root */
  571.     do {
  572.         i >>= 1;
  573.  
  574.         /* if node's address is odd-numbered, choose bigger brother node */
  575.         if (k & 1) i += 0x8000;
  576.  
  577.         j++;
  578.     } while ((k = prnt[k]) != R);
  579.     Putcode(j, i);
  580.     code = i;
  581.     len = j;
  582.     Lupdate(c);
  583. }
  584.  
  585. static void _fastcall EncodePosition (unsigned c) {
  586.  
  587.     unsigned i;
  588.  
  589.     /* output upper 6 bits by table lookup */
  590.     i = c >> 6;
  591.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  592.  
  593.     /* output lower 6 bits verbatim */
  594.     Putcode(6, (c & 0x3f) << 10);
  595. }
  596.  
  597. static void _fastcall EncodeEnd (void) {
  598.  
  599.     if (putlen) {
  600.         *outbuf = (putbuf >> 8);
  601.         outbuf++;
  602.         codesize++;
  603.     }
  604. }
  605.  
  606. static int _fastcall DecodeChar (void) {
  607.  
  608.     unsigned c;
  609.  
  610.     c = son[R];
  611.  
  612.     /* travel from root to leaf, */
  613.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  614.     /* the bigger (son[]+1} if 1 */
  615.     while (c < T) {
  616.         c += GetBit();
  617.         c = son[c];
  618.  
  619.     }
  620.     c -= T;
  621.     Lupdate(c);
  622.     return c;
  623. }
  624.  
  625. static int _fastcall DecodePosition (void) {
  626.  
  627.     unsigned i, j, c;
  628.  
  629.     /* recover upper 6 bits from table */
  630.     i = GetByte();
  631.     c = (unsigned)d_code[i] << 6;
  632.     j = d_len[i];
  633.  
  634.     /* read lower 6 bits verbatim */
  635.     j -= 2;
  636.     while (j--) {
  637.         i = (i << 1) + GetBit();
  638.     }
  639.     return (c | (i & 0x3f));
  640. }
  641.  
  642.  
  643.  
  644. char * _fastcall unpack_msg (char **hold) {
  645.  
  646.     char *pp;
  647.     static char *tempbuf;
  648.  
  649.  
  650.     pp = *hold;
  651.     *hold = NULL;
  652.     textsize = (word)atol(pp);
  653.     if(textsize < 1024) {
  654.         printf("\n Error in textsize (%u)\n",textsize);
  655.         my_free(pp);
  656.         return NULL;
  657.     }
  658.     tempbuf = pp;
  659.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  660.     if(*tempbuf == '\r') tempbuf++;
  661.     else goto Grunged;
  662.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  663.     if(*tempbuf == '\r') tempbuf++;
  664.     else goto Grunged;
  665.     while(*tempbuf && *tempbuf != '\r') tempbuf++;
  666.     if(*tempbuf == '\r') tempbuf++;
  667.     else {
  668. Grunged:
  669.         printf("\n Grunged msg \n");
  670.         my_free(pp);
  671.         return NULL;
  672.     }
  673.     inbuf = tempbuf;
  674.     outbuf = (char *)malloc((unsigned)(sizeof(char) * textsize)+256);
  675.     if(!outbuf) {
  676.         printf("\n Can't allocate memory to uncompress \n");
  677.         my_free(pp);
  678.         return NULL;
  679.     }
  680.     tempbuf = outbuf;
  681.     if(!Decode()){
  682.         my_free(tempbuf);
  683.         tempbuf = NULL;
  684.     }
  685.     else tempbuf[textsize] = 0;
  686.     my_free(pp);
  687.     *hold = tempbuf;
  688.     return tempbuf;
  689. }
  690.  
  691.  
  692.  
  693. char * _fastcall pack_msg (char *hold,XMSG *msg) {
  694.  
  695.     char *tempo;
  696.     char lastmsgid[80]="";
  697.     char lastreply[80]="";
  698.     unsigned int temp;
  699.     static char *tempbuf;
  700.     char textlen[18];
  701.  
  702.  
  703.   if(strlen(hold) < 1024) return NULL;    /* Too small to jack with */
  704.   if(tempo = strstr(hold,"\01MSGID:")) {
  705.     strncpy(lastmsgid,&tempo[7],80);
  706.     lastmsgid[79] = 0;
  707.     tempo = strchr(lastmsgid,'\r');
  708.     if(tempo) *tempo = 0;
  709.     lstrip(lastmsgid);
  710.     rstrip(lastmsgid);
  711.   }
  712.   else *lastmsgid = 0;
  713.   if(tempo = strstr(hold,"\01REPLY:")) {
  714.     strncpy(lastreply,&tempo[7],80);
  715.     lastreply[79] = 0;
  716.     tempo=strchr(lastreply,'\r');
  717.     if(tempo) *tempo = 0;
  718.     lstrip(lastreply);
  719.     rstrip(lastreply);
  720.   }
  721.   else *lastreply = 0;
  722.   textsize = strlen(hold);
  723.   bytestodo = textsize;
  724.   outbuf = (char *)malloc((sizeof(char)*textsize)+256);
  725.   if(!outbuf) {
  726.     printf("\n Can't allocate memory to compress \n");
  727.     my_free(hold);
  728.     return NULL;
  729.   }
  730.   tempbuf = outbuf;
  731.   inbuf = hold;
  732.   if(!Encode()) {
  733.     my_free(tempbuf);
  734.     my_free(hold);
  735.     return NULL;
  736.   }
  737.   sprintf(textlen,"%01u",bytestodo);
  738.   my_free(hold);
  739.   hold = (char *)malloc(((sizeof(char) * codesize) + 2) + (strlen(lastmsgid) + 1)+
  740.     (strlen(lastmsgid) + 1) + (strlen(textlen) + 1));
  741.   if(!hold) {
  742.     printf("\n Can't allocate memory to compress \n");
  743.     my_free(tempbuf);
  744.     return NULL;
  745.   }
  746.   sprintf(hold,"%s\r%s\r%s\r",textlen,lastmsgid,lastreply);
  747.   temp = strlen(hold);
  748.   tempo = &hold[temp];
  749.   memcpy(tempo,tempbuf,codesize);
  750.   my_free(tempbuf);
  751.   msg->length = temp + codesize + 1;
  752.   return hold;
  753. }
  754.  
  755.  
  756.  
  757. static int _fastcall alloc_stuff (void) {
  758.  
  759.     text_buf = (unsigned char *)malloc(sizeof(char) * (N + F - 1));
  760.     if(!text_buf) return 0;
  761.     lson = (int *)malloc(sizeof(int) * (N + 1));
  762.     if(!lson) {
  763.         my_free(text_buf);
  764.         return 0;
  765.     }
  766.     rson = (int *)malloc(sizeof(int) * (N+257));
  767.     if(!rson) {
  768.         my_free(text_buf);
  769.         my_free(lson);
  770.         return 0;
  771.     }
  772.     dad = (int *)malloc(sizeof(int) * (N+1));
  773.     if(!dad) {
  774.         my_free(text_buf);
  775.         my_free(lson);
  776.         my_free(rson);
  777.         return 0;
  778.     }
  779.     return 1;
  780. }
  781.  
  782.  
  783.  
  784. void _fastcall free_stuff (void) {
  785.  
  786.     my_free(text_buf);
  787.     my_free(lson);
  788.     my_free(rson);
  789.     my_free(dad);
  790. }
  791.  
  792. #pragma optimize("",on)
  793.