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