annotate huffman.c @ 11560:8a4984c5cacc libavcodec

Define AVMediaType enum, and use it instead of enum CodecType, which is deprecated and will be dropped at the next major bump.
author stefano
date Tue, 30 Mar 2010 23:30:55 +0000
parents 0dce4fe6e6f3
children 7dd2a45249a9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5820
ffac546a3861 moves fraps huffman decoder to its own file, making it more generic
aurel
parents: 5215
diff changeset
1 /**
8718
e9d9d946f213 Use full internal pathname in doxygen @file directives.
diego
parents: 8299
diff changeset
2 * @file libavcodec/huffman.c
5820
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
ef2149182f1c COSMETICS: Remove all trailing whitespace.
diego
parents: 2701
diff changeset
22
2700
485571c9182f Fraps FPS1 video decoder (v1 & v2), courtesy of Roine Gustafsson <roine
melanson
parents:
diff changeset
23 #include "avcodec.h"
9428
0dce4fe6e6f3 Rename bitstream.h to get_bits.h.
stefano
parents: 8718
diff changeset
24 #include "get_bits.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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
27 /* symbol for Huffman tree node */
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
28 #define HNODE -1
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
29
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
30
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
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, int no_zero_count)
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
32 {
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
33 int s;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
34
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
35 s = nodes[node].sym;
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
41 }else{
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
42 pfx <<= 1;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
43 pl++;
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
44 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, pos,
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
45 no_zero_count);
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
46 pfx |= 1;
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
47 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0+1, pfx, pl, pos,
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
48 no_zero_count);
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
49 }
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
50 }
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
51
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
52 static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags)
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
53 {
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
54 int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT);
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
55 uint32_t bits[256];
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
59
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
62 }
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
63
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
64
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
65 /**
5824
6ac956b341f2 Cygwin don't like this function declaration.
aurel
parents: 5820
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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,
8299
524cb7f5ad2b avoid POSIX reserved _t suffix
aurel
parents: 6473
diff changeset
70 Node *nodes, HuffCmp cmp, int flags)
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
71 {
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
72 int i, j;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
73 int cur_node;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
74 int64_t sum = 0;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
80 }
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
81
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
84 return -1;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
101 }
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
102 cur_node++;
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
103 }
6473
e0cd9697ac6d huffman: add a zero_count flag and use it in fraps
aurel
parents: 6472
diff changeset
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 }