[FFmpeg-cvslog] avcodec/magicyuv: Don't invert Huffman table symbols twice

[Andreas Rheinhardt]

ffmpeg | branch: master | Andreas Rheinhardt <andreas.rheinhardt at gmail.com> | Mon Aug 31 20:30:34 2020 +0200| [7332a23b848555780f3d24370c8314dd9f348a35] | committer: Andreas Rheinhardt

avcodec/magicyuv: Don't invert Huffman table symbols twice

When the MagicYUV decoder builds Huffman tables from an array of code
lengths, it proceeds as follows: First it copies the entries of the
array of lengths into an array of HuffEntries (a struct which contains
a length and a symbol field); it also sets the symbol field in
descending order from nb_elem - 1 to 0, where nb_elem is the common number
of elements of the length and HuffEntry arrays. Then the HuffEntry array
is sorted lexicographically: a > b iff a.len > b.len or a.len == b.len and
a.sym > b.sym. Afterwards the symbols of the so sorted array are
inverted again (i.e. each symbol sym is replaced by nb_elem - sym).

Yet inverting can easily be avoided altogether: Just modify the order so
that smaller symbols correspond to bigger HuffEntries. This leads to the
same permutation as the current code does and given that the two
inversions just cancel each other out, the result is the same.

Reviewed-by: Paul B Mahol <onemda at gmail.com>
Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>

> http://git.videolan.org/gitweb.cgi/ffmpeg.git/?a=commit;h=7332a23b848555780f3d24370c8314dd9f348a35
---

 libavcodec/magicyuv.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/libavcodec/magicyuv.c b/libavcodec/magicyuv.c
index a255f82d9c..32d744add2 100644
--- a/libavcodec/magicyuv.c
+++ b/libavcodec/magicyuv.c
@@ -79,19 +79,19 @@ typedef struct MagicYUVContext {
 static int huff_cmp_len(const void *a, const void *b)
 {
     const HuffEntry *aa = a, *bb = b;
-    return (aa->len - bb->len) * 256 + aa->sym - bb->sym;
+    return (aa->len - bb->len) * 256 + bb->sym - aa->sym;
 }
 
 static int huff_cmp_len10(const void *a, const void *b)
 {
     const HuffEntry *aa = a, *bb = b;
-    return (aa->len - bb->len) * 1024 + aa->sym - bb->sym;
+    return (aa->len - bb->len) * 1024 + bb->sym - aa->sym;
 }
 
 static int huff_cmp_len12(const void *a, const void *b)
 {
     const HuffEntry *aa = a, *bb = b;
-    return (aa->len - bb->len) * 4096 + aa->sym - bb->sym;
+    return (aa->len - bb->len) * 4096 + bb->sym - aa->sym;
 }
 
 static int huff_build10(VLC *vlc, uint8_t *len)
@@ -104,7 +104,7 @@ static int huff_build10(VLC *vlc, uint8_t *len)
     int i;
 
     for (i = 0; i < 1024; i++) {
-        he[i].sym = 1023 - i;
+        he[i].sym = i;
         he[i].len = len[i];
         if (len[i] == 0 || len[i] > 32)
             return AVERROR_INVALIDDATA;
@@ -115,7 +115,7 @@ static int huff_build10(VLC *vlc, uint8_t *len)
     for (i = 1023; i >= 0; i--) {
         codes[i] = code >> (32 - he[i].len);
         bits[i]  = he[i].len;
-        syms[i]  = 1023 - he[i].sym;
+        syms[i]  = he[i].sym;
         code += 0x80000000u >> (he[i].len - 1);
     }
 
@@ -136,7 +136,7 @@ static int huff_build12(VLC *vlc, uint8_t *len)
     int i;
 
     for (i = 0; i < 4096; i++) {
-        he[i].sym = 4095 - i;
+        he[i].sym = i;
         he[i].len = len[i];
         if (len[i] == 0 || len[i] > 32)
             return AVERROR_INVALIDDATA;
@@ -147,7 +147,7 @@ static int huff_build12(VLC *vlc, uint8_t *len)
     for (i = 4095; i >= 0; i--) {
         codes[i] = code >> (32 - he[i].len);
         bits[i]  = he[i].len;
-        syms[i]  = 4095 - he[i].sym;
+        syms[i]  = he[i].sym;
         code += 0x80000000u >> (he[i].len - 1);
     }
 
@@ -168,7 +168,7 @@ static int huff_build(VLC *vlc, uint8_t *len)
     int i;
 
     for (i = 0; i < 256; i++) {
-        he[i].sym = 255 - i;
+        he[i].sym = i;
         he[i].len = len[i];
         if (len[i] == 0 || len[i] > 32)
             return AVERROR_INVALIDDATA;
@@ -179,7 +179,7 @@ static int huff_build(VLC *vlc, uint8_t *len)
     for (i = 255; i >= 0; i--) {
         codes[i] = code >> (32 - he[i].len);
         bits[i]  = he[i].len;
-        syms[i]  = 255 - he[i].sym;
+        syms[i]  = he[i].sym;
         code += 0x80000000u >> (he[i].len - 1);
     }