[FFmpeg-devel] [PATCH v2 135/162] avcodec/magicyuv: Optimize creating Huffman tables

[Andreas Rheinhardt]

MagicYUV transmits its Huffman trees by providing the length of the code
corresponding to each symbol; then the decoder has to assemble the table
in such a way that (i) longer codes are to the left of the tree and (ii)
for codes of the same length the symbols are ascending from left to right.

Up until now the decoder did this as follows: It counted the number of
codes of each length and derived the first code of a given length via
(ii). Then the array of lengths is traversed a second time to create
the codes; there is one running counter for each length to do so. This
process creates a default symbol table (that is omitted).

This commit changes this as follows: Everything is indexed by the
position in the tree (with codes to the left first); given (i), we can
calculate the ranges occupied by the codes of each length; and with (ii)
we can derive the actual symbols of each code; the running counters for
each length are now used for the symbols and not for the codes.

Doing so allows us to switch to ff_init_vlc_from_lengths(); this has the
advantage that the codes table needs only be traversed once and that the
codes need not be sorted any more (right now, the codes that are so long
that they will be put into subtables need to be sorted so that codes
that end up in the same subtable are contiguous).

For a sample produced by our encoder (natural content, 4000 frames,
YUV420p, ten iterations, GCC 9.3) this decreased the amount of
decicycles for each call to build_huffman() from 1336049 to 1309401.
Notice that our encoder restricts the code lengths to 12 and our decoder
only uses subtables when the code is longer than 12 bits, so the sorting
that can be avoided does not happen at the moment. If one reduces the
decoder's tables to nine bits, the performance improvement becomes more
apparent: The amount of decicycles for build_huffman() decreased from
1165210 to 654055.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
---
 libavcodec/magicyuv.c | 39 +++++++++++++++++----------------------
 1 file changed, 17 insertions(+), 22 deletions(-)

diff --git a/libavcodec/magicyuv.c b/libavcodec/magicyuv.c
index c7e2754c44..13cb346119 100644
--- a/libavcodec/magicyuv.c
+++ b/libavcodec/magicyuv.c
@@ -47,7 +47,7 @@ typedef enum Prediction {
 
 typedef struct HuffEntry {
     uint8_t  len;
-    uint16_t code;
+    uint16_t sym;
 } HuffEntry;
 
 typedef struct MagicYUVContext {
@@ -72,27 +72,22 @@ typedef struct MagicYUVContext {
     LLVidDSPContext   llviddsp;
 } MagicYUVContext;
 
-static int huff_build(HuffEntry he[], uint16_t codes_count[33],
-                      VLC *vlc, int nb_elems)
+static int huff_build(const uint8_t len[], uint16_t codes_pos[33],
+                      VLC *vlc, int nb_elems, void *logctx)
 {
-    unsigned nb_codes = 0, max = 0;
-
-    for (int i = 32; i > 0; i--) {
-        uint16_t curr = codes_count[i];   // # of leafs of length i
-        codes_count[i] = nb_codes / 2;    // # of non-leaf nodes on level i
-        nb_codes = codes_count[i] + curr; // # of nodes on level i
-        if (curr && !max)
-            max = i;
-    }
+    HuffEntry he[4096];
+
+    for (int i = 31; i > 0; i--)
+        codes_pos[i] += codes_pos[i + 1];
+
+    for (unsigned i = nb_elems; i-- > 0;)
+        he[--codes_pos[len[i]]] = (HuffEntry){ len[i], i };
 
-    for (unsigned i = 0; i < nb_elems; i++) {
-        he[i].code = codes_count[he[i].len];
-        codes_count[he[i].len]++;
-    }
     ff_free_vlc(vlc);
-    return init_vlc(vlc, FFMIN(max, 12), nb_elems,
-                    &he[0].len,  sizeof(he[0]), sizeof(he[0].len),
-                    &he[0].code, sizeof(he[0]), sizeof(he[0].code), 0);
+    return ff_init_vlc_from_lengths(vlc, FFMIN(he[0].len, 12), nb_elems,
+                                    &he[0].len, sizeof(he[0]),
+                                    &he[0].sym, sizeof(he[0]), sizeof(he[0].sym),
+                                    0, 0, logctx);
 }
 
 static void magicyuv_median_pred16(uint16_t *dst, const uint16_t *src1,
@@ -384,7 +379,7 @@ static int build_huffman(AVCodecContext *avctx, const uint8_t *table,
 {
     MagicYUVContext *s = avctx->priv_data;
     GetByteContext gb;
-    HuffEntry he[4096];
+    uint8_t len[4096];
     uint16_t length_count[33] = { 0 };
     int i = 0, j = 0, k;
 
@@ -408,11 +403,11 @@ static int build_huffman(AVCodecContext *avctx, const uint8_t *table,
 
         length_count[x] += l;
         for (; j < k; j++)
-            he[j].len = x;
+            len[j] = x;
 
         if (j == max) {
             j = 0;
-            if (huff_build(he, length_count, &s->vlc[i], max)) {
+            if (huff_build(len, length_count, &s->vlc[i], max, avctx)) {
                 av_log(avctx, AV_LOG_ERROR, "Cannot build Huffman codes\n");
                 return AVERROR_INVALIDDATA;
             }
-- 
2.25.1