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 / shuf.c < prev    next >
C/C++ Source or Header  |  1994-06-19  |  4KB  |  229 lines
  1. /*
  2.  * shuf.c --- extract static Huffman coding
  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 "typedef.h"
  13. #include "slidehuf.h"
  14.  
  15.  
  16. #define N1 286            /* alphabet size */
  17. #define N2 (2 * N1 - 1)        /* # of nodes in Huffman tree */
  18. #define EXTRABITS 8        /* >= log2(F-THRESHOLD+258-N1) */
  19. #define BUFBITS  16        /* >= log2(MAXBUF) */
  20. #define LENFIELD  4        /* bit size of length field for tree output */
  21. #define NP (8 * 1024 / 64)
  22. #define NP2 (NP * 2 - 1)
  23.  
  24.  
  25. static unsigned int np;
  26.  
  27.  
  28. int fixed[2][16] =
  29. {
  30.   {3, 0x01, 0x04, 0x0c, 0x18, 0x30, 0},    /* old compatible */
  31.   {2, 0x01, 0x01, 0x03, 0x06, 0x0D, 0x1F, 0x4E, 0} /* 8K buf */
  32. };
  33.  
  34.  
  35. void
  36. decode_start_st0(void)
  37. {
  38.   n_max = 286;
  39.   maxmatch = MAXMATCH;
  40.   init_getbits();
  41.   np = 1 << (MAX_DICBIT - 6);
  42. }
  43.  
  44.  
  45. void
  46. encode_p_st0(unsigned short j)
  47. {
  48.   unsigned short i;
  49.  
  50.   i = j >> 6;
  51.   putcode(pt_len[i], pt_code[i]);
  52.   putbits(6, j & 0x3f);
  53. }
  54.  
  55.  
  56. #ifdef __API16__
  57. #pragma optimize("awgelzc", off)
  58. #endif
  59. static void
  60. ready_made(int method)
  61. {
  62.   int i, j;
  63.   uint code, weight;
  64.   int *tbl;
  65.  
  66.   tbl = fixed[method];
  67.   j = *tbl++;
  68.   weight = 1 << (16 - j);
  69.   code = 0; 
  70.   for(i = 0; i < np; i++)
  71.     {
  72.       while(*tbl == i)
  73.     {
  74.       j++;
  75.       tbl++;
  76.       weight >>= 1;
  77.     }
  78.       pt_len[i] = j;
  79.       pt_code[i] = code;
  80.       code += weight;
  81.     }
  82. }
  83. #ifdef __API16__
  84. #pragma optimize("awgelzc", on)
  85. #endif
  86.  
  87.  
  88. void
  89. encode_start_fix(void)
  90. {
  91.   n_max = 314;
  92.   maxmatch = 60;
  93.   np = 1 << (12 - 6);
  94.   init_putbits();
  95.   start_c_dyn();
  96.   ready_made(0);
  97. }
  98.  
  99.  
  100. static void
  101. read_tree_c(void)        /* read tree from file */
  102. {
  103.   int i, c;
  104.  
  105.   i = 0;
  106.   while(i < N1)
  107.     {
  108.       if(getbits(1))
  109.     c_len[i] = getbits(LENFIELD) + 1;
  110.       else
  111.     c_len[i] = 0;
  112.       if(++i == 3 && c_len[0] == 1 && c_len[1] == 1 && c_len[2] == 1)
  113.     {
  114.       c = getbits(CBIT);
  115.       for(i = 0; i < N1; i++)
  116.         c_len[i] = 0;
  117.       for(i = 0; i < 4096; i++)
  118.         c_table[i] = c;
  119.       return;
  120.     }
  121.     }
  122.   make_table(N1, c_len, 12, c_table);
  123. }
  124.  
  125.  
  126. static void
  127. read_tree_p(void)        /* read tree from file */
  128. {
  129.   int i, c;
  130.  
  131.   i = 0;
  132.   while(i < NP)
  133.     {
  134.       pt_len[i] = getbits(LENFIELD);
  135.       if(++i == 3 && pt_len[0] == 1 && pt_len[1] == 1 && pt_len[2] == 1)
  136.     {
  137.       c = getbits(MAX_DICBIT - 6);
  138.       for(i = 0; i < NP; i++)
  139.         pt_len[i] = 0;
  140.       for(i = 0; i < 256; i++)
  141.         pt_table[i] = c;
  142.       return;
  143.     }
  144.     }
  145. }
  146.  
  147.  
  148. void
  149. decode_start_fix(void)
  150. {
  151.   n_max = 314;
  152.   maxmatch = 60;
  153.   init_getbits();
  154.   np = 1 << (12 - 6);
  155.   start_c_dyn();
  156.   ready_made(0);
  157.   make_table(np, pt_len, 8, pt_table);
  158. }
  159.  
  160.  
  161. ushort
  162. decode_c_st0(void)
  163. {
  164.   int i, j;
  165.   static unsigned short blocksize = 0;
  166.  
  167.   if(blocksize == 0)        /* read block head */
  168.     {
  169.       blocksize = getbits(BUFBITS); /* read block blocksize */
  170.       read_tree_c();
  171.       if(getbits(1))
  172.     read_tree_p();
  173.       else
  174.     ready_made(1);
  175.       make_table(NP, pt_len, 8, pt_table);
  176.     }
  177.   blocksize--;
  178.   j = c_table[bitbuf >> 4];
  179.   if(j < N1)
  180.     fillbuf(c_len[j]);
  181.   else
  182.     {
  183.       fillbuf(12);
  184.       i = bitbuf;
  185.       do
  186.     {
  187.       if((signed short)i < 0)
  188.         j = right[j];
  189.       else
  190.         j = left [j];
  191.       i <<= 1;
  192.     }
  193.       while(j >= N1);
  194.       fillbuf(c_len[j] - 12);
  195.     }
  196.   if(j == N1 - 1)
  197.     j += getbits(EXTRABITS);
  198.  
  199.   return j;
  200. }
  201.  
  202.  
  203. ushort
  204. decode_p_st0(void)
  205. {
  206.   int i, j;
  207.  
  208.   j = pt_table[bitbuf >> 8];
  209.   if(j < np)
  210.     fillbuf(pt_len[j]);
  211.   else
  212.     {
  213.       fillbuf(8);
  214.       i = bitbuf;
  215.       do
  216.     {
  217.       if((signed short)i < 0)
  218.         j = right[j];
  219.       else
  220.         j = left [j];
  221.       i <<= 1;
  222.     }
  223.       while(j >= np);
  224.       fillbuf(pt_len[j] - 8);
  225.     }
  226.  
  227.   return (j << 6) + getbits(6);
  228. }
  229.