FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/mjpegenc_huffman.c
Date: 2025-04-25 22:50:00
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 4 4 100.0%
Branches: 72 74 97.3%
Line Branch Exec Source
1 /*
2 * MJPEG encoder
3 * Copyright (c) 2016 William Ma, Ted Ying, Jerry Jiang
4 *
5 * This file is part of FFmpeg.
6 *
7 * FFmpeg is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * FFmpeg is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with FFmpeg; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22 #include <string.h>
23 #include <stdint.h>
24 #include "libavutil/avassert.h"
25 #include "libavutil/qsort.h"
26 #include "mjpegenc_huffman.h"
27
28 /**
29 * Used to assign a occurrence count or "probability" to an input value
30 */
31 typedef struct PTable {
32 int value; ///< input value
33 int prob; ///< number of occurences of this value in input
34 } PTable;
35
36 /**
37 * Used to store intermediate lists in the package merge algorithm
38 */
39 typedef struct PackageMergerList {
40 int nitems; ///< number of items in the list and probability ex. 4
41 int item_idx[515]; ///< index range for each item in items 0, 2, 5, 9, 13
42 int probability[514]; ///< probability of each item 3, 8, 18, 46
43 int items[257 * 16]; ///< chain of all individual values that make up items A, B, A, B, C, A, B, C, D, C, D, D, E
44 } PackageMergerList;
45
46 /**
47 * Comparison function for two PTables by prob
48 *
49 * @param a First PTable to compare
50 * @param b Second PTable to compare
51 * @return < 0 for less than, 0 for equals, > 0 for greater than
52 */
53 332812 static int compare_by_prob(const void *a, const void *b)
54 {
55 332812 PTable a_val = *(PTable *) a;
56 332812 PTable b_val = *(PTable *) b;
57 332812 return a_val.prob - b_val.prob;
58 }
59
60 /**
61 * Computes the length of the Huffman encoding for each distinct input value.
62 * Uses package merge algorithm as follows:
63 * 1. start with an empty list, lets call it list(0), set i = 0
64 * 2. add 1 entry to list(i) for each symbol we have and give each a score equal to the probability of the respective symbol
65 * 3. merge the 2 symbols of least score and put them in list(i+1), and remove them from list(i). The new score will be the sum of the 2 scores
66 * 4. if there is more than 1 symbol left in the current list(i), then goto 3
67 * 5. i++
68 * 6. if i < 16 goto 2
69 * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
70 * 8. the length of the huffman code for symbol s will be equal to the number of times the symbol occurs in the select elements
71 * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
72 *
73 * All probabilities should be nonnegative integers.
74 *
75 * @param prob_table[in,out] array of a PTable for each distinct input value,
76 * will be sorted according to ascending probability
77 * @param counts[out] the number of values of a given length
78 * @param size number of elements of the prob_table array
79 * @param max_length max length of a code
80 */
81 3360 static void mjpegenc_huffman_compute_bits(PTable *prob_table,
82 uint8_t counts[/* max_length + 1 */],
83 int size, int max_length)
84 {
85 3360 PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
86
87 int times, i, j, k;
88
89 3360 int nbits[257] = {0};
90
91 int min;
92
93
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3360 times.
 3360 av_assert0(max_length > 0);
94
95 3360 to->nitems = 0;
96 3360 from->nitems = 0;
97 3360 to->item_idx[0] = 0;
98 3360 from->item_idx[0] = 0;
99
44/44
✓ Branch 0 taken 29909 times.
✓ Branch 1 taken 10481 times.
✓ Branch 3 taken 12701 times.
✓ Branch 4 taken 17208 times.
✓ Branch 6 taken 2763 times.
✓ Branch 7 taken 9938 times.
✓ Branch 9 taken 3709 times.
✓ Branch 10 taken 13499 times.
✓ Branch 12 taken 13505 times.
✓ Branch 13 taken 16404 times.
✓ Branch 14 taken 5926 times.
✓ Branch 15 taken 23983 times.
✓ Branch 16 taken 111820 times.
✓ Branch 17 taken 6758 times.
✓ Branch 19 taken 57483 times.
✓ Branch 20 taken 54337 times.
✓ Branch 21 taken 107651 times.
✓ Branch 22 taken 17591 times.
✓ Branch 24 taken 64147 times.
✓ Branch 25 taken 43504 times.
✓ Branch 26 taken 17591 times.
✓ Branch 27 taken 43504 times.
✓ Branch 28 taken 61095 times.
✓ Branch 29 taken 23983 times.
✓ Branch 30 taken 6065 times.
✓ Branch 31 taken 17918 times.
✓ Branch 32 taken 4184 times.
✓ Branch 33 taken 1881 times.
✓ Branch 34 taken 1844 times.
✓ Branch 35 taken 2340 times.
✓ Branch 36 taken 13133 times.
✓ Branch 37 taken 1592 times.
✓ Branch 39 taken 11000 times.
✓ Branch 40 taken 2133 times.
✓ Branch 41 taken 1592 times.
✓ Branch 42 taken 2133 times.
✓ Branch 43 taken 9679 times.
✓ Branch 44 taken 12712 times.
✓ Branch 46 taken 4068 times.
✓ Branch 47 taken 6413 times.
✓ Branch 48 taken 40390 times.
✓ Branch 49 taken 7752 times.
✓ Branch 50 taken 25751 times.
✓ Branch 51 taken 3360 times.
 269210 AV_QSORT(prob_table, size, PTable, compare_by_prob);
100
101
2/2
✓ Branch 0 taken 57107 times.
✓ Branch 1 taken 3360 times.
 60467 for (times = 0; times <= max_length; times++) {
102 57107 to->nitems = 0;
103 57107 to->item_idx[0] = 0;
104
105 57107 j = 0;
106 57107 k = 0;
107
108
2/2
✓ Branch 0 taken 53747 times.
✓ Branch 1 taken 3360 times.
 57107 if (times < max_length) {
109 53747 i = 0;
110 }
111
4/4
✓ Branch 0 taken 2163484 times.
✓ Branch 1 taken 302520 times.
✓ Branch 2 taken 245413 times.
✓ Branch 3 taken 57107 times.
 2466004 while (i < size || j + 1 < from->nitems) {
112 2408897 to->nitems++;
113 2408897 to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
114
2/2
✓ Branch 0 taken 2163484 times.
✓ Branch 1 taken 245413 times.
 2408897 if (i < size &&
115
2/2
✓ Branch 0 taken 2083928 times.
✓ Branch 1 taken 79556 times.
 2163484 (j + 1 >= from->nitems ||
116 2083928 prob_table[i].prob <
117
2/2
✓ Branch 0 taken 1185275 times.
✓ Branch 1 taken 898653 times.
 2083928 from->probability[j] + from->probability[j + 1])) {
118 1264831 to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
119 1264831 to->probability[to->nitems - 1] = prob_table[i].prob;
120 1264831 i++;
121 } else {
122
2/2
✓ Branch 0 taken 7005287 times.
✓ Branch 1 taken 1144066 times.
 8149353 for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
123 7005287 to->items[to->item_idx[to->nitems]++] = from->items[k];
124 }
125 1144066 to->probability[to->nitems - 1] =
126 1144066 from->probability[j] + from->probability[j + 1];
127 1144066 j += 2;
128 }
129 }
130 57107 temp = to;
131 57107 to = from;
132 57107 from = temp;
133 }
134
135
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3360 times.
 3360 min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
