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