2 * Wing Commander/Xan Video Decoder
3 * Copyright (C) 2003 the ffmpeg project
5 * This file is part of FFmpeg.
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.
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.
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 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"
36 #include "libavutil/mem.h"
38 #include "bytestream.h"
39 #define BITSTREAM_READER_LE
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 = AV_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);
94 avcodec_get_frame_defaults(&s->last_frame);
95 avcodec_get_frame_defaults(&s->current_frame);
100 static int xan_huffman_decode(unsigned char *dest, int dest_len,
101 const unsigned char *src, int src_len)
103 unsigned char byte = *src++;
104 unsigned char ival = byte + 0x16;
105 const unsigned char * ptr = src + byte*2;
106 int ptr_len = src_len - 1 - byte*2;
107 unsigned char val = ival;
108 unsigned char *dest_end = dest + dest_len;
112 return AVERROR_INVALIDDATA;
114 init_get_bits(&gb, ptr, ptr_len * 8);
116 while (val != 0x16) {
117 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
119 return AVERROR_INVALIDDATA;
123 if (dest >= dest_end)
134 * unpack simple compression
136 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
138 static void xan_unpack(unsigned char *dest, int dest_len,
139 const unsigned char *src, int src_len)
141 unsigned char opcode;
143 unsigned char *dest_org = dest;
144 unsigned char *dest_end = dest + dest_len;
147 bytestream2_init(&ctx, src, src_len);
148 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
149 opcode = bytestream2_get_byte(&ctx);
153 if ((opcode & 0x80) == 0) {
156 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
157 size2 = ((opcode & 0x1c) >> 2) + 3;
158 } else if ((opcode & 0x40) == 0) {
159 size = bytestream2_peek_byte(&ctx) >> 6;
161 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
162 size2 = (opcode & 0x3f) + 4;
166 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
167 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
170 if (dest_end - dest < size + size2 ||
171 dest + size - dest_org < back ||
172 bytestream2_get_bytes_left(&ctx) < size)
174 bytestream2_get_buffer(&ctx, dest, size);
176 av_memcpy_backptr(dest, back, size2);
179 int finish = opcode >= 0xfc;
180 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
182 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
184 bytestream2_get_buffer(&ctx, dest, size);
192 static inline void xan_wc3_output_pixel_run(XanContext *s,
193 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
199 int width = s->avctx->width;
200 unsigned char *palette_plane;
202 palette_plane = s->current_frame.data[0];
203 stride = s->current_frame.linesize[0];
204 line_inc = stride - width;
205 index = y * stride + x;
207 while (pixel_count && index < s->frame_size) {
208 int count = FFMIN(pixel_count, width - current_x);
209 memcpy(palette_plane + index, pixel_buffer, count);
210 pixel_count -= count;
212 pixel_buffer += count;
215 if (current_x >= width) {
222 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
223 int pixel_count, int motion_x,
228 int curframe_index, prevframe_index;
229 int curframe_x, prevframe_x;
230 int width = s->avctx->width;
231 unsigned char *palette_plane, *prev_palette_plane;
233 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
234 x + motion_x < 0 || x + motion_x >= s->avctx->width)
237 palette_plane = s->current_frame.data[0];
238 prev_palette_plane = s->last_frame.data[0];
239 if (!prev_palette_plane)
240 prev_palette_plane = palette_plane;
241 stride = s->current_frame.linesize[0];
242 line_inc = stride - width;
243 curframe_index = y * stride + x;
245 prevframe_index = (y + motion_y) * stride + x + motion_x;
246 prevframe_x = x + motion_x;
247 while (pixel_count &&
248 curframe_index < s->frame_size &&
249 prevframe_index < s->frame_size) {
250 int count = FFMIN3(pixel_count, width - curframe_x,
251 width - prevframe_x);
253 memcpy(palette_plane + curframe_index,
254 prev_palette_plane + prevframe_index, count);
255 pixel_count -= count;
256 curframe_index += count;
257 prevframe_index += count;
259 prevframe_x += count;
261 if (curframe_x >= width) {
262 curframe_index += line_inc;
266 if (prevframe_x >= width) {
267 prevframe_index += line_inc;
273 static int xan_wc3_decode_frame(XanContext *s) {
275 int width = s->avctx->width;
276 int height = s->avctx->height;
277 int total_pixels = width * height;
278 unsigned char opcode;
279 unsigned char flag = 0;
281 int motion_x, motion_y;
284 unsigned char *opcode_buffer = s->buffer1;
285 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
286 int opcode_buffer_size = s->buffer1_size;
287 const unsigned char *imagedata_buffer = s->buffer2;
289 /* pointers to segments inside the compressed chunk */
290 const unsigned char *huffman_segment;
291 const unsigned char *size_segment;
292 const unsigned char *vector_segment;
293 const unsigned char *imagedata_segment;
294 const unsigned char *buf_end = s->buf + s->size;
295 int huffman_offset, size_offset, vector_offset, imagedata_offset,
299 return AVERROR_INVALIDDATA;
301 huffman_offset = AV_RL16(&s->buf[0]);
302 size_offset = AV_RL16(&s->buf[2]);
303 vector_offset = AV_RL16(&s->buf[4]);
304 imagedata_offset = AV_RL16(&s->buf[6]);
306 if (huffman_offset >= s->size ||
307 size_offset >= s->size ||
308 vector_offset >= s->size ||
309 imagedata_offset >= s->size)
310 return AVERROR_INVALIDDATA;
312 huffman_segment = s->buf + huffman_offset;
313 size_segment = s->buf + size_offset;
314 vector_segment = s->buf + vector_offset;
315 imagedata_segment = s->buf + imagedata_offset;
317 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
318 huffman_segment, s->size - huffman_offset) < 0)
319 return AVERROR_INVALIDDATA;
321 if (imagedata_segment[0] == 2) {
322 xan_unpack(s->buffer2, s->buffer2_size,
323 &imagedata_segment[1], s->size - imagedata_offset - 1);
324 imagedata_size = s->buffer2_size;
326 imagedata_size = s->size - imagedata_offset - 1;
327 imagedata_buffer = &imagedata_segment[1];
330 /* use the decoded data segments to build the frame */
332 while (total_pixels && opcode_buffer < opcode_buffer_end) {
334 opcode = *opcode_buffer++;
361 size += (opcode - 10);
366 if (buf_end - size_segment < 1) {
367 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
368 return AVERROR_INVALIDDATA;
370 size = *size_segment++;
375 if (buf_end - size_segment < 2) {
376 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
377 return AVERROR_INVALIDDATA;
379 size = AV_RB16(&size_segment[0]);
385 if (buf_end - size_segment < 3) {
386 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
387 return AVERROR_INVALIDDATA;
389 size = AV_RB24(size_segment);
394 if (size > total_pixels)
400 /* run of (size) pixels is unchanged from last frame */
401 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
403 /* output a run of pixels from imagedata_buffer */
404 if (imagedata_size < size)
406 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
407 imagedata_buffer += size;
408 imagedata_size -= size;
411 if (vector_segment >= buf_end) {
412 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
413 return AVERROR_INVALIDDATA;
415 /* run-based motion compensation from last frame */
416 motion_x = sign_extend(*vector_segment >> 4, 4);
417 motion_y = sign_extend(*vector_segment & 0xF, 4);
420 /* copy a run of pixels from the previous frame */
421 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
426 /* coordinate accounting */
427 total_pixels -= size;
428 y += (x + size) / width;
429 x = (x + size) % width;
435 static inline unsigned mul(unsigned a, unsigned b)
437 return (a * b) >> 16;
440 static inline unsigned pow4(unsigned a)
442 unsigned square = mul(a, a);
443 return mul(square, square);
446 static inline unsigned pow5(unsigned a)
448 return mul(pow4(a), a);
451 static uint8_t gamma_corr(uint8_t in) {
452 unsigned lo, hi = 0xff40, target;
454 in = (in << 2) | (in >> 6);
455 /* equivalent float code:
458 return round(pow(in / 256.0, 0.8) * 256);
460 lo = target = in << 8;
462 unsigned mid = (lo + hi) >> 1;
463 unsigned pow = pow5(mid);
464 if (pow > target) hi = mid;
467 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
471 * This is a gamma correction that xan3 applies to all palette entries.
473 * There is a peculiarity, namely that the values are clamped to 253 -
474 * it seems likely that this table was calculated by a buggy fixed-point
475 * implementation, the one above under RUNTIME_GAMMA behaves like this for
477 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
478 * and thus pow(x, 0.8) is still easy to calculate.
479 * Also, the input values are first rotated to the left by 2.
481 static const uint8_t gamma_lookup[256] = {
482 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
483 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
484 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
485 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
486 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
487 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
488 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
489 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
490 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
491 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
492 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
493 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
494 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
495 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
496 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
497 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
498 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
499 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
500 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
501 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
502 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
503 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
504 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
505 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
506 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
507 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
508 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
509 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
510 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
511 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
512 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
513 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
517 static int xan_decode_frame(AVCodecContext *avctx,
518 void *data, int *got_frame,
521 const uint8_t *buf = avpkt->data;
522 int ret, buf_size = avpkt->size;
523 XanContext *s = avctx->priv_data;
527 bytestream2_init(&ctx, buf, buf_size);
528 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
533 tag = bytestream2_get_le32(&ctx);
534 size = bytestream2_get_be32(&ctx);
536 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
537 return AVERROR_INVALIDDATA;
539 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
542 if (size < PALETTE_SIZE)
543 return AVERROR_INVALIDDATA;
544 if (s->palettes_count >= PALETTES_MAX)
545 return AVERROR_INVALIDDATA;
546 tmpptr = av_realloc(s->palettes,
547 (s->palettes_count + 1) * AVPALETTE_SIZE);
549 return AVERROR(ENOMEM);
550 s->palettes = tmpptr;
551 tmpptr += s->palettes_count * AVPALETTE_COUNT;
552 for (i = 0; i < PALETTE_COUNT; i++) {
554 int r = gamma_corr(bytestream2_get_byteu(&ctx));
555 int g = gamma_corr(bytestream2_get_byteu(&ctx));
556 int b = gamma_corr(bytestream2_get_byteu(&ctx));
558 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
559 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
560 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
562 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
568 return AVERROR_INVALIDDATA;
569 new_pal = bytestream2_get_le32(&ctx);
570 if (new_pal < s->palettes_count) {
571 s->cur_palette = new_pal;
573 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
578 bytestream2_skip(&ctx, size);
582 buf_size = bytestream2_get_bytes_left(&ctx);
584 if (s->palettes_count <= 0) {
585 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
586 return AVERROR_INVALIDDATA;
589 if ((ret = ff_get_buffer(avctx, &s->current_frame))) {
590 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
593 s->current_frame.reference = 3;
596 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
598 memcpy(s->current_frame.data[1],
599 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
604 if (xan_wc3_decode_frame(s) < 0)
605 return AVERROR_INVALIDDATA;
607 /* release the last frame if it is allocated */
608 if (s->last_frame.data[0])
609 avctx->release_buffer(avctx, &s->last_frame);
612 *(AVFrame*)data = s->current_frame;
615 FFSWAP(AVFrame, s->current_frame, s->last_frame);
617 /* always report that the buffer was completely consumed */
621 static av_cold int xan_decode_end(AVCodecContext *avctx)
623 XanContext *s = avctx->priv_data;
625 /* release the frames */
626 if (s->last_frame.data[0])
627 avctx->release_buffer(avctx, &s->last_frame);
628 if (s->current_frame.data[0])
629 avctx->release_buffer(avctx, &s->current_frame);
631 av_freep(&s->buffer1);
632 av_freep(&s->buffer2);
633 av_freep(&s->palettes);
638 AVCodec ff_xan_wc3_decoder = {
640 .type = AVMEDIA_TYPE_VIDEO,
641 .id = AV_CODEC_ID_XAN_WC3,
642 .priv_data_size = sizeof(XanContext),
643 .init = xan_decode_init,
644 .close = xan_decode_end,
645 .decode = xan_decode_frame,
646 .capabilities = CODEC_CAP_DR1,
647 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),