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