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