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 #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;
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(uint8_t *dest, int dest_len,
118 const uint8_t *src, int src_len)
120 uint8_t byte = *src++;
121 uint8_t ival = byte + 0x16;
122 const uint8_t * ptr = src + byte*2;
123 int ptr_len = src_len - 1 - byte*2;
125 uint8_t *dest_end = dest + dest_len;
126 uint8_t *dest_start = dest;
130 if ((ret = init_get_bits8(&gb, ptr, ptr_len)) < 0)
133 while (val != 0x16) {
135 if (get_bits_left(&gb) < 1)
136 return AVERROR_INVALIDDATA;
137 idx = val - 0x17 + get_bits1(&gb) * byte;
139 return AVERROR_INVALIDDATA;
143 if (dest >= dest_end)
150 return dest - dest_start;
154 * unpack simple compression
156 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
158 static void xan_unpack(uint8_t *dest, int dest_len,
159 const uint8_t *src, int src_len)
163 uint8_t *dest_org = dest;
164 uint8_t *dest_end = dest + dest_len;
167 bytestream2_init(&ctx, src, src_len);
168 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
169 opcode = bytestream2_get_byte(&ctx);
173 if ((opcode & 0x80) == 0) {
176 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
177 size2 = ((opcode & 0x1c) >> 2) + 3;
178 } else if ((opcode & 0x40) == 0) {
179 size = bytestream2_peek_byte(&ctx) >> 6;
181 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
182 size2 = (opcode & 0x3f) + 4;
186 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
187 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
190 if (dest_end - dest < size + size2 ||
191 dest + size - dest_org < back ||
192 bytestream2_get_bytes_left(&ctx) < size)
194 bytestream2_get_buffer(&ctx, dest, size);
196 av_memcpy_backptr(dest, back, size2);
199 int finish = opcode >= 0xfc;
200 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
202 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
204 bytestream2_get_buffer(&ctx, dest, size);
212 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
213 const uint8_t *pixel_buffer, int x, int y, int pixel_count)
219 int width = s->avctx->width;
220 uint8_t *palette_plane;
222 palette_plane = frame->data[0];
223 stride = frame->linesize[0];
224 line_inc = stride - width;
225 index = y * stride + x;
227 while (pixel_count && index < s->frame_size) {
228 int count = FFMIN(pixel_count, width - current_x);
229 memcpy(palette_plane + index, pixel_buffer, count);
230 pixel_count -= count;
232 pixel_buffer += count;
235 if (current_x >= width) {
242 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
244 int pixel_count, int motion_x,
249 int curframe_index, prevframe_index;
250 int curframe_x, prevframe_x;
251 int width = s->avctx->width;
252 uint8_t *palette_plane, *prev_palette_plane;
254 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
255 x + motion_x < 0 || x + motion_x >= s->avctx->width)
258 palette_plane = frame->data[0];
259 prev_palette_plane = s->last_frame->data[0];
260 if (!prev_palette_plane)
261 prev_palette_plane = palette_plane;
262 stride = frame->linesize[0];
263 line_inc = stride - width;
264 curframe_index = y * stride + x;
266 prevframe_index = (y + motion_y) * stride + x + motion_x;
267 prevframe_x = x + motion_x;
269 if (prev_palette_plane == palette_plane && FFABS(motion_x + width*motion_y) < pixel_count) {
270 avpriv_request_sample(s->avctx, "Overlapping copy");
274 while (pixel_count &&
275 curframe_index < s->frame_size &&
276 prevframe_index < s->frame_size) {
277 int count = FFMIN3(pixel_count, width - curframe_x,
278 width - prevframe_x);
280 memcpy(palette_plane + curframe_index,
281 prev_palette_plane + prevframe_index, count);
282 pixel_count -= count;
283 curframe_index += count;
284 prevframe_index += count;
286 prevframe_x += count;
288 if (curframe_x >= width) {
289 curframe_index += line_inc;
293 if (prevframe_x >= width) {
294 prevframe_index += line_inc;
300 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
303 int width = s->avctx->width;
304 int height = s->avctx->height;
305 int total_pixels = width * height;
309 int motion_x, motion_y;
312 uint8_t *opcode_buffer = s->buffer1;
313 uint8_t *opcode_buffer_end = s->buffer1 + s->buffer1_size;
314 int opcode_buffer_size = s->buffer1_size;
315 const uint8_t *imagedata_buffer = s->buffer2;
317 /* pointers to segments inside the compressed chunk */
318 const uint8_t *huffman_segment;
319 GetByteContext size_segment;
320 GetByteContext vector_segment;
321 const uint8_t *imagedata_segment;
322 int huffman_offset, size_offset, vector_offset, imagedata_offset,
326 return AVERROR_INVALIDDATA;
328 huffman_offset = AV_RL16(&s->buf[0]);
329 size_offset = AV_RL16(&s->buf[2]);
330 vector_offset = AV_RL16(&s->buf[4]);
331 imagedata_offset = AV_RL16(&s->buf[6]);
333 if (huffman_offset >= s->size ||
334 size_offset >= s->size ||
335 vector_offset >= s->size ||
336 imagedata_offset >= s->size)
337 return AVERROR_INVALIDDATA;
339 huffman_segment = s->buf + huffman_offset;
340 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
341 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
342 imagedata_segment = s->buf + imagedata_offset;
344 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
345 huffman_segment, s->size - huffman_offset)) < 0)
346 return AVERROR_INVALIDDATA;
347 opcode_buffer_end = opcode_buffer + ret;
349 if (imagedata_segment[0] == 2) {
350 xan_unpack(s->buffer2, s->buffer2_size,
351 &imagedata_segment[1], s->size - imagedata_offset - 1);
352 imagedata_size = s->buffer2_size;
354 imagedata_size = s->size - imagedata_offset - 1;
355 imagedata_buffer = &imagedata_segment[1];
358 /* use the decoded data segments to build the frame */
360 while (total_pixels && opcode_buffer < opcode_buffer_end) {
362 opcode = *opcode_buffer++;
389 size += (opcode - 10);
394 if (bytestream2_get_bytes_left(&size_segment) < 1) {
395 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
396 return AVERROR_INVALIDDATA;
398 size = bytestream2_get_byte(&size_segment);
403 if (bytestream2_get_bytes_left(&size_segment) < 2) {
404 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
405 return AVERROR_INVALIDDATA;
407 size = bytestream2_get_be16(&size_segment);
412 if (bytestream2_get_bytes_left(&size_segment) < 3) {
413 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
414 return AVERROR_INVALIDDATA;
416 size = bytestream2_get_be24(&size_segment);
420 if (size > total_pixels)
426 /* run of (size) pixels is unchanged from last frame */
427 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
429 /* output a run of pixels from imagedata_buffer */
430 if (imagedata_size < size)
432 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
433 imagedata_buffer += size;
434 imagedata_size -= size;
438 if (bytestream2_get_bytes_left(&vector_segment) <= 0) {
439 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
440 return AVERROR_INVALIDDATA;
442 /* run-based motion compensation from last frame */
443 vector = bytestream2_get_byte(&vector_segment);
444 motion_x = sign_extend(vector >> 4, 4);
445 motion_y = sign_extend(vector & 0xF, 4);
447 /* copy a run of pixels from the previous frame */
448 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
453 /* coordinate accounting */
454 total_pixels -= size;
455 y += (x + size) / width;
456 x = (x + size) % width;
462 static inline unsigned mul(unsigned a, unsigned b)
464 return (a * b) >> 16;
467 static inline unsigned pow4(unsigned a)
469 unsigned square = mul(a, a);
470 return mul(square, square);
473 static inline unsigned pow5(unsigned a)
475 return mul(pow4(a), a);
478 static uint8_t gamma_corr(uint8_t in) {
479 unsigned lo, hi = 0xff40, target;
481 in = (in << 2) | (in >> 6);
482 /* equivalent float code:
485 return round(pow(in / 256.0, 0.8) * 256);
487 lo = target = in << 8;
489 unsigned mid = (lo + hi) >> 1;
490 unsigned pow = pow5(mid);
491 if (pow > target) hi = mid;
494 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
498 * This is a gamma correction that xan3 applies to all palette entries.
500 * There is a peculiarity, namely that the values are clamped to 253 -
501 * it seems likely that this table was calculated by a buggy fixed-point
502 * implementation, the one above under RUNTIME_GAMMA behaves like this for
504 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
505 * and thus pow(x, 0.8) is still easy to calculate.
506 * Also, the input values are first rotated to the left by 2.
508 static const uint8_t gamma_lookup[256] = {
509 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
510 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
511 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
512 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
513 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
514 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
515 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
516 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
517 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
518 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
519 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
520 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
521 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
522 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
523 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
524 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
525 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
526 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
527 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
528 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
529 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
530 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
531 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
532 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
533 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
534 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
535 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
536 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
537 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
538 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
539 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
540 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
544 static int xan_decode_frame(AVCodecContext *avctx,
545 void *data, int *got_frame,
548 AVFrame *frame = data;
549 const uint8_t *buf = avpkt->data;
550 int ret, buf_size = avpkt->size;
551 XanContext *s = avctx->priv_data;
555 bytestream2_init(&ctx, buf, buf_size);
556 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
561 tag = bytestream2_get_le32(&ctx);
562 size = bytestream2_get_be32(&ctx);
564 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
565 return AVERROR_INVALIDDATA;
567 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
570 if (size < PALETTE_SIZE)
571 return AVERROR_INVALIDDATA;
572 if (s->palettes_count >= PALETTES_MAX)
573 return AVERROR_INVALIDDATA;
574 tmpptr = av_realloc_array(s->palettes,
575 s->palettes_count + 1, AVPALETTE_SIZE);
577 return AVERROR(ENOMEM);
578 s->palettes = tmpptr;
579 tmpptr += s->palettes_count * AVPALETTE_COUNT;
580 for (i = 0; i < PALETTE_COUNT; i++) {
582 int r = gamma_corr(bytestream2_get_byteu(&ctx));
583 int g = gamma_corr(bytestream2_get_byteu(&ctx));
584 int b = gamma_corr(bytestream2_get_byteu(&ctx));
586 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
587 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
588 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
590 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
596 return AVERROR_INVALIDDATA;
597 new_pal = bytestream2_get_le32(&ctx);
598 if (new_pal < s->palettes_count) {
599 s->cur_palette = new_pal;
601 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
606 bytestream2_skip(&ctx, size);
610 buf_size = bytestream2_get_bytes_left(&ctx);
612 if (s->palettes_count <= 0) {
613 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
614 return AVERROR_INVALIDDATA;
617 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0)
621 s->frame_size = frame->linesize[0] * s->avctx->height;
623 memcpy(frame->data[1],
624 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
629 if (xan_wc3_decode_frame(s, frame) < 0)
630 return AVERROR_INVALIDDATA;
632 av_frame_unref(s->last_frame);
633 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
638 /* always report that the buffer was completely consumed */
642 AVCodec ff_xan_wc3_decoder = {
644 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
645 .type = AVMEDIA_TYPE_VIDEO,
646 .id = AV_CODEC_ID_XAN_WC3,
647 .priv_data_size = sizeof(XanContext),
648 .init = xan_decode_init,
649 .close = xan_decode_end,
650 .decode = xan_decode_frame,
651 .capabilities = AV_CODEC_CAP_DR1,