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;
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(uint8_t *dest, int dest_len,
117 const uint8_t *src, int src_len)
119 uint8_t byte = *src++;
120 uint8_t ival = byte + 0x16;
121 const uint8_t * ptr = src + byte*2;
122 int ptr_len = src_len - 1 - byte*2;
124 uint8_t *dest_end = dest + dest_len;
125 uint8_t *dest_start = dest;
129 if ((ret = init_get_bits8(&gb, ptr, ptr_len)) < 0)
132 while (val != 0x16) {
133 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
135 return AVERROR_INVALIDDATA;
139 if (dest >= dest_end)
146 return dest - dest_start;
150 * unpack simple compression
152 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
154 static void xan_unpack(uint8_t *dest, int dest_len,
155 const uint8_t *src, int src_len)
159 uint8_t *dest_org = dest;
160 uint8_t *dest_end = dest + dest_len;
163 bytestream2_init(&ctx, src, src_len);
164 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
165 opcode = bytestream2_get_byte(&ctx);
169 if ((opcode & 0x80) == 0) {
172 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
173 size2 = ((opcode & 0x1c) >> 2) + 3;
174 } else if ((opcode & 0x40) == 0) {
175 size = bytestream2_peek_byte(&ctx) >> 6;
177 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
178 size2 = (opcode & 0x3f) + 4;
182 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
183 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
186 if (dest_end - dest < size + size2 ||
187 dest + size - dest_org < back ||
188 bytestream2_get_bytes_left(&ctx) < size)
190 bytestream2_get_buffer(&ctx, dest, size);
192 av_memcpy_backptr(dest, back, size2);
195 int finish = opcode >= 0xfc;
196 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
198 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
200 bytestream2_get_buffer(&ctx, dest, size);
208 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
209 const uint8_t *pixel_buffer, int x, int y, int pixel_count)
215 int width = s->avctx->width;
216 uint8_t *palette_plane;
218 palette_plane = frame->data[0];
219 stride = frame->linesize[0];
220 line_inc = stride - width;
221 index = y * stride + x;
223 while (pixel_count && index < s->frame_size) {
224 int count = FFMIN(pixel_count, width - current_x);
225 memcpy(palette_plane + index, pixel_buffer, count);
226 pixel_count -= count;
228 pixel_buffer += count;
231 if (current_x >= width) {
238 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
240 int pixel_count, int motion_x,
245 int curframe_index, prevframe_index;
246 int curframe_x, prevframe_x;
247 int width = s->avctx->width;
248 uint8_t *palette_plane, *prev_palette_plane;
250 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
251 x + motion_x < 0 || x + motion_x >= s->avctx->width)
254 palette_plane = frame->data[0];
255 prev_palette_plane = s->last_frame->data[0];
256 if (!prev_palette_plane)
257 prev_palette_plane = palette_plane;
258 stride = frame->linesize[0];
259 line_inc = stride - width;
260 curframe_index = y * stride + x;
262 prevframe_index = (y + motion_y) * stride + x + motion_x;
263 prevframe_x = x + motion_x;
265 if (prev_palette_plane == palette_plane && FFABS(curframe_index - prevframe_index) < pixel_count) {
266 avpriv_request_sample(s->avctx, "Overlapping copy\n");
270 while (pixel_count &&
271 curframe_index < s->frame_size &&
272 prevframe_index < s->frame_size) {
273 int count = FFMIN3(pixel_count, width - curframe_x,
274 width - prevframe_x);
276 memcpy(palette_plane + curframe_index,
277 prev_palette_plane + prevframe_index, count);
278 pixel_count -= count;
279 curframe_index += count;
280 prevframe_index += count;
282 prevframe_x += count;
284 if (curframe_x >= width) {
285 curframe_index += line_inc;
289 if (prevframe_x >= width) {
290 prevframe_index += line_inc;
296 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
299 int width = s->avctx->width;
300 int height = s->avctx->height;
301 int total_pixels = width * height;
305 int motion_x, motion_y;
308 uint8_t *opcode_buffer = s->buffer1;
309 uint8_t *opcode_buffer_end = s->buffer1 + s->buffer1_size;
310 int opcode_buffer_size = s->buffer1_size;
311 const uint8_t *imagedata_buffer = s->buffer2;
313 /* pointers to segments inside the compressed chunk */
314 const uint8_t *huffman_segment;
315 GetByteContext size_segment;
316 GetByteContext vector_segment;
317 const uint8_t *imagedata_segment;
318 int huffman_offset, size_offset, vector_offset, imagedata_offset,
322 return AVERROR_INVALIDDATA;
324 huffman_offset = AV_RL16(&s->buf[0]);
325 size_offset = AV_RL16(&s->buf[2]);
326 vector_offset = AV_RL16(&s->buf[4]);
327 imagedata_offset = AV_RL16(&s->buf[6]);
329 if (huffman_offset >= s->size ||
330 size_offset >= s->size ||
331 vector_offset >= s->size ||
332 imagedata_offset >= s->size)
333 return AVERROR_INVALIDDATA;
335 huffman_segment = s->buf + huffman_offset;
336 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
337 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
338 imagedata_segment = s->buf + imagedata_offset;
340 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
341 huffman_segment, s->size - huffman_offset)) < 0)
342 return AVERROR_INVALIDDATA;
343 opcode_buffer_end = opcode_buffer + ret;
345 if (imagedata_segment[0] == 2) {
346 xan_unpack(s->buffer2, s->buffer2_size,
347 &imagedata_segment[1], s->size - imagedata_offset - 1);
348 imagedata_size = s->buffer2_size;
350 imagedata_size = s->size - imagedata_offset - 1;
351 imagedata_buffer = &imagedata_segment[1];
354 /* use the decoded data segments to build the frame */
356 while (total_pixels && opcode_buffer < opcode_buffer_end) {
358 opcode = *opcode_buffer++;
385 size += (opcode - 10);
390 if (bytestream2_get_bytes_left(&size_segment) < 1) {
391 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
392 return AVERROR_INVALIDDATA;
394 size = bytestream2_get_byte(&size_segment);
399 if (bytestream2_get_bytes_left(&size_segment) < 2) {
400 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
401 return AVERROR_INVALIDDATA;
403 size = bytestream2_get_be16(&size_segment);
408 if (bytestream2_get_bytes_left(&size_segment) < 3) {
409 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
410 return AVERROR_INVALIDDATA;
412 size = bytestream2_get_be24(&size_segment);
416 if (size > total_pixels)
422 /* run of (size) pixels is unchanged from last frame */
423 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
425 /* output a run of pixels from imagedata_buffer */
426 if (imagedata_size < size)
428 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
429 imagedata_buffer += size;
430 imagedata_size -= size;
434 if (bytestream2_get_bytes_left(&vector_segment) <= 0) {
435 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
436 return AVERROR_INVALIDDATA;
438 /* run-based motion compensation from last frame */
439 vector = bytestream2_get_byte(&vector_segment);
440 motion_x = sign_extend(vector >> 4, 4);
441 motion_y = sign_extend(vector & 0xF, 4);
443 /* copy a run of pixels from the previous frame */
444 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
449 /* coordinate accounting */
450 total_pixels -= size;
451 y += (x + size) / width;
452 x = (x + size) % width;
458 static inline unsigned mul(unsigned a, unsigned b)
460 return (a * b) >> 16;
463 static inline unsigned pow4(unsigned a)
465 unsigned square = mul(a, a);
466 return mul(square, square);
469 static inline unsigned pow5(unsigned a)
471 return mul(pow4(a), a);
474 static uint8_t gamma_corr(uint8_t in) {
475 unsigned lo, hi = 0xff40, target;
477 in = (in << 2) | (in >> 6);
478 /* equivalent float code:
481 return round(pow(in / 256.0, 0.8) * 256);
483 lo = target = in << 8;
485 unsigned mid = (lo + hi) >> 1;
486 unsigned pow = pow5(mid);
487 if (pow > target) hi = mid;
490 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
494 * This is a gamma correction that xan3 applies to all palette entries.
496 * There is a peculiarity, namely that the values are clamped to 253 -
497 * it seems likely that this table was calculated by a buggy fixed-point
498 * implementation, the one above under RUNTIME_GAMMA behaves like this for
500 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
501 * and thus pow(x, 0.8) is still easy to calculate.
502 * Also, the input values are first rotated to the left by 2.
504 static const uint8_t gamma_lookup[256] = {
505 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
506 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
507 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
508 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
509 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
510 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
511 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
512 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
513 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
514 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
515 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
516 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
517 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
518 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
519 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
520 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
521 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
522 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
523 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
524 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
525 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
526 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
527 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
528 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
529 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
530 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
531 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
532 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
533 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
534 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
535 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
536 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
540 static int xan_decode_frame(AVCodecContext *avctx,
541 void *data, int *got_frame,
544 AVFrame *frame = data;
545 const uint8_t *buf = avpkt->data;
546 int ret, buf_size = avpkt->size;
547 XanContext *s = avctx->priv_data;
551 bytestream2_init(&ctx, buf, buf_size);
552 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
557 tag = bytestream2_get_le32(&ctx);
558 size = bytestream2_get_be32(&ctx);
560 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
561 return AVERROR_INVALIDDATA;
563 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
566 if (size < PALETTE_SIZE)
567 return AVERROR_INVALIDDATA;
568 if (s->palettes_count >= PALETTES_MAX)
569 return AVERROR_INVALIDDATA;
570 tmpptr = av_realloc_array(s->palettes,
571 s->palettes_count + 1, AVPALETTE_SIZE);
573 return AVERROR(ENOMEM);
574 s->palettes = tmpptr;
575 tmpptr += s->palettes_count * AVPALETTE_COUNT;
576 for (i = 0; i < PALETTE_COUNT; i++) {
578 int r = gamma_corr(bytestream2_get_byteu(&ctx));
579 int g = gamma_corr(bytestream2_get_byteu(&ctx));
580 int b = gamma_corr(bytestream2_get_byteu(&ctx));
582 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
583 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
584 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
586 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
592 return AVERROR_INVALIDDATA;
593 new_pal = bytestream2_get_le32(&ctx);
594 if (new_pal < s->palettes_count) {
595 s->cur_palette = new_pal;
597 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
602 bytestream2_skip(&ctx, size);
606 buf_size = bytestream2_get_bytes_left(&ctx);
608 if (s->palettes_count <= 0) {
609 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
610 return AVERROR_INVALIDDATA;
613 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0)
617 s->frame_size = frame->linesize[0] * s->avctx->height;
619 memcpy(frame->data[1],
620 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
625 if (xan_wc3_decode_frame(s, frame) < 0)
626 return AVERROR_INVALIDDATA;
628 av_frame_unref(s->last_frame);
629 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
634 /* always report that the buffer was completely consumed */
638 AVCodec ff_xan_wc3_decoder = {
640 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
641 .type = AVMEDIA_TYPE_VIDEO,
642 .id = AV_CODEC_ID_XAN_WC3,
643 .priv_data_size = sizeof(XanContext),
644 .init = xan_decode_init,
645 .close = xan_decode_end,
646 .decode = xan_decode_frame,
647 .capabilities = CODEC_CAP_DR1,