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