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