mbox series

[FFmpeg-devel,000/114] VLC, esp. init_vlc patches

Message ID 20201110104851.321029-1-andreas.rheinhardt@gmail.com
Headers show
Series VLC, esp. init_vlc patches | expand

Message

Andreas Rheinhardt Nov. 10, 2020, 10:46 a.m. UTC 
This patchset provides an alternative to ff_init_vlc_sparse() to
initialize VLCs: ff_init_vlc_from_lengths(). It is based upon the
observation that the codes of a complete VLC can be easily computed
from the lengths if the lengths are ordered according to "left elements
in the tree first". This enables one to initialize trees via lengths and
symbol tables, making the codes redundant. This enables space savings if
a VLC is initialized by codes, (explicit) symbols and lengths or if the
symbols fit in a smaller type than the codes (as is not uncommon). It
also means that one can avoid an implicit qsort that is performed in
ff_init_vlc_sparse() in order to ensure that the codes destined for
the same subtable are contiguous, because the created codes
automatically have this property.

But this of course also restricts its applicability to scenarios where
lengths and symbols are naturally ordered from left to right in the
tree or where it is easy to order them in such a way; the first happens
with several codecs (e.g. Smacker, Theora, TrueMotion 2.0), the latter
includes all static tables as they can be sorted once and for all.

All in all, this saves about 130KB from the binary.

