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  unsigned char *dest_start = dest;
108  GetBitContext gb;
109 
110  if (ptr_len < 0)
111  return AVERROR_INVALIDDATA;
112 
113  init_get_bits(&gb, ptr, ptr_len * 8);
114 
115  while (val != 0x16) {
116  unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
117  if (idx >= 2 * byte)
118  return -1;
119  val = src[idx];
120 
121  if (val < 0x16) {
122  if (dest >= dest_end)
123  return dest_len;
124  *dest++ = val;
125  val = ival;
126  }
127  }
128 
129  return dest - dest_start;
130 }
131 
137 static void xan_unpack(unsigned char *dest, int dest_len,
138  const unsigned char *src, int src_len)
139 {
140  unsigned char opcode;
141  int size;
142  unsigned char *dest_org = dest;
143  unsigned char *dest_end = dest + dest_len;
144  const unsigned char *src_end = src + src_len;
145 
146  while (dest < dest_end && src < src_end) {
147  opcode = *src++;
148 
149  if (opcode < 0xe0) {
150  int size2, back;
151  if ((opcode & 0x80) == 0) {
152  size = opcode & 3;
153 
154  back = ((opcode & 0x60) << 3) + *src++ + 1;
155  size2 = ((opcode & 0x1c) >> 2) + 3;
156  } else if ((opcode & 0x40) == 0) {
157  size = *src >> 6;
158 
159  back = (bytestream_get_be16(&src) & 0x3fff) + 1;
160  size2 = (opcode & 0x3f) + 4;
161  } else {
162  size = opcode & 3;
163 
164  back = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
165  size2 = ((opcode & 0x0c) << 6) + *src++ + 5;
166  }
167 
168  if (dest_end - dest < size + size2 ||
169  dest + size - dest_org < back ||
170  src_end - src < size)
171  return;
172  memcpy(dest, src, size); dest += size; src += size;
173  av_memcpy_backptr(dest, back, size2);
174  dest += size2;
175  } else {
176  int finish = opcode >= 0xfc;
177  size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
178 
179  if (dest_end - dest < size || src_end - src < size)
180  return;
181  memcpy(dest, src, size); dest += size; src += size;
182  if (finish)
183  return;
184  }
185  }
186 }
187 
188 static inline void xan_wc3_output_pixel_run(XanContext *s,
189  const unsigned char *pixel_buffer, int x, int y, int pixel_count)
190 {
191  int stride;
192  int line_inc;
193  int index;
194  int current_x;
195  int width = s->avctx->width;
196  unsigned char *palette_plane;
197 
198  palette_plane = s->current_frame.data[0];
199  stride = s->current_frame.linesize[0];
200  line_inc = stride - width;
201  index = y * stride + x;
202  current_x = x;
203  while (pixel_count && index < s->frame_size) {
204  int count = FFMIN(pixel_count, width - current_x);
205  memcpy(palette_plane + index, pixel_buffer, count);
206  pixel_count -= count;
207  index += count;
208  pixel_buffer += count;
209  current_x += count;
210 
211  if (current_x >= width) {
212  index += line_inc;
213  current_x = 0;
214  }
215  }
216 }
217 
218 static inline void xan_wc3_copy_pixel_run(XanContext *s, int x, int y,
219  int pixel_count, int motion_x,
220  int motion_y)
221 {
222  int stride;
223  int line_inc;
224  int curframe_index, prevframe_index;
225  int curframe_x, prevframe_x;
226  int width = s->avctx->width;
227  unsigned char *palette_plane, *prev_palette_plane;
228 
229  if (y + motion_y < 0 || y + motion_y >= s->avctx->height ||
230  x + motion_x < 0 || x + motion_x >= s->avctx->width)
231  return;
232 
233  palette_plane = s->current_frame.data[0];
234  prev_palette_plane = s->last_frame.data[0];
235  if (!prev_palette_plane)
236  prev_palette_plane = palette_plane;
237  stride = s->current_frame.linesize[0];
238  line_inc = stride - width;
239  curframe_index = y * stride + x;
240  curframe_x = x;
241  prevframe_index = (y + motion_y) * stride + x + motion_x;
242  prevframe_x = x + motion_x;
243  while (pixel_count &&
244  curframe_index < s->frame_size &&
245  prevframe_index < s->frame_size) {
246  int count = FFMIN3(pixel_count, width - curframe_x,
247  width - prevframe_x);
248 
249  memcpy(palette_plane + curframe_index,
250  prev_palette_plane + prevframe_index, count);
251  pixel_count -= count;
252  curframe_index += count;
253  prevframe_index += count;
254  curframe_x += count;
255  prevframe_x += count;
256 
257  if (curframe_x >= width) {
258  curframe_index += line_inc;
259  curframe_x = 0;
260  }
261 
262  if (prevframe_x >= width) {
263  prevframe_index += line_inc;
264  prevframe_x = 0;
265  }
266  }
267 }
268 
270 
271  int width = s->avctx->width;
272  int height = s->avctx->height;
273  int total_pixels = width * height;
274  unsigned char opcode;
275  unsigned char flag = 0;
276  int size = 0;
277  int motion_x, motion_y;
278  int x, y, ret;
279 
280  unsigned char *opcode_buffer = s->buffer1;
281  unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
282  int opcode_buffer_size = s->buffer1_size;
283  const unsigned char *imagedata_buffer = s->buffer2;
284 
285  /* pointers to segments inside the compressed chunk */
286  const unsigned char *huffman_segment;
287  GetByteContext size_segment;
288  GetByteContext vector_segment;
289  const unsigned char *imagedata_segment;
290  int huffman_offset, size_offset, vector_offset, imagedata_offset,
291  imagedata_size;
292 
293  if (s->size < 8)
294  return AVERROR_INVALIDDATA;
295 
296  huffman_offset = AV_RL16(&s->buf[0]);
297  size_offset = AV_RL16(&s->buf[2]);
298  vector_offset = AV_RL16(&s->buf[4]);
299  imagedata_offset = AV_RL16(&s->buf[6]);
300 
301  if (huffman_offset >= s->size ||
302  size_offset >= s->size ||
303  vector_offset >= s->size ||
304  imagedata_offset >= s->size)
305  return AVERROR_INVALIDDATA;
306 
307  huffman_segment = s->buf + huffman_offset;
308  bytestream2_init(&size_segment, s->buf + size_offset, s->size - size_offset);
309  bytestream2_init(&vector_segment, s->buf + vector_offset, s->size - vector_offset);
310  imagedata_segment = s->buf + imagedata_offset;
311 
312  if ((ret = xan_huffman_decode(opcode_buffer, opcode_buffer_size,
313  huffman_segment, s->size - huffman_offset)) < 0)
314  return AVERROR_INVALIDDATA;
315  opcode_buffer_end = opcode_buffer + ret;
316 
317  if (imagedata_segment[0] == 2) {
319  &imagedata_segment[1], s->size - imagedata_offset - 1);
320  imagedata_size = s->buffer2_size;
321  } else {
322  imagedata_size = s->size - imagedata_offset - 1;
323  imagedata_buffer = &imagedata_segment[1];
324  }
325 
326  /* use the decoded data segments to build the frame */
327  x = y = 0;
328  while (total_pixels && opcode_buffer < opcode_buffer_end) {
329 
330  opcode = *opcode_buffer++;
331  size = 0;
332 
333  switch (opcode) {
334 
335  case 0:
336  flag ^= 1;
337  continue;
338 
339  case 1:
340  case 2:
341  case 3:
342  case 4:
343  case 5:
344  case 6:
345  case 7:
346  case 8:
347  size = opcode;
348  break;
349 
350  case 12:
351  case 13:
352  case 14:
353  case 15:
354  case 16:
355  case 17:
356  case 18:
357  size += (opcode - 10);
358  break;
359 
360  case 9:
361  case 19:
362  size = bytestream2_get_byte(&size_segment);
363  break;
364 
365  case 10:
366  case 20:
367  size = bytestream2_get_be16(&size_segment);
368  break;
369 
370  case 11:
371  case 21:
372  size = bytestream2_get_be24(&size_segment);
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  uint8_t vector = bytestream2_get_byte(&vector_segment);
395  motion_x = sign_extend(vector >> 4, 4);
396  motion_y = sign_extend(vector & 0xF, 4);
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 };