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"
36 #include "libavutil/mem.h"
38 #define BITSTREAM_READER_LE
40 #include "bytestream.h"
44 #define RUNTIME_GAMMA 0
46 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
47 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
48 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
49 #define PALETTE_COUNT 256
50 #define PALETTE_SIZE (PALETTE_COUNT * 3)
51 #define PALETTES_MAX 256
53 typedef struct XanContext {
55 AVCodecContext *avctx;
58 const unsigned char *buf;
62 unsigned char *buffer1;
64 unsigned char *buffer2;
75 static av_cold int xan_decode_end(AVCodecContext *avctx)
77 XanContext *s = avctx->priv_data;
79 av_frame_free(&s->last_frame);
81 av_freep(&s->buffer1);
82 av_freep(&s->buffer2);
83 av_freep(&s->palettes);
88 static av_cold int xan_decode_init(AVCodecContext *avctx)
90 XanContext *s = avctx->priv_data;
95 avctx->pix_fmt = AV_PIX_FMT_PAL8;
97 s->buffer1_size = avctx->width * avctx->height;
98 s->buffer1 = av_malloc(s->buffer1_size);
100 return AVERROR(ENOMEM);
101 s->buffer2_size = avctx->width * avctx->height;
102 s->buffer2 = av_malloc(s->buffer2_size + 130);
104 av_freep(&s->buffer1);
105 return AVERROR(ENOMEM);
108 s->last_frame = av_frame_alloc();
109 if (!s->last_frame) {
110 xan_decode_end(avctx);
111 return AVERROR(ENOMEM);
117 static int xan_huffman_decode(unsigned char *dest, int dest_len,
118 const unsigned char *src, int src_len)
120 unsigned char byte = *src++;
121 unsigned char ival = byte + 0x16;
122 const unsigned char * ptr = src + byte*2;
123 int ptr_len = src_len - 1 - byte*2;
124 unsigned char val = ival;
125 unsigned char *dest_end = dest + dest_len;
126 unsigned char *dest_start = dest;
130 return AVERROR_INVALIDDATA;
132 init_get_bits(&gb, ptr, ptr_len * 8);
134 while (val != 0x16) {
135 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
137 return AVERROR_INVALIDDATA;
141 if (dest >= dest_end)
148 return dest - dest_start;
152 * unpack simple compression
154 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
156 static void xan_unpack(unsigned char *dest, int dest_len,
157 const unsigned char *src, int src_len)
159 unsigned char opcode;
161 unsigned char *dest_org = dest;
162 unsigned char *dest_end = dest + dest_len;
165 bytestream2_init(&ctx, src, src_len);
166 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
167 opcode = bytestream2_get_byte(&ctx);
171 if ((opcode & 0x80) == 0) {
174 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
175 size2 = ((opcode & 0x1c) >> 2) + 3;
176 } else if ((opcode & 0x40) == 0) {
177 size = bytestream2_peek_byte(&ctx) >> 6;
179 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
180 size2 = (opcode & 0x3f) + 4;
184 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
185 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
188 if (dest_end - dest < size + size2 ||
189 dest + size - dest_org < back ||
190 bytestream2_get_bytes_left(&ctx) < size)
192 bytestream2_get_buffer(&ctx, dest, size);
194 av_memcpy_backptr(dest, back, size2);
197 int finish = opcode >= 0xfc;
198 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
200 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
202 bytestream2_get_buffer(&ctx, dest, size);
210 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
211 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
217 int width = s->avctx->width;
218 unsigned char *palette_plane;
220 palette_plane = frame->data[0];
221 stride = frame->linesize[0];
222 line_inc = stride - width;
223 index = y * stride + x;
225 while (pixel_count && index < s->frame_size) {
226 int count = FFMIN(pixel_count, width - current_x);
227 memcpy(palette_plane + index, pixel_buffer, count);
228 pixel_count -= count;
230 pixel_buffer += count;
233 if (current_x >= width) {
240 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
242 int pixel_count, int motion_x,
247 int curframe_index, prevframe_index;
248 int curframe_x, prevframe_x;
249 int width = s->avctx->width;
250 unsigned char *palette_plane, *prev_palette_plane;
252 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
253 x + motion_x < 0 || x + motion_x >= s->avctx->width)
256 palette_plane = frame->data[0];
257 prev_palette_plane = s->last_frame->data[0];
258 if (!prev_palette_plane)
259 prev_palette_plane = palette_plane;
260 stride = frame->linesize[0];
261 line_inc = stride - width;
262 curframe_index = y * stride + x;
264 prevframe_index = (y + motion_y) * stride + x + motion_x;
265 prevframe_x = x + motion_x;
266 while (pixel_count &&
267 curframe_index < s->frame_size &&
268 prevframe_index < s->frame_size) {
269 int count = FFMIN3(pixel_count, width - curframe_x,
270 width - prevframe_x);
272 memcpy(palette_plane + curframe_index,
273 prev_palette_plane + prevframe_index, count);
274 pixel_count -= count;
275 curframe_index += count;
276 prevframe_index += count;
278 prevframe_x += count;
280 if (curframe_x >= width) {
281 curframe_index += line_inc;
285 if (prevframe_x >= width) {
286 prevframe_index += line_inc;
292 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
295 int width = s->avctx->width;
296 int height = s->avctx->height;
297 int total_pixels = width * height;
298 unsigned char opcode;
299 unsigned char flag = 0;
301 int motion_x, motion_y;
304 unsigned char *opcode_buffer = s->buffer1;
305 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
306 int opcode_buffer_size = s->buffer1_size;
307 const unsigned char *imagedata_buffer = s->buffer2;
309 /* pointers to segments inside the compressed chunk */
310 const unsigned char *huffman_segment;
311 GetByteContext size_segment;
312 GetByteContext vector_segment;
313 const unsigned char *imagedata_segment;
314 int huffman_offset, size_offset, vector_offset, imagedata_offset,
318 return AVERROR_INVALIDDATA;
320 huffman_offset = AV_RL16(&s->buf[0]);
321 size_offset = AV_RL16(&s->buf[2]);
322 vector_offset = AV_RL16(&s->buf[4]);
323 imagedata_offset = AV_RL16(&s->buf[6]);
325 if (huffman_offset >= s->size ||
326 size_offset >= s->size ||
327 vector_offset >= s->size ||
328 imagedata_offset >= s->size)
329 return AVERROR_INVALIDDATA;
331 huffman_segment = s->buf + huffman_offset;
332 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
333 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
334 imagedata_segment = s->buf + imagedata_offset;
336 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
337 huffman_segment, s->size - huffman_offset)) < 0)
338 return AVERROR_INVALIDDATA;
339 opcode_buffer_end = opcode_buffer + ret;
341 if (imagedata_segment[0] == 2) {
342 xan_unpack(s->buffer2, s->buffer2_size,
343 &imagedata_segment[1], s->size - imagedata_offset - 1);
344 imagedata_size = s->buffer2_size;
346 imagedata_size = s->size - imagedata_offset - 1;
347 imagedata_buffer = &imagedata_segment[1];
350 /* use the decoded data segments to build the frame */
352 while (total_pixels && opcode_buffer < opcode_buffer_end) {
354 opcode = *opcode_buffer++;
381 size += (opcode - 10);
386 size = bytestream2_get_byte(&size_segment);
391 size = bytestream2_get_be16(&size_segment);
396 size = bytestream2_get_be24(&size_segment);
400 if (size > total_pixels)
406 /* run of (size) pixels is unchanged from last frame */
407 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
409 /* output a run of pixels from imagedata_buffer */
410 if (imagedata_size < size)
412 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
413 imagedata_buffer += size;
414 imagedata_size -= size;
417 /* run-based motion compensation from last frame */
418 uint8_t vector = bytestream2_get_byte(&vector_segment);
419 motion_x = sign_extend(vector >> 4, 4);
420 motion_y = sign_extend(vector & 0xF, 4);
422 /* copy a run of pixels from the previous frame */
423 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
428 /* coordinate accounting */
429 total_pixels -= size;
430 y += (x + size) / width;
431 x = (x + size) % width;
437 static inline unsigned mul(unsigned a, unsigned b)
439 return (a * b) >> 16;
442 static inline unsigned pow4(unsigned a)
444 unsigned square = mul(a, a);
445 return mul(square, square);
448 static inline unsigned pow5(unsigned a)
450 return mul(pow4(a), a);
453 static uint8_t gamma_corr(uint8_t in) {
454 unsigned lo, hi = 0xff40, target;
456 in = (in << 2) | (in >> 6);
457 /* equivalent float code:
460 return round(pow(in / 256.0, 0.8) * 256);
462 lo = target = in << 8;
464 unsigned mid = (lo + hi) >> 1;
465 unsigned pow = pow5(mid);
466 if (pow > target) hi = mid;
469 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
473 * This is a gamma correction that xan3 applies to all palette entries.
475 * There is a peculiarity, namely that the values are clamped to 253 -
476 * it seems likely that this table was calculated by a buggy fixed-point
477 * implementation, the one above under RUNTIME_GAMMA behaves like this for
479 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
480 * and thus pow(x, 0.8) is still easy to calculate.
481 * Also, the input values are first rotated to the left by 2.
483 static const uint8_t gamma_lookup[256] = {
484 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
485 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
486 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
487 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
488 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
489 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
490 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
491 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
492 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
493 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
494 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
495 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
496 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
497 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
498 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
499 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
500 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
501 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
502 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
503 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
504 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
505 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
506 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
507 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
508 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
509 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
510 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
511 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
512 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
513 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
514 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
515 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
519 static int xan_decode_frame(AVCodecContext *avctx,
520 void *data, int *got_frame,
523 AVFrame *frame = data;
524 const uint8_t *buf = avpkt->data;
525 int ret, buf_size = avpkt->size;
526 XanContext *s = avctx->priv_data;
530 bytestream2_init(&ctx, buf, buf_size);
531 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
536 tag = bytestream2_get_le32(&ctx);
537 size = bytestream2_get_be32(&ctx);
538 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
541 if (size < PALETTE_SIZE)
542 return AVERROR_INVALIDDATA;
543 if (s->palettes_count >= PALETTES_MAX)
544 return AVERROR_INVALIDDATA;
545 tmpptr = av_realloc(s->palettes,
546 (s->palettes_count + 1) * AVPALETTE_SIZE);
548 return AVERROR(ENOMEM);
549 s->palettes = tmpptr;
550 tmpptr += s->palettes_count * AVPALETTE_COUNT;
551 for (i = 0; i < PALETTE_COUNT; i++) {
553 int r = gamma_corr(bytestream2_get_byteu(&ctx));
554 int g = gamma_corr(bytestream2_get_byteu(&ctx));
555 int b = gamma_corr(bytestream2_get_byteu(&ctx));
557 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
558 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
559 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
561 *tmpptr++ = (r << 16) | (g << 8) | b;
567 return AVERROR_INVALIDDATA;
568 new_pal = bytestream2_get_le32(&ctx);
569 if (new_pal < s->palettes_count) {
570 s->cur_palette = new_pal;
572 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
577 bytestream2_skip(&ctx, size);
581 buf_size = bytestream2_get_bytes_left(&ctx);
583 if (s->palettes_count <= 0) {
584 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
585 return AVERROR_INVALIDDATA;
588 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF))) {
589 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
594 s->frame_size = frame->linesize[0] * s->avctx->height;
596 memcpy(frame->data[1],
597 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
602 if (xan_wc3_decode_frame(s, frame) < 0)
603 return AVERROR_INVALIDDATA;
605 av_frame_unref(s->last_frame);
606 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
611 /* always report that the buffer was completely consumed */
615 AVCodec ff_xan_wc3_decoder = {
617 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
618 .type = AVMEDIA_TYPE_VIDEO,
619 .id = AV_CODEC_ID_XAN_WC3,
620 .priv_data_size = sizeof(XanContext),
621 .init = xan_decode_init,
622 .close = xan_decode_end,
623 .decode = xan_decode_frame,
624 .capabilities = AV_CODEC_CAP_DR1,