annotate huffman.c @ 7601:69d5f318275f libavcodec

use LFG instead of Mersenne Twister for AC-3 PRNG
author jbr
date Sun, 17 Aug 2008 17:41:48 +0000
parents e0cd9697ac6d
children 524cb7f5ad2b
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 /**
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
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"
4140
a2247f4db5aa Fraps v2 and v4 support
kostya
parents: 3947
diff changeset
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
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,
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
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 }