uzlib_inflate.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603
  1. /*
  2. * tinfgzip.c - tiny gzip decompressor
  3. * tinflate.c - tiny inflate
  4. *
  5. * The original source headers as below for licence compliance and in
  6. * full acknowledgement of the originitor contributions. Modified by
  7. * Terry Ellison 2018 to provide lightweight stream inflate for NodeMCU
  8. * Lua. Modifications are under the standard NodeMCU MIT licence.
  9. *
  10. * Copyright (c) 2003 by Joergen Ibsen / Jibz
  11. * All Rights Reserved
  12. * http://www.ibsensoftware.com/
  13. *
  14. * Copyright (c) 2014-2016 by Paul Sokolovsky
  15. *
  16. * This software is provided 'as-is', without any express
  17. * or implied warranty. In no event will the authors be
  18. * held liable for any damages arising from the use of
  19. * this software.
  20. *
  21. * Permission is granted to anyone to use this software
  22. * for any purpose, including commercial applications,
  23. * and to alter it and redistribute it freely, subject to
  24. * the following restrictions:
  25. *
  26. * 1. The origin of this software must not be
  27. * misrepresented; you must not claim that you
  28. * wrote the original software. If you use this
  29. * software in a product, an acknowledgment in
  30. * the product documentation would be appreciated
  31. * but is not required.
  32. *
  33. * 2. Altered source versions must be plainly marked
  34. * as such, and must not be misrepresented as
  35. * being the original software.
  36. *
  37. * 3. This notice may not be removed or altered from
  38. * any source distribution.
  39. */
  40. #include <string.h>
  41. #ifdef __XTENSA__
  42. #include "c_stdio.h"
  43. #else
  44. #include <stdio.h>
  45. #endif
  46. #include "uzlib.h"
  47. #ifdef DEBUG_COUNTS
  48. #define DBG_PRINT(...) printf(__VA_ARGS__)
  49. #define DBG_COUNT(n) (debugCounts[n]++)
  50. #define DBG_ADD_COUNT(n,m) (debugCounts[n]+=m)
  51. int debugCounts[20];
  52. #else
  53. #define NDEBUG
  54. #define DBG_PRINT(...)
  55. #define DBG_COUNT(n)
  56. #define DBG_ADD_COUNT(n,m)
  57. #endif
  58. #define SIZE(arr) (sizeof(arr) / sizeof(*(arr)))
  59. jmp_buf unwindAddr;
  60. int dbg_break(void) {return 1;}
  61. typedef uint8_t uchar;
  62. typedef uint16_t ushort;
  63. typedef uint32_t uint;
  64. /* data structures */
  65. typedef struct {
  66. ushort table[16]; /* table of code length counts */
  67. ushort trans[288]; /* code -> symbol translation table */
  68. } UZLIB_TREE;
  69. struct uzlib_data {
  70. /*
  71. * extra bits and base tables for length and distance codes
  72. */
  73. uchar lengthBits[30];
  74. ushort lengthBase[30];
  75. uchar distBits[30];
  76. ushort distBase[30];
  77. /*
  78. * special ordering of code length codes
  79. */
  80. uchar clcidx[19];
  81. /*
  82. * dynamic length/symbol and distance trees
  83. */
  84. UZLIB_TREE ltree;
  85. UZLIB_TREE dtree;
  86. /*
  87. * methods encapsulate handling of the input and output streams
  88. */
  89. uchar (*get_byte)(void);
  90. void (*put_byte)(uchar b);
  91. uchar (*recall_byte)(uint offset);
  92. /*
  93. * Other state values
  94. */
  95. uint destSize;
  96. uint tag;
  97. uint bitcount;
  98. uint lzOffs;
  99. int bType;
  100. int bFinal;
  101. uint curLen;
  102. uint checksum;
  103. };
  104. /*
  105. * Note on changes to layout, naming, etc. This module combines extracts
  106. * from 3 code files from two sources (Sokolovsky, Ibsen et al) with perhaps
  107. * 30% from me Terry Ellison. These sources had inconsistent layout and
  108. * naming conventions, plus extra condtional handling of platforms that
  109. * cannot support NodeMCU. (This is intended to be run compiled and executed
  110. * on GCC POSIX and XENTA newlib environments.) So I have (1) reformatted
  111. * this file in line with NodeMCU rules; (2) demoted all private data and
  112. * functions to static and removed the redundant name prefixes; (3) reordered
  113. * functions into a more logic order; (4) added some ESP architecture
  114. * optimisations, for example these IoT devices are very RAM limited, so
  115. * statically allocating large RAM blocks is against programming guidelines.
  116. */
  117. static void skip_bytes(UZLIB_DATA *d, int num) {
  118. if (num) /* Skip a fixed number of bytes */
  119. while (num--) (void) d->get_byte();
  120. else /* Skip to next nullchar */
  121. while (d->get_byte()) {}
  122. }
  123. static uint16_t get_uint16(UZLIB_DATA *d) {
  124. uint16_t v = d->get_byte();
  125. return v | (d->get_byte() << 8);
  126. }
  127. static uint get_le_uint32 (UZLIB_DATA *d) {
  128. uint v = get_uint16(d);
  129. return v | ((uint) get_uint16(d) << 16);
  130. }
  131. /* get one bit from source stream */
  132. static int getbit (UZLIB_DATA *d) {
  133. uint bit;
  134. /* check if tag is empty */
  135. if (!d->bitcount--) {
  136. /* load next tag */
  137. d->tag = d->get_byte();
  138. d->bitcount = 7;
  139. }
  140. /* shift bit out of tag */
  141. bit = d->tag & 0x01;
  142. d->tag >>= 1;
  143. return bit;
  144. }
  145. /* read a num bit value from a stream and add base */
  146. static uint read_bits (UZLIB_DATA *d, int num, int base) {
  147. /* This is an optimised version which doesn't call getbit num times */
  148. if (!num)
  149. return base;
  150. uint i, n = (((uint)-1)<<num);
  151. for (i = d->bitcount; i < num; i +=8)
  152. d->tag |= ((uint)d->get_byte()) << i;
  153. n = d->tag & ~n;
  154. d->tag >>= num;
  155. d->bitcount = i - num;
  156. return base + n;
  157. }
  158. /* --------------------------------------------------- *
  159. * -- uninitialized global data (static structures) -- *
  160. * --------------------------------------------------- */
  161. /*
  162. * Constants are stored in flash memory on the ESP8266 NodeMCU firmware
  163. * builds, but only word aligned data access are supported in hardare so
  164. * short and byte accesses are handled by a S/W exception handler and
  165. * are SLOW. RAM is also at premium, especially static initialised vars,
  166. * so we malloc a single block on first call to hold all tables and call
  167. * the dynamic generator to generate malloced RAM tables that have the
  168. * same content as the above statically declared versions.
  169. *
  170. * This might seem a bit convolved but this runs faster and takes up
  171. * less memory than the static version on the ESP8266.
  172. */
  173. #define CLCIDX_INIT \
  174. "\x10\x11\x12\x00\x08\x07\x09\x06\x0a\x05\x0b\x04\x0c\x03\x0d\x02\x0e\x01\x0f"
  175. /* ----------------------- *
  176. * -- utility functions -- *
  177. * ----------------------- */
  178. /* build extra bits and base tables */
  179. static void build_bits_base (uchar *bits, ushort *base,
  180. int delta, int first) {
  181. int i, sum;
  182. /* build bits table */
  183. for (i = 0; i < delta; ++i) bits[i] = 0;
  184. for (i = 0; i < 30 - delta; ++i) bits[i + delta] = i / delta;
  185. /* build base table */
  186. for (sum = first, i = 0; i < 30; ++i) {
  187. base[i] = sum;
  188. sum += 1 << bits[i];
  189. }
  190. }
  191. /* build the fixed huffman trees */
  192. static void build_fixed_trees (UZLIB_TREE *lt, UZLIB_TREE *dt) {
  193. int i;
  194. /* build fixed length tree */
  195. for (i = 0; i < 7; ++i) lt->table[i] = 0;
  196. lt->table[7] = 24;
  197. lt->table[8] = 152;
  198. lt->table[9] = 112;
  199. for (i = 0; i < 24; ++i) lt->trans[i] = 256 + i;
  200. for (i = 0; i < 144; ++i) lt->trans[24 + i] = i;
  201. for (i = 0; i < 8; ++i) lt->trans[24 + 144 + i] = 280 + i;
  202. for (i = 0; i < 112; ++i) lt->trans[24 + 144 + 8 + i] = 144 + i;
  203. /* build fixed distance tree */
  204. for (i = 0; i < 5; ++i) dt->table[i] = 0;
  205. dt->table[5] = 32;
  206. for (i = 0; i < 32; ++i) dt->trans[i] = i;
  207. }
  208. /* given an array of code lengths, build a tree */
  209. static void build_tree (UZLIB_TREE *t, const uchar *lengths, uint num) {
  210. ushort offs[16];
  211. uint i, sum;
  212. /* clear code length count table */
  213. for (i = 0; i < 16; ++i)
  214. t->table[i] = 0;
  215. /* scan symbol lengths, and sum code length counts */
  216. for (i = 0; i < num; ++i)
  217. t->table[lengths[i]]++;
  218. t->table[0] = 0;
  219. /* compute offset table for distribution sort */
  220. for (sum = 0, i = 0; i < 16; ++i) {
  221. offs[i] = sum;
  222. sum += t->table[i];
  223. }
  224. /* create code->symbol translation table (symbols sorted by code) */
  225. for (i = 0; i < num; ++i) {
  226. if (lengths[i])
  227. t->trans[offs[lengths[i]]++] = i;
  228. }
  229. }
  230. /* ---------------------- *
  231. * -- decode functions -- *
  232. * ---------------------- */
  233. /* given a data stream and a tree, decode a symbol */
  234. static int decode_symbol (UZLIB_DATA *d, UZLIB_TREE *t) {
  235. int sum = 0, cur = 0, len = 0;
  236. /* get more bits while code value is above sum */
  237. do {
  238. cur = 2*cur + getbit(d);
  239. if (++len == SIZE(t->table))
  240. return UZLIB_DATA_ERROR;
  241. sum += t->table[len];
  242. cur -= t->table[len];
  243. } while (cur >= 0);
  244. sum += cur;
  245. if (sum < 0 || sum >= SIZE(t->trans))
  246. return UZLIB_DATA_ERROR;
  247. return t->trans[sum];
  248. }
  249. /* given a data stream, decode dynamic trees from it */
  250. static int decode_trees (UZLIB_DATA *d, UZLIB_TREE *lt, UZLIB_TREE *dt) {
  251. uchar lengths[288+32];
  252. uint hlit, hdist, hclen, hlimit;
  253. uint i, num, length;
  254. /* get 5 bits HLIT (257-286) */
  255. hlit = read_bits(d, 5, 257);
  256. /* get 5 bits HDIST (1-32) */
  257. hdist = read_bits(d, 5, 1);
  258. /* get 4 bits HCLEN (4-19) */
  259. hclen = read_bits(d, 4, 4);
  260. for (i = 0; i < 19; ++i) lengths[i] = 0;
  261. /* read code lengths for code length alphabet */
  262. for (i = 0; i < hclen; ++i) {
  263. /* get 3 bits code length (0-7) */
  264. uint clen = read_bits(d, 3, 0);
  265. lengths[d->clcidx[i]] = clen;
  266. }
  267. /* build code length tree, temporarily use length tree */
  268. build_tree(lt, lengths, 19);
  269. /* decode code lengths for the dynamic trees */
  270. hlimit = hlit + hdist;
  271. for (num = 0; num < hlimit; ) {
  272. int sym = decode_symbol(d, lt);
  273. uchar fill_value = 0;
  274. int lbits, lbase = 3;
  275. /* error decoding */
  276. if (sym < 0)
  277. return sym;
  278. switch (sym) {
  279. case 16:
  280. /* copy previous code length 3-6 times (read 2 bits) */
  281. fill_value = lengths[num - 1];
  282. lbits = 2;
  283. break;
  284. case 17:
  285. /* repeat code length 0 for 3-10 times (read 3 bits) */
  286. lbits = 3;
  287. break;
  288. case 18:
  289. /* repeat code length 0 for 11-138 times (read 7 bits) */
  290. lbits = 7;
  291. lbase = 11;
  292. break;
  293. default:
  294. /* values 0-15 represent the actual code lengths */
  295. lengths[num++] = sym;
  296. /* continue the for loop */
  297. continue;
  298. }
  299. /* special code length 16-18 are handled here */
  300. length = read_bits(d, lbits, lbase);
  301. if (num + length > hlimit)
  302. return UZLIB_DATA_ERROR;
  303. for (; length; --length)
  304. lengths[num++] = fill_value;
  305. }
  306. /* build dynamic trees */
  307. build_tree(lt, lengths, hlit);
  308. build_tree(dt, lengths + hlit, hdist);
  309. return UZLIB_OK;
  310. }
  311. /* ----------------------------- *
  312. * -- block inflate functions -- *
  313. * ----------------------------- */
  314. /* given a stream and two trees, inflate a block of data */
  315. static int inflate_block_data (UZLIB_DATA *d, UZLIB_TREE *lt, UZLIB_TREE *dt) {
  316. if (d->curLen == 0) {
  317. int dist;
  318. int sym = decode_symbol(d, lt);
  319. /* literal byte */
  320. if (sym < 256) {
  321. DBG_PRINT("huff sym: %02x %c\n", sym, sym);
  322. d->put_byte(sym);
  323. return UZLIB_OK;
  324. }
  325. /* end of block */
  326. if (sym == 256)
  327. return UZLIB_DONE;
  328. /* substring from sliding dictionary */
  329. sym -= 257;
  330. /* possibly get more bits from length code */
  331. d->curLen = read_bits(d, d->lengthBits[sym], d->lengthBase[sym]);
  332. dist = decode_symbol(d, dt);
  333. /* possibly get more bits from distance code */
  334. d->lzOffs = read_bits(d, d->distBits[dist], d->distBase[dist]);
  335. DBG_PRINT("huff dict: -%u for %u\n", d->lzOffs, d->curLen);
  336. }
  337. /* copy next byte from dict substring */
  338. uchar b = d->recall_byte(d->lzOffs);
  339. DBG_PRINT("huff dict byte(%u): -%u - %02x %c\n\n",
  340. d->curLen, d->lzOffs, b, b);
  341. d->put_byte(b);
  342. d->curLen--;
  343. return UZLIB_OK;
  344. }
  345. /* inflate an uncompressed block of data */
  346. static int inflate_uncompressed_block (UZLIB_DATA *d) {
  347. if (d->curLen == 0) {
  348. uint length = get_uint16(d);
  349. uint invlength = get_uint16(d);
  350. /* check length */
  351. if (length != (~invlength & 0x0000ffff))
  352. return UZLIB_DATA_ERROR;
  353. /* increment length to properly return UZLIB_DONE below, without
  354. producing data at the same time */
  355. d->curLen = length + 1;
  356. /* make sure we start next block on a byte boundary */
  357. d->bitcount = 0;
  358. }
  359. if (--d->curLen == 0) {
  360. return UZLIB_DONE;
  361. }
  362. d->put_byte(d->get_byte());
  363. return UZLIB_OK;
  364. }
  365. /* -------------------------- *
  366. * -- main parse functions -- *
  367. * -------------------------- */
  368. static int parse_gzip_header(UZLIB_DATA *d) {
  369. /* check id bytes */
  370. if (d->get_byte() != 0x1f || d->get_byte() != 0x8b)
  371. return UZLIB_DATA_ERROR;
  372. if (d->get_byte() != 8) /* check method is deflate */
  373. return UZLIB_DATA_ERROR;
  374. uchar flg = d->get_byte();/* get flag byte */
  375. if (flg & 0xe0)/* check that reserved bits are zero */
  376. return UZLIB_DATA_ERROR;
  377. skip_bytes(d, 6); /* skip rest of base header of 10 bytes */
  378. if (flg & UZLIB_FEXTRA) /* skip extra data if present */
  379. skip_bytes(d, get_uint16(d));
  380. if (flg & UZLIB_FNAME) /* skip file name if present */
  381. skip_bytes(d,0);
  382. if (flg & UZLIB_FCOMMENT) /* skip file comment if present */
  383. skip_bytes(d,0);
  384. if (flg & UZLIB_FHCRC) /* ignore header crc if present */
  385. skip_bytes(d,2);
  386. return UZLIB_OK;
  387. }
  388. /* inflate next byte of compressed stream */
  389. static int uncompress_stream (UZLIB_DATA *d) {
  390. do {
  391. int res;
  392. /* start a new block */
  393. if (d->bType == -1) {
  394. next_blk:
  395. /* read final block flag */
  396. d->bFinal = getbit(d);
  397. /* read block type (2 bits) */
  398. d->bType = read_bits(d, 2, 0);
  399. DBG_PRINT("Started new block: type=%d final=%d\n", d->bType, d->bFinal);
  400. if (d->bType == 1) {
  401. /* build fixed huffman trees */
  402. build_fixed_trees(&d->ltree, &d->dtree);
  403. } else if (d->bType == 2) {
  404. /* decode trees from stream */
  405. res = decode_trees(d, &d->ltree, &d->dtree);
  406. if (res != UZLIB_OK)
  407. return res;
  408. }
  409. }
  410. /* process current block */
  411. switch (d->bType) {
  412. case 0:
  413. /* decompress uncompressed block */
  414. res = inflate_uncompressed_block(d);
  415. break;
  416. case 1:
  417. case 2:
  418. /* decompress block with fixed or dynamic huffman trees. These */
  419. /* trees were decoded previously, so it's the same routine for both */
  420. res = inflate_block_data(d, &d->ltree, &d->dtree);
  421. break;
  422. default:
  423. return UZLIB_DATA_ERROR;
  424. }
  425. if (res == UZLIB_DONE && !d->bFinal) {
  426. /* the block has ended (without producing more data), but we
  427. can't return without data, so start procesing next block */
  428. goto next_blk;
  429. }
  430. if (res != UZLIB_OK)
  431. return res;
  432. } while (--d->destSize);
  433. return UZLIB_OK;
  434. }
  435. /*
  436. * This implementation has a different usecase to Paul Sokolovsky's
  437. * uzlib implementation, in that it is designed to target IoT devices
  438. * such as the ESP8266. Here clarity and compact code size is an
  439. * advantage, but the ESP8266 only has 40-45Kb free heap, and has to
  440. * process files with an unpacked size of up 256Kb, so a streaming
  441. * implementation is essential.
  442. *
  443. * I have taken the architectural decision to hide the implementation
  444. * detials from the uncompress routines and the caller must provide
  445. * three support routines to handle the streaming:
  446. *
  447. * void get_byte(void)
  448. * void put_byte(uchar b)
  449. * uchar recall_byte(uint offset)
  450. *
  451. * This last must be able to recall an output byte with an offet up to
  452. * the maximum dictionary size.
  453. */
  454. int uzlib_inflate (
  455. uchar (*get_byte)(void),
  456. void (*put_byte)(uchar v),
  457. uchar (*recall_byte)(uint offset),
  458. uint len, uint *crc, void **state) {
  459. int res;
  460. /* initialize decompression structure */
  461. UZLIB_DATA *d = (UZLIB_DATA *) uz_malloc(sizeof(*d));
  462. if (!d)
  463. return UZLIB_MEMORY_ERROR;
  464. *state = d;
  465. d->bitcount = 0;
  466. d->bFinal = 0;
  467. d->bType = -1;
  468. d->curLen = 0;
  469. d->destSize = len;
  470. d->get_byte = get_byte;
  471. d->put_byte = put_byte;
  472. d->recall_byte = recall_byte;
  473. if ((res = UZLIB_SETJMP(unwindAddr)) != 0) {
  474. if (crc)
  475. *crc = d->checksum;
  476. /* handle long jump */
  477. if (d) {
  478. uz_free(d);
  479. *state = NULL;
  480. }
  481. return res;
  482. }
  483. /* create RAM copy of clcidx byte array */
  484. memcpy(d->clcidx, CLCIDX_INIT, sizeof(d->clcidx));
  485. /* build extra bits and base tables */
  486. build_bits_base(d->lengthBits, d->lengthBase, 4, 3);
  487. build_bits_base(d->distBits, d->distBase, 2, 1);
  488. d->lengthBits[28] = 0; /* fix a special case */
  489. d->lengthBase[28] = 258;
  490. if ((res = parse_gzip_header(d))== UZLIB_OK)
  491. while ((res = uncompress_stream(d)) == UZLIB_OK)
  492. {}
  493. if (res == UZLIB_DONE) {
  494. d->checksum = get_le_uint32(d);
  495. (void) get_le_uint32(d); /* already got length so ignore */
  496. }
  497. UZLIB_THROW(res);
  498. }