diff mbox series

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

Message ID 20201022102006.571413-1-andreas.rheinhardt@gmail.com
State Accepted
Commit f033e6d2e635820ec3deb9b936ed3f27ac7ad0a7
Headers show
Series [FFmpeg-devel,1/2] avcodec/rv34: Don't needlessly copy VLC length and symbol arrays
Related show

Checks

Context Check Description
andriy/x86_make success Make finished
andriy/x86_make_fate success Make fate finished

Commit Message

Andreas Rheinhardt Oct. 22, 2020, 10:20 a.m. UTC
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(-)

Comments

Andreas Rheinhardt Oct. 25, 2020, 9:30 a.m. UTC | #1
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
diff mbox series

Patch

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);
 }
 
 /**