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;
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);
98 static int xan_huffman_decode(unsigned char *dest, int dest_len,
99 const unsigned char *src, int src_len)
101 unsigned char byte = *src++;
102 unsigned char ival = byte + 0x16;
103 const unsigned char * ptr = src + byte*2;
104 int ptr_len = src_len - 1 - byte*2;
105 unsigned char val = ival;
106 unsigned char *dest_end = dest + dest_len;
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)
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,
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 = s->current_frame.data[0];
201 stride = s->current_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, int x, int y,
221 int pixel_count, int motion_x,
226 int curframe_index, prevframe_index;
227 int curframe_x, prevframe_x;
228 int width = s->avctx->width;
229 unsigned char *palette_plane, *prev_palette_plane;
231 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
232 x + motion_x < 0 || x + motion_x >= s->avctx->width)
235 palette_plane = s->current_frame.data[0];
236 prev_palette_plane = s->last_frame.data[0];
237 if (!prev_palette_plane)
238 prev_palette_plane = palette_plane;
239 stride = s->current_frame.linesize[0];
240 line_inc = stride - width;
241 curframe_index = y * stride + x;
243 prevframe_index = (y + motion_y) * stride + x + motion_x;
244 prevframe_x = x + motion_x;
245 while (pixel_count &&
246 curframe_index < s->frame_size &&
247 prevframe_index < s->frame_size) {
248 int count = FFMIN3(pixel_count, width - curframe_x,
249 width - prevframe_x);
251 memcpy(palette_plane + curframe_index,
252 prev_palette_plane + prevframe_index, count);
253 pixel_count -= count;
254 curframe_index += count;
255 prevframe_index += count;
257 prevframe_x += count;
259 if (curframe_x >= width) {
260 curframe_index += line_inc;
264 if (prevframe_x >= width) {
265 prevframe_index += line_inc;
271 static int xan_wc3_decode_frame(XanContext *s) {
273 int width = s->avctx->width;
274 int height = s->avctx->height;
275 int total_pixels = width * height;
276 unsigned char opcode;
277 unsigned char flag = 0;
279 int motion_x, motion_y;
282 unsigned char *opcode_buffer = s->buffer1;
283 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
284 int opcode_buffer_size = s->buffer1_size;
285 const unsigned char *imagedata_buffer = s->buffer2;
287 /* pointers to segments inside the compressed chunk */
288 const unsigned char *huffman_segment;
289 const unsigned char *size_segment;
290 const unsigned char *vector_segment;
291 const unsigned char *imagedata_segment;
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 size = *size_segment++;
368 size = AV_RB16(&size_segment[0]);
374 size = AV_RB24(size_segment);
379 if (size > total_pixels)
385 /* run of (size) pixels is unchanged from last frame */
386 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
388 /* output a run of pixels from imagedata_buffer */
389 if (imagedata_size < size)
391 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
392 imagedata_buffer += size;
393 imagedata_size -= size;
396 /* run-based motion compensation from last frame */
397 motion_x = sign_extend(*vector_segment >> 4, 4);
398 motion_y = sign_extend(*vector_segment & 0xF, 4);
401 /* copy a run of pixels from the previous frame */
402 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
407 /* coordinate accounting */
408 total_pixels -= size;
409 y += (x + size) / width;
410 x = (x + size) % width;
416 static inline unsigned mul(unsigned a, unsigned b)
418 return (a * b) >> 16;
421 static inline unsigned pow4(unsigned a)
423 unsigned square = mul(a, a);
424 return mul(square, square);
427 static inline unsigned pow5(unsigned a)
429 return mul(pow4(a), a);
432 static uint8_t gamma_corr(uint8_t in) {
433 unsigned lo, hi = 0xff40, target;
435 in = (in << 2) | (in >> 6);
436 /* equivalent float code:
439 return round(pow(in / 256.0, 0.8) * 256);
441 lo = target = in << 8;
443 unsigned mid = (lo + hi) >> 1;
444 unsigned pow = pow5(mid);
445 if (pow > target) hi = mid;
448 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
452 * This is a gamma correction that xan3 applies to all palette entries.
454 * There is a peculiarity, namely that the values are clamped to 253 -
455 * it seems likely that this table was calculated by a buggy fixed-point
456 * implementation, the one above under RUNTIME_GAMMA behaves like this for
458 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
459 * and thus pow(x, 0.8) is still easy to calculate.
460 * Also, the input values are first rotated to the left by 2.
462 static const uint8_t gamma_lookup[256] = {
463 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
464 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
465 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
466 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
467 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
468 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
469 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
470 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
471 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
472 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
473 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
474 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
475 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
476 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
477 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
478 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
479 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
480 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
481 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
482 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
483 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
484 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
485 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
486 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
487 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
488 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
489 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
490 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
491 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
492 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
493 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
494 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
498 static int xan_decode_frame(AVCodecContext *avctx,
499 void *data, int *got_frame,
502 const uint8_t *buf = avpkt->data;
503 int ret, buf_size = avpkt->size;
504 XanContext *s = avctx->priv_data;
508 bytestream2_init(&ctx, buf, buf_size);
509 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
514 tag = bytestream2_get_le32(&ctx);
515 size = bytestream2_get_be32(&ctx);
516 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
519 if (size < PALETTE_SIZE)
520 return AVERROR_INVALIDDATA;
521 if (s->palettes_count >= PALETTES_MAX)
522 return AVERROR_INVALIDDATA;
523 tmpptr = av_realloc(s->palettes,
524 (s->palettes_count + 1) * AVPALETTE_SIZE);
526 return AVERROR(ENOMEM);
527 s->palettes = tmpptr;
528 tmpptr += s->palettes_count * AVPALETTE_COUNT;
529 for (i = 0; i < PALETTE_COUNT; i++) {
531 int r = gamma_corr(bytestream2_get_byteu(&ctx));
532 int g = gamma_corr(bytestream2_get_byteu(&ctx));
533 int b = gamma_corr(bytestream2_get_byteu(&ctx));
535 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
536 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
537 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
539 *tmpptr++ = (r << 16) | (g << 8) | b;
545 return AVERROR_INVALIDDATA;
546 new_pal = bytestream2_get_le32(&ctx);
547 if (new_pal < s->palettes_count) {
548 s->cur_palette = new_pal;
550 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
555 bytestream2_skip(&ctx, size);
559 buf_size = bytestream2_get_bytes_left(&ctx);
561 if (s->palettes_count <= 0) {
562 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
563 return AVERROR_INVALIDDATA;
566 if ((ret = ff_get_buffer(avctx, &s->current_frame))) {
567 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
570 s->current_frame.reference = 3;
573 s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
575 memcpy(s->current_frame.data[1],
576 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
581 if (xan_wc3_decode_frame(s) < 0)
582 return AVERROR_INVALIDDATA;
584 /* release the last frame if it is allocated */
585 if (s->last_frame.data[0])
586 avctx->release_buffer(avctx, &s->last_frame);
589 *(AVFrame*)data = s->current_frame;
592 FFSWAP(AVFrame, s->current_frame, s->last_frame);
594 /* always report that the buffer was completely consumed */
598 static av_cold int xan_decode_end(AVCodecContext *avctx)
600 XanContext *s = avctx->priv_data;
602 /* release the frames */
603 if (s->last_frame.data[0])
604 avctx->release_buffer(avctx, &s->last_frame);
605 if (s->current_frame.data[0])
606 avctx->release_buffer(avctx, &s->current_frame);
608 av_freep(&s->buffer1);
609 av_freep(&s->buffer2);
610 av_freep(&s->palettes);
615 AVCodec ff_xan_wc3_decoder = {
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,
624 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),