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

[Andreas Rheinhardt]

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 at 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