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
30
31 /* symbol for Huffman tree node */
33
38
40 {
41 while (root * 2 + 1 < size) {
42 int child = root * 2 + 1;
43 if (child < size - 1 && h[child].
val > h[child+1].
val)
44 child++;
45 if (h[root].
val > h[child].
val) {
48 } else
49 break;
50 }
51 }
52
54 {
56 int up[2*256];
60
61 for (offset = 1; ; offset <<= 1) {
62 for (i=0; i <
size; i++) {
64 h[i].
val = (stats[i] << 8) + offset;
65 }
66 for (i = size / 2 - 1; i >= 0; i--)
68
69 for (next = size; next < size * 2 - 1; next++) {
70 // merge the two smallest entries, and put it back in the heap
71 uint64_t min1v = h[0].
val;
73 h[0].val = INT64_MAX;
75 up[h[0].name] = next;
76 h[0].name = next;
77 h[0].val += min1v;
79 }
80
81 len[2 * size - 2] = 0;
82 for (i = 2 * size - 3; i >=
size; i--)
83 len[i] = len[up[i]] + 1;
84 for (i = 0; i <
size; i++) {
85 dst[i] = len[up[i]] + 1;
86 if (dst[i] >= 32) break;
87 }
88 if (i==size) break;
89 }
90 }
91
93 Node *nodes,
int node,
94 uint32_t pfx, int pl, int *pos, int no_zero_count)
95 {
97
99 if (s !=
HNODE || (no_zero_count && !nodes[node].
count)) {
100 bits[*pos] = pfx;
101 lens[*pos] = pl;
103 (*pos)++;
104 } else {
105 pfx <<= 1;
106 pl++;
108 pos, no_zero_count);
109 pfx |= 1;
110 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl,
111 pos, no_zero_count);
112 }
113 }
114
116 {
119 int16_t lens[256];
121 int pos = 0;
122
124 &pos, no_zero_count);
125 return ff_init_vlc_sparse(vlc,
FF_HUFFMAN_BITS, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0);
126 }
127
128
129 /**
130 * nodes size must be 2*nb_codes
131 * first nb_codes nodes.count must be set
132 */
135 {
136 int i, j;
137 int cur_node;
138 int64_t sum = 0;
139
140 for (i = 0; i < nb_codes; i++) {
143 sum += nodes[i].
count;
144 }
145
146 if (sum >> 31) {
148 "Too high symbol frequencies. "
149 "Tree construction is not possible\n");
150 return -1;
151 }
152 qsort(nodes, nb_codes,
sizeof(
Node), cmp);
153 cur_node = nb_codes;
154 nodes[nb_codes*2-1].
count = 0;
155 for (i = 0; i < nb_codes * 2 - 1; i += 2) {
156 uint32_t cur_count = nodes[i].
count + nodes[i+1].
count;
157 // find correct place to insert new node, and
158 // make space for the new node while at it
159 for(j = cur_node; j > i + 2; j--){
160 if(cur_count > nodes[j-1].
count ||
161 (cur_count == nodes[j-1].
count &&
163 break;
164 nodes[j] = nodes[j - 1];
165 }
167 nodes[j].
count = cur_count;
169 cur_node++;
170 }
173 return -1;
174 }
175 return 0;
176 }