f20e1095eaa07289582b7c9a7e57346d60eee3d4
[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 "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
95     return 0;
96 }
97
98 static int xan_huffman_decode(unsigned char *dest, int dest_len,
99                               const unsigned char *src, int src_len)
100 {
101     unsigned char byte = *src++;
102     unsigned char ival = byte + 0x16;
103     const unsigned char * ptr = src + byte*2;
104     int ptr_len = src_len - 1 - byte*2;
105     unsigned char val = ival;
106     unsigned char *dest_end = dest + dest_len;
107     GetBitContext gb;
108
109     init_get_bits(&gb, ptr, ptr_len * 8);
110
111     while ( val != 0x16 ) {
112         val = src[val - 0x17 + get_bits1(&gb) * byte];
113
114         if ( val < 0x16 ) {
115             if (dest >= dest_end)
116                 return 0;
117             *dest++ = val;
118             val = ival;
119         }
120     }
121
122     return 0;
123 }
124
125 /**
126  * unpack simple compression
127  *
128  * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
129  */
130 static void xan_unpack(unsigned char *dest, const unsigned char *src, int dest_len)
131 {
132     unsigned char opcode;
133     int size;
134     unsigned char *dest_end = dest + dest_len;
135
136     while (dest < dest_end) {
137         opcode = *src++;
138
139         if (opcode < 0xe0) {
140             int size2, back;
141             if ( (opcode & 0x80) == 0 ) {
142
143                 size = opcode & 3;
144
145                 back  = ((opcode & 0x60) << 3) + *src++ + 1;
146                 size2 = ((opcode & 0x1c) >> 2) + 3;
147
148             } else if ( (opcode & 0x40) == 0 ) {
149
150                 size = *src >> 6;
151
152                 back  = (bytestream_get_be16(&src) & 0x3fff) + 1;
153                 size2 = (opcode & 0x3f) + 4;
154
155             } else {
156
157                 size = opcode & 3;
158
159                 back  = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
160                 size2 = ((opcode & 0x0c) <<  6) + *src++ + 5;
161                 if (size + size2 > dest_end - dest)
162                     return;
163             }
164             memcpy(dest, src, size);  dest += size;  src += size;
165             av_memcpy_backptr(dest, back, size2);
166             dest += size2;
167         } else {
168             int finish = opcode >= 0xfc;
169             size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
170
171             memcpy(dest, src, size);  dest += size;  src += size;
172             if (finish)
173                 return;
174         }
175     }
176 }
177
178 static inline void xan_wc3_output_pixel_run(XanContext *s,
179     const unsigned char *pixel_buffer, int x, int y, int pixel_count)
180 {
181     int stride;
182     int line_inc;
183     int index;
184     int current_x;
185     int width = s->avctx->width;
186     unsigned char *palette_plane;
187
188     palette_plane = s->current_frame.data[0];
189     stride = s->current_frame.linesize[0];
190     line_inc = stride - width;
191     index = y * stride + x;
192     current_x = x;
193     while(pixel_count && (index < s->frame_size)) {
194         int count = FFMIN(pixel_count, width - current_x);
195         memcpy(palette_plane + index, pixel_buffer, count);
196         pixel_count  -= count;
197         index        += count;
198         pixel_buffer += count;
199         current_x    += count;
200
201         if (current_x >= width) {
202             index += line_inc;
203             current_x = 0;
204         }
205     }
206 }
207
208 static inline void xan_wc3_copy_pixel_run(XanContext *s,
209     int x, int y, int pixel_count, int motion_x, int motion_y)
210 {
211     int stride;
212     int line_inc;
213     int curframe_index, prevframe_index;
214     int curframe_x, prevframe_x;
215     int width = s->avctx->width;
216     unsigned char *palette_plane, *prev_palette_plane;
217
218     palette_plane = s->current_frame.data[0];
219     prev_palette_plane = s->last_frame.data[0];
220     stride = s->current_frame.linesize[0];
221     line_inc = stride - width;
222     curframe_index = y * stride + x;
223     curframe_x = x;
224     prevframe_index = (y + motion_y) * stride + x + motion_x;
225     prevframe_x = x + motion_x;
226     while(pixel_count && (curframe_index < s->frame_size)) {
227         int count = FFMIN3(pixel_count, width - curframe_x, width - prevframe_x);
228
229         memcpy(palette_plane + curframe_index, prev_palette_plane + prevframe_index, count);
230         pixel_count     -= count;
231         curframe_index  += count;
232         prevframe_index += count;
233         curframe_x      += count;
234         prevframe_x     += count;
235
236         if (curframe_x >= width) {
237             curframe_index += line_inc;
238             curframe_x = 0;
239         }
240
241         if (prevframe_x >= width) {
242             prevframe_index += line_inc;
243             prevframe_x = 0;
244         }
245     }
246 }
247
248 static void xan_wc3_decode_frame(XanContext *s) {
249
250     int width = s->avctx->width;
251     int height = s->avctx->height;
252     int total_pixels = width * height;
253     unsigned char opcode;
254     unsigned char flag = 0;
255     int size = 0;
256     int motion_x, motion_y;
257     int x, y;
258
259     unsigned char *opcode_buffer = s->buffer1;
260     int opcode_buffer_size = s->buffer1_size;
261     const unsigned char *imagedata_buffer = s->buffer2;
262
263     /* pointers to segments inside the compressed chunk */
264     const unsigned char *huffman_segment;
265     const unsigned char *size_segment;
266     const unsigned char *vector_segment;
267     const unsigned char *imagedata_segment;
268
269     huffman_segment =   s->buf + AV_RL16(&s->buf[0]);
270     size_segment =      s->buf + AV_RL16(&s->buf[2]);
271     vector_segment =    s->buf + AV_RL16(&s->buf[4]);
272     imagedata_segment = s->buf + AV_RL16(&s->buf[6]);
273
274     xan_huffman_decode(opcode_buffer, opcode_buffer_size,
275                        huffman_segment, s->size - (huffman_segment - s->buf) );
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