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