GCC Code Coverage Report | |||||||||||||||||||||
|
|||||||||||||||||||||
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 |
✗✓ | 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 |
✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ |
354120 |
AV_QSORT(prob_table, size, PTable, compare_by_prob); |
97 |
|||
98 |
✓✓ | 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 |
✓✓ | 84239 |
if (times < max_length) { |
106 |
79283 |
i = 0; |
|
107 |
} |
||
108 |
✓✓✓✓ |
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 |
✓✓ | 3505065 |
if (i < size && |
112 |
✓✓ | 3147874 |
(j + 1 >= from->nitems || |
113 |
3032076 |
prob_table[i].prob < |
|
114 |
✓✓ | 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 |
✓✓ | 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 |
✗✓ | 4956 |
min = (size - 1 < from->nitems) ? size - 1 : from->nitems; |
133 |
✓✓ | 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 |
✓✓ | 1273692 |
for (i = 0; i < 256; i++) { |
140 |
✓✓ | 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 |
✓✓ | 1272664 |
for (i = 0; i < 256; i++) { |
170 |
✓✓ | 1267712 |
if (s->val_count[i]) nval++; |
171 |
} |
||
172 |
✗✓ | 4952 |
av_assert0 (nval <= max_nval); |
173 |
|||
174 |
4952 |
j = 0; |
|
175 |
✓✓ | 1272664 |
for (i = 0; i < 256; i++) { |
176 |
✓✓ | 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 |
✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ |
314848 |
AV_QSORT(distincts, nval, HuffTable, compare_by_length); |
186 |
|||
187 |
4952 |
memset(bits, 0, sizeof(bits[0]) * 17); |
|
188 |
✓✓ | 114535 |
for (i = 0; i < nval; i++) { |
189 |
109583 |
val[i] = distincts[i].code; |
|
190 |
109583 |
bits[distincts[i].length]++; |
|
191 |
} |
||
192 |
4952 |
} |
Generated by: GCOVR (Version 4.2) |