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;
57 const unsigned char *buf;
61 unsigned char *buffer1;
63 unsigned char *buffer2;
74 static av_cold int xan_decode_end(AVCodecContext *avctx);
76 static av_cold int xan_decode_init(AVCodecContext *avctx)
78 XanContext *s = avctx->priv_data;
83 avctx->pix_fmt = AV_PIX_FMT_PAL8;
85 s->buffer1_size = avctx->width * avctx->height;
86 s->buffer1 = av_malloc(s->buffer1_size);
88 return AVERROR(ENOMEM);
89 s->buffer2_size = avctx->width * avctx->height;
90 s->buffer2 = av_malloc(s->buffer2_size + 130);
92 av_freep(&s->buffer1);
93 return AVERROR(ENOMEM);
95 s->last_frame = av_frame_alloc();
97 xan_decode_end(avctx);
98 return AVERROR(ENOMEM);
104 static int xan_huffman_decode(unsigned char *dest, int dest_len,
105 const unsigned char *src, int src_len)
107 unsigned char byte = *src++;
108 unsigned char ival = byte + 0x16;
109 const unsigned char * ptr = src + byte*2;
110 int ptr_len = src_len - 1 - byte*2;
111 unsigned char val = ival;
112 unsigned char *dest_end = dest + dest_len;
116 return AVERROR_INVALIDDATA;
118 init_get_bits(&gb, ptr, ptr_len * 8);
120 while (val != 0x16) {
121 unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
123 return AVERROR_INVALIDDATA;
127 if (dest >= dest_end)
138 * unpack simple compression
140 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
142 static void xan_unpack(unsigned char *dest, int dest_len,
143 const unsigned char *src, int src_len)
145 unsigned char opcode;
147 unsigned char *dest_org = dest;
148 unsigned char *dest_end = dest + dest_len;
151 bytestream2_init(&ctx, src, src_len);
152 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
153 opcode = bytestream2_get_byte(&ctx);
157 if ((opcode & 0x80) == 0) {
160 back = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
161 size2 = ((opcode & 0x1c) >> 2) + 3;
162 } else if ((opcode & 0x40) == 0) {
163 size = bytestream2_peek_byte(&ctx) >> 6;
165 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
166 size2 = (opcode & 0x3f) + 4;
170 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
171 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5;
174 if (dest_end - dest < size + size2 ||
175 dest + size - dest_org < back ||
176 bytestream2_get_bytes_left(&ctx) < size)
178 bytestream2_get_buffer(&ctx, dest, size);
180 av_memcpy_backptr(dest, back, size2);
183 int finish = opcode >= 0xfc;
184 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
186 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
188 bytestream2_get_buffer(&ctx, dest, size);
196 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
197 const unsigned char *pixel_buffer, int x, int y, int pixel_count)
203 int width = s->avctx->width;
204 unsigned char *palette_plane;
206 palette_plane = frame->data[0];
207 stride = frame->linesize[0];
208 line_inc = stride - width;
209 index = y * stride + x;
211 while (pixel_count && index < s->frame_size) {
212 int count = FFMIN(pixel_count, width - current_x);
213 memcpy(palette_plane + index, pixel_buffer, count);
214 pixel_count -= count;
216 pixel_buffer += count;
219 if (current_x >= width) {
226 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
228 int pixel_count, int motion_x,
233 int curframe_index, prevframe_index;
234 int curframe_x, prevframe_x;
235 int width = s->avctx->width;
236 unsigned char *palette_plane, *prev_palette_plane;
238 if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
239 x + motion_x < 0 || x + motion_x >= s->avctx->width)
242 palette_plane = frame->data[0];
243 prev_palette_plane = s->last_frame->data[0];
244 if (!prev_palette_plane)
245 prev_palette_plane = palette_plane;
246 stride = frame->linesize[0];
247 line_inc = stride - width;
248 curframe_index = y * stride + x;
250 prevframe_index = (y + motion_y) * stride + x + motion_x;
251 prevframe_x = x + motion_x;
253 if (prev_palette_plane == palette_plane && FFABS(curframe_index - prevframe_index) < pixel_count) {
254 avpriv_request_sample(s->avctx, "Overlapping copy\n");
258 while (pixel_count &&
259 curframe_index < s->frame_size &&
260 prevframe_index < s->frame_size) {
261 int count = FFMIN3(pixel_count, width - curframe_x,
262 width - prevframe_x);
264 memcpy(palette_plane + curframe_index,
265 prev_palette_plane + prevframe_index, count);
266 pixel_count -= count;
267 curframe_index += count;
268 prevframe_index += count;
270 prevframe_x += count;
272 if (curframe_x >= width) {
273 curframe_index += line_inc;
277 if (prevframe_x >= width) {
278 prevframe_index += line_inc;
284 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
287 int width = s->avctx->width;
288 int height = s->avctx->height;
289 int total_pixels = width * height;
290 unsigned char opcode;
291 unsigned char flag = 0;
293 int motion_x, motion_y;
296 unsigned char *opcode_buffer = s->buffer1;
297 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
298 int opcode_buffer_size = s->buffer1_size;
299 const unsigned char *imagedata_buffer = s->buffer2;
301 /* pointers to segments inside the compressed chunk */
302 const unsigned char *huffman_segment;
303 const unsigned char *size_segment;
304 const unsigned char *vector_segment;
305 const unsigned char *imagedata_segment;
306 const unsigned char *buf_end = s->buf + s->size;
307 int huffman_offset, size_offset, vector_offset, imagedata_offset,
311 return AVERROR_INVALIDDATA;
313 huffman_offset = AV_RL16(&s->buf[0]);
314 size_offset = AV_RL16(&s->buf[2]);
315 vector_offset = AV_RL16(&s->buf[4]);
316 imagedata_offset = AV_RL16(&s->buf[6]);
318 if (huffman_offset >= s->size ||
319 size_offset >= s->size ||
320 vector_offset >= s->size ||
321 imagedata_offset >= s->size)
322 return AVERROR_INVALIDDATA;
324 huffman_segment = s->buf + huffman_offset;
325 size_segment = s->buf + size_offset;
326 vector_segment = s->buf + vector_offset;
327 imagedata_segment = s->buf + imagedata_offset;
329 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
330 huffman_segment, s->size - huffman_offset) < 0)
331 return AVERROR_INVALIDDATA;
333 if (imagedata_segment[0] == 2) {
334 xan_unpack(s->buffer2, s->buffer2_size,
335 &imagedata_segment[1], s->size - imagedata_offset - 1);
336 imagedata_size = s->buffer2_size;
338 imagedata_size = s->size - imagedata_offset - 1;
339 imagedata_buffer = &imagedata_segment[1];
342 /* use the decoded data segments to build the frame */
344 while (total_pixels && opcode_buffer < opcode_buffer_end) {
346 opcode = *opcode_buffer++;
373 size += (opcode - 10);
378 if (buf_end - size_segment < 1) {
379 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
380 return AVERROR_INVALIDDATA;
382 size = *size_segment++;
387 if (buf_end - size_segment < 2) {
388 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
389 return AVERROR_INVALIDDATA;
391 size = AV_RB16(&size_segment[0]);
397 if (buf_end - size_segment < 3) {
398 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
399 return AVERROR_INVALIDDATA;
401 size = AV_RB24(size_segment);
406 if (size > total_pixels)
412 /* run of (size) pixels is unchanged from last frame */
413 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0);
415 /* output a run of pixels from imagedata_buffer */
416 if (imagedata_size < size)
418 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size);
419 imagedata_buffer += size;
420 imagedata_size -= size;
423 if (vector_segment >= buf_end) {
424 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
425 return AVERROR_INVALIDDATA;
427 /* run-based motion compensation from last frame */
428 motion_x = sign_extend(*vector_segment >> 4, 4);
429 motion_y = sign_extend(*vector_segment & 0xF, 4);
432 /* copy a run of pixels from the previous frame */
433 xan_wc3_copy_pixel_run(s, frame, x, y, size, motion_x, motion_y);
438 /* coordinate accounting */
439 total_pixels -= size;
440 y += (x + size) / width;
441 x = (x + size) % width;
447 static inline unsigned mul(unsigned a, unsigned b)
449 return (a * b) >> 16;
452 static inline unsigned pow4(unsigned a)
454 unsigned square = mul(a, a);
455 return mul(square, square);
458 static inline unsigned pow5(unsigned a)
460 return mul(pow4(a), a);
463 static uint8_t gamma_corr(uint8_t in) {
464 unsigned lo, hi = 0xff40, target;
466 in = (in << 2) | (in >> 6);
467 /* equivalent float code:
470 return round(pow(in / 256.0, 0.8) * 256);
472 lo = target = in << 8;
474 unsigned mid = (lo + hi) >> 1;
475 unsigned pow = pow5(mid);
476 if (pow > target) hi = mid;
479 return (pow4((lo + hi) >> 1) + 0x80) >> 8;
483 * This is a gamma correction that xan3 applies to all palette entries.
485 * There is a peculiarity, namely that the values are clamped to 253 -
486 * it seems likely that this table was calculated by a buggy fixed-point
487 * implementation, the one above under RUNTIME_GAMMA behaves like this for
489 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
490 * and thus pow(x, 0.8) is still easy to calculate.
491 * Also, the input values are first rotated to the left by 2.
493 static const uint8_t gamma_lookup[256] = {
494 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
495 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
496 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
497 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
498 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
499 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
500 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
501 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
502 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
503 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
504 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
505 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
506 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
507 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
508 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
509 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
510 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
511 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
512 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
513 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
514 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
515 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
516 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
517 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
518 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
519 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
520 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
521 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
522 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
523 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
524 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
525 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
529 static int xan_decode_frame(AVCodecContext *avctx,
530 void *data, int *got_frame,
533 AVFrame *frame = data;
534 const uint8_t *buf = avpkt->data;
535 int ret, buf_size = avpkt->size;
536 XanContext *s = avctx->priv_data;
540 bytestream2_init(&ctx, buf, buf_size);
541 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
546 tag = bytestream2_get_le32(&ctx);
547 size = bytestream2_get_be32(&ctx);
549 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
550 return AVERROR_INVALIDDATA;
552 size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
555 if (size < PALETTE_SIZE)
556 return AVERROR_INVALIDDATA;
557 if (s->palettes_count >= PALETTES_MAX)
558 return AVERROR_INVALIDDATA;
559 tmpptr = av_realloc(s->palettes,
560 (s->palettes_count + 1) * AVPALETTE_SIZE);
562 return AVERROR(ENOMEM);
563 s->palettes = tmpptr;
564 tmpptr += s->palettes_count * AVPALETTE_COUNT;
565 for (i = 0; i < PALETTE_COUNT; i++) {
567 int r = gamma_corr(bytestream2_get_byteu(&ctx));
568 int g = gamma_corr(bytestream2_get_byteu(&ctx));
569 int b = gamma_corr(bytestream2_get_byteu(&ctx));
571 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
572 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
573 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
575 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
581 return AVERROR_INVALIDDATA;
582 new_pal = bytestream2_get_le32(&ctx);
583 if (new_pal < s->palettes_count) {
584 s->cur_palette = new_pal;
586 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
591 bytestream2_skip(&ctx, size);
595 buf_size = bytestream2_get_bytes_left(&ctx);
597 if (s->palettes_count <= 0) {
598 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
599 return AVERROR_INVALIDDATA;
602 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0)
606 s->frame_size = frame->linesize[0] * s->avctx->height;
608 memcpy(frame->data[1],
609 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
614 if (xan_wc3_decode_frame(s, frame) < 0)
615 return AVERROR_INVALIDDATA;
617 av_frame_unref(s->last_frame);
618 if ((ret = av_frame_ref(s->last_frame, frame)) < 0)
623 /* always report that the buffer was completely consumed */
627 static av_cold int xan_decode_end(AVCodecContext *avctx)
629 XanContext *s = avctx->priv_data;
631 av_frame_free(&s->last_frame);
633 av_freep(&s->buffer1);
634 av_freep(&s->buffer2);
635 av_freep(&s->palettes);
640 AVCodec ff_xan_wc3_decoder = {
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 = CODEC_CAP_DR1,
649 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),