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