FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/tests/mjpegenc_huffman.c
Date: 2025-04-25 22:50:00
Exec Total Coverage
Lines: 42 64 65.6%
Functions: 2 2 100.0%
Branches: 33 48 68.8%
Line Branch Exec Source
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 <stdio.h>
27
28 #include "libavutil/avassert.h"
29 #include "libavutil/macros.h"
30
31 #include "libavcodec/mjpegenc_huffman.c"
32
33 // Validate the computed lengths satisfy the JPEG restrictions and is optimal.
34 3 static int check_lengths(int L, const int *probs, int nprobs,
35 int expected_length, const uint8_t expected_len_counts[/* L + 1 */])
36 {
37 PTable val_counts[256];
38 uint8_t len_counts[17];
39 3 int actual_length = 0, i;
40 3 int ret = 0;
41
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 av_assert0(nprobs <= 256);
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 av_assert0(L < FF_ARRAY_ELEMS(len_counts));
43
44
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 3 times.
 520 for (i = 0; i < nprobs; i++) {
45 517 val_counts[i] = (PTable){.value = i, .prob = probs[i]};
46 }
47
48 3 mjpegenc_huffman_compute_bits(val_counts, len_counts, nprobs, L);
49
50 // Test that the lengths can be made part of a complete, prefix-free tree:
51 3 unsigned code = 0, count = 0;
52
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 3 times.
 51 for (int i = 1; i <= L; ++i) {
53 48 count += len_counts[i];
54 48 code <<= 1;
55 48 code += len_counts[i];
56 }
57
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (code > 1U << L) {
58 ✗ fprintf(stderr, "Huffman tree overdetermined/invalid\n");
59 ✗ ret = 1;
60 }
61
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (count != nprobs) {
62 ✗ fprintf(stderr, "Total count %u does not match expected value %d\n",
63 count, nprobs);
64 ✗ ret = 1;
65 }
66 // Test that the input values have been properly ordered.
67
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 3 times.
 520 for (unsigned i = 0; i < count; ++i) {
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 517 times.
 517 if (val_counts[i].prob != probs[val_counts[i].value]) {
69 ✗ fprintf(stderr, "PTable not properly reordered\n");
70 ✗ ret = 1;
71 }
72
3/4
✓ Branch 0 taken 514 times.
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 514 times.
 517 if (i && val_counts[i - 1].prob > val_counts[i].prob) {
73 ✗ fprintf(stderr, "PTable not order ascendingly: [%u] = %d > [%u] = %d\n",
74 ✗ i - 1, val_counts[i - 1].prob, i, val_counts[i].prob);
75 ✗ ret = 1;
76 }
77 unsigned j;
78
1/2
✓ Branch 0 taken 65807 times.
✗ Branch 1 not taken.
 65807 for (j = 0; j < count; ++j)
79
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 65290 times.
 65807 if (val_counts[j].value == i)
80 517 break;
81
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 517 times.
 517 if (j >= count) {
82 ✗ fprintf(stderr, "Element %u missing after sorting\n", i);
83 ✗ ret = 1;
84 }
85 }
86
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 3 times.
 51 for (int len = L, j = 0; len; --len) {
87 48 int prob = 0;
88
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 48 times.
 565 for (int end = j + len_counts[len]; j < end; ++j)
89 517 prob += val_counts[j].prob;
90 48 actual_length += prob * len;
91 }
92 // Check that the total length is optimal
93
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (actual_length != expected_length) ret = 1;
94
95
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (ret == 1) {
96 ✗ fprintf(stderr,
97 "Actual length: %d\n"
98 "Expected length: %d\n",
99 actual_length, expected_length);
100 }
101
102 3 return ret;
103 }
104
105 static const int probs_zeroes[] = {
106 6, 6, 0, 0, 0
107 };
108 static const uint8_t len_counts_zeroes[] = {
109 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,
110 };
111
112 static const int probs_skewed[] = {
113 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,
114 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,
115 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,
116 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,
117 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,
118 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,
119 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,
120 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,
121 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,
122 0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5
123 };
124 static const uint8_t len_counts_skewed[] = {
125 0, 1, 0, 0, 1, 2, 7, 11, 18, 31, 28, 40, 0, 1, 0, 0, 116,
126 };
127
128 static const int probs_sat[] = {
129 74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121,
130 1, 1583, 0, 16, 21, 2, 132, 2, 15, 9, 13, 1, 0, 2293, 2, 8, 5, 2, 30, 0, 0, 4, 54,
131 783, 4, 1, 2, 4, 0, 22, 93, 1, 143, 19, 0, 36, 32, 4, 6, 33, 3, 45, 0, 8, 1, 0, 18,
132 17, 1, 0, 1, 0, 0, 1, 1004, 38, 3, 8, 90, 23, 0, 2819, 3, 0, 970, 158, 9, 6, 4, 48,
133 4, 0, 1, 0, 0, 60, 3, 62, 0, 2, 2, 2, 279, 66, 16, 1, 20, 0, 7, 9, 32, 1411, 6, 3,
134 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,
135 18, 5, 8, 200, 4, 4, 22, 12, 0, 4, 1, 0, 2, 4, 9, 3, 16, 7, 2, 2, 213, 0, 2, 620,
136 39303, 0, 1, 0, 2, 1, 183781, 1, 0, 0, 0, 94, 7, 3, 4, 0, 4, 306, 43, 352, 76, 34,
137 13, 11, 0, 51, 1, 13, 19, 0, 26, 0, 7276, 4, 207, 31, 1, 2, 4, 6, 19, 8, 17, 4, 6,
138 0, 1085, 0, 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2,
139 2, 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1
140 };
141 static const uint8_t len_counts_sat[] = {
142 0, 1, 0, 2, 1, 2, 2, 5, 5, 7, 7, 8, 17, 23, 16, 24, 136,
143 };
144
145 // Test the example given on @see
146 // http://guru.multimedia.cx/small-tasks-for-ffmpeg/
147 1 int main(int argc, char **argv)
148 {
149 enum {
150 MAX_LEN = 3,
151 };
152 1 int ret = 0;
153 // Probabilities of symbols 0..4
154 1 PTable val_counts[] = {
155 {.value = 0, .prob = 1},
156 {.value = 1, .prob = 2},
157 {.value = 2, .prob = 5},
158 {.value = 3, .prob = 10},
159 {.value = 4, .prob = 21},
160 };
161 // Expected code lengths for each symbol
162 static const uint8_t expected[MAX_LEN + 1] = {
163 [1] = 1, [3] = 4,
164 };
165 // Actual code lengths
166 uint8_t len_counts[MAX_LEN + 1];
167
168 // Build optimal huffman tree using an internal function, to allow for
169 // smaller-than-normal test cases. This mutates val_counts by sorting.
170 1 mjpegenc_huffman_compute_bits(val_counts, len_counts,
171 FF_ARRAY_ELEMS(val_counts), MAX_LEN);
172
173
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 for (unsigned i = 1; i < FF_ARRAY_ELEMS(len_counts); i++) {
174
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (len_counts[i] != expected[i]) {
175 ✗ fprintf(stderr,
176 "Built huffman does not equal expectations. "
177 "Expected: %d codes of length %u, "
178 "Actual: %d codes of length %u\n",
179 ✗ (int)expected[i], i,
180 ✗ (int)len_counts[i], i);
181 ✗ ret = 1;
182 }
183 }
184
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 5 for (unsigned i = 1; i < FF_ARRAY_ELEMS(val_counts); ++i) {
185
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (val_counts[i - 1].prob > val_counts[i].prob) {
186 ✗ fprintf(stderr, "Probability table not ordered ascendingly. "
187 "val_counts[%u] == %d, val_counts[%u] == %d\n",
188 ✗ i - 1, val_counts[i - 1].prob, i, val_counts[i].prob);
189 ✗ ret = 1;
190 }
191 }
192
193 // Check handling of zero probabilities
194
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if (check_lengths(16, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes), 18, len_counts_zeroes))
195 ✗ ret = 1;
196 // Check skewed distribution over 256 without saturated lengths
197
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if (check_lengths(16, probs_skewed, FF_ARRAY_ELEMS(probs_skewed), 41282, len_counts_skewed))
198 ✗ ret = 1;
199 // Check skewed distribution over 256 with saturated lengths
200
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if (check_lengths(16, probs_sat, FF_ARRAY_ELEMS(probs_sat), 669904, len_counts_sat))
201 ✗ ret = 1;
202
203 1 return ret;
204 }
205