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