Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* |
2 | * Copyright (c) 2006 Konstantin Shishkov |
||
3 | * Copyright (c) 2007 Loren Merritt |
||
4 | * |
||
5 | * This file is part of FFmpeg. |
||
6 | * |
||
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. |
||
11 | * |
||
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. |
||
16 | * |
||
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 |
||
20 | */ |
||
21 | |||
22 | /** |
||
23 | * @file |
||
24 | * huffman tree builder and VLC generator |
||
25 | */ |
||
26 | |||
27 | #include "avcodec.h" |
||
28 | #include "get_bits.h" |
||
29 | #include "huffman.h" |
||
30 | |||
31 | /* symbol for Huffman tree node */ |
||
32 | #define HNODE -1 |
||
33 | |||
34 | typedef struct { |
||
35 | uint64_t val; |
||
36 | int name; |
||
37 | } HeapElem; |
||
38 | |||
39 | static void heap_sift(HeapElem *h, int root, int size) |
||
40 | { |
||
41 | while (root * 2 + 1 < size) { |
||
42 | int child = root * 2 + 1; |
||
43 | if (child < size - 1 && h[child].val > h[child+1].val) |
||
44 | child++; |
||
45 | if (h[root].val > h[child].val) { |
||
46 | FFSWAP(HeapElem, h[root], h[child]); |
||
47 | root = child; |
||
48 | } else |
||
49 | break; |
||
50 | } |
||
51 | } |
||
52 | |||
53 | void ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats) |
||
54 | { |
||
55 | HeapElem h[256]; |
||
56 | int up[2*256]; |
||
57 | int len[2*256]; |
||
58 | int offset, i, next; |
||
59 | int size = 256; |
||
60 | |||
61 | for (offset = 1; ; offset <<= 1) { |
||
62 | for (i=0; i < size; i++) { |
||
63 | h[i].name = i; |
||
64 | h[i].val = (stats[i] << 8) + offset; |
||
65 | } |
||
66 | for (i = size / 2 - 1; i >= 0; i--) |
||
67 | heap_sift(h, i, size); |
||
68 | |||
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; |
||
72 | up[h[0].name] = next; |
||
73 | h[0].val = INT64_MAX; |
||
74 | heap_sift(h, 0, size); |
||
75 | up[h[0].name] = next; |
||
76 | h[0].name = next; |
||
77 | h[0].val += min1v; |
||
78 | heap_sift(h, 0, size); |
||
79 | } |
||
80 | |||
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; |
||
87 | } |
||
88 | if (i==size) break; |
||
89 | } |
||
90 | } |
||
91 | |||
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) |
||
95 | { |
||
96 | int s; |
||
97 | |||
98 | s = nodes[node].sym; |
||
99 | if (s != HNODE || (no_zero_count && !nodes[node].count)) { |
||
100 | bits[*pos] = pfx; |
||
101 | lens[*pos] = pl; |
||
102 | xlat[*pos] = s; |
||
103 | (*pos)++; |
||
104 | } else { |
||
105 | pfx <<= 1; |
||
106 | pl++; |
||
107 | get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, |
||
108 | pos, no_zero_count); |
||
109 | pfx |= 1; |
||
110 | get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl, |
||
111 | pos, no_zero_count); |
||
112 | } |
||
113 | } |
||
114 | |||
115 | static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits) |
||
116 | { |
||
117 | int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); |
||
118 | uint32_t bits[256]; |
||
119 | int16_t lens[256]; |
||
120 | uint8_t xlat[256]; |
||
121 | int pos = 0; |
||
122 | |||
123 | get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, |
||
124 | &pos, no_zero_count); |
||
125 | return ff_init_vlc_sparse(vlc, nb_bits, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); |
||
126 | } |
||
127 | |||
128 | |||
129 | /** |
||
130 | * nodes size must be 2*nb_codes |
||
131 | * first nb_codes nodes.count must be set |
||
132 | */ |
||
133 | int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bits, |
||
134 | Node *nodes, HuffCmp cmp, int flags) |
||
135 | { |
||
136 | int i, j; |
||
137 | int cur_node; |
||
138 | int64_t sum = 0; |
||
139 | |||
140 | for (i = 0; i < nb_codes; i++) { |
||
141 | nodes[i].sym = i; |
||
142 | nodes[i].n0 = -2; |
||
143 | sum += nodes[i].count; |
||
144 | } |
||
145 | |||
146 | if (sum >> 31) { |
||
147 | av_log(avctx, AV_LOG_ERROR, |
||
148 | "Too high symbol frequencies. " |
||
149 | "Tree construction is not possible\n"); |
||
150 | return -1; |
||
151 | } |
||
152 | qsort(nodes, nb_codes, sizeof(Node), cmp); |
||
153 | cur_node = nb_codes; |
||
154 | nodes[nb_codes*2-1].count = 0; |
||
155 | for (i = 0; i < nb_codes * 2 - 1; i += 2) { |
||
156 | uint32_t cur_count = nodes[i].count + nodes[i+1].count; |
||
157 | // find correct place to insert new node, and |
||
158 | // make space for the new node while at it |
||
159 | for(j = cur_node; j > i + 2; j--){ |
||
160 | if(cur_count > nodes[j-1].count || |
||
161 | (cur_count == nodes[j-1].count && |
||
162 | !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST))) |
||
163 | break; |
||
164 | nodes[j] = nodes[j - 1]; |
||
165 | } |
||
166 | nodes[j].sym = HNODE; |
||
167 | nodes[j].count = cur_count; |
||
168 | nodes[j].n0 = i; |
||
169 | cur_node++; |
||
170 | } |
||
171 | if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits) < 0) { |
||
172 | av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); |
||
173 | return -1; |
||
174 | } |
||
175 | return 0; |
||
176 | }>>>=><=>>>><>>=><=>>> |