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