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"
37 #include "bytestream.h"
38 #define ALT_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);
98 static int xan_huffman_decode(unsigned char *dest, int dest_len,
99 const unsigned char *src, int src_len)
101 unsigned char byte = *src++;
102 unsigned char ival = byte + 0x16;
103 const unsigned char * ptr = src + byte*2;
104 int ptr_len = src_len - 1 - byte*2;
105 unsigned char val = ival;
106 unsigned char *dest_end = dest + dest_len;
110 return AVERROR_INVALIDDATA;
112 init_get_bits(&gb, ptr, ptr_len * 8);
114 while ( val != 0x16 ) {
115 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
121 if (dest >= dest_end)
132 * unpack simple compression
134 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
136 static void xan_unpack(unsigned char *dest, int dest_len,
137 const unsigned char *src, int src_len)
139 unsigned char opcode;
141 unsigned char *dest_org = dest;
142 unsigned char *dest_end = dest + dest_len;
143 const unsigned char *src_end = src + src_len;
145 while (dest < dest_end && src < src_end) {
150 if ( (opcode & 0x80) == 0 ) {
154 back = ((opcode & 0x60) << 3) + *src++ + 1;
155 size2 = ((opcode & 0x1c) >> 2) + 3;
157 } else if ( (opcode & 0x40) == 0 ) {
161 back = (bytestream_get_be16(&src) & 0x3fff) + 1;
162 size2 = (opcode & 0x3f) + 4;
168 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
169 size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
171 if (dest_end - dest < size + size2 ||
172 dest + size - dest_org < back ||
173 src_end - src < size)
175 memcpy(dest, src, size); dest += size; src += size;
176 av_memcpy_backptr(dest, back, size2);
179 int finish = opcode >= 0xfc;
180 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
182 if (dest_end - dest < size || src_end - src < size)
184 memcpy(dest, src, size); dest += size; src += size;
191 static inline void xan_wc3_output_pixel_run(XanContext *s,
192 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
198 int width = s->avctx->width;
199 unsigned char *palette_plane;
201 palette_plane = s->current_frame.data[0];
202 stride = s->current_frame.linesize[0];
203 line_inc = stride - width;
204 index = y * stride + x;
206 while(pixel_count && (index < s->frame_size)) {
207 int count = FFMIN(pixel_count, width - current_x);
208 memcpy(palette_plane + index, pixel_buffer, count);
209 pixel_count -= count;
211 pixel_buffer += count;
214 if (current_x >= width) {
221 static inline void xan_wc3_copy_pixel_run(XanContext *s,
222 int x, int y, int pixel_count, int motion_x, int motion_y)
226 int curframe_index, prevframe_index;
227 int curframe_x, prevframe_x;
228 int width = s->avctx->width;
229 unsigned char *palette_plane, *prev_palette_plane;
231 if ( y + motion_y < 0 || y + motion_y >= s->avctx->height ||
232 x + motion_x < 0 || x + motion_x >= s->avctx->width)
235 palette_plane = s->current_frame.data[0];
236 prev_palette_plane = s->last_frame.data[0];
237 if (!prev_palette_plane)
238 prev_palette_plane = palette_plane;
239 stride = s->current_frame.linesize[0];
240 line_inc = stride - width;
241 curframe_index = y * stride + x;
243 prevframe_index = (y + motion_y) * stride + x + motion_x;
244 prevframe_x = x + motion_x;
246 curframe_index < s->frame_size &&
247 prevframe_index < s->frame_size) {
248 int count = FFMIN3(pixel_count, width - curframe_x, width - prevframe_x);
250 memcpy(palette_plane + curframe_index, 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 int huffman_offset, size_offset, vector_offset, imagedata_offset, imagedata_size;
293 return AVERROR_INVALIDDATA;
295 huffman_offset = AV_RL16(&s->buf[0]);
296 size_offset = AV_RL16(&s->buf[2]);
297 vector_offset = AV_RL16(&s->buf[4]);
298 imagedata_offset = AV_RL16(&s->buf[6]);
300 if (huffman_offset >= s->size ||
301 size_offset >= s->size ||
302 vector_offset >= s->size ||
303 imagedata_offset >= s->size)
304 return AVERROR_INVALIDDATA;
306 huffman_segment = s->buf + huffman_offset;
307 size_segment = s->buf + size_offset;
308 vector_segment = s->buf + vector_offset;
309 imagedata_segment = s->buf + imagedata_offset;
311 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
312 huffman_segment, s->size - huffman_offset) < 0)
313 return AVERROR_INVALIDDATA;
315 if (imagedata_segment[0] == 2) {
316 xan_unpack(s->buffer2, s->buffer2_size,
317 &imagedata_segment[1], s->size - imagedata_offset - 1);
318 imagedata_size = s->buffer2_size;
320 imagedata_size = s->size - imagedata_offset - 1;
321 imagedata_buffer = &imagedata_segment[1];
324 /* use the decoded data segments to build the frame */
326 while (total_pixels && opcode_buffer < opcode_buffer_end) {
328 opcode = *opcode_buffer++;
355 size += (opcode - 10);
360 size = *size_segment++;
365 size = AV_RB16(&size_segment[0]);
371 size = AV_RB24(size_segment);
375 if (size > total_pixels)
381 /* run of (size) pixels is unchanged from last frame */
382 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
384 /* output a run of pixels from imagedata_buffer */
385 if (imagedata_size < size)
387 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
388 imagedata_buffer += size;
389 imagedata_size -= size;
392 /* run-based motion compensation from last frame */
393 motion_x = sign_extend(*vector_segment >> 4, 4);
394 motion_y = sign_extend(*vector_segment & 0xF, 4);
397 /* copy a run of pixels from the previous frame */
398 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
403 /* coordinate accounting */
404 total_pixels -= size;
405 y += (x + size) / width;
406 x = (x + size) % width;
412 static inline unsigned mul(unsigned a, unsigned b)
414 return (a * b) >> 16;
417 static inline unsigned pow4(unsigned a)
419 unsigned square = mul(a, a);
420 return mul(square, square);
423 static inline unsigned pow5(unsigned a)
425 return mul(pow4(a), a);
428 static uint8_t gamma_corr(uint8_t in) {
429 unsigned lo, hi = 0xff40, target;
431 in = (in << 2) | (in >> 6);
432 /* equivalent float code:
435 return round(pow(in / 256.0, 0.8) * 256);
437 lo = target = in << 8;
439 unsigned mid = (lo + hi) >> 1;
440 unsigned pow = pow5(mid);
441 if (pow > target) hi = mid;
444 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
448 * This is a gamma correction that xan3 applies to all palette entries.
450 * There is a peculiarity, namely that the values are clamped to 253 -
451 * it seems likely that this table was calculated by a buggy fixed-point
452 * implementation, the one above under RUNTIME_GAMMA behaves like this for
454 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
455 * and thus pow(x, 0.8) is still easy to calculate.
456 * Also, the input values are first rotated to the left by 2.
458 static const uint8_t gamma_lookup[256] = {
459 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
460 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
461 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
462 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
463 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
464 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
465 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
466 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
467 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
468 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
469 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
470 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
471 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
472 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
473 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
474 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
475 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
476 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
477 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
478 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
479 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
480 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
481 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
482 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
483 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
484 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
485 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
486 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
487 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
488 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
489 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
490 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
494 static int xan_decode_frame(AVCodecContext *avctx,
495 void *data, int *data_size,
498 const uint8_t *buf = avpkt->data;
499 int ret, buf_size = avpkt->size;
500 XanContext *s = avctx->priv_data;
502 if (avctx->codec->id == CODEC_ID_XAN_WC3) {
503 const uint8_t *buf_end = buf + buf_size;
505 while (buf_end - buf > 8 && tag != VGA__TAG) {
510 tag = bytestream_get_le32(&buf);
511 size = bytestream_get_be32(&buf);
512 size = FFMIN(size, buf_end - buf);
515 if (size < PALETTE_SIZE)
516 return AVERROR_INVALIDDATA;
517 if (s->palettes_count >= PALETTES_MAX)
518 return AVERROR_INVALIDDATA;
519 tmpptr = av_realloc(s->palettes, (s->palettes_count + 1) * AVPALETTE_SIZE);
521 return AVERROR(ENOMEM);
522 s->palettes = tmpptr;
523 tmpptr += s->palettes_count * AVPALETTE_COUNT;
524 for (i = 0; i < PALETTE_COUNT; i++) {
526 int r = gamma_corr(*buf++);
527 int g = gamma_corr(*buf++);
528 int b = gamma_corr(*buf++);
530 int r = gamma_lookup[*buf++];
531 int g = gamma_lookup[*buf++];
532 int b = gamma_lookup[*buf++];
534 *tmpptr++ = (r << 16) | (g << 8) | b;
540 return AVERROR_INVALIDDATA;
541 new_pal = bytestream_get_le32(&buf);
542 if (new_pal < s->palettes_count) {
543 s->cur_palette = new_pal;
545 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
554 buf_size = buf_end - buf;
556 if (s->palettes_count <= 0) {
557 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
558 return AVERROR_INVALIDDATA;
561 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
562 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
565 s->current_frame.reference = 3;
568 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
570 memcpy(s->current_frame.data[1], s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
575 if (xan_wc3_decode_frame(s) < 0)
576 return AVERROR_INVALIDDATA;
578 /* release the last frame if it is allocated */
579 if (s->last_frame.data[0])
580 avctx->release_buffer(avctx, &s->last_frame);
582 *data_size = sizeof(AVFrame);
583 *(AVFrame*)data = s->current_frame;
586 FFSWAP(AVFrame, s->current_frame, s->last_frame);
588 /* always report that the buffer was completely consumed */
592 static av_cold int xan_decode_end(AVCodecContext *avctx)
594 XanContext *s = avctx->priv_data;
596 /* release the frames */
597 if (s->last_frame.data[0])
598 avctx->release_buffer(avctx, &s->last_frame);
599 if (s->current_frame.data[0])
600 avctx->release_buffer(avctx, &s->current_frame);
602 av_freep(&s->buffer1);
603 av_freep(&s->buffer2);
604 av_freep(&s->palettes);
609 AVCodec ff_xan_wc3_decoder = {
611 .type = AVMEDIA_TYPE_VIDEO,
612 .id = CODEC_ID_XAN_WC3,
613 .priv_data_size = sizeof(XanContext),
614 .init = xan_decode_init,
615 .close = xan_decode_end,
616 .decode = xan_decode_frame,
617 .capabilities = CODEC_CAP_DR1,
618 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),