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
make_table(nchar,bitlen,tablebits,table)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: */
99