home *** CD-ROM | disk | FTP | other *** search
/ Computer Club Elmshorn Atari PD / CCE_PD.iso / pc / 0400 / CCE_0483.ZIP / CCE_0483.PD / LZH_SOUR.CE / LHUF5.C < prev    next >
C/C++ Source or Header  |  1992-04-10  |  23KB  |  962 lines
  1. #include "lh5.h"
  2. #include <stdlib.h>
  3. #include <string.h>  /* memmove() */
  4. #ifdef __TOS__
  5.  #include "goodputc.h"
  6. #endif
  7.  
  8. /* #define _lhufs_ */
  9.  
  10. extern uchar text_buf[DICSIZ];
  11. #define buffer text_buf
  12. /* static uchar buffer[DICSIZ]; */
  13.  
  14.  
  15.  
  16. #define CRCPOLY  0xA001  /* ANSI CRC-16 */
  17.                          /* CCITT: 0x8408 */
  18. #define UPDATE_CRC(c) \
  19.     crc = crctable[(crc ^ (c)) & 0xFF] ^ (crc >> CHAR_BIT)
  20.  
  21. extern FILE *infile, *outfile;
  22. extern uint crc;
  23. ulong  origsize,compsize;
  24. #ifdef _lhufs_
  25.  uint   bitbuf;
  26.  extern uint   subbitbuf;
  27.  extern int    bitcount;
  28.  extern ulong  origsize,compsize;
  29. #else
  30.  uint          bitbuf;
  31.  uint             subbitbuf;
  32.  int              bitcount;
  33.  ulong         origsize,compsize;
  34. #endif
  35. extern uchar flg_n;
  36.  
  37. ushort crctable[UCHAR_MAX + 1];
  38. uint  subbitbuf;
  39. int   bitcount;
  40.  
  41. static void error(char *fmt, ...)
  42. {
  43.     va_list args;
  44.  
  45.     va_start(args, fmt);
  46.     putc('\n', stderr);
  47.     vfprintf(stderr, fmt, args);
  48.     putc('\n', stderr);
  49.     va_end(args);
  50.     exit(EXIT_FAILURE);
  51. }
  52.  
  53. void make_crctable(void)
  54. {
  55.     uint i, j, r;
  56.     static int crc_ready = 0;
  57.     if (crc_ready == 0) {
  58.  
  59.     for (i = 0; i <= UCHAR_MAX; i++) {
  60.         r = i;
  61.         for (j = 0; j < CHAR_BIT; j++)
  62.             if (r & 1) r = (r >> 1) ^ CRCPOLY;
  63.             else       r >>= 1;
  64.         crctable[i] = r;
  65.     }
  66.     crc_ready=1;
  67.     }
  68. }
  69.  
  70. void fillbuf(int n)  /* Shift bitbuf n bits left, read n bits */
  71. {
  72.     bitbuf <<= n;
  73.     while (n > bitcount) {
  74.         bitbuf |= subbitbuf << (n -= bitcount);
  75.         if (compsize != 0) {
  76.             compsize--;  subbitbuf = (uchar) getc(infile);
  77.         } else subbitbuf = 0;
  78.         bitcount = CHAR_BIT;
  79.     }
  80.     bitbuf |= subbitbuf >> (bitcount -= n);
  81. }
  82.  
  83.  
  84. static uint getbits(int n)
  85. {
  86.     uint x;
  87.  
  88.     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
  89.     return x;
  90. }
  91.  
  92. static void putbits(int n, uint x)  /* Write rightmost n bits of x */
  93. {
  94.     if (n < bitcount) {
  95.         subbitbuf |= x << (bitcount -= n);
  96.     } else {
  97.         if (compsize < origsize) {
  98.             if (putc(subbitbuf | (x >> (n -= bitcount)), outfile) == EOF) error("Unable to write");
  99.             compsize++;
  100.         } else unpackable = 1;
  101.         if (n < CHAR_BIT) {
  102.             subbitbuf = x << (bitcount = CHAR_BIT - n);
  103.         } else {
  104.             if (compsize < origsize) {
  105.                 if (putc(x >> (n - CHAR_BIT), outfile) == EOF) error("Unable to write");
  106.                 compsize++;
  107.             } else unpackable = 1;
  108.             subbitbuf = x << (bitcount = 2 * CHAR_BIT - n);
  109.         }
  110.     }
  111. }
  112.  
  113. int fread_crc(uchar *p, int n, FILE *f)
  114. {
  115.     int i;
  116.  
  117.     i = n = fread(p, 1, n, f);  origsize += n;
  118.     while (--i >= 0) UPDATE_CRC(*p++);
  119.     return n;
  120. }
  121.  
  122. static void fwrite_crc(uchar *p, int n, FILE *f)
  123. {
  124.     if (f!= NULL) if (fwrite(p, 1, n, f) < n) error("Unable to write");
  125.     while (--n >= 0) UPDATE_CRC(*p++);
  126. }
  127.  
  128. static void init_getbits(void)
  129. {
  130.     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
  131.     fillbuf(BITBUFSIZ);
  132. }
  133.  
  134. static void init_putbits(void)
  135. {
  136.     bitcount = CHAR_BIT;  subbitbuf = 0;
  137. }
  138.  
  139. /* --------------------------- End of IO.C --------------------------- */
  140.  
  141. /***********************************************************
  142.     decode.c
  143. ***********************************************************/
  144.  
  145.  
  146.  
  147. /* ----------------------Start of huf.c ------------------------------- */
  148.  
  149. /***********************************************************
  150.     huf.c -- static Huffman
  151. ***********************************************************/
  152.  
  153. #define NP (DICBIT + 1)
  154. #define NT (CODE_BIT + 3)
  155. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  156. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  157. #if NT > NP
  158.     #define NPT NT
  159. #else
  160.     #define NPT NP
  161. #endif
  162.  
  163. extern ushort left[2 * NC - 1], right[2 * NC - 1];
  164. extern uchar *buf, c_len[NC], pt_len[NPT];
  165. extern int   bufsiz = 0, blocksize;
  166. extern ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  167.               p_freq[2 * NP - 1], pt_table[256], pt_code[NPT],
  168.               t_freq[2 * NT - 1];
  169. extern ushort dad[4096];
  170. #define c_table dad
  171.  
  172. /***** encoding *****/
  173.  
  174. void count_t_freq(void)
  175. {
  176.     int i, k, n, count;
  177.  
  178.     for (i = 0; i < NT; i++) t_freq[i] = 0;
  179.     n = NC;
  180.     while (n > 0 && c_len[n - 1] == 0) n--;
  181.     i = 0;
  182.     while (i < n) {
  183.         k = c_len[i++];
  184.         if (k == 0) {
  185.             count = 1;
  186.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  187.             if (count <= 2) t_freq[0] += count;
  188.             else if (count <= 18) t_freq[1]++;
  189.             else if (count == 19) {  t_freq[0]++;  t_freq[1]++;  }
  190.             else t_freq[2]++;
  191.         } else t_freq[k + 2]++;
  192.     }
  193. }
  194.  
  195. void write_pt_len(int n, int nbit, int i_special)
  196. {
  197.     int i, k;
  198.  
  199.     while (n > 0 && pt_len[n - 1] == 0) n--;
  200.     putbits(nbit, n);
  201.     i = 0;
  202.     while (i < n) {
  203.         k = pt_len[i++];
  204.         if (k <= 6) putbits(3, k);
  205.         else putbits(k - 3, (1U << (k - 3)) - 2);
  206.         if (i == i_special) {
  207.             while (i < 6 && pt_len[i] == 0) i++;
  208.             putbits(2, (i - 3) & 3);
  209.         }
  210.     }
  211. }
  212.  
  213. void write_c_len(void)
  214. {
  215.     int i, k, n, count;
  216.  
  217.     n = NC;
  218.     while (n > 0 && c_len[n - 1] == 0) n--;
  219.     putbits(CBIT, n);
  220.     i = 0;
  221.     while (i < n) {
  222.         k = c_len[i++];
  223.         if (k == 0) {
  224.             count = 1;
  225.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  226.             if (count <= 2) {
  227.                 for (k = 0; k < count; k++)
  228.                     putbits(pt_len[0], pt_code[0]);
  229.             } else if (count <= 18) {
  230.                 putbits(pt_len[1], pt_code[1]);
  231.                 putbits(4, count - 3);
  232.             } else if (count == 19) {
  233.                 putbits(pt_len[0], pt_code[0]);
  234.                 putbits(pt_len[1], pt_code[1]);
  235.                 putbits(4, 15);
  236.             } else {
  237.                 putbits(pt_len[2], pt_code[2]);
  238.                 putbits(CBIT, count - 20);
  239.             }
  240.         } else putbits(pt_len[k + 2], pt_code[k + 2]);
  241.     }
  242. }
  243.  
  244. void encode_c(int c)
  245. {
  246.     putbits(c_len[c], c_code[c]);
  247. }
  248.  
  249. void encode_p(uint p)
  250. {
  251.     uint c, q;
  252.  
  253.     c = 0;  q = p;  while (q) {  q >>= 1;  c++;  }
  254.     putbits(pt_len[c], pt_code[c]);
  255.     if (c > 1) putbits(c - 1, p & (0xFFFFU >> (17 - c)));
  256. }
  257.  
  258. void send_block(void)
  259. {
  260.     uint i, k, flags, root, pos, size;
  261.  
  262.     root = make_tree(NC, c_freq, c_len, c_code);
  263.     size = c_freq[root];  putbits(16, size);
  264.     if (root >= NC) {
  265.         count_t_freq();
  266.         root = make_tree(NT, t_freq, pt_len, pt_code);
  267.         if (root >= NT) {
  268.             write_pt_len(NT, TBIT, 3);
  269.         } else {
  270.             putbits(TBIT, 0);  putbits(TBIT, root);
  271.         }
  272.         write_c_len();
  273.     } else {
  274.         putbits(TBIT, 0);  putbits(TBIT, 0);
  275.         putbits(CBIT, 0);  putbits(CBIT, root);
  276.     }
  277.     root = make_tree(NP, p_freq, pt_len, pt_code);
  278.     if (root >= NP) {
  279.         write_pt_len(NP, PBIT, -1);
  280.     } else {
  281.         putbits(PBIT, 0);  putbits(PBIT, root);
  282.     }
  283.     pos = 0;
  284.     for (i = 0; i < size; i++) {
  285.         if (i % CHAR_BIT == 0) flags = buf[pos++];  else flags <<= 1;
  286.         if (flags & (1U << (CHAR_BIT - 1))) {
  287.             encode_c(buf[pos++] + (1U << CHAR_BIT));
  288.             k = buf[pos++] << CHAR_BIT;  k += buf[pos++];
  289.             encode_p(k);
  290.         } else encode_c(buf[pos++]);
  291.         if (unpackable) return;
  292.     }
  293.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  294.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  295. }
  296. uint output_pos, output_mask;
  297.  
  298. #ifdef _lhufs_
  299. extern void output5(uint c, uint p);
  300. #else
  301. void output5(uint c, uint p)
  302. {
  303.     static uint cpos;
  304.  
  305.     if ((output_mask >>= 1) == 0) {
  306.         output_mask = 1U << (CHAR_BIT - 1);
  307.         if (output_pos >= bufsiz - 3 * CHAR_BIT) {
  308.             send_block();
  309.             if (unpackable) return;
  310.             output_pos = 0;
  311.         }
  312.         cpos = output_pos++;  buf[cpos] = 0;
  313.     }
  314.     buf[output_pos++] = (uchar) c;  c_freq[c]++;
  315.     if (c >= (1U << CHAR_BIT)) {
  316.         buf[cpos] |= output_mask;
  317.         buf[output_pos++] = (uchar)(p >> CHAR_BIT);
  318.         buf[output_pos++] = (uchar) p;
  319.         c = 0;  while (p) {  p >>= 1;  c++;  }
  320.         p_freq[c]++;
  321.     }
  322. }
  323. #endif
  324. void start_huf(void)
  325. {
  326.     int i;
  327.  
  328.     if (bufsiz == 0) {
  329.         bufsiz = 16 * 1024U;
  330.         while ((buf = malloc(bufsiz)) == NULL) {
  331.             bufsiz = (bufsiz / 10U) * 9U;
  332.             if (bufsiz < 4 * 1024U) error("Out of memory.");
  333.         }
  334.     }
  335.     buf[0] = 0;
  336.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  337.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  338.     output_pos = output_mask = 0;
  339.     init_putbits();
  340. }
  341.  
  342. void end_huf(void)
  343. {
  344.     if (! unpackable) {
  345.         send_block();
  346.         putbits(CHAR_BIT - 1, 0);  /* flush remaining bits */
  347.     }
  348. }
  349.  
  350. /***** decoding *****/
  351.  
  352. static void read_pt_len(int nn, int nbit, int i_special)
  353. {
  354.     int i, c, n;
  355.     uint mask;
  356.  
  357.     n = getbits(nbit);
  358.     if (n == 0) {
  359.         c = getbits(nbit);
  360.         for (i = 0; i < nn; i++) pt_len[i] = 0;
  361.         for (i = 0; i < 256; i++) pt_table[i] = c;
  362.     } else {
  363.         i = 0;
  364.         while (i < n) {
  365.             c = bitbuf >> (BITBUFSIZ - 3);
  366.             if (c == 7) {
  367.                 mask = 1U << (BITBUFSIZ - 1 - 3);
  368.                 while (mask & bitbuf) {  mask >>= 1;  c++;  }
  369.             }
  370.             fillbuf((c < 7) ? 3 : c - 3);
  371.             pt_len[i++] = c;
  372.             if (i == i_special) {
  373.                 c = getbits(2);
  374.                 while (--c >= 0) pt_len[i++] = 0;
  375.             }
  376.         }
  377.         while (i < nn) pt_len[i++] = 0;
  378.         make_table(nn, pt_len, 8, pt_table);
  379.     }
  380. }
  381.  
  382. static void read_c_len(void)
  383. {
  384.     int i, c, n;
  385.     uint mask;
  386.  
  387.     n = getbits(CBIT);
  388.     if (n == 0) {
  389.         c = getbits(CBIT);
  390.         for (i = 0; i < NC; i++) c_len[i] = 0;
  391.         for (i = 0; i < 4096; i++) c_table[i] = c;
  392.     } else {
  393.         i = 0;
  394.         while (i < n) {
  395.             c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  396.             if (c >= NT) {
  397.                 mask = 1U << (BITBUFSIZ - 1 - 8);
  398.                 do {
  399.                     if (bitbuf & mask) c = right[c];
  400.                     else               c = left [c];
  401.                     mask >>= 1;
  402.                 } while (c >= NT);
  403.             }
  404.             fillbuf(pt_len[c]);
  405.             if (c <= 2) {
  406.                 if      (c == 0) c = 1;
  407.                 else if (c == 1) c = getbits(4) + 3;
  408.                 else             c = getbits(CBIT) + 20;
  409.                 while (--c >= 0) c_len[i++] = 0;
  410.             } else c_len[i++] = c - 2;
  411.         }
  412.         while (i < NC) c_len[i++] = 0;
  413.         make_table(NC, c_len, 12, c_table);
  414.     }
  415. }
  416.  
  417. static uint decode_c(void)
  418. {
  419.     uint j, mask;
  420.  
  421.     if (blocksize == 0) {
  422.         blocksize = getbits(16);
  423.         read_pt_len(NT, TBIT, 3);
  424.         read_c_len();
  425.         read_pt_len(NP, PBIT, -1);
  426.     }
  427.     blocksize--;
  428.     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  429.     if (j >= NC) {
  430.         mask = 1U << (BITBUFSIZ - 1 - 12);
  431.         do {
  432.             if (bitbuf & mask) j = right[j];
  433.             else               j = left [j];
  434.             mask >>= 1;
  435.         } while (j >= NC);
  436.     }
  437.     fillbuf(c_len[j]);
  438.     return j;
  439. }
  440.  
  441. static uint decode_p(void)
  442. {
  443.     uint j, mask;
  444.  
  445.     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  446.     if (j >= NP) {
  447.         mask = 1U << (BITBUFSIZ - 1 - 8);
  448.         do {
  449.             if (bitbuf & mask) j = right[j];
  450.             else               j = left [j];
  451.             mask >>= 1;
  452.         } while (j >= NP);
  453.     }
  454.     fillbuf(pt_len[j]);
  455.     if (j != 0) j = (1U << (j - 1)) + getbits(j - 1);
  456.     return j;
  457. }
  458.  
  459. static void huf_decode_start(void)
  460. {
  461.     init_getbits();  blocksize = 0;
  462. }
  463.  
  464. /* ----------------------End   of huf.c ------------------------------- */
  465.  
  466. /* ----------------------Start of maketre.c---------------------------- */
  467.  
  468. /***********************************************************
  469.     maketree.c -- make Huffman tree
  470. ***********************************************************/
  471.  
  472. static int    n, heapsize;
  473. static short  heap[NC + 1];
  474. static ushort *freq, *sortptr, len_cnt[17];
  475. static uchar  *len;
  476.  
  477. static void count_len(int i)  /* call with i = root */
  478. {
  479.     static int depth = 0;
  480.  
  481.     if (i < n) len_cnt[(depth < 16) ? depth : 16]++;
  482.     else {
  483.         depth++;
  484.         count_len(left [i]);
  485.         count_len(right[i]);
  486.         depth--;
  487.     }
  488. }
  489.  
  490. static void make_len(int root)
  491. {
  492.     int i, k;
  493.     uint cum;
  494.  
  495.     for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  496.     count_len(root);
  497.     cum = 0;
  498.     for (i = 16; i > 0; i--)
  499.         cum += len_cnt[i] << (16 - i);
  500.     while (cum != (1U << 16)) {
  501.         fprintf(stderr, "17");
  502.         len_cnt[16]--;
  503.         for (i = 15; i > 0; i--) {
  504.             if (len_cnt[i] != 0) {
  505.                 len_cnt[i]--;  len_cnt[i+1] += 2;  break;
  506.             }
  507.         }
  508.         cum--;
  509.     }
  510.     for (i = 16; i > 0; i--) {
  511.         k = len_cnt[i];
  512.         while (--k >= 0) len[*sortptr++] = i;
  513.     }
  514. }
  515.  
  516. static void downheap(int i)
  517.     /* priority queue; send i-th entry down heap */
  518. {
  519.     int j, k;
  520.  
  521.     k = heap[i];
  522.     while ((j = 2 * i) <= heapsize) {
  523.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  524.              j++;
  525.         if (freq[k] <= freq[heap[j]]) break;
  526.         heap[i] = heap[j];  i = j;
  527.     }
  528.     heap[i] = k;
  529. }
  530.  
  531. static void make_code(int n, uchar len[], ushort code[])
  532. {
  533.     int    i;
  534.     ushort start[18];
  535.  
  536.     start[1] = 0;
  537.     for (i = 1; i <= 16; i++)
  538.         start[i + 1] = (start[i] + len_cnt[i]) << 1;
  539.     for (i = 0; i < n; i++) code[i] = start[len[i]]++;
  540. }
  541.  
  542. int make_tree(int nparm, ushort freqparm[],
  543.                 uchar lenparm[], ushort codeparm[])
  544.     /* make tree, calculate len[], return root */
  545. {
  546.     int i, j, k, avail;
  547.  
  548.     n = nparm;  freq = freqparm;  len = lenparm;
  549.     avail = n;  heapsize = 0;  heap[1] = 0;
  550.     for (i = 0; i < n; i++) {
  551.         len[i] = 0;
  552.         if (freq[i]) heap[++heapsize] = i;
  553.     }
  554.     if (heapsize < 2) {
  555.         codeparm[heap[1]] = 0;  return heap[1];
  556.     }
  557.     for (i = heapsize / 2; i >= 1; i--)
  558.         downheap(i);  /* make priority queue */
  559.     sortptr = codeparm;
  560.     do {  /* while queue has at least two entries */
  561.         i = heap[1];  /* take out least-freq entry */
  562.         if (i < n) *sortptr++ = i;
  563.         heap[1] = heap[heapsize--];
  564.         downheap(1);
  565.         j = heap[1];  /* next least-freq entry */
  566.         if (j < n) *sortptr++ = j;
  567.         k = avail++;  /* generate new node */
  568.         freq[k] = freq[i] + freq[j];
  569.         heap[1] = k;  downheap(1);  /* put into queue */
  570.         left[k] = i;  right[k] = j;
  571.     } while (heapsize > 1);
  572.     sortptr = codeparm;
  573.     make_len(k);
  574.     make_code(nparm, lenparm, codeparm);
  575.     return k;  /* return root */
  576. }
  577.  
  578. /* ----------------------End   of maketre.c---------------------------- */
  579. /* ----------------------End   of maketbl.c---------------------------- */
  580.  
  581. /***********************************************************
  582.     maketbl.c -- make table for decoding
  583. ***********************************************************/
  584.  
  585. static void make_table(int nchar, uchar bitlen[], int tablebits, ushort table[])
  586. {
  587.     ushort count[17], weight[17], start[18], *p;
  588.     uint i, k, len, ch, jutbits, avail, nextcode, mask;
  589.  
  590.     for (i = 1; i <= 16; i++) count[i] = 0;
  591.     for (i = 0; i < nchar; i++) count[bitlen[i]]++;
  592.  
  593.     start[1] = 0;
  594.     for (i = 1; i <= 16; i++)
  595.         start[i + 1] = start[i] + (count[i] << (16 - i));
  596.     if (start[17] != (ushort)(1U << 16)) error("Bad table");
  597.  
  598.     jutbits = 16 - tablebits;
  599.     for (i = 1; i <= tablebits; i++) {
  600.         start[i] >>= jutbits;
  601.         weight[i] = 1U << (tablebits - i);
  602.     }
  603.     while (i <= 16) weight[i++] = 1U << (16 - i);
  604.  
  605.     i = start[tablebits + 1] >> jutbits;
  606.     if (i != (ushort)(1U << 16)) {
  607.         k = 1U << tablebits;
  608.         while (i != k) table[i++] = 0;
  609.     }
  610.  
  611.     avail = nchar;
  612.     mask = 1U << (15 - tablebits);
  613.     for (ch = 0; ch < nchar; ch++) {
  614.         if ((len = bitlen[ch]) == 0) continue;
  615.         nextcode = start[len] + weight[len];
  616.         if (len <= tablebits) {
  617.             for (i = start[len]; i < nextcode; i++) table[i] = ch;
  618.         } else {
  619.             k = start[len];
  620.             p = &table[k >> jutbits];
  621.             i = len - tablebits;
  622.             while (i != 0) {
  623.                 if (*p == 0) {
  624.                     right[avail] = left[avail] = 0;
  625.                     *p = avail++;
  626.                 }
  627.                 if (k & mask) p = &right[*p];
  628.                 else          p = &left[*p];
  629.                 k <<= 1;  i--;
  630.             }
  631.             *p = ch;
  632.         }
  633.         start[len] = nextcode;
  634.     }
  635. }
  636.  
  637. /* ----------------------End   of maketbl.c---------------------------- */
  638.  
  639. /* --------------------- start of decode.c ---------------------------- */
  640.  
  641.  
  642. static int dec_j;  /* remaining bytes to copy */
  643.  
  644. static void decode_start(void)
  645. {
  646.     huf_decode_start();
  647.     dec_j = 0;
  648. }
  649.  
  650. static void decode5(uint count, uchar buffer[])
  651.     /* The calling function must keep the number of
  652.        bytes to be processed.  This function decodes
  653.        either 'count' bytes or 'DICSIZ' bytes, whichever
  654.        is smaller, into the array 'buffer[]' of size
  655.        'DICSIZ' or more.
  656.        Call decode_start() once for each new file
  657.        before calling this function. */
  658. {
  659.     static uint i;
  660.     uint r, c;
  661.  
  662.     r = 0;
  663.     while (--dec_j >= 0) {
  664.         buffer[r] = buffer[i];
  665.         i = (i + 1) & (DICSIZ - 1);
  666.         if (++r == count) return;
  667.     }
  668.     for ( ; ; ) {
  669.         c = decode_c();
  670.         if (c <= UCHAR_MAX) {
  671.             buffer[r] = c;
  672.             if (++r == count) return;
  673.         } else {
  674.             dec_j = c - (UCHAR_MAX + 1 - THRESHOLD);
  675.             i = (r - decode_p() - 1) & (DICSIZ - 1);
  676.             while (--dec_j >= 0) {
  677.                 buffer[r] = buffer[i];
  678.                 i = (i + 1) & (DICSIZ - 1);
  679.                 if (++r == count) return;
  680.             }
  681.         }
  682.     }
  683. }
  684.  
  685.  
  686. void decode_lh5(ulong orgsize, ulong pacsize)
  687. {
  688.   int n;
  689.   make_crctable();
  690.   origsize=orgsize;
  691.   compsize=pacsize;
  692.   crc = INIT_CRC;
  693.   
  694.   decode_start();
  695.   while (origsize != 0) {
  696.       n = (uint)((origsize > DICSIZ) ? DICSIZ : origsize);
  697.       decode5(n, buffer);
  698.       fwrite_crc(buffer, n, outfile);
  699.       if (outfile != stdout) if (!flg_n) putc('*', stdout);
  700.       origsize -= n;
  701.   }
  702. }
  703.  
  704. /* ------------------------End of Deocde.c- --------------------------- */
  705.  
  706. /* ----------------------Start of Encode.c ---------------------------- */
  707.  
  708. /***********************************************************
  709.     encode.c -- sliding dictionary with percolating update
  710. ***********************************************************/
  711.  
  712. #define PERCOLATE  1
  713. #define NIL        0
  714. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  715.  
  716. typedef short node;
  717.  
  718. extern uchar *text, *childcount;
  719. extern node pos, matchpos, avail, *position, *parent, *prev, *next = NULL;
  720. extern int remainder, matchlen;
  721.  
  722. #if MAXMATCH <= (UCHAR_MAX + 1)
  723.     extern uchar *level;
  724. #else
  725.     extern ushort *level;
  726. #endif
  727.  
  728. void allocate_memory(void)
  729. {
  730.     if (next != NULL) return;
  731.     text = malloc(DICSIZ * 2 + MAXMATCH);
  732.     level      = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  733.     childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  734.     #if PERCOLATE
  735.       position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  736.     #else
  737.       position = malloc(DICSIZ * sizeof(*position));
  738.     #endif
  739.     parent     = malloc(DICSIZ * 2 * sizeof(*parent));
  740.     prev       = malloc(DICSIZ * 2 * sizeof(*prev));
  741.     next       = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  742.     if (next == NULL) error("Out of memory.");
  743. }
  744.  
  745. #ifdef _lhufs_
  746. /* extern void split(node old);
  747. extern void insert_node(void);
  748. extern void delete_node(void);
  749. extern void get_next_match(void);
  750. extern ulong encode5(ulong orgsize); */
  751. #else
  752.  
  753. void init_slide(void)
  754. {
  755.     node i;
  756.  
  757.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  758.         level[i] = 1;
  759.         #if PERCOLATE
  760.             position[i] = NIL;  /* sentinel */
  761.         #endif
  762.     }
  763.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  764.     avail = 1;
  765.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  766.     next[DICSIZ - 1] = NIL;
  767.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  768. }
  769.  
  770. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  771.  
  772. node child(node q, uchar c)
  773.     /* q's child for character c (NIL if not found) */
  774. {
  775.     node r;
  776.  
  777.     r = next[HASH(q, c)];
  778.     parent[NIL] = q;  /* sentinel */
  779.     while (parent[r] != q) r = next[r];
  780.     return r;
  781. }
  782.  
  783. void makechild(node q, uchar c, node r)
  784.     /* Let r be q's child for character c. */
  785. {
  786.     node h, t;
  787.  
  788.     h = HASH(q, c);
  789.     t = next[h];  next[h] = r;  next[r] = t;
  790.     prev[t] = r;  prev[r] = h;
  791.     parent[r] = q;  childcount[q]++;
  792. }
  793. static void split(node old)
  794. {
  795.     node new, t;
  796.  
  797.     new = avail;  avail = next[new];  childcount[new] = 0;
  798.     t = prev[old];  prev[new] = t;  next[t] = new;
  799.     t = next[old];  next[new] = t;  prev[t] = new;
  800.     parent[new] = parent[old];
  801.     level[new] = matchlen;
  802.     position[new] = pos;
  803.     makechild(new, text[matchpos + matchlen], old);
  804.     makechild(new, text[pos + matchlen], pos);
  805. }
  806. static void insert_node(void)
  807. {
  808.     node q, r, j, t;
  809.     uchar c, *t1, *t2;
  810.     int matchl;
  811.     
  812.     matchl=matchlen;
  813.  
  814.     if (matchl >= 4) {
  815.         matchl--;
  816.         r = (matchpos + 1) | DICSIZ;
  817.         while ((q = parent[r]) == NIL) r = next[r];
  818.         while (level[q] >= matchl) {
  819.             r = q;  q = parent[q];
  820.         }
  821.         #if PERCOLATE
  822.             t = q;
  823.             while (position[t] < 0) {
  824.                 position[t] = pos;  t = parent[t];
  825.             }
  826.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  827.         #else
  828.             t = q;
  829.             while (t < DICSIZ) {
  830.                 position[t] = pos;  t = parent[t];
  831.             }
  832.         #endif
  833.     } else {
  834.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  835.         matchlen=matchl;
  836.         if ((r = child(q, c)) == NIL) {
  837.             makechild(q, c, pos);  matchl = 1;
  838.             return;
  839.         }
  840.         matchl = 2;
  841.     }
  842.     for ( ; ; ) {
  843.         if (r >= DICSIZ) {
  844.             j = MAXMATCH;  matchpos = r;
  845.         } else {
  846.             j = level[r];
  847.             matchpos = position[r] & ~PERC_FLAG;
  848.         }
  849.         if (matchpos >= pos) matchpos -= DICSIZ;
  850.         t1 = &text[pos + matchl];  t2 = &text[matchpos + matchl];
  851.         while (matchl < j) {
  852.             if (*t1 != *t2) {  matchlen=matchl; split(r);  return;  }
  853.             matchl++;  t1++;  t2++;
  854.         }
  855.         if (matchl >= MAXMATCH) break;
  856.         position[r] = pos;
  857.         q = r;
  858.         if ((r = child(q, *t1)) == NIL) {
  859.             matchlen=matchl;
  860.             makechild(q, *t1, pos);  return;
  861.         }
  862.         matchl++;
  863.     }
  864.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  865.     t = next[r];  next[pos] = t;  prev[t] = pos;
  866.     parent[pos] = q;  parent[r] = NIL;
  867.     next[r] = pos;  /* special use of next[] */
  868.     matchlen=matchl;
  869. }
  870. static void delete_node(void)
  871. {
  872.     #if PERCOLATE
  873.         node q, r, s, t, u;
  874.     #else
  875.         node r, s, t, u;
  876.     #endif
  877.  
  878.     if (parent[pos] == NIL) return;
  879.     r = prev[pos];  s = next[pos];
  880.     next[r] = s;  prev[s] = r;
  881.     r = parent[pos];  parent[pos] = NIL;
  882.     if (r >= DICSIZ || --childcount[r] > 1) return;
  883.     #if PERCOLATE
  884.         t = position[r] & ~PERC_FLAG;
  885.     #else
  886.         t = position[r];
  887.     #endif
  888.     if (t >= pos) t -= DICSIZ;
  889.     #if PERCOLATE
  890.         s = t;  q = parent[r];
  891.         while ((u = position[q]) & PERC_FLAG) {
  892.             u &= ~PERC_FLAG;  if (u >= pos) u -= DICSIZ;
  893.             if (u > s) s = u;
  894.             position[q] = (s | DICSIZ);  q = parent[q];
  895.         }
  896.         if (q < DICSIZ) {
  897.             if (u >= pos) u -= DICSIZ;
  898.             if (u > s) s = u;
  899.             position[q] = s | DICSIZ | PERC_FLAG;
  900.         }
  901.     #endif
  902.     s = child(r, text[t + level[r]]);
  903.     t = prev[s];  u = next[s];
  904.     next[t] = u;  prev[u] = t;
  905.     t = prev[r];  next[t] = s;  prev[s] = t;
  906.     t = next[r];  prev[t] = s;  next[s] = t;
  907.     parent[s] = parent[r];  parent[r] = NIL;
  908.     next[r] = avail;  avail = r;
  909. }
  910.  
  911. static void get_next_match(void)
  912. {
  913.     int n;
  914.  
  915.     remainder--;
  916.     if (++pos == DICSIZ * 2) {
  917.         memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
  918.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
  919.         remainder += n;  pos = DICSIZ;  if (!flg_n) putc('*', stdout);
  920.     }
  921.     delete_node();  insert_node();
  922. }
  923.  
  924. void init_encode5(void)
  925. {
  926.   allocate_memory();  init_slide();  start_huf();
  927. }
  928.  
  929. ulong encode5(ulong orgsize)
  930. {
  931.     int lastmatchlen;
  932.     node lastmatchpos;
  933.     unpackable=0;
  934.     make_crctable();
  935.     origsize=orgsize;
  936.     compsize=0;
  937.  
  938.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
  939.     if (!flg_n) putc('*', stdout);
  940.     matchlen = 0;
  941.     pos = DICSIZ;  insert_node();
  942.     if (matchlen > remainder) matchlen = remainder;
  943.     while (remainder > 0 && ! unpackable) {
  944.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  945.         get_next_match();
  946.         if (matchlen > remainder) matchlen = remainder;
  947.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
  948.             output5(text[pos - 1], 0);
  949.         else {
  950.             output5(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  951.                    (pos - lastmatchpos - 2) & (DICSIZ - 1));
  952.             while (--lastmatchlen > 0) get_next_match();
  953.             if (matchlen > remainder) matchlen = remainder;
  954.         }
  955.     }
  956.     end_huf();
  957.     if (unpackable) compsize=orgsize+1;
  958.     return compsize;
  959. }
  960. #endif
  961. /* ----------------------- End of Encode.c ---------------------------- */
  962.