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