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