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