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_end(AVCodecContext *avctx)
76 XanContext *s = avctx->priv_data;
78 av_frame_free(&s->last_frame);
80 av_freep(&s->buffer1);
81 av_freep(&s->buffer2);
82 av_freep(&s->palettes);
87 static av_cold int xan_decode_init(AVCodecContext *avctx)
89 XanContext *s = avctx->priv_data;
94 avctx->pix_fmt = AV_PIX_FMT_PAL8;
96 s->buffer1_size = avctx->width * avctx->height;
97 s->buffer1 = av_malloc(s->buffer1_size);
99 return AVERROR(ENOMEM);
100 s->buffer2_size = avctx->width * avctx->height;
101 s->buffer2 = av_malloc(s->buffer2_size + 130);
103 av_freep(&s->buffer1);
104 return AVERROR(ENOMEM);
107 s->last_frame = av_frame_alloc();
108 if (!s->last_frame) {
109 xan_decode_end(avctx);
110 return AVERROR(ENOMEM);
116 static int xan_huffman_decode(unsigned char *dest, int dest_len,
117 const unsigned char *src, int src_len)
119 unsigned char byte = *src++;
120 unsigned char ival = byte + 0x16;
121 const unsigned char * ptr = src + byte*2;
122 int ptr_len = src_len - 1 - byte*2;
123 unsigned char val = ival;
124 unsigned char *dest_end = dest + dest_len;
125 unsigned char *dest_start = dest;
129 return AVERROR_INVALIDDATA;
131 init_get_bits(&gb, ptr, ptr_len * 8);
133 while (val != 0x16) {
134 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
136 return AVERROR_INVALIDDATA;
140 if (dest >= dest_end)
147 return dest - dest_start;
151 * unpack simple compression
153 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
155 static void xan_unpack(unsigned char *dest, int dest_len,
156 const unsigned char *src, int src_len)
158 unsigned char opcode;
160 unsigned char *dest_org = dest;
161 unsigned char *dest_end = dest + dest_len;
164 bytestream2_init(&ctx, src, src_len);
165 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
166 opcode = bytestream2_get_byte(&ctx);
170 if ((opcode & 0x80) == 0) {
173 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
174 size2 = ((opcode & 0x1c) >> 2) + 3;
175 } else if ((opcode & 0x40) == 0) {
176 size = bytestream2_peek_byte(&ctx) >> 6;
178 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
179 size2 = (opcode & 0x3f) + 4;
183 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
184 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
187 if (dest_end - dest < size + size2 ||
188 dest + size - dest_org < back ||
189 bytestream2_get_bytes_left(&ctx) < size)
191 bytestream2_get_buffer(&ctx, dest, size);
193 av_memcpy_backptr(dest, back, size2);
196 int finish = opcode >= 0xfc;
197 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
199 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
201 bytestream2_get_buffer(&ctx, dest, size);
209 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
210 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
216 int width = s->avctx->width;
217 unsigned char *palette_plane;
219 palette_plane = frame->data[0];
220 stride = frame->linesize[0];
221 line_inc = stride - width;
222 index = y * stride + x;
224 while (pixel_count && index < s->frame_size) {
225 int count = FFMIN(pixel_count, width - current_x);
226 memcpy(palette_plane + index, pixel_buffer, count);
227 pixel_count -= count;
229 pixel_buffer += count;
232 if (current_x >= width) {
239 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
241 int pixel_count, int motion_x,
246 int curframe_index, prevframe_index;
247 int curframe_x, prevframe_x;
248 int width = s->avctx->width;
249 unsigned char *palette_plane, *prev_palette_plane;
251 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
252 x + motion_x < 0 || x + motion_x >= s->avctx->width)
255 palette_plane = frame->data[0];
256 prev_palette_plane = s->last_frame->data[0];
257 if (!prev_palette_plane)
258 prev_palette_plane = palette_plane;
259 stride = frame->linesize[0];
260 line_inc = stride - width;
261 curframe_index = y * stride + x;
263 prevframe_index = (y + motion_y) * stride + x + motion_x;
264 prevframe_x = x + motion_x;
265 while (pixel_count &&
266 curframe_index < s->frame_size &&
267 prevframe_index < s->frame_size) {
268 int count = FFMIN3(pixel_count, width - curframe_x,
269 width - prevframe_x);
271 memcpy(palette_plane + curframe_index,
272 prev_palette_plane + prevframe_index, count);
273 pixel_count -= count;
274 curframe_index += count;
275 prevframe_index += count;
277 prevframe_x += count;
279 if (curframe_x >= width) {
280 curframe_index += line_inc;
284 if (prevframe_x >= width) {
285 prevframe_index += line_inc;
291 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
294 int width = s->avctx->width;
295 int height = s->avctx->height;
296 int total_pixels = width * height;
297 unsigned char opcode;
298 unsigned char flag = 0;
300 int motion_x, motion_y;
303 unsigned char *opcode_buffer = s->buffer1;
304 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
305 int opcode_buffer_size = s->buffer1_size;
306 const unsigned char *imagedata_buffer = s->buffer2;
308 /* pointers to segments inside the compressed chunk */
309 const unsigned char *huffman_segment;
310 GetByteContext size_segment;
311 GetByteContext vector_segment;
312 const unsigned char *imagedata_segment;
313 int huffman_offset, size_offset, vector_offset, imagedata_offset,
317 return AVERROR_INVALIDDATA;
319 huffman_offset = AV_RL16(&s->buf[0]);
320 size_offset = AV_RL16(&s->buf[2]);
321 vector_offset = AV_RL16(&s->buf[4]);
322 imagedata_offset = AV_RL16(&s->buf[6]);
324 if (huffman_offset >= s->size ||
325 size_offset >= s->size ||
326 vector_offset >= s->size ||
327 imagedata_offset >= s->size)
328 return AVERROR_INVALIDDATA;
330 huffman_segment = s->buf + huffman_offset;
331 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
332 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
333 imagedata_segment = s->buf + imagedata_offset;
335 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
336 huffman_segment, s->size - huffman_offset)) < 0)
337 return AVERROR_INVALIDDATA;
338 opcode_buffer_end = opcode_buffer + ret;
340 if (imagedata_segment[0] == 2) {
341 xan_unpack(s->buffer2, s->buffer2_size,
342 &imagedata_segment[1], s->size - imagedata_offset - 1);
343 imagedata_size = s->buffer2_size;
345 imagedata_size = s->size - imagedata_offset - 1;
346 imagedata_buffer = &imagedata_segment[1];
349 /* use the decoded data segments to build the frame */
351 while (total_pixels && opcode_buffer < opcode_buffer_end) {
353 opcode = *opcode_buffer++;
380 size += (opcode - 10);
385 size = bytestream2_get_byte(&size_segment);
390 size = bytestream2_get_be16(&size_segment);
395 size = bytestream2_get_be24(&size_segment);
399 if (size > total_pixels)
405 /* run of (size) pixels is unchanged from last frame */
406 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
408 /* output a run of pixels from imagedata_buffer */
409 if (imagedata_size < size)
411 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
412 imagedata_buffer += size;
413 imagedata_size -= size;
416 /* run-based motion compensation from last frame */
417 uint8_t vector = bytestream2_get_byte(&vector_segment);
418 motion_x = sign_extend(vector >> 4, 4);
419 motion_y = sign_extend(vector & 0xF, 4);
421 /* copy a run of pixels from the previous frame */
422 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
427 /* coordinate accounting */
428 total_pixels -= size;
429 y += (x + size) / width;
430 x = (x + size) % width;
436 static inline unsigned mul(unsigned a, unsigned b)
438 return (a * b) >> 16;
441 static inline unsigned pow4(unsigned a)
443 unsigned square = mul(a, a);
444 return mul(square, square);
447 static inline unsigned pow5(unsigned a)
449 return mul(pow4(a), a);
452 static uint8_t gamma_corr(uint8_t in) {
453 unsigned lo, hi = 0xff40, target;
455 in = (in << 2) | (in >> 6);
456 /* equivalent float code:
459 return round(pow(in / 256.0, 0.8) * 256);
461 lo = target = in << 8;
463 unsigned mid = (lo + hi) >> 1;
464 unsigned pow = pow5(mid);
465 if (pow > target) hi = mid;
468 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
472 * This is a gamma correction that xan3 applies to all palette entries.
474 * There is a peculiarity, namely that the values are clamped to 253 -
475 * it seems likely that this table was calculated by a buggy fixed-point
476 * implementation, the one above under RUNTIME_GAMMA behaves like this for
478 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
479 * and thus pow(x, 0.8) is still easy to calculate.
480 * Also, the input values are first rotated to the left by 2.
482 static const uint8_t gamma_lookup[256] = {
483 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
484 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
485 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
486 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
487 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
488 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
489 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
490 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
491 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
492 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
493 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
494 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
495 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
496 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
497 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
498 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
499 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
500 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
501 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
502 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
503 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
504 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
505 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
506 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
507 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
508 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
509 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
510 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
511 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
512 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
513 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
514 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
518 static int xan_decode_frame(AVCodecContext *avctx,
519 void *data, int *got_frame,
522 AVFrame *frame = data;
523 const uint8_t *buf = avpkt->data;
524 int ret, buf_size = avpkt->size;
525 XanContext *s = avctx->priv_data;
529 bytestream2_init(&ctx, buf, buf_size);
530 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
535 tag = bytestream2_get_le32(&ctx);
536 size = bytestream2_get_be32(&ctx);
537 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
540 if (size < PALETTE_SIZE)
541 return AVERROR_INVALIDDATA;
542 if (s->palettes_count >= PALETTES_MAX)
543 return AVERROR_INVALIDDATA;
544 tmpptr = av_realloc(s->palettes,
545 (s->palettes_count + 1) * AVPALETTE_SIZE);
547 return AVERROR(ENOMEM);
548 s->palettes = tmpptr;
549 tmpptr += s->palettes_count * AVPALETTE_COUNT;
550 for (i = 0; i < PALETTE_COUNT; i++) {
552 int r = gamma_corr(bytestream2_get_byteu(&ctx));
553 int g = gamma_corr(bytestream2_get_byteu(&ctx));
554 int b = gamma_corr(bytestream2_get_byteu(&ctx));
556 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
557 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
558 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
560 *tmpptr++ = (r << 16) | (g << 8) | b;
566 return AVERROR_INVALIDDATA;
567 new_pal = bytestream2_get_le32(&ctx);
568 if (new_pal < s->palettes_count) {
569 s->cur_palette = new_pal;
571 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
576 bytestream2_skip(&ctx, size);
580 buf_size = bytestream2_get_bytes_left(&ctx);
582 if (s->palettes_count <= 0) {
583 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
584 return AVERROR_INVALIDDATA;
587 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF))) {
588 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
593 s->frame_size = frame->linesize[0] * s->avctx->height;
595 memcpy(frame->data[1],
596 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
601 if (xan_wc3_decode_frame(s, frame) < 0)
602 return AVERROR_INVALIDDATA;
604 av_frame_unref(s->last_frame);
605 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
610 /* always report that the buffer was completely consumed */
614 AVCodec ff_xan_wc3_decoder = {
616 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
617 .type = AVMEDIA_TYPE_VIDEO,
618 .id = AV_CODEC_ID_XAN_WC3,
619 .priv_data_size = sizeof(XanContext),
620 .init = xan_decode_init,
621 .close = xan_decode_end,
622 .decode = xan_decode_frame,
623 .capabilities = CODEC_CAP_DR1,