home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / AR002.LZH / MAKETBL.C < prev    next >
C/C++ Source or Header  |  1990-08-15  |  2KB  |  57 lines
  1. /***********************************************************
  2.     maketbl.c -- make table for decoding
  3. ***********************************************************/
  4. #include "ar.h"
  5.  
  6. void make_table(int nchar, uchar bitlen[], int tablebits, ushort table[])
  7. {
  8.     ushort count[17], weight[17], start[18], *p;
  9.     uint i, k, len, ch, jutbits, avail, nextcode, mask;
  10.  
  11.     for (i = 1; i <= 16; i++) count[i] = 0;
  12.     for (i = 0; i < nchar; i++) count[bitlen[i]]++;
  13.  
  14.     start[1] = 0;
  15.     for (i = 1; i <= 16; i++)
  16.         start[i + 1] = start[i] + (count[i] << (16 - i));
  17.     if (start[17] != (ushort)(1U << 16)) error("Bad table");
  18.  
  19.     jutbits = 16 - tablebits;
  20.     for (i = 1; i <= tablebits; i++) {
  21.         start[i] >>= jutbits;
  22.         weight[i] = 1U << (tablebits - i);
  23.     }
  24.     while (i <= 16) weight[i++] = 1U << (16 - i);
  25.  
  26.     i = start[tablebits + 1] >> jutbits;
  27.     if (i != (ushort)(1U << 16)) {
  28.         k = 1U << tablebits;
  29.         while (i != k) table[i++] = 0;
  30.     }
  31.  
  32.     avail = nchar;
  33.     mask = 1U << (15 - tablebits);
  34.     for (ch = 0; ch < nchar; ch++) {
  35.         if ((len = bitlen[ch]) == 0) continue;
  36.         nextcode = start[len] + weight[len];
  37.         if (len <= tablebits) {
  38.             for (i = start[len]; i < nextcode; i++) table[i] = ch;
  39.         } else {
  40.             k = start[len];
  41.             p = &table[k >> jutbits];
  42.             i = len - tablebits;
  43.             while (i != 0) {
  44.                 if (*p == 0) {
  45.                     right[avail] = left[avail] = 0;
  46.                     *p = avail++;
  47.                 }
  48.                 if (k & mask) p = &right[*p];
  49.                 else          p = &left[*p];
  50.                 k <<= 1;  i--;
  51.             }
  52.             *p = ch;
  53.         }
  54.         start[len] = nextcode;
  55.     }
  56. }
  57.