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