ffmpeg / libavcodec / idcinvideo.c @ d36beb3f
History  View  Annotate  Download (7.68 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 
* @file

24 
* id Quake II Cin Video Decoder by Dr. Tim Ferguson

25 
* For more information about the id CIN format, visit:

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

27 
*

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

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

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

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

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

33 
* AVPaletteControl structure.

34 
*

35 
* id CIN video is purely Huffmancoded, intraframeonly codec. It achieves

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

37 
* tend to be similar.

38 
*

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

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

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

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

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

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

45 
*/

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

60 
unsigned char used; 
61 
int children[2]; 
62 
} hnode; 
63  
64 
typedef struct IdcinContext { 
65  
66 
AVCodecContext *avctx; 
67 
AVFrame frame; 
68  
69 
const unsigned char *buf; 
70 
int size;

71  
72 
hnode huff_nodes[256][HUF_TOKENS*2]; 
73 
int num_huff_nodes[256]; 
74  
75 
} IdcinContext; 
76  
77 
/*

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

79 
* being assigned to a higher probability.

80 
* @return the node index of the lowest unused node, or 1 if all nodes

81 
* are used.

82 
*/

83 
static int huff_smallest_node(hnode *hnodes, int num_hnodes) { 
84 
int i;

85 
int best, best_node;

86  
87 
best = 99999999;

88 
best_node = 1;

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

91 
continue;

92 
if(!hnodes[i].count)

93 
continue;

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

95 
best = hnodes[i].count; 
96 
best_node = i; 
97 
} 
98 
} 
99  
100 
if(best_node == 1) 
101 
return 1; 
102 
hnodes[best_node].used = 1;

103 
return best_node;

104 
} 
105  
106 
/*

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

108 
*

109 
* On completion:

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

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

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

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

114 
*/

115 
static av_cold void huff_build_tree(IdcinContext *s, int prev) { 
116 
hnode *node, *hnodes; 
117 
int num_hnodes, i;

118  
119 
num_hnodes = HUF_TOKENS; 
120 
hnodes = s>huff_nodes[prev]; 
121 
for(i = 0; i < HUF_TOKENS * 2; i++) 
122 
hnodes[i].used = 0;

123  
124 
while (1) { 
125 
node = &hnodes[num_hnodes]; /* next free node */

126  
127 
/* pick two lowest counts */

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

129 
if(node>children[0] == 1) 
130 
break; /* reached the root node */ 
131  
132 
node>children[1] = huff_smallest_node(hnodes, num_hnodes);

133 
if(node>children[1] == 1) 
134 
break; /* reached the root node */ 
135  
136 
/* combine nodes probability for new node */

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

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

139 
num_hnodes++; 
140 
} 
141  
142 
s>num_huff_nodes[prev] = num_hnodes  1;

143 
} 
144  
145 
static av_cold int idcin_decode_init(AVCodecContext *avctx) 
146 
{ 
147 
IdcinContext *s = avctx>priv_data; 
148 
int i, j, histogram_index = 0; 
149 
unsigned char *histograms; 
150  
151 
s>avctx = avctx; 
152 
avctx>pix_fmt = PIX_FMT_PAL8; 
153  
154 
/* make sure the Huffman tables make it */

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

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

157 
return 1; 
158 
} 
159  
160 
/* build the 256 Huffman decode trees */

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

177 
int prev;

178 
unsigned char v = 0; 
179 
int bit_pos, node_num, dat_pos;

180  
181 
prev = bit_pos = dat_pos = 0;

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

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

185 
node_num = s>num_huff_nodes[prev]; 
186 
hnodes = s>huff_nodes[prev]; 
187  
188 
while(node_num >= HUF_TOKENS) {

189 
if(!bit_pos) {

190 
if(dat_pos >= s>size) {

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

192 
return;

193 
} 
194 
bit_pos = 8;

195 
v = s>buf[dat_pos++]; 
196 
} 
197  
198 
node_num = hnodes[node_num].children[v & 0x01];

199 
v = v >> 1;

200 
bit_pos; 
201 
} 
202  
203 
s>frame.data[0][x] = node_num;

204 
prev = node_num; 
205 
} 
206 
} 
207 
} 
208  
209 
static int idcin_decode_frame(AVCodecContext *avctx, 
210 
void *data, int *data_size, 
211 
AVPacket *avpkt) 
212 
{ 
213 
const uint8_t *buf = avpkt>data;

214 
int buf_size = avpkt>size;

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

225 
av_log(avctx, AV_LOG_ERROR, " id CIN Video: get_buffer() failed\n");

226 
return 1; 
227 
} 
228  
229 
idcin_decode_vlcs(s); 
230  
231 
/* make the palette available on the way out */

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

234 
if (palette_control>palette_changed) {

235 
palette_control>palette_changed = 0;

236 
s>frame.palette_has_changed = 1;

237 
} 
238  
239 
*data_size = sizeof(AVFrame);

240 
*(AVFrame*)data = s>frame; 
241  
242 
/* report that the buffer was completely consumed */

243 
return buf_size;

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

258 
AVMEDIA_TYPE_VIDEO, 
259 
CODEC_ID_IDCIN, 
260 
sizeof(IdcinContext),

261 
idcin_decode_init, 
262 
NULL,

263 
idcin_decode_end, 
264 
idcin_decode_frame, 
265 
CODEC_CAP_DR1, 
266 
.long_name = NULL_IF_CONFIG_SMALL("id Quake II CIN video"),

267 
}; 
268 