ffmpeg / libavcodec / idcinvideo.c @ e4141433
History  View  Annotate  Download (7.67 KB)
1 
/*


2 
* Id Quake II CIN Video Decoder

3 
* Copyright (C) 2003 the ffmpeg project

4 
*

5 
* This file is part of FFmpeg.

6 
*

7 
* FFmpeg is free software; you can redistribute it and/or

8 
* modify it under the terms of the GNU Lesser General Public

9 
* License as published by the Free Software Foundation; either

10 
* version 2.1 of the License, or (at your option) any later version.

11 
*

12 
* FFmpeg is distributed in the hope that it will be useful,

13 
* but WITHOUT ANY WARRANTY; without even the implied warranty of

14 
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

15 
* Lesser General Public License for more details.

16 
*

17 
* You should have received a copy of the GNU Lesser General Public

18 
* License along with FFmpeg; if not, write to the Free Software

19 
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA

20 
*

21 
*/

22  
23 
/**

24 
* @file idcinvideo.c

25 
* Id Quake II Cin Video Decoder by Dr. Tim Ferguson

26 
* For more information about the Id CIN format, visit:

27 
* http://www.csse.monash.edu.au/~timf/

28 
*

29 
* This video decoder outputs PAL8 colorspace data. Interacting with this

30 
* decoder is a little involved. During initialization, the demuxer must

31 
* transmit the 65536byte Huffman table(s) to the decoder via extradata.

32 
* Then, whenever a palette change is encountered while demuxing the file,

33 
* the demuxer must use the same extradata space to transmit an

34 
* AVPaletteControl structure.

35 
*

36 
* Id CIN video is purely Huffmancoded, intraframeonly codec. It achieves

37 
* a little more compression by exploiting the fact that adjacent pixels

38 
* tend to be similar.

39 
*

40 
* Note that this decoder could use ffmpeg's optimized VLC facilities

41 
* rather than naive, treebased Huffman decoding. However, there are 256

42 
* Huffman tables. Plus, the VLC bit coding order is right > left instead

43 
* or left > right, so all of the bits would have to be reversed. Further,

44 
* the original Quake II implementation likely used a similar naive

45 
* decoding algorithm and it worked fine on much lower spec machines.

46 
*/

47  
48 
#include <stdio.h> 
49 
#include <stdlib.h> 
50 
#include <string.h> 
51 
#include <unistd.h> 
52  
53 
#include "common.h" 
54 
#include "avcodec.h" 
55 
#include "dsputil.h" 
56  
57 
#define HUFFMAN_TABLE_SIZE 64 * 1024 
58 
#define HUF_TOKENS 256 
59 
#define PALETTE_COUNT 256 
60  
61 
typedef struct 
62 
{ 
63 
int count;

64 
unsigned char used; 
65 
int children[2]; 
66 
} hnode_t; 
67  
68 
typedef struct IdcinContext { 
69  
70 
AVCodecContext *avctx; 
71 
DSPContext dsp; 
72 
AVFrame frame; 
73  
74 
unsigned char *buf; 
75 
int size;

76  
77 
hnode_t huff_nodes[256][HUF_TOKENS*2]; 
78 
int num_huff_nodes[256]; 
79  
80 
} IdcinContext; 
81  
82 
/*

83 
* Find the lowest probability node in a Huffman table, and mark it as

84 
* being assigned to a higher probability.

85 
* Returns the node index of the lowest unused node, or 1 if all nodes

86 
* are used.

87 
*/

88 
static int huff_smallest_node(hnode_t *hnodes, int num_hnodes) { 
89 
int i;

90 
int best, best_node;

91  
92 
best = 99999999;

93 
best_node = 1;

94 
for(i = 0; i < num_hnodes; i++) { 
95 
if(hnodes[i].used)

96 
continue;

97 
if(!hnodes[i].count)

98 
continue;

99 
if(hnodes[i].count < best) {

100 
best = hnodes[i].count; 
101 
best_node = i; 
102 
} 
103 
} 
104  
105 
if(best_node == 1) 
106 
return 1; 
107 
hnodes[best_node].used = 1;

108 
return best_node;

109 
} 
110  
111 
/*

112 
* Build the Huffman tree using the generated/loaded probabilities histogram.

113 
*

114 
* On completion:

115 
* huff_nodes[prev][i < HUF_TOKENS]  are the nodes at the base of the tree.

116 
* huff_nodes[prev][i >= HUF_TOKENS]  are used to construct the tree.

117 
* num_huff_nodes[prev]  contains the index to the root node of the tree.

118 
* That is: huff_nodes[prev][num_huff_nodes[prev]] is the root node.

119 
*/

