2 * Copyright (c) 2006 Konstantin Shishkov
3 * Copyright (c) 2007 Loren Merritt
5 * This file is part of Libav.
7 * Libav 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 * Libav 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 Libav; 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
31 /* symbol for Huffman tree node */
39 static void heap_sift(HeapElem
*h
, int root
, int size
)
41 while (root
* 2 + 1 < size
) {
42 int child
= root
* 2 + 1;
43 if (child
< size
- 1 && h
[child
].val
> h
[child
+1].val
)
45 if (h
[root
].val
> h
[child
].val
) {
46 FFSWAP(HeapElem
, h
[root
], h
[child
]);
53 void ff_huff_gen_len_table(uint8_t *dst
, const uint64_t *stats
)
61 for (offset
= 1; ; offset
<<= 1) {
62 for (i
=0; i
< size
; i
++) {
64 h
[i
].val
= (stats
[i
] << 8) + offset
;
66 for (i
= size
/ 2 - 1; i
>= 0; i
--)
67 heap_sift(h
, i
, size
);
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
;
74 heap_sift(h
, 0, size
);
78 heap_sift(h
, 0, size
);
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;
92 static void get_tree_codes(uint32_t *bits
, int16_t *lens
, uint8_t *xlat
,
93 Node
*nodes
, int node
,
94 uint32_t pfx
, int pl
, int *pos
, int no_zero_count
)
99 if (s
!= HNODE
|| (no_zero_count
&& !nodes
[node
].count
)) {
107 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
, pfx
, pl
,
110 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
+ 1, pfx
, pl
,
115 static int build_huff_tree(VLC
*vlc
, Node
*nodes
, int head
, int flags
)
117 int no_zero_count
= !(flags
& FF_HUFFMAN_FLAG_ZERO_COUNT
);
123 get_tree_codes(bits
, lens
, xlat
, nodes
, head
, 0, 0,
124 &pos
, no_zero_count
);
125 return ff_init_vlc_sparse(vlc
, 9, pos
, lens
, 2, 2, bits
, 4, 4, xlat
, 1, 1, 0);
130 * nodes size must be 2*nb_codes
131 * first nb_codes nodes.count must be set
133 int ff_huff_build_tree(AVCodecContext
*avctx
, VLC
*vlc
, int nb_codes
,
134 Node
*nodes
, HuffCmp cmp
, int flags
)
140 for (i
= 0; i
< nb_codes
; i
++) {
143 sum
+= nodes
[i
].count
;
147 av_log(avctx
, AV_LOG_ERROR
,
148 "Too high symbol frequencies. "
149 "Tree construction is not possible\n");
152 qsort(nodes
, nb_codes
, sizeof(Node
), cmp
);
154 nodes
[nb_codes
*2-1].count
= 0;
155 for (i
= 0; i
< nb_codes
* 2 - 1; i
+= 2) {
156 nodes
[cur_node
].sym
= HNODE
;
157 nodes
[cur_node
].count
= nodes
[i
].count
+ nodes
[i
+ 1].count
;
158 nodes
[cur_node
].n0
= i
;
159 for (j
= cur_node
; j
> 0; j
--) {
160 if (nodes
[j
].count
> nodes
[j
- 1].count
||
161 (nodes
[j
].count
== nodes
[j
- 1].count
&&
162 (!(flags
& FF_HUFFMAN_FLAG_HNODE_FIRST
) ||
163 nodes
[j
].n0
== j
- 1 || nodes
[j
].n0
== j
- 2 ||
164 (nodes
[j
].sym
!=HNODE
&& nodes
[j
-1].sym
!=HNODE
))))
166 FFSWAP(Node
, nodes
[j
], nodes
[j
- 1]);
170 if (build_huff_tree(vlc
, nodes
, nb_codes
* 2 - 2, flags
) < 0) {
171 av_log(avctx
, AV_LOG_ERROR
, "Error building tree\n");