[FFmpeg-devel,1/2] avcodec/rv34: Don't needlessly copy VLC length and symbol arrays

Most of the VLCs used by RealVideo 3 and 4 obey three simple rules:
Shorter codes are on the left of the tree, for each length, the symbols
are ascending from left to right and the symbols either form a
permutation of 1..size or 0..(size - 1). For the latter case, one just
needs to store the length of each symbol and create the codes according
to the other rules; no explicit code or symbol array must be stored.
The former case is also treated in much the same way by artificially
assigning a length of zero to the symbol 0; when a length of zero was
encountered, the element was ignored except that the symbol counter was
still incremented. If the length was nonzero, the symbol would be
assigned via the symbol counter and the length copied over into a new
array.

Yet this is unnecessary, as ff_init_vlc_sparse() follows exactly the
same pattern: If a length of zero is encountered, the element is ignored
and only the symbol counter incremented. So one can directly forward the
length array and also need not create a symbol table oneself, because
ff_init_vlc_sparse() will infer the same symbol table in this case.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
---
 libavcodec/rv34.c | 40 ++++++++++++++++++----------------------
 1 file changed, 18 insertions(+), 22 deletions(-)

Andreas Rheinhardt:
> Most of the VLCs used by RealVideo 3 and 4 obey three simple rules:
> Shorter codes are on the left of the tree, for each length, the symbols
> are ascending from left to right and the symbols either form a
> permutation of 1..size or 0..(size - 1). For the latter case, one just
> needs to store the length of each symbol and create the codes according
> to the other rules; no explicit code or symbol array must be stored.
> The former case is also treated in much the same way by artificially
> assigning a length of zero to the symbol 0; when a length of zero was
> encountered, the element was ignored except that the symbol counter was
> still incremented. If the length was nonzero, the symbol would be
> assigned via the symbol counter and the length copied over into a new
> array.
> 
> Yet this is unnecessary, as ff_init_vlc_sparse() follows exactly the
> same pattern: If a length of zero is encountered, the element is ignored
> and only the symbol counter incremented. So one can directly forward the
> length array and also need not create a symbol table oneself, because
> ff_init_vlc_sparse() will infer the same symbol table in this case.
> 
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> ---
>  libavcodec/rv34.c | 40 ++++++++++++++++++----------------------
>  1 file changed, 18 insertions(+), 22 deletions(-)
> 
> diff --git a/libavcodec/rv34.c b/libavcodec/rv34.c
> index ec0cd27916..d251c6817c 100644
> --- a/libavcodec/rv34.c
> +++ b/libavcodec/rv34.c
> @@ -106,37 +106,33 @@ static VLC_TYPE table_data[117592][2];
>   * @param insyms symbols for input codes (NULL for default ones)
>   * @param num    VLC table number (for static initialization)
>   */
> -static void rv34_gen_vlc(const uint8_t *bits, int size, VLC *vlc, const uint8_t *insyms,
> +static void rv34_gen_vlc(const uint8_t *bits, int size, VLC *vlc, const uint8_t *syms,
>                           const int num)
>  {
> -    int i;
>      int counts[17] = {0}, codes[17];
> -    uint16_t cw[MAX_VLC_SIZE], syms[MAX_VLC_SIZE];
> -    uint8_t bits2[MAX_VLC_SIZE];
> -    int maxbits = 0, realsize = 0;
> -
> -    for(i = 0; i < size; i++){
> -        if(bits[i]){
> -            bits2[realsize] = bits[i];
> -            syms[realsize] = insyms ? insyms[i] : i;
> -            realsize++;
> -            maxbits = FFMAX(maxbits, bits[i]);
> -            counts[bits[i]]++;
> -        }
> -    }
> +    uint16_t cw[MAX_VLC_SIZE];
> +    int maxbits;
>  
> -    codes[0] = 0;
> -    for(i = 0; i < 16; i++)
> +    for (int i = 0; i < size; i++)
> +        counts[bits[i]]++;
> +
> +    /* bits[0] is zero for some tables, i.e. syms actually starts at 1.
> +     * So we reset it here. The code assigned to this element is 0x00. */
> +    codes[0] = counts[0] = 0;
> +    for (int i = 0; i < 16; i++) {
>          codes[i+1] = (codes[i] + counts[i]) << 1;
> -    for(i = 0; i < realsize; i++)
> -        cw[i] = codes[bits2[i]]++;
> +        if (counts[i])
> +            maxbits = i;
> +    }
> +    for (int i = 0; i < size; i++)
> +        cw[i] = codes[bits[i]]++;
>  
>      vlc->table = &table_data[table_offs[num]];
>      vlc->table_allocated = table_offs[num + 1] - table_offs[num];
> -    ff_init_vlc_sparse(vlc, FFMIN(maxbits, 9), realsize,
> -                       bits2, 1, 1,
> +    ff_init_vlc_sparse(vlc, FFMIN(maxbits, 9), size,
> +                       bits, 1, 1,
>                         cw,    2, 2,
> -                       syms,  2, 2, INIT_VLC_USE_NEW_STATIC);
> +                       syms, !!syms, !!syms, INIT_VLC_USE_NEW_STATIC);
>  }
>  
>  /**
> 
Will apply this patchset tomorrow unless there are objections.

- Andreas