inflate.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661
  1. /* inflate: see inflate.h. A compact, bounds-checked DEFLATE decoder.
  2. *
  3. * The Huffman decoder is the canonical-code bit-at-a-time form; the LZ77
  4. * history is a 32 KB circular window that is also used as the output staging
  5. * area, so the caller's sink is called in chunks (never per byte). */
  6. #include "inflate.h"
  7. #define MAXBITS INFLATE_MAXBITS
  8. #define MAXLCODES 286
  9. #define MAXDCODES 30
  10. #define MAXCODES (MAXLCODES + MAXDCODES)
  11. #define FIXLCODES 288
  12. #define FASTBITS 9
  13. static unsigned int crc_table[256];
  14. static int crc_table_ready;
  15. static void crc_table_init(void)
  16. {
  17. unsigned int n, k, c;
  18. if (crc_table_ready)
  19. return;
  20. for (n = 0; n < 256; n++) {
  21. c = n;
  22. for (k = 0; k < 8; k++)
  23. c = (c & 1) ? (0xEDB88320u ^ (c >> 1)) : (c >> 1);
  24. crc_table[n] = c;
  25. }
  26. crc_table_ready = 1;
  27. }
  28. static unsigned int crc_update(unsigned int crc, const unsigned char *p,
  29. unsigned int len)
  30. {
  31. unsigned int i;
  32. for (i = 0; i < len; i++)
  33. crc ^= p[i], crc = (crc >> 8) ^ crc_table[crc & 0xFF];
  34. return crc;
  35. }
  36. static void adler_update(unsigned int *a, unsigned int *b,
  37. const unsigned char *p, unsigned int len)
  38. {
  39. unsigned int n;
  40. while (len) {
  41. n = len > 5552 ? 5552 : len;
  42. len -= n;
  43. while (n--) {
  44. *a += *p++;
  45. *b += *a;
  46. }
  47. *a %= 65521;
  48. *b %= 65521;
  49. }
  50. }
  51. unsigned int crc32_bytes(const void *data, unsigned int len)
  52. {
  53. crc_table_init();
  54. return crc_update(0xFFFFFFFFu, (const unsigned char *)data, len) ^
  55. 0xFFFFFFFFu;
  56. }
  57. unsigned int adler32_bytes(const void *data, unsigned int len)
  58. {
  59. unsigned int a = 1, b = 0;
  60. adler_update(&a, &b, (const unsigned char *)data, len);
  61. return (b << 16) | a;
  62. }
  63. /* ---- source ---------------------------------------------------------- */
  64. static int src_byte(struct inflate_src *s, unsigned int *out)
  65. {
  66. while (s->len == 0) {
  67. const unsigned char *p;
  68. unsigned int len;
  69. if (!s->more || !s->more(s->ctx, &p, &len) || len == 0)
  70. return -1;
  71. s->p = p;
  72. s->len = len;
  73. }
  74. *out = *s->p++;
  75. s->len--;
  76. return 0;
  77. }
  78. /* ---- output ---------------------------------------------------------- */
  79. static int flush_out(struct inflate *z)
  80. {
  81. unsigned int start, first, rest;
  82. int r;
  83. if (z->pending == 0)
  84. return 0;
  85. start = (z->wpos + 32768u - z->pending) & 32767u;
  86. first = z->pending;
  87. if (start + first > 32768u)
  88. first = 32768u - start;
  89. rest = z->pending - first;
  90. z->crc = crc_update(z->crc, z->win + start, first);
  91. adler_update(&z->adler_a, &z->adler_b, z->win + start, first);
  92. if (rest) {
  93. z->crc = crc_update(z->crc, z->win, rest);
  94. adler_update(&z->adler_a, &z->adler_b, z->win, rest);
  95. }
  96. r = z->sink.write(z->sink.ctx, z->win + start, first);
  97. if (!r && rest)
  98. r = z->sink.write(z->sink.ctx, z->win, rest);
  99. if (r)
  100. return -1;
  101. z->pending = 0;
  102. if (z->progress)
  103. z->progress(z->progress_ctx);
  104. return 0;
  105. }
  106. static int put_byte(struct inflate *z, unsigned int b)
  107. {
  108. z->win[z->wpos] = (unsigned char)b;
  109. z->wpos = (z->wpos + 1) & 32767u;
  110. z->total++;
  111. if (++z->pending >= 16384)
  112. return flush_out(z);
  113. return 0;
  114. }
  115. /* ---- bit reader ------------------------------------------------------ */
  116. static int need_bits(struct inflate *z, int n)
  117. {
  118. while (z->bitcnt < n) {
  119. unsigned int b;
  120. if (src_byte(&z->src, &b))
  121. return -1;
  122. z->bitbuf |= b << z->bitcnt;
  123. z->bitcnt += 8;
  124. }
  125. return 0;
  126. }
  127. static int get_bits(struct inflate *z, int n)
  128. {
  129. unsigned int v;
  130. if (n == 0)
  131. return 0;
  132. if (need_bits(z, n))
  133. return -1;
  134. v = z->bitbuf & ((1u << n) - 1u);
  135. z->bitbuf >>= n;
  136. z->bitcnt -= n;
  137. z->total_bits += (unsigned int)n;
  138. return (int)v;
  139. }
  140. static int align_byte(struct inflate *z)
  141. {
  142. int pad = (int)((8u - (unsigned int)(z->total_bits & 7u)) & 7u);
  143. if (pad && get_bits(z, pad) < 0)
  144. return -1;
  145. return 0;
  146. }
  147. /* ---- Huffman --------------------------------------------------------- */
  148. static int huff_build(struct inflate_huff *h, const unsigned char *lengths,
  149. int n)
  150. {
  151. unsigned short offs[MAXBITS + 1];
  152. int len, sym, left;
  153. for (len = 0; len <= MAXBITS; len++)
  154. h->count[len] = 0;
  155. for (sym = 0; sym < n; sym++)
  156. h->count[lengths[sym]]++;
  157. if (h->count[0] == n)
  158. return 0; /* no codes: caller rejects if it needs one */
  159. left = 1;
  160. for (len = 1; len <= MAXBITS; len++) {
  161. left <<= 1;
  162. left -= h->count[len];
  163. if (left < 0)
  164. return -1; /* over-subscribed */
  165. }
  166. offs[1] = 0;
  167. for (len = 1; len < MAXBITS; len++)
  168. offs[len + 1] = (unsigned short)(offs[len] + h->count[len]);
  169. for (sym = 0; sym < n; sym++)
  170. if (lengths[sym])
  171. h->symbol[offs[lengths[sym]]++] = (unsigned short)sym;
  172. return 1;
  173. }
  174. static int huff_decode(struct inflate *z, const struct inflate_huff *h)
  175. {
  176. int len, code = 0, first = 0, index = 0;
  177. for (len = 1; len <= MAXBITS; len++) {
  178. int b = get_bits(z, 1);
  179. int count;
  180. if (b < 0)
  181. return -1;
  182. code |= b;
  183. count = h->count[len];
  184. if (code - count < first)
  185. return h->symbol[index + (code - first)];
  186. index += count;
  187. first += count;
  188. first <<= 1;
  189. code <<= 1;
  190. }
  191. return -1;
  192. }
  193. /* ---- DEFLATE blocks -------------------------------------------------- */
  194. static const unsigned short len_base[29] = {
  195. 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  196. 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
  197. };
  198. static const unsigned char len_ext[29] = {
  199. 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  200. 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
  201. };
  202. static const unsigned short dist_base[30] = {
  203. 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129,
  204. 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097,
  205. 6145, 8193, 12289, 16385, 24577
  206. };
  207. static const unsigned char dist_ext[30] = {
  208. 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  209. 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
  210. };
  211. static int copy_match(struct inflate *z, unsigned int len, unsigned int dist)
  212. {
  213. if (dist == 0 || dist > 32768u || len > 258u)
  214. return -1;
  215. while (len--) {
  216. unsigned int src = (z->wpos + 32768u - dist) & 32767u;
  217. if (put_byte(z, z->win[src]))
  218. return -1;
  219. }
  220. return 0;
  221. }
  222. static int codes(struct inflate *z, const struct inflate_huff *lencode,
  223. const struct inflate_huff *distcode)
  224. {
  225. for (;;) {
  226. int sym = huff_decode(z, lencode);
  227. int len, dsym, dist;
  228. if (sym < 0)
  229. return -1;
  230. if (sym < 256) {
  231. if (put_byte(z, (unsigned int)sym))
  232. return -1;
  233. } else if (sym == 256) {
  234. return 0;
  235. } else {
  236. sym -= 257;
  237. if (sym >= 29)
  238. return -1;
  239. len = len_base[sym];
  240. if (len_ext[sym]) {
  241. int e = get_bits(z, len_ext[sym]);
  242. if (e < 0)
  243. return -1;
  244. len += e;
  245. }
  246. dsym = huff_decode(z, distcode);
  247. if (dsym < 0 || dsym >= 30)
  248. return -1;
  249. dist = dist_base[dsym];
  250. if (dist_ext[dsym]) {
  251. int e = get_bits(z, dist_ext[dsym]);
  252. if (e < 0)
  253. return -1;
  254. dist += e;
  255. }
  256. if (copy_match(z, (unsigned int)len, (unsigned int)dist))
  257. return -1;
  258. }
  259. }
  260. }
  261. static int stored_block(struct inflate *z)
  262. {
  263. int len, nlen, i;
  264. len = get_bits(z, 16);
  265. nlen = get_bits(z, 16);
  266. if (len < 0 || nlen < 0 || (len ^ nlen) != 0xFFFF)
  267. return -1;
  268. for (i = 0; i < len; i++) {
  269. int b = get_bits(z, 8);
  270. if (b < 0 || put_byte(z, (unsigned int)b))
  271. return -1;
  272. }
  273. return 0;
  274. }
  275. static int fixed_block(struct inflate *z)
  276. {
  277. unsigned char lengths[FIXLCODES];
  278. static const unsigned char dist_lengths[30] = {
  279. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  280. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
  281. };
  282. struct inflate_huff lencode, distcode;
  283. int i;
  284. for (i = 0; i < 144; i++)
  285. lengths[i] = 8;
  286. for (; i < 256; i++)
  287. lengths[i] = 9;
  288. for (; i < 280; i++)
  289. lengths[i] = 7;
  290. for (; i < 288; i++)
  291. lengths[i] = 8;
  292. if (huff_build(&lencode, lengths, 288) < 0 ||
  293. huff_build(&distcode, dist_lengths, 30) < 0)
  294. return -1;
  295. return codes(z, &lencode, &distcode);
  296. }
  297. static int dynamic_block(struct inflate *z)
  298. {
  299. static const unsigned char order[19] = {
  300. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  301. };
  302. unsigned char lengths[MAXCODES];
  303. struct inflate_huff lencode, distcode;
  304. int hlit, hdist, hclen, i, total;
  305. hlit = get_bits(z, 5);
  306. hdist = get_bits(z, 5);
  307. hclen = get_bits(z, 4);
  308. if (hlit < 0 || hdist < 0 || hclen < 0)
  309. return -1;
  310. hlit += 257;
  311. hdist += 1;
  312. hclen += 4;
  313. if (hlit > MAXLCODES || hdist > MAXDCODES)
  314. return -1;
  315. for (i = 0; i < 19; i++)
  316. lengths[i] = 0;
  317. for (i = 0; i < hclen; i++) {
  318. int v = get_bits(z, 3);
  319. if (v < 0)
  320. return -1;
  321. lengths[order[i]] = (unsigned char)v;
  322. }
  323. if (huff_build(&lencode, lengths, 19) < 0)
  324. return -1;
  325. total = hlit + hdist;
  326. for (i = 0; i < total; ) {
  327. int sym = huff_decode(z, &lencode);
  328. int rep, val;
  329. if (sym < 0)
  330. return -1;
  331. if (sym < 16) {
  332. lengths[i++] = (unsigned char)sym;
  333. continue;
  334. }
  335. if (sym == 16) {
  336. if (i == 0)
  337. return -1;
  338. rep = get_bits(z, 2);
  339. if (rep < 0)
  340. return -1;
  341. rep += 3;
  342. val = lengths[i - 1];
  343. } else if (sym == 17) {
  344. rep = get_bits(z, 3);
  345. if (rep < 0)
  346. return -1;
  347. rep += 3;
  348. val = 0;
  349. } else if (sym == 18) {
  350. rep = get_bits(z, 7);
  351. if (rep < 0)
  352. return -1;
  353. rep += 11;
  354. val = 0;
  355. } else {
  356. return -1;
  357. }
  358. if (i + rep > total)
  359. return -1;
  360. while (rep--)
  361. lengths[i++] = (unsigned char)val;
  362. }
  363. if (huff_build(&lencode, lengths, hlit) < 0)
  364. return -1;
  365. if (huff_build(&distcode, lengths + hlit, hdist) < 0)
  366. return -1;
  367. return codes(z, &lencode, &distcode);
  368. }
  369. void inflate_init(struct inflate *z, struct inflate_src *src,
  370. struct inflate_sink *sink)
  371. {
  372. unsigned char *p = (unsigned char *)z;
  373. unsigned int i;
  374. crc_table_init();
  375. for (i = 0; i < sizeof(*z); i++)
  376. p[i] = 0;
  377. z->src = *src;
  378. z->sink = *sink;
  379. z->crc = 0xFFFFFFFFu;
  380. z->adler_a = 1;
  381. z->adler_b = 0;
  382. }
  383. static int inflate_blocks(struct inflate *z)
  384. {
  385. for (;;) {
  386. int last = get_bits(z, 1);
  387. int type = get_bits(z, 2);
  388. int r;
  389. if (last < 0 || type < 0)
  390. return -1;
  391. if (type == 0) {
  392. if (align_byte(z))
  393. return -1;
  394. r = stored_block(z);
  395. } else if (type == 1) {
  396. r = fixed_block(z);
  397. } else if (type == 2) {
  398. r = dynamic_block(z);
  399. } else {
  400. return -1;
  401. }
  402. if (r)
  403. return -1;
  404. if (last)
  405. break;
  406. }
  407. return flush_out(z);
  408. }
  409. int inflate_raw(struct inflate *z, unsigned int *out_len)
  410. {
  411. if (inflate_blocks(z))
  412. return -1;
  413. if (out_len)
  414. *out_len = (unsigned int)z->total;
  415. return 0;
  416. }
  417. int inflate_zlib(struct inflate *z, unsigned int *out_len)
  418. {
  419. unsigned int cmf, flg, want;
  420. int i;
  421. if (src_byte(&z->src, &cmf) || src_byte(&z->src, &flg))
  422. return -1;
  423. if ((cmf & 0x0F) != 8 || (cmf >> 4) > 7)
  424. return -1;
  425. if (((cmf << 8) | flg) % 31 != 0)
  426. return -1;
  427. if (flg & 0x20) /* preset dictionary: not supported */
  428. return -1;
  429. if (inflate_blocks(z))
  430. return -1;
  431. if (align_byte(z))
  432. return -1;
  433. want = 0;
  434. for (i = 0; i < 4; i++) {
  435. int b = get_bits(z, 8);
  436. if (b < 0)
  437. return -1;
  438. want = (want << 8) | (unsigned int)b; /* zlib is big-endian */
  439. }
  440. if (want != ((z->adler_b << 16) | z->adler_a))
  441. return -1;
  442. if (out_len)
  443. *out_len = (unsigned int)z->total;
  444. return 0;
  445. }
  446. int inflate_gzip(struct inflate *z, unsigned int *out_len)
  447. {
  448. unsigned int id1, id2, cm, flg, b, skip, want_crc, want_size;
  449. int i;
  450. if (src_byte(&z->src, &id1) || src_byte(&z->src, &id2) ||
  451. src_byte(&z->src, &cm) || src_byte(&z->src, &flg))
  452. return -1;
  453. if (id1 != 0x1F || id2 != 0x8B || cm != 8)
  454. return -1;
  455. for (i = 0; i < 6; i++) /* MTIME, XFL, OS */
  456. if (src_byte(&z->src, &b))
  457. return -1;
  458. if (flg & 0x04) { /* FEXTRA */
  459. unsigned int lo, hi;
  460. if (src_byte(&z->src, &lo) || src_byte(&z->src, &hi))
  461. return -1;
  462. skip = lo | (hi << 8);
  463. while (skip--)
  464. if (src_byte(&z->src, &b))
  465. return -1;
  466. }
  467. if (flg & 0x08) { /* FNAME */
  468. do {
  469. if (src_byte(&z->src, &b))
  470. return -1;
  471. } while (b);
  472. }
  473. if (flg & 0x10) { /* FCOMMENT */
  474. do {
  475. if (src_byte(&z->src, &b))
  476. return -1;
  477. } while (b);
  478. }
  479. if (flg & 0x02) { /* FHCRC */
  480. if (src_byte(&z->src, &b) || src_byte(&z->src, &b))
  481. return -1;
  482. }
  483. if (inflate_blocks(z))
  484. return -1;
  485. if (align_byte(z))
  486. return -1;
  487. /* The trailer: CRC32 then ISIZE, both little-endian. */
  488. want_crc = 0;
  489. for (i = 0; i < 4; i++) {
  490. int v = get_bits(z, 8);
  491. if (v < 0)
  492. return -1;
  493. want_crc |= (unsigned int)v << (8 * i);
  494. }
  495. want_size = 0;
  496. for (i = 0; i < 4; i++) {
  497. int v = get_bits(z, 8);
  498. if (v < 0)
  499. return -1;
  500. want_size |= (unsigned int)v << (8 * i);
  501. }
  502. if ((want_crc ^ 0xFFFFFFFFu) != z->crc)
  503. return -1;
  504. if (want_size != (unsigned int)z->total)
  505. return -1;
  506. if (out_len)
  507. *out_len = (unsigned int)z->total;
  508. return 0;
  509. }
  510. /* ---- whole-buffer helpers ------------------------------------------- */
  511. struct mem_sink {
  512. unsigned char *dst;
  513. unsigned int cap, pos;
  514. };
  515. static int mem_write(void *ctx, const unsigned char *data, unsigned int len)
  516. {
  517. struct mem_sink *m = (struct mem_sink *)ctx;
  518. if (len > m->cap - m->pos)
  519. return -1;
  520. {
  521. unsigned int i;
  522. for (i = 0; i < len; i++)
  523. m->dst[m->pos + i] = data[i];
  524. }
  525. m->pos += len;
  526. return 0;
  527. }
  528. static int mem_inflate(const void *src, unsigned int len, void *dst,
  529. unsigned int cap, unsigned int *out_len, void *ws,
  530. int gzip)
  531. {
  532. struct inflate *z = (struct inflate *)ws;
  533. struct inflate_src s;
  534. struct inflate_sink sink;
  535. struct mem_sink m;
  536. s.p = (const unsigned char *)src;
  537. s.len = len;
  538. s.more = 0;
  539. s.ctx = 0;
  540. m.dst = (unsigned char *)dst;
  541. m.cap = cap;
  542. m.pos = 0;
  543. sink.write = mem_write;
  544. sink.ctx = &m;
  545. inflate_init(z, &s, &sink);
  546. if (gzip ? inflate_gzip(z, out_len) : inflate_zlib(z, out_len))
  547. return -1;
  548. return 0;
  549. }
  550. int inflate_zlib_mem(const void *src, unsigned int len, void *dst,
  551. unsigned int cap, unsigned int *out_len, void *ws)
  552. {
  553. return mem_inflate(src, len, dst, cap, out_len, ws, 0);
  554. }
  555. int inflate_gzip_mem(const void *src, unsigned int len, void *dst,
  556. unsigned int cap, unsigned int *out_len, void *ws)
  557. {
  558. return mem_inflate(src, len, dst, cap, out_len, ws, 1);
  559. }
  560. int inflate_raw_mem(const void *src, unsigned int len, void *dst,
  561. unsigned int cap, unsigned int *out_len, void *ws)
  562. {
  563. struct inflate *z = (struct inflate *)ws;
  564. struct inflate_src s;
  565. struct inflate_sink sink;
  566. struct mem_sink m;
  567. s.p = (const unsigned char *)src;
  568. s.len = len;
  569. s.more = 0;
  570. s.ctx = 0;
  571. m.dst = (unsigned char *)dst;
  572. m.cap = cap;
  573. m.pos = 0;
  574. sink.write = mem_write;
  575. sink.ctx = &m;
  576. inflate_init(z, &s, &sink);
  577. return inflate_raw(z, out_len);
  578. }