FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/mjpegenc_huffman.c
Date: 2025-01-20 09:27:23
Exec Total Coverage
Lines: 75 75 100.0%
Functions: 5 5 100.0%
Branches: 123 126 97.6%
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 * Comparison function for two PTables by prob
30 *
31 * @param a First PTable to compare
32 * @param b Second PTable to compare
33 * @return < 0 for less than, 0 for equals, > 0 for greater than
34 */
35 482253 static int compare_by_prob(const void *a, const void *b)
36 {
37 482253 PTable a_val = *(PTable *) a;
38 482253 PTable b_val = *(PTable *) b;
39 482253 return a_val.prob - b_val.prob;
40 }
41
42 /**
43 * Comparison function for two HuffTables by length
44 *
45 * @param a First HuffTable to compare
46 * @param b Second HuffTable to compare
47 * @return < 0 for less than, 0 for equals, > 0 for greater than
48 */
49 436846 static int compare_by_length(const void *a, const void *b)
50 {
51 436846 HuffTable a_val = *(HuffTable *) a;
52 436846 HuffTable b_val = *(HuffTable *) b;
53 436846 return a_val.length - b_val.length;
54 }
55
56 /**
57 * Computes the length of the Huffman encoding for each distinct input value.
58 * Uses package merge algorithm as follows:
59 * 1. start with an empty list, lets call it list(0), set i = 0
60 * 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
61 * 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
62 * 4. if there is more than 1 symbol left in the current list(i), then goto 3
63 * 5. i++
64 * 6. if i < 16 goto 2
65 * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
66 * 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
67 * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
68 *
69 * All probabilities should be positive integers. The output is sorted by code,
70 * not by length.
71 *
72 * @param prob_table input array of a PTable for each distinct input value
73 * @param distincts output array of a HuffTable that will be populated by this function
74 * @param size size of the prob_table array
75 * @param max_length max length of an encoding
76 */
77 4960 void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
78 {
79 4960 PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
80
81 int times, i, j, k;
82
83 4960 int nbits[257] = {0};
84
85 int min;
86
87
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4960 times.
 4960 av_assert0(max_length > 0);
88
89 4960 to->nitems = 0;
90 4960 from->nitems = 0;
91 4960 to->item_idx[0] = 0;
92 4960 from->item_idx[0] = 0;
93
44/44
✓ Branch 0 taken 43419 times.
✓ Branch 1 taken 15273 times.
✓ Branch 3 taken 18497 times.
✓ Branch 4 taken 24922 times.
✓ Branch 6 taken 3996 times.
✓ Branch 7 taken 14501 times.
✓ Branch 9 taken 5235 times.
✓ Branch 10 taken 19687 times.
✓ Branch 12 taken 19656 times.
✓ Branch 13 taken 23763 times.
✓ Branch 14 taken 8533 times.
✓ Branch 15 taken 34886 times.
✓ Branch 16 taken 161382 times.
✓ Branch 17 taken 9771 times.
✓ Branch 19 taken 82425 times.
✓ Branch 20 taken 78957 times.
✓ Branch 21 taken 155681 times.
✓ Branch 22 taken 25513 times.
✓ Branch 24 taken 92466 times.
✓ Branch 25 taken 63215 times.
✓ Branch 26 taken 25513 times.
✓ Branch 27 taken 63215 times.
✓ Branch 28 taken 88728 times.
✓ Branch 29 taken 34886 times.
✓ Branch 30 taken 8894 times.
✓ Branch 31 taken 25992 times.
✓ Branch 32 taken 6135 times.
✓ Branch 33 taken 2759 times.
✓ Branch 34 taken 2747 times.
✓ Branch 35 taken 3388 times.
✓ Branch 36 taken 19660 times.
✓ Branch 37 taken 2370 times.
✓ Branch 39 taken 16524 times.
✓ Branch 40 taken 3136 times.
✓ Branch 41 taken 2370 times.
✓ Branch 42 taken 3136 times.
✓ Branch 43 taken 14055 times.
✓ Branch 44 taken 18461 times.
✓ Branch 46 taken 5935 times.
✓ Branch 47 taken 9338 times.
✓ Branch 48 taken 58692 times.
✓ Branch 49 taken 11300 times.
✓ Branch 50 taken 37476 times.
✓ Branch 51 taken 4960 times.
 389981 AV_QSORT(prob_table, size, PTable, compare_by_prob);
94
95
2/2
✓ Branch 0 taken 84307 times.
✓ Branch 1 taken 4960 times.
 89267 for (times = 0; times <= max_length; times++) {
96 84307 to->nitems = 0;
97 84307 to->item_idx[0] = 0;
98
99 84307 j = 0;
100 84307 k = 0;
101
102
2/2
✓ Branch 0 taken 79347 times.
✓ Branch 1 taken 4960 times.
 84307 if (times < max_length) {
103 79347 i = 0;
104 }
105
4/4
✓ Branch 0 taken 3151411 times.
✓ Branch 1 taken 442911 times.
✓ Branch 2 taken 358604 times.
✓ Branch 3 taken 84307 times.
 3594322 while (i < size || j + 1 < from->nitems) {
106 3510015 to->nitems++;
107 3510015 to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
108
2/2
✓ Branch 0 taken 3151411 times.
✓ Branch 1 taken 358604 times.
 3510015 if (i < size &&
109
2/2
✓ Branch 0 taken 3035468 times.
✓ Branch 1 taken 115943 times.
 3151411 (j + 1 >= from->nitems ||
110 3035468 prob_table[i].prob <
111
2/2
✓ Branch 0 taken 1727464 times.
✓ Branch 1 taken 1308004 times.
 3035468 from->probability[j] + from->probability[j + 1])) {
112 1843407 to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
113 1843407 to->probability[to->nitems - 1] = prob_table[i].prob;
114 1843407 i++;
115 } else {
116
2/2
✓ Branch 0 taken 10186475 times.
✓ Branch 1 taken 1666608 times.
 11853083 for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
117 10186475 to->items[to->item_idx[to->nitems]++] = from->items[k];
118 }
119 1666608 to->probability[to->nitems - 1] =
120 1666608 from->probability[j] + from->probability[j + 1];
121 1666608 j += 2;
122 }
123 }
124 84307 temp = to;
125 84307 to = from;
126 84307 from = temp;
127 }
128
129
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4960 times.
 4960 min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
