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/error.h" | ||
30 | #include "libavutil/log.h" | ||
31 | #include "libavutil/macros.h" | ||
32 | #include "libavutil/mem.h" | ||
33 | #include "libavutil/qsort.h" | ||
34 | |||
35 | #include "huffman.h" | ||
36 | #include "vlc.h" | ||
37 | |||
38 | /* symbol for Huffman tree node */ | ||
39 | #define HNODE -1 | ||
40 | |||
41 | typedef struct HeapElem { | ||
42 | uint64_t val; | ||
43 | int name; | ||
44 | } HeapElem; | ||
45 | |||
46 | 1973140 | static void heap_sift(HeapElem *h, int root, int size) | |
47 | { | ||
48 |
2/2✓ Branch 0 taken 13354908 times.
✓ Branch 1 taken 761161 times.
|
14116069 | while (root * 2 + 1 < size) { |
49 | 13354908 | int child = root * 2 + 1; | |
50 |
4/4✓ Branch 0 taken 13346304 times.
✓ Branch 1 taken 8604 times.
✓ Branch 2 taken 6177070 times.
✓ Branch 3 taken 7169234 times.
|
13354908 | if (child < size - 1 && h[child].val > h[child+1].val) |
51 | 6177070 | child++; | |
52 |
2/2✓ Branch 0 taken 12142929 times.
✓ Branch 1 taken 1211979 times.
|
13354908 | if (h[root].val > h[child].val) { |
53 | 12142929 | FFSWAP(HeapElem, h[root], h[child]); | |
54 | 12142929 | root = child; | |
55 | } else | ||
56 | 1211979 | break; | |
57 | } | ||
58 | 1973140 | } | |
59 | |||
60 | 2446 | int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0) | |
61 | { | ||
62 | 2446 | HeapElem *h = av_malloc_array(sizeof(*h), stats_size); | |
63 | 2446 | int *up = av_malloc_array(sizeof(*up) * 2, stats_size); | |
64 | 2446 | uint8_t *len = av_malloc_array(sizeof(*len) * 2, stats_size); | |
65 | 2446 | uint16_t *map= av_malloc_array(sizeof(*map), stats_size); | |
66 | int offset, i, next; | ||
67 | 2446 | int size = 0; | |
68 | 2446 | int ret = 0; | |
69 | |||
70 |
4/8✓ Branch 0 taken 2446 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2446 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2446 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 2446 times.
|
2446 | if (!h || !up || !len || !map) { |
71 | ✗ | ret = AVERROR(ENOMEM); | |
72 | ✗ | goto end; | |
73 | } | ||
74 | |||
75 |
2/2✓ Branch 0 taken 875008 times.
✓ Branch 1 taken 2446 times.
|
877454 | for (i = 0; i<stats_size; i++) { |
76 | 875008 | dst[i] = 255; | |
77 |
3/4✓ Branch 0 taken 83691 times.
✓ Branch 1 taken 791317 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 83691 times.
|
875008 | if (stats[i] || !skip0) |
78 | 791317 | map[size++] = i; | |
79 | } | ||
80 | |||
81 | 2446 | for (offset = 1; ; offset <<= 1) { | |
82 |
2/2✓ Branch 0 taken 791317 times.
✓ Branch 1 taken 2446 times.
|
793763 | for (i=0; i < size; i++) { |
83 | 791317 | h[i].name = i; | |
84 | 791317 | h[i].val = (stats[map[i]] << 14) + offset; | |
85 | } | ||
86 |
2/2✓ Branch 0 taken 395398 times.
✓ Branch 1 taken 2446 times.
|
397844 | for (i = size / 2 - 1; i >= 0; i--) |
87 | 395398 | heap_sift(h, i, size); | |
88 | |||
89 |
2/2✓ Branch 0 taken 788871 times.
✓ Branch 1 taken 2446 times.
|
791317 | for (next = size; next < size * 2 - 1; next++) { |
90 | // merge the two smallest entries, and put it back in the heap | ||
91 | 788871 | uint64_t min1v = h[0].val; | |
92 | 788871 | up[h[0].name] = next; | |
93 | 788871 | h[0].val = INT64_MAX; | |
94 | 788871 | heap_sift(h, 0, size); | |
95 | 788871 | up[h[0].name] = next; | |
96 | 788871 | h[0].name = next; | |
97 | 788871 | h[0].val += min1v; | |
98 | 788871 | heap_sift(h, 0, size); | |
99 | } | ||
100 | |||
101 | 2446 | len[2 * size - 2] = 0; | |
102 |
2/2✓ Branch 0 taken 786425 times.
✓ Branch 1 taken 2446 times.
|
788871 | for (i = 2 * size - 3; i >= size; i--) |
103 | 786425 | len[i] = len[up[i]] + 1; | |
104 |
2/2✓ Branch 0 taken 791317 times.
✓ Branch 1 taken 2446 times.
|
793763 | for (i = 0; i < size; i++) { |
105 | 791317 | dst[map[i]] = len[up[i]] + 1; | |
106 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 791317 times.
|
791317 | if (dst[map[i]] >= 32) break; |
107 | } | ||
108 |
1/2✓ Branch 0 taken 2446 times.
✗ Branch 1 not taken.
|
2446 | if (i==size) break; |
109 | } | ||
110 | 2446 | end: | |
111 | 2446 | av_free(h); | |
112 | 2446 | av_free(up); | |
113 | 2446 | av_free(len); | |
114 | 2446 | av_free(map); | |
115 | 2446 | return ret; | |
116 | } | ||
117 | |||
118 | 287031 | static void get_tree_codes(int8_t *lens, uint8_t *xlat, | |
119 | Node *nodes, int node, int pl, int *pos, int no_zero_count) | ||
120 | { | ||
121 | int s; | ||
122 | |||
123 | 287031 | s = nodes[node].sym; | |
124 |
5/6✓ Branch 0 taken 141669 times.
✓ Branch 1 taken 145362 times.
✓ Branch 2 taken 35334 times.
✓ Branch 3 taken 106335 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 35334 times.
|
287031 | if (s != HNODE || (no_zero_count && !nodes[node].count)) { |
125 | 145362 | lens[*pos] = pl; | |
126 | 145362 | xlat[*pos] = s; | |
127 | 145362 | (*pos)++; | |
128 | } else { | ||
129 | 141669 | pl++; | |
130 | 141669 | get_tree_codes(lens, xlat, nodes, nodes[node].n0, pl, | |
131 | pos, no_zero_count); | ||
132 | 141669 | get_tree_codes(lens, xlat, nodes, nodes[node].n0 + 1, pl, | |
133 | pos, no_zero_count); | ||
134 | } | ||
135 | 287031 | } | |
136 | |||
137 | 3693 | static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits, void *logctx) | |
138 | { | ||
139 | 3693 | int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); | |
140 | int8_t lens[256]; | ||
141 | uint8_t xlat[256]; | ||
142 | 3693 | int pos = 0; | |
143 | |||
144 | 3693 | get_tree_codes(lens, xlat, nodes, head, 0, | |
145 | &pos, no_zero_count); | ||
146 | 3693 | return ff_vlc_init_from_lengths(vlc, nb_bits, pos, lens, 1, | |
147 | xlat, 1, 1, 0, 0, logctx); | ||
148 | } | ||
149 | |||
150 | |||
151 | /** | ||
152 | * nodes size must be 2*nb_codes | ||
153 | * first nb_codes nodes.count must be set | ||
154 | */ | ||
155 | 3693 | int ff_huff_build_tree(void *logctx, VLC *vlc, int nb_codes, int nb_bits, | |
156 | Node *nodes, HuffCmp cmp, int flags) | ||
157 | { | ||
158 | int i, j; | ||
159 | int cur_node; | ||
160 | 3693 | int64_t sum = 0; | |
161 | |||
162 |
2/2✓ Branch 0 taken 145362 times.
✓ Branch 1 taken 3693 times.
|
149055 | for (i = 0; i < nb_codes; i++) { |
163 | 145362 | nodes[i].sym = i; | |
164 | 145362 | nodes[i].n0 = -2; | |
165 | 145362 | sum += nodes[i].count; | |
166 | } | ||
167 | |||
168 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3693 times.
|
3693 | if (sum >> 31) { |
169 | ✗ | av_log(logctx, AV_LOG_ERROR, | |
170 | "Too high symbol frequencies. " | ||
171 | "Tree construction is not possible\n"); | ||
172 | ✗ | return -1; | |
173 | } | ||
174 |
44/44✓ Branch 0 taken 60121 times.
✓ Branch 1 taken 20542 times.
✓ Branch 3 taken 32073 times.
✓ Branch 4 taken 28048 times.
✓ Branch 6 taken 10242 times.
✓ Branch 7 taken 21831 times.
✓ Branch 9 taken 8683 times.
✓ Branch 10 taken 19365 times.
✓ Branch 12 taken 31653 times.
✓ Branch 13 taken 28468 times.
✓ Branch 14 taken 12435 times.
✓ Branch 15 taken 47686 times.
✓ Branch 16 taken 493365 times.
✓ Branch 17 taken 20114 times.
✓ Branch 19 taken 342802 times.
✓ Branch 20 taken 150563 times.
✓ Branch 21 taken 326481 times.
✓ Branch 22 taken 40480 times.
✓ Branch 24 taken 196284 times.
✓ Branch 25 taken 130197 times.
✓ Branch 26 taken 40480 times.
✓ Branch 27 taken 130197 times.
✓ Branch 28 taken 170677 times.
✓ Branch 29 taken 47686 times.
✓ Branch 30 taken 6709 times.
✓ Branch 31 taken 40977 times.
✓ Branch 32 taken 4852 times.
✓ Branch 33 taken 1857 times.
✓ Branch 34 taken 1475 times.
✓ Branch 35 taken 3377 times.
✓ Branch 36 taken 7894 times.
✓ Branch 37 taken 619 times.
✓ Branch 39 taken 5181 times.
✓ Branch 40 taken 2713 times.
✓ Branch 41 taken 619 times.
✓ Branch 42 taken 2713 times.
✓ Branch 43 taken 24609 times.
✓ Branch 44 taken 22458 times.
✓ Branch 46 taken 9926 times.
✓ Branch 47 taken 10616 times.
✓ Branch 48 taken 80663 times.
✓ Branch 49 taken 17164 times.
✓ Branch 50 taken 50760 times.
✓ Branch 51 taken 3693 times.
|
864150 | AV_QSORT(nodes, nb_codes, Node, cmp); |
175 | 3693 | cur_node = nb_codes; | |
176 | 3693 | nodes[nb_codes*2-1].count = 0; | |
177 |
2/2✓ Branch 0 taken 145362 times.
✓ Branch 1 taken 3693 times.
|
149055 | for (i = 0; i < nb_codes * 2 - 1; i += 2) { |
178 | 145362 | uint32_t cur_count = nodes[i].count + nodes[i+1].count; | |
179 | // find correct place to insert new node, and | ||
180 | // make space for the new node while at it | ||
181 |
2/2✓ Branch 0 taken 5623698 times.
✓ Branch 1 taken 16173 times.
|
5639871 | for(j = cur_node; j > i + 2; j--){ |
182 |
2/2✓ Branch 0 taken 5565907 times.
✓ Branch 1 taken 57791 times.
|
5623698 | if(cur_count > nodes[j-1].count || |
183 |
2/2✓ Branch 0 taken 90183 times.
✓ Branch 1 taken 5475724 times.
|
5565907 | (cur_count == nodes[j-1].count && |
184 |
2/2✓ Branch 0 taken 18785 times.
✓ Branch 1 taken 71398 times.
|
90183 | !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST))) |
185 | break; | ||
186 | 5494509 | nodes[j] = nodes[j - 1]; | |
187 | } | ||
188 | 145362 | nodes[j].sym = HNODE; | |
189 | 145362 | nodes[j].count = cur_count; | |
190 | 145362 | nodes[j].n0 = i; | |
191 | 145362 | cur_node++; | |
192 | } | ||
193 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3693 times.
|
3693 | if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits, logctx) < 0) { |
194 | ✗ | av_log(logctx, AV_LOG_ERROR, "Error building tree\n"); | |
195 | ✗ | return -1; | |
196 | } | ||
197 | 3693 | return 0; | |
198 | } | ||
199 |