1498
|
1 /*
|
|
2 * Id Quake II CIN Video Decoder
|
|
3 * Copyright (C) 2003 the ffmpeg project
|
|
4 *
|
|
5 * This library is free software; you can redistribute it and/or
|
|
6 * modify it under the terms of the GNU Lesser General Public
|
|
7 * License as published by the Free Software Foundation; either
|
|
8 * version 2 of the License, or (at your option) any later version.
|
|
9 *
|
|
10 * This library is distributed in the hope that it will be useful,
|
|
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
13 * Lesser General Public License for more details.
|
|
14 *
|
|
15 * You should have received a copy of the GNU Lesser General Public
|
|
16 * License along with this library; if not, write to the Free Software
|
|
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
18 *
|
|
19 */
|
|
20
|
|
21 /**
|
|
22 * @file idcinvideo.c
|
|
23 * Id Quake II Cin Video Decoder by Dr. Tim Ferguson
|
|
24 * For more information about the Id CIN format, visit:
|
|
25 * http://www.csse.monash.edu.au/~timf/
|
|
26 *
|
1499
|
27 * This video decoder outputs PAL8 colorspace data. Interacting with this
|
|
28 * decoder is a little involved. During initialization, the demuxer must
|
|
29 * transmit the 65536-byte Huffman table(s) to the decoder via extradata.
|
|
30 * Then, whenever a palette change is encountered while demuxing the file,
|
|
31 * the demuxer must use the same extradata space to transmit an
|
|
32 * AVPaletteControl structure.
|
1498
|
33 *
|
|
34 * Id CIN video is purely Huffman-coded, intraframe-only codec. It achieves
|
|
35 * a little more compression by exploiting the fact that adjacent pixels
|
|
36 * tend to be similar.
|
|
37 *
|
|
38 * Note that this decoder could use ffmpeg's optimized VLC facilities
|
|
39 * rather than naive, tree-based Huffman decoding. However, there are 256
|
|
40 * Huffman tables. Plus, the VLC bit coding order is right -> left instead
|
|
41 * or left -> right, so all of the bits would have to be reversed. Further,
|
|
42 * the original Quake II implementation likely used a similar naive
|
|
43 * decoding algorithm and it worked fine on much lower spec machines.
|
|
44 */
|
|
45
|
|
46 #include <stdio.h>
|
|
47 #include <stdlib.h>
|
|
48 #include <string.h>
|
|
49 #include <unistd.h>
|
|
50
|
|
51 #include "common.h"
|
|
52 #include "avcodec.h"
|
|
53 #include "dsputil.h"
|
|
54
|
|
55 #define HUFFMAN_TABLE_SIZE 64 * 1024
|
|
56 #define HUF_TOKENS 256
|
|
57 #define PALETTE_COUNT 256
|
|
58
|
|
59 typedef struct
|
|
60 {
|
|
61 int count;
|
|
62 unsigned char used;
|
|
63 int children[2];
|
|
64 } hnode_t;
|
|
65
|
|
66 typedef struct IdcinContext {
|
|
67
|
|
68 AVCodecContext *avctx;
|
|
69 DSPContext dsp;
|
|
70 AVFrame frame;
|
|
71
|
|
72 unsigned char *buf;
|
|
73 int size;
|
|
74
|
|
75 unsigned char palette[PALETTE_COUNT * 4];
|
|
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 = (IdcinContext *)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 avctx->has_b_frames = 0;
|
|
159 dsputil_init(&s->dsp, avctx);
|
|
160
|
|
161 /* make sure the Huffman tables make it */
|
|
162 if (s->avctx->extradata_size != HUFFMAN_TABLE_SIZE) {
|
|
163 printf(" Id CIN video: expected extradata size of %d\n", HUFFMAN_TABLE_SIZE);
|
|
164 return -1;
|
|
165 }
|
|
166
|
|
167 /* build the 256 Huffman decode trees */
|
|
168 histograms = (unsigned char *)s->avctx->extradata;
|
|
169 for (i = 0; i < 256; i++) {
|
|
170 for(j = 0; j < HUF_TOKENS; j++)
|
|
171 s->huff_nodes[i][j].count = histograms[histogram_index++];
|
|
172 huff_build_tree(s, i);
|
|
173 }
|
|
174
|
|
175 s->frame.data[0] = NULL;
|
|
176
|
|
177 return 0;
|
|
178 }
|
|
179
|
|
180 static void idcin_decode_vlcs(IdcinContext *s)
|
|
181 {
|
|
182 hnode_t *hnodes;
|
|
183 long x, y;
|
|
184 int prev;
|
|
185 unsigned char v = 0;
|
|
186 int bit_pos, node_num, dat_pos;
|
|
187
|
|
188 prev = bit_pos = dat_pos = 0;
|
|
189 for (y = 0; y < (s->frame.linesize[0] * s->avctx->height);
|
|
190 y += s->frame.linesize[0]) {
|
|
191 for (x = y; x < y + s->avctx->width; x++) {
|
|
192 node_num = s->num_huff_nodes[prev];
|
|
193 hnodes = s->huff_nodes[prev];
|
|
194
|
|
195 while(node_num >= HUF_TOKENS) {
|
|
196 if(!bit_pos) {
|
|
197 if(dat_pos > s->size) {
|
|
198 printf("Huffman decode error.\n");
|
|
199 return;
|
|
200 }
|
|
201 bit_pos = 8;
|
|
202 v = s->buf[dat_pos++];
|
|
203 }
|
|
204
|
|
205 node_num = hnodes[node_num].children[v & 0x01];
|
|
206 v = v >> 1;
|
|
207 bit_pos--;
|
|
208 }
|
|
209
|
|
210 s->frame.data[0][x] = node_num;
|
|
211 prev = node_num;
|
|
212 }
|
|
213 }
|
|
214 }
|
|
215
|
|
216 static int idcin_decode_frame(AVCodecContext *avctx,
|
|
217 void *data, int *data_size,
|
|
218 uint8_t *buf, int buf_size)
|
|
219 {
|
|
220 IdcinContext *s = (IdcinContext *)avctx->priv_data;
|
|
221 AVPaletteControl *palette_control =
|
|
222 (AVPaletteControl *)avctx->extradata;
|
|
223 int i;
|
|
224 unsigned int *palette32;
|
|
225 int palette_index = 0;
|
|
226 unsigned char r, g, b;
|
|
227
|
|
228 s->buf = buf;
|
|
229 s->size = buf_size;
|
|
230
|
|
231 if (palette_control->palette_changed) {
|
|
232 palette32 = (unsigned int *)s->palette;
|
|
233 for (i = 0; i < PALETTE_COUNT; i++) {
|
|
234 r = palette_control->palette[palette_index++] * 1;
|
|
235 g = palette_control->palette[palette_index++] * 1;
|
|
236 b = palette_control->palette[palette_index++] * 1;
|
|
237 palette32[i] = (r << 16) | (g << 8) | (b);
|
|
238 }
|
|
239 palette_control->palette_changed = 0;
|
|
240 }
|
|
241
|
|
242 if (s->frame.data[0])
|
|
243 avctx->release_buffer(avctx, &s->frame);
|
|
244
|
|
245 if (avctx->get_buffer(avctx, &s->frame)) {
|
|
246 printf (" Id CIN Video: get_buffer() failed\n");
|
|
247 return -1;
|
|
248 }
|
|
249
|
|
250 idcin_decode_vlcs(s);
|
|
251
|
|
252 /* make the palette available on the way out */
|
|
253 memcpy(s->frame.data[1], s->palette, PALETTE_COUNT * 4);
|
|
254
|
|
255 *data_size = sizeof(AVFrame);
|
|
256 *(AVFrame*)data = s->frame;
|
|
257
|
|
258 /* report that the buffer was completely consumed */
|
|
259 return buf_size;
|
|
260 }
|
|
261
|
|
262 static int idcin_decode_end(AVCodecContext *avctx)
|
|
263 {
|
|
264 IdcinContext *s = (IdcinContext *)avctx->priv_data;
|
|
265
|
|
266 if (s->frame.data[0])
|
|
267 avctx->release_buffer(avctx, &s->frame);
|
|
268
|
|
269 return 0;
|
|
270 }
|
|
271
|
|
272 AVCodec idcin_decoder = {
|
|
273 "idcinvideo",
|
|
274 CODEC_TYPE_VIDEO,
|
|
275 CODEC_ID_IDCIN,
|
|
276 sizeof(IdcinContext),
|
|
277 idcin_decode_init,
|
|
278 NULL,
|
|
279 idcin_decode_end,
|
|
280 idcin_decode_frame,
|
|
281 CODEC_CAP_DR1,
|
|
282 };
|
|
283
|