ffmpeg / libavcodec / huffman.c @ 2912e87a
History  View  Annotate  Download (3.36 KB)
1 
/**


2 
* @file

3 
* huffman tree builder and VLC generator

4 
* Copyright (c) 2006 Konstantin Shishkov

5 
*

6 
* This file is part of Libav.

7 
*

8 
* Libav 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.

12 
*

13 
* Libav 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.

17 
*

18 
* You should have received a copy of the GNU Lesser General Public

19 
* License along with Libav; if not, write to the Free Software

20 
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA

21 
*/

22  
23 
#include "avcodec.h" 
24 
#include "get_bits.h" 
25 
#include "huffman.h" 
26  
27 
/* symbol for Huffman tree node */

28 
#define HNODE 1 
29  
30  
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, int no_zero_count) 
32 
{ 
33 
int s;

34  
35 
s = nodes[node].sym; 
36 
if(s != HNODE  (no_zero_count && !nodes[node].count)){

37 
bits[*pos] = pfx; 
38 
lens[*pos] = pl; 
39 
xlat[*pos] = s; 
40 
(*pos)++; 
41 
}else{

42 
pfx <<= 1;

43 
pl++; 
44 
get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos, 
45 
no_zero_count); 
46 
pfx = 1;

47 
get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos,

48 
no_zero_count); 
49 
} 
50 
} 
51  
52 
static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags) 
53 
{ 
54 
int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT);

55 
uint32_t bits[256];

56 
int16_t lens[256];

57 
uint8_t xlat[256];

58 
int pos = 0; 
59  
60 
get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos, no_zero_count); 
61 
return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); 
62 
} 
63  
64  
65 
/**

66 
* nodes size must be 2*nb_codes

67 
* first nb_codes nodes.count must be set

68 
*/

69 
int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, 
70 
Node *nodes, HuffCmp cmp, int flags)

71 
{ 
72 
int i, j;

73 
int cur_node;

74 
int64_t sum = 0;

75  
76 
for(i = 0; i < nb_codes; i++){ 
77 
nodes[i].sym = i; 
78 
nodes[i].n0 = 2;

79 
sum += nodes[i].count; 
80 
} 
81  
82 
if(sum >> 31) { 
83 
av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n");

84 
return 1; 
85 
} 
86 
qsort(nodes, nb_codes, sizeof(Node), cmp);

87 
cur_node = nb_codes; 
88 
nodes[nb_codes*21].count = 0; 
89 
for(i = 0; i < nb_codes*21; i += 2){ 
90 
nodes[cur_node].sym = HNODE; 
91 
nodes[cur_node].count = nodes[i].count + nodes[i+1].count;

92 
nodes[cur_node].n0 = i; 
93 
for(j = cur_node; j > 0; j){ 
94 
if(nodes[j].count > nodes[j1].count  
95 
(nodes[j].count == nodes[j1].count &&

96 
(!(flags & FF_HUFFMAN_FLAG_HNODE_FIRST)  
97 
nodes[j].n0==j1  nodes[j].n0==j2  
98 
(nodes[j].sym!=HNODE && nodes[j1].sym!=HNODE))))

99 
break;

100 
FFSWAP(Node, nodes[j], nodes[j1]);

101 
} 
102 
cur_node++; 
103 
} 
104 
if(build_huff_tree(vlc, nodes, nb_codes*22, flags) < 0){ 
105 
av_log(avctx, AV_LOG_ERROR, "Error building tree\n");

106 
return 1; 
107 
} 
108 
return 0; 
109 
} 