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