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;
57 const unsigned char *buf;
61 unsigned char *buffer1;
63 unsigned char *buffer2;
74 static av_cold int xan_decode_end(AVCodecContext *avctx);
76 static av_cold int xan_decode_init(AVCodecContext *avctx)
78 XanContext *s = avctx->priv_data;
83 avctx->pix_fmt = AV_PIX_FMT_PAL8;
85 s->buffer1_size = avctx->width * avctx->height;
86 s->buffer1 = av_malloc(s->buffer1_size);
88 return AVERROR(ENOMEM);
89 s->buffer2_size = avctx->width * avctx->height;
90 s->buffer2 = av_malloc(s->buffer2_size + 130);
92 av_freep(&s->buffer1);
93 return AVERROR(ENOMEM);
95 s->last_frame = av_frame_alloc();
97 xan_decode_end(avctx);
98 return AVERROR(ENOMEM);
104 static int xan_huffman_decode(unsigned char *dest, int dest_len,
105 const unsigned char *src, int src_len)
107 unsigned char byte = *src++;
108 unsigned char ival = byte + 0x16;
109 const unsigned char * ptr = src + byte*2;
110 int ptr_len = src_len - 1 - byte*2;
111 unsigned char val = ival;
112 unsigned char *dest_end = dest + dest_len;
116 return AVERROR_INVALIDDATA;
118 init_get_bits(&gb, ptr, ptr_len * 8);
120 while (val != 0x16) {
121 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
123 return AVERROR_INVALIDDATA;
127 if (dest >= dest_end)
138 * unpack simple compression
140 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
142 static void xan_unpack(unsigned char *dest, int dest_len,
143 const unsigned char *src, int src_len)
145 unsigned char opcode;
147 unsigned char *dest_org = dest;
148 unsigned char *dest_end = dest + dest_len;
151 bytestream2_init(&ctx, src, src_len);
152 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
153 opcode = bytestream2_get_byte(&ctx);
157 if ((opcode & 0x80) == 0) {
160 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
161 size2 = ((opcode & 0x1c) >> 2) + 3;
162 } else if ((opcode & 0x40) == 0) {
163 size = bytestream2_peek_byte(&ctx) >> 6;
165 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
166 size2 = (opcode & 0x3f) + 4;
170 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
171 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
174 if (dest_end - dest < size + size2 ||
175 dest + size - dest_org < back ||
176 bytestream2_get_bytes_left(&ctx) < size)
178 bytestream2_get_buffer(&ctx, dest, size);
180 av_memcpy_backptr(dest, back, size2);
183 int finish = opcode >= 0xfc;
184 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
186 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
188 bytestream2_get_buffer(&ctx, dest, size);
196 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
197 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
203 int width = s->avctx->width;
204 unsigned char *palette_plane;
206 palette_plane = frame->data[0];
207 stride = frame->linesize[0];
208 line_inc = stride - width;
209 index = y * stride + x;
211 while (pixel_count && index < s->frame_size) {
212 int count = FFMIN(pixel_count, width - current_x);
213 memcpy(palette_plane + index, pixel_buffer, count);
214 pixel_count -= count;
216 pixel_buffer += count;
219 if (current_x >= width) {
226 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
228 int pixel_count, int motion_x,
233 int curframe_index, prevframe_index;
234 int curframe_x, prevframe_x;
235 int width = s->avctx->width;
236 unsigned char *palette_plane, *prev_palette_plane;
238 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
239 x + motion_x < 0 || x + motion_x >= s->avctx->width)
242 palette_plane = frame->data[0];
243 prev_palette_plane = s->last_frame->data[0];
244 if (!prev_palette_plane)
245 prev_palette_plane = palette_plane;
246 stride = frame->linesize[0];
247 line_inc = stride - width;
248 curframe_index = y * stride + x;
250 prevframe_index = (y + motion_y) * stride + x + motion_x;
251 prevframe_x = x + motion_x;
252 while (pixel_count &&
253 curframe_index < s->frame_size &&
254 prevframe_index < s->frame_size) {
255 int count = FFMIN3(pixel_count, width - curframe_x,
256 width - prevframe_x);
258 memcpy(palette_plane + curframe_index,
259 prev_palette_plane + prevframe_index, count);
260 pixel_count -= count;
261 curframe_index += count;
262 prevframe_index += count;
264 prevframe_x += count;
266 if (curframe_x >= width) {
267 curframe_index += line_inc;
271 if (prevframe_x >= width) {
272 prevframe_index += line_inc;
278 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
281 int width = s->avctx->width;
282 int height = s->avctx->height;
283 int total_pixels = width * height;
284 unsigned char opcode;
285 unsigned char flag = 0;
287 int motion_x, motion_y;
290 unsigned char *opcode_buffer = s->buffer1;
291 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
292 int opcode_buffer_size = s->buffer1_size;
293 const unsigned char *imagedata_buffer = s->buffer2;
295 /* pointers to segments inside the compressed chunk */
296 const unsigned char *huffman_segment;
297 const unsigned char *size_segment;
298 const unsigned char *vector_segment;
299 const unsigned char *imagedata_segment;
300 const unsigned char *buf_end = s->buf + s->size;
301 int huffman_offset, size_offset, vector_offset, imagedata_offset,
305 return AVERROR_INVALIDDATA;
307 huffman_offset = AV_RL16(&s->buf[0]);
308 size_offset = AV_RL16(&s->buf[2]);
309 vector_offset = AV_RL16(&s->buf[4]);
310 imagedata_offset = AV_RL16(&s->buf[6]);
312 if (huffman_offset >= s->size ||
313 size_offset >= s->size ||
314 vector_offset >= s->size ||
315 imagedata_offset >= s->size)
316 return AVERROR_INVALIDDATA;
318 huffman_segment = s->buf + huffman_offset;
319 size_segment = s->buf + size_offset;
320 vector_segment = s->buf + vector_offset;
321 imagedata_segment = s->buf + imagedata_offset;
323 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
324 huffman_segment, s->size - huffman_offset) < 0)
325 return AVERROR_INVALIDDATA;
327 if (imagedata_segment[0] == 2) {
328 xan_unpack(s->buffer2, s->buffer2_size,
329 &imagedata_segment[1], s->size - imagedata_offset - 1);
330 imagedata_size = s->buffer2_size;
332 imagedata_size = s->size - imagedata_offset - 1;
333 imagedata_buffer = &imagedata_segment[1];
336 /* use the decoded data segments to build the frame */
338 while (total_pixels && opcode_buffer < opcode_buffer_end) {
340 opcode = *opcode_buffer++;
367 size += (opcode - 10);
372 if (buf_end - size_segment < 1) {
373 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
374 return AVERROR_INVALIDDATA;
376 size = *size_segment++;
381 if (buf_end - size_segment < 2) {
382 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
383 return AVERROR_INVALIDDATA;
385 size = AV_RB16(&size_segment[0]);
391 if (buf_end - size_segment < 3) {
392 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
393 return AVERROR_INVALIDDATA;
395 size = AV_RB24(size_segment);
400 if (size > total_pixels)
406 /* run of (size) pixels is unchanged from last frame */
407 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
409 /* output a run of pixels from imagedata_buffer */
410 if (imagedata_size < size)
412 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
413 imagedata_buffer += size;
414 imagedata_size -= size;
417 if (vector_segment >= buf_end) {
418 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
419 return AVERROR_INVALIDDATA;
421 /* run-based motion compensation from last frame */
422 motion_x = sign_extend(*vector_segment >> 4, 4);
423 motion_y = sign_extend(*vector_segment & 0xF, 4);
426 /* copy a run of pixels from the previous frame */
427 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
432 /* coordinate accounting */
433 total_pixels -= size;
434 y += (x + size) / width;
435 x = (x + size) % width;
441 static inline unsigned mul(unsigned a, unsigned b)
443 return (a * b) >> 16;
446 static inline unsigned pow4(unsigned a)
448 unsigned square = mul(a, a);
449 return mul(square, square);
452 static inline unsigned pow5(unsigned a)
454 return mul(pow4(a), a);
457 static uint8_t gamma_corr(uint8_t in) {
458 unsigned lo, hi = 0xff40, target;
460 in = (in << 2) | (in >> 6);
461 /* equivalent float code:
464 return round(pow(in / 256.0, 0.8) * 256);
466 lo = target = in << 8;
468 unsigned mid = (lo + hi) >> 1;
469 unsigned pow = pow5(mid);
470 if (pow > target) hi = mid;
473 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
477 * This is a gamma correction that xan3 applies to all palette entries.
479 * There is a peculiarity, namely that the values are clamped to 253 -
480 * it seems likely that this table was calculated by a buggy fixed-point
481 * implementation, the one above under RUNTIME_GAMMA behaves like this for
483 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
484 * and thus pow(x, 0.8) is still easy to calculate.
485 * Also, the input values are first rotated to the left by 2.
487 static const uint8_t gamma_lookup[256] = {
488 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
489 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
490 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
491 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
492 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
493 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
494 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
495 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
496 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
497 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
498 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
499 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
500 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
501 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
502 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
503 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
504 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
505 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
506 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
507 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
508 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
509 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
510 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
511 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
512 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
513 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
514 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
515 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
516 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
517 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
518 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
519 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
523 static int xan_decode_frame(AVCodecContext *avctx,
524 void *data, int *got_frame,
527 AVFrame *frame = data;
528 const uint8_t *buf = avpkt->data;
529 int ret, buf_size = avpkt->size;
530 XanContext *s = avctx->priv_data;
534 bytestream2_init(&ctx, buf, buf_size);
535 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
540 tag = bytestream2_get_le32(&ctx);
541 size = bytestream2_get_be32(&ctx);
543 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
544 return AVERROR_INVALIDDATA;
546 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
549 if (size < PALETTE_SIZE)
550 return AVERROR_INVALIDDATA;
551 if (s->palettes_count >= PALETTES_MAX)
552 return AVERROR_INVALIDDATA;
553 tmpptr = av_realloc(s->palettes,
554 (s->palettes_count + 1) * AVPALETTE_SIZE);
556 return AVERROR(ENOMEM);
557 s->palettes = tmpptr;
558 tmpptr += s->palettes_count * AVPALETTE_COUNT;
559 for (i = 0; i < PALETTE_COUNT; i++) {
561 int r = gamma_corr(bytestream2_get_byteu(&ctx));
562 int g = gamma_corr(bytestream2_get_byteu(&ctx));
563 int b = gamma_corr(bytestream2_get_byteu(&ctx));
565 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
566 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
567 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
569 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
575 return AVERROR_INVALIDDATA;
576 new_pal = bytestream2_get_le32(&ctx);
577 if (new_pal < s->palettes_count) {
578 s->cur_palette = new_pal;
580 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
585 bytestream2_skip(&ctx, size);
589 buf_size = bytestream2_get_bytes_left(&ctx);
591 if (s->palettes_count <= 0) {
592 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
593 return AVERROR_INVALIDDATA;
596 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0)
600 s->frame_size = frame->linesize[0] * s->avctx->height;
602 memcpy(frame->data[1],
603 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
608 if (xan_wc3_decode_frame(s, frame) < 0)
609 return AVERROR_INVALIDDATA;
611 av_frame_unref(s->last_frame);
612 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
617 /* always report that the buffer was completely consumed */
621 static av_cold int xan_decode_end(AVCodecContext *avctx)
623 XanContext *s = avctx->priv_data;
625 av_frame_free(&s->last_frame);
627 av_freep(&s->buffer1);
628 av_freep(&s->buffer2);
629 av_freep(&s->palettes);
634 AVCodec ff_xan_wc3_decoder = {
636 .type = AVMEDIA_TYPE_VIDEO,
637 .id = AV_CODEC_ID_XAN_WC3,
638 .priv_data_size = sizeof(XanContext),
639 .init = xan_decode_init,
640 .close = xan_decode_end,
641 .decode = xan_decode_frame,
642 .capabilities = CODEC_CAP_DR1,
643 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),