source: trip-planner-front/node_modules/pako/lib/zlib/inftrees.js@ 188ee53

Last change on this file since 188ee53 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

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