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