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