Line data Source code
1 : /*
2 : * tinflate - tiny inflate
3 : *
4 : * Copyright (c) 2003 by Joergen Ibsen / Jibz
5 : * All Rights Reserved
6 : * http://www.ibsensoftware.com/
7 : *
8 : * Copyright (c) 2014-2016 by Paul Sokolovsky
9 : *
10 : * This software is provided 'as-is', without any express
11 : * or implied warranty. In no event will the authors be
12 : * held liable for any damages arising from the use of
13 : * this software.
14 : *
15 : * Permission is granted to anyone to use this software
16 : * for any purpose, including commercial applications,
17 : * and to alter it and redistribute it freely, subject to
18 : * the following restrictions:
19 : *
20 : * 1. The origin of this software must not be
21 : * misrepresented; you must not claim that you
22 : * wrote the original software. If you use this
23 : * software in a product, an acknowledgment in
24 : * the product documentation would be appreciated
25 : * but is not required.
26 : *
27 : * 2. Altered source versions must be plainly marked
28 : * as such, and must not be misrepresented as
29 : * being the original software.
30 : *
31 : * 3. This notice may not be removed or altered from
32 : * any source distribution.
33 : */
34 :
35 : /*
36 : minor changes for C++ build for ArduPilot by tridge
37 : */
38 :
39 : #include <assert.h>
40 : #include "tinf.h"
41 :
42 : uint32_t tinf_get_le_uint32(TINF_DATA *d);
43 : uint32_t tinf_get_be_uint32(TINF_DATA *d);
44 :
45 : /* --------------------------------------------------- *
46 : * -- uninitialized global data (static structures) -- *
47 : * --------------------------------------------------- */
48 :
49 : #ifdef RUNTIME_BITS_TABLES
50 :
51 : /* extra bits and base tables for length codes */
52 : unsigned char length_bits[30];
53 : unsigned short length_base[30];
54 :
55 : /* extra bits and base tables for distance codes */
56 : unsigned char dist_bits[30];
57 : unsigned short dist_base[30];
58 :
59 : #else
60 :
61 : static const unsigned char length_bits[30] = {
62 : 0, 0, 0, 0, 0, 0, 0, 0,
63 : 1, 1, 1, 1, 2, 2, 2, 2,
64 : 3, 3, 3, 3, 4, 4, 4, 4,
65 : 5, 5, 5, 5
66 : };
67 : static const unsigned short length_base[30] = {
68 : 3, 4, 5, 6, 7, 8, 9, 10,
69 : 11, 13, 15, 17, 19, 23, 27, 31,
70 : 35, 43, 51, 59, 67, 83, 99, 115,
71 : 131, 163, 195, 227, 258
72 : };
73 :
74 : static const unsigned char dist_bits[30] = {
75 : 0, 0, 0, 0, 1, 1, 2, 2,
76 : 3, 3, 4, 4, 5, 5, 6, 6,
77 : 7, 7, 8, 8, 9, 9, 10, 10,
78 : 11, 11, 12, 12, 13, 13
79 : };
80 : static const unsigned short dist_base[30] = {
81 : 1, 2, 3, 4, 5, 7, 9, 13,
82 : 17, 25, 33, 49, 65, 97, 129, 193,
83 : 257, 385, 513, 769, 1025, 1537, 2049, 3073,
84 : 4097, 6145, 8193, 12289, 16385, 24577
85 : };
86 :
87 : #endif
88 :
89 : /* special ordering of code length codes */
90 : static const unsigned char clcidx[] = {
91 : 16, 17, 18, 0, 8, 7, 9, 6,
92 : 10, 5, 11, 4, 12, 3, 13, 2,
93 : 14, 1, 15
94 : };
95 :
96 : /* ----------------------- *
97 : * -- utility functions -- *
98 : * ----------------------- */
99 :
100 : #ifdef RUNTIME_BITS_TABLES
101 : /* build extra bits and base tables */
102 : static void tinf_build_bits_base(unsigned char *bits, unsigned short *base, int delta, int first)
103 : {
104 : int i, sum;
105 :
106 : /* build bits table */
107 : for (i = 0; i < delta; ++i) bits[i] = 0;
108 : for (i = 0; i < 30 - delta; ++i) bits[i + delta] = i / delta;
109 :
110 : /* build base table */
111 : for (sum = first, i = 0; i < 30; ++i)
112 : {
113 : base[i] = sum;
114 : sum += 1 << bits[i];
115 : }
116 : }
117 : #endif
118 :
119 : /* build the fixed huffman trees */
120 4004 : static void tinf_build_fixed_trees(TINF_TREE *lt, TINF_TREE *dt)
121 : {
122 : int i;
123 :
124 : /* build fixed length tree */
125 32032 : for (i = 0; i < 7; ++i) lt->table[i] = 0;
126 :
127 4004 : lt->table[7] = 24;
128 4004 : lt->table[8] = 152;
129 4004 : lt->table[9] = 112;
130 :
131 100100 : for (i = 0; i < 24; ++i) lt->trans[i] = 256 + i;
132 580580 : for (i = 0; i < 144; ++i) lt->trans[24 + i] = i;
133 36036 : for (i = 0; i < 8; ++i) lt->trans[24 + 144 + i] = 280 + i;
134 452452 : for (i = 0; i < 112; ++i) lt->trans[24 + 144 + 8 + i] = 144 + i;
135 :
136 : /* build fixed distance tree */
137 24024 : for (i = 0; i < 5; ++i) dt->table[i] = 0;
138 :
139 4004 : dt->table[5] = 32;
140 :
141 132132 : for (i = 0; i < 32; ++i) dt->trans[i] = i;
142 4004 : }
143 :
144 : /* given an array of code lengths, build a tree */
145 30843 : static void tinf_build_tree(TINF_TREE *t, const unsigned char *lengths, unsigned int num)
146 : {
147 : unsigned short offs[16];
148 : unsigned int i, sum;
149 :
150 : /* clear code length count table */
151 524331 : for (i = 0; i < 16; ++i) t->table[i] = 0;
152 :
153 : /* scan symbol lengths, and sum code length counts */
154 3278181 : for (i = 0; i < num; ++i) t->table[lengths[i]]++;
155 :
156 30843 : t->table[0] = 0;
157 :
158 : /* compute offset table for distribution sort */
159 524331 : for (sum = 0, i = 0; i < 16; ++i)
160 : {
161 493488 : offs[i] = sum;
162 493488 : sum += t->table[i];
163 : }
164 :
165 : /* create code->symbol translation table (symbols sorted by code) */
166 3278181 : for (i = 0; i < num; ++i)
167 : {
168 3247338 : if (lengths[i]) t->trans[offs[lengths[i]]++] = i;
169 : }
170 30843 : }
171 :
172 : /* ---------------------- *
173 : * -- decode functions -- *
174 : * ---------------------- */
175 :
176 8311788 : unsigned char uzlib_get_byte(TINF_DATA *d)
177 : {
178 : /* If end of source buffer is not reached, return next byte from source
179 : buffer. */
180 8311788 : if (d->source < d->source_limit) {
181 8311788 : return *d->source++;
182 : }
183 :
184 : /* Otherwise if there's callback and we haven't seen EOF yet, try to
185 : read next byte using it. (Note: the callback can also update ->source
186 : and ->source_limit). */
187 0 : if (d->readSource && !d->eof) {
188 0 : int val = d->readSource(d);
189 0 : if (val >= 0) {
190 0 : return (unsigned char)val;
191 : }
192 : }
193 :
194 : /* Otherwise, we hit EOF (either from ->readSource() or from exhaustion
195 : of the buffer), and it will be "sticky", i.e. further calls to this
196 : function will end up here too. */
197 0 : d->eof = true;
198 :
199 0 : return 0;
200 : }
201 :
202 0 : uint32_t tinf_get_le_uint32(TINF_DATA *d)
203 : {
204 0 : uint32_t val = 0;
205 : int i;
206 0 : for (i = 4; i--;) {
207 0 : val = val >> 8 | ((uint32_t)uzlib_get_byte(d)) << 24;
208 : }
209 0 : return val;
210 : }
211 :
212 0 : uint32_t tinf_get_be_uint32(TINF_DATA *d)
213 : {
214 0 : uint32_t val = 0;
215 : int i;
216 0 : for (i = 4; i--;) {
217 0 : val = val << 8 | uzlib_get_byte(d);
218 : }
219 0 : return val;
220 : }
221 :
222 : /* get one bit from source stream */
223 66443094 : static int tinf_getbit(TINF_DATA *d)
224 : {
225 : unsigned int bit;
226 :
227 : /* check if tag is empty */
228 66443094 : if (!d->bitcount--)
229 : {
230 : /* load next tag */
231 8311788 : d->tag = uzlib_get_byte(d);
232 8311788 : d->bitcount = 7;
233 : }
234 :
235 : /* shift bit out of tag */
236 66443094 : bit = d->tag & 0x01;
237 66443094 : d->tag >>= 1;
238 :
239 66443094 : return bit;
240 : }
241 :
242 : /* read a num bit value from a stream and add base */
243 4563442 : static unsigned int tinf_read_bits(TINF_DATA *d, int num, int base)
244 : {
245 4563442 : unsigned int val = 0;
246 :
247 : /* read num bits */
248 4563442 : if (num)
249 : {
250 3467274 : unsigned int limit = 1 << (num);
251 : unsigned int mask;
252 :
253 19707824 : for (mask = 1; mask < limit; mask *= 2)
254 16240550 : if (tinf_getbit(d)) val += mask;
255 : }
256 :
257 4563442 : return val + base;
258 : }
259 :
260 : /* given a data stream and a tree, decode a symbol */
261 9875422 : static int tinf_decode_symbol(TINF_DATA *d, TINF_TREE *t)
262 : {
263 9875422 : int sum = 0, cur = 0, len = 0;
264 :
265 : /* get more bits while code value is above sum */
266 : do {
267 :
268 50188259 : cur = 2*cur + tinf_getbit(d);
269 :
270 50188259 : if (++len == TINF_ARRAY_SIZE(t->table)) {
271 0 : return TINF_DATA_ERROR;
272 : }
273 :
274 50188259 : sum += t->table[len];
275 50188259 : cur -= t->table[len];
276 :
277 50188259 : } while (cur >= 0);
278 :
279 9875422 : sum += cur;
280 9875422 : if (sum < 0 || sum >= (int)(TINF_ARRAY_SIZE(t->trans))) {
281 0 : return TINF_DATA_ERROR;
282 : }
283 :
284 9875422 : return t->trans[sum];
285 : }
286 :
287 : /* given a data stream, decode dynamic trees from it */
288 10281 : static int tinf_decode_trees(TINF_DATA *d, TINF_TREE *lt, TINF_TREE *dt)
289 : {
290 : unsigned char lengths[288+32];
291 : unsigned int hlit, hdist, hclen, hlimit;
292 : unsigned int i, num, length;
293 :
294 : /* get 5 bits HLIT (257-286) */
295 10281 : hlit = tinf_read_bits(d, 5, 257);
296 :
297 : /* get 5 bits HDIST (1-32) */
298 10281 : hdist = tinf_read_bits(d, 5, 1);
299 :
300 : /* get 4 bits HCLEN (4-19) */
301 10281 : hclen = tinf_read_bits(d, 4, 4);
302 :
303 205620 : for (i = 0; i < 19; ++i) lengths[i] = 0;
304 :
305 : /* read code lengths for code length alphabet */
306 170655 : for (i = 0; i < hclen; ++i)
307 : {
308 : /* get 3 bits code length (0-7) */
309 160374 : unsigned int clen = tinf_read_bits(d, 3, 0);
310 :
311 160374 : lengths[clcidx[i]] = clen;
312 : }
313 :
314 : /* build code length tree, temporarily use length tree */
315 10281 : tinf_build_tree(lt, lengths, 19);
316 :
317 : /* decode code lengths for the dynamic trees */
318 10281 : hlimit = hlit + hdist;
319 1130830 : for (num = 0; num < hlimit; )
320 : {
321 1120549 : int sym = tinf_decode_symbol(d, lt);
322 1120549 : unsigned char fill_value = 0;
323 1120549 : int lbits, lbase = 3;
324 :
325 : /* error decoding */
326 1120549 : if (sym < 0) return sym;
327 :
328 1120549 : switch (sym)
329 : {
330 9062 : case 16:
331 9062 : if (num == 0) {
332 0 : return TINF_DATA_ERROR;
333 : }
334 : /* copy previous code length 3-6 times (read 2 bits) */
335 9062 : fill_value = lengths[num - 1];
336 9062 : lbits = 2;
337 9062 : break;
338 50744 : case 17:
339 : /* repeat code length 0 for 3-10 times (read 3 bits) */
340 50744 : lbits = 3;
341 50744 : break;
342 23360 : case 18:
343 : /* repeat code length 0 for 11-138 times (read 7 bits) */
344 23360 : lbits = 7;
345 23360 : lbase = 11;
346 23360 : break;
347 1037383 : default:
348 : /* values 0-15 represent the actual code lengths */
349 1037383 : lengths[num++] = sym;
350 : /* continue the for loop */
351 1037383 : continue;
352 : }
353 :
354 : /* special code length 16-18 are handled here */
355 83166 : length = tinf_read_bits(d, lbits, lbase);
356 83166 : if (num + length > hlimit) return TINF_DATA_ERROR;
357 2097782 : for (; length; --length)
358 : {
359 2014616 : lengths[num++] = fill_value;
360 : }
361 : }
362 :
363 : /* build dynamic trees */
364 10281 : tinf_build_tree(lt, lengths, hlit);
365 10281 : tinf_build_tree(dt, lengths + hlit, hdist);
366 :
367 10281 : return TINF_OK;
368 : }
369 :
370 : /* ----------------------------- *
371 : * -- block inflate functions -- *
372 : * ----------------------------- */
373 :
374 : /* given a stream and two trees, inflate a block of data */
375 72984591 : static int tinf_inflate_block_data(TINF_DATA *d, TINF_TREE *lt, TINF_TREE *dt)
376 : {
377 72984591 : if (d->curlen == 0) {
378 : unsigned int offs;
379 : int dist;
380 6617486 : int sym = tinf_decode_symbol(d, lt);
381 : //printf("huff sym: %02x\n", sym);
382 :
383 6617486 : if (d->eof) {
384 0 : return TINF_DATA_ERROR;
385 : }
386 :
387 : /* literal byte */
388 6617486 : if (sym < 256) {
389 4480099 : TINF_PUT(d, sym);
390 4480099 : return TINF_OK;
391 : }
392 :
393 : /* end of block */
394 2137387 : if (sym == 256) {
395 0 : return TINF_DONE;
396 : }
397 :
398 : /* substring from sliding dictionary */
399 2137387 : sym -= 257;
400 : /* possibly get more bits from length code */
401 2137387 : d->curlen = tinf_read_bits(d, length_bits[sym], length_base[sym]);
402 :
403 2137387 : dist = tinf_decode_symbol(d, dt);
404 2137387 : if (dist < 0) {
405 0 : return dist;
406 : }
407 : /* possibly get more bits from distance code */
408 2137387 : offs = tinf_read_bits(d, dist_bits[dist], dist_base[dist]);
409 2137387 : if (d->dict_ring) {
410 0 : if (offs > d->dict_size) {
411 0 : return TINF_DICT_ERROR;
412 : }
413 0 : d->lzOff = d->dict_idx - offs;
414 0 : if (d->lzOff < 0) {
415 0 : d->lzOff += d->dict_size;
416 : }
417 : } else {
418 2137387 : d->lzOff = -offs;
419 : }
420 : }
421 :
422 : /* copy next byte from dict substring */
423 68504492 : if (d->dict_ring) {
424 0 : TINF_PUT(d, d->dict_ring[d->lzOff]);
425 0 : if ((unsigned)++d->lzOff == d->dict_size) {
426 0 : d->lzOff = 0;
427 : }
428 : } else {
429 68504492 : d->dest[0] = d->dest[d->lzOff];
430 68504492 : d->dest++;
431 : }
432 68504492 : d->curlen--;
433 68504492 : return TINF_OK;
434 : }
435 :
436 : /* inflate an uncompressed block of data */
437 0 : static int tinf_inflate_uncompressed_block(TINF_DATA *d)
438 : {
439 0 : if (d->curlen == 0) {
440 : unsigned int length, invlength;
441 :
442 : /* get length */
443 0 : length = uzlib_get_byte(d);
444 0 : length += 256 * uzlib_get_byte(d);
445 : /* get one's complement of length */
446 0 : invlength = uzlib_get_byte(d);
447 0 : invlength += 256 * uzlib_get_byte(d);
448 : /* check length */
449 0 : if (length != (~invlength & 0x0000ffff)) return TINF_DATA_ERROR;
450 :
451 : /* increment length to properly return TINF_DONE below, without
452 : producing data at the same time */
453 0 : d->curlen = length + 1;
454 :
455 : /* make sure we start next block on a byte boundary */
456 0 : d->bitcount = 0;
457 : }
458 :
459 0 : if (--d->curlen == 0) {
460 0 : return TINF_DONE;
461 : }
462 :
463 0 : unsigned char c = uzlib_get_byte(d);
464 0 : TINF_PUT(d, c);
465 0 : return TINF_OK;
466 : }
467 :
468 : /* ---------------------- *
469 : * -- public functions -- *
470 : * ---------------------- */
471 :
472 : /* initialize global (static) data */
473 0 : void uzlib_init(void)
474 : {
475 : #ifdef RUNTIME_BITS_TABLES
476 : /* build extra bits and base tables */
477 : tinf_build_bits_base(length_bits, length_base, 4, 3);
478 : tinf_build_bits_base(dist_bits, dist_base, 2, 1);
479 :
480 : /* fix a special case */
481 : length_bits[28] = 0;
482 : length_base[28] = 258;
483 : #endif
484 0 : }
485 :
486 : /* initialize decompression structure */
487 14285 : void uzlib_uncompress_init(TINF_DATA *d, void *dict, unsigned int dictLen)
488 : {
489 14285 : d->eof = 0;
490 14285 : d->source_limit = NULL;
491 14285 : d->readSource = NULL;
492 14285 : d->bitcount = 0;
493 14285 : d->bfinal = 0;
494 14285 : d->btype = -1;
495 14285 : d->dict_size = dictLen;
496 14285 : d->dict_ring = (unsigned char *)dict;
497 14285 : d->dict_idx = 0;
498 14285 : d->curlen = 0;
499 14285 : }
500 :
501 : /* inflate next byte of compressed stream */
502 72984591 : int uzlib_uncompress(TINF_DATA *d)
503 : {
504 : do {
505 : int res;
506 :
507 : /* start a new block */
508 72984591 : if (d->btype == -1) {
509 14285 : next_blk:
510 : /* read final block flag */
511 14285 : d->bfinal = tinf_getbit(d);
512 : /* read block type (2 bits) */
513 14285 : d->btype = tinf_read_bits(d, 2, 0);
514 :
515 : //printf("Started new block: type=%d final=%d\n", d->btype, d->bfinal);
516 :
517 14285 : if (d->btype == 1) {
518 : /* build fixed huffman trees */
519 4004 : tinf_build_fixed_trees(&d->ltree, &d->dtree);
520 10281 : } else if (d->btype == 2) {
521 : /* decode trees from stream */
522 10281 : res = tinf_decode_trees(d, &d->ltree, &d->dtree);
523 10281 : if (res != TINF_OK) {
524 0 : return res;
525 : }
526 : }
527 : }
528 :
529 : /* process current block */
530 72984591 : switch (d->btype)
531 : {
532 0 : case 0:
533 : /* decompress uncompressed block */
534 0 : res = tinf_inflate_uncompressed_block(d);
535 0 : break;
536 72984591 : case 1:
537 : case 2:
538 : /* decompress block with fixed/dynamic huffman trees */
539 : /* trees were decoded previously, so it's the same routine for both */
540 72984591 : res = tinf_inflate_block_data(d, &d->ltree, &d->dtree);
541 72984591 : break;
542 0 : default:
543 0 : return TINF_DATA_ERROR;
544 : }
545 :
546 72984591 : if (res == TINF_DONE && !d->bfinal) {
547 : /* the block has ended (without producing more data), but we
548 : can't return without data, so start procesing next block */
549 0 : goto next_blk;
550 : }
551 :
552 72984591 : if (res != TINF_OK) {
553 0 : return res;
554 : }
555 :
556 72984591 : } while (--d->destSize);
557 :
558 14285 : return TINF_OK;
559 : }
560 :
561 : #if 0
562 : int uzlib_uncompress_chksum(TINF_DATA *d)
563 : {
564 : int res;
565 : unsigned char *data = d->dest;
566 :
567 : res = uzlib_uncompress(d);
568 :
569 : if (res < 0) return res;
570 :
571 : switch (d->checksum_type) {
572 :
573 : case TINF_CHKSUM_ADLER:
574 : d->checksum = uzlib_adler32(data, d->dest - data, d->checksum);
575 : break;
576 :
577 : case TINF_CHKSUM_CRC:
578 : d->checksum = uzlib_crc32(data, d->dest - data, d->checksum);
579 : break;
580 : }
581 :
582 : if (res == TINF_DONE) {
583 : unsigned int val;
584 :
585 : switch (d->checksum_type) {
586 :
587 : case TINF_CHKSUM_ADLER:
588 : val = tinf_get_be_uint32(d);
589 : if (d->checksum != val) {
590 : return TINF_CHKSUM_ERROR;
591 : }
592 : break;
593 :
594 : case TINF_CHKSUM_CRC:
595 : val = tinf_get_le_uint32(d);
596 : if (~d->checksum != val) {
597 : return TINF_CHKSUM_ERROR;
598 : }
599 : // Uncompressed size. TODO: Check
600 : val = tinf_get_le_uint32(d);
601 : break;
602 : }
603 : }
604 :
605 : return res;
606 : }
607 : #endif
|
