inflate.c 14 KB

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