Mercurial > libavcodec.hg
annotate huffman.c @ 6323:e6da66f378c7 libavcodec
mpegvideo.h has two function declarations with the 'inline' specifier
but no definition for those functions. The C standard requires a
definition to appear in the same translation unit for any function
declared with 'inline'. Most of the files including mpegvideo.h do not
define those functions. Fix this by removing the 'inline' specifiers
from the header.
patch by Uoti Urpala
author | diego |
---|---|
date | Sun, 03 Feb 2008 17:54:30 +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 } |