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;
109 return AVERROR_INVALIDDATA;
111 init_get_bits(&gb, ptr, ptr_len * 8);
113 while (val != 0x16) {
114 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
116 return AVERROR_INVALIDDATA;
120 if (dest >= dest_end)
131 * unpack simple compression
133 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
135 static void xan_unpack(unsigned char *dest, int dest_len,
136 const unsigned char *src, int src_len)
138 unsigned char opcode;
140 unsigned char *dest_org = dest;
141 unsigned char *dest_end = dest + dest_len;
144 bytestream2_init(&ctx, src, src_len);
145 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
146 opcode = bytestream2_get_byte(&ctx);
150 if ((opcode & 0x80) == 0) {
153 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
154 size2 = ((opcode & 0x1c) >> 2) + 3;
155 } else if ((opcode & 0x40) == 0) {
156 size = bytestream2_peek_byte(&ctx) >> 6;
158 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
159 size2 = (opcode & 0x3f) + 4;
163 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
164 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
167 if (dest_end - dest < size + size2 ||
168 dest + size - dest_org < back ||
169 bytestream2_get_bytes_left(&ctx) < size)
171 bytestream2_get_buffer(&ctx, dest, size);
173 av_memcpy_backptr(dest, back, size2);
176 int finish = opcode >= 0xfc;
177 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
179 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
181 bytestream2_get_buffer(&ctx, dest, size);
189 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
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 = frame->data[0];
200 stride = 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, AVFrame *frame,
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 = 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 = 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, AVFrame *frame)
274 int width = s->avctx->width;
275 int height = s->avctx->height;
276 int total_pixels = width * height;
277 unsigned char opcode;
278 unsigned char flag = 0;
280 int motion_x, motion_y;
283 unsigned char *opcode_buffer = s->buffer1;
284 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
285 int opcode_buffer_size = s->buffer1_size;
286 const unsigned char *imagedata_buffer = s->buffer2;
288 /* pointers to segments inside the compressed chunk */
289 const unsigned char *huffman_segment;
290 const unsigned char *size_segment;
291 const unsigned char *vector_segment;
292 const unsigned char *imagedata_segment;
293 int huffman_offset, size_offset, vector_offset, imagedata_offset,
297 return AVERROR_INVALIDDATA;
299 huffman_offset = AV_RL16(&s->buf[0]);
300 size_offset = AV_RL16(&s->buf[2]);
301 vector_offset = AV_RL16(&s->buf[4]);
302 imagedata_offset = AV_RL16(&s->buf[6]);
304 if (huffman_offset >= s->size ||
305 size_offset >= s->size ||
306 vector_offset >= s->size ||
307 imagedata_offset >= s->size)
308 return AVERROR_INVALIDDATA;
310 huffman_segment = s->buf + huffman_offset;
311 size_segment = s->buf + size_offset;
312 vector_segment = s->buf + vector_offset;
313 imagedata_segment = s->buf + imagedata_offset;
315 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
316 huffman_segment, s->size - huffman_offset) < 0)
317 return AVERROR_INVALIDDATA;
319 if (imagedata_segment[0] == 2) {
320 xan_unpack(s->buffer2, s->buffer2_size,
321 &imagedata_segment[1], s->size - imagedata_offset - 1);
322 imagedata_size = s->buffer2_size;
324 imagedata_size = s->size - imagedata_offset - 1;
325 imagedata_buffer = &imagedata_segment[1];
328 /* use the decoded data segments to build the frame */
330 while (total_pixels && opcode_buffer < opcode_buffer_end) {
332 opcode = *opcode_buffer++;
359 size += (opcode - 10);
364 size = *size_segment++;
369 size = AV_RB16(&size_segment[0]);
375 size = AV_RB24(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 motion_x = sign_extend(*vector_segment >> 4, 4);
399 motion_y = sign_extend(*vector_segment & 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 .type = AVMEDIA_TYPE_VIDEO,
611 .id = AV_CODEC_ID_XAN_WC3,
612 .priv_data_size = sizeof(XanContext),
613 .init = xan_decode_init,
614 .close = xan_decode_end,
615 .decode = xan_decode_frame,
616 .capabilities = CODEC_CAP_DR1,
617 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),