Images 💾⌗

Last commit ⭐⌗ 

commit 5ff69579a4e4b3edab91ef65d7d37baa64ea97a5
Author:     Nico Weber <thakis@chromium.org>
AuthorDate: Sun Jun 30 14:15:07 2024 +0200
Commit:     Nico Weber <thakis@chromium.org>
CommitDate: Mon Jul 1 00:29:39 2024 +0200

    LibGfx/WebPWriter: Implement run-length encoding
    
    This implements the start of lossless webp's compression scheme,
    which is almost, but not quite, entirely unlike deflate.
    
    The green channel is now green-or-length, and has up to 280
    entries, instead of up to 256 before. We now use the 40-entry
    distance code (even though it only ever stores 1s now).
    
    Due to this, a few places change to taking spans instead of
    Array<256>s.
    
    The spec only has the transform from prefix or distance code
    to value. The inverse prefix_decompose() in this patch is
    my own invention. I checked with a python script that it's
    a true inverse (see PR for the script).
    
    We now look for back-references with a distance of 1, which is
    equivalent to run-length encoding. It's fairly fast to compute,
    but leaves compression on the table. Full window-based
    back references will be in a future PR.
    
    We also still don't do color cache entries yet, but that should
    be fairly straightforward to add. (It will make the green channel
    larger than 280 entries.)
    
    We still use a single global huffman table for the entire image.
    Doing one per tile should be doable with the organization we now
    have, and might also be in a future PR.
    
    File sizes, and perf numbers on HEAD before this patch series (see
    previous commit for perf comparison to previous commit):
    
        sunset-retro.png (876K):
            1.7M -> 1.6M,
            25.3 ms ± 0.5 ms -> 27.5 ms ± 0.8 ms
    
    (helps little; from 1.94x as input to 1.83x as large.
    About 5% smaller, for about a 10% slowdown.)
    
        wow.gif (nee giphy.gif) (184k):
            3.9M -> 1.4M
            105.7 ms ± 1.7 ms -> 74.0 ms ± 1.1 ms
    
    (from 21.2x as big as the gif input to 7.6x as big.
    About 64% smaller, for a 28% speed _up_.)
    
        7z7c.gif (11K):
            40K -> 8.4K
            13.9 ms ± 0.6 ms -> 12.9 ms ± 0.5 ms
    
    (from 3.6x as big as the gif input to 0.76x as big :^)
    About 79% smaller, for a 7% speed _up_.)