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