1 /*
2 * Copyright (c) 2016 William Ma, Sofia Kim, Dustin Woo
3 *
4 * This file is part of FFmpeg.
5 *
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.
10 *
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.
15 *
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
19 */
20
21 /**
22 * @file
23 * Optimal Huffman Encoding tests.
24 */
25
26 #include "libavcodec/avcodec.h"
27 #include <stdlib.h>
28 #include "libavcodec/mjpegenc.h"
29 #include "libavcodec/mjpegenc_huffman.h"
30 #include "libavcodec/mjpegenc_common.h"
31 #include "libavcodec/mpegvideo.h"
32
33 // Validate the computed lengths satisfy the JPEG restrictions and is optimal.
check_lengths(int L,int expected_length,const int * probs,int nprobs)34 static int check_lengths(int L, int expected_length,
35 const int *probs, int nprobs)
36 {
37 HuffTable lengths[256];
38 PTable val_counts[256];
39 int actual_length = 0, i, j, k, prob, length;
40 int ret = 0;
41 double cantor_measure = 0;
42 av_assert0(nprobs <= 256);
43
44 for (i = 0; i < nprobs; i++) {
45 val_counts[i] = (PTable){.value = i, .prob = probs[i]};
46 }
47
48 ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
49
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;
59
60 if (prob) {
61 actual_length += prob * length;
62 cantor_measure += 1. / (1 << length);
63 }
64
65 if (length > L || length < 1) return 1;
66 }
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;
71
72 if (ret == 1) {
73 fprintf(stderr,
74 "Cantor measure: %f\n"
75 "Actual length: %d\n"
76 "Expected length: %d\n",
77 cantor_measure, actual_length, expected_length);
78 }
79
80 return ret;
81 }
82
83 static const int probs_zeroes[] = {
84 6, 6, 0, 0, 0
85 };
86
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
98 };
99
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
112 };
113
114 // Test the example given on @see
115 // http://guru.multimedia.cx/small-tasks-for-ffmpeg/
main(int argc,char ** argv)116 int main(int argc, char **argv)
117 {
118 int i, ret = 0;
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},
126 };
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},
134 };
135 // Actual code lengths
136 HuffTable distincts[5];
137
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);
142
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) {
146 fprintf(stderr,
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);
152 ret = 1;
153 }
154 }
155
156 // Check handling of zero probabilities
157 if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
158 ret = 1;
159 // Check skewed distribution over 256 without saturated lengths
160 if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
161 ret = 1;
162 // Check skewed distribution over 256 with saturated lengths
163 if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
164 ret = 1;
165
166 return ret;
167 }
168