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