[FFmpeg-devel] [PATCH] Implement optimal huffman encoding for (M)JPEG.

Jerry Jiang jerryjiang1128 at gmail.com
Tue Dec 27 09:37:09 EET 2016


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

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(&current);
+        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 <string.h>
+#include <stdint.h>
+#include <assert.h>
+#include <stdlib.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 -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 <stdlib.h>
+#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 <a
+// href="http://guru.multimedia.cx/small-tasks-for-ffmpeg/">Small Tasks</a>
+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
--
2.10.2


More information about the ffmpeg-devel mailing list