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 / maketbl.c < prev    next >
Text File  |  1994-02-14  |  4KB  |  144 lines
  1. /***********************************************************
  2.     maketbl.c -- makes decoding table
  3. ***********************************************************/
  4. #include "slidehuf.h"
  5.  
  6. #if 0
  7. static short c, n, tblsiz, len, depth, maxdepth, avail;
  8. static unsigned short codeword, bit, *tbl;
  9. static unsigned char *blen;
  10.  
  11. static short mktbl()
  12. {
  13.     short i;
  14.  
  15.     if (len == depth) {
  16.         while (++c < n)
  17.             if (blen[c] == len) {
  18.                 i = codeword;  
  19.                 codeword += bit;
  20.                 if (codeword > tblsiz) error(BROKENARC, "Bad table (1)");
  21.                 while (i < codeword) tbl[i++] = c;
  22.                 return c;
  23.             }
  24.         c = -1;  
  25.         len++;  
  26.         bit >>= 1;
  27.     }
  28.     depth++;
  29.     if (depth < maxdepth) {
  30.         (void) mktbl();  
  31.         (void) mktbl();
  32.     } 
  33.     else if (depth > USHRT_BIT) {
  34.         error(BROKENARC, "Bad table (2)");
  35.     } 
  36.     else {
  37.         if ((i = avail++) >= 2 * n - 1) error(BROKENARC, "Bad table (3)");
  38.         left[i] = mktbl();  
  39.         right[i] = mktbl();
  40.         if (codeword >= tblsiz) error(BROKENARC, "Bad table (4)");
  41.         if (depth == maxdepth) tbl[codeword++] = i;
  42.     }
  43.     depth--;
  44.     return i;
  45. }
  46.  
  47. void make_table(short nchar, unsigned char bitlen[],
  48. short tablebits, unsigned short table[])
  49. {
  50.     n = avail = nchar;  
  51.     blen = bitlen;  
  52.     tbl = table;
  53.     tblsiz = 1U << tablebits;  
  54.     bit = tblsiz / 2;
  55.     maxdepth = tablebits + 1;
  56.     depth = len = 1;  
  57.     c = -1;  
  58.     codeword = 0;
  59.     (void) mktbl();  /* left subtree */
  60.     (void) mktbl();  /* right subtree */
  61.     if (codeword != tblsiz) error(BROKENARC, "Bad table (5)");
  62. }
  63. #else
  64. void make_table(nchar, bitlen, tablebits, table)
  65. short nchar;
  66. unsigned char bitlen[];
  67. short tablebits;
  68. unsigned short table[];
  69. {
  70.     unsigned short count[17];  /* count of bitlen */
  71.     unsigned short weight[17]; /* 0x10000ul >> bitlen */
  72.     unsigned short start[17];  /* first code of bitlen */
  73.     unsigned short total;
  74.     unsigned int i;
  75.     int j, k, l, m, n, avail;
  76.     unsigned short *p;
  77.  
  78.     avail = nchar;
  79.  
  80.     /* initialize */
  81.     for (i = 1; i <= 16; i++) {
  82.         count[i] = 0;
  83.         weight[i] = 1 << (16 - i);
  84.     }
  85.  
  86.     /* count */
  87.     for (i = 0; i < nchar; i++) count[bitlen[i]]++;
  88.  
  89.     /* calculate first code */
  90.     total = 0;
  91.     for (i = 1; i <= 16; i++) {
  92.         start[i] = total;
  93.         total += weight[i] * count[i];
  94.     }
  95.     if ((total & 0xffff) != 0)
  96.         error("Bad table (5)\n");
  97.  
  98.     /* shift data for make table. */
  99.     m = 16 - tablebits;
  100.     for (i = 1; i <= tablebits; i++) {
  101.         start[i] >>= m;
  102.         weight[i] >>= m;
  103.     }
  104.  
  105.     /* initialize */
  106.     j = start[tablebits + 1] >> m;
  107.     k = 1 << tablebits;
  108.     if (j != 0)
  109.         for (i = j; i < k; i++) table[i] = 0;
  110.  
  111.     /* create table and tree */
  112.     for (j = 0; j < nchar; j++) {
  113.         k = bitlen[j];
  114.         if (k == 0) continue;
  115.         l = start[k] + weight[k];
  116.         if (k <= tablebits) {
  117.             /* code in table */
  118.             for (i = start[k]; i < l; i++) table[i] = j;
  119.         } 
  120.         else {
  121.             /* code not in table */
  122.             p = &table[(i = start[k]) >> m];
  123.             i <<= tablebits;
  124.             n = k - tablebits;
  125.             /* make tree (n length) */
  126.             while (--n >= 0) {
  127.                 if (*p == 0) {
  128.                     right[avail] = left[avail] = 0;
  129.                     *p = avail++;
  130.                 }
  131.                 if (i & 0x8000) p = &right[*p];
  132.                 else            p = &left[*p];
  133.                 i <<= 1;
  134.             }
  135.             *p = j;
  136.         }
  137.         start[k] = l;
  138.     }
  139. }
  140. #endif
  141.  
  142.  
  143.  
  144.