home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / lha100bt.zip / lha-1.00 / src / huf.c < prev    next >
C/C++ Source or Header  |  1992-04-04  |  7KB  |  337 lines
  1. /***********************************************************
  2.     huf.c -- new static Huffman
  3. ***********************************************************/
  4. #ifdef sony_news
  5. #include <sys/param.h>
  6. #endif
  7. #if defined(__STDC__) || defined(NEWSOS)
  8. #include <stdlib.h>
  9. #endif
  10. #include "slidehuf.h"
  11.  
  12. #define NP (MAX_DICBIT + 1)
  13. #define NT (USHRT_BIT + 3)
  14. #define PBIT 4  /* smallest integer such that (1 << PBIT) > NP */
  15. #define TBIT 5  /* smallest integer such that (1 << TBIT) > NT */
  16. /*#if NT > NP
  17.     #define NPT NT
  18. #else
  19.     #define NPT NP
  20. #endif*/
  21. #define NPT 0x80
  22.  
  23. unsigned short left[2 * NC - 1], right[2 * NC - 1];
  24. unsigned char c_len[NC], pt_len[NPT];
  25. unsigned short c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  26.        p_freq[2 * NP - 1], pt_table[256], pt_code[NPT],
  27.        t_freq[2 * NT - 1];
  28. static unsigned char *buf;
  29. static unsigned short bufsiz;
  30. static unsigned short blocksize;
  31.  
  32. /***** encoding *****/
  33.  
  34. static void count_t_freq(void)
  35. {
  36.     short i, k, n, count;
  37.  
  38.     for (i = 0; i < NT; i++) t_freq[i] = 0;
  39.     n = NC;
  40.     while (n > 0 && c_len[n - 1] == 0) n--;
  41.     i = 0;
  42.     while (i < n) {
  43.         k = c_len[i++];
  44.         if (k == 0) {
  45.             count = 1;
  46.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  47.             if (count <= 2) t_freq[0] += count;
  48.             else if (count <= 18) t_freq[1]++;
  49.             else if (count == 19) {  t_freq[0]++;  t_freq[1]++;  }
  50.             else t_freq[2]++;
  51.         } else t_freq[k + 2]++;
  52.     }
  53. }
  54.  
  55. static void write_pt_len(n, nbit, i_special)
  56. short n;
  57. short nbit;
  58. short i_special;
  59. {
  60.     short i, k;
  61.  
  62.     while (n > 0 && pt_len[n - 1] == 0) n--;
  63.     putbits(nbit, n);
  64.     i = 0;
  65.     while (i < n) {
  66.         k = pt_len[i++];
  67.         if (k <= 6) putbits(3, k);
  68.         else putbits(k - 3, USHRT_MAX << 1);
  69.         if (i == i_special) {
  70.             while (i < 6 && pt_len[i] == 0) i++;
  71.             putbits(2, i - 3);
  72.         }
  73.     }
  74. }
  75.  
  76. static void write_c_len(void)
  77. {
  78.     short i, k, n, count;
  79.  
  80.     n = NC;
  81.     while (n > 0 && c_len[n - 1] == 0) n--;
  82.     putbits(CBIT, n);
  83.     i = 0;
  84.     while (i < n) {
  85.         k = c_len[i++];
  86.         if (k == 0) {
  87.             count = 1;
  88.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  89.             if (count <= 2) {
  90.                 for (k = 0; k < count; k++)
  91.                     putcode(pt_len[0], pt_code[0]);
  92.             } else if (count <= 18) {
  93.                 putcode(pt_len[1], pt_code[1]);
  94.                 putbits(4, count - 3);
  95.             } else if (count == 19) {
  96.                 putcode(pt_len[0], pt_code[0]);
  97.                 putcode(pt_len[1], pt_code[1]);
  98.                 putbits(4, 15);
  99.             } else {
  100.                 putcode(pt_len[2], pt_code[2]);
  101.                 putbits(CBIT, count - 20);
  102.             }
  103.         } else putcode(pt_len[k + 2], pt_code[k + 2]);
  104.     }
  105. }
  106.  
  107. static void encode_c(c)
  108. short c;
  109. {
  110.     putcode(c_len[c], c_code[c]);
  111. }
  112.  
  113. static void encode_p(p)
  114. unsigned short p;
  115. {
  116.     unsigned short c, q;
  117.  
  118.     c = 0;  q = p;  while (q) {  q >>= 1;  c++;  }
  119.     putcode(pt_len[c], pt_code[c]);
  120.     if (c > 1) putbits(c - 1, p);
  121. }
  122.  
  123. static void send_block(void)
  124. {
  125.     unsigned char flags;
  126.     unsigned short i, k, root, pos, size;
  127.  
  128.     root = make_tree(NC, c_freq, c_len, c_code);
  129.     size = c_freq[root];  putbits(16, size);
  130.     if (root >= NC) {
  131.         count_t_freq();
  132.         root = make_tree(NT, t_freq, pt_len, pt_code);
  133.         if (root >= NT) {
  134.             write_pt_len(NT, TBIT, 3);
  135.         } else {
  136.             putbits(TBIT, 0);  putbits(TBIT, root);
  137.         }
  138.         write_c_len();
  139.     } else {
  140.         putbits(TBIT, 0);  putbits(TBIT, 0);
  141.         putbits(CBIT, 0);  putbits(CBIT, root);
  142.     }
  143.     root = make_tree(NP, p_freq, pt_len, pt_code);
  144.     if (root >= NP) {
  145.         write_pt_len(NP, PBIT, -1);
  146.     } else {
  147.         putbits(PBIT, 0);  putbits(PBIT, root);
  148.     }
  149.     pos = 0;
  150.     for (i = 0; i < size; i++) {
  151.         if (i % CHAR_BIT == 0) flags = buf[pos++];  else flags <<= 1;
  152.         if (flags & (1 << (CHAR_BIT - 1))) {
  153.             encode_c(buf[pos++] + (1 << CHAR_BIT));
  154.             k = buf[pos++] << CHAR_BIT;  k += buf[pos++];
  155.             encode_p(k);
  156.         } else encode_c(buf[pos++]);
  157.         if (unpackable) return;
  158.     }
  159.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  160.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  161. }
  162.  
  163. static unsigned short output_pos, output_mask;
  164.  
  165. void output_st1(c, p)
  166. unsigned short c;
  167. unsigned short p;
  168. {
  169.     static unsigned short cpos;
  170.  
  171.     output_mask >>= 1;
  172.     if (output_mask == 0) {
  173.         output_mask = 1 << (CHAR_BIT - 1);
  174.         if (output_pos >= bufsiz - 3 * CHAR_BIT) {
  175.             send_block();
  176.             if (unpackable) return;
  177.             output_pos = 0;
  178.         }
  179.         cpos = output_pos++;  buf[cpos] = 0;
  180.     }
  181.     buf[output_pos++] = (unsigned char) c;  c_freq[c]++;
  182.     if (c >= (1 << CHAR_BIT)) {
  183.         buf[cpos] |= output_mask;
  184.         buf[output_pos++] = (unsigned char)(p >> CHAR_BIT);
  185.         buf[output_pos++] = (unsigned char) p;
  186.         c = 0;  while (p) {  p >>= 1;  c++;  }
  187.         p_freq[c]++;
  188.     }
  189. }
  190.  
  191. unsigned char *alloc_buf(void)
  192. {
  193.     bufsiz = 16 * 1024; /* 65408U; */
  194.     while ((buf = (unsigned char *)malloc(bufsiz)) == NULL) {
  195.         bufsiz = (bufsiz / 10) * 9;
  196.         if (bufsiz < 4 * 1024) break;
  197.     }
  198.     return buf;
  199. }
  200.  
  201. void encode_start_st1(void)
  202. {
  203.     int i;
  204.  
  205.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  206.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  207.     output_pos = output_mask = 0;
  208.     init_putbits();
  209.     buf[0] = 0;
  210. }
  211.  
  212. void encode_end_st1(void)
  213. {
  214.     if (! unpackable) {
  215.         send_block();
  216.         putbits(CHAR_BIT - 1, 0);  /* flush remaining bits */
  217.     }
  218. }
  219.  
  220. /***** decoding *****/
  221.  
  222. static void read_pt_len(nn, nbit, i_special)
  223. short nn;
  224. short nbit;
  225. short i_special;
  226. {
  227.     short i, c, n;
  228.  
  229.     n = getbits(nbit);
  230.     if (n == 0) {
  231.         c = getbits(nbit);
  232.         for (i = 0; i < nn; i++) pt_len[i] = 0;
  233.         for (i = 0; i < 256; i++) pt_table[i] = c;
  234.     } else {
  235.         i = 0;
  236.         while (i < n) {
  237.             c = bitbuf >> (16 - 3);
  238.             if (c == 7) {
  239.                 unsigned short mask = 1 << (16 - 4);
  240.                 while (mask & bitbuf) {  mask >>= 1;  c++;  }
  241.             }
  242.             fillbuf((c < 7) ? 3 : c - 3);
  243.             pt_len[i++] = c;
  244.             if (i == i_special) {
  245.                 c = getbits(2);
  246.                 while (--c >= 0) pt_len[i++] = 0;
  247.             }
  248.         }
  249.         while (i < nn) pt_len[i++] = 0;
  250.         make_table(nn, pt_len, 8, pt_table);
  251.     }
  252. }
  253.  
  254. static void read_c_len(void)
  255. {
  256.     short i, c, n;
  257.  
  258.     n = getbits(CBIT);
  259.     if (n == 0) {
  260.         c = getbits(CBIT);
  261.         for (i = 0; i < NC; i++) c_len[i] = 0;
  262.         for (i = 0; i < 4096; i++) c_table[i] = c;
  263.     } else {
  264.         i = 0;
  265.         while (i < n) {
  266.             c = pt_table[bitbuf >> (16 - 8)];
  267.             if (c >= NT) {
  268.                 unsigned short mask = 1 << (16 - 9);
  269.                 do {
  270.                     if (bitbuf & mask) c = right[c];
  271.                     else               c = left [c];
  272.                     mask >>= 1;
  273.                 } while (c >= NT);
  274.             }
  275.             fillbuf(pt_len[c]);
  276.             if (c <= 2) {
  277.                 if      (c == 0) c = 1;
  278.                 else if (c == 1) c = getbits(4) + 3;
  279.                 else             c = getbits(CBIT) + 20;
  280.                 while (--c >= 0) c_len[i++] = 0;
  281.             } else c_len[i++] = c - 2;
  282.         }
  283.         while (i < NC) c_len[i++] = 0;
  284.         make_table(NC, c_len, 12, c_table);
  285.     }
  286. }
  287.  
  288. unsigned short decode_c_st1(void)
  289. {
  290.     unsigned short j, mask;
  291.  
  292.     if (blocksize == 0) {
  293.         blocksize = getbits(16);
  294.         read_pt_len(NT, TBIT, 3);
  295.         read_c_len();
  296.         read_pt_len(NP, PBIT, -1);
  297.     }
  298.     blocksize--;
  299.     j = c_table[bitbuf >> 4];
  300.     if (j < NC) fillbuf(c_len[j]);
  301.     else {
  302.         fillbuf(12);  mask = 1 << (16 - 1);
  303.         do {
  304.             if (bitbuf & mask) j = right[j];
  305.             else               j = left [j];
  306.             mask >>= 1;
  307.         } while (j >= NC);
  308.         fillbuf(c_len[j] - 12);
  309.     }
  310.     return j;
  311. }
  312.  
  313. unsigned short decode_p_st1(void)
  314. {
  315.     unsigned short j, mask;
  316.  
  317.     j = pt_table[bitbuf >> (16 - 8)];
  318.     if (j < NP) fillbuf(pt_len[j]);
  319.     else {
  320.         fillbuf(8);  mask = 1 << (16 - 1);
  321.         do {
  322.             if (bitbuf & mask) j = right[j];
  323.             else               j = left [j];
  324.             mask >>= 1;
  325.         } while (j >= NP);
  326.         fillbuf(pt_len[j] - 8);
  327.     }
  328.     if (j != 0) j = (1 << (j - 1)) + getbits(j - 1);
  329.     return j;
  330. }
  331.  
  332. void decode_start_st1(void)
  333. {
  334.     init_getbits();
  335.     blocksize = 0;
  336. }
  337.