[FFmpeg-devel] [PATCH 4/4] avcodec/vp3: Make parsing Theora Huffman tables more spec-compliant
Peter Ross
pross at xvid.org
Sun Oct 25 23:41:53 EET 2020
On Sun, Oct 25, 2020 at 09:02:25AM +0100, Andreas Rheinhardt wrote:
> Andreas Rheinhardt:
> > Theora allows to use custom Huffman tables which are coded in the
> > bitstream as a tree: Whether the next node is a leaf or not is coded
> > in a bit; each node itself contains a five bit token. Each tree can
> > contain at most 32 leafs; typically they contain exactly 32 with the 32
> > symbols forming a permutation of 0..31. Yet the standard does not impose
> > either of these requirements. It explicitly allows less than 32 leafs
> > and multiple codes with the same token.
> >
> > But our decoder used an algorithm that required the codes->token mapping
> > to be injective and that also presumed that there be at least two leafs:
> > Instead of using an array for codes, tokens and code lengths, the
> > decoder only had arrays for codes and code lengths. The code and length
> > for a given token were stored in entry[token]. As no symbols table was
> > used when initializing the VLC, the default one applied and therefore
> > the entry[token] got the symbol token (if the length of said entry is >0).
> > Yet if multiple codes had the same token, the codes and lengths from the
> > later token would overwrite the earlier codes and lengths.
> >
> > Furthermore, less than 32 leafs could also lead to problems: Namely if
> > this was not the first time Huffman tables have been parsed in which
> > case the array is not zeroed initially so that old entries could make
> > the new table invalid.
> >
> > libtheora seems to always use 32 leafs and no duplicate tokens; I am not
> > aware of any existing valid files that do not.
> >
> > This is fixed by using a codes, symbols and lengths array when
> > initializing the VLC. In order to reduce the amount of stuff kept in the
> > context only the symbols and lengths (which both fit into an uint8_t)
> > are kept in the context; the codes are derived from the lengths
> > immediately before creating the tables.
> >
> > There is now only one thing left which is not spec-compliant: Trees with
> > only one node (which has length zero) are not supported by
> > ff_init_vlc_sparse() yet.
> >
> > Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
> > ---
> > My initial aim with this was btw to switch all the callers
> > ff_init_vlc_sparse() with bits_size != 1 to use only uint8_t for the
> > bits (== lengths) to simplify reading them in ff_init_vlc_sparse().
> >
> > libavcodec/vp3.c | 85 ++++++++++++++++++++++++------------------------
> > 1 file changed, 43 insertions(+), 42 deletions(-)
> >
> > diff --git a/libavcodec/vp3.c b/libavcodec/vp3.c
> > index e629a18b8e..a6e9d44302 100644
> > --- a/libavcodec/vp3.c
> > +++ b/libavcodec/vp3.c
> > @@ -155,6 +155,15 @@ typedef struct {
> >
> > #define MIN_DEQUANT_VAL 2
> >
> > +typedef struct HuffEntry {
> > + uint8_t len, sym;
> > +} HuffEntry;
> > +
> > +typedef struct HuffTable {
> > + HuffEntry entries[32];
> > + uint8_t nb_entries;
> > +} HuffTable;
> > +
> > typedef struct Vp3DecodeContext {
> > AVCodecContext *avctx;
> > int theora, theora_tables, theora_header;
> > @@ -285,11 +294,7 @@ typedef struct Vp3DecodeContext {
> > uint8_t *edge_emu_buffer;
> >
> > /* Huffman decode */
> > - int hti;
> > - unsigned int hbits;
> > - int entries;
> > - int huff_code_size;
> > - uint32_t huffman_table[80][32][2];
> > + HuffTable huffman_table[80];
> >
> > uint8_t filter_limit_values[64];
> > DECLARE_ALIGNED(8, int, bounding_values_array)[256 + 2];
> > @@ -2309,6 +2314,20 @@ static av_cold int init_frames(Vp3DecodeContext *s)
> > return 0;
> > }
> >
> > +static av_cold int theora_init_huffman_tables(VLC *vlc, const HuffTable *huff)
> > +{
> > + uint32_t code = 0, codes[32];
> > +
> > + for (unsigned i = 0; i < huff->nb_entries; i++) {
> > + codes[i] = code >> (31 - huff->entries[i].len);
> > + code += 0x80000000U >> huff->entries[i].len;
> > + }
> > + return ff_init_vlc_sparse(vlc, 11, huff->nb_entries,
> > + &huff->entries[0].len, sizeof(huff->entries[0]), 1,
> > + codes, 4, 4,
> > + &huff->entries[0].sym, sizeof(huff->entries[0]), 1, 0);
> > +}
> > +
> > static av_cold int vp3_decode_init(AVCodecContext *avctx)
> > {
> > Vp3DecodeContext *s = avctx->priv_data;
> > @@ -2432,10 +2451,9 @@ static av_cold int vp3_decode_init(AVCodecContext *avctx)
> > }
> > } else {
> > for (i = 0; i < 80; i++) {
> > - if (init_vlc(&s->xc_vlc[i], 11, 32,
> > - &s->huffman_table[i][0][1], 8, 4,
> > - &s->huffman_table[i][0][0], 8, 4, 0) < 0)
> > - goto vlc_fail;
> > + ret = theora_init_huffman_tables(&s->xc_vlc[i], &s->huffman_table[i]);
> > + if (ret < 0)
> > + return ret;
> > }
> > }
> >
> > @@ -2476,10 +2494,6 @@ static av_cold int vp3_decode_init(AVCodecContext *avctx)
> > #endif
> >
> > return allocate_tables(avctx);
> > -
> > -vlc_fail:
> > - av_log(avctx, AV_LOG_FATAL, "Invalid huffman table\n");
> > - return -1;
> > }
> >
> > /// Release and shuffle frames after decode finishes
> > @@ -2811,36 +2825,30 @@ error:
> > return ret;
> > }
> >
> > -static int read_huffman_tree(AVCodecContext *avctx, GetBitContext *gb)
> > +static int read_huffman_tree(HuffTable *huff, GetBitContext *gb, int length,
> > + AVCodecContext *avctx)
> > {
> > - Vp3DecodeContext *s = avctx->priv_data;
> > -
> > if (get_bits1(gb)) {
> > int token;
> > - if (s->entries >= 32) { /* overflow */
> > + if (huff->nb_entries >= 32) { /* overflow */
> > av_log(avctx, AV_LOG_ERROR, "huffman tree overflow\n");
> > return -1;
> > }
> > token = get_bits(gb, 5);
> > - ff_dlog(avctx, "hti %d hbits %x token %d entry : %d size %d\n",
> > - s->hti, s->hbits, token, s->entries, s->huff_code_size);
> > - s->huffman_table[s->hti][token][0] = s->hbits;
> > - s->huffman_table[s->hti][token][1] = s->huff_code_size;
> > - s->entries++;
> > + ff_dlog(avctx, "code length %d, curr entry %d, token %d\n",
> > + length, huff->nb_entries, token);
> > + huff->entries[huff->nb_entries++] = (HuffEntry){ length, token };
> > } else {
> > - if (s->huff_code_size >= 32) { /* overflow */
> > + /* The following bound follows from the fact that nb_entries <= 32. */
> > + if (length >= 31) { /* overflow */
> > av_log(avctx, AV_LOG_ERROR, "huffman tree overflow\n");
> > return -1;
> > }
> > - s->huff_code_size++;
> > - s->hbits <<= 1;
> > - if (read_huffman_tree(avctx, gb))
> > + length++;
> > + if (read_huffman_tree(huff, gb, length, avctx))
> > return -1;
> > - s->hbits |= 1;
> > - if (read_huffman_tree(avctx, gb))
> > + if (read_huffman_tree(huff, gb, length, avctx))
> > return -1;
> > - s->hbits >>= 1;
> > - s->huff_code_size--;
> > }
> > return 0;
> > }
> > @@ -2965,7 +2973,7 @@ static int theora_decode_header(AVCodecContext *avctx, GetBitContext *gb)
> > static int theora_decode_tables(AVCodecContext *avctx, GetBitContext *gb)
> > {
> > Vp3DecodeContext *s = avctx->priv_data;
> > - int i, n, matrices, inter, plane;
> > + int i, n, matrices, inter, plane, ret;
> >
> > if (!s->theora_header)
> > return AVERROR_INVALIDDATA;
> > @@ -3057,17 +3065,10 @@ static int theora_decode_tables(AVCodecContext *avctx, GetBitContext *gb)
> > }
> >
> > /* Huffman tables */
> > - for (s->hti = 0; s->hti < 80; s->hti++) {
> > - s->entries = 0;
> > - s->huff_code_size = 1;
> > - if (!get_bits1(gb)) {
> > - s->hbits = 0;
> > - if (read_huffman_tree(avctx, gb))
> > - return -1;
> > - s->hbits = 1;
> > - if (read_huffman_tree(avctx, gb))
> > - return -1;
> > - }
> > + for (int i = 0; i < 80; i++) {
> > + s->huffman_table[i].nb_entries = 0;
> > + if ((ret = read_huffman_tree(&s->huffman_table[i], gb, 0, avctx)) < 0)
> > + return ret;
> > }
> >
> > s->theora_tables = 1;
> >
> Ping. (There is now a trivial merge conflict due to me using 80 as loop
> bound in the patch above, but using FF_ARRAY_ELEMS in the patch that has
> actually been applied to master. I can resend it if you like.)
looks good
-- Peter
(A907 E02F A6E5 0CD2 34CD 20D2 6760 79C5 AC40 DD6B)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20201026/9f2d8b41/attachment.sig>
More information about the ffmpeg-devel
mailing list