120 
static void huff_build_tree(IdcinContext *s, int prev) { 
121 
hnode_t *node, *hnodes; 
122 
int num_hnodes, i;

123  
124 
num_hnodes = HUF_TOKENS; 
125 
hnodes = s>huff_nodes[prev]; 
126 
for(i = 0; i < HUF_TOKENS * 2; i++) 
127 
hnodes[i].used = 0;

128  
129 
while (1) { 
130 
node = &hnodes[num_hnodes]; /* next free node */

131  
132 
/* pick two lowest counts */

133 
node>children[0] = huff_smallest_node(hnodes, num_hnodes);

134 
if(node>children[0] == 1) 
135 
break; /* reached the root node */ 
136  
137 
node>children[1] = huff_smallest_node(hnodes, num_hnodes);

138 
if(node>children[1] == 1) 
139 
break; /* reached the root node */ 
140  
141 
/* combine nodes probability for new node */

142 
node>count = hnodes[node>children[0]].count +

143 
hnodes[node>children[1]].count;

144 
num_hnodes++; 
145 
} 
146  
147 
s>num_huff_nodes[prev] = num_hnodes  1;

148 
} 
149  
150 
static int idcin_decode_init(AVCodecContext *avctx) 
151 
{ 
152 
IdcinContext *s = avctx>priv_data; 
153 
int i, j, histogram_index = 0; 
154 
unsigned char *histograms; 
155  
156 
s>avctx = avctx; 
157 
avctx>pix_fmt = PIX_FMT_PAL8; 
158 
dsputil_init(&s>dsp, avctx); 
159  
160 
/* make sure the Huffman tables make it */

161 
if (s>avctx>extradata_size != HUFFMAN_TABLE_SIZE) {

162 
av_log(s>avctx, AV_LOG_ERROR, " Id CIN video: expected extradata size of %d\n", HUFFMAN_TABLE_SIZE);

163 
return 1; 
164 
} 
165  
166 
/* build the 256 Huffman decode trees */

167 
histograms = (unsigned char *)s>avctx>extradata; 
168 
for (i = 0; i < 256; i++) { 
169 
for(j = 0; j < HUF_TOKENS; j++) 
170 
s>huff_nodes[i][j].count = histograms[histogram_index++]; 
171 
huff_build_tree(s, i); 
172 
} 
173  
174 
s>frame.data[0] = NULL; 
175  
176 
return 0; 
177 
} 
178  
179 
static void idcin_decode_vlcs(IdcinContext *s) 
180 
{ 
181 
hnode_t *hnodes; 
182 
long x, y;

183 
int prev;

184 
unsigned char v = 0; 
185 
int bit_pos, node_num, dat_pos;

186  
187 
prev = bit_pos = dat_pos = 0;

188 
for (y = 0; y < (s>frame.linesize[0] * s>avctx>height); 
189 
y += s>frame.linesize[0]) {

190 
for (x = y; x < y + s>avctx>width; x++) {

191 
node_num = s>num_huff_nodes[prev]; 
192 
hnodes = s>huff_nodes[prev]; 
193  
194 
while(node_num >= HUF_TOKENS) {

195 
if(!bit_pos) {

196 
if(dat_pos >= s>size) {

197 
av_log(s>avctx, AV_LOG_ERROR, "Huffman decode error.\n");

198 
return;

199 
} 
200 
bit_pos = 8;

201 
v = s>buf[dat_pos++]; 
202 
} 
203  
204 
node_num = hnodes[node_num].children[v & 0x01];

205 
v = v >> 1;

206 
bit_pos; 
207 
} 
208  
209 
s>frame.data[0][x] = node_num;

210 
prev = node_num; 
211 
} 
212 
} 
213 
} 
214  
215 
static int idcin_decode_frame(AVCodecContext *avctx, 
216 
void *data, int *data_size, 
217 
uint8_t *buf, int buf_size)

218 
{ 
219 
IdcinContext *s = avctx>priv_data; 
220 
AVPaletteControl *palette_control = avctx>palctrl; 
221  
222 
s>buf = buf; 
223 
s>size = buf_size; 
224  
225 
if (s>frame.data[0]) 
226 
avctx>release_buffer(avctx, &s>frame); 
227  
228 
if (avctx>get_buffer(avctx, &s>frame)) {

229 
av_log(avctx, AV_LOG_ERROR, " Id CIN Video: get_buffer() failed\n");

230 
return 1; 
231 
} 
232  
233 
idcin_decode_vlcs(s); 
234  
235 
/* make the palette available on the way out */

236 
memcpy(s>frame.data[1], palette_control>palette, PALETTE_COUNT * 4); 
237 
/* If palette changed inform application*/

238 
if (palette_control>palette_changed) {

239 
palette_control>palette_changed = 0;

240 
s>frame.palette_has_changed = 1;

241 
} 
242  
243 
*data_size = sizeof(AVFrame);

244 
*(AVFrame*)data = s>frame; 
245  
246 
/* report that the buffer was completely consumed */

247 
return buf_size;

248 
} 
249  
250 
static int idcin_decode_end(AVCodecContext *avctx) 
251 
{ 
252 
IdcinContext *s = avctx>priv_data; 
253  
254 
if (s>frame.data[0]) 
255 
avctx>release_buffer(avctx, &s>frame); 
256  
257 
return 0; 
258 
} 
259  
260 
AVCodec idcin_decoder = { 
261 
"idcinvideo",

262 
CODEC_TYPE_VIDEO, 
263 
CODEC_ID_IDCIN, 
264 
sizeof(IdcinContext),

265 
idcin_decode_init, 
266 
NULL,

267 
idcin_decode_end, 
268 
idcin_decode_frame, 
269 
CODEC_CAP_DR1, 
270 
}; 
271 