FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/tests/mjpegenc_huffman.c
Date: 2024-04-19 17:50:32
Exec Total Coverage
Lines: 35 42 83.3%
Functions: 2 2 100.0%
Branches: 27 42 64.3%
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 "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
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 av_assert0(nprobs <= 256);
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 ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
49
50
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 3 times.
 520 for (i = 0; i < nprobs; i++) {
51 // Find the value's prob and length
52
1/2
✓ Branch 0 taken 65807 times.
✗ Branch 1 not taken.
 65807 for (j = 0; j < nprobs; j++)
53
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 65290 times.
 65807 if (val_counts[j].value == i) break;
54
1/2
✓ Branch 0 taken 65807 times.
✗ Branch 1 not taken.
 65807 for (k = 0; k < nprobs; k++)
55
2/2
✓ Branch 0 taken 517 times.
✓ Branch 1 taken 65290 times.
 65807 if (lengths[k].code == i) break;
56
2/4
✓ Branch 0 taken 517 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 517 times.
 517 if (!(j < nprobs && k < nprobs)) return 1;
57 517 prob = val_counts[j].prob;
58 517 length = lengths[k].length;
59
60
2/2
✓ Branch 0 taken 340 times.
✓ Branch 1 taken 177 times.
 517 if (prob) {
61 340 actual_length += prob * length;
62 340 cantor_measure += 1. / (1 << length);
63 }
64
65
2/4
✓ Branch 0 taken 517 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 517 times.
 517 if (length > L || length < 1) return 1;
66 }
67 // Check that the codes can be prefix-free.
68
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (cantor_measure > 1) ret = 1;
69 // Check that the total length is optimal
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (actual_length != expected_length) ret = 1;
71
72
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 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
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
144
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (distincts[i].code != expected[i].code ||
145
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 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/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 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/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 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/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 1 if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
164 ✗ ret = 1;
165
166 1 return ret;
167 }
168