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"
37 #include "bytestream.h"
38 #define 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 = 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;
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;
145 const unsigned char *src_end = src + src_len;
147 while (dest < dest_end && src < src_end) {
152 if ((opcode & 0x80) == 0) {
155 back = ((opcode & 0x60) << 3) + *src++ + 1;
156 size2 = ((opcode & 0x1c) >> 2) + 3;
157 } else if ((opcode & 0x40) == 0) {
160 back = (bytestream_get_be16(&src) & 0x3fff) + 1;
161 size2 = (opcode & 0x3f) + 4;
165 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
166 size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
169 if (dest_end - dest < size + size2 ||
170 dest + size - dest_org < back ||
171 src_end - src < size)
173 memcpy(dest, src, size); dest += size; src += size;
174 av_memcpy_backptr(dest, back, size2);
177 int finish = opcode >= 0xfc;
178 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
180 if (dest_end - dest < size || src_end - src < size)
182 memcpy(dest, src, size); dest += size; src += size;
189 static inline void xan_wc3_output_pixel_run(XanContext *s,
190 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
196 int width = s->avctx->width;
197 unsigned char *palette_plane;
199 palette_plane = s->current_frame.data[0];
200 stride = s->current_frame.linesize[0];
201 line_inc = stride - width;
202 index = y * stride + x;
204 while (pixel_count && index < s->frame_size) {
205 int count = FFMIN(pixel_count, width - current_x);
206 memcpy(palette_plane + index, pixel_buffer, count);
207 pixel_count -= count;
209 pixel_buffer += count;
212 if (current_x >= width) {
219 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
220 int pixel_count, int motion_x,
225 int curframe_index, prevframe_index;
226 int curframe_x, prevframe_x;
227 int width = s->avctx->width;
228 unsigned char *palette_plane, *prev_palette_plane;
230 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
231 x + motion_x < 0 || x + motion_x >= s->avctx->width)
234 palette_plane = s->current_frame.data[0];
235 prev_palette_plane = s->last_frame.data[0];
236 if (!prev_palette_plane)
237 prev_palette_plane = palette_plane;
238 stride = s->current_frame.linesize[0];
239 line_inc = stride - width;
240 curframe_index = y * stride + x;
242 prevframe_index = (y + motion_y) * stride + x + motion_x;
243 prevframe_x = x + motion_x;
244 while (pixel_count &&
245 curframe_index < s->frame_size &&
246 prevframe_index < s->frame_size) {
247 int count = FFMIN3(pixel_count, width - curframe_x,
248 width - prevframe_x);
250 memcpy(palette_plane + curframe_index,
251 prev_palette_plane + prevframe_index, count);
252 pixel_count -= count;
253 curframe_index += count;
254 prevframe_index += count;
256 prevframe_x += count;
258 if (curframe_x >= width) {
259 curframe_index += line_inc;
263 if (prevframe_x >= width) {
264 prevframe_index += line_inc;
270 static int xan_wc3_decode_frame(XanContext *s) {
272 int width = s->avctx->width;
273 int height = s->avctx->height;
274 int total_pixels = width * height;
275 unsigned char opcode;
276 unsigned char flag = 0;
278 int motion_x, motion_y;
281 unsigned char *opcode_buffer = s->buffer1;
282 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
283 int opcode_buffer_size = s->buffer1_size;
284 const unsigned char *imagedata_buffer = s->buffer2;
286 /* pointers to segments inside the compressed chunk */
287 const unsigned char *huffman_segment;
288 const unsigned char *size_segment;
289 const unsigned char *vector_segment;
290 const unsigned char *imagedata_segment;
291 const unsigned char *buf_end = s->buf + s->size;
292 int huffman_offset, size_offset, vector_offset, imagedata_offset,
296 return AVERROR_INVALIDDATA;
298 huffman_offset = AV_RL16(&s->buf[0]);
299 size_offset = AV_RL16(&s->buf[2]);
300 vector_offset = AV_RL16(&s->buf[4]);
301 imagedata_offset = AV_RL16(&s->buf[6]);
303 if (huffman_offset >= s->size ||
304 size_offset >= s->size ||
305 vector_offset >= s->size ||
306 imagedata_offset >= s->size)
307 return AVERROR_INVALIDDATA;
309 huffman_segment = s->buf + huffman_offset;
310 size_segment = s->buf + size_offset;
311 vector_segment = s->buf + vector_offset;
312 imagedata_segment = s->buf + imagedata_offset;
314 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
315 huffman_segment, s->size - huffman_offset) < 0)
316 return AVERROR_INVALIDDATA;
318 if (imagedata_segment[0] == 2) {
319 xan_unpack(s->buffer2, s->buffer2_size,
320 &imagedata_segment[1], s->size - imagedata_offset - 1);
321 imagedata_size = s->buffer2_size;
323 imagedata_size = s->size - imagedata_offset - 1;
324 imagedata_buffer = &imagedata_segment[1];
327 /* use the decoded data segments to build the frame */
329 while (total_pixels && opcode_buffer < opcode_buffer_end) {
331 opcode = *opcode_buffer++;
358 size += (opcode - 10);
363 size = *size_segment++;
368 size = AV_RB16(&size_segment[0]);
374 size = AV_RB24(size_segment);
379 if (size > total_pixels)
385 /* run of (size) pixels is unchanged from last frame */
386 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
388 /* output a run of pixels from imagedata_buffer */
389 if (imagedata_size < size)
391 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
392 imagedata_buffer += size;
393 imagedata_size -= size;
396 if (vector_segment >= buf_end) {
397 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
398 return AVERROR_INVALIDDATA;
400 /* run-based motion compensation from last frame */
401 motion_x = sign_extend(*vector_segment >> 4, 4);
402 motion_y = sign_extend(*vector_segment & 0xF, 4);
405 /* copy a run of pixels from the previous frame */
406 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
411 /* coordinate accounting */
412 total_pixels -= size;
413 y += (x + size) / width;
414 x = (x + size) % width;
420 static inline unsigned mul(unsigned a, unsigned b)
422 return (a * b) >> 16;
425 static inline unsigned pow4(unsigned a)
427 unsigned square = mul(a, a);
428 return mul(square, square);
431 static inline unsigned pow5(unsigned a)
433 return mul(pow4(a), a);
436 static uint8_t gamma_corr(uint8_t in) {
437 unsigned lo, hi = 0xff40, target;
439 in = (in << 2) | (in >> 6);
440 /* equivalent float code:
443 return round(pow(in / 256.0, 0.8) * 256);
445 lo = target = in << 8;
447 unsigned mid = (lo + hi) >> 1;
448 unsigned pow = pow5(mid);
449 if (pow > target) hi = mid;
452 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
456 * This is a gamma correction that xan3 applies to all palette entries.
458 * There is a peculiarity, namely that the values are clamped to 253 -
459 * it seems likely that this table was calculated by a buggy fixed-point
460 * implementation, the one above under RUNTIME_GAMMA behaves like this for
462 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
463 * and thus pow(x, 0.8) is still easy to calculate.
464 * Also, the input values are first rotated to the left by 2.
466 static const uint8_t gamma_lookup[256] = {
467 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
468 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
469 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
470 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
471 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
472 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
473 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
474 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
475 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
476 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
477 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
478 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
479 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
480 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
481 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
482 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
483 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
484 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
485 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
486 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
487 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
488 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
489 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
490 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
491 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
492 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
493 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
494 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
495 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
496 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
497 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
498 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
502 static int xan_decode_frame(AVCodecContext *avctx,
503 void *data, int *data_size,
506 const uint8_t *buf = avpkt->data;
507 int ret, buf_size = avpkt->size;
508 XanContext *s = avctx->priv_data;
510 if (avctx->codec->id == AV_CODEC_ID_XAN_WC3) {
511 const uint8_t *buf_end = buf + buf_size;
513 while (buf_end - buf > 8 && tag != VGA__TAG) {
518 tag = bytestream_get_le32(&buf);
519 size = bytestream_get_be32(&buf);
521 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
522 return AVERROR_INVALIDDATA;
524 size = FFMIN(size, buf_end - buf);
527 if (size < PALETTE_SIZE)
528 return AVERROR_INVALIDDATA;
529 if (s->palettes_count >= PALETTES_MAX)
530 return AVERROR_INVALIDDATA;
531 tmpptr = av_realloc(s->palettes,
532 (s->palettes_count + 1) * AVPALETTE_SIZE);
534 return AVERROR(ENOMEM);
535 s->palettes = tmpptr;
536 tmpptr += s->palettes_count * AVPALETTE_COUNT;
537 for (i = 0; i < PALETTE_COUNT; i++) {
539 int r = gamma_corr(*buf++);
540 int g = gamma_corr(*buf++);
541 int b = gamma_corr(*buf++);
543 int r = gamma_lookup[*buf++];
544 int g = gamma_lookup[*buf++];
545 int b = gamma_lookup[*buf++];
547 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
553 return AVERROR_INVALIDDATA;
554 new_pal = bytestream_get_le32(&buf);
555 if (new_pal < s->palettes_count) {
556 s->cur_palette = new_pal;
558 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
567 buf_size = buf_end - buf;
569 if (s->palettes_count <= 0) {
570 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
571 return AVERROR_INVALIDDATA;
574 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
575 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
578 s->current_frame.reference = 3;
581 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
583 memcpy(s->current_frame.data[1],
584 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
589 if (xan_wc3_decode_frame(s) < 0)
590 return AVERROR_INVALIDDATA;
592 /* release the last frame if it is allocated */
593 if (s->last_frame.data[0])
594 avctx->release_buffer(avctx, &s->last_frame);
596 *data_size = sizeof(AVFrame);
597 *(AVFrame*)data = s->current_frame;
600 FFSWAP(AVFrame, s->current_frame, s->last_frame);
602 /* always report that the buffer was completely consumed */
606 static av_cold int xan_decode_end(AVCodecContext *avctx)
608 XanContext *s = avctx->priv_data;
610 /* release the frames */
611 if (s->last_frame.data[0])
612 avctx->release_buffer(avctx, &s->last_frame);
613 if (s->current_frame.data[0])
614 avctx->release_buffer(avctx, &s->current_frame);
616 av_freep(&s->buffer1);
617 av_freep(&s->buffer2);
618 av_freep(&s->palettes);
623 AVCodec ff_xan_wc3_decoder = {
625 .type = AVMEDIA_TYPE_VIDEO,
626 .id = AV_CODEC_ID_XAN_WC3,
627 .priv_data_size = sizeof(XanContext),
628 .init = xan_decode_init,
629 .close = xan_decode_end,
630 .decode = xan_decode_frame,
631 .capabilities = CODEC_CAP_DR1,
632 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),