inflate.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978
  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 10
  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 fast path ----------------------------------------
  511. *
  512. * The streaming decoder above reads one bit per Huffman step and stages
  513. * every byte in the 32 KB ring. When the whole input and output are in
  514. * memory (the boot rootfs, PNG/HTTP bodies decoded into one buffer) that
  515. * is needlessly slow: here the output buffer itself is the LZ77 history,
  516. * the bit buffer is refilled a byte at a time up to 32 bits, and codes of
  517. * up to FASTBITS are resolved with one table lookup. Longer codes fall
  518. * back to the canonical walk on the bits already in the buffer. Only the
  519. * checksum the container needs is computed, once, over the finished
  520. * output. The tables live in the caller's struct-inflate workspace. */
  521. #define FAST_SIZE (1u << FASTBITS)
  522. struct fhuff {
  523. struct inflate_huff h;
  524. unsigned short fast[FAST_SIZE]; /* (sym << 4) | len, 0 = slow */
  525. };
  526. struct fz {
  527. const unsigned char *in, *in_end;
  528. unsigned int bitbuf;
  529. int bitcnt;
  530. unsigned int over; /* zero bytes padded past the end */
  531. unsigned char *out, *out_start, *out_end;
  532. };
  533. struct fz_ws {
  534. struct fhuff lit, dist;
  535. };
  536. static void fz_refill(struct fz *f)
  537. {
  538. while (f->bitcnt <= 24) {
  539. unsigned int b = 0;
  540. if (f->in < f->in_end)
  541. b = *f->in++;
  542. else
  543. f->over++;
  544. f->bitbuf |= b << f->bitcnt;
  545. f->bitcnt += 8;
  546. }
  547. }
  548. static int fz_bits(struct fz *f, int n)
  549. {
  550. unsigned int v;
  551. if (f->bitcnt < n)
  552. fz_refill(f);
  553. v = f->bitbuf & ((1u << n) - 1u);
  554. f->bitbuf >>= n;
  555. f->bitcnt -= n;
  556. return (int)v;
  557. }
  558. static int fhuff_build(struct fhuff *fh, const unsigned char *lengths, int n)
  559. {
  560. unsigned int next[MAXBITS + 2];
  561. int r, len, sym, i;
  562. r = huff_build(&fh->h, lengths, n);
  563. if (r < 0)
  564. return -1;
  565. for (i = 0; i < (int)FAST_SIZE; i++)
  566. fh->fast[i] = 0;
  567. {
  568. /* next[len] = first canonical code of length len. */
  569. unsigned int c = 0;
  570. next[1] = 0;
  571. for (len = 1; len < MAXBITS; len++) {
  572. c = (c + fh->h.count[len]) << 1;
  573. next[len + 1] = c;
  574. }
  575. }
  576. for (sym = 0; sym < n; sym++) {
  577. unsigned int c, rev = 0;
  578. int l = lengths[sym], k;
  579. if (!l)
  580. continue;
  581. c = next[l]++;
  582. if (l > FASTBITS)
  583. continue;
  584. for (k = 0; k < l; k++)
  585. rev |= ((c >> k) & 1u) << (l - 1 - k);
  586. for (; rev < FAST_SIZE; rev += 1u << l)
  587. fh->fast[rev] = (unsigned short)((sym << 4) | l);
  588. }
  589. return r;
  590. }
  591. static int fz_decode(struct fz *f, const struct fhuff *fh)
  592. {
  593. unsigned int e;
  594. int len, code = 0, first = 0, index = 0;
  595. if (f->bitcnt < MAXBITS)
  596. fz_refill(f);
  597. e = fh->fast[f->bitbuf & (FAST_SIZE - 1u)];
  598. if (e) {
  599. f->bitbuf >>= e & 15u;
  600. f->bitcnt -= (int)(e & 15u);
  601. return (int)(e >> 4);
  602. }
  603. for (len = 1; len <= MAXBITS; len++) {
  604. int count;
  605. code |= (int)(f->bitbuf & 1u);
  606. f->bitbuf >>= 1;
  607. f->bitcnt--;
  608. count = fh->h.count[len];
  609. if (code - count < first)
  610. return fh->h.symbol[index + (code - first)];
  611. index += count;
  612. first += count;
  613. first <<= 1;
  614. code <<= 1;
  615. }
  616. return -1;
  617. }
  618. static int fz_codes(struct fz *f, const struct fhuff *lit,
  619. const struct fhuff *dist)
  620. {
  621. for (;;) {
  622. int sym = fz_decode(f, lit);
  623. unsigned int len, d;
  624. unsigned char *out, *src;
  625. if (sym < 256) {
  626. if (sym < 0 || f->out >= f->out_end)
  627. return -1;
  628. *f->out++ = (unsigned char)sym;
  629. continue;
  630. }
  631. if (sym == 256)
  632. return f->over > 4 ? -1 : 0;
  633. sym -= 257;
  634. if (sym >= 29)
  635. return -1;
  636. len = len_base[sym];
  637. if (len_ext[sym])
  638. len += (unsigned int)fz_bits(f, len_ext[sym]);
  639. sym = fz_decode(f, dist);
  640. if (sym < 0 || sym >= 30)
  641. return -1;
  642. d = dist_base[sym];
  643. if (dist_ext[sym])
  644. d += (unsigned int)fz_bits(f, dist_ext[sym]);
  645. out = f->out;
  646. if (d > (unsigned int)(out - f->out_start) ||
  647. len > (unsigned int)(f->out_end - out))
  648. return -1;
  649. src = out - d;
  650. if (d >= 4) {
  651. while (len >= 4) {
  652. out[0] = src[0]; out[1] = src[1];
  653. out[2] = src[2]; out[3] = src[3];
  654. out += 4; src += 4; len -= 4;
  655. }
  656. }
  657. while (len--)
  658. *out++ = *src++;
  659. f->out = out;
  660. }
  661. }
  662. static int fz_blocks(struct fz *f, struct fz_ws *ws)
  663. {
  664. static const unsigned char order[19] = {
  665. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  666. };
  667. unsigned char lengths[FIXLCODES + MAXDCODES];
  668. int last, type, i;
  669. do {
  670. last = fz_bits(f, 1);
  671. type = fz_bits(f, 2);
  672. if (type == 0) {
  673. unsigned int len, nlen;
  674. fz_bits(f, f->bitcnt & 7);
  675. len = (unsigned int)fz_bits(f, 16);
  676. nlen = (unsigned int)fz_bits(f, 16);
  677. if ((len ^ nlen) != 0xFFFFu ||
  678. len > (unsigned int)(f->out_end - f->out))
  679. return -1;
  680. /* Return the whole buffered bytes to the input and
  681. * copy the stored data straight from it. */
  682. {
  683. unsigned int back = (unsigned int)f->bitcnt >> 3;
  684. if (back < f->over)
  685. return -1;
  686. f->in -= back - f->over;
  687. f->bitbuf = 0;
  688. f->bitcnt = 0;
  689. f->over = 0;
  690. }
  691. if (len > (unsigned int)(f->in_end - f->in))
  692. return -1;
  693. while (len--)
  694. *f->out++ = *f->in++;
  695. } else if (type == 1) {
  696. for (i = 0; i < 144; i++)
  697. lengths[i] = 8;
  698. for (; i < 256; i++)
  699. lengths[i] = 9;
  700. for (; i < 280; i++)
  701. lengths[i] = 7;
  702. for (; i < 288; i++)
  703. lengths[i] = 8;
  704. for (i = 0; i < 30; i++)
  705. lengths[288 + i] = 5;
  706. if (fhuff_build(&ws->lit, lengths, 288) < 0 ||
  707. fhuff_build(&ws->dist, lengths + 288, 30) < 0 ||
  708. fz_codes(f, &ws->lit, &ws->dist))
  709. return -1;
  710. } else if (type == 2) {
  711. int hlit = fz_bits(f, 5) + 257;
  712. int hdist = fz_bits(f, 5) + 1;
  713. int hclen = fz_bits(f, 4) + 4;
  714. int total = hlit + hdist;
  715. if (hlit > MAXLCODES || hdist > MAXDCODES)
  716. return -1;
  717. for (i = 0; i < 19; i++)
  718. lengths[i] = 0;
  719. for (i = 0; i < hclen; i++)
  720. lengths[order[i]] = (unsigned char)fz_bits(f, 3);
  721. if (fhuff_build(&ws->lit, lengths, 19) < 0)
  722. return -1;
  723. for (i = 0; i < total; ) {
  724. int sym = fz_decode(f, &ws->lit), rep, val;
  725. if (sym < 0)
  726. return -1;
  727. if (sym < 16) {
  728. lengths[i++] = (unsigned char)sym;
  729. continue;
  730. }
  731. if (sym == 16) {
  732. if (i == 0)
  733. return -1;
  734. rep = 3 + fz_bits(f, 2);
  735. val = lengths[i - 1];
  736. } else if (sym == 17) {
  737. rep = 3 + fz_bits(f, 3);
  738. val = 0;
  739. } else {
  740. rep = 11 + fz_bits(f, 7);
  741. val = 0;
  742. }
  743. if (i + rep > total)
  744. return -1;
  745. while (rep--)
  746. lengths[i++] = (unsigned char)val;
  747. }
  748. if (fhuff_build(&ws->lit, lengths, hlit) < 0 ||
  749. fhuff_build(&ws->dist, lengths + hlit, hdist) < 0 ||
  750. fz_codes(f, &ws->lit, &ws->dist))
  751. return -1;
  752. } else {
  753. return -1;
  754. }
  755. if (f->over > 4)
  756. return -1;
  757. } while (!last);
  758. /* Byte-align and hand the whole bytes still buffered back to the
  759. * input, so the container trailer is read from memory. */
  760. fz_bits(f, f->bitcnt & 7);
  761. {
  762. unsigned int back = (unsigned int)f->bitcnt >> 3;
  763. if (back < f->over)
  764. return -1; /* consumed padding: truncated */
  765. f->in -= back - f->over;
  766. f->bitbuf = 0;
  767. f->bitcnt = 0;
  768. f->over = 0;
  769. }
  770. return 0;
  771. }
  772. /* container: 0 raw, 1 zlib, 2 gzip */
  773. static int fz_inflate(const void *src, unsigned int len, void *dst,
  774. unsigned int cap, unsigned int *out_len, void *ws,
  775. int container)
  776. {
  777. struct fz f;
  778. const unsigned char *p = (const unsigned char *)src;
  779. const unsigned char *end = p + len;
  780. unsigned int n;
  781. if (container == 2) {
  782. unsigned int flg;
  783. if (len < 18 || p[0] != 0x1F || p[1] != 0x8B || p[2] != 8)
  784. return -1;
  785. flg = p[3];
  786. p += 10;
  787. if (flg & 0x04) {
  788. if (end - p < 2)
  789. return -1;
  790. n = p[0] | ((unsigned int)p[1] << 8);
  791. p += 2;
  792. if ((unsigned int)(end - p) < n)
  793. return -1;
  794. p += n;
  795. }
  796. if (flg & 0x08) {
  797. while (p < end && *p)
  798. p++;
  799. p++;
  800. }
  801. if (flg & 0x10) {
  802. while (p < end && *p)
  803. p++;
  804. p++;
  805. }
  806. if (flg & 0x02)
  807. p += 2;
  808. if (p >= end)
  809. return -1;
  810. } else if (container == 1) {
  811. if (len < 6 || (p[0] & 0x0F) != 8 || (p[0] >> 4) > 7 ||
  812. (((unsigned int)p[0] << 8) | p[1]) % 31 != 0 ||
  813. (p[1] & 0x20))
  814. return -1;
  815. p += 2;
  816. }
  817. f.in = p;
  818. f.in_end = end;
  819. f.bitbuf = 0;
  820. f.bitcnt = 0;
  821. f.over = 0;
  822. f.out = f.out_start = (unsigned char *)dst;
  823. f.out_end = f.out_start + cap;
  824. if (fz_blocks(&f, (struct fz_ws *)ws))
  825. return -1;
  826. n = (unsigned int)(f.out - f.out_start);
  827. if (container == 2) {
  828. unsigned int crc, size;
  829. if (f.in_end - f.in < 8)
  830. return -1;
  831. crc_table_init();
  832. crc = crc_update(0xFFFFFFFFu, f.out_start, n) ^ 0xFFFFFFFFu;
  833. if (crc != (f.in[0] | ((unsigned int)f.in[1] << 8) |
  834. ((unsigned int)f.in[2] << 16) |
  835. ((unsigned int)f.in[3] << 24)))
  836. return -1;
  837. size = f.in[4] | ((unsigned int)f.in[5] << 8) |
  838. ((unsigned int)f.in[6] << 16) |
  839. ((unsigned int)f.in[7] << 24);
  840. if (size != n)
  841. return -1;
  842. } else if (container == 1) {
  843. unsigned int a = 1, b = 0;
  844. if (f.in_end - f.in < 4)
  845. return -1;
  846. adler_update(&a, &b, f.out_start, n);
  847. if (((b << 16) | a) != (((unsigned int)f.in[0] << 24) |
  848. ((unsigned int)f.in[1] << 16) |
  849. ((unsigned int)f.in[2] << 8) | f.in[3]))
  850. return -1;
  851. }
  852. if (out_len)
  853. *out_len = n;
  854. return 0;
  855. }
  856. int inflate_zlib_mem(const void *src, unsigned int len, void *dst,
  857. unsigned int cap, unsigned int *out_len, void *ws)
  858. {
  859. return fz_inflate(src, len, dst, cap, out_len, ws, 1);
  860. }
  861. int inflate_gzip_mem(const void *src, unsigned int len, void *dst,
  862. unsigned int cap, unsigned int *out_len, void *ws)
  863. {
  864. return fz_inflate(src, len, dst, cap, out_len, ws, 2);
  865. }
  866. int inflate_raw_mem(const void *src, unsigned int len, void *dst,
  867. unsigned int cap, unsigned int *out_len, void *ws)
  868. {
  869. return fz_inflate(src, len, dst, cap, out_len, ws, 0);
  870. }