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