git.sesse.net Git - ffmpeg/blob - libavcodec/xan.c

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