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