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 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 
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 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 
57 
58  const unsigned char *buf;
59  int size;
60 
61  /* scratch space */
62  unsigned char *buffer1;
64  unsigned char *buffer2;
66 
67  unsigned *palettes;
70 
72 
73 } XanContext;
74 
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;
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 
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 
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) {
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 
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 
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],
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 */
590 
591  /* always report that the buffer was completely consumed */
592  return buf_size;
593 }
594 
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 
613  .name = "xan_wc3",
614  .type = AVMEDIA_TYPE_VIDEO,
615  .id = CODEC_ID_XAN_WC3,
616  .priv_data_size = sizeof(XanContext),
620  .capabilities = CODEC_CAP_DR1,
621  .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
622 };