[FFmpeg-devel,4/4] avcodec/vp3: Make parsing Theora Huffman tables more spec-compliant

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@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(-)

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@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.)

- Andreas

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@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)