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. |
34 |
|
3 |
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 |
|
3 |
int actual_length = 0, i, j, k, prob, length; |
40 |
|
3 |
int ret = 0; |
41 |
|
3 |
double cantor_measure = 0; |
42 |
✗✓ |
3 |
av_assert0(nprobs <= 256); |
43 |
|
|
|
44 |
✓✓ |
520 |
for (i = 0; i < nprobs; i++) { |
45 |
|
517 |
val_counts[i] = (PTable){.value = i, .prob = probs[i]}; |
46 |
|
|
} |
47 |
|
|
|
48 |
|
3 |
ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L); |
49 |
|
|
|
50 |
✓✓ |
520 |
for (i = 0; i < nprobs; i++) { |
51 |
|
|
// Find the value's prob and length |
52 |
✓✗ |
65807 |
for (j = 0; j < nprobs; j++) |
53 |
✓✓ |
65807 |
if (val_counts[j].value == i) break; |
54 |
✓✗ |
65807 |
for (k = 0; k < nprobs; k++) |
55 |
✓✓ |
65807 |
if (lengths[k].code == i) break; |
56 |
✓✗✗✓
|
517 |
if (!(j < nprobs && k < nprobs)) return 1; |
57 |
|
517 |
prob = val_counts[j].prob; |
58 |
|
517 |
length = lengths[k].length; |
59 |
|
|
|
60 |
✓✓ |
517 |
if (prob) { |
61 |
|
340 |
actual_length += prob * length; |
62 |
|
340 |
cantor_measure += 1. / (1 << length); |
63 |
|
|
} |
64 |
|
|
|
65 |
✓✗✗✓
|
517 |
if (length > L || length < 1) return 1; |
66 |
|
|
} |
67 |
|
|
// Check that the codes can be prefix-free. |
68 |
✗✓ |
3 |
if (cantor_measure > 1) ret = 1; |
69 |
|
|
// Check that the total length is optimal |
70 |
✗✓ |
3 |
if (actual_length != expected_length) ret = 1; |
71 |
|
|
|
72 |
✗✓ |
3 |
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 |
|
3 |
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/ |
116 |
|
1 |
int main(int argc, char **argv) |
117 |
|
|
{ |
118 |
|
1 |
int i, ret = 0; |
119 |
|
|
// Probabilities of symbols 0..4 |
120 |
|
1 |
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 |
|
1 |
ff_mjpegenc_huffman_compute_bits(val_counts, distincts, |
141 |
|
|
FF_ARRAY_ELEMS(distincts), 3); |
142 |
|
|
|
143 |
✓✓ |
6 |
for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) { |
144 |
✓✗ |
5 |
if (distincts[i].code != expected[i].code || |
145 |
✗✓ |
5 |
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 |
✗✓ |
1 |
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 |
✗✓ |
1 |
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 |
✗✓ |
1 |
if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat))) |
164 |
|
|
ret = 1; |
165 |
|
|
|
166 |
|
1 |
return ret; |
167 |
|
|
} |