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         if (bitlen[i] > 16) {
  37             /* CVE-2006-4335 */
  38             error("Bad table (case a)");
  39             exit(1);
  40         }
  41         else
  42             count[bitlen[i]]++;
  43     }
  44
  45     /* calculate first code */
  46     total = 0;
  47     for (i = 1; i <= 16; i++) {
  48         start[i] = total;
  49         total += weight[i] * count[i];
  50     }
  51     if ((total & 0xffff) != 0 || tablebits > 16) { /* 16 for weight below */
  52         error("make_table(): Bad table (case b)");
  53         exit(1);
  54     }
  55
  56     /* shift data for make table. */
  57     m = 16 - tablebits;
  58     for (i = 1; i <= tablebits; i++) {
  59         start[i] >>= m;
  60         weight[i] >>= m;
  61     }
  62
  63     /* initialize */
  64     j = start[tablebits + 1] >> m;
  65     k = MIN(1 << tablebits, 4096);
  66     if (j != 0)
  67         for (i = j; i < k; i++)
  68             table[i] = 0;
  69
  70     /* create table and tree */
  71     for (j = 0; j < nchar; j++) {
  72         k = bitlen[j];
  73         if (k == 0)
  74             continue;
  75         l = start[k] + weight[k];
  76         if (k <= tablebits) {
  77             /* code in table */
  78             l = MIN(l, 4096);
  79             for (i = start[k]; i < l; i++)
  80                 table[i] = j;
  81         }
  82         else {
  83             /* code not in table */
  84             i = start[k];
  85             if ((i >> m) > 4096) {
  86                 /* CVE-2006-4337 */
  87                 error("Bad table (case c)");
  88                 exit(1);
  89             }
  90             p = &table[i >> m];
  91             i <<= tablebits;
  92             n = k - tablebits;
  93             /* make tree (n length) */
  94             while (--n >= 0) {
  95                 if (*p == 0) {
  96                     right[avail] = left[avail] = 0;
  97                     *p = avail++;
  98                 }
  99                 if (i & 0x8000)
 100                     p = &right[*p];
 101                 else
 102                     p = &left[*p];
 103                 i <<= 1;
 104             }
 105             *p = j;
 106         }
 107         start[k] = l;
 108     }
 109 }