[FFmpeg-devel] [PATCH 01/23] avcodec/x86/vvc/dsp_init: Make put wrappers static

[Andreas Rheinhardt]

Michael Niedermayer:
> On Sat, Apr 05, 2025 at 09:38:10AM +0200, Michael Niedermayer wrote:
>> On Thu, Apr 03, 2025 at 10:31:26PM +0200, Andreas Rheinhardt wrote:
>>> Patches attached.
>>>
>>> - Andreas
>>
>> [...]
>>
>>>  libavcodec/mjpegenc_huffman.c                    |   33 ++++++------------
>>>  libavcodec/tests/mjpegenc_huffman.c              |    6 ++-
>>>  tests/ref/fate/jpg-icc                           |    6 +--
>>>  tests/ref/lavf/jpg                               |    4 +-
>>>  tests/ref/lavf/smjpeg                            |    4 +-
>>>  tests/ref/seek/vsynth_lena-mjpeg                 |   40 +++++++++++------------
>>>  tests/ref/vsynth/vsynth1-mjpeg                   |    4 +-
>>>  tests/ref/vsynth/vsynth1-mjpeg-422               |    4 +-
>>>  tests/ref/vsynth/vsynth1-mjpeg-444               |    4 +-
>>>  tests/ref/vsynth/vsynth1-mjpeg-huffman           |    4 +-
>>>  tests/ref/vsynth/vsynth1-mjpeg-trell             |    4 +-
>>>  tests/ref/vsynth/vsynth1-mjpeg-trell-huffman     |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg                   |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg-422               |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg-444               |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg-huffman           |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg-trell             |    4 +-
>>>  tests/ref/vsynth/vsynth2-mjpeg-trell-huffman     |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg                   |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg-422               |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg-444               |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg-huffman           |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg-trell             |    4 +-
>>>  tests/ref/vsynth/vsynth3-mjpeg-trell-huffman     |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg               |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg-422           |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg-444           |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg-huffman       |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg-trell         |    4 +-
>>>  tests/ref/vsynth/vsynth_lena-mjpeg-trell-huffman |    4 +-
>>>  30 files changed, 91 insertions(+), 98 deletions(-)
>>> 515cd8ef4364423e2e7ec04535f04b0580e97c78  0020-avcodec-mjpegenc_huffman-Avoid-AV_QSORT-to-sort-entr.patch
>>> From a17db6215a1600021c9d4a7d6c7923ac5816ea70 Mon Sep 17 00:00:00 2001
>>> From: Andreas Rheinhardt <andreas.rheinhardt at outlook.com>
>>> Date: Wed, 2 Apr 2025 15:06:43 +0200
>>> Subject: [PATCH 20/23] avcodec/mjpegenc_huffman: Avoid AV_QSORT to sort
>>>  entries by length
>>>
>>> It is unnecessary; all one needs to ensure that shorter codes
>>> precede longer ones is to get the number of codes for each
>>> length. Then the codes of length 1 occupy the first count[1]
>>> positions, the codes of length 2 the next count[2]...
>>> Doing so gives a 3.4% speedup of ff_mjpeg_encode_huffman_close()
>>> here; it also saves about 340B.
>>>
>>> The new code sorts codes of the same length in order of
>>> ascending symbol. The old code did not and therefore
>>> the FATE checksums needed to be updated. Due to MJPEG's
>>> 0xFF unescaping file sizes as well as file checksums
>>> needed to be updated; the decoded picture hashes stayed
>>> the same.
>>
>> so theres a difference in size because of escaping differences
>> that implies the previous table was not optimal (by the definition
>> of smallest filesize)
>>
>> have you considered to use this effect to reduce escaping overhead
>> further and thus improve compression further ?
>>
>> for example one can build a variable length code that has no "all 1" code with
>> very little overhead. One also could maybe avoid codes that have
>> long runs of 1 over some threshold
>>
>> The patch as is, is fine of course. Thats just an idea to improve
>> compression by another 0.1-0.3% or so
> 
> or another way to see this, is that a huffman table assumes the cost
> of each code of the same length is equal.
> But due to the escaping thats not true, a code starting and ending in 0 and
> not having 8 1 bits in  it is less costly than a code that is
> more likely to create patterns that need escaping
> 
> the maximum compression gain from this is small, but it may be
> an interresting problem. Within the bitstream syntax and adding
> no cost on the decoder
> 

I implemented this (with the exception of the 0xFF in the middle of a
code) and surprisingly it turned out not so beneficial. See
https://ffmpeg.org/pipermail/ffmpeg-devel/2025-April/342212.html

- Andreas