[FFmpeg-devel] [PATCH] Implement optimal huffman encoding for (M)JPEG.
Clément Bœsch
u at pkh.me
Wed Dec 28 11:12:44 EET 2016
On Wed, Dec 28, 2016 at 01:22:14AM -0500, Jerry Jiang wrote:
> Changelog | 1 +
> doc/encoders.texi | 21 +++
> libavcodec/Makefile | 8 +-
> libavcodec/mjpegenc.c | 265 +++++++++++++++++++--------
> libavcodec/mjpegenc.h | 68 ++++++-
> libavcodec/mjpegenc_common.c | 161 ++++++++++++++--
> libavcodec/mjpegenc_common.h | 2 +
> libavcodec/mjpegenc_huffman.c | 190 +++++++++++++++++++
> libavcodec/mjpegenc_huffman.h | 71 +++++++
> libavcodec/mpegvideo.h | 1 +
> libavcodec/mpegvideo_enc.c | 5 +-
> libavcodec/tests/.gitignore | 1 +
> libavcodec/tests/mjpegenc_huffman.c | 144 +++++++++++++++
> tests/fate/libavcodec.mak | 6 +
> tests/fate/vcodec.mak | 4 +-
> tests/ref/vsynth/vsynth1-mjpeg-huffman | 4 +
> tests/ref/vsynth/vsynth1-mjpeg-trell-huffman | 4 +
> tests/ref/vsynth/vsynth2-mjpeg-huffman | 4 +
> tests/ref/vsynth/vsynth2-mjpeg-trell-huffman | 4 +
> tests/ref/vsynth/vsynth3-mjpeg-huffman | 4 +
> tests/ref/vsynth/vsynth3-mjpeg-trell-huffman | 4 +
> 21 files changed, 865 insertions(+), 107 deletions(-)
> create mode 100644 libavcodec/mjpegenc_huffman.c
> create mode 100644 libavcodec/mjpegenc_huffman.h
> create mode 100644 libavcodec/tests/mjpegenc_huffman.c
> create mode 100644 tests/ref/vsynth/vsynth1-mjpeg-huffman
> create mode 100644 tests/ref/vsynth/vsynth1-mjpeg-trell-huffman
> create mode 100644 tests/ref/vsynth/vsynth2-mjpeg-huffman
> create mode 100644 tests/ref/vsynth/vsynth2-mjpeg-trell-huffman
> create mode 100644 tests/ref/vsynth/vsynth3-mjpeg-huffman
> create mode 100644 tests/ref/vsynth/vsynth3-mjpeg-trell-huffman
>
some general style/cosmetics issues i saw several times:
- missing \n before opening brace in functions
- use of ++var instead of var++. this is not a c++ project.
- use of sizeof(x)/sizeof(*x) instead of FF_ARRAY_ELEMS
- a few "MJpegBuffer* x" instead of "MJpegBuffer *x"
- missing vertical align with the "(" in various places such prototypes or
your fprintf calls
[...]
> +/**
> + * Enum for the Huffman encoding strategy.
> + */
> +enum HuffmanTableOption {
> + HUFFMAN_TABLE_DEFAULT = 0, ///< Use the default Huffman tables.
> + HUFFMAN_TABLE_OPTIMAL = 1 ///< Compute and use optimal Huffman tables.
add a NB_HUFFMAN_TABLE_OPTION or something at the end, which you can use
in the options to define the range from 0 to NB-1
btw, wrong indent.
[...]
> +/**
> + * Comparison function for two PTables by prob
> + *
> + * @param a First PTable to compare
> + * @param b Second PTable to compare
> + * @return -1 for less than, 0 for equals, 1 for greater than
> + */
> +static int compare_by_prob(const void *a, const void *b) {
> + PTable a_val = *(PTable *) a;
> + PTable b_val = *(PTable *) b;
> + return FFDIFFSIGN(a_val.prob, b_val.prob);
> +}
> +
> +/**
> + * Comparison function for two HuffTables by length
> + *
> + * @param a First HuffTable to compare
> + * @param b Second HuffTable to compare
> + * @return -1 for less than, 0 for equals, 1 for greater than
> + */
> +static int compare_by_length(const void *a, const void *b) {
> + HuffTable a_val = *(HuffTable *) a;
> + HuffTable b_val = *(HuffTable *) b;
> + return FFDIFFSIGN(a_val.length, b_val.length);
> +}
> +
Wouldn't AV_QSORT() work just the same if you did return a-b?
[...]
> + * All probabilities should be positive integers. The output is sorted by code,
> + * not by length.
> + *
> + * @param prob_table input array of a PTable for each distinct input value
> + * @param distincts output array of a HuffTable that will be populated by this function
> + * @param size size of the prob_table array
> + * @param maxLength max length of an encoding
no camel case in variable names please
[...]
> +// Test the example given on @see <a
> +// href="http://guru.multimedia.cx/small-tasks-for-ffmpeg/">Small Tasks</a>
not a fan of that html; would you mind just keeping the url? "@see http://..."
> +int main(int argc, char **argv) {
> + int i, ret = 0;
> + // Probabilities of symbols 0..4
> + PTable val_counts[] = {
> + {.value = 0, .prob = 1},
> + {.value = 1, .prob = 2},
> + {.value = 2, .prob = 5},
> + {.value = 3, .prob = 10},
> + {.value = 4, .prob = 21},
> + };
> + // Expected code lengths for each symbol
> + HuffTable expected[] = {
> + {.code = 0, .length = 3},
> + {.code = 1, .length = 3},
> + {.code = 2, .length = 3},
> + {.code = 3, .length = 3},
> + {.code = 4, .length = 1},
> + };
static const HuffTable?
> + // Actual code lengths
> + HuffTable distincts[5];
> +
> + // Build optimal huffman tree
> + ff_mjpegenc_huffman_compute_bits(val_counts, distincts, 5, 3);
> +
> + for (i = 0; i < 5; i++) {
i < FF_ARRAY_ELEMS(distincts)
> + if (distincts[i].code != expected[i].code ||
> + distincts[i].length != expected[i].length) {
> + fprintf(stderr,
> + "Built huffman does not equal expectations. "
> + "Expected: code %d probability %d, "
> + "Actual: code %d probability %d\n",
> + expected[i].code, expected[i].length,
> + distincts[i].code, distincts[i].length);
> + ret = 1;
> + }
> + }
> +
> + {
> + // Check handling of zero probabilities
> + int probs[] = {6, 6, 0, 0, 0};
static const int
> + if (check_lengths(16, 18, probs, sizeof(probs) / sizeof(probs[0]))) {
> + ret = 1;
> + }
> + }
> + {
> + // Check skewed distribution over 256 without saturated lengths
> + int probs[] = {2, 0, 0, 0, 0, 1, 0, 0, 20, 0, 2, 0, 10, 5, 1, 1, 9, 1, 1, 6, 0, 5, 0, 1, 0, 7, 6, 1, 1, 5, 0, 0, 0, 0, 11, 0, 0, 0, 51, 1, 0, 20, 0, 1, 0, 0, 0, 0, 6, 106, 1, 0, 1, 0, 2, 1, 16, 0, 0, 5, 0, 0, 0, 4, 3, 15, 4, 4, 0, 0, 0, 3, 0, 0, 1, 0, 3, 0, 3, 2, 2, 0, 0, 4, 3, 40, 1, 2, 0, 22, 0, 0, 0, 9, 0, 0, 0, 0, 1, 1, 0, 1, 6, 11, 4, 10, 28, 6, 1, 0, 0, 9, 9, 4, 0, 0, 0, 0, 8, 33844, 2, 0, 2, 1, 1, 5, 0, 0, 1, 9, 1, 0, 4, 14, 4, 0, 0, 3, 8, 0, 51, 9, 6, 1, 1, 2, 2, 3, 1, 5, 5, 29, 0, 0, 0, 0, 14, 29, 6, 4, 13, 12, 2, 3, 1, 0, 5, 4, 1, 1, 0, 0, 29, 1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 1, 7, 0, 42, 0, 0, 0, 0, 0, 2, 0, 3, 9, 0, 0, 0, 2, 1, 0, 0, 6, 5, 6, 1, 2, 3, 0, 0, 0, 3, 0, 0, 28, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 23, 0, 0, 0, 0, 0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5};
- ditto static const.
- also add some line breaks please.
- you could declare it outside the function (or at the top) with all the
other probs to remove a bunch of random opened scopes. The binary
section of the table should be the exact same in all the cases if it's
declared as static const.
> + if (check_lengths(16, 41282, probs, sizeof(probs) / sizeof(probs[0]))) {
> + ret = 1;
wrong indent.
btw, you can drop the { } for single statements if you feel like it
[...]
--
Clément B.
More information about the ffmpeg-devel
mailing list