2 * Copyright (c) 2006 Konstantin Shishkov
3 * Copyright (c) 2007 Loren Merritt
5 * This file is part of FFmpeg.
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.
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.
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
24 * huffman tree builder and VLC generator
33 /* symbol for Huffman tree node */
41 static void heap_sift(HeapElem
*h
, int root
, int size
)
43 while (root
* 2 + 1 < size
) {
44 int child
= root
* 2 + 1;
45 if (child
< size
- 1 && h
[child
].val
> h
[child
+1].val
)
47 if (h
[root
].val
> h
[child
].val
) {
48 FFSWAP(HeapElem
, h
[root
], h
[child
]);
55 int ff_huff_gen_len_table(uint8_t *dst
, const uint64_t *stats
, int stats_size
, int skip0
)
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
);
65 if (!h
|| !up
|| !len
) {
66 ret
= AVERROR(ENOMEM
);
70 for (i
= 0; i
<stats_size
; i
++) {
72 if (stats
[i
] || !skip0
)
76 for (offset
= 1; ; offset
<<= 1) {
77 for (i
=0; i
< size
; i
++) {
79 h
[i
].val
= (stats
[map
[i
]] << 14) + offset
;
81 for (i
= size
/ 2 - 1; i
>= 0; i
--)
82 heap_sift(h
, i
, size
);
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
;
89 heap_sift(h
, 0, size
);
93 heap_sift(h
, 0, size
);
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;
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
)
120 if (s
!= HNODE
|| (no_zero_count
&& !nodes
[node
].count
)) {
128 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
, pfx
, pl
,
131 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
+ 1, pfx
, pl
,
136 static int build_huff_tree(VLC
*vlc
, Node
*nodes
, int head
, int flags
, int nb_bits
)
138 int no_zero_count
= !(flags
& FF_HUFFMAN_FLAG_ZERO_COUNT
);
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);
151 * nodes size must be 2*nb_codes
152 * first nb_codes nodes.count must be set
154 int ff_huff_build_tree(AVCodecContext
*avctx
, VLC
*vlc
, int nb_codes
, int nb_bits
,
155 Node
*nodes
, HuffCmp cmp
, int flags
)
161 for (i
= 0; i
< nb_codes
; i
++) {
164 sum
+= nodes
[i
].count
;
168 av_log(avctx
, AV_LOG_ERROR
,
169 "Too high symbol frequencies. "
170 "Tree construction is not possible\n");
173 qsort(nodes
, nb_codes
, sizeof(Node
), cmp
);
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
)))
185 nodes
[j
] = nodes
[j
- 1];
187 nodes
[j
].sym
= HNODE
;
188 nodes
[j
].count
= cur_count
;
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");