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
42 #define RUNTIME_GAMMA 0
44 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
45 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
46 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
47 #define PALETTE_COUNT 256
48 #define PALETTE_SIZE (PALETTE_COUNT * 3)
49 #define PALETTES_MAX 256
51 typedef struct XanContext {
53 AVCodecContext *avctx;
55 AVFrame current_frame;
57 const unsigned char *buf;
61 unsigned char *buffer1;
63 unsigned char *buffer2;
74 static av_cold int xan_decode_init(AVCodecContext *avctx)
76 XanContext *s = avctx->priv_data;
81 avctx->pix_fmt = AV_PIX_FMT_PAL8;
83 s->buffer1_size = avctx->width * avctx->height;
84 s->buffer1 = av_malloc(s->buffer1_size);
86 return AVERROR(ENOMEM);
87 s->buffer2_size = avctx->width * avctx->height;
88 s->buffer2 = av_malloc(s->buffer2_size + 130);
90 av_freep(&s->buffer1);
91 return AVERROR(ENOMEM);
93 avcodec_get_frame_defaults(&s->last_frame);
94 avcodec_get_frame_defaults(&s->current_frame);
99 static int xan_huffman_decode(unsigned char *dest, int dest_len,
100 const unsigned char *src, int src_len)
102 unsigned char byte = *src++;
103 unsigned char ival = byte + 0x16;
104 const unsigned char * ptr = src + byte*2;
105 int ptr_len = src_len - 1 - byte*2;
106 unsigned char val = ival;
107 unsigned char *dest_end = dest + dest_len;
111 return AVERROR_INVALIDDATA;
113 init_get_bits(&gb, ptr, ptr_len * 8);
115 while (val != 0x16) {
116 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
122 if (dest >= dest_end)
133 * unpack simple compression
135 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
137 static void xan_unpack(unsigned char *dest, int dest_len,
138 const unsigned char *src, int src_len)
140 unsigned char opcode;
142 unsigned char *dest_org = dest;
143 unsigned char *dest_end = dest + dest_len;
144 const unsigned char *src_end = src + src_len;
146 while (dest < dest_end && src < src_end) {
151 if ((opcode & 0x80) == 0) {
154 back = ((opcode & 0x60) << 3) + *src++ + 1;
155 size2 = ((opcode & 0x1c) >> 2) + 3;
156 } else if ((opcode & 0x40) == 0) {
159 back = (bytestream_get_be16(&src) & 0x3fff) + 1;
160 size2 = (opcode & 0x3f) + 4;
164 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
165 size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
168 if (dest_end - dest < size + size2 ||
169 dest + size - dest_org < back ||
170 src_end - src < size)
172 memcpy(dest, src, size); dest += size; src += size;
173 av_memcpy_backptr(dest, back, size2);
176 int finish = opcode >= 0xfc;
177 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
179 if (dest_end - dest < size || src_end - src < size)
181 memcpy(dest, src, size); dest += size; src += size;
188 static inline void xan_wc3_output_pixel_run(XanContext *s,
189 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
195 int width = s->avctx->width;
196 unsigned char *palette_plane;
198 palette_plane = s->current_frame.data[0];
199 stride = s->current_frame.linesize[0];
200 line_inc = stride - width;
201 index = y * stride + x;
203 while (pixel_count && index < s->frame_size) {
204 int count = FFMIN(pixel_count, width - current_x);
205 memcpy(palette_plane + index, pixel_buffer, count);
206 pixel_count -= count;
208 pixel_buffer += count;
211 if (current_x >= width) {
218 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
219 int pixel_count, int motion_x,
224 int curframe_index, prevframe_index;
225 int curframe_x, prevframe_x;
226 int width = s->avctx->width;
227 unsigned char *palette_plane, *prev_palette_plane;
229 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
230 x + motion_x < 0 || x + motion_x >= s->avctx->width)
233 palette_plane = s->current_frame.data[0];
234 prev_palette_plane = s->last_frame.data[0];
235 if (!prev_palette_plane)
236 prev_palette_plane = palette_plane;
237 stride = s->current_frame.linesize[0];
238 line_inc = stride - width;
239 curframe_index = y * stride + x;
241 prevframe_index = (y + motion_y) * stride + x + motion_x;
242 prevframe_x = x + motion_x;
243 while (pixel_count &&
244 curframe_index < s->frame_size &&
245 prevframe_index < s->frame_size) {
246 int count = FFMIN3(pixel_count, width - curframe_x,
247 width - prevframe_x);
249 memcpy(palette_plane + curframe_index,
250 prev_palette_plane + prevframe_index, count);
251 pixel_count -= count;
252 curframe_index += count;
253 prevframe_index += count;
255 prevframe_x += count;
257 if (curframe_x >= width) {
258 curframe_index += line_inc;
262 if (prevframe_x >= width) {
263 prevframe_index += line_inc;
269 static int xan_wc3_decode_frame(XanContext *s) {
271 int width = s->avctx->width;
272 int height = s->avctx->height;
273 int total_pixels = width * height;
274 unsigned char opcode;
275 unsigned char flag = 0;
277 int motion_x, motion_y;
280 unsigned char *opcode_buffer = s->buffer1;
281 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
282 int opcode_buffer_size = s->buffer1_size;
283 const unsigned char *imagedata_buffer = s->buffer2;
285 /* pointers to segments inside the compressed chunk */
286 const unsigned char *huffman_segment;
287 const unsigned char *size_segment;
288 const unsigned char *vector_segment;
289 const unsigned char *imagedata_segment;
290 const unsigned char *buf_end = s->buf + s->size;
291 int huffman_offset, size_offset, vector_offset, imagedata_offset,
295 return AVERROR_INVALIDDATA;
297 huffman_offset = AV_RL16(&s->buf[0]);
298 size_offset = AV_RL16(&s->buf[2]);
299 vector_offset = AV_RL16(&s->buf[4]);
300 imagedata_offset = AV_RL16(&s->buf[6]);
302 if (huffman_offset >= s->size ||
303 size_offset >= s->size ||
304 vector_offset >= s->size ||
305 imagedata_offset >= s->size)
306 return AVERROR_INVALIDDATA;
308 huffman_segment = s->buf + huffman_offset;
309 size_segment = s->buf + size_offset;
310 vector_segment = s->buf + vector_offset;
311 imagedata_segment = s->buf + imagedata_offset;
313 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
314 huffman_segment, s->size - huffman_offset) < 0)
315 return AVERROR_INVALIDDATA;
317 if (imagedata_segment[0] == 2) {
318 xan_unpack(s->buffer2, s->buffer2_size,
319 &imagedata_segment[1], s->size - imagedata_offset - 1);
320 imagedata_size = s->buffer2_size;
322 imagedata_size = s->size - imagedata_offset - 1;
323 imagedata_buffer = &imagedata_segment[1];
326 /* use the decoded data segments to build the frame */
328 while (total_pixels && opcode_buffer < opcode_buffer_end) {
330 opcode = *opcode_buffer++;
357 size += (opcode - 10);
362 if (buf_end - size_segment < 1) {
363 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
364 return AVERROR_INVALIDDATA;
366 size = *size_segment++;
371 if (buf_end - size_segment < 2) {
372 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
373 return AVERROR_INVALIDDATA;
375 size = AV_RB16(&size_segment[0]);
381 if (buf_end - size_segment < 3) {
382 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
383 return AVERROR_INVALIDDATA;
385 size = AV_RB24(size_segment);
390 if (size > total_pixels)
396 /* run of (size) pixels is unchanged from last frame */
397 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
399 /* output a run of pixels from imagedata_buffer */
400 if (imagedata_size < size)
402 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
403 imagedata_buffer += size;
404 imagedata_size -= size;
407 if (vector_segment >= buf_end) {
408 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
409 return AVERROR_INVALIDDATA;
411 /* run-based motion compensation from last frame */
412 motion_x = sign_extend(*vector_segment >> 4, 4);
413 motion_y = sign_extend(*vector_segment & 0xF, 4);
416 /* copy a run of pixels from the previous frame */
417 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
422 /* coordinate accounting */
423 total_pixels -= size;
424 y += (x + size) / width;
425 x = (x + size) % width;
431 static inline unsigned mul(unsigned a, unsigned b)
433 return (a * b) >> 16;
436 static inline unsigned pow4(unsigned a)
438 unsigned square = mul(a, a);
439 return mul(square, square);
442 static inline unsigned pow5(unsigned a)
444 return mul(pow4(a), a);
447 static uint8_t gamma_corr(uint8_t in) {
448 unsigned lo, hi = 0xff40, target;
450 in = (in << 2) | (in >> 6);
451 /* equivalent float code:
454 return round(pow(in / 256.0, 0.8) * 256);
456 lo = target = in << 8;
458 unsigned mid = (lo + hi) >> 1;
459 unsigned pow = pow5(mid);
460 if (pow > target) hi = mid;
463 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
467 * This is a gamma correction that xan3 applies to all palette entries.
469 * There is a peculiarity, namely that the values are clamped to 253 -
470 * it seems likely that this table was calculated by a buggy fixed-point
471 * implementation, the one above under RUNTIME_GAMMA behaves like this for
473 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
474 * and thus pow(x, 0.8) is still easy to calculate.
475 * Also, the input values are first rotated to the left by 2.
477 static const uint8_t gamma_lookup[256] = {
478 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
479 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
480 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
481 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
482 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
483 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
484 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
485 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
486 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
487 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
488 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
489 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
490 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
491 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
492 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
493 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
494 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
495 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
496 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
497 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
498 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
499 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
500 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
501 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
502 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
503 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
504 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
505 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
506 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
507 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
508 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
509 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
513 static int xan_decode_frame(AVCodecContext *avctx,
514 void *data, int *data_size,
517 const uint8_t *buf = avpkt->data;
518 int ret, buf_size = avpkt->size;
519 XanContext *s = avctx->priv_data;
521 if (avctx->codec->id == AV_CODEC_ID_XAN_WC3) {
522 const uint8_t *buf_end = buf + buf_size;
524 while (buf_end - buf > 8 && tag != VGA__TAG) {
529 tag = bytestream_get_le32(&buf);
530 size = bytestream_get_be32(&buf);
532 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
533 return AVERROR_INVALIDDATA;
535 size = FFMIN(size, buf_end - buf);
538 if (size < PALETTE_SIZE)
539 return AVERROR_INVALIDDATA;
540 if (s->palettes_count >= PALETTES_MAX)
541 return AVERROR_INVALIDDATA;
542 tmpptr = av_realloc(s->palettes,
543 (s->palettes_count + 1) * AVPALETTE_SIZE);
545 return AVERROR(ENOMEM);
546 s->palettes = tmpptr;
547 tmpptr += s->palettes_count * AVPALETTE_COUNT;
548 for (i = 0; i < PALETTE_COUNT; i++) {
550 int r = gamma_corr(*buf++);
551 int g = gamma_corr(*buf++);
552 int b = gamma_corr(*buf++);
554 int r = gamma_lookup[*buf++];
555 int g = gamma_lookup[*buf++];
556 int b = gamma_lookup[*buf++];
558 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
564 return AVERROR_INVALIDDATA;
565 new_pal = bytestream_get_le32(&buf);
566 if (new_pal < s->palettes_count) {
567 s->cur_palette = new_pal;
569 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
578 buf_size = buf_end - buf;
580 if (s->palettes_count <= 0) {
581 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
582 return AVERROR_INVALIDDATA;
585 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
586 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
589 s->current_frame.reference = 3;
592 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
594 memcpy(s->current_frame.data[1],
595 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
600 if (xan_wc3_decode_frame(s) < 0)
601 return AVERROR_INVALIDDATA;
603 /* release the last frame if it is allocated */
604 if (s->last_frame.data[0])
605 avctx->release_buffer(avctx, &s->last_frame);
607 *data_size = sizeof(AVFrame);
608 *(AVFrame*)data = s->current_frame;
611 FFSWAP(AVFrame, s->current_frame, s->last_frame);
613 /* always report that the buffer was completely consumed */
617 static av_cold int xan_decode_end(AVCodecContext *avctx)
619 XanContext *s = avctx->priv_data;
621 /* release the frames */
622 if (s->last_frame.data[0])
623 avctx->release_buffer(avctx, &s->last_frame);
624 if (s->current_frame.data[0])
625 avctx->release_buffer(avctx, &s->current_frame);
627 av_freep(&s->buffer1);
628 av_freep(&s->buffer2);
629 av_freep(&s->palettes);
634 AVCodec ff_xan_wc3_decoder = {
636 .type = AVMEDIA_TYPE_VIDEO,
637 .id = AV_CODEC_ID_XAN_WC3,
638 .priv_data_size = sizeof(XanContext),
639 .init = xan_decode_init,
640 .close = xan_decode_end,
641 .decode = xan_decode_frame,
642 .capabilities = CODEC_CAP_DR1,
643 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),