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