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