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 = 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 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 size = *size_segment++;
367 size = AV_RB16(&size_segment[0]);
373 size = AV_RB24(size_segment);
378 if (size > total_pixels)
384 /* run of (size) pixels is unchanged from last frame */
385 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
387 /* output a run of pixels from imagedata_buffer */
388 if (imagedata_size < size)
390 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
391 imagedata_buffer += size;
392 imagedata_size -= size;
395 /* run-based motion compensation from last frame */
396 motion_x = sign_extend(*vector_segment >> 4, 4);
397 motion_y = sign_extend(*vector_segment & 0xF, 4);
400 /* copy a run of pixels from the previous frame */
401 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
406 /* coordinate accounting */
407 total_pixels -= size;
408 y += (x + size) / width;
409 x = (x + size) % width;
415 static inline unsigned mul(unsigned a, unsigned b)
417 return (a * b) >> 16;
420 static inline unsigned pow4(unsigned a)
422 unsigned square = mul(a, a);
423 return mul(square, square);
426 static inline unsigned pow5(unsigned a)
428 return mul(pow4(a), a);
431 static uint8_t gamma_corr(uint8_t in) {
432 unsigned lo, hi = 0xff40, target;
434 in = (in << 2) | (in >> 6);
435 /* equivalent float code:
438 return round(pow(in / 256.0, 0.8) * 256);
440 lo = target = in << 8;
442 unsigned mid = (lo + hi) >> 1;
443 unsigned pow = pow5(mid);
444 if (pow > target) hi = mid;
447 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
451 * This is a gamma correction that xan3 applies to all palette entries.
453 * There is a peculiarity, namely that the values are clamped to 253 -
454 * it seems likely that this table was calculated by a buggy fixed-point
455 * implementation, the one above under RUNTIME_GAMMA behaves like this for
457 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
458 * and thus pow(x, 0.8) is still easy to calculate.
459 * Also, the input values are first rotated to the left by 2.
461 static const uint8_t gamma_lookup[256] = {
462 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
463 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
464 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
465 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
466 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
467 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
468 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
469 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
470 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
471 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
472 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
473 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
474 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
475 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
476 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
477 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
478 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
479 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
480 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
481 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
482 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
483 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
484 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
485 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
486 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
487 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
488 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
489 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
490 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
491 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
492 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
493 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
497 static int xan_decode_frame(AVCodecContext *avctx,
498 void *data, int *data_size,
501 const uint8_t *buf = avpkt->data;
502 int ret, buf_size = avpkt->size;
503 XanContext *s = avctx->priv_data;
505 if (avctx->codec->id == CODEC_ID_XAN_WC3) {
506 const uint8_t *buf_end = buf + buf_size;
508 while (buf_end - buf > 8 && tag != VGA__TAG) {
513 tag = bytestream_get_le32(&buf);
514 size = bytestream_get_be32(&buf);
515 size = FFMIN(size, buf_end - buf);
518 if (size < PALETTE_SIZE)
519 return AVERROR_INVALIDDATA;
520 if (s->palettes_count >= PALETTES_MAX)
521 return AVERROR_INVALIDDATA;
522 tmpptr = av_realloc(s->palettes,
523 (s->palettes_count + 1) * AVPALETTE_SIZE);
525 return AVERROR(ENOMEM);
526 s->palettes = tmpptr;
527 tmpptr += s->palettes_count * AVPALETTE_COUNT;
528 for (i = 0; i < PALETTE_COUNT; i++) {
530 int r = gamma_corr(*buf++);
531 int g = gamma_corr(*buf++);
532 int b = gamma_corr(*buf++);
534 int r = gamma_lookup[*buf++];
535 int g = gamma_lookup[*buf++];
536 int b = gamma_lookup[*buf++];
538 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
544 return AVERROR_INVALIDDATA;
545 new_pal = bytestream_get_le32(&buf);
546 if (new_pal < s->palettes_count) {
547 s->cur_palette = new_pal;
549 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
558 buf_size = buf_end - buf;
560 if (s->palettes_count <= 0) {
561 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
562 return AVERROR_INVALIDDATA;
565 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
566 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
569 s->current_frame.reference = 3;
572 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
574 memcpy(s->current_frame.data[1],
575 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
580 if (xan_wc3_decode_frame(s) < 0)
581 return AVERROR_INVALIDDATA;
583 /* release the last frame if it is allocated */
584 if (s->last_frame.data[0])
585 avctx->release_buffer(avctx, &s->last_frame);
587 *data_size = sizeof(AVFrame);
588 *(AVFrame*)data = s->current_frame;
591 FFSWAP(AVFrame, s->current_frame, s->last_frame);
593 /* always report that the buffer was completely consumed */
597 static av_cold int xan_decode_end(AVCodecContext *avctx)
599 XanContext *s = avctx->priv_data;
601 /* release the frames */
602 if (s->last_frame.data[0])
603 avctx->release_buffer(avctx, &s->last_frame);
604 if (s->current_frame.data[0])
605 avctx->release_buffer(avctx, &s->current_frame);
607 av_freep(&s->buffer1);
608 av_freep(&s->buffer2);
609 av_freep(&s->palettes);
614 AVCodec ff_xan_wc3_decoder = {
616 .type = AVMEDIA_TYPE_VIDEO,
617 .id = CODEC_ID_XAN_WC3,
618 .priv_data_size = sizeof(XanContext),
619 .init = xan_decode_init,
620 .close = xan_decode_end,
621 .decode = xan_decode_frame,
622 .capabilities = CODEC_CAP_DR1,
623 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),