maketbl.c

   1 /***********************************************************
   2         maketbl.c -- make table for decoding
   3 ***********************************************************/
   4 #include "ar.h"
   5
   6 void
   7 make_table(int nchar, uchar bitlen[], int tablebits, ushort table[])
   8 {
   9     ushort count[17], weight[17], start[18], *p;
  10     uint i, k, len, ch, jutbits, avail, nextcode, mask;
  11
  12     for (i = 1; i <= 16; i++)
  13         count[i] = 0;
  14     for (i = 0; i < nchar; i++)
  15         count[bitlen[i]]++;
  16
  17     start[1] = 0;
  18     for (i = 1; i <= 16; i++)
  19         start[i + 1] = start[i] + (count[i] << (16 - i));
  20     if (start[17] != (ushort) (1U << 16))
  21         error("Bad table");
  22
  23     jutbits = 16 - tablebits;
  24     for (i = 1; i <= tablebits; i++) {
  25         start[i] >>= jutbits;
  26         weight[i] = 1U << (tablebits - i);
  27     }
  28     while (i <= 16) {
  29         weight[i] = 1U << (16 - i);
  30         i++;
  31     }
  32
  33     i = start[tablebits + 1] >> jutbits;
  34     if (i != (ushort) (1U << 16)) {
  35         k = 1U << tablebits;
  36         while (i != k)
  37             table[i++] = 0;
  38     }
  39
  40     avail = nchar;
  41     mask = 1U << (15 - tablebits);
  42     for (ch = 0; ch < nchar; ch++) {
  43         if ((len = bitlen[ch]) == 0)
  44             continue;
  45         nextcode = start[len] + weight[len];
  46         if (len <= tablebits) {
  47             for (i = start[len]; i < nextcode; i++)
  48                 table[i] = ch;
  49         }
  50         else {
  51             k = start[len];
  52             p = &table[k >> jutbits];
  53             i = len - tablebits;
  54             while (i != 0) {
  55                 if (*p == 0) {
  56                     right[avail] = left[avail] = 0;
  57                     *p = avail++;
  58                 }
  59                 if (k & mask)
  60                     p = &right[*p];
  61                 else
  62                     p = &left[*p];
  63                 k <<= 1;
  64                 i--;
  65             }
  66             *p = ch;
  67         }
  68         start[len] = nextcode;
  69     }
  70 }