GCC Code Coverage Report | |||||||||||||||||||||
|
|||||||||||||||||||||
Line | Branch | Exec | Source |
1 |
/* |
||
2 |
* Copyright (c) 2006 Konstantin Shishkov |
||
3 |
* Copyright (c) 2007 Loren Merritt |
||
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 |
/** |
||
23 |
* @file |
||
24 |
* huffman tree builder and VLC generator |
||
25 |
*/ |
||
26 |
|||
27 |
#include <stdint.h> |
||
28 |
|||
29 |
#include "libavutil/qsort.h" |
||
30 |
#include "libavutil/common.h" |
||
31 |
|||
32 |
#include "avcodec.h" |
||
33 |
#include "huffman.h" |
||
34 |
#include "vlc.h" |
||
35 |
|||
36 |
/* symbol for Huffman tree node */ |
||
37 |
#define HNODE -1 |
||
38 |
|||
39 |
typedef struct HeapElem { |
||
40 |
uint64_t val; |
||
41 |
int name; |
||
42 |
} HeapElem; |
||
43 |
|||
44 |
1973140 |
static void heap_sift(HeapElem *h, int root, int size) |
|
45 |
{ |
||
46 |
✓✓ | 14116069 |
while (root * 2 + 1 < size) { |
47 |
13354908 |
int child = root * 2 + 1; |
|
48 |
✓✓✓✓ |
13354908 |
if (child < size - 1 && h[child].val > h[child+1].val) |
49 |
6177070 |
child++; |
|
50 |
✓✓ | 13354908 |
if (h[root].val > h[child].val) { |
51 |
12142929 |
FFSWAP(HeapElem, h[root], h[child]); |
|
52 |
12142929 |
root = child; |
|
53 |
} else |
||
54 |
1211979 |
break; |
|
55 |
} |
||
56 |
1973140 |
} |
|
57 |
|||
58 |
2446 |
int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0) |
|
59 |
{ |
||
60 |
2446 |
HeapElem *h = av_malloc_array(sizeof(*h), stats_size); |
|
61 |
2446 |
int *up = av_malloc_array(sizeof(*up) * 2, stats_size); |
|
62 |
2446 |
uint8_t *len = av_malloc_array(sizeof(*len) * 2, stats_size); |
|
63 |
2446 |
uint16_t *map= av_malloc_array(sizeof(*map), stats_size); |
|
64 |
int offset, i, next; |
||
65 |
2446 |
int size = 0; |
|
66 |
2446 |
int ret = 0; |
|
67 |
|||
68 |
✓✗✓✗ ✓✗✗✓ |
2446 |
if (!h || !up || !len || !map) { |
69 |
ret = AVERROR(ENOMEM); |
||
70 |
goto end; |
||
71 |
} |
||
72 |
|||
73 |
✓✓ | 877454 |
for (i = 0; i<stats_size; i++) { |
74 |
875008 |
dst[i] = 255; |
|
75 |
✓✓✗✓ |
875008 |
if (stats[i] || !skip0) |
76 |
791317 |
map[size++] = i; |
|
77 |
} |
||
78 |
|||
79 |
2446 |
for (offset = 1; ; offset <<= 1) { |
|
80 |
✓✓ | 793763 |
for (i=0; i < size; i++) { |
81 |
791317 |
h[i].name = i; |
|
82 |
791317 |
h[i].val = (stats[map[i]] << 14) + offset; |
|
83 |
} |
||
84 |
✓✓ | 397844 |
for (i = size / 2 - 1; i >= 0; i--) |
85 |
395398 |
heap_sift(h, i, size); |
|
86 |
|||
87 |
✓✓ | 791317 |
for (next = size; next < size * 2 - 1; next++) { |
88 |
// merge the two smallest entries, and put it back in the heap |
||
89 |
788871 |
uint64_t min1v = h[0].val; |
|
90 |
788871 |
up[h[0].name] = next; |
|
91 |
788871 |
h[0].val = INT64_MAX; |
|
92 |
788871 |
heap_sift(h, 0, size); |
|
93 |
788871 |
up[h[0].name] = next; |
|
94 |
788871 |
h[0].name = next; |
|
95 |
788871 |
h[0].val += min1v; |
|
96 |
788871 |
heap_sift(h, 0, size); |
|
97 |
} |
||
98 |
|||
99 |
2446 |
len[2 * size - 2] = 0; |
|
100 |
✓✓ | 788871 |
for (i = 2 * size - 3; i >= size; i--) |
101 |
786425 |
len[i] = len[up[i]] + 1; |
|
102 |
✓✓ | 793763 |
for (i = 0; i < size; i++) { |
103 |
791317 |
dst[map[i]] = len[up[i]] + 1; |
|
104 |
✗✓ | 791317 |
if (dst[map[i]] >= 32) break; |
105 |
} |
||
106 |
✓✗ | 2446 |
if (i==size) break; |
107 |
} |
||
108 |
2446 |
end: |
|
109 |
2446 |
av_free(h); |
|
110 |
2446 |
av_free(up); |
|
111 |
2446 |
av_free(len); |
|
112 |
2446 |
av_free(map); |
|
113 |
2446 |
return ret; |
|
114 |
} |
||
115 |
|||
116 |
319323 |
static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat, |
|
117 |
Node *nodes, int node, |
||
118 |
uint32_t pfx, int pl, int *pos, int no_zero_count) |
||
119 |
{ |
||
120 |
int s; |
||
121 |
|||
122 |
319323 |
s = nodes[node].sym; |
|
123 |
✓✓✓✓ ✗✓ |
319323 |
if (s != HNODE || (no_zero_count && !nodes[node].count)) { |
124 |
162210 |
bits[*pos] = pfx; |
|
125 |
162210 |
lens[*pos] = pl; |
|
126 |
162210 |
xlat[*pos] = s; |
|
127 |
162210 |
(*pos)++; |
|
128 |
} else { |
||
129 |
157113 |
pfx <<= 1; |
|
130 |
157113 |
pl++; |
|
131 |
157113 |
get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, |
|
132 |
pos, no_zero_count); |
||
133 |
157113 |
pfx |= 1; |
|
134 |
157113 |
get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl, |
|
135 |
pos, no_zero_count); |
||
136 |
} |
||
137 |
319323 |
} |
|
138 |
|||
139 |
5097 |
static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits) |
|
140 |
{ |
||
141 |
5097 |
int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); |
|
142 |
uint32_t bits[256]; |
||
143 |
int16_t lens[256]; |
||
144 |
uint8_t xlat[256]; |
||
145 |
5097 |
int pos = 0; |
|
146 |
|||
147 |
5097 |
get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, |
|
148 |
&pos, no_zero_count); |
||
149 |
5097 |
return ff_init_vlc_sparse(vlc, nb_bits, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); |
|
150 |
} |
||
151 |
|||
152 |
|||
153 |
/** |
||
154 |
* nodes size must be 2*nb_codes |
||
155 |
* first nb_codes nodes.count must be set |
||
156 |
*/ |
||
157 |
5097 |
int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bits, |
|
158 |
Node *nodes, HuffCmp cmp, int flags) |
||
159 |
{ |
||
160 |
int i, j; |
||
161 |
int cur_node; |
||
162 |
5097 |
int64_t sum = 0; |
|
163 |
|||
164 |
✓✓ | 167307 |
for (i = 0; i < nb_codes; i++) { |
165 |
162210 |
nodes[i].sym = i; |
|
166 |
162210 |
nodes[i].n0 = -2; |
|
167 |
162210 |
sum += nodes[i].count; |
|
168 |
} |
||
169 |
|||
170 |
✗✓ | 5097 |
if (sum >> 31) { |
171 |
av_log(avctx, AV_LOG_ERROR, |
||
172 |
"Too high symbol frequencies. " |
||
173 |
"Tree construction is not possible\n"); |
||
174 |
return -1; |
||
175 |
} |
||
176 |
✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ |
851113 |
AV_QSORT(nodes, nb_codes, Node, cmp); |
177 |
5097 |
cur_node = nb_codes; |
|
178 |
5097 |
nodes[nb_codes*2-1].count = 0; |
|
179 |
✓✓ | 167307 |
for (i = 0; i < nb_codes * 2 - 1; i += 2) { |
180 |
162210 |
uint32_t cur_count = nodes[i].count + nodes[i+1].count; |
|
181 |
// find correct place to insert new node, and |
||
182 |
// make space for the new node while at it |
||
183 |
✓✓ | 5708460 |
for(j = cur_node; j > i + 2; j--){ |
184 |
✓✓ | 5685299 |
if(cur_count > nodes[j-1].count || |
185 |
✓✓ | 5617648 |
(cur_count == nodes[j-1].count && |
186 |
✓✓ | 101452 |
!(flags & FF_HUFFMAN_FLAG_HNODE_FIRST))) |
187 |
break; |
||
188 |
5546250 |
nodes[j] = nodes[j - 1]; |
|
189 |
} |
||
190 |
162210 |
nodes[j].sym = HNODE; |
|
191 |
162210 |
nodes[j].count = cur_count; |
|
192 |
162210 |
nodes[j].n0 = i; |
|
193 |
162210 |
cur_node++; |
|
194 |
} |
||
195 |
✗✓ | 5097 |
if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits) < 0) { |
196 |
av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); |
||
197 |
return -1; |
||
198 |
} |
||
199 |
5097 |
return 0; |
|
200 |
} |
Generated by: GCOVR (Version 4.2) |