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)\n");
  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 }
  94
  95 /* Local Variables: */
  96 /* mode:c */
  97 /* tab-width:4 */
  98 /* End: */