1/* 2 * Wing Commander/Xan Video Decoder 3 * Copyright (C) 2003 the ffmpeg project 4 * 5 * This file is part of FFmpeg. 6 * 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. 11 * 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. 16 * 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 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 "libavutil/mem.h" 37#include "avcodec.h" 38#include "bytestream.h" 39#define BITSTREAM_READER_LE 40#include "get_bits.h" 41#include "internal.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 57 const uint8_t *buf; 58 int size; 59 60 /* scratch space */ 61 uint8_t *buffer1; 62 int buffer1_size; 63 uint8_t *buffer2; 64 int buffer2_size; 65 66 unsigned *palettes; 67 int palettes_count; 68 int cur_palette; 69 70 int frame_size; 71 72} XanContext; 73 74static av_cold int xan_decode_end(AVCodecContext *avctx) 75{ 76 XanContext *s = avctx->priv_data; 77 78 av_frame_free(&s->last_frame); 79 80 av_freep(&s->buffer1); 81 av_freep(&s->buffer2); 82 av_freep(&s->palettes); 83 84 return 0; 85} 86 87static av_cold int xan_decode_init(AVCodecContext *avctx) 88{ 89 XanContext *s = avctx->priv_data; 90 91 s->avctx = avctx; 92 s->frame_size = 0; 93 94 avctx->pix_fmt = AV_PIX_FMT_PAL8; 95 96 s->buffer1_size = avctx->width * avctx->height; 97 s->buffer1 = av_malloc(s->buffer1_size); 98 if (!s->buffer1) 99 return AVERROR(ENOMEM); 100 s->buffer2_size = avctx->width * avctx->height; 101 s->buffer2 = av_malloc(s->buffer2_size + 130); 102 if (!s->buffer2) { 103 av_freep(&s->buffer1); 104 return AVERROR(ENOMEM); 105 } 106 107 s->last_frame = av_frame_alloc(); 108 if (!s->last_frame) { 109 xan_decode_end(avctx); 110 return AVERROR(ENOMEM); 111 } 112 113 return 0; 114} 115 116static int xan_huffman_decode(uint8_t *dest, int dest_len, 117 const uint8_t *src, int src_len) 118{ 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; 123 uint8_t val = ival; 124 uint8_t *dest_end = dest + dest_len; 125 uint8_t *dest_start = dest; 126 int ret; 127 GetBitContext gb; 128 129 if ((ret = init_get_bits8(&gb, ptr, ptr_len)) < 0) 130 return ret; 131 132 while (val != 0x16) { 133 unsigned idx = val - 0x17 + get_bits1(&gb) * byte; 134 if (idx >= 2 * byte) 135 return AVERROR_INVALIDDATA; 136 val = src[idx]; 137 138 if (val < 0x16) { 139 if (dest >= dest_end) 140 return dest_len; 141 *dest++ = val; 142 val = ival; 143 } 144 } 145 146 return dest - dest_start; 147} 148 149/** 150 * unpack simple compression 151 * 152 * @param dest destination buffer of dest_len, must be padded with at least 130 bytes 153 */ 154static void xan_unpack(uint8_t *dest, int dest_len, 155 const uint8_t *src, int src_len) 156{ 157 uint8_t opcode; 158 int size; 159 uint8_t *dest_org = dest; 160 uint8_t *dest_end = dest + dest_len; 161 GetByteContext ctx; 162 163 bytestream2_init(&ctx, src, src_len); 164 while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) { 165 opcode = bytestream2_get_byte(&ctx); 166 167 if (opcode < 0xe0) { 168 int size2, back; 169 if ((opcode & 0x80) == 0) { 170 size = opcode & 3; 171 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; 176 177 back = (bytestream2_get_be16(&ctx) & 0x3fff) + 1; 178 size2 = (opcode & 0x3f) + 4; 179 } else { 180 size = opcode & 3; 181 182 back = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1; 183 size2 = ((opcode & 0x0c) << 6) + bytestream2_get_byte(&ctx) + 5; 184 } 185 186 if (dest_end - dest < size + size2 || 187 dest + size - dest_org < back || 188 bytestream2_get_bytes_left(&ctx) < size) 189 return; 190 bytestream2_get_buffer(&ctx, dest, size); 191 dest += size; 192 av_memcpy_backptr(dest, back, size2); 193 dest += size2; 194 } else { 195 int finish = opcode >= 0xfc; 196 size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4; 197 198 if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size) 199 return; 200 bytestream2_get_buffer(&ctx, dest, size); 201 dest += size; 202 if (finish) 203 return; 204 } 205 } 206} 207 208static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame, 209 const uint8_t *pixel_buffer, int x, int y, int pixel_count) 210{ 211 int stride; 212 int line_inc; 213 int index; 214 int current_x; 215 int width = s->avctx->width; 216 uint8_t *palette_plane; 217 218 palette_plane = frame->data[0]; 219 stride = frame->linesize[0]; 220 line_inc = stride - width; 221 index = y * stride + x; 222 current_x = 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; 227 index += count; 228 pixel_buffer += count; 229 current_x += count; 230 231 if (current_x >= width) { 232 index += line_inc; 233 current_x = 0; 234 } 235 } 236} 237 238static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame, 239 int x, int y, 240 int pixel_count, int motion_x, 241 int motion_y) 242{ 243 int stride; 244 int line_inc; 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; 249 250 if (y + motion_y < 0 || y + motion_y >= s->avctx->height || 251 x + motion_x < 0 || x + motion_x >= s->avctx->width) 252 return; 253 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; 261 curframe_x = x; 262 prevframe_index = (y + motion_y) * stride + x + motion_x; 263 prevframe_x = x + motion_x; 264 265 if (prev_palette_plane == palette_plane && FFABS(curframe_index - prevframe_index) < pixel_count) { 266 avpriv_request_sample(s->avctx, "Overlapping copy\n"); 267 return ; 268 } 269 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); 275 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; 281 curframe_x += count; 282 prevframe_x += count; 283 284 if (curframe_x >= width) { 285 curframe_index += line_inc; 286 curframe_x = 0; 287 } 288 289 if (prevframe_x >= width) { 290 prevframe_index += line_inc; 291 prevframe_x = 0; 292 } 293 } 294} 295 296static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame) 297{ 298 299 int width = s->avctx->width; 300 int height = s->avctx->height; 301 int total_pixels = width * height; 302 uint8_t opcode; 303 uint8_t flag = 0; 304 int size = 0; 305 int motion_x, motion_y; 306 int x, y, ret; 307 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; 312 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, 319 imagedata_size; 320 321 if (s->size < 8) 322 return AVERROR_INVALIDDATA; 323 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]); 328 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; 334 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; 339 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; 344 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; 349 } else { 350 imagedata_size = s->size - imagedata_offset - 1; 351 imagedata_buffer = &imagedata_segment[1]; 352 } 353 354 /* use the decoded data segments to build the frame */ 355 x = y = 0; 356 while (total_pixels && opcode_buffer < opcode_buffer_end) { 357 358 opcode = *opcode_buffer++; 359 size = 0; 360 361 switch (opcode) { 362 363 case 0: 364 flag ^= 1; 365 continue; 366 367 case 1: 368 case 2: 369 case 3: 370 case 4: 371 case 5: 372 case 6: 373 case 7: 374 case 8: 375 size = opcode; 376 break; 377 378 case 12: 379 case 13: 380 case 14: 381 case 15: 382 case 16: 383 case 17: 384 case 18: 385 size += (opcode - 10); 386 break; 387 388 case 9: 389 case 19: 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; 393 } 394 size = bytestream2_get_byte(&size_segment); 395 break; 396 397 case 10: 398 case 20: 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; 402 } 403 size = bytestream2_get_be16(&size_segment); 404 break; 405 406 case 11: 407 case 21: 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; 411 } 412 size = bytestream2_get_be24(&size_segment); 413 break; 414 } 415 416 if (size > total_pixels) 417 break; 418 419 if (opcode < 12) { 420 flag ^= 1; 421 if (flag) { 422 /* run of (size) pixels is unchanged from last frame */ 423 xan_wc3_copy_pixel_run(s, frame, x, y, size, 0, 0); 424 } else { 425 /* output a run of pixels from imagedata_buffer */ 426 if (imagedata_size < size) 427 break; 428 xan_wc3_output_pixel_run(s, frame, imagedata_buffer, x, y, size); 429 imagedata_buffer += size; 430 imagedata_size -= size; 431 } 432 } else { 433 uint8_t vector; 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; 437 } 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); 442 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); 445 446 flag = 0; 447 } 448 449 /* coordinate accounting */ 450 total_pixels -= size; 451 y += (x + size) / width; 452 x = (x + size) % width; 453 } 454 return 0; 455} 456 457#if RUNTIME_GAMMA 458static inline unsigned mul(unsigned a, unsigned b) 459{ 460 return (a * b) >> 16; 461} 462 463static inline unsigned pow4(unsigned a) 464{ 465 unsigned square = mul(a, a); 466 return mul(square, square); 467} 468 469static inline unsigned pow5(unsigned a) 470{ 471 return mul(pow4(a), a); 472} 473 474static uint8_t gamma_corr(uint8_t in) { 475 unsigned lo, hi = 0xff40, target; 476 int i = 15; 477 in = (in << 2) | (in >> 6); 478 /* equivalent float code: 479 if (in >= 252) 480 return 253; 481 return round(pow(in / 256.0, 0.8) * 256); 482 */ 483 lo = target = in << 8; 484 do { 485 unsigned mid = (lo + hi) >> 1; 486 unsigned pow = pow5(mid); 487 if (pow > target) hi = mid; 488 else lo = mid; 489 } while (--i); 490 return (pow4((lo + hi) >> 1) + 0x80) >> 8; 491} 492#else 493/** 494 * This is a gamma correction that xan3 applies to all palette entries. 495 * 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 499 * example. 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. 503 */ 504static 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 537}; 538#endif 539 540static int xan_decode_frame(AVCodecContext *avctx, 541 void *data, int *got_frame, 542 AVPacket *avpkt) 543{ 544 AVFrame *frame = data; 545 const uint8_t *buf = avpkt->data; 546 int ret, buf_size = avpkt->size; 547 XanContext *s = avctx->priv_data; 548 GetByteContext ctx; 549 int tag = 0; 550 551 bytestream2_init(&ctx, buf, buf_size); 552 while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) { 553 unsigned *tmpptr; 554 uint32_t new_pal; 555 int size; 556 int i; 557 tag = bytestream2_get_le32(&ctx); 558 size = bytestream2_get_be32(&ctx); 559 if(size < 0) { 560 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size); 561 return AVERROR_INVALIDDATA; 562 } 563 size = FFMIN(size, bytestream2_get_bytes_left(&ctx)); 564 switch (tag) { 565 case PALT_TAG: 566 if (size < PALETTE_SIZE) 567 return AVERROR_INVALIDDATA; 568 if (s->palettes_count >= PALETTES_MAX) 569 return AVERROR_INVALIDDATA; 570 tmpptr = av_realloc(s->palettes, 571 (s->palettes_count + 1) * AVPALETTE_SIZE); 572 if (!tmpptr) 573 return AVERROR(ENOMEM); 574 s->palettes = tmpptr; 575 tmpptr += s->palettes_count * AVPALETTE_COUNT; 576 for (i = 0; i < PALETTE_COUNT; i++) { 577#if RUNTIME_GAMMA 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)); 581#else 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)]; 585#endif 586 *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b; 587 } 588 s->palettes_count++; 589 break; 590 case SHOT_TAG: 591 if (size < 4) 592 return AVERROR_INVALIDDATA; 593 new_pal = bytestream2_get_le32(&ctx); 594 if (new_pal < s->palettes_count) { 595 s->cur_palette = new_pal; 596 } else 597 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n"); 598 break; 599 case VGA__TAG: 600 break; 601 default: 602 bytestream2_skip(&ctx, size); 603 break; 604 } 605 } 606 buf_size = bytestream2_get_bytes_left(&ctx); 607 608 if (s->palettes_count <= 0) { 609 av_log(s->avctx, AV_LOG_ERROR, "No palette found\n"); 610 return AVERROR_INVALIDDATA; 611 } 612 613 if ((ret = ff_get_buffer(avctx, frame, AV_GET_BUFFER_FLAG_REF)) < 0) 614 return ret; 615 616 if (!s->frame_size) 617 s->frame_size = frame->linesize[0] * s->avctx->height; 618 619 memcpy(frame->data[1], 620 s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE); 621 622 s->buf = ctx.buffer; 623 s->size = buf_size; 624 625 if (xan_wc3_decode_frame(s, frame) < 0) 626 return AVERROR_INVALIDDATA; 627 628 av_frame_unref(s->last_frame); 629 if ((ret = av_frame_ref(s->last_frame, frame)) < 0) 630 return ret; 631 632 *got_frame = 1; 633 634 /* always report that the buffer was completely consumed */ 635 return buf_size; 636} 637 638AVCodec ff_xan_wc3_decoder = { 639 .name = "xan_wc3", 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, 648}; 649