Mercurial > libavcodec.hg
annotate huffman.c @ 6207:7346bcbb3d53 libavcodec
revert r11677, it is considered speed critical
author | bcoudurier |
---|---|
date | Thu, 31 Jan 2008 01:25:29 +0000 |
parents | 94fa03139210 |
children | e39e03d99d24 |
rev | line source |
---|---|
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
1 /** |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
2 * @file huffman.c |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
3 * huffman tree builder and VLC generator |
4140 | 4 * Copyright (c) 2006 Konstantin Shishkov |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
5 * |
3947
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
6 * This file is part of FFmpeg. |
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
7 * |
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
8 * FFmpeg is free software; you can redistribute it and/or |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
9 * modify it under the terms of the GNU Lesser General Public |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
10 * License as published by the Free Software Foundation; either |
3947
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
11 * version 2.1 of the License, or (at your option) any later version. |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
12 * |
3947
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
13 * FFmpeg is distributed in the hope that it will be useful, |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
16 * Lesser General Public License for more details. |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
17 * |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
18 * You should have received a copy of the GNU Lesser General Public |
3947
c8c591fe26f8
Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents:
3036
diff
changeset
|
19 * License along with FFmpeg; if not, write to the Free Software |
3036
0b546eab515d
Update licensing information: The FSF changed postal address.
diego
parents:
2967
diff
changeset
|
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
21 */ |
2967 | 22 |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
23 #include "avcodec.h" |
4140 | 24 #include "bitstream.h" |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
25 #include "huffman.h" |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
26 |
4140 | 27 /* symbol for Huffman tree node */ |
28 #define HNODE -1 | |
29 | |
30 | |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
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) |
4140 | 32 { |
33 int s; | |
34 | |
35 s = nodes[node].sym; | |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
36 if(s != HNODE || !nodes[node].count){ |
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
37 bits[*pos] = pfx; |
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
38 lens[*pos] = pl; |
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
39 xlat[*pos] = s; |
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
40 (*pos)++; |
4140 | 41 }else{ |
42 pfx <<= 1; | |
43 pl++; | |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
44 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos); |
4140 | 45 pfx |= 1; |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
46 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos); |
4140 | 47 } |
48 } | |
49 | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
50 static int build_huff_tree(VLC *vlc, Node *nodes, int head) |
4140 | 51 { |
52 uint32_t bits[256]; | |
53 int16_t lens[256]; | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
54 uint8_t xlat[256]; |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
55 int pos = 0; |
4140 | 56 |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
57 get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos); |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
58 return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); |
4140 | 59 } |
60 | |
61 | |
62 /** | |
5824 | 63 * nodes size must be 2*nb_codes |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
64 * first nb_codes nodes.count must be set |
4140 | 65 */ |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
66 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, |
5824 | 67 Node *nodes, huff_cmp_t cmp, int hnode_first) |
4140 | 68 { |
69 int i, j; | |
70 int cur_node; | |
71 int64_t sum = 0; | |
72 | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
73 for(i = 0; i < nb_codes; i++){ |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
74 nodes[i].sym = i; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
75 nodes[i].n0 = -2; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
76 sum += nodes[i].count; |
4140 | 77 } |
78 | |
79 if(sum >> 31) { | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
80 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n"); |
4140 | 81 return -1; |
82 } | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
83 qsort(nodes, nb_codes, sizeof(Node), cmp); |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
84 cur_node = nb_codes; |
5960
94fa03139210
Fix nodes[nb_codes*2-1].count being uninitialized and used to initialize
reimar
parents:
5824
diff
changeset
|
85 nodes[nb_codes*2-1].count = 0; |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
86 for(i = 0; i < nb_codes*2-1; i += 2){ |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
87 nodes[cur_node].sym = HNODE; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
88 nodes[cur_node].count = nodes[i].count + nodes[i+1].count; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
89 nodes[cur_node].n0 = i; |
4140 | 90 for(j = cur_node; j > 0; j--){ |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
91 if(nodes[j].count > nodes[j-1].count || |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
92 (nodes[j].count == nodes[j-1].count && |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
93 (!hnode_first || nodes[j].n0==j-1 || nodes[j].n0==j-2 || |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
94 (nodes[j].sym!=HNODE && nodes[j-1].sym!=HNODE)))) |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
95 break; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
96 FFSWAP(Node, nodes[j], nodes[j-1]); |
4140 | 97 } |
98 cur_node++; | |
99 } | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
100 if(build_huff_tree(vlc, nodes, nb_codes*2-2) < 0){ |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
101 av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); |
2700
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
102 return -1; |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
103 } |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
104 return 0; |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
105 } |