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
  31     i = start[tablebits + 1] >> jutbits;
  32     if (i != (ushort) (1U << 16)) {
  33         k = 1U << tablebits;
  34         while (i != k)
  35             table[i++] = 0;
  36     }
  37
  38     avail = nchar;
  39     mask = 1U << (15 - tablebits);
  40     for (ch = 0; ch < nchar; ch++) {
  41         if ((len = bitlen[ch]) == 0)
  42             continue;
  43         nextcode = start[len] + weight[len];
  44         if (len <= tablebits) {
  45             for (i = start[len]; i < nextcode; i++)
  46                 table[i] = ch;
  47         }
  48         else {
  49             k = start[len];
  50             p = &table[k >> jutbits];
  51             i = len - tablebits;
  52             while (i != 0) {
  53                 if (*p == 0) {
  54                     right[avail] = left[avail] = 0;
  55                     *p = avail++;
  56                 }
  57                 if (k & mask)
  58                     p = &right[*p];
  59                 else
  60                     p = &left[*p];
  61                 k <<= 1;
  62                 i--;
  63             }
  64             *p = ch;
  65         }
  66         start[len] = nextcode;
  67     }
  68 }