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