bccbe24d85b7489c18f14c463abf52a882adef24
[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             if (buf_end - size_segment < 1) {
363                 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
364                 return AVERROR_INVALIDDATA;
365             }
366             size = *size_segment++;
367             break;
368
369         case 10:
370         case 20:
371             if (buf_end - size_segment < 2) {
372                 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
373                 return AVERROR_INVALIDDATA;
374             }
375             size = AV_RB16(&size_segment[0]);
376             size_segment += 2;
377             break;
378
379         case 11:
380         case 21:
381             if (buf_end - size_segment < 3) {
382                 av_log(s->avctx, AV_LOG_ERROR, "size_segment overread\n");
383                 return AVERROR_INVALIDDATA;
384             }
385             size = AV_RB24(size_segment);
386             size_segment += 3;
387             break;
388         }
389
390         if (size > total_pixels)
391             break;
392
393         if (opcode < 12) {
394             flag ^= 1;
395             if (flag) {
396                 /* run of (size) pixels is unchanged from last frame */
397                 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
398             } else {
399                 /* output a run of pixels from imagedata_buffer */
400                 if (imagedata_size < size)
401                     break;
402                 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
403                 imagedata_buffer += size;
404                 imagedata_size -= size;
405             }
406         } else {
407             if (vector_segment >= buf_end) {
408                 av_log(s->avctx, AV_LOG_ERROR, "vector_segment overread\n");
409                 return AVERROR_INVALIDDATA;
410             }
411             /* run-based motion compensation from last frame */
412             motion_x = sign_extend(*vector_segment >> 4,  4);
413             motion_y = sign_extend(*vector_segment & 0xF, 4);
414             vector_segment++;
415
416             /* copy a run of pixels from the previous frame */
417             xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
418
419             flag = 0;
420         }
421
422         /* coordinate accounting */
423         total_pixels -= size;
424         y += (x + size) / width;
425         x  = (x + size) % width;
426     }
427     return 0;
428 }
429
430 #if RUNTIME_GAMMA
431 static inline unsigned mul(unsigned a, unsigned b)
432 {
433     return (a * b) >> 16;
434 }
435
436 static inline unsigned pow4(unsigned a)
437 {
438     unsigned square = mul(a, a);
439     return mul(square, square);
440 }
441
442 static inline unsigned pow5(unsigned a)
443 {
444     return mul(pow4(a), a);
445 }
446
447 static uint8_t gamma_corr(uint8_t in) {
448     unsigned lo, hi = 0xff40, target;
449     int i = 15;
450     in = (in << 2) | (in >> 6);
451     /*  equivalent float code:
452     if (in >= 252)
453         return 253;
454     return round(pow(in / 256.0, 0.8) * 256);
455     */
456     lo = target = in << 8;
457     do {
458         unsigned mid = (lo + hi) >> 1;
459         unsigned pow = pow5(mid);
460         if (pow > target) hi = mid;
461         else lo = mid;
462     } while (--i);
463     return (pow4((lo + hi) >> 1) + 0x80) >> 8;
464 }
465 #else
466 /**
467  * This is a gamma correction that xan3 applies to all palette entries.
468  *
469  * There is a peculiarity, namely that the values are clamped to 253 -
470  * it seems likely that this table was calculated by a buggy fixed-point
471  * implementation, the one above under RUNTIME_GAMMA behaves like this for
472  * example.
473  * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
474  * and thus pow(x, 0.8) is still easy to calculate.
475  * Also, the input values are first rotated to the left by 2.
476  */
477 static const uint8_t gamma_lookup[256] = {
478     0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
479     0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
480     0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
481     0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
482     0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
483     0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
484     0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
485     0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
486     0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
487     0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
488     0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
489     0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
490     0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
491     0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
492     0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
493     0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
494     0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
495     0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
496     0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
497     0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
498     0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
499     0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
500     0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
501     0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
502     0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
503     0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
504     0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
505     0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
506     0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
507     0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
508     0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
509     0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
510 };
511 #endif
512
513 static int xan_decode_frame(AVCodecContext *avctx,
514                             void *data, int *data_size,
515                             AVPacket *avpkt)
516 {
517     const uint8_t *buf = avpkt->data;
518     int ret, buf_size = avpkt->size;
519     XanContext *s = avctx->priv_data;
520
521     if (avctx->codec->id == AV_CODEC_ID_XAN_WC3) {
522         const uint8_t *buf_end = buf + buf_size;
523         int tag = 0;
524         while (buf_end - buf > 8 && tag != VGA__TAG) {
525             unsigned *tmpptr;
526             uint32_t new_pal;
527             int size;
528             int i;
529             tag  = bytestream_get_le32(&buf);
530             size = bytestream_get_be32(&buf);
531             if(size < 0) {
532                 av_log(avctx, AV_LOG_ERROR, "Invalid tag size %d\n", size);
533                 return AVERROR_INVALIDDATA;
534             }
535             size = FFMIN(size, buf_end - buf);
536             switch (tag) {
537             case PALT_TAG:
538                 if (size < PALETTE_SIZE)
539                     return AVERROR_INVALIDDATA;
540                 if (s->palettes_count >= PALETTES_MAX)
541                     return AVERROR_INVALIDDATA;
542                 tmpptr = av_realloc(s->palettes,
543                                     (s->palettes_count + 1) * AVPALETTE_SIZE);
544                 if (!tmpptr)
545                     return AVERROR(ENOMEM);
546                 s->palettes = tmpptr;
547                 tmpptr += s->palettes_count * AVPALETTE_COUNT;
548                 for (i = 0; i < PALETTE_COUNT; i++) {
549 #if RUNTIME_GAMMA
550                     int r = gamma_corr(*buf++);
551                     int g = gamma_corr(*buf++);
552                     int b = gamma_corr(*buf++);
553 #else
554                     int r = gamma_lookup[*buf++];
555                     int g = gamma_lookup[*buf++];
556                     int b = gamma_lookup[*buf++];
557 #endif
558                     *tmpptr++ = (0xFFU << 24) | (r << 16) | (g << 8) | b;
559                 }
560                 s->palettes_count++;
561                 break;
562             case SHOT_TAG:
563                 if (size < 4)
564                     return AVERROR_INVALIDDATA;
565                 new_pal = bytestream_get_le32(&buf);
566                 if (new_pal < s->palettes_count) {
567                     s->cur_palette = new_pal;
568                 } else
569                     av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
570                 break;
571             case VGA__TAG:
572                 break;
573             default:
574                 buf += size;
575                 break;
576             }
577         }
578         buf_size = buf_end - buf;
579     }
580     if (s->palettes_count <= 0) {
581         av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
582         return AVERROR_INVALIDDATA;
583     }
584
585     if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
586         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
587         return ret;
588     }
589     s->current_frame.reference = 3;
590
591     if (!s->frame_size)
592         s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
593
594     memcpy(s->current_frame.data[1],
595            s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
596
597     s->buf = buf;
598     s->size = buf_size;
599
600     if (xan_wc3_decode_frame(s) < 0)
601         return AVERROR_INVALIDDATA;
602
603     /* release the last frame if it is allocated */
604     if (s->last_frame.data[0])
605         avctx->release_buffer(avctx, &s->last_frame);
606
607     *data_size = sizeof(AVFrame);
608     *(AVFrame*)data = s->current_frame;
609
610     /* shuffle frames */
611     FFSWAP(AVFrame, s->current_frame, s->last_frame);
612
613     /* always report that the buffer was completely consumed */
614     return buf_size;
615 }
616
617 static av_cold int xan_decode_end(AVCodecContext *avctx)
618 {
619     XanContext *s = avctx->priv_data;
620
621     /* release the frames */
622     if (s->last_frame.data[0])
623         avctx->release_buffer(avctx, &s->last_frame);
624     if (s->current_frame.data[0])
625         avctx->release_buffer(avctx, &s->current_frame);
626
627     av_freep(&s->buffer1);
628     av_freep(&s->buffer2);
629     av_freep(&s->palettes);
630
631     return 0;
632 }
633
634 AVCodec ff_xan_wc3_decoder = {
635     .name           = "xan_wc3",
636     .type           = AVMEDIA_TYPE_VIDEO,
637     .id             = AV_CODEC_ID_XAN_WC3,
638     .priv_data_size = sizeof(XanContext),
639     .init           = xan_decode_init,
640     .close          = xan_decode_end,
641     .decode         = xan_decode_frame,
642     .capabilities   = CODEC_CAP_DR1,
643     .long_name      = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
644 };