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 "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
  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
 152                 size = opcode & 3;
 153
 154                 back  = ((opcode & 0x60) << 3) + *src++ + 1;
 155                 size2 = ((opcode & 0x1c) >> 2) + 3;
 156
 157             } else if ( (opcode & 0x40) == 0 ) {
 158
 159                 size = *src >> 6;
 160
 161                 back  = (bytestream_get_be16(&src) & 0x3fff) + 1;
 162                 size2 = (opcode & 0x3f) + 4;
 163
 164             } else {
 165
 166                 size = opcode & 3;
 167
 168                 back  = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
 169                 size2 = ((opcode & 0x0c) <<  6) + *src++ + 5;
 170             }
 171             if (dest_end - dest < size + size2 ||
 172                 dest + size - dest_org < back ||
 173                 src_end - src < size)
 174                 return;
 175             memcpy(dest, src, size);  dest += size;  src += size;
 176             av_memcpy_backptr(dest, back, size2);
 177             dest += size2;
 178         } else {
 179             int finish = opcode >= 0xfc;
 180             size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
 181
 182             if (dest_end - dest < size || src_end - src < size)
 183                 return;
 184             memcpy(dest, src, size);  dest += size;  src += size;
 185             if (finish)
 186                 return;
 187         }
 188     }
 189 }
 190
 191 static inline void xan_wc3_output_pixel_run(XanContext *s,
 192     const unsigned char *pixel_buffer, int x, int y, int pixel_count)
 193 {
 194     int stride;
 195     int line_inc;
 196     int index;
 197     int current_x;
 198     int width = s->avctx->width;
 199     unsigned char *palette_plane;
 200
 201     palette_plane = s->current_frame.data[0];
 202     stride = s->current_frame.linesize[0];
 203     line_inc = stride - width;
 204     index = y * stride + x;
 205     current_x = x;
 206     while(pixel_count && (index < s->frame_size)) {
 207         int count = FFMIN(pixel_count, width - current_x);
 208         memcpy(palette_plane + index, pixel_buffer, count);
 209         pixel_count  -= count;
 210         index        += count;
 211         pixel_buffer += count;
 212         current_x    += count;
 213
 214         if (current_x >= width) {
 215             index += line_inc;
 216             current_x = 0;
 217         }
 218     }
 219 }
 220
 221 static inline void xan_wc3_copy_pixel_run(XanContext *s,
 222     int x, int y, int pixel_count, int motion_x, int motion_y)
 223 {
 224     int stride;
 225     int line_inc;
 226     int curframe_index, prevframe_index;
 227     int curframe_x, prevframe_x;
 228     int width = s->avctx->width;
 229     unsigned char *palette_plane, *prev_palette_plane;
 230
 231     if ( y + motion_y < 0 || y + motion_y >= s->avctx->height ||
 232          x + motion_x < 0 || x + motion_x >= s->avctx->width)
 233         return;
 234
 235     palette_plane = s->current_frame.data[0];
 236     prev_palette_plane = s->last_frame.data[0];
 237     if (!prev_palette_plane)
 238         prev_palette_plane = palette_plane;
 239     stride = s->current_frame.linesize[0];
 240     line_inc = stride - width;
 241     curframe_index = y * stride + x;
 242     curframe_x = x;
 243     prevframe_index = (y + motion_y) * stride + x + motion_x;
 244     prevframe_x = x + motion_x;
 245     while(pixel_count &&
 246           curframe_index  < s->frame_size &&
 247           prevframe_index < s->frame_size) {
 248         int count = FFMIN3(pixel_count, width - curframe_x, width - prevframe_x);
 249
 250         memcpy(palette_plane + curframe_index, prev_palette_plane + prevframe_index, count);
 251         pixel_count     -= count;
 252         curframe_index  += count;
 253         prevframe_index += count;
 254         curframe_x      += count;
 255         prevframe_x     += count;
 256
 257         if (curframe_x >= width) {
 258             curframe_index += line_inc;
 259             curframe_x = 0;
 260         }
 261
 262         if (prevframe_x >= width) {
 263             prevframe_index += line_inc;
 264             prevframe_x = 0;
 265         }
 266     }
 267 }
 268
 269 static int xan_wc3_decode_frame(XanContext *s) {
 270
 271     int width = s->avctx->width;
 272     int height = s->avctx->height;
 273     int total_pixels = width * height;
 274     unsigned char opcode;
 275     unsigned char flag = 0;
 276     int size = 0;
 277     int motion_x, motion_y;
 278     int x, y;
 279
 280     unsigned char *opcode_buffer = s->buffer1;
 281     unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
 282     int opcode_buffer_size = s->buffer1_size;
 283     const unsigned char *imagedata_buffer = s->buffer2;
 284
 285     /* pointers to segments inside the compressed chunk */
 286     const unsigned char *huffman_segment;
 287     const unsigned char *size_segment;
 288     const unsigned char *vector_segment;
 289     const unsigned char *imagedata_segment;
 290     int huffman_offset, size_offset, vector_offset, imagedata_offset, 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         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 == 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, (s->palettes_count + 1) * AVPALETTE_SIZE);
 520                 if (!tmpptr)
 521                     return AVERROR(ENOMEM);
 522                 s->palettes = tmpptr;
 523                 tmpptr += s->palettes_count * AVPALETTE_COUNT;
 524                 for (i = 0; i < PALETTE_COUNT; i++) {
 525 #if RUNTIME_GAMMA
 526                     int r = gamma_corr(*buf++);
 527                     int g = gamma_corr(*buf++);
 528                     int b = gamma_corr(*buf++);
 529 #else
 530                     int r = gamma_lookup[*buf++];
 531                     int g = gamma_lookup[*buf++];
 532                     int b = gamma_lookup[*buf++];
 533 #endif
 534                     *tmpptr++ = (r << 16) | (g << 8) | b;
 535                 }
 536                 s->palettes_count++;
 537                 break;
 538             case SHOT_TAG:
 539                 if (size < 4)
 540                     return AVERROR_INVALIDDATA;
 541                 new_pal = bytestream_get_le32(&buf);
 542                 if (new_pal < s->palettes_count) {
 543                     s->cur_palette = new_pal;
 544                 } else
 545                     av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
 546                 break;
 547             case VGA__TAG:
 548                 break;
 549             default:
 550                 buf += size;
 551                 break;
 552             }
 553         }
 554         buf_size = buf_end - buf;
 555     }
 556     if (s->palettes_count <= 0) {
 557         av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
 558         return AVERROR_INVALIDDATA;
 559     }
 560
 561     if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
 562         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 563         return ret;
 564     }
 565     s->current_frame.reference = 3;
 566
 567     if (!s->frame_size)
 568         s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
 569
 570     memcpy(s->current_frame.data[1], s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
 571
 572     s->buf = buf;
 573     s->size = buf_size;
 574
 575     if (xan_wc3_decode_frame(s) < 0)
 576         return AVERROR_INVALIDDATA;
 577
 578     /* release the last frame if it is allocated */
 579     if (s->last_frame.data[0])
 580         avctx->release_buffer(avctx, &s->last_frame);
 581
 582     *data_size = sizeof(AVFrame);
 583     *(AVFrame*)data = s->current_frame;
 584
 585     /* shuffle frames */
 586     FFSWAP(AVFrame, s->current_frame, s->last_frame);
 587
 588     /* always report that the buffer was completely consumed */
 589     return buf_size;
 590 }
 591
 592 static av_cold int xan_decode_end(AVCodecContext *avctx)
 593 {
 594     XanContext *s = avctx->priv_data;
 595
 596     /* release the frames */
 597     if (s->last_frame.data[0])
 598         avctx->release_buffer(avctx, &s->last_frame);
 599     if (s->current_frame.data[0])
 600         avctx->release_buffer(avctx, &s->current_frame);
 601
 602     av_freep(&s->buffer1);
 603     av_freep(&s->buffer2);
 604     av_freep(&s->palettes);
 605
 606     return 0;
 607 }
 608
 609 AVCodec ff_xan_wc3_decoder = {
 610     .name           = "xan_wc3",
 611     .type           = AVMEDIA_TYPE_VIDEO,
 612     .id             = CODEC_ID_XAN_WC3,
 613     .priv_data_size = sizeof(XanContext),
 614     .init           = xan_decode_init,
 615     .close          = xan_decode_end,
 616     .decode         = xan_decode_frame,
 617     .capabilities   = CODEC_CAP_DR1,
 618     .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
 619 };