[FFmpeg-devel] [PATCH] [RFC] proof-of-concept minimal inflate.
Reimar Döffinger
Reimar.Doeffinger at gmx.de
Sat Mar 5 23:34:31 CET 2016
FFmpeg currently lacks a fallback inflate algorithm
when zlib is not available.
We have a lot of infrastructure for it already available
though, like VLC code reading (though only in libavcodec,
not libavutil).
This is a hackish quick-and-dirty version.
It certainly is not optimized, and I would want it to
be mostly small/simple, not necessarily fast anyway
as it would at most be a fallback.
Is there interest in me cleaning up the code and
integrating it as fallback, or are you all happy
with zlib and I should drop it?
I at least like that readability-wise this code
is miles and miles ahead of zlib...
---
libavcodec/inflate.c | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 192 insertions(+)
create mode 100644 libavcodec/inflate.c
diff --git a/libavcodec/inflate.c b/libavcodec/inflate.c
new file mode 100644
index 0000000..0340d7c
--- /dev/null
+++ b/libavcodec/inflate.c
@@ -0,0 +1,192 @@
+#define BITSTREAM_READER_LE
+
+#include "get_bits.h"
+#include "libavutil/internal.h"
+static uint16_t reverse(uint16_t x, int n)
+{
+ return (ff_reverse[x & 0xFF] << 8 | ff_reverse[x >> 8]) >> (16 - n);
+}
+
+static int bits2codes(uint16_t *codes, const uint8_t *bits, int count)
+{
+ int len_counts[16] = {0};
+ int code_starts[16] = {0};
+ int i;
+ for (i = 0; i < count; i++) {
+ av_assert0(bits[i] < 16);
+ len_counts[bits[i]]++;
+ }
+ for (i = 2; i < 16; i++)
+ code_starts[i] = (code_starts[i - 1] + len_counts[i - 1]) << 1;
+ for (i = 0; i < count; i++) {
+ int n = bits[i];
+ if (!n) continue;
+ codes[i] = code_starts[n]++;
+ codes[i] = reverse(codes[i], n);
+ }
+ for (i = 0; i < 16; i++) if (code_starts[i] > (1 << i)) return AVERROR_INVALIDDATA;
+ return 0;
+}
+
+static void get_static_huff(VLC *v, VLC *dv)
+{
+ uint8_t main_bits[288 + 32];
+ uint16_t main_codes[288 + 32];
+ memset(main_bits, 8, 144);
+ memset(main_bits + 144, 9, 256 - 144);
+ memset(main_bits + 256, 7, 280 - 256);
+ memset(main_bits + 280, 0, 288 - 280);
+ memset(main_bits + 288, 5, 32);
+
+ bits2codes(main_codes, main_bits, 288);
+ ff_free_vlc(v);
+ init_vlc(v, 9, 288, main_bits, 1, 1, main_codes, 2, 2, INIT_VLC_LE);
+ bits2codes(main_codes + 288, main_bits + 288, 32);
+ ff_free_vlc(dv);
+ init_vlc(dv, 9, 32, main_bits + 288, 1, 1, main_codes + 288, 2, 2, INIT_VLC_LE);
+}
+
+static int build_dyn_huff(GetBitContext *gb, VLC *v, VLC *dv)
+{
+ VLC tmpv;
+ int i, max;
+ uint8_t main_bits[288 + 32] = {0};
+ uint16_t main_codes[288 + 32];
+ uint8_t clen_bits[19] = {0};
+ uint16_t clen_codes[19];
+ int hlit = get_bits(gb, 5) + 257;
+ int hdist = get_bits(gb, 5) + 1;
+ int hclen = get_bits(gb, 4) + 4;
+ for (i = 0; i < hclen; i++)
+ {
+ static const uint8_t map[19] = {
+ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
+ 11, 4, 12, 3, 13, 2, 14, 1, 15};
+ clen_bits[map[i]] = get_bits(gb, 3);
+ }
+ bits2codes(clen_codes, clen_bits, 19);
+ init_vlc(&tmpv, 7, 19, clen_bits, 1, 1, clen_codes, 2, 2, INIT_VLC_LE);
+ i = 0;
+ max = hlit + hdist;
+ do {
+ int code = get_vlc2(gb, tmpv.table, 7, 1);
+ if (code < 0 || code > 18) return AVERROR_INVALIDDATA;
+ if (code < 16) {
+ main_bits[i++] = code;
+ } else if (code == 16) {
+ int cnt = get_bits(gb, 2) + 3;
+ if (cnt > max - i) return AVERROR_INVALIDDATA;
+ if (i == 0) return AVERROR_INVALIDDATA;
+ memset(main_bits + i, main_bits[i - 1], cnt);
+ i += cnt;
+ } else {
+ int cnt = code == 17 ? get_bits(gb, 3) + 3 : get_bits(gb, 7) + 11;
+ i += cnt;
+ }
+ } while (i < max);
+ ff_free_vlc(&tmpv);
+ bits2codes(main_codes, main_bits, hlit);
+ ff_free_vlc(v);
+ init_vlc(v, 9, hlit, main_bits, 1, 1, main_codes, 2, 2, INIT_VLC_LE);
+ bits2codes(main_codes + hlit, main_bits + hlit, hdist);
+ ff_free_vlc(dv);
+ init_vlc(dv, 9, hdist, main_bits + hlit, 1, 1, main_codes + hlit, 2, 2, INIT_VLC_LE);
+}
+
+static int inflate_block(GetBitContext *gb, const VLC *v, const VLC *dv, uint8_t *out, uint8_t *out_end)
+{
+ uint8_t *start = out;
+ int code;
+ do {
+ code = get_vlc2(gb, v->table, 9, 2);
+ if (code < 0 || code > 285 || get_bits_left(gb) < 0) return AVERROR_INVALIDDATA;
+ if (code < 256) {
+ if (out >= out_end) return -1;
+ *out++ = code;
+ } else if (code > 256) {
+ // Note: Overall length 258 has two encodings.
+ // We also accept the pointless inefficient one.
+ static const uint8_t len_tab[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 255};
+ static const uint16_t dist_tab[] = {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};
+ int len;
+ int dist;
+
+ code -= 257;
+ len = len_tab[code] + 3;
+ if (code >= 8 && code < 28)
+ len += get_bits(gb, (code >> 2) - 1);
+
+ code = get_vlc2(gb, dv->table, 9, 2);
+ if (code < 0 || code > 29 || get_bits_left(gb) < 0) return AVERROR_INVALIDDATA;
+ dist = dist_tab[code];
+ if (code > 3) {
+ dist += get_bits(gb, (code >> 1) - 1);
+ }
+
+ if (len > out_end - out) return -1;
+ if (dist > out - start) return AVERROR_INVALIDDATA;
+ av_memcpy_backptr(out, dist, len);
+ out += len;
+ }
+ } while (code != 256);
+ return out - start;
+}
+
+int ff_inflate(const uint8_t *in, int inlen, uint8_t *out, int outlen)
+{
+ int final, type, len = 0;
+ GetBitContext gb;
+ VLC v = { .table = NULL };
+ VLC dv = { .table = NULL };
+ uint8_t *out_end = out + outlen;
+ int ret = init_get_bits8(&gb, in, inlen);
+ if (ret < 0) return ret;
+ do {
+ final = get_bits1(&gb);
+ type = get_bits(&gb, 2);
+ switch (type) {
+ case 0: {
+ const uint8_t *src = align_get_bits(&gb);
+ ret = get_bits(&gb, 16);
+ skip_bits(&gb, 16);
+ if (ret > outlen - len) return -1;
+ skip_bits_long(&gb, 8*ret);
+ if (get_bits_left(&gb) < 0) return AVERROR_INVALIDDATA;
+ memcpy(out + len, src, ret);
+ len += ret;
+ break;
+ }
+ case 1:
+ get_static_huff(&v, &dv);
+ ret = inflate_block(&gb, &v, &dv, out, out_end);
+ break;
+ case 2:
+ ret = build_dyn_huff(&gb, &v, &dv);
+ if (ret < 0) return ret;
+ ret = inflate_block(&gb, &v, &dv, out, out_end);
+ break;
+ case 3:
+ return AVERROR_INVALIDDATA;
+ }
+ if (get_bits_left(&gb) < 0) return AVERROR_INVALIDDATA;
+ if (ret < 0) return ret;
+ if (ret > INT_MAX - len) return -1;
+ len += ret;
+ } while (!final);
+ return len;
+}
+
+int main(int argc, char **argv)
+{
+ uint8_t in[4096];
+ uint8_t out[8*4096] = {0};
+ FILE *f = fopen(argv[1], "rb");
+ int flen = fread(in, 1, sizeof(in), f);
+ int outs = ff_inflate(in + 2, flen - 2, out, sizeof(out) - 1);
+ if (outs < 0) printf("failed!\n");
+ if (outs > 0) {
+ out[outs] = 0;
+ printf("%s", out);
+ }
+ return 0;
+}
--
2.7.0
More information about the ffmpeg-devel
mailing list