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