Mercurial > libavcodec.hg
comparison huffman.c @ 5820:ffac546a3861 libavcodec
moves fraps huffman decoder to its own file, making it more generic
author | aurel |
---|---|
date | Sun, 14 Oct 2007 21:19:40 +0000 |
parents | fraps.c@2b72f9bc4f06 |
children | 6ac956b341f2 |
comparison
equal
deleted
inserted
replaced
5819:88e131c2d3f8 | 5820:ffac546a3861 |
---|---|
1 /** | |
2 * @file huffman.c | |
3 * huffman tree builder and VLC generator | |
4 * Copyright (c) 2006 Konstantin Shishkov | |
5 * | |
6 * This file is part of FFmpeg. | |
7 * | |
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. | |
12 * | |
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. | |
17 * | |
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 | |
21 */ | |
22 | |
23 #include "avcodec.h" | |
24 #include "bitstream.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) | |
32 { | |
33 int s; | |
34 | |
35 s = nodes[node].sym; | |
36 if(s != HNODE || !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 pfx |= 1; | |
46 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos); | |
47 } | |
48 } | |
49 | |
50 static int build_huff_tree(VLC *vlc, Node *nodes, int head) | |
51 { | |
52 uint32_t bits[256]; | |
53 int16_t lens[256]; | |
54 uint8_t xlat[256]; | |
55 int pos = 0; | |
56 | |
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); | |
59 } | |
60 | |
61 | |
62 /** | |
63 * first nb_codes nodes.count must be set | |
64 */ | |
65 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, | |
66 Node nodes[2*nb_codes], huff_cmp_t cmp, int hnode_first) | |
67 { | |
68 int i, j; | |
69 int cur_node; | |
70 int64_t sum = 0; | |
71 | |
72 for(i = 0; i < nb_codes; i++){ | |
73 nodes[i].sym = i; | |
74 nodes[i].n0 = -2; | |
75 sum += nodes[i].count; | |
76 } | |
77 | |
78 if(sum >> 31) { | |
79 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n"); | |
80 return -1; | |
81 } | |
82 qsort(nodes, nb_codes, sizeof(Node), cmp); | |
83 cur_node = nb_codes; | |
84 for(i = 0; i < nb_codes*2-1; i += 2){ | |
85 nodes[cur_node].sym = HNODE; | |
86 nodes[cur_node].count = nodes[i].count + nodes[i+1].count; | |
87 nodes[cur_node].n0 = i; | |
88 for(j = cur_node; j > 0; j--){ | |
89 if(nodes[j].count > nodes[j-1].count || | |
90 (nodes[j].count == nodes[j-1].count && | |
91 (!hnode_first || nodes[j].n0==j-1 || nodes[j].n0==j-2 || | |
92 (nodes[j].sym!=HNODE && nodes[j-1].sym!=HNODE)))) | |
93 break; | |
94 FFSWAP(Node, nodes[j], nodes[j-1]); | |
95 } | |
96 cur_node++; | |
97 } | |
98 if(build_huff_tree(vlc, nodes, nb_codes*2-2) < 0){ | |
99 av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); | |
100 return -1; | |
101 } | |
102 return 0; | |
103 } |