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"
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_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);
97 static int xan_huffman_decode(unsigned char *dest, int dest_len,
98 const unsigned char *src, int src_len)
100 unsigned char byte = *src++;
101 unsigned char ival = byte + 0x16;
102 const unsigned char * ptr = src + byte*2;
103 int ptr_len = src_len - 1 - byte*2;
104 unsigned char val = ival;
105 unsigned char *dest_end = dest + dest_len;
106 unsigned char *dest_start = dest;
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;
117 return AVERROR_INVALIDDATA;
121 if (dest >= dest_end)
128 return dest - dest_start;
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;
145 bytestream2_init(&ctx, src, src_len);
146 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
147 opcode = bytestream2_get_byte(&ctx);
151 if ((opcode & 0x80) == 0) {
154 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
155 size2 = ((opcode & 0x1c) >> 2) + 3;
156 } else if ((opcode & 0x40) == 0) {
157 size = bytestream2_peek_byte(&ctx) >> 6;
159 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
160 size2 = (opcode & 0x3f) + 4;
164 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
165 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
168 if (dest_end - dest < size + size2 ||
169 dest + size - dest_org < back ||
170 bytestream2_get_bytes_left(&ctx) < size)
172 bytestream2_get_buffer(&ctx, dest, 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 || bytestream2_get_bytes_left(&ctx) < size)
182 bytestream2_get_buffer(&ctx, dest, size);
190 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
191 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
197 int width = s->avctx->width;
198 unsigned char *palette_plane;
200 palette_plane = frame->data[0];
201 stride = frame->linesize[0];
202 line_inc = stride - width;
203 index = y * stride + x;
205 while (pixel_count && index < s->frame_size) {
206 int count = FFMIN(pixel_count, width - current_x);
207 memcpy(palette_plane + index, pixel_buffer, count);
208 pixel_count -= count;
210 pixel_buffer += count;
213 if (current_x >= width) {
220 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
222 int pixel_count, int motion_x,
227 int curframe_index, prevframe_index;
228 int curframe_x, prevframe_x;
229 int width = s->avctx->width;
230 unsigned char *palette_plane, *prev_palette_plane;
232 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
233 x + motion_x < 0 || x + motion_x >= s->avctx->width)
236 palette_plane = frame->data[0];
237 prev_palette_plane = s->last_frame.data[0];
238 if (!prev_palette_plane)
239 prev_palette_plane = palette_plane;
240 stride = frame->linesize[0];
241 line_inc = stride - width;
242 curframe_index = y * stride + x;
244 prevframe_index = (y + motion_y) * stride + x + motion_x;
245 prevframe_x = x + motion_x;
246 while (pixel_count &&
247 curframe_index < s->frame_size &&
248 prevframe_index < s->frame_size) {
249 int count = FFMIN3(pixel_count, width - curframe_x,
250 width - prevframe_x);
252 memcpy(palette_plane + curframe_index,
253 prev_palette_plane + prevframe_index, count);
254 pixel_count -= count;
255 curframe_index += count;
256 prevframe_index += count;
258 prevframe_x += count;
260 if (curframe_x >= width) {
261 curframe_index += line_inc;
265 if (prevframe_x >= width) {
266 prevframe_index += line_inc;
272 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
275 int width = s->avctx->width;
276 int height = s->avctx->height;
277 int total_pixels = width * height;
278 unsigned char opcode;
279 unsigned char flag = 0;
281 int motion_x, motion_y;
284 unsigned char *opcode_buffer = s->buffer1;
285 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
286 int opcode_buffer_size = s->buffer1_size;
287 const unsigned char *imagedata_buffer = s->buffer2;
289 /* pointers to segments inside the compressed chunk */
290 const unsigned char *huffman_segment;
291 GetByteContext size_segment;
292 GetByteContext vector_segment;
293 const unsigned char *imagedata_segment;
294 int huffman_offset, size_offset, vector_offset, imagedata_offset,
298 return AVERROR_INVALIDDATA;
300 huffman_offset = AV_RL16(&s->buf[0]);
301 size_offset = AV_RL16(&s->buf[2]);
302 vector_offset = AV_RL16(&s->buf[4]);
303 imagedata_offset = AV_RL16(&s->buf[6]);
305 if (huffman_offset >= s->size ||
306 size_offset >= s->size ||
307 vector_offset >= s->size ||
308 imagedata_offset >= s->size)
309 return AVERROR_INVALIDDATA;
311 huffman_segment = s->buf + huffman_offset;
312 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
313 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
314 imagedata_segment = s->buf + imagedata_offset;
316 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
317 huffman_segment, s->size - huffman_offset)) < 0)
318 return AVERROR_INVALIDDATA;
319 opcode_buffer_end = opcode_buffer + ret;
321 if (imagedata_segment[0] == 2) {
322 xan_unpack(s->buffer2, s->buffer2_size,
323 &imagedata_segment[1], s->size - imagedata_offset - 1);
324 imagedata_size = s->buffer2_size;
326 imagedata_size = s->size - imagedata_offset - 1;
327 imagedata_buffer = &imagedata_segment[1];
330 /* use the decoded data segments to build the frame */
332 while (total_pixels && opcode_buffer < opcode_buffer_end) {
334 opcode = *opcode_buffer++;
361 size += (opcode - 10);
366 size = bytestream2_get_byte(&size_segment);
371 size = bytestream2_get_be16(&size_segment);
376 size = bytestream2_get_be24(&size_segment);
380 if (size > total_pixels)
386 /* run of (size) pixels is unchanged from last frame */
387 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
389 /* output a run of pixels from imagedata_buffer */
390 if (imagedata_size < size)
392 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
393 imagedata_buffer += size;
394 imagedata_size -= size;
397 /* run-based motion compensation from last frame */
398 uint8_t vector = bytestream2_get_byte(&vector_segment);
399 motion_x = sign_extend(vector >> 4, 4);
400 motion_y = sign_extend(vector & 0xF, 4);
402 /* copy a run of pixels from the previous frame */
403 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
408 /* coordinate accounting */
409 total_pixels -= size;
410 y += (x + size) / width;
411 x = (x + size) % width;
417 static inline unsigned mul(unsigned a, unsigned b)
419 return (a * b) >> 16;
422 static inline unsigned pow4(unsigned a)
424 unsigned square = mul(a, a);
425 return mul(square, square);
428 static inline unsigned pow5(unsigned a)
430 return mul(pow4(a), a);
433 static uint8_t gamma_corr(uint8_t in) {
434 unsigned lo, hi = 0xff40, target;
436 in = (in << 2) | (in >> 6);
437 /* equivalent float code:
440 return round(pow(in / 256.0, 0.8) * 256);
442 lo = target = in << 8;
444 unsigned mid = (lo + hi) >> 1;
445 unsigned pow = pow5(mid);
446 if (pow > target) hi = mid;
449 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
453 * This is a gamma correction that xan3 applies to all palette entries.
455 * There is a peculiarity, namely that the values are clamped to 253 -
456 * it seems likely that this table was calculated by a buggy fixed-point
457 * implementation, the one above under RUNTIME_GAMMA behaves like this for
459 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
460 * and thus pow(x, 0.8) is still easy to calculate.
461 * Also, the input values are first rotated to the left by 2.
463 static const uint8_t gamma_lookup[256] = {
464 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
465 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
466 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
467 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
468 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
469 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
470 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
471 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
472 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
473 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
474 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
475 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
476 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
477 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
478 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
479 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
480 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
481 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
482 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
483 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
484 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
485 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
486 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
487 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
488 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
489 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
490 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
491 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
492 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
493 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
494 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
495 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
499 static int xan_decode_frame(AVCodecContext *avctx,
500 void *data, int *got_frame,
503 AVFrame *frame = data;
504 const uint8_t *buf = avpkt->data;
505 int ret, buf_size = avpkt->size;
506 XanContext *s = avctx->priv_data;
510 bytestream2_init(&ctx, buf, buf_size);
511 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
516 tag = bytestream2_get_le32(&ctx);
517 size = bytestream2_get_be32(&ctx);
518 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
521 if (size < PALETTE_SIZE)
522 return AVERROR_INVALIDDATA;
523 if (s->palettes_count >= PALETTES_MAX)
524 return AVERROR_INVALIDDATA;
525 tmpptr = av_realloc(s->palettes,
526 (s->palettes_count + 1) * AVPALETTE_SIZE);
528 return AVERROR(ENOMEM);
529 s->palettes = tmpptr;
530 tmpptr += s->palettes_count * AVPALETTE_COUNT;
531 for (i = 0; i < PALETTE_COUNT; i++) {
533 int r = gamma_corr(bytestream2_get_byteu(&ctx));
534 int g = gamma_corr(bytestream2_get_byteu(&ctx));
535 int b = gamma_corr(bytestream2_get_byteu(&ctx));
537 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
538 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
539 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
541 *tmpptr++ = (r << 16) | (g << 8) | b;
547 return AVERROR_INVALIDDATA;
548 new_pal = bytestream2_get_le32(&ctx);
549 if (new_pal < s->palettes_count) {
550 s->cur_palette = new_pal;
552 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
557 bytestream2_skip(&ctx, size);
561 buf_size = bytestream2_get_bytes_left(&ctx);
563 if (s->palettes_count <= 0) {
564 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
565 return AVERROR_INVALIDDATA;
568 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF))) {
569 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
574 s->frame_size = frame->linesize[0] * s->avctx->height;
576 memcpy(frame->data[1],
577 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
582 if (xan_wc3_decode_frame(s, frame) < 0)
583 return AVERROR_INVALIDDATA;
585 av_frame_unref(&s->last_frame);
586 if ((ret = av_frame_ref(&s->last_frame, frame)) < 0)
591 /* always report that the buffer was completely consumed */
595 static av_cold int xan_decode_end(AVCodecContext *avctx)
597 XanContext *s = avctx->priv_data;
599 av_frame_unref(&s->last_frame);
601 av_freep(&s->buffer1);
602 av_freep(&s->buffer2);
603 av_freep(&s->palettes);
608 AVCodec ff_xan_wc3_decoder = {
610 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
611 .type = AVMEDIA_TYPE_VIDEO,
612 .id = AV_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,