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