From patchwork Tue Dec 27 07:37:09 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jerry Jiang X-Patchwork-Id: 1940 Delivered-To: ffmpegpatchwork@gmail.com Received: by 10.103.89.21 with SMTP id n21csp1369302vsb; Mon, 26 Dec 2016 23:42:59 -0800 (PST) X-Received: by 10.28.48.7 with SMTP id w7mr26198161wmw.115.1482824579855; Mon, 26 Dec 2016 23:42:59 -0800 (PST) Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id x74si45249289wmd.166.2016.12.26.23.42.59; Mon, 26 Dec 2016 23:42:59 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@gmail.com; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE dis=NONE) header.from=gmail.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id ACE9F689D34; Tue, 27 Dec 2016 09:42:53 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-qk0-f170.google.com (mail-qk0-f170.google.com [209.85.220.170]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 8C7E7689975 for ; Tue, 27 Dec 2016 09:42:46 +0200 (EET) Received: by mail-qk0-f170.google.com with SMTP id u25so203026296qki.2 for ; Mon, 26 Dec 2016 23:42:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=ubXhlm+xVZSeGZUst+xxLyEe13BTfD/4tTeNLTPUwCI=; b=Ctl6+LuRaUSKvE1tnQRbuMu/DKn9/4actJXQuK9a0U6bJVzerLFgxtp+mza2Cb+9kG YbL++N3uHmeZk9Vrn3ffOCp8kfF5HhIoYLryyybCG2UrZNGVdeJVSB0Kxm/Vj4P6IilB HzoAr8hIGAhQi2o2pmKXAU1UFfoj2x5mJeWut7dxaM7gFzNWyFcvhVC9PL9ubZ52Rtqi JZQSxEuqu4jc7gtsirN35tjv62uexSiER8+luwt52dhg2kakEf5+URMF6KGs5NrV2WW2 2MW+Xap0NJj5X9mmF+M3aysRo+OzADXE41XCnMf8HXayPaaMRYushpFtFbFH/Zecd+FL obsw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=ubXhlm+xVZSeGZUst+xxLyEe13BTfD/4tTeNLTPUwCI=; b=he7ZD+Zsiaihz13azkDYorFPTFwXUgUX51ket1lrOcwaptNeUWJ+SB4RddHcGZRx/1 kcq0qbzLnJnSCswR2MzjC/ZdNVWjpPg8+7I1JK8RYWNSNV4oiG7gIG+mGHC3ZivwyW7D nWZpljCIbH3UCAUEsdFsd0cqWjmMKaJ6qSgdYcSQQaU1zFZWWdzXYVmhVw6FPUxa8z+U Nzs9zXUZwEEgur4N4RbzgPkMNzMl9uAYPHsS6ipFir57LPhvxQnh+KF6JfW1S3tZPKhQ 6GT3MeP1v/q8C/uEaKUVGO4J0SZd6sAwqgdn2S9UZ+djRr/ZRF13yL/zRRW1bTRZURl1 hAbw== X-Gm-Message-State: AIkVDXIXBvdIjox5av6FOM7hXpH7AXcwn/T9g2ICnFCGMycpdM9Mk32r8BeYKnKAlu+NvctUIlrrmLpfMgBTjg== X-Received: by 10.55.8.12 with SMTP id 12mr23183559qki.74.1482824240516; Mon, 26 Dec 2016 23:37:20 -0800 (PST) MIME-Version: 1.0 From: Jerry Jiang Date: Tue, 27 Dec 2016 07:37:09 +0000 Message-ID: To: ffmpeg-devel@ffmpeg.org X-Content-Filtered-By: Mailman/MimeDel 2.1.20 Subject: [FFmpeg-devel] [PATCH] Implement optimal huffman encoding for (M)JPEG. X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Hey everyone, This is my first patch submitted to FFmpeg, so I'm sure that I missed something. Please bear with me. :P This patch implements the solution outlined here: https://guru.multimedia.cx/small-tasks-for-ffmpeg/ Activated by passing the flag "-huffman optimal" to the mjpeg encoder, otherwise the default huffman tables are used. --- libavcodec/Makefile | 8 +- libavcodec/mjpegenc.c | 265 +++++++++++++++++++-------- libavcodec/mjpegenc.h | 60 +++++- libavcodec/mjpegenc_common.c | 161 ++++++++++++++-- libavcodec/mjpegenc_common.h | 2 + libavcodec/mjpegenc_huffman.c | 198 ++++++++++++++++++++ libavcodec/mjpegenc_huffman.h | 71 +++++++ libavcodec/mpegvideo.h | 1 + libavcodec/mpegvideo_enc.c | 5 +- libavcodec/tests/.gitignore | 1 + libavcodec/tests/mjpegenc_huffman.c | 130 +++++++++++++ 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 + 19 files changed, 829 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 -- 2.10.2 diff --git a/libavcodec/Makefile b/libavcodec/Makefile index ec4f7fc..399eaf3 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 \ @@ -177,7 +178,8 @@ OBJS-$(CONFIG_AMRWB_DECODER) += amrwbdec.o celp_filters.o \ OBJS-$(CONFIG_AMV_ENCODER) += mjpegenc.o mjpegenc_common.o \ mpegvideo_enc.o motion_est.o \ ratecontrol.o mpeg12data.o \ - mpegvideo.o + mpegvideo.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 @@ -379,7 +381,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 @@ -1012,6 +1015,7 @@ TESTPROGS = avpacket \ jpeg2000dwt \ mathops \ options \ + mjpegenc_huffman \ utils \ TESTPROGS-$(CONFIG_CABAC) += cabac diff --git a/libavcodec/mjpegenc.c b/libavcodec/mjpegenc.c index 3d11377..d443183 100644 --- a/libavcodec/mjpegenc.c +++ b/libavcodec/mjpegenc.c @@ -39,35 +39,6 @@ #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 - } - } -} - av_cold int ff_mjpeg_encode_init(MpegEncContext *s) { MJpegContext *m; @@ -84,7 +55,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 +75,17 @@ 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->buffer = NULL; + m->buffer_last = NULL; + m->error = 0; s->mjpeg_ctx = m; return 0; @@ -115,100 +93,223 @@ av_cold int ff_mjpeg_encode_init(MpegEncContext *s) av_cold void ff_mjpeg_encode_close(MpegEncContext *s) { + // In the event of an error, not all the buffers may be freed. + while (s->mjpeg_ctx->buffer) { + struct MJpegBuffer *buffer = s->mjpeg_ctx->buffer; + s->mjpeg_ctx->buffer = buffer->next; + + av_freep(&buffer); + } + s->mjpeg_ctx->buffer_last = NULL; + av_freep(&s->mjpeg_ctx); } -static void encode_block(MpegEncContext *s, int16_t *block, int n) +/** + * 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}; + MJpegBuffer* current; + MJpegBuffer* next; + + for (current = m->buffer; current;) { + int size_increase = s->avctx->internal->byte_buffer_size/4 + + s->mb_width*MAX_MB_BYTES; + + ff_mpv_reallocate_putbitbuffer(s, MAX_MB_BYTES, size_increase); + + for (i = 0; i < current->ncode; ++i) { + code = current->codes[i]; + nbits = code & 0xf; + table_id = current->table_ids[i]; + put_bits(&s->pb, huff_size[table_id][code], huff_code[table_id][code]); + if (nbits != 0) { + put_sbits(&s->pb, nbits, current->mants[i]); + } + } + + next = current->next; + av_freep(¤t); + current = next; + } + + m->buffer = NULL; + m->buffer_last = NULL; +} + +/** + * 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) { + MJpegBuffer *m = s->buffer_last; + m->table_ids[m->ncode] = table_id; + m->codes[m->ncode++] = 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, nbits, code, i, j; - int component, dc, run, last_index, val; + int mant, code; + MJpegBuffer *m = s->buffer_last; + av_assert0(m->ncode >= 0); + av_assert0(m->ncode < sizeof(m->codes) / sizeof(m->codes[0])); + + 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); + + m->mants[m->ncode] = 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. + * @return int Return code, 0 if succeeded. + */ +static int encode_block(MpegEncContext *s, int16_t *block, int n) +{ + 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; + MJpegBuffer* buffer_block = m->buffer_last; + + // Any block has at most 64 coefficients. + if (buffer_block == NULL || buffer_block->ncode + 64 + > sizeof(buffer_block->codes) / sizeof(buffer_block->codes[0])) { + buffer_block = av_malloc(sizeof(MJpegBuffer)); + if (!buffer_block) { + return AVERROR(ENOMEM); + } + + buffer_block->next = NULL; + buffer_block->ncode = 0; + + // Add to end of buffer. + if (!m->buffer) { + m->buffer = buffer_block; + m->buffer_last = buffer_block; + } else { + m->buffer_last->next = buffer_block; + m->buffer_last = buffer_block; + } + } /* 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); + + return 0; } -void ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) +int ff_mjpeg_encode_mb(MpegEncContext *s, int16_t block[12][64]) { int i; + int ret = 0; + if (s->mjpeg_ctx->error) + return s->mjpeg_ctx->error; if (s->chroma_format == CHROMA_444) { - encode_block(s, block[0], 0); - encode_block(s, block[2], 2); - encode_block(s, block[4], 4); - encode_block(s, block[8], 8); - encode_block(s, block[5], 5); - encode_block(s, block[9], 9); + if (!ret) ret = encode_block(s, block[0], 0); + if (!ret) ret = encode_block(s, block[2], 2); + if (!ret) ret = encode_block(s, block[4], 4); + if (!ret) ret = encode_block(s, block[8], 8); + if (!ret) ret = encode_block(s, block[5], 5); + if (!ret) ret = encode_block(s, block[9], 9); if (16*s->mb_x+8 < s->width) { - encode_block(s, block[1], 1); - encode_block(s, block[3], 3); - encode_block(s, block[6], 6); - encode_block(s, block[10], 10); - encode_block(s, block[7], 7); - encode_block(s, block[11], 11); + if (!ret) ret = encode_block(s, block[1], 1); + if (!ret) ret = encode_block(s, block[3], 3); + if (!ret) ret = encode_block(s, block[6], 6); + if (!ret) ret = encode_block(s, block[10], 10); + if (!ret) ret = encode_block(s, block[7], 7); + if (!ret) ret = encode_block(s, block[11], 11); } } else { for(i=0;i<5;i++) { - encode_block(s, block[i], i); + if (!ret) ret = encode_block(s, block[i], i); } if (s->chroma_format == CHROMA_420) { - encode_block(s, block[5], 5); + if (!ret) ret = encode_block(s, block[5], 5); } else { - encode_block(s, block[6], 6); - encode_block(s, block[5], 5); - encode_block(s, block[7], 7); + if (!ret) ret = encode_block(s, block[6], 6); + if (!ret) ret = encode_block(s, block[5], 5); + if (!ret) ret = encode_block(s, block[7], 7); } } + if (ret) { + s->mjpeg_ctx->error = ret; + return ret; + } s->i_tex_bits += get_bits_diff(s); + return 0; } // maximum over s->mjpeg_vsample[i] @@ -261,7 +362,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 = 1 }, 1, 2, VE, "huffman" }, + { "default", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = 1 }, INT_MIN, INT_MAX, VE, "huffman" }, + { "optimal", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = 2 }, INT_MIN, INT_MAX, VE, "huffman" }, { NULL}, }; diff --git a/libavcodec/mjpegenc.h b/libavcodec/mjpegenc.h index 60cd566..659ee8f 100644 --- a/libavcodec/mjpegenc.h +++ b/libavcodec/mjpegenc.h @@ -39,16 +39,57 @@ #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. The data is stored in a linked + * list buffer, as the exact size may vary. + */ +typedef struct MJpegBuffer { + // 0=DC lum, 1=DC chrom, 2=AC lum, 3=AC chrom + uint8_t table_ids[64 * 12]; ///< The Huffman table id associated with the data. + uint8_t codes[64 * 12]; ///< The exponents. + uint16_t mants[64 * 12]; ///< The mantissas. + int ncode; ///< Number of current entries in this buffer. + struct MJpegBuffer *next; ///< The next struct in the linked list. +} MJpegBuffer; + +/** + * 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. + + /** 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. - 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]; + MJpegBuffer *buffer; ///< JPEG buffer linked list head. + MJpegBuffer *buffer_last; ///< JPEG buffer linked list tail. + int error; ///< Error code. } MJpegContext; static inline void put_marker(PutBitContext *p, enum JpegMarker code) @@ -58,7 +99,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 7a6fe746..f795f9f 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 == 2) { + 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_chromina nce, + 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_chromina nce, + 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_chrominan ce, + 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_chrominan ce, + avpriv_mjpeg_val_ac_chrominance); + } AV_WB16(ptr, size); } @@ -372,14 +414,111 @@ 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; + MJpegBuffer* current; + + 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 (current = m->buffer; current; current = current->next) { + for(i = 0; i < current->ncode; i++) { + ff_mjpeg_encode_huffman_increment(ctx[current->table_ids[i]], current->codes[i]); + } + } + + 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 == 2) { + 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 6e51ca0..7d760f8 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 0000000..d652dfa --- /dev/null +++ b/libavcodec/mjpegenc_huffman.c @@ -0,0 +1,198 @@ +/* + * 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/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 -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; + if (a_val.prob < b_val.prob) { + return -1; + } + if (a_val.prob > b_val.prob) { + return 1; + } + return 0; +} + +/** + * Comparison function for two HuffTables by length + * + * @param a First HuffTable to compare + * @param b Second PTable 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; + if (a_val.length < b_val.length) { + return -1; + } + if (a_val.length > b_val.length) { + return 1; + } + return 0; +} + +/** + * 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 + * + * @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 + */ +void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int maxLength) { + 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 <= maxLength; times++) { + to->nitems = 0; + to->item_idx[0] = 0; + + j = 0; + k = 0; + + if (times < maxLength) { + 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 0000000..6fd6737 --- /dev/null +++ b/libavcodec/mjpegenc_huffman.h @@ -0,0 +1,71 @@ +/* + * 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 maxLength); +#endif /* AVCODEC_MJPEGENC_HUFFMAN_H */ diff --git a/libavcodec/mpegvideo.h b/libavcodec/mpegvideo.h index c82fa3e..85df191 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 10b4c5b..a906f84 100644 --- a/libavcodec/mpegvideo_enc.c +++ b/libavcodec/mpegvideo_enc.c @@ -3897,9 +3897,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 0ab0296..f22ac82 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 0000000..a2bc993 --- /dev/null +++ b/libavcodec/tests/mjpegenc_huffman.c @@ -0,0 +1,130 @@ +/* + * 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; + 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) { + if (length > L) return 1; + actual_length += prob * length; + cantor_measure += 1. / (1 << length); + } else { + if (length != 0) return 1; + } + } + // Check that the codes can be prefix-free and not all 1's. + if (cantor_measure >= 1) return 1; + // Check that the total length is optimal + if (actual_length != expected_length) return 1; + + return 0; +} + +// Test the example given on @see Small Tasks +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}, + }; + // 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++) { + 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}; + check_lengths(16, 18, probs, sizeof(probs) / sizeof(probs[0])); + } + { + // 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}; + check_lengths(16, 41277, probs, sizeof(probs) / sizeof(probs[0])); + } + { + // Check skewed distribution over 256 with saturated lengths + int probs[] = {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}; + check_lengths(16, 669660, probs, sizeof(probs) / sizeof(probs[0])); + } + + return ret; +} diff --git a/tests/fate/libavcodec.mak b/tests/fate/libavcodec.mak index 3bc74c1..32b0c1e 100644 --- a/tests/fate/libavcodec.mak +++ b/tests/fate/libavcodec.mak @@ -49,5 +49,11 @@ fate-libavcodec-utils: CMD = run libavcodec/tests/utils fate-libavcodec-utils: CMP = null fate-libavcodec-utils: REF = /dev/null +FATE_LIBAVCODEC-yes += fate-libavcodec-huffman +fate-libavcodec-huffman: libavcodec/tests/mjpegenc_huffman$(EXESUF) +fate-libavcodec-huffman: CMD = run libavcodec/tests/mjpegenc_huffman +fate-libavcodec-huffman: CMP = null +fate-libavcodec-huffman: REF = /dev/null + FATE-$(CONFIG_AVCODEC) += $(FATE_LIBAVCODEC-yes) fate-libavcodec: $(FATE_LIBAVCODEC-yes) diff --git a/tests/fate/vcodec.mak b/tests/fate/vcodec.mak index a51f16c..97beb15 100644 --- a/tests/fate/vcodec.mak +++ b/tests/fate/vcodec.mak @@ -213,11 +213,13 @@ fate-vsynth%-jpeg2000-97: DECINOPTS = -vcodec jpeg2000 FATE_VCODEC-$(call ENCDEC, LJPEG MJPEG, AVI) += ljpeg fate-vsynth%-ljpeg: ENCOPTS = -strict -1 -FATE_VCODEC-$(call ENCDEC, MJPEG, AVI) += mjpeg mjpeg-422 mjpeg-444 mjpeg-trell +FATE_VCODEC-$(call ENCDEC, MJPEG, AVI) += mjpeg mjpeg-422 mjpeg-444 mjpeg-trell mjpeg-huffman mjpeg-trell-huffman fate-vsynth%-mjpeg: ENCOPTS = -qscale 9 -pix_fmt yuvj420p fate-vsynth%-mjpeg-422: ENCOPTS = -qscale 9 -pix_fmt yuvj422p fate-vsynth%-mjpeg-444: ENCOPTS = -qscale 9 -pix_fmt yuvj444p fate-vsynth%-mjpeg-trell: ENCOPTS = -qscale 9 -pix_fmt yuvj420p -trellis 1 +fate-vsynth%-mjpeg-huffman: ENCOPTS = -qscale 9 -pix_fmt yuvj420p -huffman optimal +fate-vsynth%-mjpeg-trell-huffman:ENCOPTS = -qscale 9 -pix_fmt yuvj420p -trellis 1 -huffman optimal FATE_VCODEC-$(call ENCDEC, MPEG1VIDEO, MPEG1VIDEO MPEGVIDEO) += mpeg1 mpeg1b fate-vsynth%-mpeg1: FMT = mpeg1video diff --git a/tests/ref/vsynth/vsynth1-mjpeg-huffman b/tests/ref/vsynth/vsynth1-mjpeg-huffman new file mode 100644 index 0000000..e8c3f0f --- /dev/null +++ b/tests/ref/vsynth/vsynth1-mjpeg-huffman @@ -0,0 +1,4 @@ +63ea9bd494e16bad8f3a0c8dbb3dc11e *tests/data/fate/vsynth1-mjpeg-huffman.avi +1391380 tests/data/fate/vsynth1-mjpeg-huffman.avi +9a3b8169c251d19044f7087a95458c55 *tests/data/fate/vsynth1-mjpeg -huffman.out.rawvideo +stddev: 7.87 PSNR: 30.21 MAXDIFF: 63 bytes: 7603200/ 7603200 diff --git a/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman new file mode 100644 index 0000000..20ce783 --- /dev/null +++ b/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman @@ -0,0 +1,4 @@ +d9410fa80c07edbd2a2b44ceb06086ca *tests/data/fate/vsynth1-mjpeg -trell-huffman.avi +1360456 tests/data/fate/vsynth1-mjpeg-trell-huffman.avi +0266b223bdd7928426a951164bb4a366 *tests/data/fate/vsynth1-mjpeg -trell-huffman.out.rawvideo +stddev: 7.68 PSNR: 30.42 MAXDIFF: 62 bytes: 7603200/ 7603200 diff --git a/tests/ref/vsynth/vsynth2-mjpeg-huffman b/tests/ref/vsynth/vsynth2-mjpeg-huffman new file mode 100644 index 0000000..0cf998b --- /dev/null +++ b/tests/ref/vsynth/vsynth2-mjpeg-huffman @@ -0,0 +1,4 @@ +9bf00cd3188b7395b798bb10df376243 *tests/data/fate/vsynth2-mjpeg-huffman.avi +792742 tests/data/fate/vsynth2-mjpeg-huffman.avi +2b8c59c59e33d6ca7c85d31c5eeab7be *tests/data/fate/vsynth2-mjpeg -huffman.out.rawvideo +stddev: 4.87 PSNR: 34.37 MAXDIFF: 55 bytes: 7603200/ 7603200 diff --git a/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman new file mode 100644 index 0000000..3686740 --- /dev/null +++ b/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman @@ -0,0 +1,4 @@ +a59d99d31d24875161504820d4266e4d *tests/data/fate/vsynth2-mjpeg -trell-huffman.avi +734728 tests/data/fate/vsynth2-mjpeg-trell-huffman.avi +42376126213c73c86b408882e24ba015 *tests/data/fate/vsynth2-mjpeg -trell-huffman.out.rawvideo +stddev: 5.03 PSNR: 34.09 MAXDIFF: 67 bytes: 7603200/ 7603200 diff --git a/tests/ref/vsynth/vsynth3-mjpeg-huffman b/tests/ref/vsynth/vsynth3-mjpeg-huffman new file mode 100644 index 0000000..634a1a5 --- /dev/null +++ b/tests/ref/vsynth/vsynth3-mjpeg-huffman @@ -0,0 +1,4 @@ +eec435352485fec167179a63405505be *tests/data/fate/vsynth3-mjpeg-huffman.avi +48156 tests/data/fate/vsynth3-mjpeg-huffman.avi +c4fe7a2669afbd96c640748693fc4e30 *tests/data/fate/vsynth3-mjpeg -huffman.out.rawvideo +stddev: 8.60 PSNR: 29.43 MAXDIFF: 58 bytes: 86700/ 86700 diff --git a/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman new file mode 100644 index 0000000..719029f --- /dev/null +++ b/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman @@ -0,0 +1,4 @@ +484fa337b71c06a0206243814c4894b0 *tests/data/fate/vsynth3-mjpeg -trell-huffman.avi +47816 tests/data/fate/vsynth3-mjpeg-trell-huffman.avi +f0ccfe4584d193fd6d690a85a70db188 *tests/data/fate/vsynth3-mjpeg -trell-huffman.out.rawvideo +stddev: 8.27 PSNR: 29.78 MAXDIFF: 55 bytes: 86700/ 86700