[FFmpeg-devel] [PATCH 3/4] avcodec/magicyuvenc: Avoid sorting Huffman table unnecessarily

[Andreas Rheinhardt]

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
---
 libavcodec/magicyuvenc.c | 41 ++++++++++++++--------------------------
 1 file changed, 14 insertions(+), 27 deletions(-)

diff --git a/libavcodec/magicyuvenc.c b/libavcodec/magicyuvenc.c
index 0bd6b8ef6a..1b8bb53114 100644
--- a/libavcodec/magicyuvenc.c
+++ b/libavcodec/magicyuvenc.c
@@ -40,7 +40,6 @@ typedef enum Prediction {
 } Prediction;
 
 typedef struct HuffEntry {
-    uint8_t  sym;
     uint8_t  len;
     uint32_t code;
 } HuffEntry;
@@ -245,32 +244,18 @@ static av_cold int magy_encode_init(AVCodecContext *avctx)
     return 0;
 }
 
-static int magy_huff_cmp_len(const void *a, const void *b)
+static void calculate_codes(HuffEntry *he, uint16_t codes_count[33])
 {
-    const HuffEntry *aa = a, *bb = b;
-    return (aa->len - bb->len) * 256 + aa->sym - bb->sym;
-}
-
-static int huff_cmp_sym(const void *a, const void *b)
-{
-    const HuffEntry *aa = a, *bb = b;
-    return bb->sym - aa->sym;
-}
-
-static void calculate_codes(HuffEntry *he)
-{
-    uint32_t code;
-    int i;
-
-    AV_QSORT(he, 256, HuffEntry, magy_huff_cmp_len);
-
-    code = 1;
-    for (i = 255; i >= 0; i--) {
-        he[i].code  = code >> (32 - he[i].len);
-        code       += 0x80000000u >> (he[i].len - 1);
+    for (unsigned i = 32, nb_codes = 0; 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
     }
 
-    AV_QSORT(he, 256, HuffEntry, huff_cmp_sym);
+    for (unsigned i = 0; i < 255; i++) {
+        he[i].code = codes_count[he[i].len];
+        codes_count[he[i].len]++;
+    }
 }
 
 static void count_usage(uint8_t *src, int width,
@@ -301,6 +286,7 @@ static int compare_by_prob(const void *a, const void *b)
 }
 
 static void magy_huffman_compute_bits(PTable *prob_table, HuffEntry *distincts,
+                                      uint16_t codes_counts[33],
                                       int size, int max_length)
 {
     PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
@@ -356,8 +342,8 @@ static void magy_huffman_compute_bits(PTable *prob_table, HuffEntry *distincts,
     }
 
     for (i = 0; i < size; i++) {
-        distincts[i].sym = i;
         distincts[i].len = nbits[i];
+        codes_counts[nbits[i]]++;
     }
 }
 
@@ -366,6 +352,7 @@ static int encode_table(AVCodecContext *avctx, uint8_t *dst,
                         PutBitContext *pb, HuffEntry *he)
 {
     PTable counts[256] = { {0} };
+    uint16_t codes_counts[33] = { 0 };
     int i;
 
     count_usage(dst, width, height, counts);
@@ -375,9 +362,9 @@ static int encode_table(AVCodecContext *avctx, uint8_t *dst,
         counts[i].value = 255 - i;
     }
 
-    magy_huffman_compute_bits(counts, he, 256, 12);
+    magy_huffman_compute_bits(counts, he, codes_counts, 256, 12);
 
-    calculate_codes(he);
+    calculate_codes(he, codes_counts);
 
     for (i = 0; i < 256; i++) {
         put_bits(pb, 1, 0);
-- 
2.25.1