[FFmpeg-devel] [PATCH 1/2] [RFC] proof-of-concept minimal inflate.
Reimar Döffinger
Reimar.Doeffinger at gmx.de
Thu Mar 24 16:33:29 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 small fallback implementation that should
run at reasonable speed but is not optimized and
lacks crazy features like being able to interrupt
decompressing at any point in the stream, which hides
a lot of behaviour.
The main thing making it slower is that the static
huffman table often used for small blocks is generated
dynamically, and it could be further optimized using
the GET_VLC and similar macros.
Signed-off-by: Reimar Döffinger <Reimar.Doeffinger at gmx.de>
---
libavcodec/inflate.c | 279 +++++++++++++++++++++++++++++++++++++++++++++++++++
libavcodec/inflate.h | 54 ++++++++++
2 files changed, 333 insertions(+)
create mode 100644 libavcodec/inflate.c
create mode 100644 libavcodec/inflate.h
diff --git a/libavcodec/inflate.c b/libavcodec/inflate.c
new file mode 100644
index 0000000..3218db9
--- /dev/null
+++ b/libavcodec/inflate.c
@@ -0,0 +1,279 @@
+/*
+ * Inflate decompression
+ *
+ * Copyright (c) 2016 Reimar Döffinger <Reimar.Doeffinger at gmx.de>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "inflate.h"
+
+#define BITSTREAM_READER_LE 1
+
+#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 int get_static_huff(VLC *v, VLC *dv)
+{
+ int ret;
+ 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, 8, 288 - 280);
+ memset(main_bits + 288, 5, 32);
+
+ bits2codes(main_codes, main_bits, 288);
+ ff_free_vlc(v);
+ ret = init_vlc(v, 9, 288, main_bits, 1, 1, main_codes, 2, 2, INIT_VLC_LE);
+ if (ret < 0) return ret;
+ bits2codes(main_codes + 288, main_bits + 288, 32);
+ ff_free_vlc(dv);
+ ret = init_vlc(dv, 9, 32, main_bits + 288, 1, 1, main_codes + 288, 2, 2, INIT_VLC_LE);
+ if (ret < 0) return ret;
+ return 0;
+}
+
+static int build_dyn_huff(GetBitContext *gb, VLC *v, VLC *dv)
+{
+ VLC tmpv;
+ int i, max, ret;
+ 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);
+ ret = init_vlc(&tmpv, 7, 19, clen_bits, 1, 1, clen_codes, 2, 2, INIT_VLC_LE);
+ if (ret < 0) goto err_out;
+ i = 0;
+ max = hlit + hdist;
+ do {
+ int code = get_vlc2(gb, tmpv.table, 7, 1);
+ if (code < 0 || code > 18 || get_bits_left(gb) < 0) goto err_out;
+ if (code < 16) {
+ main_bits[i++] = code;
+ } else if (code == 16) {
+ int cnt = get_bits(gb, 2) + 3;
+ if (cnt > max - i) goto err_out;
+ if (i == 0) goto err_out;
+ 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);
+ bits2codes(main_codes, main_bits, hlit);
+ ff_free_vlc(&tmpv);
+ ff_free_vlc(v);
+ ret = init_vlc(v, 9, hlit, main_bits, 1, 1, main_codes, 2, 2, INIT_VLC_LE);
+ if (ret < 0) goto err_out;
+ bits2codes(main_codes + hlit, main_bits + hlit, hdist);
+ ff_free_vlc(dv);
+ ret = init_vlc(dv, 9, hdist, main_bits + hlit, 1, 1, main_codes + hlit, 2, 2, INIT_VLC_LE);
+ if (ret < 0) goto err_out;
+ return 0;
+
+err_out:
+ ff_free_vlc(&tmpv);
+ return get_bits_left(gb) < 0 ? AVERROR_EOF : AVERROR_INVALIDDATA;
+}
+
+static int inflate_block(GetBitContext *gb, const VLC *v, const VLC *dv, const uint8_t *start, uint8_t *out, uint8_t *out_end)
+{
+ uint8_t *orig_out = out;
+ int code;
+ do {
+ code = get_vlc2(gb, v->table, 9, 2);
+ if (get_bits_left(gb) < 0) goto out;
+ if (code < 0 || code > 285) return AVERROR_INVALIDDATA;
+ if (code < 256) {
+ if (out >= out_end) return AVERROR_BUFFER_TOO_SMALL;
+ *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 (get_bits_left(gb) < 0) goto out;
+ if (code < 0 || code > 29) return AVERROR_INVALIDDATA;
+ dist = dist_tab[code];
+ if (code > 3) {
+ dist += get_bits(gb, (code >> 1) - 1);
+ }
+
+ if (len > out_end - out) return AVERROR_BUFFER_TOO_SMALL;
+ if (dist > out - start) return AVERROR_INVALIDDATA;
+ av_memcpy_backptr(out, dist, len);
+ out += len;
+ }
+ } while (code != 256);
+out:
+ return out - orig_out;
+}
+
+int ff_inflate(GetBitContext *gb, uint8_t *out, int *outlen, int flags)
+{
+ int done, final, type, len = 0;
+ VLC v = { .table = NULL };
+ VLC dv = { .table = NULL };
+ uint8_t *out_end = out + *outlen;
+ int ret = -1;
+ if (flags & FF_INFLATE_HAS_HEADER) skip_bits(gb, 16);
+ if (flags & FF_INFLATE_USE_DICTIONARY) {
+ if (*outlen < FF_INFLATE_DICT_SIZE) return AVERROR(EINVAL);
+ len += FF_INFLATE_DICT_SIZE;
+ } else if (flags & FF_INFLATE_UPDATE_DICTIONARY) {
+ if (*outlen < FF_INFLATE_DICT_SIZE) return AVERROR(EINVAL);
+ out += FF_INFLATE_DICT_SIZE;
+ }
+ *outlen = 0;
+ do {
+ done = 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 > out_end - (out + len)) {
+ ret = AVERROR_BUFFER_TOO_SMALL;
+ break;
+ }
+ skip_bits_long(gb, 8*ret);
+ if (get_bits_left(gb) < 0) break;
+ if ((flags & FF_INFLATE_SYNC_FLUSH) && ret == 0) done = 1;
+ memcpy(out + len, src + 4, ret);
+ break;
+ }
+ case 1:
+ ret = get_static_huff(&v, &dv);
+ if (ret < 0) break;
+ ret = inflate_block(gb, &v, &dv, out, out + len, out_end);
+ break;
+ case 2:
+ ret = build_dyn_huff(gb, &v, &dv);
+ if (ret < 0) break;
+ ret = inflate_block(gb, &v, &dv, out, out + len, out_end);
+ break;
+ case 3:
+ ret = AVERROR_INVALIDDATA;
+ break;
+ }
+ if (get_bits_left(gb) < 0 || ret == AVERROR_EOF) {
+ if (ret > 0) len += ret;
+ ret = AVERROR_EOF;
+ goto eof_out;
+ }
+ if (ret < 0) goto out;
+ len += ret;
+ } while (!done);
+ ret = final;
+
+eof_out:
+ if (flags & FF_INFLATE_USE_DICTIONARY) {
+ len -= FF_INFLATE_DICT_SIZE;
+ } else if (flags & FF_INFLATE_UPDATE_DICTIONARY) {
+ out -= FF_INFLATE_DICT_SIZE;
+ }
+ if (flags & FF_INFLATE_UPDATE_DICTIONARY) {
+ if (len < FF_INFLATE_DICT_SIZE) {
+ if (flags & FF_INFLATE_USE_DICTIONARY) {
+ memmove(out, out + len, FF_INFLATE_DICT_SIZE);
+ } else {
+ memset(out, 0, FF_INFLATE_DICT_SIZE - len);
+ memcpy(out + FF_INFLATE_DICT_SIZE - len, out + FF_INFLATE_DICT_SIZE, len);
+ }
+ } else {
+ memcpy(out, out + len, FF_INFLATE_DICT_SIZE);
+ }
+ }
+ *outlen = len;
+
+out:
+ ff_free_vlc(&v);
+ ff_free_vlc(&dv);
+ return ret;
+}
+
+#ifdef TEST
+int main(int argc, char **argv)
+{
+ uint8_t in[4096];
+ uint8_t out[8*4096] = {0};
+ int ret;
+ int outs = sizeof(out) - 1;
+ FILE *f = fopen(argv[1], "rb");
+ int flen = fread(in, 1, sizeof(in), f);
+ GetBitContext gb;
+ fclose(f);
+ init_get_bits8(&gb, in, flen);
+ ret = ff_inflate(&gb, out, &outs, FF_INFLATE_HAS_HEADER);
+ if (ret < 0) printf("failed %i!\n", ret);
+ if (outs > 0) {
+ out[outs] = 0;
+ printf("%s", out);
+ }
+ return 0;
+}
+#endif
diff --git a/libavcodec/inflate.h b/libavcodec/inflate.h
new file mode 100644
index 0000000..3dd40eb
--- /dev/null
+++ b/libavcodec/inflate.h
@@ -0,0 +1,54 @@
+/*
+ * Header file for inflate decompression
+ *
+ * Copyright (c) 2016 Reimar Döffinger <Reimar.Doeffinger at gmx.de>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVCODEC_INFLATE_H
+#define AVCODEC_INFLATE_H
+
+#include <stdint.h>
+
+struct GetBitContext;
+
+#define FF_INFLATE_OUTPUT_PADDING 16 ///< To allow for future optimization
+#define FF_INFLATE_DICT_SIZE (32*1024)
+
+#define FF_INFLATE_HAS_HEADER 1 ///< Compressed data starts with zlib header
+#define FF_INFLATE_USE_DICTIONARY 2 ///< out starts with FF_INFLATE_DICT_SIZE bytes pre-filled with custom dictionary
+#define FF_INFLATE_UPDATE_DICTIONARY 4 ///< fill first FF_INFLATE_DICT_SIZE bytes of out with dictionary after decompression
+#define FF_INFLATE_SYNC_FLUSH 8 ///< Stop decoding after flush marker
+
+/**
+ * \param out output buffer, must allow for up to FF_INFLATE_OUTPUT_PADDING
+ * additional bytes beyond outlen/actual output being written
+ * \param outlen input: length of buffer out points to, including any initial
+ * dictionary but not including the padding
+ * output: decompressed data written, not including any dictionary
+ * \return 0: no error but not final chunk
+ * 1: final chunk decoded
+ * AVERROR_INVALIDDATA: bad syntax in stream
+ * AVERROR_EOF: unexpected EOF, input too short or incorrect termination
+ * Note: this type of error seems not detectable using zlib.
+ * AVERROR_BUFFER_TOO_SMALL: outlen too small to fit decompressed data
+ * AVERROR(EINVAL): dictionary enabled but outlen < FF_INFLATE_DICT_SIZE
+ */
+int ff_inflate(struct GetBitContext *gb, uint8_t *out, int *outlen, int flags);
+
+#endif /* AVCODEC_INFLATE_H */
--
2.7.0
More information about the ffmpeg-devel
mailing list