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
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 if (buf_end - size_segment < 1) {
364 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
365 return AVERROR_INVALIDDATA;
367 size = *size_segment++;
372 if (buf_end - size_segment < 2) {
373 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
374 return AVERROR_INVALIDDATA;
376 size = AV_RB16(&size_segment[0]);
382 if (buf_end - size_segment < 3) {
383 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
384 return AVERROR_INVALIDDATA;
386 size = AV_RB24(size_segment);
391 if (size > total_pixels)
397 /* run of (size) pixels is unchanged from last frame */
398 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
400 /* output a run of pixels from imagedata_buffer */
401 if (imagedata_size < size)
403 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
404 imagedata_buffer += size;
405 imagedata_size -= size;
408 if (vector_segment >= buf_end) {
409 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
410 return AVERROR_INVALIDDATA;
412 /* run-based motion compensation from last frame */
413 motion_x = sign_extend(*vector_segment >> 4, 4);
414 motion_y = sign_extend(*vector_segment & 0xF, 4);
417 /* copy a run of pixels from the previous frame */
418 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
423 /* coordinate accounting */
424 total_pixels -= size;
425 y += (x + size) / width;
426 x = (x + size) % width;
432 static inline unsigned mul(unsigned a, unsigned b)
434 return (a * b) >> 16;
437 static inline unsigned pow4(unsigned a)
439 unsigned square = mul(a, a);
440 return mul(square, square);
443 static inline unsigned pow5(unsigned a)
445 return mul(pow4(a), a);
448 static uint8_t gamma_corr(uint8_t in) {
449 unsigned lo, hi = 0xff40, target;
451 in = (in << 2) | (in >> 6);
452 /* equivalent float code:
455 return round(pow(in / 256.0, 0.8) * 256);
457 lo = target = in << 8;
459 unsigned mid = (lo + hi) >> 1;
460 unsigned pow = pow5(mid);
461 if (pow > target) hi = mid;
464 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
468 * This is a gamma correction that xan3 applies to all palette entries.
470 * There is a peculiarity, namely that the values are clamped to 253 -
471 * it seems likely that this table was calculated by a buggy fixed-point
472 * implementation, the one above under RUNTIME_GAMMA behaves like this for
474 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
475 * and thus pow(x, 0.8) is still easy to calculate.
476 * Also, the input values are first rotated to the left by 2.
478 static const uint8_t gamma_lookup[256] = {
479 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
480 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
481 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
482 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
483 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
484 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
485 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
486 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
487 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
488 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
489 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
490 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
491 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
492 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
493 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
494 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
495 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
496 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
497 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
498 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
499 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
500 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
501 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
502 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
503 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
504 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
505 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
506 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
507 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
508 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
509 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
510 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
514 static int xan_decode_frame(AVCodecContext *avctx,
515 void *data, int *got_frame,
518 const uint8_t *buf = avpkt->data;
519 int ret, buf_size = avpkt->size;
520 XanContext *s = avctx->priv_data;
522 if (avctx->codec->id == AV_CODEC_ID_XAN_WC3) {
523 const uint8_t *buf_end = buf + buf_size;
525 while (buf_end - buf > 8 && tag != VGA__TAG) {
530 tag = bytestream_get_le32(&buf);
531 size = bytestream_get_be32(&buf);
533 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
534 return AVERROR_INVALIDDATA;
536 size = FFMIN(size, buf_end - buf);
539 if (size < PALETTE_SIZE)
540 return AVERROR_INVALIDDATA;
541 if (s->palettes_count >= PALETTES_MAX)
542 return AVERROR_INVALIDDATA;
543 tmpptr = av_realloc(s->palettes,
544 (s->palettes_count + 1) * AVPALETTE_SIZE);
546 return AVERROR(ENOMEM);
547 s->palettes = tmpptr;
548 tmpptr += s->palettes_count * AVPALETTE_COUNT;
549 for (i = 0; i < PALETTE_COUNT; i++) {
551 int r = gamma_corr(*buf++);
552 int g = gamma_corr(*buf++);
553 int b = gamma_corr(*buf++);
555 int r = gamma_lookup[*buf++];
556 int g = gamma_lookup[*buf++];
557 int b = gamma_lookup[*buf++];
559 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
565 return AVERROR_INVALIDDATA;
566 new_pal = bytestream_get_le32(&buf);
567 if (new_pal < s->palettes_count) {
568 s->cur_palette = new_pal;
570 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
579 buf_size = buf_end - buf;
581 if (s->palettes_count <= 0) {
582 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
583 return AVERROR_INVALIDDATA;
586 if ((ret = ff_get_buffer(avctx, &s->current_frame))) {
587 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
590 s->current_frame.reference = 3;
593 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
595 memcpy(s->current_frame.data[1],
596 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
601 if (xan_wc3_decode_frame(s) < 0)
602 return AVERROR_INVALIDDATA;
604 /* release the last frame if it is allocated */
605 if (s->last_frame.data[0])
606 avctx->release_buffer(avctx, &s->last_frame);
609 *(AVFrame*)data = s->current_frame;
612 FFSWAP(AVFrame, s->current_frame, s->last_frame);
614 /* always report that the buffer was completely consumed */
618 static av_cold int xan_decode_end(AVCodecContext *avctx)
620 XanContext *s = avctx->priv_data;
622 /* release the frames */
623 if (s->last_frame.data[0])
624 avctx->release_buffer(avctx, &s->last_frame);
625 if (s->current_frame.data[0])
626 avctx->release_buffer(avctx, &s->current_frame);
628 av_freep(&s->buffer1);
629 av_freep(&s->buffer2);
630 av_freep(&s->palettes);
635 AVCodec ff_xan_wc3_decoder = {
637 .type = AVMEDIA_TYPE_VIDEO,
638 .id = AV_CODEC_ID_XAN_WC3,
639 .priv_data_size = sizeof(XanContext),
640 .init = xan_decode_init,
641 .close = xan_decode_end,
642 .decode = xan_decode_frame,
643 .capabilities = CODEC_CAP_DR1,
644 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),