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 #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
  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 = AV_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
  98 static 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  */
 136 static 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
 187 static 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
 217 static 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
 268 static 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
 413 static inline unsigned mul(unsigned a, unsigned b)
 414 {
 415     return (a * b) >> 16;
 416 }
 417
 418 static inline unsigned pow4(unsigned a)
 419 {
 420     unsigned square = mul(a, a);
 421     return mul(square, square);
 422 }
 423
 424 static inline unsigned pow5(unsigned a)
 425 {
 426     return mul(pow4(a), a);
 427 }
 428
 429 static 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  */
 459 static 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
 495 static 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 == AV_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 = ff_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
 595 static 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
 612 AVCodec ff_xan_wc3_decoder = {
 613     .name           = "xan_wc3",
 614     .type           = AVMEDIA_TYPE_VIDEO,
 615     .id             = AV_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 };