1/* 2 * Wing Commander/Xan Video Decoder 3 * Copyright (C) 2003 the ffmpeg project 4 * 5 * This file is part of Libav. 6 * 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. 11 * 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. 16 * 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 20 */ 21 22/** 23 * @file 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) 27 * 28 * The xan_wc3 decoder outputs PAL8 data. 29 */ 30 31#include <stdio.h> 32#include <stdlib.h> 33#include <string.h> 34 35#include "libavutil/intreadwrite.h" 36#include "avcodec.h" 37#include "bytestream.h" 38#define BITSTREAM_READER_LE 39#include "get_bits.h" 40// for av_memcpy_backptr 41#include "libavutil/lzo.h" 42 43#define RUNTIME_GAMMA 0 44 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 51 52typedef struct XanContext { 53 54 AVCodecContext *avctx; 55 AVFrame last_frame; 56 AVFrame current_frame; 57 58 const unsigned char *buf; 59 int size; 60 61 /* scratch space */ 62 unsigned char *buffer1; 63 int buffer1_size; 64 unsigned char *buffer2; 65 int buffer2_size; 66 67 unsigned *palettes; 68 int palettes_count; 69 int cur_palette; 70 71 int frame_size; 72 73} XanContext; 74 75static av_cold int xan_decode_init(AVCodecContext *avctx) 76{ 77 XanContext *s = avctx->priv_data; 78 79 s->avctx = avctx; 80 s->frame_size = 0; 81 82 avctx->pix_fmt = PIX_FMT_PAL8; 83 84 s->buffer1_size = avctx->width * avctx->height; 85 s->buffer1 = av_malloc(s->buffer1_size); 86 if (!s->buffer1) 87 return AVERROR(ENOMEM); 88 s->buffer2_size = avctx->width * avctx->height; 89 s->buffer2 = av_malloc(s->buffer2_size + 130); 90 if (!s->buffer2) { 91 av_freep(&s->buffer1); 92 return AVERROR(ENOMEM); 93 } 94 95 return 0; 96} 97 98static int xan_huffman_decode(unsigned char *dest, int dest_len, 99 const unsigned char *src, int src_len) 100{ 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; 107 GetBitContext gb; 108 109 if (ptr_len < 0) 110 return AVERROR_INVALIDDATA; 111 112 init_get_bits(&gb, ptr, ptr_len * 8); 113 114 while (val != 0x16) { 115 unsigned idx = val - 0x17 + get_bits1(&gb) * byte; 116 if (idx >= 2 * byte) 117 return -1; 118 val = src[idx]; 119 120 if (val < 0x16) { 121 if (dest >= dest_end) 122 return 0; 123 *dest++ = val; 124 val = ival; 125 } 126 } 127 128 return 0; 129} 130 131/** 132 * unpack simple compression 133 * 134 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes 135 */ 136static void xan_unpack(unsigned char *dest, int dest_len, 137 const unsigned char *src, int src_len) 138{ 139 unsigned char opcode; 140 int size; 141 unsigned char *dest_org = dest; 142 unsigned char *dest_end = dest + dest_len; 143 const unsigned char *src_end = src + src_len; 144 145 while (dest < dest_end && src < src_end) { 146 opcode = *src++; 147 148 if (opcode < 0xe0) { 149 int size2, back; 150 if ((opcode & 0x80) == 0) { 151 size = opcode & 3; 152 153 back = ((opcode & 0x60) << 3) + *src++ + 1; 154 size2 = ((opcode & 0x1c) >> 2) + 3; 155 } else if ((opcode & 0x40) == 0) { 156 size = *src >> 6; 157 158 back = (bytestream_get_be16(&src) & 0x3fff) + 1; 159 size2 = (opcode & 0x3f) + 4; 160 } else { 161 size = opcode & 3; 162 163 back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1; 164 size2 = ((opcode & 0x0c) << 6) + *src++ + 5; 165 } 166 167 if (dest_end - dest < size + size2 || 168 dest + size - dest_org < back || 169 src_end - src < size) 170 return; 171 memcpy(dest, src, size); dest += size; src += size; 172 av_memcpy_backptr(dest, back, size2); 173 dest += size2; 174 } else { 175 int finish = opcode >= 0xfc; 176 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4; 177 178 if (dest_end - dest < size || src_end - src < size) 179 return; 180 memcpy(dest, src, size); dest += size; src += size; 181 if (finish) 182 return; 183 } 184 } 185} 186 187static inline void xan_wc3_output_pixel_run(XanContext *s, 188 const unsigned char *pixel_buffer, int x, int y, int pixel_count) 189{ 190 int stride; 191 int line_inc; 192 int index; 193 int current_x; 194 int width = s->avctx->width; 195 unsigned char *palette_plane; 196 197 palette_plane = s->current_frame.data[0]; 198 stride = s->current_frame.linesize[0]; 199 line_inc = stride - width; 200 index = y * stride + x; 201 current_x = x; 202 while (pixel_count && index < s->frame_size) { 203 int count = FFMIN(pixel_count, width - current_x); 204 memcpy(palette_plane + index, pixel_buffer, count); 205 pixel_count -= count; 206 index += count; 207 pixel_buffer += count; 208 current_x += count; 209 210 if (current_x >= width) { 211 index += line_inc; 212 current_x = 0; 213 } 214 } 215} 216 217static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y, 218 int pixel_count, int motion_x, 219 int motion_y) 220{ 221 int stride; 222 int line_inc; 223 int curframe_index, prevframe_index; 224 int curframe_x, prevframe_x; 225 int width = s->avctx->width; 226 unsigned char *palette_plane, *prev_palette_plane; 227 228 if (y + motion_y < 0 || y + motion_y >= s->avctx->height || 229 x + motion_x < 0 || x + motion_x >= s->avctx->width) 230 return; 231 232 palette_plane = s->current_frame.data[0]; 233 prev_palette_plane = s->last_frame.data[0]; 234 if (!prev_palette_plane) 235 prev_palette_plane = palette_plane; 236 stride = s->current_frame.linesize[0]; 237 line_inc = stride - width; 238 curframe_index = y * stride + x; 239 curframe_x = x; 240 prevframe_index = (y + motion_y) * stride + x + motion_x; 241 prevframe_x = x + motion_x; 242 while (pixel_count && 243 curframe_index < s->frame_size && 244 prevframe_index < s->frame_size) { 245 int count = FFMIN3(pixel_count, width - curframe_x, 246 width - prevframe_x); 247 248 memcpy(palette_plane + curframe_index, 249 prev_palette_plane + prevframe_index, count); 250 pixel_count -= count; 251 curframe_index += count; 252 prevframe_index += count; 253 curframe_x += count; 254 prevframe_x += count; 255 256 if (curframe_x >= width) { 257 curframe_index += line_inc; 258 curframe_x = 0; 259 } 260 261 if (prevframe_x >= width) { 262 prevframe_index += line_inc; 263 prevframe_x = 0; 264 } 265 } 266} 267 268static int xan_wc3_decode_frame(XanContext *s) { 269 270 int width = s->avctx->width; 271 int height = s->avctx->height; 272 int total_pixels = width * height; 273 unsigned char opcode; 274 unsigned char flag = 0; 275 int size = 0; 276 int motion_x, motion_y; 277 int x, y; 278 279 unsigned char *opcode_buffer = s->buffer1; 280 unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size; 281 int opcode_buffer_size = s->buffer1_size; 282 const unsigned char *imagedata_buffer = s->buffer2; 283 284 /* pointers to segments inside the compressed chunk */ 285 const unsigned char *huffman_segment; 286 const unsigned char *size_segment; 287 const unsigned char *vector_segment; 288 const unsigned char *imagedata_segment; 289 int huffman_offset, size_offset, vector_offset, imagedata_offset, 290 imagedata_size; 291 292 if (s->size < 8) 293 return AVERROR_INVALIDDATA; 294 295 huffman_offset = AV_RL16(&s->buf[0]); 296 size_offset = AV_RL16(&s->buf[2]); 297 vector_offset = AV_RL16(&s->buf[4]); 298 imagedata_offset = AV_RL16(&s->buf[6]); 299 300 if (huffman_offset >= s->size || 301 size_offset >= s->size || 302 vector_offset >= s->size || 303 imagedata_offset >= s->size) 304 return AVERROR_INVALIDDATA; 305 306 huffman_segment = s->buf + huffman_offset; 307 size_segment = s->buf + size_offset; 308 vector_segment = s->buf + vector_offset; 309 imagedata_segment = s->buf + imagedata_offset; 310 311 if (xan_huffman_decode(opcode_buffer, opcode_buffer_size, 312 huffman_segment, s->size - huffman_offset) < 0) 313 return AVERROR_INVALIDDATA; 314 315 if (imagedata_segment[0] == 2) { 316 xan_unpack(s->buffer2, s->buffer2_size, 317 &imagedata_segment[1], s->size - imagedata_offset - 1); 318 imagedata_size = s->buffer2_size; 319 } else { 320 imagedata_size = s->size - imagedata_offset - 1; 321 imagedata_buffer = &imagedata_segment[1]; 322 } 323 324 /* use the decoded data segments to build the frame */ 325 x = y = 0; 326 while (total_pixels && opcode_buffer < opcode_buffer_end) { 327 328 opcode = *opcode_buffer++; 329 size = 0; 330 331 switch (opcode) { 332 333 case 0: 334 flag ^= 1; 335 continue; 336 337 case 1: 338 case 2: 339 case 3: 340 case 4: 341 case 5: 342 case 6: 343 case 7: 344 case 8: 345 size = opcode; 346 break; 347 348 case 12: 349 case 13: 350 case 14: 351 case 15: 352 case 16: 353 case 17: 354 case 18: 355 size += (opcode - 10); 356 break; 357 358 case 9: 359 case 19: 360 size = *size_segment++; 361 break; 362 363 case 10: 364 case 20: 365 size = AV_RB16(&size_segment[0]); 366 size_segment += 2; 367 break; 368 369 case 11: 370 case 21: 371 size = AV_RB24(size_segment); 372 size_segment += 3; 373 break; 374 } 375 376 if (size > total_pixels) 377 break; 378 379 if (opcode < 12) { 380 flag ^= 1; 381 if (flag) { 382 /* run of (size) pixels is unchanged from last frame */ 383 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0); 384 } else { 385 /* output a run of pixels from imagedata_buffer */ 386 if (imagedata_size < size) 387 break; 388 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size); 389 imagedata_buffer += size; 390 imagedata_size -= size; 391 } 392 } else { 393 /* run-based motion compensation from last frame */ 394 motion_x = sign_extend(*vector_segment >> 4, 4); 395 motion_y = sign_extend(*vector_segment & 0xF, 4); 396 vector_segment++; 397 398 /* copy a run of pixels from the previous frame */ 399 xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y); 400 401 flag = 0; 402 } 403 404 /* coordinate accounting */ 405 total_pixels -= size; 406 y += (x + size) / width; 407 x = (x + size) % width; 408 } 409 return 0; 410} 411 412#if RUNTIME_GAMMA 413static inline unsigned mul(unsigned a, unsigned b) 414{ 415 return (a * b) >> 16; 416} 417 418static inline unsigned pow4(unsigned a) 419{ 420 unsigned square = mul(a, a); 421 return mul(square, square); 422} 423 424static inline unsigned pow5(unsigned a) 425{ 426 return mul(pow4(a), a); 427} 428 429static uint8_t gamma_corr(uint8_t in) { 430 unsigned lo, hi = 0xff40, target; 431 int i = 15; 432 in = (in << 2) | (in >> 6); 433 /* equivalent float code: 434 if (in >= 252) 435 return 253; 436 return round(pow(in / 256.0, 0.8) * 256); 437 */ 438 lo = target = in << 8; 439 do { 440 unsigned mid = (lo + hi) >> 1; 441 unsigned pow = pow5(mid); 442 if (pow > target) hi = mid; 443 else lo = mid; 444 } while (--i); 445 return (pow4((lo + hi) >> 1) + 0x80) >> 8; 446} 447#else 448/** 449 * This is a gamma correction that xan3 applies to all palette entries. 450 * 451 * There is a peculiarity, namely that the values are clamped to 253 - 452 * it seems likely that this table was calculated by a buggy fixed-point 453 * implementation, the one above under RUNTIME_GAMMA behaves like this for 454 * example. 455 * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5 456 * and thus pow(x, 0.8) is still easy to calculate. 457 * Also, the input values are first rotated to the left by 2. 458 */ 459static const uint8_t gamma_lookup[256] = { 460 0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C, 461 0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50, 462 0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71, 463 0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F, 464 0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC, 465 0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8, 466 0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3, 467 0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD, 468 0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D, 469 0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51, 470 0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72, 471 0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90, 472 0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD, 473 0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9, 474 0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4, 475 0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD, 476 0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E, 477 0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52, 478 0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73, 479 0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91, 480 0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE, 481 0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA, 482 0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4, 483 0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD, 484 0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F, 485 0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53, 486 0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74, 487 0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92, 488 0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF, 489 0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB, 490 0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5, 491 0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD 492}; 493#endif 494 495static int xan_decode_frame(AVCodecContext *avctx, 496 void *data, int *data_size, 497 AVPacket *avpkt) 498{ 499 const uint8_t *buf = avpkt->data; 500 int ret, buf_size = avpkt->size; 501 XanContext *s = avctx->priv_data; 502 503 if (avctx->codec->id == CODEC_ID_XAN_WC3) { 504 const uint8_t *buf_end = buf + buf_size; 505 int tag = 0; 506 while (buf_end - buf > 8 && tag != VGA__TAG) { 507 unsigned *tmpptr; 508 uint32_t new_pal; 509 int size; 510 int i; 511 tag = bytestream_get_le32(&buf); 512 size = bytestream_get_be32(&buf); 513 size = FFMIN(size, buf_end - buf); 514 switch (tag) { 515 case PALT_TAG: 516 if (size < PALETTE_SIZE) 517 return AVERROR_INVALIDDATA; 518 if (s->palettes_count >= PALETTES_MAX) 519 return AVERROR_INVALIDDATA; 520 tmpptr = av_realloc(s->palettes, 521 (s->palettes_count + 1) * AVPALETTE_SIZE); 522 if (!tmpptr) 523 return AVERROR(ENOMEM); 524 s->palettes = tmpptr; 525 tmpptr += s->palettes_count * AVPALETTE_COUNT; 526 for (i = 0; i < PALETTE_COUNT; i++) { 527#if RUNTIME_GAMMA 528 int r = gamma_corr(*buf++); 529 int g = gamma_corr(*buf++); 530 int b = gamma_corr(*buf++); 531#else 532 int r = gamma_lookup[*buf++]; 533 int g = gamma_lookup[*buf++]; 534 int b = gamma_lookup[*buf++]; 535#endif 536 *tmpptr++ = (r << 16) | (g << 8) | b; 537 } 538 s->palettes_count++; 539 break; 540 case SHOT_TAG: 541 if (size < 4) 542 return AVERROR_INVALIDDATA; 543 new_pal = bytestream_get_le32(&buf); 544 if (new_pal < s->palettes_count) { 545 s->cur_palette = new_pal; 546 } else 547 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n"); 548 break; 549 case VGA__TAG: 550 break; 551 default: 552 buf += size; 553 break; 554 } 555 } 556 buf_size = buf_end - buf; 557 } 558 if (s->palettes_count <= 0) { 559 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n"); 560 return AVERROR_INVALIDDATA; 561 } 562 563 if ((ret = avctx->get_buffer(avctx, &s->current_frame))) { 564 av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n"); 565 return ret; 566 } 567 s->current_frame.reference = 3; 568 569 if (!s->frame_size) 570 s->frame_size = s->current_frame.linesize[0] * s->avctx->height; 571 572 memcpy(s->current_frame.data[1], 573 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE); 574 575 s->buf = buf; 576 s->size = buf_size; 577 578 if (xan_wc3_decode_frame(s) < 0) 579 return AVERROR_INVALIDDATA; 580 581 /* release the last frame if it is allocated */ 582 if (s->last_frame.data[0]) 583 avctx->release_buffer(avctx, &s->last_frame); 584 585 *data_size = sizeof(AVFrame); 586 *(AVFrame*)data = s->current_frame; 587 588 /* shuffle frames */ 589 FFSWAP(AVFrame, s->current_frame, s->last_frame); 590 591 /* always report that the buffer was completely consumed */ 592 return buf_size; 593} 594 595static av_cold int xan_decode_end(AVCodecContext *avctx) 596{ 597 XanContext *s = avctx->priv_data; 598 599 /* release the frames */ 600 if (s->last_frame.data[0]) 601 avctx->release_buffer(avctx, &s->last_frame); 602 if (s->current_frame.data[0]) 603 avctx->release_buffer(avctx, &s->current_frame); 604 605 av_freep(&s->buffer1); 606 av_freep(&s->buffer2); 607 av_freep(&s->palettes); 608 609 return 0; 610} 611 612AVCodec ff_xan_wc3_decoder = { 613 .name = "xan_wc3", 614 .type = AVMEDIA_TYPE_VIDEO, 615 .id = CODEC_ID_XAN_WC3, 616 .priv_data_size = sizeof(XanContext), 617 .init = xan_decode_init, 618 .close = xan_decode_end, 619 .decode = xan_decode_frame, 620 .capabilities = CODEC_CAP_DR1, 621 .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"), 622}; 623