main
1import * as utils from "../utils/common.js";
2
3var MAXBITS = 15;
4var ENOUGH_LENS = 852;
5var ENOUGH_DISTS = 592;
6//var ENOUGH = (ENOUGH_LENS+ENOUGH_DISTS);
7
8var CODES = 0;
9var LENS = 1;
10var DISTS = 2;
11
12var lbase = [ /* Length codes 257..285 base */
13 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
14 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
15];
16
17var lext = [ /* Length codes 257..285 extra */
18 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
19 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 72, 78
20];
21
22var dbase = [ /* Distance codes 0..29 base */
23 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
24 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
25 8193, 12289, 16385, 24577, 0, 0
26];
27
28var dext = [ /* Distance codes 0..29 extra */
29 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
30 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
31 28, 28, 29, 29, 64, 64
32];
33
34export default function inflate_table(type, lens, lens_index, codes, table, table_index, work, opts)
35{
36 var bits = opts.bits;
37 //here = opts.here; /* table entry for duplication */
38
39 var len = 0; /* a code's length in bits */
40 var sym = 0; /* index of code symbols */
41 var min = 0, max = 0; /* minimum and maximum code lengths */
42 var root = 0; /* number of index bits for root table */
43 var curr = 0; /* number of index bits for current table */
44 var drop = 0; /* code bits to drop for sub-table */
45 var left = 0; /* number of prefix codes available */
46 var used = 0; /* code entries in table used */
47 var huff = 0; /* Huffman code */
48 var incr; /* for incrementing code, index */
49 var fill; /* index for replicating entries */
50 var low; /* low bits for current root entry */
51 var mask; /* mask for low root bits */
52 var next; /* next available space in table */
53 var base = null; /* base value table to use */
54 var base_index = 0;
55// var shoextra; /* extra bits table to use */
56 var end; /* use base and extra for symbol > end */
57 var count = new utils.Buf16(MAXBITS + 1); //[MAXBITS+1]; /* number of codes of each length */
58 var offs = new utils.Buf16(MAXBITS + 1); //[MAXBITS+1]; /* offsets in table for each length */
59 var extra = null;
60 var extra_index = 0;
61
62 var here_bits, here_op, here_val;
63
64 /*
65 Process a set of code lengths to create a canonical Huffman code. The
66 code lengths are lens[0..codes-1]. Each length corresponds to the
67 symbols 0..codes-1. The Huffman code is generated by first sorting the
68 symbols by length from short to long, and retaining the symbol order
69 for codes with equal lengths. Then the code starts with all zero bits
70 for the first code of the shortest length, and the codes are integer
71 increments for the same length, and zeros are appended as the length
72 increases. For the deflate format, these bits are stored backwards
73 from their more natural integer increment ordering, and so when the
74 decoding tables are built in the large loop below, the integer codes
75 are incremented backwards.
76
77 This routine assumes, but does not check, that all of the entries in
78 lens[] are in the range 0..MAXBITS. The caller must assure this.
79 1..MAXBITS is interpreted as that code length. zero means that that
80 symbol does not occur in this code.
81
82 The codes are sorted by computing a count of codes for each length,
83 creating from that a table of starting indices for each length in the
84 sorted table, and then entering the symbols in order in the sorted
85 table. The sorted table is work[], with that space being provided by
86 the caller.
87
88 The length counts are used for other purposes as well, i.e. finding
89 the minimum and maximum length codes, determining if there are any
90 codes at all, checking for a valid set of lengths, and looking ahead
91 at length counts to determine sub-table sizes when building the
92 decoding tables.
93 */
94
95 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
96 for (len = 0; len <= MAXBITS; len++) {
97 count[len] = 0;
98 }
99 for (sym = 0; sym < codes; sym++) {
100 count[lens[lens_index + sym]]++;
101 }
102
103 /* bound code lengths, force root to be within code lengths */
104 root = bits;
105 for (max = MAXBITS; max >= 1; max--) {
106 if (count[max] !== 0) { break; }
107 }
108 if (root > max) {
109 root = max;
110 }
111 if (max === 0) { /* no symbols to code at all */
112 //table.op[opts.table_index] = 64; //here.op = (var char)64; /* invalid code marker */
113 //table.bits[opts.table_index] = 1; //here.bits = (var char)1;
114 //table.val[opts.table_index++] = 0; //here.val = (var short)0;
115 table[table_index++] = (1 << 24) | (64 << 16) | 0;
116
117
118 //table.op[opts.table_index] = 64;
119 //table.bits[opts.table_index] = 1;
120 //table.val[opts.table_index++] = 0;
121 table[table_index++] = (1 << 24) | (64 << 16) | 0;
122
123 opts.bits = 1;
124 return 0; /* no symbols, but wait for decoding to report error */
125 }
126 for (min = 1; min < max; min++) {
127 if (count[min] !== 0) { break; }
128 }
129 if (root < min) {
130 root = min;
131 }
132
133 /* check for an over-subscribed or incomplete set of lengths */
134 left = 1;
135 for (len = 1; len <= MAXBITS; len++) {
136 left <<= 1;
137 left -= count[len];
138 if (left < 0) {
139 return -1;
140 } /* over-subscribed */
141 }
142 if (left > 0 && (type === CODES || max !== 1)) {
143 return -1; /* incomplete set */
144 }
145
146 /* generate offsets into symbol table for each length for sorting */
147 offs[1] = 0;
148 for (len = 1; len < MAXBITS; len++) {
149 offs[len + 1] = offs[len] + count[len];
150 }
151
152 /* sort symbols by length, by symbol order within each length */
153 for (sym = 0; sym < codes; sym++) {
154 if (lens[lens_index + sym] !== 0) {
155 work[offs[lens[lens_index + sym]]++] = sym;
156 }
157 }
158
159 /*
160 Create and fill in decoding tables. In this loop, the table being
161 filled is at next and has curr index bits. The code being used is huff
162 with length len. That code is converted to an index by dropping drop
163 bits off of the bottom. For codes where len is less than drop + curr,
164 those top drop + curr - len bits are incremented through all values to
165 fill the table with replicated entries.
166
167 root is the number of index bits for the root table. When len exceeds
168 root, sub-tables are created pointed to by the root entry with an index
169 of the low root bits of huff. This is saved in low to check for when a
170 new sub-table should be started. drop is zero when the root table is
171 being filled, and drop is root when sub-tables are being filled.
172
173 When a new sub-table is needed, it is necessary to look ahead in the
174 code lengths to determine what size sub-table is needed. The length
175 counts are used for this, and so count[] is decremented as codes are
176 entered in the tables.
177
178 used keeps track of how many table entries have been allocated from the
179 provided *table space. It is checked for LENS and DIST tables against
180 the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in
181 the initial root table size constants. See the comments in inftrees.h
182 for more information.
183
184 sym increments through all symbols, and the loop terminates when
185 all codes of length max, i.e. all codes, have been processed. This
186 routine permits incomplete codes, so another loop after this one fills
187 in the rest of the decoding tables with invalid code markers.
188 */
189
190 /* set up for code type */
191 // poor man optimization - use if-else instead of switch,
192 // to avoid deopts in old v8
193 if (type === CODES) {
194 base = extra = work; /* dummy value--not used */
195 end = 19;
196
197 } else if (type === LENS) {
198 base = lbase;
199 base_index -= 257;
200 extra = lext;
201 extra_index -= 257;
202 end = 256;
203
204 } else { /* DISTS */
205 base = dbase;
206 extra = dext;
207 end = -1;
208 }
209
210 /* initialize opts for loop */
211 huff = 0; /* starting code */
212 sym = 0; /* starting code symbol */
213 len = min; /* starting code length */
214 next = table_index; /* current table to fill in */
215 curr = root; /* current table index bits */
216 drop = 0; /* current bits to drop from code for index */
217 low = -1; /* trigger new sub-table when len > root */
218 used = 1 << root; /* use root table entries */
219 mask = used - 1; /* mask for comparing low */
220
221 /* check available table space */
222 if ((type === LENS && used > ENOUGH_LENS) ||
223 (type === DISTS && used > ENOUGH_DISTS)) {
224 return 1;
225 }
226
227 /* process all codes and make table entries */
228 for (;;) {
229 /* create table entry */
230 here_bits = len - drop;
231 if (work[sym] < end) {
232 here_op = 0;
233 here_val = work[sym];
234 }
235 else if (work[sym] > end) {
236 here_op = extra[extra_index + work[sym]];
237 here_val = base[base_index + work[sym]];
238 }
239 else {
240 here_op = 32 + 64; /* end of block */
241 here_val = 0;
242 }
243
244 /* replicate for those indices with low len bits equal to huff */
245 incr = 1 << (len - drop);
246 fill = 1 << curr;
247 min = fill; /* save offset to next table */
248 do {
249 fill -= incr;
250 table[next + (huff >> drop) + fill] = (here_bits << 24) | (here_op << 16) | here_val |0;
251 } while (fill !== 0);
252
253 /* backwards increment the len-bit code huff */
254 incr = 1 << (len - 1);
255 while (huff & incr) {
256 incr >>= 1;
257 }
258 if (incr !== 0) {
259 huff &= incr - 1;
260 huff += incr;
261 } else {
262 huff = 0;
263 }
264
265 /* go to next symbol, update count, len */
266 sym++;
267 if (--count[len] === 0) {
268 if (len === max) { break; }
269 len = lens[lens_index + work[sym]];
270 }
271
272 /* create new sub-table if needed */
273 if (len > root && (huff & mask) !== low) {
274 /* if first time, transition to sub-tables */
275 if (drop === 0) {
276 drop = root;
277 }
278
279 /* increment past last table */
280 next += min; /* here min is 1 << curr */
281
282 /* determine length of next table */
283 curr = len - drop;
284 left = 1 << curr;
285 while (curr + drop < max) {
286 left -= count[curr + drop];
287 if (left <= 0) { break; }
288 curr++;
289 left <<= 1;
290 }
291
292 /* check for enough space */
293 used += 1 << curr;
294 if ((type === LENS && used > ENOUGH_LENS) ||
295 (type === DISTS && used > ENOUGH_DISTS)) {
296 return 1;
297 }
298
299 /* point entry in root table to sub-table */
300 low = huff & mask;
301 /*table.op[low] = curr;
302 table.bits[low] = root;
303 table.val[low] = next - opts.table_index;*/
304 table[low] = (root << 24) | (curr << 16) | (next - table_index) |0;
305 }
306 }
307
308 /* fill in remaining table entry if code is incomplete (guaranteed to have
309 at most one remaining entry, since if the code is incomplete, the
310 maximum code length that was allowed to get this far is one bit) */
311 if (huff !== 0) {
312 //table.op[next + huff] = 64; /* invalid code marker */
313 //table.bits[next + huff] = len - drop;
314 //table.val[next + huff] = 0;
315 table[next + huff] = ((len - drop) << 24) | (64 << 16) |0;
316 }
317
318 /* set return parameters */
319 //opts.table_index += used;
320 opts.bits = root;
321 return 0;
322};