| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978 |
- /* inflate: see inflate.h. A compact, bounds-checked DEFLATE decoder.
- *
- * The Huffman decoder is the canonical-code bit-at-a-time form; the LZ77
- * history is a 32 KB circular window that is also used as the output staging
- * area, so the caller's sink is called in chunks (never per byte). */
- #include "inflate.h"
- #define MAXBITS INFLATE_MAXBITS
- #define MAXLCODES 286
- #define MAXDCODES 30
- #define MAXCODES (MAXLCODES + MAXDCODES)
- #define FIXLCODES 288
- #define FASTBITS 10
- static unsigned int crc_table[256];
- static int crc_table_ready;
- static void crc_table_init(void)
- {
- unsigned int n, k, c;
- if (crc_table_ready)
- return;
- for (n = 0; n < 256; n++) {
- c = n;
- for (k = 0; k < 8; k++)
- c = (c & 1) ? (0xEDB88320u ^ (c >> 1)) : (c >> 1);
- crc_table[n] = c;
- }
- crc_table_ready = 1;
- }
- static unsigned int crc_update(unsigned int crc, const unsigned char *p,
- unsigned int len)
- {
- unsigned int i;
- for (i = 0; i < len; i++)
- crc ^= p[i], crc = (crc >> 8) ^ crc_table[crc & 0xFF];
- return crc;
- }
- static void adler_update(unsigned int *a, unsigned int *b,
- const unsigned char *p, unsigned int len)
- {
- unsigned int n;
- while (len) {
- n = len > 5552 ? 5552 : len;
- len -= n;
- while (n--) {
- *a += *p++;
- *b += *a;
- }
- *a %= 65521;
- *b %= 65521;
- }
- }
- unsigned int crc32_bytes(const void *data, unsigned int len)
- {
- crc_table_init();
- return crc_update(0xFFFFFFFFu, (const unsigned char *)data, len) ^
- 0xFFFFFFFFu;
- }
- unsigned int adler32_bytes(const void *data, unsigned int len)
- {
- unsigned int a = 1, b = 0;
- adler_update(&a, &b, (const unsigned char *)data, len);
- return (b << 16) | a;
- }
- /* ---- source ---------------------------------------------------------- */
- static int src_byte(struct inflate_src *s, unsigned int *out)
- {
- while (s->len == 0) {
- const unsigned char *p;
- unsigned int len;
- if (!s->more || !s->more(s->ctx, &p, &len) || len == 0)
- return -1;
- s->p = p;
- s->len = len;
- }
- *out = *s->p++;
- s->len--;
- return 0;
- }
- /* ---- output ---------------------------------------------------------- */
- static int flush_out(struct inflate *z)
- {
- unsigned int start, first, rest;
- int r;
- if (z->pending == 0)
- return 0;
- start = (z->wpos + 32768u - z->pending) & 32767u;
- first = z->pending;
- if (start + first > 32768u)
- first = 32768u - start;
- rest = z->pending - first;
- z->crc = crc_update(z->crc, z->win + start, first);
- adler_update(&z->adler_a, &z->adler_b, z->win + start, first);
- if (rest) {
- z->crc = crc_update(z->crc, z->win, rest);
- adler_update(&z->adler_a, &z->adler_b, z->win, rest);
- }
- r = z->sink.write(z->sink.ctx, z->win + start, first);
- if (!r && rest)
- r = z->sink.write(z->sink.ctx, z->win, rest);
- if (r)
- return -1;
- z->pending = 0;
- if (z->progress)
- z->progress(z->progress_ctx);
- return 0;
- }
- static int put_byte(struct inflate *z, unsigned int b)
- {
- z->win[z->wpos] = (unsigned char)b;
- z->wpos = (z->wpos + 1) & 32767u;
- z->total++;
- if (++z->pending >= 16384)
- return flush_out(z);
- return 0;
- }
- /* ---- bit reader ------------------------------------------------------ */
- static int need_bits(struct inflate *z, int n)
- {
- while (z->bitcnt < n) {
- unsigned int b;
- if (src_byte(&z->src, &b))
- return -1;
- z->bitbuf |= b << z->bitcnt;
- z->bitcnt += 8;
- }
- return 0;
- }
- static int get_bits(struct inflate *z, int n)
- {
- unsigned int v;
- if (n == 0)
- return 0;
- if (need_bits(z, n))
- return -1;
- v = z->bitbuf & ((1u << n) - 1u);
- z->bitbuf >>= n;
- z->bitcnt -= n;
- z->total_bits += (unsigned int)n;
- return (int)v;
- }
- static int align_byte(struct inflate *z)
- {
- int pad = (int)((8u - (unsigned int)(z->total_bits & 7u)) & 7u);
- if (pad && get_bits(z, pad) < 0)
- return -1;
- return 0;
- }
- /* ---- Huffman --------------------------------------------------------- */
- static int huff_build(struct inflate_huff *h, const unsigned char *lengths,
- int n)
- {
- unsigned short offs[MAXBITS + 1];
- int len, sym, left;
- for (len = 0; len <= MAXBITS; len++)
- h->count[len] = 0;
- for (sym = 0; sym < n; sym++)
- h->count[lengths[sym]]++;
- if (h->count[0] == n)
- return 0; /* no codes: caller rejects if it needs one */
- left = 1;
- for (len = 1; len <= MAXBITS; len++) {
- left <<= 1;
- left -= h->count[len];
- if (left < 0)
- return -1; /* over-subscribed */
- }
- offs[1] = 0;
- for (len = 1; len < MAXBITS; len++)
- offs[len + 1] = (unsigned short)(offs[len] + h->count[len]);
- for (sym = 0; sym < n; sym++)
- if (lengths[sym])
- h->symbol[offs[lengths[sym]]++] = (unsigned short)sym;
- return 1;
- }
- static int huff_decode(struct inflate *z, const struct inflate_huff *h)
- {
- int len, code = 0, first = 0, index = 0;
- for (len = 1; len <= MAXBITS; len++) {
- int b = get_bits(z, 1);
- int count;
- if (b < 0)
- return -1;
- code |= b;
- count = h->count[len];
- if (code - count < first)
- return h->symbol[index + (code - first)];
- index += count;
- first += count;
- first <<= 1;
- code <<= 1;
- }
- return -1;
- }
- /* ---- DEFLATE blocks -------------------------------------------------- */
- static const unsigned short len_base[29] = {
- 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
- 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
- };
- static const unsigned char len_ext[29] = {
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
- 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
- };
- static const unsigned short dist_base[30] = {
- 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129,
- 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097,
- 6145, 8193, 12289, 16385, 24577
- };
- static const unsigned char dist_ext[30] = {
- 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
- 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
- };
- static int copy_match(struct inflate *z, unsigned int len, unsigned int dist)
- {
- if (dist == 0 || dist > 32768u || len > 258u)
- return -1;
- while (len--) {
- unsigned int src = (z->wpos + 32768u - dist) & 32767u;
- if (put_byte(z, z->win[src]))
- return -1;
- }
- return 0;
- }
- static int codes(struct inflate *z, const struct inflate_huff *lencode,
- const struct inflate_huff *distcode)
- {
- for (;;) {
- int sym = huff_decode(z, lencode);
- int len, dsym, dist;
- if (sym < 0)
- return -1;
- if (sym < 256) {
- if (put_byte(z, (unsigned int)sym))
- return -1;
- } else if (sym == 256) {
- return 0;
- } else {
- sym -= 257;
- if (sym >= 29)
- return -1;
- len = len_base[sym];
- if (len_ext[sym]) {
- int e = get_bits(z, len_ext[sym]);
- if (e < 0)
- return -1;
- len += e;
- }
- dsym = huff_decode(z, distcode);
- if (dsym < 0 || dsym >= 30)
- return -1;
- dist = dist_base[dsym];
- if (dist_ext[dsym]) {
- int e = get_bits(z, dist_ext[dsym]);
- if (e < 0)
- return -1;
- dist += e;
- }
- if (copy_match(z, (unsigned int)len, (unsigned int)dist))
- return -1;
- }
- }
- }
- static int stored_block(struct inflate *z)
- {
- int len, nlen, i;
- len = get_bits(z, 16);
- nlen = get_bits(z, 16);
- if (len < 0 || nlen < 0 || (len ^ nlen) != 0xFFFF)
- return -1;
- for (i = 0; i < len; i++) {
- int b = get_bits(z, 8);
- if (b < 0 || put_byte(z, (unsigned int)b))
- return -1;
- }
- return 0;
- }
- static int fixed_block(struct inflate *z)
- {
- unsigned char lengths[FIXLCODES];
- static const unsigned char dist_lengths[30] = {
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
- };
- struct inflate_huff lencode, distcode;
- int i;
- for (i = 0; i < 144; i++)
- lengths[i] = 8;
- for (; i < 256; i++)
- lengths[i] = 9;
- for (; i < 280; i++)
- lengths[i] = 7;
- for (; i < 288; i++)
- lengths[i] = 8;
- if (huff_build(&lencode, lengths, 288) < 0 ||
- huff_build(&distcode, dist_lengths, 30) < 0)
- return -1;
- return codes(z, &lencode, &distcode);
- }
- static int dynamic_block(struct inflate *z)
- {
- static const unsigned char order[19] = {
- 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
- };
- unsigned char lengths[MAXCODES];
- struct inflate_huff lencode, distcode;
- int hlit, hdist, hclen, i, total;
- hlit = get_bits(z, 5);
- hdist = get_bits(z, 5);
- hclen = get_bits(z, 4);
- if (hlit < 0 || hdist < 0 || hclen < 0)
- return -1;
- hlit += 257;
- hdist += 1;
- hclen += 4;
- if (hlit > MAXLCODES || hdist > MAXDCODES)
- return -1;
- for (i = 0; i < 19; i++)
- lengths[i] = 0;
- for (i = 0; i < hclen; i++) {
- int v = get_bits(z, 3);
- if (v < 0)
- return -1;
- lengths[order[i]] = (unsigned char)v;
- }
- if (huff_build(&lencode, lengths, 19) < 0)
- return -1;
- total = hlit + hdist;
- for (i = 0; i < total; ) {
- int sym = huff_decode(z, &lencode);
- int rep, val;
- if (sym < 0)
- return -1;
- if (sym < 16) {
- lengths[i++] = (unsigned char)sym;
- continue;
- }
- if (sym == 16) {
- if (i == 0)
- return -1;
- rep = get_bits(z, 2);
- if (rep < 0)
- return -1;
- rep += 3;
- val = lengths[i - 1];
- } else if (sym == 17) {
- rep = get_bits(z, 3);
- if (rep < 0)
- return -1;
- rep += 3;
- val = 0;
- } else if (sym == 18) {
- rep = get_bits(z, 7);
- if (rep < 0)
- return -1;
- rep += 11;
- val = 0;
- } else {
- return -1;
- }
- if (i + rep > total)
- return -1;
- while (rep--)
- lengths[i++] = (unsigned char)val;
- }
- if (huff_build(&lencode, lengths, hlit) < 0)
- return -1;
- if (huff_build(&distcode, lengths + hlit, hdist) < 0)
- return -1;
- return codes(z, &lencode, &distcode);
- }
- void inflate_init(struct inflate *z, struct inflate_src *src,
- struct inflate_sink *sink)
- {
- unsigned char *p = (unsigned char *)z;
- unsigned int i;
- crc_table_init();
- for (i = 0; i < sizeof(*z); i++)
- p[i] = 0;
- z->src = *src;
- z->sink = *sink;
- z->crc = 0xFFFFFFFFu;
- z->adler_a = 1;
- z->adler_b = 0;
- }
- static int inflate_blocks(struct inflate *z)
- {
- for (;;) {
- int last = get_bits(z, 1);
- int type = get_bits(z, 2);
- int r;
- if (last < 0 || type < 0)
- return -1;
- if (type == 0) {
- if (align_byte(z))
- return -1;
- r = stored_block(z);
- } else if (type == 1) {
- r = fixed_block(z);
- } else if (type == 2) {
- r = dynamic_block(z);
- } else {
- return -1;
- }
- if (r)
- return -1;
- if (last)
- break;
- }
- return flush_out(z);
- }
- int inflate_raw(struct inflate *z, unsigned int *out_len)
- {
- if (inflate_blocks(z))
- return -1;
- if (out_len)
- *out_len = (unsigned int)z->total;
- return 0;
- }
- int inflate_zlib(struct inflate *z, unsigned int *out_len)
- {
- unsigned int cmf, flg, want;
- int i;
- if (src_byte(&z->src, &cmf) || src_byte(&z->src, &flg))
- return -1;
- if ((cmf & 0x0F) != 8 || (cmf >> 4) > 7)
- return -1;
- if (((cmf << 8) | flg) % 31 != 0)
- return -1;
- if (flg & 0x20) /* preset dictionary: not supported */
- return -1;
- if (inflate_blocks(z))
- return -1;
- if (align_byte(z))
- return -1;
- want = 0;
- for (i = 0; i < 4; i++) {
- int b = get_bits(z, 8);
- if (b < 0)
- return -1;
- want = (want << 8) | (unsigned int)b; /* zlib is big-endian */
- }
- if (want != ((z->adler_b << 16) | z->adler_a))
- return -1;
- if (out_len)
- *out_len = (unsigned int)z->total;
- return 0;
- }
- int inflate_gzip(struct inflate *z, unsigned int *out_len)
- {
- unsigned int id1, id2, cm, flg, b, skip, want_crc, want_size;
- int i;
- if (src_byte(&z->src, &id1) || src_byte(&z->src, &id2) ||
- src_byte(&z->src, &cm) || src_byte(&z->src, &flg))
- return -1;
- if (id1 != 0x1F || id2 != 0x8B || cm != 8)
- return -1;
- for (i = 0; i < 6; i++) /* MTIME, XFL, OS */
- if (src_byte(&z->src, &b))
- return -1;
- if (flg & 0x04) { /* FEXTRA */
- unsigned int lo, hi;
- if (src_byte(&z->src, &lo) || src_byte(&z->src, &hi))
- return -1;
- skip = lo | (hi << 8);
- while (skip--)
- if (src_byte(&z->src, &b))
- return -1;
- }
- if (flg & 0x08) { /* FNAME */
- do {
- if (src_byte(&z->src, &b))
- return -1;
- } while (b);
- }
- if (flg & 0x10) { /* FCOMMENT */
- do {
- if (src_byte(&z->src, &b))
- return -1;
- } while (b);
- }
- if (flg & 0x02) { /* FHCRC */
- if (src_byte(&z->src, &b) || src_byte(&z->src, &b))
- return -1;
- }
- if (inflate_blocks(z))
- return -1;
- if (align_byte(z))
- return -1;
- /* The trailer: CRC32 then ISIZE, both little-endian. */
- want_crc = 0;
- for (i = 0; i < 4; i++) {
- int v = get_bits(z, 8);
- if (v < 0)
- return -1;
- want_crc |= (unsigned int)v << (8 * i);
- }
- want_size = 0;
- for (i = 0; i < 4; i++) {
- int v = get_bits(z, 8);
- if (v < 0)
- return -1;
- want_size |= (unsigned int)v << (8 * i);
- }
- if ((want_crc ^ 0xFFFFFFFFu) != z->crc)
- return -1;
- if (want_size != (unsigned int)z->total)
- return -1;
- if (out_len)
- *out_len = (unsigned int)z->total;
- return 0;
- }
- /* ---- whole-buffer fast path ----------------------------------------
- *
- * The streaming decoder above reads one bit per Huffman step and stages
- * every byte in the 32 KB ring. When the whole input and output are in
- * memory (the boot rootfs, PNG/HTTP bodies decoded into one buffer) that
- * is needlessly slow: here the output buffer itself is the LZ77 history,
- * the bit buffer is refilled a byte at a time up to 32 bits, and codes of
- * up to FASTBITS are resolved with one table lookup. Longer codes fall
- * back to the canonical walk on the bits already in the buffer. Only the
- * checksum the container needs is computed, once, over the finished
- * output. The tables live in the caller's struct-inflate workspace. */
- #define FAST_SIZE (1u << FASTBITS)
- struct fhuff {
- struct inflate_huff h;
- unsigned short fast[FAST_SIZE]; /* (sym << 4) | len, 0 = slow */
- };
- struct fz {
- const unsigned char *in, *in_end;
- unsigned int bitbuf;
- int bitcnt;
- unsigned int over; /* zero bytes padded past the end */
- unsigned char *out, *out_start, *out_end;
- };
- struct fz_ws {
- struct fhuff lit, dist;
- };
- static void fz_refill(struct fz *f)
- {
- while (f->bitcnt <= 24) {
- unsigned int b = 0;
- if (f->in < f->in_end)
- b = *f->in++;
- else
- f->over++;
- f->bitbuf |= b << f->bitcnt;
- f->bitcnt += 8;
- }
- }
- static int fz_bits(struct fz *f, int n)
- {
- unsigned int v;
- if (f->bitcnt < n)
- fz_refill(f);
- v = f->bitbuf & ((1u << n) - 1u);
- f->bitbuf >>= n;
- f->bitcnt -= n;
- return (int)v;
- }
- static int fhuff_build(struct fhuff *fh, const unsigned char *lengths, int n)
- {
- unsigned int next[MAXBITS + 2];
- int r, len, sym, i;
- r = huff_build(&fh->h, lengths, n);
- if (r < 0)
- return -1;
- for (i = 0; i < (int)FAST_SIZE; i++)
- fh->fast[i] = 0;
- {
- /* next[len] = first canonical code of length len. */
- unsigned int c = 0;
- next[1] = 0;
- for (len = 1; len < MAXBITS; len++) {
- c = (c + fh->h.count[len]) << 1;
- next[len + 1] = c;
- }
- }
- for (sym = 0; sym < n; sym++) {
- unsigned int c, rev = 0;
- int l = lengths[sym], k;
- if (!l)
- continue;
- c = next[l]++;
- if (l > FASTBITS)
- continue;
- for (k = 0; k < l; k++)
- rev |= ((c >> k) & 1u) << (l - 1 - k);
- for (; rev < FAST_SIZE; rev += 1u << l)
- fh->fast[rev] = (unsigned short)((sym << 4) | l);
- }
- return r;
- }
- static int fz_decode(struct fz *f, const struct fhuff *fh)
- {
- unsigned int e;
- int len, code = 0, first = 0, index = 0;
- if (f->bitcnt < MAXBITS)
- fz_refill(f);
- e = fh->fast[f->bitbuf & (FAST_SIZE - 1u)];
- if (e) {
- f->bitbuf >>= e & 15u;
- f->bitcnt -= (int)(e & 15u);
- return (int)(e >> 4);
- }
- for (len = 1; len <= MAXBITS; len++) {
- int count;
- code |= (int)(f->bitbuf & 1u);
- f->bitbuf >>= 1;
- f->bitcnt--;
- count = fh->h.count[len];
- if (code - count < first)
- return fh->h.symbol[index + (code - first)];
- index += count;
- first += count;
- first <<= 1;
- code <<= 1;
- }
- return -1;
- }
- static int fz_codes(struct fz *f, const struct fhuff *lit,
- const struct fhuff *dist)
- {
- for (;;) {
- int sym = fz_decode(f, lit);
- unsigned int len, d;
- unsigned char *out, *src;
- if (sym < 256) {
- if (sym < 0 || f->out >= f->out_end)
- return -1;
- *f->out++ = (unsigned char)sym;
- continue;
- }
- if (sym == 256)
- return f->over > 4 ? -1 : 0;
- sym -= 257;
- if (sym >= 29)
- return -1;
- len = len_base[sym];
- if (len_ext[sym])
- len += (unsigned int)fz_bits(f, len_ext[sym]);
- sym = fz_decode(f, dist);
- if (sym < 0 || sym >= 30)
- return -1;
- d = dist_base[sym];
- if (dist_ext[sym])
- d += (unsigned int)fz_bits(f, dist_ext[sym]);
- out = f->out;
- if (d > (unsigned int)(out - f->out_start) ||
- len > (unsigned int)(f->out_end - out))
- return -1;
- src = out - d;
- if (d >= 4) {
- while (len >= 4) {
- out[0] = src[0]; out[1] = src[1];
- out[2] = src[2]; out[3] = src[3];
- out += 4; src += 4; len -= 4;
- }
- }
- while (len--)
- *out++ = *src++;
- f->out = out;
- }
- }
- static int fz_blocks(struct fz *f, struct fz_ws *ws)
- {
- static const unsigned char order[19] = {
- 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
- };
- unsigned char lengths[FIXLCODES + MAXDCODES];
- int last, type, i;
- do {
- last = fz_bits(f, 1);
- type = fz_bits(f, 2);
- if (type == 0) {
- unsigned int len, nlen;
- fz_bits(f, f->bitcnt & 7);
- len = (unsigned int)fz_bits(f, 16);
- nlen = (unsigned int)fz_bits(f, 16);
- if ((len ^ nlen) != 0xFFFFu ||
- len > (unsigned int)(f->out_end - f->out))
- return -1;
- /* Return the whole buffered bytes to the input and
- * copy the stored data straight from it. */
- {
- unsigned int back = (unsigned int)f->bitcnt >> 3;
- if (back < f->over)
- return -1;
- f->in -= back - f->over;
- f->bitbuf = 0;
- f->bitcnt = 0;
- f->over = 0;
- }
- if (len > (unsigned int)(f->in_end - f->in))
- return -1;
- while (len--)
- *f->out++ = *f->in++;
- } else if (type == 1) {
- for (i = 0; i < 144; i++)
- lengths[i] = 8;
- for (; i < 256; i++)
- lengths[i] = 9;
- for (; i < 280; i++)
- lengths[i] = 7;
- for (; i < 288; i++)
- lengths[i] = 8;
- for (i = 0; i < 30; i++)
- lengths[288 + i] = 5;
- if (fhuff_build(&ws->lit, lengths, 288) < 0 ||
- fhuff_build(&ws->dist, lengths + 288, 30) < 0 ||
- fz_codes(f, &ws->lit, &ws->dist))
- return -1;
- } else if (type == 2) {
- int hlit = fz_bits(f, 5) + 257;
- int hdist = fz_bits(f, 5) + 1;
- int hclen = fz_bits(f, 4) + 4;
- int total = hlit + hdist;
- if (hlit > MAXLCODES || hdist > MAXDCODES)
- return -1;
- for (i = 0; i < 19; i++)
- lengths[i] = 0;
- for (i = 0; i < hclen; i++)
- lengths[order[i]] = (unsigned char)fz_bits(f, 3);
- if (fhuff_build(&ws->lit, lengths, 19) < 0)
- return -1;
- for (i = 0; i < total; ) {
- int sym = fz_decode(f, &ws->lit), rep, val;
- if (sym < 0)
- return -1;
- if (sym < 16) {
- lengths[i++] = (unsigned char)sym;
- continue;
- }
- if (sym == 16) {
- if (i == 0)
- return -1;
- rep = 3 + fz_bits(f, 2);
- val = lengths[i - 1];
- } else if (sym == 17) {
- rep = 3 + fz_bits(f, 3);
- val = 0;
- } else {
- rep = 11 + fz_bits(f, 7);
- val = 0;
- }
- if (i + rep > total)
- return -1;
- while (rep--)
- lengths[i++] = (unsigned char)val;
- }
- if (fhuff_build(&ws->lit, lengths, hlit) < 0 ||
- fhuff_build(&ws->dist, lengths + hlit, hdist) < 0 ||
- fz_codes(f, &ws->lit, &ws->dist))
- return -1;
- } else {
- return -1;
- }
- if (f->over > 4)
- return -1;
- } while (!last);
- /* Byte-align and hand the whole bytes still buffered back to the
- * input, so the container trailer is read from memory. */
- fz_bits(f, f->bitcnt & 7);
- {
- unsigned int back = (unsigned int)f->bitcnt >> 3;
- if (back < f->over)
- return -1; /* consumed padding: truncated */
- f->in -= back - f->over;
- f->bitbuf = 0;
- f->bitcnt = 0;
- f->over = 0;
- }
- return 0;
- }
- /* container: 0 raw, 1 zlib, 2 gzip */
- static int fz_inflate(const void *src, unsigned int len, void *dst,
- unsigned int cap, unsigned int *out_len, void *ws,
- int container)
- {
- struct fz f;
- const unsigned char *p = (const unsigned char *)src;
- const unsigned char *end = p + len;
- unsigned int n;
- if (container == 2) {
- unsigned int flg;
- if (len < 18 || p[0] != 0x1F || p[1] != 0x8B || p[2] != 8)
- return -1;
- flg = p[3];
- p += 10;
- if (flg & 0x04) {
- if (end - p < 2)
- return -1;
- n = p[0] | ((unsigned int)p[1] << 8);
- p += 2;
- if ((unsigned int)(end - p) < n)
- return -1;
- p += n;
- }
- if (flg & 0x08) {
- while (p < end && *p)
- p++;
- p++;
- }
- if (flg & 0x10) {
- while (p < end && *p)
- p++;
- p++;
- }
- if (flg & 0x02)
- p += 2;
- if (p >= end)
- return -1;
- } else if (container == 1) {
- if (len < 6 || (p[0] & 0x0F) != 8 || (p[0] >> 4) > 7 ||
- (((unsigned int)p[0] << 8) | p[1]) % 31 != 0 ||
- (p[1] & 0x20))
- return -1;
- p += 2;
- }
- f.in = p;
- f.in_end = end;
- f.bitbuf = 0;
- f.bitcnt = 0;
- f.over = 0;
- f.out = f.out_start = (unsigned char *)dst;
- f.out_end = f.out_start + cap;
- if (fz_blocks(&f, (struct fz_ws *)ws))
- return -1;
- n = (unsigned int)(f.out - f.out_start);
- if (container == 2) {
- unsigned int crc, size;
- if (f.in_end - f.in < 8)
- return -1;
- crc_table_init();
- crc = crc_update(0xFFFFFFFFu, f.out_start, n) ^ 0xFFFFFFFFu;
- if (crc != (f.in[0] | ((unsigned int)f.in[1] << 8) |
- ((unsigned int)f.in[2] << 16) |
- ((unsigned int)f.in[3] << 24)))
- return -1;
- size = f.in[4] | ((unsigned int)f.in[5] << 8) |
- ((unsigned int)f.in[6] << 16) |
- ((unsigned int)f.in[7] << 24);
- if (size != n)
- return -1;
- } else if (container == 1) {
- unsigned int a = 1, b = 0;
- if (f.in_end - f.in < 4)
- return -1;
- adler_update(&a, &b, f.out_start, n);
- if (((b << 16) | a) != (((unsigned int)f.in[0] << 24) |
- ((unsigned int)f.in[1] << 16) |
- ((unsigned int)f.in[2] << 8) | f.in[3]))
- return -1;
- }
- if (out_len)
- *out_len = n;
- return 0;
- }
- int inflate_zlib_mem(const void *src, unsigned int len, void *dst,
- unsigned int cap, unsigned int *out_len, void *ws)
- {
- return fz_inflate(src, len, dst, cap, out_len, ws, 1);
- }
- int inflate_gzip_mem(const void *src, unsigned int len, void *dst,
- unsigned int cap, unsigned int *out_len, void *ws)
- {
- return fz_inflate(src, len, dst, cap, out_len, ws, 2);
- }
- int inflate_raw_mem(const void *src, unsigned int len, void *dst,
- unsigned int cap, unsigned int *out_len, void *ws)
- {
- return fz_inflate(src, len, dst, cap, out_len, ws, 0);
- }
|