]> git.sesse.net Git - ffmpeg/blob - libavcodec/xan.c
Drop DCTELEM typedef
[ffmpeg] / 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 "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
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,
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 = s->current_frame.data[0];
201     stride = s->current_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, int x, int y,
221                                           int pixel_count, int motion_x,
222                                           int motion_y)
223 {
224     int stride;
225     int line_inc;
226     int curframe_index, prevframe_index;
227     int curframe_x, prevframe_x;
228     int width = s->avctx->width;
229     unsigned char *palette_plane, *prev_palette_plane;
230
231     if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
232         x + motion_x < 0 || x + motion_x >= s->avctx->width)
233         return;
234
235     palette_plane = s->current_frame.data[0];
236     prev_palette_plane = s->last_frame.data[0];
237     if (!prev_palette_plane)
238         prev_palette_plane = palette_plane;
239     stride = s->current_frame.linesize[0];
240     line_inc = stride - width;
241     curframe_index = y * stride + x;
242     curframe_x = x;
243     prevframe_index = (y + motion_y) * stride + x + motion_x;
244     prevframe_x = x + motion_x;
245     while (pixel_count &&
246            curframe_index  < s->frame_size &&
247            prevframe_index < s->frame_size) {
248         int count = FFMIN3(pixel_count, width - curframe_x,
249                            width - prevframe_x);
250
251         memcpy(palette_plane + curframe_index,
252                prev_palette_plane + prevframe_index, count);
253         pixel_count     -= count;
254         curframe_index  += count;
255         prevframe_index += count;
256         curframe_x      += count;
257         prevframe_x     += count;
258
259         if (curframe_x >= width) {
260             curframe_index += line_inc;
261             curframe_x = 0;
262         }
263
264         if (prevframe_x >= width) {
265             prevframe_index += line_inc;
266             prevframe_x = 0;
267         }
268     }
269 }
270
271 static int xan_wc3_decode_frame(XanContext *s) {
272
273     int width  = s->avctx->width;
274     int height = s->avctx->height;
275     int total_pixels = width * height;
276     unsigned char opcode;
277     unsigned char flag = 0;
278     int size = 0;
279     int motion_x, motion_y;
280     int x, y;
281
282     unsigned char *opcode_buffer = s->buffer1;
283     unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
284     int opcode_buffer_size = s->buffer1_size;
285     const unsigned char *imagedata_buffer = s->buffer2;
286
287     /* pointers to segments inside the compressed chunk */
288     const unsigned char *huffman_segment;
289     const unsigned char *size_segment;
290     const unsigned char *vector_segment;
291     const unsigned char *imagedata_segment;
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             /* run-based motion compensation from last frame */
397             motion_x = sign_extend(*vector_segment >> 4,  4);
398             motion_y = sign_extend(*vector_segment & 0xF, 4);
399             vector_segment++;
400
401             /* copy a run of pixels from the previous frame */
402             xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
403
404             flag = 0;
405         }
406
407         /* coordinate accounting */
408         total_pixels -= size;
409         y += (x + size) / width;
410         x  = (x + size) % width;
411     }
412     return 0;
413 }
414
415 #if RUNTIME_GAMMA
416 static inline unsigned mul(unsigned a, unsigned b)
417 {
418     return (a * b) >> 16;
419 }
420
421 static inline unsigned pow4(unsigned a)
422 {
423     unsigned square = mul(a, a);
424     return mul(square, square);
425 }
426
427 static inline unsigned pow5(unsigned a)
428 {
429     return mul(pow4(a), a);
430 }
431
432 static uint8_t gamma_corr(uint8_t in) {
433     unsigned lo, hi = 0xff40, target;
434     int i = 15;
435     in = (in << 2) | (in >> 6);
436     /*  equivalent float code:
437     if (in >= 252)
438         return 253;
439     return round(pow(in / 256.0, 0.8) * 256);
440     */
441     lo = target = in << 8;
442     do {
443         unsigned mid = (lo + hi) >> 1;
444         unsigned pow = pow5(mid);
445         if (pow > target) hi = mid;
446         else lo = mid;
447     } while (--i);
448     return (pow4((lo + hi) >> 1) + 0x80) >> 8;
449 }
450 #else
451 /**
452  * This is a gamma correction that xan3 applies to all palette entries.
453  *
454  * There is a peculiarity, namely that the values are clamped to 253 -
455  * it seems likely that this table was calculated by a buggy fixed-point
456  * implementation, the one above under RUNTIME_GAMMA behaves like this for
457  * example.
458  * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
459  * and thus pow(x, 0.8) is still easy to calculate.
460  * Also, the input values are first rotated to the left by 2.
461  */
462 static const uint8_t gamma_lookup[256] = {
463     0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
464     0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
465     0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
466     0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
467     0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
468     0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
469     0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
470     0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
471     0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
472     0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
473     0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
474     0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
475     0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
476     0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
477     0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
478     0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
479     0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
480     0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
481     0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
482     0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
483     0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
484     0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
485     0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
486     0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
487     0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
488     0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
489     0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
490     0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
491     0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
492     0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
493     0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
494     0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
495 };
496 #endif
497
498 static int xan_decode_frame(AVCodecContext *avctx,
499                             void *data, int *got_frame,
500                             AVPacket *avpkt)
501 {
502     const uint8_t *buf = avpkt->data;
503     int ret, buf_size = avpkt->size;
504     XanContext *s = avctx->priv_data;
505     GetByteContext ctx;
506     int tag = 0;
507
508     bytestream2_init(&ctx, buf, buf_size);
509     while (bytestream2_get_bytes_left(&ctx) > 8 && tag != VGA__TAG) {
510         unsigned *tmpptr;
511         uint32_t new_pal;
512         int size;
513         int i;
514         tag  = bytestream2_get_le32(&ctx);
515         size = bytestream2_get_be32(&ctx);
516         size = FFMIN(size, bytestream2_get_bytes_left(&ctx));
517         switch (tag) {
518         case PALT_TAG:
519             if (size < PALETTE_SIZE)
520                 return AVERROR_INVALIDDATA;
521             if (s->palettes_count >= PALETTES_MAX)
522                 return AVERROR_INVALIDDATA;
523             tmpptr = av_realloc(s->palettes,
524                                 (s->palettes_count + 1) * AVPALETTE_SIZE);
525             if (!tmpptr)
526                 return AVERROR(ENOMEM);
527             s->palettes = tmpptr;
528             tmpptr += s->palettes_count * AVPALETTE_COUNT;
529             for (i = 0; i < PALETTE_COUNT; i++) {
530 #if RUNTIME_GAMMA
531                 int r = gamma_corr(bytestream2_get_byteu(&ctx));
532                 int g = gamma_corr(bytestream2_get_byteu(&ctx));
533                 int b = gamma_corr(bytestream2_get_byteu(&ctx));
534 #else
535                 int r = gamma_lookup[bytestream2_get_byteu(&ctx)];
536                 int g = gamma_lookup[bytestream2_get_byteu(&ctx)];
537                 int b = gamma_lookup[bytestream2_get_byteu(&ctx)];
538 #endif
539                 *tmpptr++ = (r << 16) | (g << 8) | b;
540             }
541             s->palettes_count++;
542             break;
543         case SHOT_TAG:
544             if (size < 4)
545                 return AVERROR_INVALIDDATA;
546             new_pal = bytestream2_get_le32(&ctx);
547             if (new_pal < s->palettes_count) {
548                 s->cur_palette = new_pal;
549             } else
550                 av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
551             break;
552         case VGA__TAG:
553             break;
554         default:
555             bytestream2_skip(&ctx, size);
556             break;
557         }
558     }
559     buf_size = bytestream2_get_bytes_left(&ctx);
560
561     if (s->palettes_count <= 0) {
562         av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
563         return AVERROR_INVALIDDATA;
564     }
565
566     if ((ret = ff_get_buffer(avctx, &s->current_frame))) {
567         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
568         return ret;
569     }
570     s->current_frame.reference = 3;
571
572     if (!s->frame_size)
573         s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
574
575     memcpy(s->current_frame.data[1],
576            s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
577
578     s->buf = ctx.buffer;
579     s->size = buf_size;
580
581     if (xan_wc3_decode_frame(s) < 0)
582         return AVERROR_INVALIDDATA;
583
584     /* release the last frame if it is allocated */
585     if (s->last_frame.data[0])
586         avctx->release_buffer(avctx, &s->last_frame);
587
588     *got_frame = 1;
589     *(AVFrame*)data = s->current_frame;
590
591     /* shuffle frames */
592     FFSWAP(AVFrame, s->current_frame, s->last_frame);
593
594     /* always report that the buffer was completely consumed */
595     return buf_size;
596 }
597
598 static av_cold int xan_decode_end(AVCodecContext *avctx)
599 {
600     XanContext *s = avctx->priv_data;
601
602     /* release the frames */
603     if (s->last_frame.data[0])
604         avctx->release_buffer(avctx, &s->last_frame);
605     if (s->current_frame.data[0])
606         avctx->release_buffer(avctx, &s->current_frame);
607
608     av_freep(&s->buffer1);
609     av_freep(&s->buffer2);
610     av_freep(&s->palettes);
611
612     return 0;
613 }
614
615 AVCodec ff_xan_wc3_decoder = {
616     .name           = "xan_wc3",
617     .type           = AVMEDIA_TYPE_VIDEO,
618     .id             = AV_CODEC_ID_XAN_WC3,
619     .priv_data_size = sizeof(XanContext),
620     .init           = xan_decode_init,
621     .close          = xan_decode_end,
622     .decode         = xan_decode_frame,
623     .capabilities   = CODEC_CAP_DR1,
624     .long_name      = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
625 };