2 * Wing Commander/Xan Video Decoder
3 * Copyright (C) 2003 the ffmpeg project
5 * This file is part of Libav.
7 * Libav 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.
12 * Libav 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.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with Libav; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * Xan video decoder for Wing Commander III computer game
25 * by Mario Brito (mbrito@student.dei.uc.pt)
26 * and Mike Melanson (melanson@pcisys.net)
28 * The xan_wc3 decoder outputs PAL8 data.
35 #include "libavutil/intreadwrite.h"
37 #include "bytestream.h"
38 #define ALT_BITSTREAM_READER_LE
40 // for av_memcpy_backptr
41 #include "libavutil/lzo.h"
43 #define RUNTIME_GAMMA 0
45 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
46 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
47 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
48 #define PALETTE_COUNT 256
49 #define PALETTE_SIZE (PALETTE_COUNT * 3)
50 #define PALETTES_MAX 256
52 typedef struct XanContext {
54 AVCodecContext *avctx;
56 AVFrame current_frame;
58 const unsigned char *buf;
62 unsigned char *buffer1;
64 unsigned char *buffer2;
75 static av_cold int xan_decode_init(AVCodecContext *avctx)
77 XanContext *s = avctx->priv_data;
82 avctx->pix_fmt = PIX_FMT_PAL8;
84 s->buffer1_size = avctx->width * avctx->height;
85 s->buffer1 = av_malloc(s->buffer1_size);
87 return AVERROR(ENOMEM);
88 s->buffer2_size = avctx->width * avctx->height;
89 s->buffer2 = av_malloc(s->buffer2_size + 130);
91 av_freep(&s->buffer1);
92 return AVERROR(ENOMEM);
98 static int xan_huffman_decode(unsigned char *dest, int dest_len,
99 const unsigned char *src, int src_len)
101 unsigned char byte = *src++;
102 unsigned char ival = byte + 0x16;
103 const unsigned char * ptr = src + byte*2;
104 int ptr_len = src_len - 1 - byte*2;
105 unsigned char val = ival;
106 unsigned char *dest_end = dest + dest_len;
110 return AVERROR_INVALIDDATA;
112 init_get_bits(&gb, ptr, ptr_len * 8);
114 while ( val != 0x16 ) {
115 val = src[val - 0x17 + get_bits1(&gb) * byte];
118 if (dest >= dest_end)
129 * unpack simple compression
131 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
133 static void xan_unpack(unsigned char *dest, const unsigned char *src, int dest_len)
135 unsigned char opcode;
137 unsigned char *dest_end = dest + dest_len;
139 while (dest < dest_end) {
144 if ( (opcode & 0x80) == 0 ) {
148 back = ((opcode & 0x60) << 3) + *src++ + 1;
149 size2 = ((opcode & 0x1c) >> 2) + 3;
151 } else if ( (opcode & 0x40) == 0 ) {
155 back = (bytestream_get_be16(&src) & 0x3fff) + 1;
156 size2 = (opcode & 0x3f) + 4;
162 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
163 size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
164 if (size + size2 > dest_end - dest)
167 memcpy(dest, src, size); dest += size; src += size;
168 av_memcpy_backptr(dest, back, size2);
171 int finish = opcode >= 0xfc;
172 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
174 memcpy(dest, src, size); dest += size; src += size;
181 static inline void xan_wc3_output_pixel_run(XanContext *s,
182 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
188 int width = s->avctx->width;
189 unsigned char *palette_plane;
191 palette_plane = s->current_frame.data[0];
192 stride = s->current_frame.linesize[0];
193 line_inc = stride - width;
194 index = y * stride + x;
196 while(pixel_count && (index < s->frame_size)) {
197 int count = FFMIN(pixel_count, width - current_x);
198 memcpy(palette_plane + index, pixel_buffer, count);
199 pixel_count -= count;
201 pixel_buffer += count;
204 if (current_x >= width) {
211 static inline void xan_wc3_copy_pixel_run(XanContext *s,
212 int x, int y, int pixel_count, int motion_x, int motion_y)
216 int curframe_index, prevframe_index;
217 int curframe_x, prevframe_x;
218 int width = s->avctx->width;
219 unsigned char *palette_plane, *prev_palette_plane;
221 palette_plane = s->current_frame.data[0];
222 prev_palette_plane = s->last_frame.data[0];
223 stride = s->current_frame.linesize[0];
224 line_inc = stride - width;
225 curframe_index = y * stride + x;
227 prevframe_index = (y + motion_y) * stride + x + motion_x;
228 prevframe_x = x + motion_x;
229 while(pixel_count && (curframe_index < s->frame_size)) {
230 int count = FFMIN3(pixel_count, width - curframe_x, width - prevframe_x);
232 memcpy(palette_plane + curframe_index, prev_palette_plane + prevframe_index, count);
233 pixel_count -= count;
234 curframe_index += count;
235 prevframe_index += count;
237 prevframe_x += count;
239 if (curframe_x >= width) {
240 curframe_index += line_inc;
244 if (prevframe_x >= width) {
245 prevframe_index += line_inc;
251 static int xan_wc3_decode_frame(XanContext *s) {
253 int width = s->avctx->width;
254 int height = s->avctx->height;
255 int total_pixels = width * height;
256 unsigned char opcode;
257 unsigned char flag = 0;
259 int motion_x, motion_y;
262 unsigned char *opcode_buffer = s->buffer1;
263 int opcode_buffer_size = s->buffer1_size;
264 const unsigned char *imagedata_buffer = s->buffer2;
266 /* pointers to segments inside the compressed chunk */
267 const unsigned char *huffman_segment;
268 const unsigned char *size_segment;
269 const unsigned char *vector_segment;
270 const unsigned char *imagedata_segment;
271 int huffman_offset, size_offset, vector_offset, imagedata_offset;
274 return AVERROR_INVALIDDATA;
276 huffman_offset = AV_RL16(&s->buf[0]);
277 size_offset = AV_RL16(&s->buf[2]);
278 vector_offset = AV_RL16(&s->buf[4]);
279 imagedata_offset = AV_RL16(&s->buf[6]);
281 if (huffman_offset >= s->size ||
282 size_offset >= s->size ||
283 vector_offset >= s->size ||
284 imagedata_offset >= s->size)
285 return AVERROR_INVALIDDATA;
287 huffman_segment = s->buf + huffman_offset;
288 size_segment = s->buf + size_offset;
289 vector_segment = s->buf + vector_offset;
290 imagedata_segment = s->buf + imagedata_offset;
292 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
293 huffman_segment, s->size - huffman_offset) < 0)
294 return AVERROR_INVALIDDATA;
296 if (imagedata_segment[0] == 2)
297 xan_unpack(s->buffer2, &imagedata_segment[1], s->buffer2_size);
299 imagedata_buffer = &imagedata_segment[1];
301 /* use the decoded data segments to build the frame */
303 while (total_pixels) {
305 opcode = *opcode_buffer++;
332 size += (opcode - 10);
337 size = *size_segment++;
342 size = AV_RB16(&size_segment[0]);
348 size = AV_RB24(size_segment);
356 /* run of (size) pixels is unchanged from last frame */
357 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
359 /* output a run of pixels from imagedata_buffer */
360 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
361 imagedata_buffer += size;
364 /* run-based motion compensation from last frame */
365 motion_x = sign_extend(*vector_segment >> 4, 4);
366 motion_y = sign_extend(*vector_segment & 0xF, 4);
369 /* copy a run of pixels from the previous frame */
370 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
375 /* coordinate accounting */
376 total_pixels -= size;
377 y += (x + size) / width;
378 x = (x + size) % width;
384 static inline unsigned mul(unsigned a, unsigned b)
386 return (a * b) >> 16;
389 static inline unsigned pow4(unsigned a)
391 unsigned square = mul(a, a);
392 return mul(square, square);
395 static inline unsigned pow5(unsigned a)
397 return mul(pow4(a), a);
400 static uint8_t gamma_corr(uint8_t in) {
401 unsigned lo, hi = 0xff40, target;
403 in = (in << 2) | (in >> 6);
404 /* equivalent float code:
407 return round(pow(in / 256.0, 0.8) * 256);
409 lo = target = in << 8;
411 unsigned mid = (lo + hi) >> 1;
412 unsigned pow = pow5(mid);
413 if (pow > target) hi = mid;
416 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
420 * This is a gamma correction that xan3 applies to all palette entries.
422 * There is a peculiarity, namely that the values are clamped to 253 -
423 * it seems likely that this table was calculated by a buggy fixed-point
424 * implementation, the one above under RUNTIME_GAMMA behaves like this for
426 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
427 * and thus pow(x, 0.8) is still easy to calculate.
428 * Also, the input values are first rotated to the left by 2.
430 static const uint8_t gamma_lookup[256] = {
431 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
432 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
433 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
434 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
435 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
436 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
437 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
438 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
439 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
440 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
441 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
442 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
443 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
444 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
445 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
446 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
447 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
448 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
449 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
450 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
451 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
452 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
453 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
454 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
455 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
456 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
457 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
458 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
459 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
460 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
461 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
462 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
466 static int xan_decode_frame(AVCodecContext *avctx,
467 void *data, int *data_size,
470 const uint8_t *buf = avpkt->data;
471 int ret, buf_size = avpkt->size;
472 XanContext *s = avctx->priv_data;
474 if (avctx->codec->id == CODEC_ID_XAN_WC3) {
475 const uint8_t *buf_end = buf + buf_size;
477 while (buf_end - buf > 8 && tag != VGA__TAG) {
482 tag = bytestream_get_le32(&buf);
483 size = bytestream_get_be32(&buf);
484 size = FFMIN(size, buf_end - buf);
487 if (size < PALETTE_SIZE)
488 return AVERROR_INVALIDDATA;
489 if (s->palettes_count >= PALETTES_MAX)
490 return AVERROR_INVALIDDATA;
491 tmpptr = av_realloc(s->palettes, (s->palettes_count + 1) * AVPALETTE_SIZE);
493 return AVERROR(ENOMEM);
494 s->palettes = tmpptr;
495 tmpptr += s->palettes_count * AVPALETTE_COUNT;
496 for (i = 0; i < PALETTE_COUNT; i++) {
498 int r = gamma_corr(*buf++);
499 int g = gamma_corr(*buf++);
500 int b = gamma_corr(*buf++);
502 int r = gamma_lookup[*buf++];
503 int g = gamma_lookup[*buf++];
504 int b = gamma_lookup[*buf++];
506 *tmpptr++ = (r << 16) | (g << 8) | b;
512 return AVERROR_INVALIDDATA;
513 new_pal = bytestream_get_le32(&buf);
514 if (new_pal < s->palettes_count) {
515 s->cur_palette = new_pal;
517 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
526 buf_size = buf_end - buf;
528 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
529 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
532 s->current_frame.reference = 3;
535 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
537 memcpy(s->current_frame.data[1], s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
542 if (xan_wc3_decode_frame(s) < 0)
543 return AVERROR_INVALIDDATA;
545 /* release the last frame if it is allocated */
546 if (s->last_frame.data[0])
547 avctx->release_buffer(avctx, &s->last_frame);
549 *data_size = sizeof(AVFrame);
550 *(AVFrame*)data = s->current_frame;
553 FFSWAP(AVFrame, s->current_frame, s->last_frame);
555 /* always report that the buffer was completely consumed */
559 static av_cold int xan_decode_end(AVCodecContext *avctx)
561 XanContext *s = avctx->priv_data;
563 /* release the frames */
564 if (s->last_frame.data[0])
565 avctx->release_buffer(avctx, &s->last_frame);
566 if (s->current_frame.data[0])
567 avctx->release_buffer(avctx, &s->current_frame);
569 av_freep(&s->buffer1);
570 av_freep(&s->buffer2);
571 av_freep(&s->palettes);
576 AVCodec ff_xan_wc3_decoder = {
578 .type = AVMEDIA_TYPE_VIDEO,
579 .id = CODEC_ID_XAN_WC3,
580 .priv_data_size = sizeof(XanContext),
581 .init = xan_decode_init,
582 .close = xan_decode_end,
583 .decode = xan_decode_frame,
584 .capabilities = CODEC_CAP_DR1,
585 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),