src/maketbl.c

   1 /* ------------------------------------------------------------------------ */
   2 /* LHa for UNIX                                                             */
   3 /*              maketbl.c -- makes decoding table                           */
   4 /*                                                                          */
   5 /*      Modified                Nobutaka Watazaki                           */
   6 /*                                                                          */
   7 /*  Ver. 1.14   Source All chagned              1995.01.14  N.Watazaki      */
   8 /* ------------------------------------------------------------------------ */
   9 #include "lha.h"
  10
  11 void
  12 make_table(nchar, bitlen, tablebits, table)
  13     short           nchar;
  14     unsigned char   bitlen[];
  15     short           tablebits;
  16     unsigned short  table[];
  17 {
  18     unsigned short  count[17];  /* count of bitlen */
  19     unsigned short  weight[17]; /* 0x10000ul >> bitlen */
  20     unsigned short  start[17];  /* first code of bitlen */
  21     unsigned short  total;
  22     unsigned int    i, l;
  23     int             j, k, m, n, avail;
  24     unsigned short *p;
  25
  26     avail = nchar;
  27
  28     /* initialize */
  29     for (i = 1; i <= 16; i++) {
  30         count[i] = 0;
  31         weight[i] = 1 << (16 - i);
  32     }
  33
  34     /* count */
  35     for (i = 0; i < nchar; i++)
  36         count[bitlen[i]]++;
  37
  38     /* calculate first code */
  39     total = 0;
  40     for (i = 1; i <= 16; i++) {
  41         start[i] = total;
  42         total += weight[i] * count[i];
  43     }
  44     if ((total & 0xffff) != 0)
  45         error("make_table(): Bad table (5)");
  46
  47     /* shift data for make table. */
  48     m = 16 - tablebits;
  49     for (i = 1; i <= tablebits; i++) {
  50         start[i] >>= m;
  51         weight[i] >>= m;
  52     }
  53
  54     /* initialize */
  55     j = start[tablebits + 1] >> m;
  56     k = 1 << tablebits;
  57     if (j != 0)
  58         for (i = j; i < k; i++)
  59             table[i] = 0;
  60
  61     /* create table and tree */
  62     for (j = 0; j < nchar; j++) {
  63         k = bitlen[j];
  64         if (k == 0)
  65             continue;
  66         l = start[k] + weight[k];
  67         if (k <= tablebits) {
  68             /* code in table */
  69             for (i = start[k]; i < l; i++)
  70                 table[i] = j;
  71         }
  72         else {
  73             /* code not in table */
  74             p = &table[(i = start[k]) >> m];
  75             i <<= tablebits;
  76             n = k - tablebits;
  77             /* make tree (n length) */
  78             while (--n >= 0) {
  79                 if (*p == 0) {
  80                     right[avail] = left[avail] = 0;
  81                     *p = avail++;
  82                 }
  83                 if (i & 0x8000)
  84                     p = &right[*p];
  85                 else
  86                     p = &left[*p];
  87                 i <<= 1;
  88             }
  89             *p = j;
  90         }
  91         start[k] = l;
  92     }
  93 }