From 884506dfe2e29a5b2bd2905ca4f17e277e32acb1 Mon Sep 17 00:00:00 2001 From: Jerry Jiang Date: Wed, 1 Feb 2017 23:23:04 -0800 Subject: Implement optimal huffman encoding for (M)JPEG. > seems to break > make fate-vsynth1-mjpeg-444 Fixed. --- libavcodec/Makefile | 8 +- libavcodec/mjpegenc.c | 243 ++++++++++++++++++++++++++---------- libavcodec/mjpegenc.h | 68 ++++++++-- libavcodec/mjpegenc_common.c | 166 ++++++++++++++++++++++-- libavcodec/mjpegenc_common.h | 2 + libavcodec/mjpegenc_huffman.c | 195 +++++++++++++++++++++++++++++ libavcodec/mjpegenc_huffman.h | 74 +++++++++++ libavcodec/mpegvideo.h | 1 + libavcodec/mpegvideo_enc.c | 17 ++- libavcodec/tests/.gitignore | 1 + libavcodec/tests/mjpegenc_huffman.c | 163 ++++++++++++++++++++++++ 11 files changed, 847 insertions(+), 91 deletions(-) create mode 100644 libavcodec/mjpegenc_huffman.c create mode 100644 libavcodec/mjpegenc_huffman.h create mode 100644 libavcodec/tests/mjpegenc_huffman.c (limited to 'libavcodec') diff --git a/libavcodec/Makefile b/libavcodec/Makefile index 43a6add317..4765e9c96c 100644 --- a/libavcodec/Makefile +++ b/libavcodec/Makefile @@ -39,6 +39,7 @@ OBJS = allcodecs.o \ mediacodec.o \ mpeg12framerate.o \ options.o \ + mjpegenc_huffman.o \ parser.o \ profiles.o \ qsv_api.o \ @@ -175,7 +176,8 @@ OBJS-$(CONFIG_AMRWB_DECODER) += amrwbdec.o celp_filters.o \ celp_math.o acelp_filters.o \ acelp_vectors.o \ acelp_pitch_delay.o -OBJS-$(CONFIG_AMV_ENCODER) += mjpegenc.o mjpegenc_common.o +OBJS-$(CONFIG_AMV_ENCODER) += mjpegenc.o mjpegenc_common.o \ + mjpegenc_huffman.o OBJS-$(CONFIG_ANM_DECODER) += anm.o OBJS-$(CONFIG_ANSI_DECODER) += ansi.o cga_data.o OBJS-$(CONFIG_APE_DECODER) += apedec.o @@ -377,7 +379,8 @@ OBJS-$(CONFIG_METASOUND_DECODER) += metasound.o metasound_data.o \ OBJS-$(CONFIG_MICRODVD_DECODER) += microdvddec.o ass.o OBJS-$(CONFIG_MIMIC_DECODER) += mimic.o OBJS-$(CONFIG_MJPEG_DECODER) += mjpegdec.o -OBJS-$(CONFIG_MJPEG_ENCODER) += mjpegenc.o mjpegenc_common.o +OBJS-$(CONFIG_MJPEG_ENCODER) += mjpegenc.o mjpegenc_common.o \ + mjpegenc_huffman.o OBJS-$(CONFIG_MJPEGB_DECODER) += mjpegbdec.o OBJS-$(CONFIG_MJPEG_VAAPI_ENCODER) += vaapi_encode_mjpeg.o OBJS-$(CONFIG_MLP_DECODER) += mlpdec.o mlpdsp.o @@ -1014,6 +1017,7 @@ TESTPROGS = avpacket \ jpeg2000dwt \ mathops \ options \ + mjpegenc_huffman \ utils \ TESTPROGS-$(CONFIG_CABAC) += cabac diff --git a/libavcodec/mjpegenc.c b/libavcodec/mjpegenc.c index 3d113770df..a4899c5d6e 100644 --- a/libavcodec/mjpegenc.c +++ b/libavcodec/mjpegenc.c @@ -39,39 +39,15 @@ #include "mjpeg.h" #include "mjpegenc.h" -static uint8_t uni_ac_vlc_len[64 * 64 * 2]; -static uint8_t uni_chroma_ac_vlc_len[64 * 64 * 2]; - -static av_cold void init_uni_ac_vlc(const uint8_t huff_size_ac[256], uint8_t *uni_ac_vlc_len) -{ - int i; - - for (i = 0; i < 128; i++) { - int level = i - 64; - int run; - if (!level) - continue; - for (run = 0; run < 64; run++) { - int len, code, nbits; - int alevel = FFABS(level); - - len = (run >> 4) * huff_size_ac[0xf0]; - - nbits= av_log2_16bit(alevel) + 1; - code = ((15&run) << 4) | nbits; - - len += huff_size_ac[code] + nbits; - - uni_ac_vlc_len[UNI_AC_ENC_INDEX(run, i)] = len; - // We ignore EOB as its just a constant which does not change generally - } - } -} +// Don't know, but let's guess 16 bits per code +#define MJPEG_HUFFMAN_EST_BITS_PER_CODE 16 av_cold int ff_mjpeg_encode_init(MpegEncContext *s) { MJpegContext *m; + av_assert0(s->slice_context_count == 1); + if (s->width > 65500 || s->height > 65500) { av_log(s, AV_LOG_ERROR, "JPEG does not support resolutions above 65500x65500\n"); return AVERROR(EINVAL); @@ -84,7 +60,9 @@ av_cold int ff_mjpeg_encode_init(MpegEncContext *s) s->min_qcoeff=-1023; s->max_qcoeff= 1023; - /* build all the huffman tables */ + // Build default Huffman tables. + // These may be overwritten later with more optimal Huffman tables, but + // they are needed at least right now for some processes like trellis. ff_mjpeg_build_huffman_codes(m->huff_size_dc_luminance, m->huff_code_dc_luminance, avpriv_mjpeg_bits_dc_luminance, @@ -102,12 +80,18 @@ av_cold int ff_mjpeg_encode_init(MpegEncContext *s) avpriv_mjpeg_bits_ac_chrominance, avpriv_mjpeg_val_ac_chrominance); - init_uni_ac_vlc(m->huff_size_ac_luminance, uni_ac_vlc_len); - init_uni_ac_vlc(m->huff_size_ac_chrominance, uni_chroma_ac_vlc_len); + init_uni_ac_vlc(m->huff_size_ac_luminance, m->uni_ac_vlc_len); + init_uni_ac_vlc(m->huff_size_ac_chrominance, m->uni_chroma_ac_vlc_len); s->intra_ac_vlc_length = - s->intra_ac_vlc_last_length = uni_ac_vlc_len; + s->intra_ac_vlc_last_length = m->uni_ac_vlc_len; s->intra_chroma_ac_vlc_length = - s->intra_chroma_ac_vlc_last_length = uni_chroma_ac_vlc_len; + s->intra_chroma_ac_vlc_last_length = m->uni_chroma_ac_vlc_len; + + // Buffers start out empty. + m->huff_buffer = NULL; + m->huff_ncode = 0; + m->huff_capacity = 0; + m->error = 0; s->mjpeg_ctx = m; return 0; @@ -115,71 +99,193 @@ av_cold int ff_mjpeg_encode_init(MpegEncContext *s) av_cold void ff_mjpeg_encode_close(MpegEncContext *s) { + av_freep(&s->mjpeg_ctx->huff_buffer); av_freep(&s->mjpeg_ctx); } +/** + * Encodes and outputs the entire frame in the JPEG format. + * + * @param s The MpegEncContext. + */ +void ff_mjpeg_encode_picture_frame(MpegEncContext *s) +{ + int i, nbits, code, table_id; + MJpegContext *m = s->mjpeg_ctx; + uint8_t *huff_size[4] = {m->huff_size_dc_luminance, + m->huff_size_dc_chrominance, + m->huff_size_ac_luminance, + m->huff_size_ac_chrominance}; + uint16_t *huff_code[4] = {m->huff_code_dc_luminance, + m->huff_code_dc_chrominance, + m->huff_code_ac_luminance, + m->huff_code_ac_chrominance}; + size_t total_bits = 0; + size_t bytes_needed; + + // Estimate the total size first + for (i = 0; i < m->huff_ncode; i++) { + table_id = m->huff_buffer[i].table_id; + code = m->huff_buffer[i].code; + nbits = code & 0xf; + + total_bits += huff_size[table_id][code] + nbits; + } + + bytes_needed = (total_bits + 7) / 8; + ff_mpv_reallocate_putbitbuffer(s, bytes_needed, bytes_needed); + + for (i = 0; i < m->huff_ncode; i++) { + table_id = m->huff_buffer[i].table_id; + code = m->huff_buffer[i].code; + nbits = code & 0xf; + + put_bits(&s->pb, huff_size[table_id][code], huff_code[table_id][code]); + if (nbits != 0) { + put_sbits(&s->pb, nbits, m->huff_buffer[i].mant); + } + } + + m->huff_ncode = 0; +} + +/** + * Add code and table_id to the JPEG buffer. + * + * @param s The MJpegContext which contains the JPEG buffer. + * @param table_id Which Huffman table the code belongs to. + * @param code The encoded exponent of the coefficients and the run-bits. + */ +static inline void ff_mjpeg_encode_code(MJpegContext *s, uint8_t table_id, int code) +{ + MJpegHuffmanCode *c = &s->huff_buffer[s->huff_ncode++]; + av_assert0(s->huff_ncode < s->huff_capacity); + c->table_id = table_id; + c->code = code; +} + +/** + * Add the coefficient's data to the JPEG buffer. + * + * @param s The MJpegContext which contains the JPEG buffer. + * @param table_id Which Huffman table the code belongs to. + * @param val The coefficient. + * @param run The run-bits. + */ +static void ff_mjpeg_encode_coef(MJpegContext *s, uint8_t table_id, int val, int run) +{ + int mant, code; + + if (val == 0) { + av_assert0(run == 0); + ff_mjpeg_encode_code(s, table_id, 0); + } else { + mant = val; + if (val < 0) { + val = -val; + mant--; + } + + code = (run << 4) | (av_log2_16bit(val) + 1); + + s->huff_buffer[s->huff_ncode].mant = mant; + ff_mjpeg_encode_code(s, table_id, code); + } +} + +/** + * Add the block's data into the JPEG buffer. + * + * @param s The MJpegEncContext that contains the JPEG buffer. + * @param block The block. + * @param n The block's index or number. + */ static void encode_block(MpegEncContext *s, int16_t *block, int n) { - int mant, nbits, code, i, j; - int component, dc, run, last_index, val; + int i, j, table_id; + int component, dc, last_index, val, run; MJpegContext *m = s->mjpeg_ctx; - uint8_t *huff_size_ac; - uint16_t *huff_code_ac; + + if (m->error) return; + + av_assert0(m->huff_capacity >= m->huff_ncode + 64); /* DC coef */ component = (n <= 3 ? 0 : (n&1) + 1); + table_id = (n <= 3 ? 0 : 1); dc = block[0]; /* overflow is impossible */ val = dc - s->last_dc[component]; - if (n < 4) { - ff_mjpeg_encode_dc(&s->pb, val, m->huff_size_dc_luminance, m->huff_code_dc_luminance); - huff_size_ac = m->huff_size_ac_luminance; - huff_code_ac = m->huff_code_ac_luminance; - } else { - ff_mjpeg_encode_dc(&s->pb, val, m->huff_size_dc_chrominance, m->huff_code_dc_chrominance); - huff_size_ac = m->huff_size_ac_chrominance; - huff_code_ac = m->huff_code_ac_chrominance; - } + + ff_mjpeg_encode_coef(m, table_id, val, 0); + s->last_dc[component] = dc; /* AC coefs */ run = 0; last_index = s->block_last_index[n]; + table_id |= 2; + for(i=1;i<=last_index;i++) { j = s->intra_scantable.permutated[i]; val = block[j]; + if (val == 0) { run++; } else { while (run >= 16) { - put_bits(&s->pb, huff_size_ac[0xf0], huff_code_ac[0xf0]); + ff_mjpeg_encode_code(m, table_id, 0xf0); run -= 16; } - mant = val; - if (val < 0) { - val = -val; - mant--; - } - - nbits= av_log2_16bit(val) + 1; - code = (run << 4) | nbits; - - put_bits(&s->pb, huff_size_ac[code], huff_code_ac[code]); - - put_sbits(&s->pb, nbits, mant); + ff_mjpeg_encode_coef(m, table_id, val, run); run = 0; } } /* output EOB only if not already 64 values */ if (last_index < 63 || run != 0) - put_bits(&s->pb, huff_size_ac[0], huff_code_ac[0]); + ff_mjpeg_encode_code(m, table_id, 0); } -void ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) +// Possibly reallocate the huffman code buffer, assuming blocks_per_mb. +// Set s->mjpeg_ctx->error on ENOMEM. +static void realloc_huffman(MpegEncContext *s, int blocks_per_mb) { - int i; + MJpegContext *m = s->mjpeg_ctx; + size_t num_mbs, num_blocks, num_codes; + MJpegHuffmanCode *new_buf; + if (m->error) return; + // Make sure we have enough space to hold this frame. + num_mbs = s->mb_width * s->mb_height; + num_blocks = num_mbs * blocks_per_mb; + av_assert0(m->huff_ncode <= + (s->mb_y * s->mb_width + s->mb_x) * blocks_per_mb * 64); + num_codes = num_blocks * 64; + + new_buf = av_fast_realloc(m->huff_buffer, &m->huff_capacity, + num_codes * sizeof(MJpegHuffmanCode)); + if (!new_buf) { + m->error = AVERROR(ENOMEM); + } else { + m->huff_buffer = new_buf; + } +} + +int ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) +{ + int i, is_chroma_420; + + // Number of bits used depends on future data. + // So, nothing that relies on encoding many times and taking the + // one with the fewest bits will work properly here. + if (s->i_tex_bits != MJPEG_HUFFMAN_EST_BITS_PER_CODE * + s->mjpeg_ctx->huff_ncode) { + av_log(NULL, AV_LOG_ERROR, "Unsupported encoding method\n"); + return AVERROR(EINVAL); + } + if (s->chroma_format == CHROMA_444) { + realloc_huffman(s, 12); encode_block(s, block[0], 0); encode_block(s, block[2], 2); encode_block(s, block[4], 4); @@ -196,10 +302,12 @@ void ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) encode_block(s, block[11], 11); } } else { + is_chroma_420 = (s->chroma_format == CHROMA_420); + realloc_huffman(s, 5 + (is_chroma_420 ? 1 : 3)); for(i=0;i<5;i++) { encode_block(s, block[i], i); } - if (s->chroma_format == CHROMA_420) { + if (is_chroma_420) { encode_block(s, block[5], 5); } else { encode_block(s, block[6], 6); @@ -207,8 +315,11 @@ void ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) encode_block(s, block[7], 7); } } + if (s->mjpeg_ctx->error) + return s->mjpeg_ctx->error; - s->i_tex_bits += get_bits_diff(s); + s->i_tex_bits = MJPEG_HUFFMAN_EST_BITS_PER_CODE * s->mjpeg_ctx->huff_ncode; + return 0; } // maximum over s->mjpeg_vsample[i] @@ -261,7 +372,9 @@ FF_MPV_COMMON_OPTS { "left", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = 1 }, INT_MIN, INT_MAX, VE, "pred" }, { "plane", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = 2 }, INT_MIN, INT_MAX, VE, "pred" }, { "median", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = 3 }, INT_MIN, INT_MAX, VE, "pred" }, - +{ "huffman", "Huffman table strategy", OFFSET(huffman), AV_OPT_TYPE_INT, { .i64 = HUFFMAN_TABLE_DEFAULT }, 0, NB_HUFFMAN_TABLE_OPTION - 1, VE, "huffman" }, + { "default", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = HUFFMAN_TABLE_DEFAULT }, INT_MIN, INT_MAX, VE, "huffman" }, + { "optimal", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = HUFFMAN_TABLE_OPTIMAL }, INT_MIN, INT_MAX, VE, "huffman" }, { NULL}, }; diff --git a/libavcodec/mjpegenc.h b/libavcodec/mjpegenc.h index 60cd56677f..577fa1fec6 100644 --- a/libavcodec/mjpegenc.h +++ b/libavcodec/mjpegenc.h @@ -39,18 +39,67 @@ #include "mpegvideo.h" #include "put_bits.h" +/** + * Buffer of JPEG frame data. + * + * Optimal Huffman table generation requires the frame data to be loaded into + * a buffer so that the tables can be computed. + * There are at most mb_width*mb_height*12*64 of these per frame. + */ +typedef struct MJpegHuffmanCode { + // 0=DC lum, 1=DC chrom, 2=AC lum, 3=AC chrom + uint8_t table_id; ///< The Huffman table id associated with the data. + uint8_t code; ///< The exponent. + uint16_t mant; ///< The mantissa. +} MJpegHuffmanCode; + +/** + * Holds JPEG frame data and Huffman table data. + */ typedef struct MJpegContext { - uint8_t huff_size_dc_luminance[12]; //FIXME use array [3] instead of lumi / chroma, for easier addressing - uint16_t huff_code_dc_luminance[12]; - uint8_t huff_size_dc_chrominance[12]; - uint16_t huff_code_dc_chrominance[12]; + //FIXME use array [3] instead of lumi / chroma, for easier addressing + uint8_t huff_size_dc_luminance[12]; ///< DC luminance Huffman table size. + uint16_t huff_code_dc_luminance[12]; ///< DC luminance Huffman table codes. + uint8_t huff_size_dc_chrominance[12]; ///< DC chrominance Huffman table size. + uint16_t huff_code_dc_chrominance[12]; ///< DC chrominance Huffman table codes. + + uint8_t huff_size_ac_luminance[256]; ///< AC luminance Huffman table size. + uint16_t huff_code_ac_luminance[256]; ///< AC luminance Huffman table codes. + uint8_t huff_size_ac_chrominance[256]; ///< AC chrominance Huffman table size. + uint16_t huff_code_ac_chrominance[256]; ///< AC chrominance Huffman table codes. - uint8_t huff_size_ac_luminance[256]; - uint16_t huff_code_ac_luminance[256]; - uint8_t huff_size_ac_chrominance[256]; - uint16_t huff_code_ac_chrominance[256]; + /** Storage for AC luminance VLC (in MpegEncContext) */ + uint8_t uni_ac_vlc_len[64 * 64 * 2]; + /** Storage for AC chrominance VLC (in MpegEncContext) */ + uint8_t uni_chroma_ac_vlc_len[64 * 64 * 2]; + + // Default DC tables have exactly 12 values + uint8_t bits_dc_luminance[17]; ///< DC luminance Huffman bits. + uint8_t val_dc_luminance[12]; ///< DC luminance Huffman values. + uint8_t bits_dc_chrominance[17]; ///< DC chrominance Huffman bits. + uint8_t val_dc_chrominance[12]; ///< DC chrominance Huffman values. + + // 8-bit JPEG has max 256 values + uint8_t bits_ac_luminance[17]; ///< AC luminance Huffman bits. + uint8_t val_ac_luminance[256]; ///< AC luminance Huffman values. + uint8_t bits_ac_chrominance[17]; ///< AC chrominance Huffman bits. + uint8_t val_ac_chrominance[256]; ///< AC chrominance Huffman values. + + unsigned int huff_capacity; ///< Size of the buffer, in entries. + size_t huff_ncode; ///< Number of current entries in the buffer. + MJpegHuffmanCode *huff_buffer; ///< Buffer for Huffman code values. + int error; ///< Error code. } MJpegContext; +/** + * 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. + NB_HUFFMAN_TABLE_OPTION = 2 +}; + static inline void put_marker(PutBitContext *p, enum JpegMarker code) { put_bits(p, 8, 0xff); @@ -58,7 +107,8 @@ static inline void put_marker(PutBitContext *p, enum JpegMarker code) } int ff_mjpeg_encode_init(MpegEncContext *s); +void ff_mjpeg_encode_picture_frame(MpegEncContext *s); void ff_mjpeg_encode_close(MpegEncContext *s); -void ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]); +int ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]); #endif /* AVCODEC_MJPEGENC_H */ diff --git a/libavcodec/mjpegenc_common.c b/libavcodec/mjpegenc_common.c index 7a6fe7468f..8ec3df9090 100644 --- a/libavcodec/mjpegenc_common.c +++ b/libavcodec/mjpegenc_common.c @@ -33,8 +33,35 @@ #include "put_bits.h" #include "mjpegenc.h" #include "mjpegenc_common.h" +#include "mjpegenc_huffman.h" #include "mjpeg.h" +av_cold void init_uni_ac_vlc(const uint8_t huff_size_ac[256], uint8_t *uni_ac_vlc_len) +{ + int i; + + for (i = 0; i < 128; i++) { + int level = i - 64; + int run; + if (!level) + continue; + for (run = 0; run < 64; run++) { + int len, code, nbits; + int alevel = FFABS(level); + + len = (run >> 4) * huff_size_ac[0xf0]; + + nbits= av_log2_16bit(alevel) + 1; + code = ((15&run) << 4) | nbits; + + len += huff_size_ac[code] + nbits; + + uni_ac_vlc_len[UNI_AC_ENC_INDEX(run, i)] = len; + // We ignore EOB as its just a constant which does not change generally + } + } +} + /* table_class: 0 = DC coef, 1 = AC coefs */ static int put_huffman_table(PutBitContext *p, int table_class, int table_id, const uint8_t *bits_table, const uint8_t *value_table) @@ -104,15 +131,30 @@ static void jpeg_table_header(AVCodecContext *avctx, PutBitContext *p, ptr = put_bits_ptr(p); put_bits(p, 16, 0); /* patched later */ size = 2; - size += put_huffman_table(p, 0, 0, avpriv_mjpeg_bits_dc_luminance, - avpriv_mjpeg_val_dc); - size += put_huffman_table(p, 0, 1, avpriv_mjpeg_bits_dc_chrominance, - avpriv_mjpeg_val_dc); - - size += put_huffman_table(p, 1, 0, avpriv_mjpeg_bits_ac_luminance, - avpriv_mjpeg_val_ac_luminance); - size += put_huffman_table(p, 1, 1, avpriv_mjpeg_bits_ac_chrominance, - avpriv_mjpeg_val_ac_chrominance); + + // Only MJPEG can have a variable Huffman variable. All other + // formats use the default Huffman table. + if (s->out_format == FMT_MJPEG && s->huffman == HUFFMAN_TABLE_OPTIMAL) { + size += put_huffman_table(p, 0, 0, s->mjpeg_ctx->bits_dc_luminance, + s->mjpeg_ctx->val_dc_luminance); + size += put_huffman_table(p, 0, 1, s->mjpeg_ctx->bits_dc_chrominance, + s->mjpeg_ctx->val_dc_chrominance); + + size += put_huffman_table(p, 1, 0, s->mjpeg_ctx->bits_ac_luminance, + s->mjpeg_ctx->val_ac_luminance); + size += put_huffman_table(p, 1, 1, s->mjpeg_ctx->bits_ac_chrominance, + s->mjpeg_ctx->val_ac_chrominance); + } else { + size += put_huffman_table(p, 0, 0, avpriv_mjpeg_bits_dc_luminance, + avpriv_mjpeg_val_dc); + size += put_huffman_table(p, 0, 1, avpriv_mjpeg_bits_dc_chrominance, + avpriv_mjpeg_val_dc); + + size += put_huffman_table(p, 1, 0, avpriv_mjpeg_bits_ac_luminance, + avpriv_mjpeg_val_ac_luminance); + size += put_huffman_table(p, 1, 1, avpriv_mjpeg_bits_ac_chrominance, + avpriv_mjpeg_val_ac_chrominance); + } AV_WB16(ptr, size); } @@ -372,14 +414,116 @@ void ff_mjpeg_escape_FF(PutBitContext *pb, int start) } } +/** + * Builds all 4 optimal Huffman tables. + * + * Uses the data stored in the JPEG buffer to compute the tables. + * Stores the Huffman tables in the bits_* and val_* arrays in the MJpegContext. + * + * @param m MJpegContext containing the JPEG buffer. + */ +static void ff_mjpeg_build_optimal_huffman(MJpegContext *m) +{ + int i, ret, table_id, code; + + MJpegEncHuffmanContext dc_luminance_ctx; + MJpegEncHuffmanContext dc_chrominance_ctx; + MJpegEncHuffmanContext ac_luminance_ctx; + MJpegEncHuffmanContext ac_chrominance_ctx; + MJpegEncHuffmanContext *ctx[4] = {&dc_luminance_ctx, + &dc_chrominance_ctx, + &ac_luminance_ctx, + &ac_chrominance_ctx}; + for (i = 0; i < 4; i++) { + ff_mjpeg_encode_huffman_init(ctx[i]); + } + for (i = 0; i < m->huff_ncode; i++) { + table_id = m->huff_buffer[i].table_id; + code = m->huff_buffer[i].code; + + ff_mjpeg_encode_huffman_increment(ctx[table_id], code); + } + + ret = ff_mjpeg_encode_huffman_close(&dc_luminance_ctx, + m->bits_dc_luminance, + m->val_dc_luminance, 12); + av_assert0(!ret); + ret = ff_mjpeg_encode_huffman_close(&dc_chrominance_ctx, + m->bits_dc_chrominance, + m->val_dc_chrominance, 12); + av_assert0(!ret); + ret = ff_mjpeg_encode_huffman_close(&ac_luminance_ctx, + m->bits_ac_luminance, + m->val_ac_luminance, 256); + av_assert0(!ret); + ret = ff_mjpeg_encode_huffman_close(&ac_chrominance_ctx, + m->bits_ac_chrominance, + m->val_ac_chrominance, 256); + av_assert0(!ret); + + ff_mjpeg_build_huffman_codes(m->huff_size_dc_luminance, + m->huff_code_dc_luminance, + m->bits_dc_luminance, + m->val_dc_luminance); + ff_mjpeg_build_huffman_codes(m->huff_size_dc_chrominance, + m->huff_code_dc_chrominance, + m->bits_dc_chrominance, + m->val_dc_chrominance); + ff_mjpeg_build_huffman_codes(m->huff_size_ac_luminance, + m->huff_code_ac_luminance, + m->bits_ac_luminance, + m->val_ac_luminance); + ff_mjpeg_build_huffman_codes(m->huff_size_ac_chrominance, + m->huff_code_ac_chrominance, + m->bits_ac_chrominance, + m->val_ac_chrominance); +} + +/** + * Writes the complete JPEG frame. + * + * Header + values + stuffing. + * + * @param s The MpegEncContext. + * @return int Error code, 0 if successful. + */ int ff_mjpeg_encode_stuffing(MpegEncContext *s) { int i; PutBitContext *pbc = &s->pb; int mb_y = s->mb_y - !s->mb_x; + int ret; + MJpegContext *m; + + m = s->mjpeg_ctx; + + if (m->error) + return m->error; + + if (s->huffman == HUFFMAN_TABLE_OPTIMAL) { + ff_mjpeg_build_optimal_huffman(m); + + // Replace the VLCs with the optimal ones. + // The default ones may be used for trellis during quantization. + init_uni_ac_vlc(m->huff_size_ac_luminance, m->uni_ac_vlc_len); + init_uni_ac_vlc(m->huff_size_ac_chrominance, m->uni_chroma_ac_vlc_len); + s->intra_ac_vlc_length = + s->intra_ac_vlc_last_length = m->uni_ac_vlc_len; + s->intra_chroma_ac_vlc_length = + s->intra_chroma_ac_vlc_last_length = m->uni_chroma_ac_vlc_len; + } + + ff_mjpeg_encode_picture_header(s->avctx, &s->pb, &s->intra_scantable, + s->pred, s->intra_matrix, s->chroma_intra_matrix); + ff_mjpeg_encode_picture_frame(s); + if (m->error < 0) { + ret = m->error; + return ret; + } + + ret = ff_mpv_reallocate_putbitbuffer(s, put_bits_count(&s->pb) / 8 + 100, + put_bits_count(&s->pb) / 4 + 1000); - int ret = ff_mpv_reallocate_putbitbuffer(s, put_bits_count(&s->pb) / 8 + 100, - put_bits_count(&s->pb) / 4 + 1000); if (ret < 0) { av_log(s->avctx, AV_LOG_ERROR, "Buffer reallocation failed\n"); goto fail; diff --git a/libavcodec/mjpegenc_common.h b/libavcodec/mjpegenc_common.h index 6e51ca04f8..7d760f8a32 100644 --- a/libavcodec/mjpegenc_common.h +++ b/libavcodec/mjpegenc_common.h @@ -40,4 +40,6 @@ void ff_mjpeg_init_hvsample(AVCodecContext *avctx, int hsample[4], int vsample[4 void ff_mjpeg_encode_dc(PutBitContext *pb, int val, uint8_t *huff_size, uint16_t *huff_code); +av_cold void init_uni_ac_vlc(const uint8_t huff_size_ac[256], uint8_t *uni_ac_vlc_len); + #endif /* AVCODEC_MJPEGENC_COMMON_H */ diff --git a/libavcodec/mjpegenc_huffman.c b/libavcodec/mjpegenc_huffman.c new file mode 100644 index 0000000000..a5d7d5365b --- /dev/null +++ b/libavcodec/mjpegenc_huffman.c @@ -0,0 +1,195 @@ +/* + * MJPEG encoder + * Copyright (c) 2016 William Ma, Ted Ying, Jerry Jiang + * + * This file is part of FFmpeg. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include +#include "libavutil/common.h" +#include "libavutil/error.h" +#include "libavutil/qsort.h" +#include "mjpegenc_huffman.h" + +/** + * Comparison function for two PTables by prob + * + * @param a First PTable to compare + * @param b Second PTable to compare + * @return < 0 for less than, 0 for equals, > 0 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 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 < 0 for less than, 0 for equals, > 0 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 a_val.length - b_val.length; +} + +/** + * Computes the length of the Huffman encoding for each distinct input value. + * Uses package merge algorithm as follows: + * 1. start with an empty list, lets call it list(0), set i = 0 + * 2. add 1 entry to list(i) for each symbol we have and give each a score equal to the probability of the respective symbol + * 3. merge the 2 symbols of least score and put them in list(i+1), and remove them from list(i). The new score will be the sum of the 2 scores + * 4. if there is more than 1 symbol left in the current list(i), then goto 3 + * 5. i++ + * 6. if i < 16 goto 2 + * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols) + * 8. the length of the huffman code for symbol s will be equal to the number of times the symbol occurs in the select elements + * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details + * + * 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 max_length max length of an encoding + */ +void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length) +{ + PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp; + + int times, i, j, k; + + int nbits[257] = {0}; + + int min; + + to->nitems = 0; + from->nitems = 0; + to->item_idx[0] = 0; + from->item_idx[0] = 0; + AV_QSORT(prob_table, size, PTable, compare_by_prob); + + for (times = 0; times <= max_length; times++) { + to->nitems = 0; + to->item_idx[0] = 0; + + j = 0; + k = 0; + + if (times < max_length) { + i = 0; + } + while (i < size || j + 1 < from->nitems) { + to->nitems++; + to->item_idx[to->nitems] = to->item_idx[to->nitems - 1]; + if (i < size && + (j + 1 >= from->nitems || + prob_table[i].prob < + from->probability[j] + from->probability[j + 1])) { + to->items[to->item_idx[to->nitems]++] = prob_table[i].value; + to->probability[to->nitems - 1] = prob_table[i].prob; + i++; + } else { + for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) { + to->items[to->item_idx[to->nitems]++] = from->items[k]; + } + to->probability[to->nitems - 1] = + from->probability[j] + from->probability[j + 1]; + j += 2; + } + } + temp = to; + to = from; + from = temp; + } + + min = (size - 1 < from->nitems) ? size - 1 : from->nitems; + for (i = 0; i < from->item_idx[min]; i++) { + nbits[from->items[i]]++; + } + // we don't want to return the 256 bit count (it was just in here to prevent + // all 1s encoding) + j = 0; + for (i = 0; i < 256; i++) { + if (nbits[i] > 0) { + distincts[j].code = i; + distincts[j].length = nbits[i]; + j++; + } + } +} + +void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s) +{ + memset(s->val_count, 0, sizeof(s->val_count)); +} + +/** + * Produces a Huffman encoding with a given input + * + * @param s input to encode + * @param bits output array where the ith character represents how many input values have i length encoding + * @param val output array of input values sorted by their encoded length + * @param max_nval maximum number of distinct input values + * @return int Return code, 0 if succeeded. + */ +int ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17], + uint8_t val[], int max_nval) +{ + int i, j; + int nval = 0; + PTable val_counts[257]; + HuffTable distincts[256]; + + for (i = 0; i < 256; i++) { + if (s->val_count[i]) nval++; + } + if (nval > max_nval) { + return AVERROR(EINVAL); + } + + j = 0; + for (i = 0; i < 256; i++) { + if (s->val_count[i]) { + val_counts[j].value = i; + val_counts[j].prob = s->val_count[i]; + j++; + } + } + val_counts[j].value = 256; + val_counts[j].prob = 0; + ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16); + AV_QSORT(distincts, nval, HuffTable, compare_by_length); + + memset(bits, 0, sizeof(bits[0]) * 17); + for (i = 0; i < nval; i++) { + val[i] = distincts[i].code; + bits[distincts[i].length]++; + } + + return 0; +} diff --git a/libavcodec/mjpegenc_huffman.h b/libavcodec/mjpegenc_huffman.h new file mode 100644 index 0000000000..ec6251b519 --- /dev/null +++ b/libavcodec/mjpegenc_huffman.h @@ -0,0 +1,74 @@ +/* + * MJPEG encoder + * Copyright (c) 2016 William Ma, Ted Ying, Jerry Jiang + * + * This file is part of FFmpeg. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +/** + * @file + * Huffman table generation for MJPEG encoder. + */ + +#ifndef AVCODEC_MJPEGENC_HUFFMAN_H +#define AVCODEC_MJPEGENC_HUFFMAN_H + +typedef struct MJpegEncHuffmanContext { + int val_count[256]; +} MJpegEncHuffmanContext; + +// Uses the package merge algorithm to compute the Huffman table. +void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s); +static inline void ff_mjpeg_encode_huffman_increment(MJpegEncHuffmanContext *s, + uint8_t val) +{ + s->val_count[val]++; +} +int ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, + uint8_t bits[17], uint8_t val[], + int max_nval); + + +/** + * Used to assign a occurrence count or "probability" to an input value + */ +typedef struct PTable { + int value; ///< input value + int prob; ///< number of occurences of this value in input +} PTable; + +/** + * Used to store intermediate lists in the package merge algorithm + */ +typedef struct PackageMergerList { + int nitems; ///< number of items in the list and probability ex. 4 + int item_idx[515]; ///< index range for each item in items 0, 2, 5, 9, 13 + int probability[514]; ///< probability of each item 3, 8, 18, 46 + int items[257 * 16]; ///< chain of all individual values that make up items A, B, A, B, C, A, B, C, D, C, D, D, E +} PackageMergerList; + +/** + * Used to store optimal huffman encoding results + */ +typedef struct HuffTable { + int code; ///< code is the input value + int length; ///< length of the encoding +} HuffTable; + +void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, + int size, int max_length); +#endif /* AVCODEC_MJPEGENC_HUFFMAN_H */ diff --git a/libavcodec/mpegvideo.h b/libavcodec/mpegvideo.h index c82fa3e1a1..85df19154f 100644 --- a/libavcodec/mpegvideo.h +++ b/libavcodec/mpegvideo.h @@ -422,6 +422,7 @@ typedef struct MpegEncContext { struct MJpegContext *mjpeg_ctx; int esc_pos; int pred; + int huffman; /* MSMPEG4 specific */ int mv_table_index; diff --git a/libavcodec/mpegvideo_enc.c b/libavcodec/mpegvideo_enc.c index cdda73b654..b1d8dae4b2 100644 --- a/libavcodec/mpegvideo_enc.c +++ b/libavcodec/mpegvideo_enc.c @@ -266,7 +266,8 @@ static void mpv_encode_defaults(MpegEncContext *s) s->picture_in_gop_number = 0; } -av_cold int ff_dct_encode_init(MpegEncContext *s) { +av_cold int ff_dct_encode_init(MpegEncContext *s) +{ if (ARCH_X86) ff_dct_encode_init_x86(s); @@ -642,6 +643,15 @@ FF_ENABLE_DEPRECATION_WARNINGS return -1; } + if ((s->mpv_flags & FF_MPV_FLAG_QP_RD) && + (s->codec_id == AV_CODEC_ID_AMV || + s->codec_id == AV_CODEC_ID_MJPEG)) { + // Used to produce garbage with MJPEG. + av_log(avctx, AV_LOG_ERROR, + "QP RD is no longer compatible with MJPEG or AMV\n"); + return -1; + } + #if FF_API_PRIVATE_OPT FF_DISABLE_DEPRECATION_WARNINGS if (avctx->scenechange_threshold) @@ -3932,9 +3942,8 @@ static int encode_picture(MpegEncContext *s, int picture_number) s->last_bits= put_bits_count(&s->pb); switch(s->out_format) { case FMT_MJPEG: - if (CONFIG_MJPEG_ENCODER) - ff_mjpeg_encode_picture_header(s->avctx, &s->pb, &s->intra_scantable, - s->pred, s->intra_matrix, s->chroma_intra_matrix); + /* The MJPEG headers are printed after the initial encoding so that the + * optimal huffman encoding can be found. */ break; case FMT_H261: if (CONFIG_H261_ENCODER) diff --git a/libavcodec/tests/.gitignore b/libavcodec/tests/.gitignore index 0ab029696d..f22ac821cb 100644 --- a/libavcodec/tests/.gitignore +++ b/libavcodec/tests/.gitignore @@ -10,6 +10,7 @@ /imgconvert /jpeg2000dwt /mathops +/mjpegenc_huffman /motion /options /rangecoder diff --git a/libavcodec/tests/mjpegenc_huffman.c b/libavcodec/tests/mjpegenc_huffman.c new file mode 100644 index 0000000000..4559cbe765 --- /dev/null +++ b/libavcodec/tests/mjpegenc_huffman.c @@ -0,0 +1,163 @@ +/* + * Copyright (c) 2016 William Ma, Sofia Kim, Dustin Woo + * + * This file is part of FFmpeg. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +/** + * @file + * Optimal Huffman Encoding tests. + */ + +#include "libavcodec/avcodec.h" +#include +#include "libavcodec/mjpegenc.h" +#include "libavcodec/mjpegenc_huffman.h" +#include "libavcodec/mjpegenc_common.h" +#include "libavcodec/mpegvideo.h" + +// Validate the computed lengths satisfy the JPEG restrictions and is optimal. +static int check_lengths(int L, int expected_length, + const int *probs, int nprobs) +{ + HuffTable lengths[256]; + PTable val_counts[256]; + int actual_length = 0, i, j, k, prob, length; + int ret = 0; + double cantor_measure = 0; + assert(nprobs <= 256); + + for (i = 0; i < nprobs; i++) { + val_counts[i] = (PTable){.value = i, .prob = probs[i]}; + } + + ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L); + + for (i = 0; i < nprobs; i++) { + // Find the value's prob and length + for (j = 0; j < nprobs; j++) + if (val_counts[j].value == i) break; + for (k = 0; k < nprobs; k++) + if (lengths[k].code == i) break; + if (!(j < nprobs && k < nprobs)) return 1; + prob = val_counts[j].prob; + length = lengths[k].length; + + if (prob) { + actual_length += prob * length; + cantor_measure += 1. / (1 << length); + } + + if (length > L || length < 1) return 1; + } + // Check that the codes can be prefix-free. + if (cantor_measure > 1) ret = 1; + // Check that the total length is optimal + if (actual_length != expected_length) ret = 1; + + if (ret == 1) { + fprintf(stderr, + "Cantor measure: %f\n" + "Actual length: %d\n" + "Expected length: %d\n", + cantor_measure, actual_length, expected_length); + } + + return ret; +} + +static const int probs_zeroes[] = {6, 6, 0, 0, 0}; +static const int probs_skewed[] = {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}; +static const int probs_sat[] = {74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, + 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121, 1, 1583, 0, 16, 21, 2, 132, + 2, 15, 9, 13, 1, 0, 2293, 2, 8, 5, 2, 30, 0, 0, 4, 54, 783, 4, 1, 2, 4, + 0, 22, 93, 1, 143, 19, 0, 36, 32, 4, 6, 33, 3, 45, 0, 8, 1, 0, 18, 17, 1, + 0, 1, 0, 0, 1, 1004, 38, 3, 8, 90, 23, 0, 2819, 3, 0, 970, 158, 9, 6, 4, + 48, 4, 0, 1, 0, 0, 60, 3, 62, 0, 2, 2, 2, 279, 66, 16, 1, 20, 0, 7, 9, + 32, 1411, 6, 3, 27, 1, 5, 49, 0, 0, 0, 0, 0, 2, 10, 1, 1, 2, 3, 801, 3, + 25, 5, 1, 1, 0, 632, 0, 14, 18, 5, 8, 200, 4, 4, 22, 12, 0, 4, 1, 0, 2, + 4, 9, 3, 16, 7, 2, 2, 213, 0, 2, 620, 39303, 0, 1, 0, 2, 1, 183781, 1, + 0, 0, 0, 94, 7, 3, 4, 0, 4, 306, 43, 352, 76, 34, 13, 11, 0, 51, 1, 13, + 19, 0, 26, 0, 7276, 4, 207, 31, 1, 2, 4, 6, 19, 8, 17, 4, 6, 0, 1085, 0, + 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2, 2, + 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1}; + +// Test the example given on @see +// http://guru.multimedia.cx/small-tasks-for-ffmpeg/ +int main(int argc, char **argv) +{ + int i, ret = 0; + // Probabilities of symbols 0..4 + static 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 + static const HuffTable expected[] = { + {.code = 0, .length = 3}, + {.code = 1, .length = 3}, + {.code = 2, .length = 3}, + {.code = 3, .length = 3}, + {.code = 4, .length = 1}, + }; + // Actual code lengths + HuffTable distincts[5]; + + // Build optimal huffman tree using an internal function, to allow for + // smaller-than-normal test cases. This mutates val_counts by sorting. + ff_mjpegenc_huffman_compute_bits(val_counts, distincts, + FF_ARRAY_ELEMS(distincts), 3); + + for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) { + 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 + if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes))) + ret = 1; + // Check skewed distribution over 256 without saturated lengths + if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed))) + ret = 1; + // Check skewed distribution over 256 with saturated lengths + if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat))) + ret = 1; + + return ret; +} -- cgit v1.2.1