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