Andreas Rheinhardt (114):
  avcodec/bitstream: Add second function to create VLCs
  avcodec/tscc2: Reduce the size of the tables used to initialize VLCs
  avcodec/tscc2: Combine tables for initializing VLCs
  avcodec/bitstream: Allow static VLC tables to be bigger than needed
  avcodec/tscc2: Make VLC tables static
  avcodec/cllc: Improve creating VLCs
  avcodec/smacker: Improve creating Huffman VLC tables
  avcodec/on2avc: Use smaller tables for VLCs
  avcodec/on2avcdata: Combine tables for codebooks
  avcodec/on2avc: Apply offset when initializing VLC
  avcodec/imc: Make Huffman tables smaller
  avcodec/imc: Avoid offsets table when creating VLCs
  avcodec/clearvideo: Avoid code tables for initializing VLCs
  avcodec/clearvideo: Avoid code duplication when initializing VLCs
  avcodec/clearvideo: Avoid huge VLC length tables
  avcodec/clearvideo: Inline constants
  avcodec/clearvideo: Use minimal max_depth in get_vlc2()
  avcodec/clearvideo: Apply VLC offset during init
  avcodec/clearvideo: Make VLC tables static
  avcodec/wnv1: Make array for initializing VLC smaller
  avcodec/wnv1: Apply offset during init, not later every time
  avcodec/cook: Make tables to initialize VLCs smaller
  avcodec/cook: Apply offset when initializing VLC table
  avcodec/cook: Avoid big length tables for VLC initialization
  avcodec/cook: Inline constants
  avcodec/rv10: Reduce the size of the tables used to initialize VLCs
  avcodec/rv10: Reduce number of exceptions when reading VLC value
  avcodec/rv10: Use symbol table more effectively
  avcodec/rv10: Make VLC tables smaller
  avcodec/rv10: Simplify handling of skip VLC entries
  avcodec/mimic: Reduce size of tables used to initialize VLCs
  avcodec/mimic: Make VLC static
  avcodec/motionpixels: Only create VLC iff it is going to be used
  avcodec/motionpixels: Be more strict when parsing Huffman trees
  avcodec/motionpixels: Don't check for complete VLC
  avcodec/motionpixels: Use symbols table
  avcodec/motionpixels: Simplify creating VLC tables
  avcodec/mpc7: Reduce size of tables used to initialize VLCs
  avcodec/mpc7: Apply offsets when creating VLCs
  avcodec/mpc7: Avoid offsets table when creating VLCs
  avcodec/mpc8: Reduce size of tables used to initialize VLCs
  avcodec/mpc8: Apply offsets when initializing VLCs
  avcodec/mpc8: Reduce the size of the length tables to initialize VLCs
  avcodec/mpc8: Reduce the size of some VLCs
  avcodec/mpc8: Avoid code duplication when initializing VLCs
  avcodec/mobiclip: Avoid redundant codes table to initialize VLCs
  avcodec/mobiclip: Avoid code duplication when initializing VLCs
  avcodec/mobiclip: Reindentation
  avcodec/qdm2: Make tables used to initialize VLCs smaller
  avcodec/qdm2_tablegen: Avoid code duplication when creating VLCs
  avcodec/qdm2: Apply offsets when initializing VLCs
  avcodec/qdm2: Initialize array of VLCs in a loop
  avcodec/qdm2: Avoid offsets table when initializing VLCs
  avcodec/rv40vlc2: Make VLC smaller
  avcodec/rv40: Make the tables used to initialize VLCs smaller
  avcodec/rv40: Make better use of VLC symbols table
  avcodec/rv40: Avoid offset table when initializing static VLCs
  avcodec/rv40: Avoid code duplication when initializing VLCs
  avcodec/mss4: Simplify creating VLC tables
  avcodec/mss4: Don't duplicate standard JPEG tables
  avcodec/mss4: Make VLCs static
  avcodec/sheervideo: Add av_cold to build_vlc()
  avcodec/sheervideo: Simplify creating VLC table
  avcodec/g2meet: Use least max_depth in get_vlc2()
  avcodec/mjpegdec: Simplify creating VLC table
  avcodec/indeo2: Make tables used to initialize VLCs smaller
  avcodec/mpeg4video: Make tables used to initialize VLCs smaller
  avcodec/mpeg4videodec: Make studio VLCs static
  avcodec/truemotion2: Simplify creating VLC table
  avcodec/atrac3plus: Simplify creating VLCs
  avcodec/atrac3plus: Make tables used to initialize VLCs smaller
  avcodec/atrac3plus: Simplify getting offset of VLC in VLC_TYPE buf
  avcodec/atrac3plus: Combine symbols tables
  avcodec/atrac3plus: Combine codebooks into one array
  avcodec/atrac3plus: Run-length encode length tables to make them
    smaller
  avcodec/vc1: Already offset subblock VLC tables during init
  avcodec/vc1: Use symbols table for VLC for Block-level Transform Type
  avcodec/vc1: Use a symbols table to decode interlaced MV vector VLCs
  avcodec/vc1_block, msmpeg4dec: Don't check for errors for complete
    VLCs
  avcodec/vc1_block: Don't use 0 for NULL
  avcodec/vc1: Use symbols table to decode AC coefficients
  avcodec/vc1_block: Use local variables inside macro
  avcodec/vc1: Use symbols table to decode MV differentials
  avcodec/vc1: Use symbols table to parse macroblock mode
  avcodec/vc1: Don't check for errors for complete VLC
  avcodec/vc1: Make tables used to initialize VLCs smaller
  avcodec/vc1: Avoid code duplication when initializing VLCs
  avcodec/rv34: Avoid offsets table for initialization of static VLCs
  avcodec/atrac9dec: Don't confuse max_depth of VLC with max codelength
  avcodec/atrac9dec: Use least max_depth in call to get_vlc2()
  avcodec/atrac9dec: Don't use unnecessarily large VLC tables
  avcodec/atrac9dec: Make tables used to initialize VLCs smaller
  avcodec/atrac9tab: Unify tables used to initialize VLCs
  avcodec/atrac9dec: Don't create VLCs that are never used
  avcodec/atrac9dec: Make VLCs static
  avcodec/atrac9dec: Replace av_free() by av_freep() in close function
  avcodec/atrac9tab: Add missing static to internal table
  avcodec/vp3: Apply VLC offset during init
  avcodec/vp3: Make tables used to initialize VLCs smaller
  avcodec/vp3: Use symbols table for VP3 motion vectors
  avcodec/vp3: Remove code duplication when initializing Theora VLCs
  avcodec/intrax8: Replace always-false check by assert
  avcodec/intrax8: Remove VLC offsets table
  avcodec/intrax8: Avoid code duplication when initializing VLCs
  avcodec/intrax8: Reduce the size of tables used to initialize VLCs
  avcodec/atrac3: Use symbols table
  avcodec/hqx: Inline constants
  avcodec/hqx: Don't check for errors for complete VLCs
  avcodec/utvideodec: Avoid implicit qsort when creating Huffman tables
  avcodec/magicyuv: Optimize creating Huffman tables
  avcodec/qdmc: Don't check for errors for complete VLCs
  avcodec/qdmc: Make tables used to initialize VLCs smaller
  avcodec/qdmc: Apply offset when creating VLC
  avcodec/qdmc: Avoid code duplication when initializing VLC

 configure                    |    2 +-
 libavcodec/atrac3.c          |   18 +-
 libavcodec/atrac3data.h      |  100 +-
 libavcodec/atrac3plus.c      |  159 +-
 libavcodec/atrac3plus_data.h | 1674 +++----
 libavcodec/atrac9dec.c       |   84 +-
 libavcodec/atrac9tab.h       | 2128 ++++-----
 libavcodec/bitstream.c       |  135 +-
 libavcodec/clearvideo.c      |  276 +-
 libavcodec/clearvideodata.h  | 2448 +++-------
 libavcodec/cllc.c            |   14 +-
 libavcodec/cook.c            |   43 +-
 libavcodec/cookdata.h        |  626 +--
 libavcodec/g2meet.c          |    4 +-
 libavcodec/hqx.c             |    6 +-
 libavcodec/hqx.h             |    1 +
 libavcodec/hqxvlc.c          |    2 +-
 libavcodec/imc.c             |   19 +-
 libavcodec/imcdata.h         |   66 +-
 libavcodec/indeo2.c          |    8 +-
 libavcodec/indeo2data.h      |   67 +-
 libavcodec/intrax8.c         |   89 +-
 libavcodec/intrax8huf.h      | 1674 ++++---
 libavcodec/ituh263dec.c      |    2 +-
 libavcodec/magicyuv.c        |   37 +-
 libavcodec/mimic.c           |   67 +-
 libavcodec/mjpegdec.c        |   15 +-
 libavcodec/mobiclip.c        |  241 +-
 libavcodec/motionpixels.c    |   33 +-
 libavcodec/mpc7.c            |   50 +-
 libavcodec/mpc7data.h        |  160 +-
 libavcodec/mpc8.c            |  148 +-
 libavcodec/mpc8huff.h        |  678 +--
 libavcodec/mpeg4data.h       |  150 +-
 libavcodec/mpeg4video.h      |   12 +-
 libavcodec/mpeg4videodec.c   |   92 +-
 libavcodec/msmpeg4dec.c      |    5 -
 libavcodec/mss4.c            |  127 +-
 libavcodec/on2avc.c          |   29 +-
 libavcodec/on2avcdata.c      | 8116 +++++++++-------------------------
 libavcodec/on2avcdata.h      |   10 +-
 libavcodec/qdm2.c            |    2 +-
 libavcodec/qdm2_tablegen.h   |  165 +-
 libavcodec/qdm2data.h        |  248 +-
 libavcodec/qdmc.c            |  143 +-
 libavcodec/rv10.c            |  240 +-
 libavcodec/rv34.c            |   66 +-
 libavcodec/rv40.c            |   85 +-
 libavcodec/rv40vlc2.h        | 1139 +++--
 libavcodec/sheervideo.c      |   15 +-
 libavcodec/smacker.c         |   46 +-
 libavcodec/truemotion2.c     |   24 +-
 libavcodec/tscc2.c           |   77 +-
 libavcodec/tscc2data.h       | 1269 ++----
 libavcodec/utvideodec.c      |   35 +-
 libavcodec/vc1.c             |  377 +-
 libavcodec/vc1_block.c       |  165 +-
 libavcodec/vc1acdata.h       |  174 -
 libavcodec/vc1data.c         | 1851 ++++----
 libavcodec/vc1data.h         |   87 +-
 libavcodec/vlc.h             |   47 +
 libavcodec/vp3.c             |   98 +-
 libavcodec/vp3data.h         | 3147 +++----------
 libavcodec/vp4data.h         | 1536 +++----
 libavcodec/wnv1.c            |   25 +-
 65 files changed, 10324 insertions(+), 20352 deletions(-)