ffmpeg / libavcodec / idcinvideo.c @ 2029f312
History  View  Annotate  Download (7.65 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 "avcodec.h" 
54 
#include "dsputil.h" 
55  
56 
#define HUFFMAN_TABLE_SIZE 64 * 1024 
57 
#define HUF_TOKENS 256 
58 
#define PALETTE_COUNT 256 
59  
60 
typedef struct 
61 
{ 
62 
int count;

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

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

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

83 
* being assigned to a higher probability.

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

85 
* are used.

86 
*/

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

89 
int best, best_node;

90  
91 
best = 99999999;

92 
best_node = 1;

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

95 
continue;

96 
if(!hnodes[i].count)

97 
continue;

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

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

107 
return best_node;

108 
} 
109  
110 
/*

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

112 
*

113 
* On completion:

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

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

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

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

118 
*/

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

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

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

130  
131 
/* pick two lowest counts */

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

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

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

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

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

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

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

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

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

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

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

182 
int prev;

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

185  
186 
prev = bit_pos = dat_pos = 0;

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

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

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

194 
if(!bit_pos) {

195 
if(dat_pos >= s>size) {

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

197 
return;

198 
} 
199 
bit_pos = 8;

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

204 
v = v >> 1;

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

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

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

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

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

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

237 
if (palette_control>palette_changed) {

238 
palette_control>palette_changed = 0;

239 
s>frame.palette_has_changed = 1;

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

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

246 
return buf_size;

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

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

264 
idcin_decode_init, 
265 
NULL,

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