diff mbox series

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

Message ID 20201008191842.385813-3-andreas.rheinhardt@gmail.com
State Accepted
Headers show
Series [FFmpeg-devel,1/4] avcodec/mjpegdec: Remove use_static from build_vlc() | expand

Checks

Context Check Description
andriy/default pending
andriy/make success Make finished
andriy/make_fate success Make fate finished

Commit Message

Andreas Rheinhardt Oct. 8, 2020, 7:18 p.m. UTC 
Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
---
 libavcodec/magicyuvenc.c | 41 ++++++++++++++--------------------------
 1 file changed, 14 insertions(+), 27 deletions(-)

Comments

Paul B Mahol Oct. 8, 2020, 8:02 p.m. UTC | #1 
On Thu, Oct 08, 2020 at 09:18:41PM +0200, Andreas Rheinhardt wrote:
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> ---
>  libavcodec/magicyuvenc.c | 41 ++++++++++++++--------------------------
>  1 file changed, 14 insertions(+), 27 deletions(-)
> 

should be ok if encoding still works
diff mbox series

Patch

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);