| Message ID | 20200831210930.18900-1-andreas.rheinhardt@gmail.com |
|---|---|
| State | Accepted |
| Commit | 7332a23b848555780f3d24370c8314dd9f348a35 |
| Headers | show |
| Series | [FFmpeg-devel,1/8] avcodec/magicyuv: Don't invert Huffman table symbols twice | expand |
| Context | Check | Description |
|---|---|---|
| andriy/default | pending | |
| andriy/make | success | Make finished |
| andriy/make_fate | success | Make fate finished |
On 8/31/20, Andreas Rheinhardt <andreas.rheinhardt@gmail.com> wrote: > 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. > > Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com> > --- > libavcodec/magicyuv.c | 18 +++++++++--------- > 1 file changed, 9 insertions(+), 9 deletions(-) > LGTM whole patch set.
Paul B Mahol: > On 8/31/20, Andreas Rheinhardt <andreas.rheinhardt@gmail.com> wrote: >> 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. >> >> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com> >> --- >> libavcodec/magicyuv.c | 18 +++++++++--------- >> 1 file changed, 9 insertions(+), 9 deletions(-) >> > > LGTM whole patch set. > Applied. Thanks for testing and reviewing. - Andreas
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); }
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. Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com> --- libavcodec/magicyuv.c | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-)