2 * Copyright (c) 2016 William Ma, Sofia Kim, Dustin Woo
4 * This file is part of FFmpeg.
6 * FFmpeg is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * FFmpeg is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with FFmpeg; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 * Optimal Huffman Encoding tests.
26 #include "libavcodec/avcodec.h"
28 #include "libavcodec/mjpegenc.h"
29 #include "libavcodec/mjpegenc_huffman.h"
30 #include "libavcodec/mjpegenc_common.h"
31 #include "libavcodec/mpegvideo.h"
33 // Validate the computed lengths satisfy the JPEG restrictions and is optimal.
34 static int check_lengths(int L, int expected_length,
35 const int *probs, int nprobs)
37 HuffTable lengths[256];
38 PTable val_counts[256];
39 int actual_length = 0, i, j, k, prob, length;
41 double cantor_measure = 0;
42 av_assert0(nprobs <= 256);
44 for (i = 0; i < nprobs; i++) {
45 val_counts[i] = (PTable){.value = i, .prob = probs[i]};
48 ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
50 for (i = 0; i < nprobs; i++) {
51 // Find the value's prob and length
52 for (j = 0; j < nprobs; j++)
53 if (val_counts[j].value == i) break;
54 for (k = 0; k < nprobs; k++)
55 if (lengths[k].code == i) break;
56 if (!(j < nprobs && k < nprobs)) return 1;
57 prob = val_counts[j].prob;
58 length = lengths[k].length;
61 actual_length += prob * length;
62 cantor_measure += 1. / (1 << length);
65 if (length > L || length < 1) return 1;
67 // Check that the codes can be prefix-free.
68 if (cantor_measure > 1) ret = 1;
69 // Check that the total length is optimal
70 if (actual_length != expected_length) ret = 1;
74 "Cantor measure: %f\n"
76 "Expected length: %d\n",
77 cantor_measure, actual_length, expected_length);
83 static const int probs_zeroes[] = {
87 static const int probs_skewed[] = {
88 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,
89 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,
90 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,
91 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,
92 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,
93 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,
94 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,
95 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,
96 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,
97 0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5
100 static const int probs_sat[] = {
101 74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121,
102 1, 1583, 0, 16, 21, 2, 132, 2, 15, 9, 13, 1, 0, 2293, 2, 8, 5, 2, 30, 0, 0, 4, 54,
103 783, 4, 1, 2, 4, 0, 22, 93, 1, 143, 19, 0, 36, 32, 4, 6, 33, 3, 45, 0, 8, 1, 0, 18,
104 17, 1, 0, 1, 0, 0, 1, 1004, 38, 3, 8, 90, 23, 0, 2819, 3, 0, 970, 158, 9, 6, 4, 48,
105 4, 0, 1, 0, 0, 60, 3, 62, 0, 2, 2, 2, 279, 66, 16, 1, 20, 0, 7, 9, 32, 1411, 6, 3,
106 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,
107 18, 5, 8, 200, 4, 4, 22, 12, 0, 4, 1, 0, 2, 4, 9, 3, 16, 7, 2, 2, 213, 0, 2, 620,
108 39303, 0, 1, 0, 2, 1, 183781, 1, 0, 0, 0, 94, 7, 3, 4, 0, 4, 306, 43, 352, 76, 34,
109 13, 11, 0, 51, 1, 13, 19, 0, 26, 0, 7276, 4, 207, 31, 1, 2, 4, 6, 19, 8, 17, 4, 6,
110 0, 1085, 0, 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2,
111 2, 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1
114 // Test the example given on @see
115 // http://guru.multimedia.cx/small-tasks-for-ffmpeg/
116 int main(int argc, char **argv)
119 // Probabilities of symbols 0..4
120 PTable val_counts[] = {
121 {.value = 0, .prob = 1},
122 {.value = 1, .prob = 2},
123 {.value = 2, .prob = 5},
124 {.value = 3, .prob = 10},
125 {.value = 4, .prob = 21},
127 // Expected code lengths for each symbol
128 static const HuffTable expected[] = {
129 {.code = 0, .length = 3},
130 {.code = 1, .length = 3},
131 {.code = 2, .length = 3},
132 {.code = 3, .length = 3},
133 {.code = 4, .length = 1},
135 // Actual code lengths
136 HuffTable distincts[5];
138 // Build optimal huffman tree using an internal function, to allow for
139 // smaller-than-normal test cases. This mutates val_counts by sorting.
140 ff_mjpegenc_huffman_compute_bits(val_counts, distincts,
141 FF_ARRAY_ELEMS(distincts), 3);
143 for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
144 if (distincts[i].code != expected[i].code ||
145 distincts[i].length != expected[i].length) {
147 "Built huffman does not equal expectations. "
148 "Expected: code %d probability %d, "
149 "Actual: code %d probability %d\n",
150 expected[i].code, expected[i].length,
151 distincts[i].code, distincts[i].length);
156 // Check handling of zero probabilities
157 if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
159 // Check skewed distribution over 256 without saturated lengths
160 if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
162 // Check skewed distribution over 256 with saturated lengths
163 if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))