3 * huffman tree builder and VLC generator
4 * Copyright (c) 2006 Konstantin Shishkov
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #include "bitstream.h"
27 /* symbol for Huffman tree node */
31 static void get_tree_codes(uint32_t *bits
, int16_t *lens
, uint8_t *xlat
, Node
*nodes
, int node
, uint32_t pfx
, int pl
, int *pos
)
36 if(s
!= HNODE
|| !nodes
[node
].count
){
44 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
, pfx
, pl
, pos
);
46 get_tree_codes(bits
, lens
, xlat
, nodes
, nodes
[node
].n0
+1, pfx
, pl
, pos
);
50 static int build_huff_tree(VLC
*vlc
, Node
*nodes
, int head
)
57 get_tree_codes(bits
, lens
, xlat
, nodes
, head
, 0, 0, &pos
);
58 return init_vlc_sparse(vlc
, 9, pos
, lens
, 2, 2, bits
, 4, 4, xlat
, 1, 1, 0);
63 * nodes size must be 2*nb_codes
64 * first nb_codes nodes.count must be set
66 int ff_huff_build_tree(AVCodecContext
*avctx
, VLC
*vlc
, int nb_codes
,
67 Node
*nodes
, huff_cmp_t cmp
, int hnode_first
)
73 for(i
= 0; i
< nb_codes
; i
++){
76 sum
+= nodes
[i
].count
;
80 av_log(avctx
, AV_LOG_ERROR
, "Too high symbol frequencies. Tree construction is not possible\n");
83 qsort(nodes
, nb_codes
, sizeof(Node
), cmp
);
85 nodes
[nb_codes
*2-1].count
= 0;
86 for(i
= 0; i
< nb_codes
*2-1; i
+= 2){
87 nodes
[cur_node
].sym
= HNODE
;
88 nodes
[cur_node
].count
= nodes
[i
].count
+ nodes
[i
+1].count
;
89 nodes
[cur_node
].n0
= i
;
90 for(j
= cur_node
; j
> 0; j
--){
91 if(nodes
[j
].count
> nodes
[j
-1].count
||
92 (nodes
[j
].count
== nodes
[j
-1].count
&&
93 (!hnode_first
|| nodes
[j
].n0
==j
-1 || nodes
[j
].n0
==j
-2 ||
94 (nodes
[j
].sym
!=HNODE
&& nodes
[j
-1].sym
!=HNODE
))))
96 FFSWAP(Node
, nodes
[j
], nodes
[j
-1]);
100 if(build_huff_tree(vlc
, nodes
, nb_codes
*2-2) < 0){
101 av_log(avctx
, AV_LOG_ERROR
, "Error building tree\n");