[FFmpeg-devel] [PATCH 10/25] avcodec/magicyuv: Fix building Huffman table

[Andreas Rheinhardt]

Paul B Mahol:
> On Sat, Sep 26, 2020 at 12:27:49PM +0200, Andreas Rheinhardt wrote:
>> The MagicYUV format stores Huffman tables in its bitstream by coding
>> the length of a given symbol; it does not code the actual code directly,
>> instead this is to be inferred by the rule that a symbol is to the left
>> of every shorter symbol in the Huffman tree and that for symbols of the
>> same length the symbol is ascending from left to right. With one
>> exception, this is also what our decoder did.
>>
>> The exception only matters when there are codes of length 32, because
>> in this case the first symbol of this length did not get the code 0,
>> but 1; e.g. if there were exactly two nodes of length 32, then they
>> would get assigned the codes 1 and 2 and a node of length 31 will get
>> the 31-bit code 1 which is a prefix of the 32 bit code 2, making the
>> Huffman table invalid. On the other hand, if there were only one symbol
>> with the length 32, the earlier code would accept this un-Huffman-tree.
>>
>> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
>> ---
>>  libavcodec/magicyuv.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> should be ok with subject fixed, it is not fix, its just fixes single
> case that never happens in reality.
> 

I know that this does not affect normal files, but I have trouble
finding an accurate commit message that avoids "fix". So how about "Fix
edge case when building Huffman tables"?

>>
>> diff --git a/libavcodec/magicyuv.c b/libavcodec/magicyuv.c
>> index 1b3f4cfc6b..17dea69d76 100644
>> --- a/libavcodec/magicyuv.c
>> +++ b/libavcodec/magicyuv.c
>> @@ -86,7 +86,7 @@ static int huff_build(HuffEntry he[], VLC *vlc, int nb_elems)
>>  
>>      AV_QSORT(he, nb_elems, HuffEntry, huff_cmp_len);
>>  
>> -    code = 1;
>> +    code = 0;
>>      for (unsigned i = 0; i < nb_elems; i++) {
>>          he[i].code = code >> (32 - he[i].len);
>>          code += 0x80000000u >> (he[i].len - 1);
>> -- 
>> 2.25.1
>>
>> _______________________________________________
>> ffmpeg-devel mailing list
>> ffmpeg-devel at ffmpeg.org
>> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>>
>> To unsubscribe, visit link above, or email
>> ffmpeg-devel-request at ffmpeg.org with subject "unsubscribe".