xan: Only read within the data that actually was initialized
[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     unsigned char *dest_start = dest;
107     GetBitContext gb;
108
109     if (ptr_len < 0)
110         return AVERROR_INVALIDDATA;
111
112     init_get_bits(&gb, ptr, ptr_len * 8);
113
114     while (val != 0x16) {
115         unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
116         if (idx >= 2 * byte)
117             return AVERROR_INVALIDDATA;
118         val = src[idx];
119
120         if (val < 0x16) {
121             if (dest >= dest_end)
122                 return dest_len;
123             *dest++ = val;
124             val = ival;
125         }
126     }
127
128     return dest - dest_start;
129 }
130
131 /**
132  * unpack simple compression
133  *
134  * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
135  */
136 static void xan_unpack(unsigned char *dest, int dest_len,
137                        const unsigned char *src, int src_len)
138 {
139     unsigned char opcode;
140     int size;
141     unsigned char *dest_org = dest;
142     unsigned char *dest_end = dest + dest_len;
143     GetByteContext ctx;
144
145     bytestream2_init(&ctx, src, src_len);
146     while (dest < dest_end && bytestream2_get_bytes_left(&ctx)) {
147         opcode = bytestream2_get_byte(&ctx);
148
149         if (opcode < 0xe0) {
150             int size2, back;
151             if ((opcode & 0x80) == 0) {
152                 size = opcode & 3;
153
154                 back  = ((opcode & 0x60) << 3) + bytestream2_get_byte(&ctx) + 1;
155                 size2 = ((opcode & 0x1c) >> 2) + 3;
156             } else if ((opcode & 0x40) == 0) {
157                 size = bytestream2_peek_byte(&ctx) >> 6;
158
159                 back  = (bytestream2_get_be16(&ctx) & 0x3fff) + 1;
160                 size2 = (opcode & 0x3f) + 4;
161             } else {
162                 size = opcode & 3;
163
164                 back  = ((opcode & 0x10) << 12) + bytestream2_get_be16(&ctx) + 1;
165                 size2 = ((opcode & 0x0c) <<  6) + bytestream2_get_byte(&ctx) + 5;
166             }
167
168             if (dest_end - dest < size + size2 ||
169                 dest + size - dest_org < back ||
170                 bytestream2_get_bytes_left(&ctx) < size)
171                 return;
172             bytestream2_get_buffer(&ctx, dest, size);
173             dest += size;
174             av_memcpy_backptr(dest, back, size2);
175             dest += size2;
176         } else {
177             int finish = opcode >= 0xfc;
178             size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
179
180             if (dest_end - dest < size || bytestream2_get_bytes_left(&ctx) < size)
181                 return;
182             bytestream2_get_buffer(&ctx, dest, size);
183             dest += size;
184             if (finish)
185                 return;
186         }
187     }
188 }
189
190 static inline void xan_wc3_output_pixel_run(XanContext *s, AVFrame *frame,
191     const unsigned char *pixel_buffer, int x, int y, int pixel_count)
192 {
193     int stride;
194     int line_inc;
195     int index;
196     int current_x;
197     int width = s->avctx->width;
198     unsigned char *palette_plane;
199
200     palette_plane = frame->data[0];
201     stride = frame->linesize[0];
202     line_inc = stride - width;
203     index = y * stride + x;
204     current_x = x;
205     while (pixel_count && index < s->frame_size) {
206         int count = FFMIN(pixel_count, width - current_x);
207         memcpy(palette_plane + index, pixel_buffer, count);
208         pixel_count  -= count;
209         index        += count;
210         pixel_buffer += count;
211         current_x    += count;
212
213         if (current_x >= width) {
214             index += line_inc;
215             current_x = 0;
216         }
217     }
218 }
219
220 static inline void xan_wc3_copy_pixel_run(XanContext *s, AVFrame *frame,
221                                           int x, int y,
222                                           int pixel_count, int motion_x,
223                                           int motion_y)
224 {
225     int stride;
226     int line_inc;
227     int curframe_index, prevframe_index;
228     int curframe_x, prevframe_x;
229     int width = s->avctx->width;
230     unsigned char *palette_plane, *prev_palette_plane;
231
232     if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
233         x + motion_x < 0 || x + motion_x >= s->avctx->width)
234         return;
235
236     palette_plane = frame->data[0];
237     prev_palette_plane = s->last_frame.data[0];
238     if (!prev_palette_plane)
239         prev_palette_plane = palette_plane;
240     stride = frame->linesize[0];
241     line_inc = stride - width;
242     curframe_index = y * stride + x;
243     curframe_x = x;
244     prevframe_index = (y + motion_y) * stride + x + motion_x;
245     prevframe_x = x + motion_x;
246     while (pixel_count &&
247            curframe_index  < s->frame_size &&
248            prevframe_index < s->frame_size) {
249         int count = FFMIN3(pixel_count, width - curframe_x,
250                            width - prevframe_x);
251
252         memcpy(palette_plane + curframe_index,
253                prev_palette_plane + prevframe_index, count);
254         pixel_count     -= count;
255         curframe_index  += count;
256         prevframe_index += count;
257         curframe_x      += count;
258         prevframe_x     += count;
259
260         if (curframe_x >= width) {
261             curframe_index += line_inc;
262             curframe_x = 0;
263         }
264
265         if (prevframe_x >= width) {
266             prevframe_index += line_inc;
267             prevframe_x = 0;
268         }
269     }
270 }
271
272 static int xan_wc3_decode_frame(XanContext *s, AVFrame *frame)
273 {
274
275     int width  = s->avctx->width;
276     int height = s->avctx->height;
277     int total_pixels = width * height;
278     unsigned char opcode;
279     unsigned char flag = 0;
280     int size = 0;
281     int motion_x, motion_y;
282     int x, y, ret;
283
284     unsigned char *opcode_buffer = s->buffer1;
285     unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
286     int opcode_buffer_size = s->buffer1_size;
287     const unsigned char *imagedata_buffer = s->buffer2;
288
289     /* pointers to segments inside the compressed chunk */
290     const unsigned char *huffman_segment;
291     GetByteContext       size_segment;
292     GetByteContext       vector_segment;
293     const unsigned char *imagedata_segment;
294     int huffman_offset, size_offset, vector_offset, imagedata_offset,
295         imagedata_size;
296
297     if (s->size < 8)
298         return AVERROR_INVALIDDATA;
299
300     huffman_offset    = AV_RL16(&s->buf[0]);
301     size_offset       = AV_RL16(&s->buf[2]);
302     vector_offset     = AV_RL16(&s->buf[4]);
303     imagedata_offset  = AV_RL16(&s->buf[6]);
304
305     if (huffman_offset   >= s->size ||
306         size_offset      >= s->size ||
307         vector_offset    >= s->size ||
308         imagedata_offset >= s->size)
309         return AVERROR_INVALIDDATA;
310
311     huffman_segment   = s->buf + huffman_offset;
312     bytestream2_init(&size_segment,   s->buf + size_offset,   s->size - size_offset);
313     bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
314     imagedata_segment = s->buf + imagedata_offset;
315
316     if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
317                                   huffman_segment, s->size - huffman_offset)) < 0)
318         return AVERROR_INVALIDDATA;
319     opcode_buffer_end = opcode_buffer + ret;
320
321     if (imagedata_segment[0] == 2) {
322         xan_unpack(s->buffer2, s->buffer2_size,
323                    &imagedata_segment[1], s->size - imagedata_offset - 1);
324         imagedata_size = s->buffer2_size;
325     } else {
326         imagedata_size = s->size - imagedata_offset - 1;
327         imagedata_buffer = &imagedata_segment[1];
328     }
329
330     /* use the decoded data segments to build the frame */
331     x = y = 0;
332     while (total_pixels && opcode_buffer < opcode_buffer_end) {
333
334         opcode = *opcode_buffer++;
335         size = 0;
336
337         switch (opcode) {
338
339         case 0:
340             flag ^= 1;
341             continue;
342
343         case 1:
344         case 2:
345         case 3:
346         case 4:
347         case 5:
348         case 6:
349         case 7:
350         case 8:
351             size = opcode;
352             break;
353
354         case 12:
355         case 13:
356         case 14:
357         case 15:
358         case 16:
359         case 17:
360         case 18:
361             size += (opcode - 10);
362             break;
363
364         case 9:
365         case 19:
366             size = bytestream2_get_byte(&size_segment);
367             break;
368
369         case 10:
370         case 20:
371             size = bytestream2_get_be16(&size_segment);
372             break;
373
374         case 11:
375         case 21:
376             size = bytestream2_get_be24(&size_segment);
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             uint8_t vector = bytestream2_get_byte(&vector_segment);
399             motion_x = sign_extend(vector >> 4,  4);
400             motion_y = sign_extend(vector & 0xF, 4);
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 };