130
2/2
✓ Branch 0 taken 859609 times.
✓ Branch 1 taken 4960 times.
 864569 for (i = 0; i < from->item_idx[min]; i++) {
131 859609 nbits[from->items[i]]++;
132 }
133 // we don't want to return the 256 bit count (it was just in here to prevent
134 // all 1s encoding)
135 4960 j = 0;
136
2/2
✓ Branch 0 taken 1269760 times.
✓ Branch 1 taken 4960 times.
 1274720 for (i = 0; i < 256; i++) {
137
2/2
✓ Branch 0 taken 110261 times.
✓ Branch 1 taken 1159499 times.
 1269760 if (nbits[i] > 0) {
138 110261 distincts[j].code = i;
139 110261 distincts[j].length = nbits[i];
140 110261 j++;
141 }
142 }
143 4960 }
144
145 4956 void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
146 {
147 4956 memset(s->val_count, 0, sizeof(s->val_count));
148 4956 }
149
150 /**
151 * Produces a Huffman encoding with a given input
152 *
153 * @param s input to encode
154 * @param bits output array where the ith character represents how many input values have i length encoding
155 * @param val output array of input values sorted by their encoded length
156 * @param max_nval maximum number of distinct input values
157 */
158 4956 void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
159 uint8_t val[], int max_nval)
160 {
161 int i, j;
162 4956 int nval = 0;
163 PTable val_counts[257];
164 HuffTable distincts[256];
165
166
2/2
✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.
 1273692 for (i = 0; i < 256; i++) {
167
2/2
✓ Branch 0 taken 109739 times.
✓ Branch 1 taken 1158997 times.
 1268736 if (s->val_count[i]) nval++;
168 }
169
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.
 4956 av_assert0 (nval <= max_nval);
170
171 4956 j = 0;
172
2/2
✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.
 1273692 for (i = 0; i < 256; i++) {
173
2/2
✓ Branch 0 taken 109739 times.
✓ Branch 1 taken 1158997 times.
 1268736 if (s->val_count[i]) {
174 109739 val_counts[j].value = i;
175 109739 val_counts[j].prob = s->val_count[i];
176 109739 j++;
177 }
178 }
179 4956 val_counts[j].value = 256;
180 4956 val_counts[j].prob = 0;
181 4956 ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
182
44/44
✓ Branch 0 taken 40995 times.
✓ Branch 1 taken 10879 times.
✓ Branch 3 taken 10486 times.
✓ Branch 4 taken 30509 times.
✓ Branch 6 taken 1553 times.
✓ Branch 7 taken 8933 times.
✓ Branch 9 taken 6717 times.
✓ Branch 10 taken 23792 times.
✓ Branch 12 taken 9589 times.
✓ Branch 13 taken 31406 times.
✓ Branch 14 taken 9420 times.
✓ Branch 15 taken 31575 times.
✓ Branch 16 taken 152014 times.
✓ Branch 17 taken 7360 times.
✓ Branch 19 taken 85439 times.
✓ Branch 20 taken 66575 times.
✓ Branch 21 taken 128149 times.
✓ Branch 22 taken 16046 times.
✓ Branch 24 taken 70260 times.
✓ Branch 25 taken 57889 times.
✓ Branch 26 taken 16046 times.
✓ Branch 27 taken 57889 times.
✓ Branch 28 taken 73935 times.
✓ Branch 29 taken 31575 times.
✓ Branch 30 taken 13063 times.
✓ Branch 31 taken 18512 times.
✓ Branch 32 taken 9070 times.
✓ Branch 33 taken 3993 times.
✓ Branch 34 taken 3607 times.
✓ Branch 35 taken 5463 times.
✓ Branch 36 taken 22819 times.
✓ Branch 37 taken 3009 times.
✓ Branch 39 taken 18228 times.
✓ Branch 40 taken 4591 times.
✓ Branch 41 taken 3009 times.
✓ Branch 42 taken 4591 times.
✓ Branch 43 taken 15230 times.
✓ Branch 44 taken 13336 times.
✓ Branch 46 taken 2994 times.
✓ Branch 47 taken 7885 times.
✓ Branch 48 taken 51874 times.
✓ Branch 49 taken 10214 times.
✓ Branch 50 taken 33522 times.
✓ Branch 51 taken 4956 times.
 346481 AV_QSORT(distincts, nval, HuffTable, compare_by_length);
183
184 4956 memset(bits, 0, sizeof(bits[0]) * 17);
185
2/2
✓ Branch 0 taken 109739 times.
✓ Branch 1 taken 4956 times.
 114695 for (i = 0; i < nval; i++) {
186 109739 val[i] = distincts[i].code;
187 109739 bits[distincts[i].length]++;
188 }
189 4956 }
190