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 #define BITSTREAM_READER_LE
40 #include "bytestream.h"
44 #define RUNTIME_GAMMA 0
46 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
47 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
48 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
49 #define PALETTE_COUNT 256
50 #define PALETTE_SIZE (PALETTE_COUNT * 3)
51 #define PALETTES_MAX 256
53 typedef struct XanContext {
55 AVCodecContext *avctx;
75 static av_cold int xan_decode_end(AVCodecContext *avctx)
77 XanContext *s = avctx->priv_data;
79 av_frame_free(&s->last_frame);
81 av_freep(&s->buffer1);
82 av_freep(&s->buffer2);
83 av_freep(&s->palettes);
88 static av_cold int xan_decode_init(AVCodecContext *avctx)
90 XanContext *s = avctx->priv_data;
95 avctx->pix_fmt = AV_PIX_FMT_PAL8;
97 s->buffer1_size = avctx->width * avctx->height;
98 s->buffer1 = av_malloc(s->buffer1_size);
100 return AVERROR(ENOMEM);
101 s->buffer2_size = avctx->width * avctx->height;
102 s->buffer2 = av_malloc(s->buffer2_size + 130);
104 av_freep(&s->buffer1);
105 return AVERROR(ENOMEM);
108 s->last_frame = av_frame_alloc();
109 if (!s->last_frame) {
110 xan_decode_end(avctx);
111 return AVERROR(ENOMEM);
117 static int xan_huffman_decode(uint8_t *dest, int dest_len,
118 const uint8_t *src, int src_len)
120 uint8_t byte = *src++;
121 uint8_t ival = byte + 0x16;
122 const uint8_t * ptr = src + byte*2;
123 int ptr_len = src_len - 1 - byte*2;
125 uint8_t *dest_end = dest + dest_len;
126 uint8_t *dest_start = dest;
130 if ((ret = init_get_bits8(&gb, ptr, ptr_len)) < 0)
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(uint8_t *dest, int dest_len,
156 const uint8_t *src, int src_len)
160 uint8_t *dest_org = dest;
161 uint8_t *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 uint8_t *pixel_buffer, int x, int y, int pixel_count)
216 int width = s->avctx->width;
217 uint8_t *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 uint8_t *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;
266 if (prev_palette_plane == palette_plane && FFABS(curframe_index - prevframe_index) < pixel_count) {
267 avpriv_request_sample(s->avctx, "Overlapping copy");
271 while (pixel_count &&
272 curframe_index < s->frame_size &&
273 prevframe_index < s->frame_size) {
274 int count = FFMIN3(pixel_count, width - curframe_x,
275 width - prevframe_x);
277 memcpy(palette_plane + curframe_index,
278 prev_palette_plane + prevframe_index, count);
279 pixel_count -= count;
280 curframe_index += count;
281 prevframe_index += count;
283 prevframe_x += count;
285 if (curframe_x >= width) {
286 curframe_index += line_inc;
290 if (prevframe_x >= width) {
291 prevframe_index += line_inc;
297 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
300 int width = s->avctx->width;
301 int height = s->avctx->height;
302 int total_pixels = width * height;
306 int motion_x, motion_y;
309 uint8_t *opcode_buffer = s->buffer1;
310 uint8_t *opcode_buffer_end = s->buffer1 + s->buffer1_size;
311 int opcode_buffer_size = s->buffer1_size;
312 const uint8_t *imagedata_buffer = s->buffer2;
314 /* pointers to segments inside the compressed chunk */
315 const uint8_t *huffman_segment;
316 GetByteContext size_segment;
317 GetByteContext vector_segment;
318 const uint8_t *imagedata_segment;
319 int huffman_offset, size_offset, vector_offset, imagedata_offset,
323 return AVERROR_INVALIDDATA;
325 huffman_offset = AV_RL16(&s->buf[0]);
326 size_offset = AV_RL16(&s->buf[2]);
327 vector_offset = AV_RL16(&s->buf[4]);
328 imagedata_offset = AV_RL16(&s->buf[6]);
330 if (huffman_offset >= s->size ||
331 size_offset >= s->size ||
332 vector_offset >= s->size ||
333 imagedata_offset >= s->size)
334 return AVERROR_INVALIDDATA;
336 huffman_segment = s->buf + huffman_offset;
337 bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
338 bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
339 imagedata_segment = s->buf + imagedata_offset;
341 if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
342 huffman_segment, s->size - huffman_offset)) < 0)
343 return AVERROR_INVALIDDATA;
344 opcode_buffer_end = opcode_buffer + ret;
346 if (imagedata_segment[0] == 2) {
347 xan_unpack(s->buffer2, s->buffer2_size,
348 &imagedata_segment[1], s->size - imagedata_offset - 1);
349 imagedata_size = s->buffer2_size;
351 imagedata_size = s->size - imagedata_offset - 1;
352 imagedata_buffer = &imagedata_segment[1];
355 /* use the decoded data segments to build the frame */
357 while (total_pixels && opcode_buffer < opcode_buffer_end) {
359 opcode = *opcode_buffer++;
386 size += (opcode - 10);
391 if (bytestream2_get_bytes_left(&size_segment) < 1) {
392 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
393 return AVERROR_INVALIDDATA;
395 size = bytestream2_get_byte(&size_segment);
400 if (bytestream2_get_bytes_left(&size_segment) < 2) {
401 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
402 return AVERROR_INVALIDDATA;
404 size = bytestream2_get_be16(&size_segment);
409 if (bytestream2_get_bytes_left(&size_segment) < 3) {
410 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
411 return AVERROR_INVALIDDATA;
413 size = bytestream2_get_be24(&size_segment);
417 if (size > total_pixels)
423 /* run of (size) pixels is unchanged from last frame */
424 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
426 /* output a run of pixels from imagedata_buffer */
427 if (imagedata_size < size)
429 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
430 imagedata_buffer += size;
431 imagedata_size -= size;
435 if (bytestream2_get_bytes_left(&vector_segment) <= 0) {
436 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
437 return AVERROR_INVALIDDATA;
439 /* run-based motion compensation from last frame */
440 vector = bytestream2_get_byte(&vector_segment);
441 motion_x = sign_extend(vector >> 4, 4);
442 motion_y = sign_extend(vector & 0xF, 4);
444 /* copy a run of pixels from the previous frame */
445 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
450 /* coordinate accounting */
451 total_pixels -= size;
452 y += (x + size) / width;
453 x = (x + size) % width;
459 static inline unsigned mul(unsigned a, unsigned b)
461 return (a * b) >> 16;
464 static inline unsigned pow4(unsigned a)
466 unsigned square = mul(a, a);
467 return mul(square, square);
470 static inline unsigned pow5(unsigned a)
472 return mul(pow4(a), a);
475 static uint8_t gamma_corr(uint8_t in) {
476 unsigned lo, hi = 0xff40, target;
478 in = (in << 2) | (in >> 6);
479 /* equivalent float code:
482 return round(pow(in / 256.0, 0.8) * 256);
484 lo = target = in << 8;
486 unsigned mid = (lo + hi) >> 1;
487 unsigned pow = pow5(mid);
488 if (pow > target) hi = mid;
491 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
495 * This is a gamma correction that xan3 applies to all palette entries.
497 * There is a peculiarity, namely that the values are clamped to 253 -
498 * it seems likely that this table was calculated by a buggy fixed-point
499 * implementation, the one above under RUNTIME_GAMMA behaves like this for
501 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
502 * and thus pow(x, 0.8) is still easy to calculate.
503 * Also, the input values are first rotated to the left by 2.
505 static const uint8_t gamma_lookup[256] = {
506 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
507 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
508 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
509 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
510 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
511 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
512 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
513 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
514 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
515 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
516 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
517 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
518 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
519 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
520 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
521 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
522 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
523 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
524 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
525 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
526 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
527 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
528 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
529 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
530 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
531 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
532 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
533 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
534 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
535 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
536 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
537 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
541 static int xan_decode_frame(AVCodecContext *avctx,
542 void *data, int *got_frame,
545 AVFrame *frame = data;
546 const uint8_t *buf = avpkt->data;
547 int ret, buf_size = avpkt->size;
548 XanContext *s = avctx->priv_data;
552 bytestream2_init(&ctx, buf, buf_size);
553 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
558 tag = bytestream2_get_le32(&ctx);
559 size = bytestream2_get_be32(&ctx);
561 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
562 return AVERROR_INVALIDDATA;
564 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
567 if (size < PALETTE_SIZE)
568 return AVERROR_INVALIDDATA;
569 if (s->palettes_count >= PALETTES_MAX)
570 return AVERROR_INVALIDDATA;
571 tmpptr = av_realloc_array(s->palettes,
572 s->palettes_count + 1, AVPALETTE_SIZE);
574 return AVERROR(ENOMEM);
575 s->palettes = tmpptr;
576 tmpptr += s->palettes_count * AVPALETTE_COUNT;
577 for (i = 0; i < PALETTE_COUNT; i++) {
579 int r = gamma_corr(bytestream2_get_byteu(&ctx));
580 int g = gamma_corr(bytestream2_get_byteu(&ctx));
581 int b = gamma_corr(bytestream2_get_byteu(&ctx));
583 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
584 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
585 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
587 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
593 return AVERROR_INVALIDDATA;
594 new_pal = bytestream2_get_le32(&ctx);
595 if (new_pal < s->palettes_count) {
596 s->cur_palette = new_pal;
598 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
603 bytestream2_skip(&ctx, size);
607 buf_size = bytestream2_get_bytes_left(&ctx);
609 if (s->palettes_count <= 0) {
610 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
611 return AVERROR_INVALIDDATA;
614 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0)
618 s->frame_size = frame->linesize[0] * s->avctx->height;
620 memcpy(frame->data[1],
621 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
626 if (xan_wc3_decode_frame(s, frame) < 0)
627 return AVERROR_INVALIDDATA;
629 av_frame_unref(s->last_frame);
630 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
635 /* always report that the buffer was completely consumed */
639 AVCodec ff_xan_wc3_decoder = {
641 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
642 .type = AVMEDIA_TYPE_VIDEO,
643 .id = AV_CODEC_ID_XAN_WC3,
644 .priv_data_size = sizeof(XanContext),
645 .init = xan_decode_init,
646 .close = xan_decode_end,
647 .decode = xan_decode_frame,
648 .capabilities = AV_CODEC_CAP_DR1,