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