136
2/2
✓ Branch 0 taken 591753 times.
✓ Branch 1 taken 3360 times.
 595113 for (i = 0; i < from->item_idx[min]; i++) {
137 591753 nbits[from->items[i]]++;
138 }
139 // we don't want to return the 256 bit count (it was just in here to prevent
140 // all 1s encoding)
141 3360 memset(counts, 0, sizeof(counts[0]) * (max_length + 1));
142
2/2
✓ Branch 0 taken 860160 times.
✓ Branch 1 taken 3360 times.
 863520 for (int i = 0; i < 256; ++i)
143 860160 counts[nbits[i]]++;
144 3360 }
145
146 3356 void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
147 {
148 3356 memset(s->val_count, 0, sizeof(s->val_count));
149 3356 }
150
151 /**
152 * Produces a Huffman encoding with a given input
153 *
154 * @param s input to encode
155 * @param bits output array where the ith character represents how many input values have i length encoding
156 * @param val output array of input values sorted by their encoded length
157 * @param max_nval maximum number of distinct input values
158 */
159 3356 void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
160 uint8_t val[], int max_nval)
161 {
162 PTable val_counts[257];
163
164 av_assert1(max_nval <= FF_ARRAY_ELEMS(val_counts) - 1);
165
166 3356 int nval = 0;
167
2/2
✓ Branch 0 taken 859136 times.
✓ Branch 1 taken 3356 times.
 862492 for (int i = 0; i < 256; i++) {
168
2/2
✓ Branch 0 taken 75178 times.
✓ Branch 1 taken 783958 times.
 859136 if (s->val_count[i]) {
169 75178 val_counts[nval].value = i;
170 75178 val_counts[nval].prob = s->val_count[i];
171 75178 nval++;
172 av_assert2(nval <= max_nval);
173 }
174 }
175 3356 val_counts[nval].value = 256;
176 3356 val_counts[nval].prob = 0;
177
178 3356 mjpegenc_huffman_compute_bits(val_counts, bits, nval + 1, 16);
179
180 // val_counts[0] is the fake element we added earlier.
181 av_assert1(val_counts[0].prob == 0 && val_counts[0].value == 256);
182 // The following loop puts the values with higher occurence first,
183 // ensuring that they get the shorter codes.
184
2/2
✓ Branch 0 taken 75178 times.
✓ Branch 1 taken 3356 times.
 78534 for (int i = 0; i < nval; ++i)
185 75178 val[i] = val_counts[nval - i].value;
186 3356 }
187