home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1997 December / VPR9712A.ISO / OLS / OS2 / LHA2P205 / LHA2P205.LZH / lha2-2.05pre / source.lzh / src / huf.c < prev    next >
C/C++ Source or Header  |  1994-06-20  |  8KB  |  502 lines
  1. /*
  2.  * huf.c --- new static Huffman
  3.  *   Copyright (C) 1988-1992, Haruyasu YOSHIZAKI
  4.  *
  5.  * $Log$
  6.  */
  7.  
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <limits.h>
  12. #include <time.h>
  13. #include "port2.h"
  14. #include "typedef.h"
  15. #include "lh.h"
  16. #include "slidehuf.h"
  17.  
  18.  
  19. #define TMPBUF_MAX    (1024 * 16)
  20. #define NP (MAX_DICBIT + 1)
  21. #define NT (USHRT_BIT + 3)
  22. /* smallest integer such that (1U << PBIT) > NP */
  23. #define PBIT 4
  24. /* smallest integer such that (1U << TBIT) > NT */
  25. #define TBIT 5
  26. #define NPT 0x80
  27.  
  28.  
  29. ushort left[2 * NC - 1], right[2 * NC - 1];
  30. uchar c_len[NC], pt_len[NPT];
  31. ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  32.   p_freq[2 * NP - 1], pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
  33.  
  34.  
  35. static uchar *buf;
  36. static ushort bufsiz, blocksize;
  37. static ushort output_pos, output_mask;
  38.  
  39.  
  40. /*
  41.  * encoding
  42.  */
  43. static void
  44. count_t_freq(void)
  45. {
  46.   short i, k, n, count;
  47.  
  48.   for(i = 0; i < NT; i++)
  49.     t_freq[i] = 0;
  50.   n = NC;
  51.   while(n > 0 && c_len[n - 1] == 0)
  52.     n--;
  53.   i = 0;
  54.   while(i < n)
  55.     {
  56.       k = c_len[i++];
  57.       if(k == 0)
  58.     {
  59.       count = 1;
  60.       while(i < n && c_len[i] == 0)
  61.         {
  62.           i++;
  63.           count++;
  64.         }
  65.       if(count <= 2)
  66.         t_freq[0] += count;
  67.       else if(count <= 18)
  68.         t_freq[1]++;
  69.       else if(count == 19)
  70.         {
  71.           t_freq[0]++;
  72.           t_freq[1]++;
  73.         }
  74.       else
  75.         t_freq[2]++;
  76.     }
  77.       else
  78.     t_freq[k + 2]++;
  79.     }
  80. }
  81.  
  82.  
  83. static void
  84. write_pt_len(short n, short nbit, short i_special)
  85. {
  86.   short i, k;
  87.  
  88.   while(n > 0 && pt_len[n - 1] == 0)
  89.     n--;
  90.   putbits(nbit, n);
  91.   i = 0;
  92.   while(i < n)
  93.     {
  94.       k = pt_len[i++];
  95.       if(k <= 6)
  96.     putbits(3, k);
  97.       else
  98.     putbits(k - 3, USHRT_MAX << 1);
  99.       if(i == i_special)
  100.     {
  101.       while(i < 6 && pt_len[i] == 0)
  102.         i++;
  103.       putbits(2, i - 3);
  104.     }
  105.     }
  106. }
  107.  
  108.  
  109. static void
  110. write_c_len(void)
  111. {
  112.   short i, k, n, count;
  113.  
  114.   n = NC;
  115.   while(n > 0 && c_len[n - 1] == 0)
  116.     n--;
  117.   putbits(CBIT, n);
  118.   i = 0;
  119.   while(i < n)
  120.     {
  121.       k = c_len[i++];
  122.       if(k == 0)
  123.     {
  124.       count = 1;
  125.       while(i < n && c_len[i] == 0)
  126.         {
  127.           i++;
  128.           count++;
  129.         }
  130.       if(count <= 2)
  131.         {
  132.           for(k = 0; k < count; k++)
  133.         putcode(pt_len[0], pt_code[0]);
  134.         }
  135.       else if(count <= 18)
  136.         {
  137.           putcode(pt_len[1], pt_code[1]);
  138.           putbits(4, count - 3);
  139.         }
  140.       else if(count == 19)
  141.         {
  142.           putcode(pt_len[0], pt_code[0]);
  143.           putcode(pt_len[1], pt_code[1]);
  144.           putbits(4, 15);
  145.         }
  146.       else
  147.         {
  148.           putcode(pt_len[2], pt_code[2]);
  149.           putbits(CBIT, count - 20);
  150.         }
  151.     }
  152.       else
  153.     putcode(pt_len[k + 2], pt_code[k + 2]);
  154.     }
  155. }
  156.  
  157.  
  158. static void
  159. encode_c(short c)
  160. {
  161.   putcode(c_len[c], c_code[c]);
  162. }
  163.  
  164.  
  165. static void
  166. encode_p(ushort p)
  167. {
  168.   ushort c, q;
  169.  
  170.   c = 0;
  171.   q = p;
  172.   while(q)
  173.     {
  174.       q >>= 1;
  175.       c++;
  176.     }
  177.   putcode(pt_len[c], pt_code[c]);
  178.   if(c > 1)
  179.     putbits(c - 1, p);
  180. }
  181.  
  182.  
  183. static void
  184. send_block(void)
  185. {
  186.   uchar flags;
  187.   ushort i, k, root, pos, size;
  188.  
  189.   root = make_tree(NC, c_freq, c_len, c_code);
  190.   size = c_freq[root];
  191.   putbits(16, size);
  192.   if(root >= NC)
  193.     {
  194.       count_t_freq();
  195.       root = make_tree(NT, t_freq, pt_len, pt_code);
  196.       if(root >= NT)
  197.     {
  198.       write_pt_len(NT, TBIT, 3);
  199.     }
  200.       else
  201.     {
  202.       putbits(TBIT, 0);
  203.       putbits(TBIT, root);
  204.     }
  205.       write_c_len();
  206.     }
  207.   else
  208.     {
  209.       putbits(TBIT, 0);
  210.       putbits(TBIT, 0);
  211.       putbits(CBIT, 0);
  212.       putbits(CBIT, root);
  213.     }
  214.   root = make_tree(NP, p_freq, pt_len, pt_code);
  215.   if(root >= NP)
  216.     {
  217.       write_pt_len(NP, PBIT, -1);
  218.     }
  219.   else
  220.     {
  221.       putbits(PBIT, 0);
  222.       putbits(PBIT, root);
  223.     }
  224.   pos = 0;
  225.   for(i = 0; i < size; i++)
  226.     {
  227.       if(i % CHAR_BIT == 0)
  228.     flags = buf[pos++];
  229.       else
  230.     flags <<= 1;
  231.       if(flags & (1U << (CHAR_BIT - 1)))
  232.     {
  233.       encode_c(buf[pos++] + (1U << CHAR_BIT));
  234.       k = buf[pos++] << CHAR_BIT;
  235.       k += buf[pos++];
  236.       encode_p(k);
  237.     }
  238.       else
  239.     encode_c(buf[pos++]);
  240.       if(unpackable)
  241.     return;
  242.     }
  243.   for(i = 0; i < NC; i++)
  244.     c_freq[i] = 0;
  245.   for(i = 0; i < NP; i++)
  246.     p_freq[i] = 0;
  247. }
  248.  
  249.  
  250. void
  251. output_st1(ushort c, ushort p)
  252. {
  253.   static ushort cpos;
  254.  
  255.   if((output_mask >>= 1) == 0)
  256.     {
  257.       output_mask = 1U << (CHAR_BIT - 1);
  258.       if(output_pos >= bufsiz - 3 * CHAR_BIT)
  259.     {
  260.       send_block();
  261.       if(unpackable)
  262.         return;
  263.       output_pos = 0;
  264.     }
  265.       cpos = output_pos++;
  266.       buf[cpos] = 0;
  267.     }
  268.   buf[output_pos++] = (uchar)c;
  269.   c_freq[c]++;
  270.   if(c >= (1U << CHAR_BIT))
  271.     {
  272.       buf[cpos] |= output_mask;
  273.       buf[output_pos++] = (uchar)(p >> CHAR_BIT);
  274.       buf[output_pos++] = (uchar) p;
  275.       c = 0;
  276.       while(p)
  277.     {
  278.       p >>= 1;
  279.       c++;
  280.     }
  281.       p_freq[c]++;
  282.     }
  283. }
  284.  
  285.  
  286. void *
  287. alloc_buf(void)
  288. {
  289.   bufsiz = TMPBUF_MAX;
  290.   while((buf = malloc(bufsiz)) == NULL)
  291.     {
  292.       bufsiz = (bufsiz / 10U) * 9U;
  293.       if(bufsiz < 4 * 1024U)
  294.     break;
  295.     }
  296.  
  297.   return buf;
  298. }
  299.  
  300.  
  301. void
  302. encode_start_st1(void)
  303. {
  304.   int i;
  305.  
  306.   for(i = 0; i < NC; i++)
  307.     c_freq[i] = 0;
  308.   for(i = 0; i < NP; i++)
  309.     p_freq[i] = 0;
  310.   output_pos = output_mask = 0;
  311.   init_putbits();
  312.   buf[0] = 0;
  313. }
  314.  
  315.  
  316. void
  317. encode_end_st1(void)
  318. {
  319.   if(! unpackable)
  320.     {
  321.       send_block();
  322.       putbits(CHAR_BIT - 1, 0);    /* flush remaining bits */
  323.     }
  324. }
  325.  
  326.  
  327. /*
  328.  * decoding
  329.  */
  330. static void
  331. read_pt_len(short nn, short nbit, short i_special)
  332. {
  333.   short i, c, n;
  334.  
  335.   n = getbits(nbit);
  336.   if(n == 0)
  337.     {
  338.       c = getbits(nbit);
  339.       for(i = 0; i < nn; i++)
  340.     pt_len[i] = 0;
  341.       for(i = 0; i < 256; i++)
  342.     pt_table[i] = c;
  343.     }
  344.   else
  345.     {
  346.       i = 0;
  347.       while(i < n)
  348.     {
  349.       c = bitbuf >> (16 - 3);
  350.       if(c == 7)
  351.         {
  352.           ushort mask = 1U << (16 - 4);
  353.           while(mask & bitbuf)
  354.         {
  355.           mask >>= 1;
  356.           c++;
  357.         }
  358.         }
  359.       fillbuf((c < 7) ? 3 : c - 3);
  360.       pt_len[i++] = c;
  361.       if(i == i_special)
  362.         {
  363.           c = getbits(2);
  364.           while(--c >= 0)
  365.         pt_len[i++] = 0;
  366.         }
  367.     }
  368.       while(i < nn)
  369.     pt_len[i++] = 0;
  370.       make_table(nn, pt_len, 8, pt_table);
  371.     }
  372. }
  373.  
  374.  
  375. static void
  376. read_c_len(void)
  377. {
  378.   short i, c, n;
  379.  
  380.   n = getbits(CBIT);
  381.   if(n == 0)
  382.     {
  383.       c = getbits(CBIT);
  384.       for(i = 0; i < NC; i++)
  385.     c_len[i] = 0;
  386.       for(i = 0; i < 4096; i++)
  387.     c_table[i] = c;
  388.     }
  389.   else
  390.     {
  391.       i = 0;
  392.       while(i < n)
  393.     {
  394.       c = pt_table[bitbuf >> (16 - 8)];
  395.       if(c >= NT)
  396.         {
  397.           ushort mask = 1U << (16 - 9);
  398.           do
  399.         {
  400.           if(bitbuf & mask)
  401.             c = right[c];
  402.           else
  403.             c = left [c];
  404.           mask >>= 1;
  405.         }
  406.           while(c >= NT);
  407.         }
  408.       fillbuf(pt_len[c]);
  409.       if(c <= 2)
  410.         {
  411.           if(c == 0)
  412.         c = 1;
  413.           else if(c == 1)
  414.         c = getbits(4) + 3;
  415.           else
  416.         c = getbits(CBIT) + 20;
  417.           while(--c >= 0)
  418.         c_len[i++] = 0;
  419.         }
  420.       else
  421.         c_len[i++] = c - 2;
  422.     }
  423.       while(i < NC)
  424.     c_len[i++] = 0;
  425.       make_table(NC, c_len, 12, c_table);
  426.     }
  427. }
  428.  
  429.  
  430. ushort
  431. decode_c_st1(void)
  432. {
  433.   ushort j, mask;
  434.  
  435.   if(blocksize == 0)
  436.     {
  437.       blocksize = getbits(16);
  438.       read_pt_len(NT, TBIT, 3);
  439.       read_c_len();
  440.       read_pt_len(NP, PBIT, -1);
  441.     }
  442.   blocksize--;
  443.   j = c_table[bitbuf >> 4];
  444.   if(j < NC)
  445.     fillbuf(c_len[j]);
  446.   else
  447.     {
  448.       fillbuf(12);
  449.       mask = 1U << (16 - 1);
  450.       do
  451.     {
  452.       if(bitbuf & mask)
  453.         j = right[j];
  454.       else
  455.         j = left [j];
  456.       mask >>= 1;
  457.     }
  458.       while(j >= NC);
  459.       fillbuf(c_len[j] - 12);
  460.     }
  461.  
  462.   return j;
  463. }
  464.  
  465.  
  466. ushort
  467. decode_p_st1(void)
  468. {
  469.   ushort j, mask;
  470.  
  471.   j = pt_table[bitbuf >> (16 - 8)];
  472.   if(j < NP)
  473.     fillbuf(pt_len[j]);
  474.   else
  475.     {
  476.       fillbuf(8);
  477.       mask = 1U << (16 - 1);
  478.       do
  479.     {
  480.       if(bitbuf & mask)
  481.         j = right[j];
  482.       else
  483.         j = left [j];
  484.       mask >>= 1;
  485.     }
  486.       while(j >= NP);
  487.       fillbuf(pt_len[j] - 8);
  488.     }
  489.   if(j != 0)
  490.     j = (1U << (j - 1)) + getbits(j - 1);
  491.  
  492.   return j;
  493. }
  494.  
  495.  
  496. void
  497. decode_start_st1(void)
  498. {
  499.   init_getbits();
  500.   blocksize = 0;
  501. }
  502.