Mercurial > libavcodec.hg
annotate huffman.c @ 7205:68528efbc91f libavcodec
Document av_find_opt().
author | stefano |
---|---|
date | Sun, 06 Jul 2008 08:16:50 +0000 |
parents | e0cd9697ac6d |
children | 524cb7f5ad2b |
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 | |
6473 | 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) |
4140 | 32 { |
33 int s; | |
34 | |
35 s = nodes[node].sym; | |
6473 | 36 if(s != HNODE || (no_zero_count && !nodes[node].count)){ |
4142
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++; | |
6473 | 44 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos, |
45 no_zero_count); | |
4140 | 46 pfx |= 1; |
6473 | 47 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos, |
48 no_zero_count); | |
4140 | 49 } |
50 } | |
51 | |
6473 | 52 static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags) |
4140 | 53 { |
6473 | 54 int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); |
4140 | 55 uint32_t bits[256]; |
56 int16_t lens[256]; | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
57 uint8_t xlat[256]; |
4142
79ddfdee291d
Correct support for Fraps v4 (and Huffman tree for < 256 symbols)
kostya
parents:
4141
diff
changeset
|
58 int pos = 0; |
4140 | 59 |
6473 | 60 get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, &pos, no_zero_count); |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
61 return init_vlc_sparse(vlc, 9, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); |
4140 | 62 } |
63 | |
64 | |
65 /** | |
5824 | 66 * 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
|
67 * first nb_codes nodes.count must be set |
4140 | 68 */ |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
69 int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, |
6472
e39e03d99d24
huffman: pass hnode_first as a flag instead of as an argument on its own
aurel
parents:
5960
diff
changeset
|
70 Node *nodes, huff_cmp_t cmp, int flags) |
4140 | 71 { |
72 int i, j; | |
73 int cur_node; | |
74 int64_t sum = 0; | |
75 | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
76 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
|
77 nodes[i].sym = i; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
78 nodes[i].n0 = -2; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
79 sum += nodes[i].count; |
4140 | 80 } |
81 | |
82 if(sum >> 31) { | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
83 av_log(avctx, AV_LOG_ERROR, "Too high symbol frequencies. Tree construction is not possible\n"); |
4140 | 84 return -1; |
85 } | |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
86 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
|
87 cur_node = nb_codes; |
5960
94fa03139210
Fix nodes[nb_codes*2-1].count being uninitialized and used to initialize
reimar
parents:
5824
diff
changeset
|
88 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
|
89 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
|
90 nodes[cur_node].sym = HNODE; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
91 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
|
92 nodes[cur_node].n0 = i; |
4140 | 93 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
|
94 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
|
95 (nodes[j].count == nodes[j-1].count && |
6472
e39e03d99d24
huffman: pass hnode_first as a flag instead of as an argument on its own
aurel
parents:
5960
diff
changeset
|
96 (!(flags & FF_HUFFMAN_FLAG_HNODE_FIRST) || |
e39e03d99d24
huffman: pass hnode_first as a flag instead of as an argument on its own
aurel
parents:
5960
diff
changeset
|
97 nodes[j].n0==j-1 || nodes[j].n0==j-2 || |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
98 (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
|
99 break; |
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
100 FFSWAP(Node, nodes[j], nodes[j-1]); |
4140 | 101 } |
102 cur_node++; | |
103 } | |
6473 | 104 if(build_huff_tree(vlc, nodes, nb_codes*2-2, flags) < 0){ |
5820
ffac546a3861
moves fraps huffman decoder to its own file, making it more generic
aurel
parents:
5215
diff
changeset
|
105 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
|
106 return -1; |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
107 } |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
108 return 0; |
485571c9182f
Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff
changeset
|
109 } |