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 #include "bytestream.h"
39 #define BITSTREAM_READER_LE
42 #define RUNTIME_GAMMA 0
44 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
45 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
46 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
47 #define PALETTE_COUNT 256
48 #define PALETTE_SIZE (PALETTE_COUNT * 3)
49 #define PALETTES_MAX 256
51 typedef struct XanContext {
53 AVCodecContext *avctx;
55 AVFrame current_frame;
57 const unsigned char *buf;
61 unsigned char *buffer1;
63 unsigned char *buffer2;
74 static av_cold int xan_decode_init(AVCodecContext *avctx)
76 XanContext *s = avctx->priv_data;
81 avctx->pix_fmt = AV_PIX_FMT_PAL8;
83 s->buffer1_size = avctx->width * avctx->height;
84 s->buffer1 = av_malloc(s->buffer1_size);
86 return AVERROR(ENOMEM);
87 s->buffer2_size = avctx->width * avctx->height;
88 s->buffer2 = av_malloc(s->buffer2_size + 130);
90 av_freep(&s->buffer1);
91 return AVERROR(ENOMEM);
93 avcodec_get_frame_defaults(&s->last_frame);
94 avcodec_get_frame_defaults(&s->current_frame);
99 static int xan_huffman_decode(unsigned char *dest, int dest_len,
100 const unsigned char *src, int src_len)
102 unsigned char byte = *src++;
103 unsigned char ival = byte + 0x16;
104 const unsigned char * ptr = src + byte*2;
105 int ptr_len = src_len - 1 - byte*2;
106 unsigned char val = ival;
107 unsigned char *dest_end = dest + dest_len;
111 return AVERROR_INVALIDDATA;
113 init_get_bits(&gb, ptr, ptr_len * 8);
115 while (val != 0x16) {
116 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
122 if (dest >= dest_end)
133 * unpack simple compression
135 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
137 static void xan_unpack(unsigned char *dest, int dest_len,
138 const unsigned char *src, int src_len)
140 unsigned char opcode;
142 unsigned char *dest_org = dest;
143 unsigned char *dest_end = dest + dest_len;
144 const unsigned char *src_end = src + src_len;
146 while (dest < dest_end && src < src_end) {
151 if ((opcode & 0x80) == 0) {
154 back = ((opcode & 0x60) << 3) + *src++ + 1;
155 size2 = ((opcode & 0x1c) >> 2) + 3;
156 } else if ((opcode & 0x40) == 0) {
159 back = (bytestream_get_be16(&src) & 0x3fff) + 1;
160 size2 = (opcode & 0x3f) + 4;
164 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
165 size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
168 if (dest_end - dest < size + size2 ||
169 dest + size - dest_org < back ||
170 src_end - src < size)
172 memcpy(dest, src, size); dest += size; src += size;
173 av_memcpy_backptr(dest, back, size2);
176 int finish = opcode >= 0xfc;
177 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
179 if (dest_end - dest < size || src_end - src < size)
181 memcpy(dest, src, size); dest += size; src += size;
188 static inline void xan_wc3_output_pixel_run(XanContext *s,
189 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
195 int width = s->avctx->width;
196 unsigned char *palette_plane;
198 palette_plane = s->current_frame.data[0];
199 stride = s->current_frame.linesize[0];
200 line_inc = stride - width;
201 index = y * stride + x;
203 while (pixel_count && index < s->frame_size) {
204 int count = FFMIN(pixel_count, width - current_x);
205 memcpy(palette_plane + index, pixel_buffer, count);
206 pixel_count -= count;
208 pixel_buffer += count;
211 if (current_x >= width) {
218 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
219 int pixel_count, int motion_x,
224 int curframe_index, prevframe_index;
225 int curframe_x, prevframe_x;
226 int width = s->avctx->width;
227 unsigned char *palette_plane, *prev_palette_plane;
229 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
230 x + motion_x < 0 || x + motion_x >= s->avctx->width)
233 palette_plane = s->current_frame.data[0];
234 prev_palette_plane = s->last_frame.data[0];
235 if (!prev_palette_plane)
236 prev_palette_plane = palette_plane;
237 stride = s->current_frame.linesize[0];
238 line_inc = stride - width;
239 curframe_index = y * stride + x;
241 prevframe_index = (y + motion_y) * stride + x + motion_x;
242 prevframe_x = x + motion_x;
243 while (pixel_count &&
244 curframe_index < s->frame_size &&
245 prevframe_index < s->frame_size) {
246 int count = FFMIN3(pixel_count, width - curframe_x,
247 width - prevframe_x);
249 memcpy(palette_plane + curframe_index,
250 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 const unsigned char *buf_end = s->buf + s->size;
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 if (vector_segment >= buf_end) {
396 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
397 return AVERROR_INVALIDDATA;
399 /* run-based motion compensation from last frame */
400 motion_x = sign_extend(*vector_segment >> 4, 4);
401 motion_y = sign_extend(*vector_segment & 0xF, 4);
404 /* copy a run of pixels from the previous frame */
405 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
410 /* coordinate accounting */
411 total_pixels -= size;
412 y += (x + size) / width;
413 x = (x + size) % width;
419 static inline unsigned mul(unsigned a, unsigned b)
421 return (a * b) >> 16;
424 static inline unsigned pow4(unsigned a)
426 unsigned square = mul(a, a);
427 return mul(square, square);
430 static inline unsigned pow5(unsigned a)
432 return mul(pow4(a), a);
435 static uint8_t gamma_corr(uint8_t in) {
436 unsigned lo, hi = 0xff40, target;
438 in = (in << 2) | (in >> 6);
439 /* equivalent float code:
442 return round(pow(in / 256.0, 0.8) * 256);
444 lo = target = in << 8;
446 unsigned mid = (lo + hi) >> 1;
447 unsigned pow = pow5(mid);
448 if (pow > target) hi = mid;
451 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
455 * This is a gamma correction that xan3 applies to all palette entries.
457 * There is a peculiarity, namely that the values are clamped to 253 -
458 * it seems likely that this table was calculated by a buggy fixed-point
459 * implementation, the one above under RUNTIME_GAMMA behaves like this for
461 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
462 * and thus pow(x, 0.8) is still easy to calculate.
463 * Also, the input values are first rotated to the left by 2.
465 static const uint8_t gamma_lookup[256] = {
466 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
467 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
468 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
469 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
470 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
471 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
472 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
473 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
474 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
475 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
476 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
477 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
478 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
479 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
480 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
481 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
482 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
483 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
484 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
485 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
486 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
487 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
488 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
489 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
490 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
491 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
492 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
493 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
494 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
495 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
496 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
497 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
501 static int xan_decode_frame(AVCodecContext *avctx,
502 void *data, int *data_size,
505 const uint8_t *buf = avpkt->data;
506 int ret, buf_size = avpkt->size;
507 XanContext *s = avctx->priv_data;
509 if (avctx->codec->id == AV_CODEC_ID_XAN_WC3) {
510 const uint8_t *buf_end = buf + buf_size;
512 while (buf_end - buf > 8 && tag != VGA__TAG) {
517 tag = bytestream_get_le32(&buf);
518 size = bytestream_get_be32(&buf);
520 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
521 return AVERROR_INVALIDDATA;
523 size = FFMIN(size, buf_end - buf);
526 if (size < PALETTE_SIZE)
527 return AVERROR_INVALIDDATA;
528 if (s->palettes_count >= PALETTES_MAX)
529 return AVERROR_INVALIDDATA;
530 tmpptr = av_realloc(s->palettes,
531 (s->palettes_count + 1) * AVPALETTE_SIZE);
533 return AVERROR(ENOMEM);
534 s->palettes = tmpptr;
535 tmpptr += s->palettes_count * AVPALETTE_COUNT;
536 for (i = 0; i < PALETTE_COUNT; i++) {
538 int r = gamma_corr(*buf++);
539 int g = gamma_corr(*buf++);
540 int b = gamma_corr(*buf++);
542 int r = gamma_lookup[*buf++];
543 int g = gamma_lookup[*buf++];
544 int b = gamma_lookup[*buf++];
546 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
552 return AVERROR_INVALIDDATA;
553 new_pal = bytestream_get_le32(&buf);
554 if (new_pal < s->palettes_count) {
555 s->cur_palette = new_pal;
557 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
566 buf_size = buf_end - buf;
568 if (s->palettes_count <= 0) {
569 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
570 return AVERROR_INVALIDDATA;
573 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
574 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
577 s->current_frame.reference = 3;
580 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
582 memcpy(s->current_frame.data[1],
583 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
588 if (xan_wc3_decode_frame(s) < 0)
589 return AVERROR_INVALIDDATA;
591 /* release the last frame if it is allocated */
592 if (s->last_frame.data[0])
593 avctx->release_buffer(avctx, &s->last_frame);
595 *data_size = sizeof(AVFrame);
596 *(AVFrame*)data = s->current_frame;
599 FFSWAP(AVFrame, s->current_frame, s->last_frame);
601 /* always report that the buffer was completely consumed */
605 static av_cold int xan_decode_end(AVCodecContext *avctx)
607 XanContext *s = avctx->priv_data;
609 /* release the frames */
610 if (s->last_frame.data[0])
611 avctx->release_buffer(avctx, &s->last_frame);
612 if (s->current_frame.data[0])
613 avctx->release_buffer(avctx, &s->current_frame);
615 av_freep(&s->buffer1);
616 av_freep(&s->buffer2);
617 av_freep(&s->palettes);
622 AVCodec ff_xan_wc3_decoder = {
624 .type = AVMEDIA_TYPE_VIDEO,
625 .id = AV_CODEC_ID_XAN_WC3,
626 .priv_data_size = sizeof(XanContext),
627 .init = xan_decode_init,
628 .close = xan_decode_end,
629 .decode = xan_decode_frame,
630 .capabilities = CODEC_CAP_DR1,
631 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),