FFmpeg coverage


Directory: ../../../ffmpeg/
File: src/libavcodec/mjpegenc_huffman.c
Date: 2021-09-22 05:58:22
Exec Total Coverage
Lines: 75 75 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 <stdlib.h>
25 #include "libavutil/avassert.h"
26 #include "libavutil/common.h"
27 #include "libavutil/error.h"
28 #include "libavutil/qsort.h"
29 #include "mjpegenc_huffman.h"
30
31 /**
32 * Comparison function for two PTables by prob
33 *
34 * @param a First PTable to compare
35 * @param b Second PTable to compare
36 * @return < 0 for less than, 0 for equals, > 0 for greater than
37 */
38 480909 static int compare_by_prob(const void *a, const void *b)
39 {
40 480909 PTable a_val = *(PTable *) a;
41 480909 PTable b_val = *(PTable *) b;
42 480909 return a_val.prob - b_val.prob;
43 }
44
45 /**
46 * Comparison function for two HuffTables by length
47 *
48 * @param a First HuffTable to compare
49 * @param b Second HuffTable to compare
50 * @return < 0 for less than, 0 for equals, > 0 for greater than
51 */
52 436310 static int compare_by_length(const void *a, const void *b)
53 {
54 436310 HuffTable a_val = *(HuffTable *) a;
55 436310 HuffTable b_val = *(HuffTable *) b;
56 436310 return a_val.length - b_val.length;
57 }
58
59 /**
60 * Computes the length of the Huffman encoding for each distinct input value.
61 * Uses package merge algorithm as follows:
62 * 1. start with an empty list, lets call it list(0), set i = 0
63 * 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
64 * 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
65 * 4. if there is more than 1 symbol left in the current list(i), then goto 3
66 * 5. i++
67 * 6. if i < 16 goto 2
68 * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
69 * 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
70 * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
71 *
72 * All probabilities should be positive integers. The output is sorted by code,
73 * not by length.
74 *
75 * @param prob_table input array of a PTable for each distinct input value
76 * @param distincts output array of a HuffTable that will be populated by this function
77 * @param size size of the prob_table array
78 * @param max_length max length of an encoding
79 */
80 4956 void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
81 {
82 4956 PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
83
84 int times, i, j, k;
85
86 4956 int nbits[257] = {0};
87
88 int min;
89
90
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.
4956 av_assert0(max_length > 0);
91
92 4956 to->nitems = 0;
93 4956 from->nitems = 0;
94 4956 to->item_idx[0] = 0;
95 4956 from->item_idx[0] = 0;
96
44/44
✓ Branch 0 taken 43354 times.
✓ Branch 1 taken 15199 times.
✓ Branch 3 taken 18450 times.
✓ Branch 4 taken 24904 times.
✓ Branch 6 taken 4082 times.
✓ Branch 7 taken 14368 times.
✓ Branch 9 taken 5325 times.
✓ Branch 10 taken 19579 times.
✓ Branch 12 taken 19645 times.
✓ Branch 13 taken 23709 times.
✓ Branch 14 taken 8512 times.
✓ Branch 15 taken 34842 times.
✓ Branch 16 taken 160384 times.
✓ Branch 17 taken 9661 times.
✓ Branch 19 taken 81631 times.
✓ Branch 20 taken 78753 times.
✓ Branch 21 taken 155829 times.
✓ Branch 22 taken 25434 times.
✓ Branch 24 taken 92849 times.
✓ Branch 25 taken 62980 times.
✓ Branch 26 taken 62980 times.
✓ Branch 27 taken 25434 times.
✓ Branch 28 taken 88414 times.
✓ Branch 29 taken 34842 times.
✓ Branch 30 taken 8836 times.
✓ Branch 31 taken 26006 times.
✓ Branch 32 taken 6074 times.
✓ Branch 33 taken 2762 times.
✓ Branch 34 taken 2704 times.
✓ Branch 35 taken 3370 times.
✓ Branch 36 taken 19435 times.
✓ Branch 37 taken 2339 times.
✓ Branch 39 taken 16308 times.
✓ Branch 40 taken 3127 times.
✓ Branch 41 taken 2339 times.
✓ Branch 42 taken 3127 times.
✓ Branch 43 taken 13956 times.
✓ Branch 44 taken 18547 times.
✓ Branch 46 taken 5890 times.
✓ Branch 47 taken 9309 times.
✓ Branch 48 taken 58553 times.
✓ Branch 49 taken 11409 times.
✓ Branch 50 taken 37459 times.
✓ Branch 51 taken 4956 times.
354120 AV_QSORT(prob_table, size, PTable, compare_by_prob);
97
98
2/2
✓ Branch 0 taken 84239 times.
✓ Branch 1 taken 4956 times.
89195 for (times = 0; times <= max_length; times++) {
99 84239 to->nitems = 0;
100 84239 to->item_idx[0] = 0;
101
102 84239 j = 0;
103 84239 k = 0;
104
105
2/2
✓ Branch 0 taken 79283 times.
✓ Branch 1 taken 4956 times.
84239 if (times < max_length) {
106 79283 i = 0;
107 }
108
4/4
✓ Branch 0 taken 3147874 times.
✓ Branch 1 taken 441430 times.
✓ Branch 2 taken 357191 times.
✓ Branch 3 taken 84239 times.
3589304 while (i < size || j + 1 < from->nitems) {
109 3505065 to->nitems++;
110 3505065 to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
111
2/2
✓ Branch 0 taken 3147874 times.
✓ Branch 1 taken 357191 times.
3505065 if (i < size &&
112
2/2
✓ Branch 0 taken 3032076 times.
✓ Branch 1 taken 115798 times.
3147874 (j + 1 >= from->nitems ||
113 3032076 prob_table[i].prob <
114
2/2
✓ Branch 0 taken 1725049 times.
✓ Branch 1 taken 1307027 times.
3032076 from->probability[j] + from->probability[j + 1])) {
115 1840847 to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
116 1840847 to->probability[to->nitems - 1] = prob_table[i].prob;
117 1840847 i++;
118 } else {
119
2/2
✓ Branch 0 taken 10172795 times.
✓ Branch 1 taken 1664218 times.
11837013 for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
120 10172795 to->items[to->item_idx[to->nitems]++] = from->items[k];
121 }
122 1664218 to->probability[to->nitems - 1] =
123 1664218 from->probability[j] + from->probability[j + 1];
124 1664218 j += 2;
125 }
126 }
127 84239 temp = to;
128 84239 to = from;
129 84239 from = temp;
130 }
131
132
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.
4956 min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
133
2/2
✓ Branch 0 taken 858649 times.
✓ Branch 1 taken 4956 times.
863605 for (i = 0; i < from->item_idx[min]; i++) {
134 858649 nbits[from->items[i]]++;
135 }
136 // we don't want to return the 256 bit count (it was just in here to prevent
137 // all 1s encoding)
138 4956 j = 0;
139
2/2
✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.
1273692 for (i = 0; i < 256; i++) {
140
2/2
✓ Branch 0 taken 110105 times.
✓ Branch 1 taken 1158631 times.
1268736 if (nbits[i] > 0) {
141 110105 distincts[j].code = i;
142 110105 distincts[j].length = nbits[i];
143 110105 j++;
144 }
145 }
146 4956 }
147
148 4952 void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
149 {
150 4952 memset(s->val_count, 0, sizeof(s->val_count));
151 4952 }
152
153 /**
154 * Produces a Huffman encoding with a given input
155 *
156 * @param s input to encode
157 * @param bits output array where the ith character represents how many input values have i length encoding
158 * @param val output array of input values sorted by their encoded length
159 * @param max_nval maximum number of distinct input values
160 */
161 4952 void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
162 uint8_t val[], int max_nval)
163 {
164 int i, j;
165 4952 int nval = 0;
166 PTable val_counts[257];
167 HuffTable distincts[256];
168
169
2/2
✓ Branch 0 taken 1267712 times.
✓ Branch 1 taken 4952 times.
1272664 for (i = 0; i < 256; i++) {
170
2/2
✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 1158129 times.
1267712 if (s->val_count[i]) nval++;
171 }
172
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4952 times.
4952 av_assert0 (nval <= max_nval);
173
174 4952 j = 0;
175
2/2
✓ Branch 0 taken 1267712 times.
✓ Branch 1 taken 4952 times.
1272664 for (i = 0; i < 256; i++) {
176
2/2
✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 1158129 times.
1267712 if (s->val_count[i]) {
177 109583 val_counts[j].value = i;
178 109583 val_counts[j].prob = s->val_count[i];
179 109583 j++;
180 }
181 }
182 4952 val_counts[j].value = 256;
183 4952 val_counts[j].prob = 0;
184 4952 ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
185
44/44
✓ Branch 0 taken 40930 times.
✓ Branch 1 taken 10908 times.
✓ Branch 3 taken 10492 times.
✓ Branch 4 taken 30438 times.
✓ Branch 6 taken 1544 times.
✓ Branch 7 taken 8948 times.
✓ Branch 9 taken 6747 times.
✓ Branch 10 taken 23691 times.
✓ Branch 12 taken 9615 times.
✓ Branch 13 taken 31315 times.
✓ Branch 14 taken 9425 times.
✓ Branch 15 taken 31505 times.
✓ Branch 16 taken 152588 times.
✓ Branch 17 taken 7465 times.
✓ Branch 19 taken 86443 times.
✓ Branch 20 taken 66145 times.
✓ Branch 21 taken 127497 times.
✓ Branch 22 taken 15962 times.
✓ Branch 24 taken 69849 times.
✓ Branch 25 taken 57648 times.
✓ Branch 26 taken 57648 times.
✓ Branch 27 taken 15962 times.
✓ Branch 28 taken 73610 times.
✓ Branch 29 taken 31505 times.
✓ Branch 30 taken 13005 times.
✓ Branch 31 taken 18500 times.
✓ Branch 32 taken 9114 times.
✓ Branch 33 taken 3891 times.
✓ Branch 34 taken 3609 times.
✓ Branch 35 taken 5505 times.
✓ Branch 36 taken 22527 times.
✓ Branch 37 taken 2995 times.
✓ Branch 39 taken 18022 times.
✓ Branch 40 taken 4505 times.
✓ Branch 41 taken 2995 times.
✓ Branch 42 taken 4505 times.
✓ Branch 43 taken 15255 times.
✓ Branch 44 taken 13255 times.
✓ Branch 46 taken 3014 times.
✓ Branch 47 taken 7894 times.
✓ Branch 48 taken 51838 times.
✓ Branch 49 taken 10134 times.
✓ Branch 50 taken 33462 times.
✓ Branch 51 taken 4952 times.
314848 AV_QSORT(distincts, nval, HuffTable, compare_by_length);
186
187 4952 memset(bits, 0, sizeof(bits[0]) * 17);
188
2/2
✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 4952 times.
114535 for (i = 0; i < nval; i++) {
189 109583 val[i] = distincts[i].code;
190 109583 bits[distincts[i].length]++;
191 }
192 4952 }
193