diff mbox series

[FFmpeg-devel,14/14] avcodec/huffyuv: Speed up generating Huffman codes

Message ID GV1P250MB0737FB4229D22DFA811D61BF8F589@GV1P250MB0737.EURP250.PROD.OUTLOOK.COM
State Accepted
Commit cad1593330e9d1990fa092bc7cd2fa4324d6ccf9
Headers show
Series [FFmpeg-devel,01/14] avcodec/ylc: Remove inclusion of huffyuvdsp.h | expand

Checks

Context Check Description
andriy/make_x86 success Make finished
andriy/make_fate_x86 success Make fate finished

Commit Message

Andreas Rheinhardt Oct. 2, 2022, 12:10 a.m. UTC 
The codes here have the property that the long codes
are to the left of the tree (each zero bit child node
is by definition to the left of its one bit sibling);
they also have the property that among codes of the same length,
the symbol is ascending from left to right.

These properties can be used to create the codes from
the lengths in only two passes over the array of lengths
(the current code uses one pass for each length, i.e. 32):
First one counts how many nodes of each length there are.
Then one calculates the range of codes of each length
(possible because the codes are ordered by length in the tree).
This enables one to calculate the actual codes with only
one further traversal of the length array.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
---
Given that the long codes are to the left of the tree,
one can actually use uint16_t here despite the codes
being up to 32 bits long (so many leading digits have to be zero
that the codes fit into uint16_t).

 libavcodec/huffyuv.c | 22 +++++++++++++---------
 1 file changed, 13 insertions(+), 9 deletions(-)
diff mbox series

Patch

diff --git a/libavcodec/huffyuv.c b/libavcodec/huffyuv.c
index bbe4b952b0..6bcaacfc37 100644
--- a/libavcodec/huffyuv.c
+++ b/libavcodec/huffyuv.c
@@ -39,19 +39,23 @@ 
 
 int ff_huffyuv_generate_bits_table(uint32_t *dst, const uint8_t *len_table, int n)
 {
-    int len, index;
-    uint32_t bits = 0;
+    int lens[33] = { 0 };
+    uint32_t codes[33];
 
-    for (len = 32; len > 0; len--) {
-        for (index = 0; index < n; index++) {
-            if (len_table[index] == len)
-                dst[index] = bits++;
-        }
-        if (bits & 1) {
+    for (int i = 0; i < n; i++)
+        lens[len_table[i]]++;
+
+    codes[32] = 0;
+    for (int i = FF_ARRAY_ELEMS(lens) - 1; i > 0; i--) {
+        if ((lens[i] + codes[i]) & 1) {
             av_log(NULL, AV_LOG_ERROR, "Error generating huffman table\n");
             return -1;
         }
-        bits >>= 1;
+        codes[i - 1] = (lens[i] + codes[i]) >> 1;
+    }
+    for (int i = 0; i < n; i++) {
+        if (len_table[i])
+            dst[i] = codes[len_table[i]]++;
     }
     return 0;
 }