libavcodec/xan.c
Go to the documentation of this file.
00001 /*
00002  * Wing Commander/Xan Video Decoder
00003  * Copyright (C) 2003 the ffmpeg project
00004  *
00005  * This file is part of Libav.
00006  *
00007  * Libav is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or (at your option) any later version.
00011  *
00012  * Libav is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with Libav; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00020  */
00021 
00031 #include <stdio.h>
00032 #include <stdlib.h>
00033 #include <string.h>
00034 
00035 #include "libavutil/intreadwrite.h"
00036 #include "avcodec.h"
00037 #include "internal.h"
00038 #include "bytestream.h"
00039 #define BITSTREAM_READER_LE
00040 #include "get_bits.h"
00041 // for av_memcpy_backptr
00042 #include "libavutil/lzo.h"
00043 
00044 #define RUNTIME_GAMMA 0
00045 
00046 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
00047 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
00048 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
00049 #define PALETTE_COUNT 256
00050 #define PALETTE_SIZE (PALETTE_COUNT * 3)
00051 #define PALETTES_MAX 256
00052 
00053 typedef struct XanContext {
00054 
00055     AVCodecContext *avctx;
00056     AVFrame last_frame;
00057     AVFrame current_frame;
00058 
00059     const unsigned char *buf;
00060     int size;
00061 
00062     /* scratch space */
00063     unsigned char *buffer1;
00064     int buffer1_size;
00065     unsigned char *buffer2;
00066     int buffer2_size;
00067 
00068     unsigned *palettes;
00069     int palettes_count;
00070     int cur_palette;
00071 
00072     int frame_size;
00073 
00074 } XanContext;
00075 
00076 static av_cold int xan_decode_init(AVCodecContext *avctx)
00077 {
00078     XanContext *s = avctx->priv_data;
00079 
00080     s->avctx = avctx;
00081     s->frame_size = 0;
00082 
00083     avctx->pix_fmt = PIX_FMT_PAL8;
00084 
00085     s->buffer1_size = avctx->width * avctx->height;
00086     s->buffer1 = av_malloc(s->buffer1_size);
00087     if (!s->buffer1)
00088         return AVERROR(ENOMEM);
00089     s->buffer2_size = avctx->width * avctx->height;
00090     s->buffer2 = av_malloc(s->buffer2_size + 130);
00091     if (!s->buffer2) {
00092         av_freep(&s->buffer1);
00093         return AVERROR(ENOMEM);
00094     }
00095 
00096     return 0;
00097 }
00098 
00099 static int xan_huffman_decode(unsigned char *dest, int dest_len,
00100                               const unsigned char *src, int src_len)
00101 {
00102     unsigned char byte = *src++;
00103     unsigned char ival = byte + 0x16;
00104     const unsigned char * ptr = src + byte*2;
00105     int ptr_len = src_len - 1 - byte*2;
00106     unsigned char val = ival;
00107     unsigned char *dest_end = dest + dest_len;
00108     unsigned char *dest_start = dest;
00109     GetBitContext gb;
00110 
00111     if (ptr_len < 0)
00112         return AVERROR_INVALIDDATA;
00113 
00114     init_get_bits(&gb, ptr, ptr_len * 8);
00115 
00116     while (val != 0x16) {
00117         unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
00118         if (idx >= 2 * byte)
00119             return -1;
00120         val = src[idx];
00121 
00122         if (val < 0x16) {
00123             if (dest >= dest_end)
00124                 return dest_len;
00125             *dest++ = val;
00126             val = ival;
00127         }
00128     }
00129 
00130     return dest - dest_start;
00131 }
00132 
00138 static void xan_unpack(unsigned char *dest, int dest_len,
00139                        const unsigned char *src, int src_len)
00140 {
00141     unsigned char opcode;
00142     int size;
00143     unsigned char *dest_org = dest;
00144     unsigned char *dest_end = dest + dest_len;
00145     const unsigned char *src_end = src + src_len;
00146 
00147     while (dest < dest_end && src < src_end) {
00148         opcode = *src++;
00149 
00150         if (opcode < 0xe0) {
00151             int size2, back;
00152             if ((opcode & 0x80) == 0) {
00153                 size = opcode & 3;
00154 
00155                 back  = ((opcode & 0x60) << 3) + *src++ + 1;
00156                 size2 = ((opcode & 0x1c) >> 2) + 3;
00157             } else if ((opcode & 0x40) == 0) {
00158                 size = *src >> 6;
00159 
00160                 back  = (bytestream_get_be16(&src) & 0x3fff) + 1;
00161                 size2 = (opcode & 0x3f) + 4;
00162             } else {
00163                 size = opcode & 3;
00164 
00165                 back  = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
00166                 size2 = ((opcode & 0x0c) <<  6) + *src++ + 5;
00167             }
00168 
00169             if (dest_end - dest < size + size2 ||
00170                 dest + size - dest_org < back ||
00171                 src_end - src < size)
00172                 return;
00173             memcpy(dest, src, size);  dest += size;  src += size;
00174             av_memcpy_backptr(dest, back, size2);
00175             dest += size2;
00176         } else {
00177             int finish = opcode >= 0xfc;
00178             size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
00179 
00180             if (dest_end - dest < size || src_end - src < size)
00181                 return;
00182             memcpy(dest, src, size);  dest += size;  src += size;
00183             if (finish)
00184                 return;
00185         }
00186     }
00187 }
00188 
00189 static inline void xan_wc3_output_pixel_run(XanContext *s,
00190     const unsigned char *pixel_buffer, int x, int y, int pixel_count)
00191 {
00192     int stride;
00193     int line_inc;
00194     int index;
00195     int current_x;
00196     int width = s->avctx->width;
00197     unsigned char *palette_plane;
00198 
00199     palette_plane = s->current_frame.data[0];
00200     stride = s->current_frame.linesize[0];
00201     line_inc = stride - width;
00202     index = y * stride + x;
00203     current_x = x;
00204     while (pixel_count && index < s->frame_size) {
00205         int count = FFMIN(pixel_count, width - current_x);
00206         memcpy(palette_plane + index, pixel_buffer, count);
00207         pixel_count  -= count;
00208         index        += count;
00209         pixel_buffer += count;
00210         current_x    += count;
00211 
00212         if (current_x >= width) {
00213             index += line_inc;
00214             current_x = 0;
00215         }
00216     }
00217 }
00218 
00219 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
00220                                           int pixel_count, int motion_x,
00221                                           int motion_y)
00222 {
00223     int stride;
00224     int line_inc;
00225     int curframe_index, prevframe_index;
00226     int curframe_x, prevframe_x;
00227     int width = s->avctx->width;
00228     unsigned char *palette_plane, *prev_palette_plane;
00229 
00230     if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
00231         x + motion_x < 0 || x + motion_x >= s->avctx->width)
00232         return;
00233 
00234     palette_plane = s->current_frame.data[0];
00235     prev_palette_plane = s->last_frame.data[0];
00236     if (!prev_palette_plane)
00237         prev_palette_plane = palette_plane;
00238     stride = s->current_frame.linesize[0];
00239     line_inc = stride - width;
00240     curframe_index = y * stride + x;
00241     curframe_x = x;
00242     prevframe_index = (y + motion_y) * stride + x + motion_x;
00243     prevframe_x = x + motion_x;
00244     while (pixel_count &&
00245            curframe_index  < s->frame_size &&
00246            prevframe_index < s->frame_size) {
00247         int count = FFMIN3(pixel_count, width - curframe_x,
00248                            width - prevframe_x);
00249 
00250         memcpy(palette_plane + curframe_index,
00251                prev_palette_plane + prevframe_index, count);
00252         pixel_count     -= count;
00253         curframe_index  += count;
00254         prevframe_index += count;
00255         curframe_x      += count;
00256         prevframe_x     += count;
00257 
00258         if (curframe_x >= width) {
00259             curframe_index += line_inc;
00260             curframe_x = 0;
00261         }
00262 
00263         if (prevframe_x >= width) {
00264             prevframe_index += line_inc;
00265             prevframe_x = 0;
00266         }
00267     }
00268 }
00269 
00270 static int xan_wc3_decode_frame(XanContext *s) {
00271 
00272     int width  = s->avctx->width;
00273     int height = s->avctx->height;
00274     int total_pixels = width * height;
00275     unsigned char opcode;
00276     unsigned char flag = 0;
00277     int size = 0;
00278     int motion_x, motion_y;
00279     int x, y, ret;
00280 
00281     unsigned char *opcode_buffer = s->buffer1;
00282     unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
00283     int opcode_buffer_size = s->buffer1_size;
00284     const unsigned char *imagedata_buffer = s->buffer2;
00285 
00286     /* pointers to segments inside the compressed chunk */
00287     const unsigned char *huffman_segment;
00288     GetByteContext       size_segment;
00289     GetByteContext       vector_segment;
00290     const unsigned char *imagedata_segment;
00291     int huffman_offset, size_offset, vector_offset, imagedata_offset,
00292         imagedata_size;
00293 
00294     if (s->size < 8)
00295         return AVERROR_INVALIDDATA;
00296 
00297     huffman_offset    = AV_RL16(&s->buf[0]);
00298     size_offset       = AV_RL16(&s->buf[2]);
00299     vector_offset     = AV_RL16(&s->buf[4]);
00300     imagedata_offset  = AV_RL16(&s->buf[6]);
00301 
00302     if (huffman_offset   >= s->size ||
00303         size_offset      >= s->size ||
00304         vector_offset    >= s->size ||
00305         imagedata_offset >= s->size)
00306         return AVERROR_INVALIDDATA;
00307 
00308     huffman_segment   = s->buf + huffman_offset;
00309     bytestream2_init(&size_segment,   s->buf + size_offset,   s->size - size_offset);
00310     bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
00311     imagedata_segment = s->buf + imagedata_offset;
00312 
00313     if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
00314                                   huffman_segment, s->size - huffman_offset)) < 0)
00315         return AVERROR_INVALIDDATA;
00316     opcode_buffer_end = opcode_buffer + ret;
00317 
00318     if (imagedata_segment[0] == 2) {
00319         xan_unpack(s->buffer2, s->buffer2_size,
00320                    &imagedata_segment[1], s->size - imagedata_offset - 1);
00321         imagedata_size = s->buffer2_size;
00322     } else {
00323         imagedata_size = s->size - imagedata_offset - 1;
00324         imagedata_buffer = &imagedata_segment[1];
00325     }
00326 
00327     /* use the decoded data segments to build the frame */
00328     x = y = 0;
00329     while (total_pixels && opcode_buffer < opcode_buffer_end) {
00330 
00331         opcode = *opcode_buffer++;
00332         size = 0;
00333 
00334         switch (opcode) {
00335 
00336         case 0:
00337             flag ^= 1;
00338             continue;
00339 
00340         case 1:
00341         case 2:
00342         case 3:
00343         case 4:
00344         case 5:
00345         case 6:
00346         case 7:
00347         case 8:
00348             size = opcode;
00349             break;
00350 
00351         case 12:
00352         case 13:
00353         case 14:
00354         case 15:
00355         case 16:
00356         case 17:
00357         case 18:
00358             size += (opcode - 10);
00359             break;
00360 
00361         case 9:
00362         case 19:
00363             size = bytestream2_get_byte(&size_segment);
00364             break;
00365 
00366         case 10:
00367         case 20:
00368             size = bytestream2_get_be16(&size_segment);
00369             break;
00370 
00371         case 11:
00372         case 21:
00373             size = bytestream2_get_be24(&size_segment);
00374             break;
00375         }
00376 
00377         if (size > total_pixels)
00378             break;
00379 
00380         if (opcode < 12) {
00381             flag ^= 1;
00382             if (flag) {
00383                 /* run of (size) pixels is unchanged from last frame */
00384                 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
00385             } else {
00386                 /* output a run of pixels from imagedata_buffer */
00387                 if (imagedata_size < size)
00388                     break;
00389                 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
00390                 imagedata_buffer += size;
00391                 imagedata_size -= size;
00392             }
00393         } else {
00394             /* run-based motion compensation from last frame */
00395             uint8_t vector = bytestream2_get_byte(&vector_segment);
00396             motion_x = sign_extend(vector >> 4,  4);
00397             motion_y = sign_extend(vector & 0xF, 4);
00398 
00399             /* copy a run of pixels from the previous frame */
00400             xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
00401 
00402             flag = 0;
00403         }
00404 
00405         /* coordinate accounting */
00406         total_pixels -= size;
00407         y += (x + size) / width;
00408         x  = (x + size) % width;
00409     }
00410     return 0;
00411 }
00412 
00413 #if RUNTIME_GAMMA
00414 static inline unsigned mul(unsigned a, unsigned b)
00415 {
00416     return (a * b) >> 16;
00417 }
00418 
00419 static inline unsigned pow4(unsigned a)
00420 {
00421     unsigned square = mul(a, a);
00422     return mul(square, square);
00423 }
00424 
00425 static inline unsigned pow5(unsigned a)
00426 {
00427     return mul(pow4(a), a);
00428 }
00429 
00430 static uint8_t gamma_corr(uint8_t in) {
00431     unsigned lo, hi = 0xff40, target;
00432     int i = 15;
00433     in = (in << 2) | (in >> 6);
00434     /*  equivalent float code:
00435     if (in >= 252)
00436         return 253;
00437     return round(pow(in / 256.0, 0.8) * 256);
00438     */
00439     lo = target = in << 8;
00440     do {
00441         unsigned mid = (lo + hi) >> 1;
00442         unsigned pow = pow5(mid);
00443         if (pow > target) hi = mid;
00444         else lo = mid;
00445     } while (--i);
00446     return (pow4((lo + hi) >> 1) + 0x80) >> 8;
00447 }
00448 #else
00449 
00460 static const uint8_t gamma_lookup[256] = {
00461     0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
00462     0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
00463     0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
00464     0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
00465     0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
00466     0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
00467     0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
00468     0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
00469     0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
00470     0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
00471     0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
00472     0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
00473     0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
00474     0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
00475     0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
00476     0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
00477     0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
00478     0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
00479     0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
00480     0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
00481     0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
00482     0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
00483     0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
00484     0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
00485     0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
00486     0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
00487     0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
00488     0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
00489     0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
00490     0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
00491     0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
00492     0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
00493 };
00494 #endif
00495 
00496 static int xan_decode_frame(AVCodecContext *avctx,
00497                             void *data, int *data_size,
00498                             AVPacket *avpkt)
00499 {
00500     const uint8_t *buf = avpkt->data;
00501     int ret, buf_size = avpkt->size;
00502     XanContext *s = avctx->priv_data;
00503 
00504     if (avctx->codec->id == CODEC_ID_XAN_WC3) {
00505         const uint8_t *buf_end = buf + buf_size;
00506         int tag = 0;
00507         while (buf_end - buf > 8 && tag != VGA__TAG) {
00508             unsigned *tmpptr;
00509             uint32_t new_pal;
00510             int size;
00511             int i;
00512             tag  = bytestream_get_le32(&buf);
00513             size = bytestream_get_be32(&buf);
00514             size = FFMIN(size, buf_end - buf);
00515             switch (tag) {
00516             case PALT_TAG:
00517                 if (size < PALETTE_SIZE)
00518                     return AVERROR_INVALIDDATA;
00519                 if (s->palettes_count >= PALETTES_MAX)
00520                     return AVERROR_INVALIDDATA;
00521                 tmpptr = av_realloc(s->palettes,
00522                                     (s->palettes_count + 1) * AVPALETTE_SIZE);
00523                 if (!tmpptr)
00524                     return AVERROR(ENOMEM);
00525                 s->palettes = tmpptr;
00526                 tmpptr += s->palettes_count * AVPALETTE_COUNT;
00527                 for (i = 0; i < PALETTE_COUNT; i++) {
00528 #if RUNTIME_GAMMA
00529                     int r = gamma_corr(*buf++);
00530                     int g = gamma_corr(*buf++);
00531                     int b = gamma_corr(*buf++);
00532 #else
00533                     int r = gamma_lookup[*buf++];
00534                     int g = gamma_lookup[*buf++];
00535                     int b = gamma_lookup[*buf++];
00536 #endif
00537                     *tmpptr++ = (r << 16) | (g << 8) | b;
00538                 }
00539                 s->palettes_count++;
00540                 break;
00541             case SHOT_TAG:
00542                 if (size < 4)
00543                     return AVERROR_INVALIDDATA;
00544                 new_pal = bytestream_get_le32(&buf);
00545                 if (new_pal < s->palettes_count) {
00546                     s->cur_palette = new_pal;
00547                 } else
00548                     av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
00549                 break;
00550             case VGA__TAG:
00551                 break;
00552             default:
00553                 buf += size;
00554                 break;
00555             }
00556         }
00557         buf_size = buf_end - buf;
00558     }
00559     if (s->palettes_count <= 0) {
00560         av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
00561         return AVERROR_INVALIDDATA;
00562     }
00563 
00564     if ((ret = ff_get_buffer(avctx, &s->current_frame))) {
00565         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
00566         return ret;
00567     }
00568     s->current_frame.reference = 3;
00569 
00570     if (!s->frame_size)
00571         s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
00572 
00573     memcpy(s->current_frame.data[1],
00574            s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
00575 
00576     s->buf = buf;
00577     s->size = buf_size;
00578 
00579     if (xan_wc3_decode_frame(s) < 0)
00580         return AVERROR_INVALIDDATA;
00581 
00582     /* release the last frame if it is allocated */
00583     if (s->last_frame.data[0])
00584         avctx->release_buffer(avctx, &s->last_frame);
00585 
00586     *data_size = sizeof(AVFrame);
00587     *(AVFrame*)data = s->current_frame;
00588 
00589     /* shuffle frames */
00590     FFSWAP(AVFrame, s->current_frame, s->last_frame);
00591 
00592     /* always report that the buffer was completely consumed */
00593     return buf_size;
00594 }
00595 
00596 static av_cold int xan_decode_end(AVCodecContext *avctx)
00597 {
00598     XanContext *s = avctx->priv_data;
00599 
00600     /* release the frames */
00601     if (s->last_frame.data[0])
00602         avctx->release_buffer(avctx, &s->last_frame);
00603     if (s->current_frame.data[0])
00604         avctx->release_buffer(avctx, &s->current_frame);
00605 
00606     av_freep(&s->buffer1);
00607     av_freep(&s->buffer2);
00608     av_freep(&s->palettes);
00609 
00610     return 0;
00611 }
00612 
00613 AVCodec ff_xan_wc3_decoder = {
00614     .name           = "xan_wc3",
00615     .type           = AVMEDIA_TYPE_VIDEO,
00616     .id             = CODEC_ID_XAN_WC3,
00617     .priv_data_size = sizeof(XanContext),
00618     .init           = xan_decode_init,
00619     .close          = xan_decode_end,
00620     .decode         = xan_decode_frame,
00621     .capabilities   = CODEC_CAP_DR1,
00622     .long_name      = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
00623 };