/* 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); }