lagarith.c
Go to the documentation of this file.
1 /*
2  * Lagarith lossless decoder
3  * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
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 
28 #include "avcodec.h"
29 #include "get_bits.h"
30 #include "mathops.h"
31 #include "dsputil.h"
32 #include "lagarithrac.h"
33 
35  FRAME_RAW = 1,
46 };
47 
48 typedef struct LagarithContext {
52  int zeros;
53  int zeros_rem;
54  uint8_t *rgb_planes;
57 
66 static uint64_t softfloat_reciprocal(uint32_t denom)
67 {
68  int shift = av_log2(denom - 1) + 1;
69  uint64_t ret = (1ULL << 52) / denom;
70  uint64_t err = (1ULL << 52) - ret * denom;
71  ret <<= shift;
72  err <<= shift;
73  err += denom / 2;
74  return ret + err / denom;
75 }
76 
85 static uint32_t softfloat_mul(uint32_t x, uint64_t mantissa)
86 {
87  uint64_t l = x * (mantissa & 0xffffffff);
88  uint64_t h = x * (mantissa >> 32);
89  h += l >> 32;
90  l &= 0xffffffff;
91  l += 1 << av_log2(h >> 21);
92  h += l >> 32;
93  return h >> 20;
94 }
95 
96 static uint8_t lag_calc_zero_run(int8_t x)
97 {
98  return (x << 1) ^ (x >> 7);
99 }
100 
101 static int lag_decode_prob(GetBitContext *gb, uint32_t *value)
102 {
103  static const uint8_t series[] = { 1, 2, 3, 5, 8, 13, 21 };
104  int i;
105  int bit = 0;
106  int bits = 0;
107  int prevbit = 0;
108  unsigned val;
109 
110  for (i = 0; i < 7; i++) {
111  if (prevbit && bit)
112  break;
113  prevbit = bit;
114  bit = get_bits1(gb);
115  if (bit && !prevbit)
116  bits += series[i];
117  }
118  bits--;
119  if (bits < 0 || bits > 31) {
120  *value = 0;
121  return -1;
122  } else if (bits == 0) {
123  *value = 0;
124  return 0;
125  }
126 
127  val = get_bits_long(gb, bits);
128  val |= 1 << bits;
129 
130  *value = val - 1;
131 
132  return 0;
133 }
134 
136 {
137  int i, j, scale_factor;
138  unsigned prob, cumulative_target;
139  unsigned cumul_prob = 0;
140  unsigned scaled_cumul_prob = 0;
141 
142  rac->prob[0] = 0;
143  rac->prob[257] = UINT_MAX;
144  /* Read probabilities from bitstream */
145  for (i = 1; i < 257; i++) {
146  if (lag_decode_prob(gb, &rac->prob[i]) < 0) {
147  av_log(rac->avctx, AV_LOG_ERROR, "Invalid probability encountered.\n");
148  return -1;
149  }
150  if ((uint64_t)cumul_prob + rac->prob[i] > UINT_MAX) {
151  av_log(rac->avctx, AV_LOG_ERROR, "Integer overflow encountered in cumulative probability calculation.\n");
152  return -1;
153  }
154  cumul_prob += rac->prob[i];
155  if (!rac->prob[i]) {
156  if (lag_decode_prob(gb, &prob)) {
157  av_log(rac->avctx, AV_LOG_ERROR, "Invalid probability run encountered.\n");
158  return -1;
159  }
160  if (prob > 257 - i)
161  prob = 257 - i;
162  for (j = 0; j < prob; j++)
163  rac->prob[++i] = 0;
164  }
165  }
166 
167  if (!cumul_prob) {
168  av_log(rac->avctx, AV_LOG_ERROR, "All probabilities are 0!\n");
169  return -1;
170  }
171 
172  /* Scale probabilities so cumulative probability is an even power of 2. */
173  scale_factor = av_log2(cumul_prob);
174 
175  if (cumul_prob & (cumul_prob - 1)) {
176  uint64_t mul = softfloat_reciprocal(cumul_prob);
177  for (i = 1; i < 257; i++) {
178  rac->prob[i] = softfloat_mul(rac->prob[i], mul);
179  scaled_cumul_prob += rac->prob[i];
180  }
181 
182  scale_factor++;
183  cumulative_target = 1 << scale_factor;
184 
185  if (scaled_cumul_prob > cumulative_target) {
186  av_log(rac->avctx, AV_LOG_ERROR,
187  "Scaled probabilities are larger than target!\n");
188  return -1;
189  }
190 
191  scaled_cumul_prob = cumulative_target - scaled_cumul_prob;
192 
193  for (i = 1; scaled_cumul_prob; i = (i & 0x7f) + 1) {
194  if (rac->prob[i]) {
195  rac->prob[i]++;
196  scaled_cumul_prob--;
197  }
198  /* Comment from reference source:
199  * if (b & 0x80 == 0) { // order of operations is 'wrong'; it has been left this way
200  * // since the compression change is negligable and fixing it
201  * // breaks backwards compatibilty
202  * b =- (signed int)b;
203  * b &= 0xFF;
204  * } else {
205  * b++;
206  * b &= 0x7f;
207  * }
208  */
209  }
210  }
211 
212  rac->scale = scale_factor;
213 
214  /* Fill probability array with cumulative probability for each symbol. */
215  for (i = 1; i < 257; i++)
216  rac->prob[i] += rac->prob[i - 1];
217 
218  return 0;
219 }
220 
221 static void add_lag_median_prediction(uint8_t *dst, uint8_t *src1,
222  uint8_t *diff, int w, int *left,
223  int *left_top)
224 {
225  /* This is almost identical to add_hfyu_median_prediction in dsputil.h.
226  * However the &0xFF on the gradient predictor yealds incorrect output
227  * for lagarith.
228  */
229  int i;
230  uint8_t l, lt;
231 
232  l = *left;
233  lt = *left_top;
234 
235  for (i = 0; i < w; i++) {
236  l = mid_pred(l, src1[i], l + src1[i] - lt) + diff[i];
237  lt = src1[i];
238  dst[i] = l;
239  }
240 
241  *left = l;
242  *left_top = lt;
243 }
244 
245 static void lag_pred_line(LagarithContext *l, uint8_t *buf,
246  int width, int stride, int line)
247 {
248  int L, TL;
249 
250  if (!line) {
251  /* Left prediction only for first line */
252  L = l->dsp.add_hfyu_left_prediction(buf + 1, buf + 1,
253  width - 1, buf[0]);
254  } else {
255  /* Left pixel is actually prev_row[width] */
256  L = buf[width - stride - 1];
257 
258  if (line == 1) {
259  /* Second line, left predict first pixel, the rest of the line is median predicted
260  * NOTE: In the case of RGB this pixel is top predicted */
261  TL = l->avctx->pix_fmt == PIX_FMT_YUV420P ? buf[-stride] : L;
262  } else {
263  /* Top left is 2 rows back, last pixel */
264  TL = buf[width - (2 * stride) - 1];
265  }
266 
267  add_lag_median_prediction(buf, buf - stride, buf,
268  width, &L, &TL);
269  }
270 }
271 
273  uint8_t *dst, int width, int stride,
274  int esc_count)
275 {
276  int i = 0;
277  int ret = 0;
278 
279  if (!esc_count)
280  esc_count = -1;
281 
282  /* Output any zeros remaining from the previous run */
283 handle_zeros:
284  if (l->zeros_rem) {
285  int count = FFMIN(l->zeros_rem, width - i);
286  memset(dst + i, 0, count);
287  i += count;
288  l->zeros_rem -= count;
289  }
290 
291  while (i < width) {
292  dst[i] = lag_get_rac(rac);
293  ret++;
294 
295  if (dst[i])
296  l->zeros = 0;
297  else
298  l->zeros++;
299 
300  i++;
301  if (l->zeros == esc_count) {
302  int index = lag_get_rac(rac);
303  ret++;
304 
305  l->zeros = 0;
306 
307  l->zeros_rem = lag_calc_zero_run(index);
308  goto handle_zeros;
309  }
310  }
311  return ret;
312 }
313 
314 static int lag_decode_zero_run_line(LagarithContext *l, uint8_t *dst,
315  const uint8_t *src, const uint8_t *src_end,
316  int width, int esc_count)
317 {
318  int i = 0;
319  int count;
320  uint8_t zero_run = 0;
321  const uint8_t *src_start = src;
322  uint8_t mask1 = -(esc_count < 2);
323  uint8_t mask2 = -(esc_count < 3);
324  uint8_t *end = dst + (width - 2);
325 
326 output_zeros:
327  if (l->zeros_rem) {
328  count = FFMIN(l->zeros_rem, width - i);
329  if (end - dst < count) {
330  av_log(l->avctx, AV_LOG_ERROR, "Too many zeros remaining.\n");
331  return AVERROR_INVALIDDATA;
332  }
333 
334  memset(dst, 0, count);
335  l->zeros_rem -= count;
336  dst += count;
337  }
338 
339  while (dst < end) {
340  i = 0;
341  while (!zero_run && dst + i < end) {
342  i++;
343  if (src + i >= src_end)
344  return AVERROR_INVALIDDATA;
345  zero_run =
346  !(src[i] | (src[i + 1] & mask1) | (src[i + 2] & mask2));
347  }
348  if (zero_run) {
349  zero_run = 0;
350  i += esc_count;
351  memcpy(dst, src, i);
352  dst += i;
353  l->zeros_rem = lag_calc_zero_run(src[i]);
354 
355  src += i + 1;
356  goto output_zeros;
357  } else {
358  memcpy(dst, src, i);
359  src += i;
360  dst += i;
361  }
362  }
363  return src_start - src;
364 }
365 
366 
367 
368 static int lag_decode_arith_plane(LagarithContext *l, uint8_t *dst,
369  int width, int height, int stride,
370  const uint8_t *src, int src_size)
371 {
372  int i = 0;
373  int read = 0;
374  uint32_t length;
375  uint32_t offset = 1;
376  int esc_count = src[0];
377  GetBitContext gb;
378  lag_rac rac;
379  const uint8_t *src_end = src + src_size;
380 
381  rac.avctx = l->avctx;
382  l->zeros = 0;
383 
384  if (esc_count < 4) {
385  length = width * height;
386  if (esc_count && AV_RL32(src + 1) < length) {
387  length = AV_RL32(src + 1);
388  offset += 4;
389  }
390 
391  init_get_bits(&gb, src + offset, src_size * 8);
392 
393  if (lag_read_prob_header(&rac, &gb) < 0)
394  return -1;
395 
396  lag_rac_init(&rac, &gb, length - stride);
397 
398  for (i = 0; i < height; i++)
399  read += lag_decode_line(l, &rac, dst + (i * stride), width,
400  stride, esc_count);
401 
402  if (read > length)
404  "Output more bytes than length (%d of %d)\n", read,
405  length);
406  } else if (esc_count < 8) {
407  esc_count -= 4;
408  if (esc_count > 0) {
409  /* Zero run coding only, no range coding. */
410  for (i = 0; i < height; i++) {
411  int res = lag_decode_zero_run_line(l, dst + (i * stride), src,
412  src_end, width, esc_count);
413  if (res < 0)
414  return res;
415  src += res;
416  }
417  } else {
418  if (src_size < width * height)
419  return AVERROR_INVALIDDATA; // buffer not big enough
420  /* Plane is stored uncompressed */
421  for (i = 0; i < height; i++) {
422  memcpy(dst + (i * stride), src, width);
423  src += width;
424  }
425  }
426  } else if (esc_count == 0xff) {
427  /* Plane is a solid run of given value */
428  for (i = 0; i < height; i++)
429  memset(dst + i * stride, src[1], width);
430  /* Do not apply prediction.
431  Note: memset to 0 above, setting first value to src[1]
432  and applying prediction gives the same result. */
433  return 0;
434  } else {
436  "Invalid zero run escape code! (%#x)\n", esc_count);
437  return -1;
438  }
439 
440  for (i = 0; i < height; i++) {
441  lag_pred_line(l, dst, width, stride, i);
442  dst += stride;
443  }
444 
445  return 0;
446 }
447 
457  void *data, int *data_size, AVPacket *avpkt)
458 {
459  const uint8_t *buf = avpkt->data;
460  int buf_size = avpkt->size;
461  LagarithContext *l = avctx->priv_data;
462  AVFrame *const p = &l->picture;
463  uint8_t frametype = 0;
464  uint32_t offset_gu = 0, offset_bv = 0, offset_ry = 9;
465  int offs[4];
466  uint8_t *srcs[4], *dst;
467  int i, j, planes = 3;
468 
469  AVFrame *picture = data;
470 
471  if (p->data[0])
472  avctx->release_buffer(avctx, p);
473 
474  p->reference = 0;
475  p->key_frame = 1;
476 
477  frametype = buf[0];
478 
479  offset_gu = AV_RL32(buf + 1);
480  offset_bv = AV_RL32(buf + 5);
481 
482  switch (frametype) {
483  case FRAME_SOLID_RGBA:
484  avctx->pix_fmt = PIX_FMT_RGB32;
485 
486  if (avctx->get_buffer(avctx, p) < 0) {
487  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
488  return -1;
489  }
490 
491  dst = p->data[0];
492  for (j = 0; j < avctx->height; j++) {
493  for (i = 0; i < avctx->width; i++)
494  AV_WN32(dst + i * 4, offset_gu);
495  dst += p->linesize[0];
496  }
497  break;
498  case FRAME_ARITH_RGBA:
499  avctx->pix_fmt = PIX_FMT_RGB32;
500  planes = 4;
501  offset_ry += 4;
502  offs[3] = AV_RL32(buf + 9);
503  case FRAME_ARITH_RGB24:
504  if (frametype == FRAME_ARITH_RGB24)
505  avctx->pix_fmt = PIX_FMT_RGB24;
506 
507  if (avctx->get_buffer(avctx, p) < 0) {
508  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
509  return -1;
510  }
511 
512  offs[0] = offset_bv;
513  offs[1] = offset_gu;
514  offs[2] = offset_ry;
515 
516  if (!l->rgb_planes) {
517  l->rgb_stride = FFALIGN(avctx->width, 16);
518  l->rgb_planes = av_malloc(l->rgb_stride * avctx->height * planes);
519  if (!l->rgb_planes) {
520  av_log(avctx, AV_LOG_ERROR, "cannot allocate temporary buffer\n");
521  return AVERROR(ENOMEM);
522  }
523  }
524  for (i = 0; i < planes; i++)
525  srcs[i] = l->rgb_planes + (i + 1) * l->rgb_stride * avctx->height - l->rgb_stride;
526  if (offset_ry >= buf_size ||
527  offset_gu >= buf_size ||
528  offset_bv >= buf_size ||
529  (planes == 4 && offs[3] >= buf_size)) {
530  av_log(avctx, AV_LOG_ERROR,
531  "Invalid frame offsets\n");
532  return AVERROR_INVALIDDATA;
533  }
534  for (i = 0; i < planes; i++)
535  lag_decode_arith_plane(l, srcs[i],
536  avctx->width, avctx->height,
537  -l->rgb_stride, buf + offs[i],
538  buf_size - offs[i]);
539  dst = p->data[0];
540  for (i = 0; i < planes; i++)
541  srcs[i] = l->rgb_planes + i * l->rgb_stride * avctx->height;
542  for (j = 0; j < avctx->height; j++) {
543  for (i = 0; i < avctx->width; i++) {
544  uint8_t r, g, b, a;
545  r = srcs[0][i];
546  g = srcs[1][i];
547  b = srcs[2][i];
548  r += g;
549  b += g;
550  if (frametype == FRAME_ARITH_RGBA) {
551  a = srcs[3][i];
552  AV_WN32(dst + i * 4, MKBETAG(a, r, g, b));
553  } else {
554  dst[i * 3 + 0] = r;
555  dst[i * 3 + 1] = g;
556  dst[i * 3 + 2] = b;
557  }
558  }
559  dst += p->linesize[0];
560  for (i = 0; i < planes; i++)
561  srcs[i] += l->rgb_stride;
562  }
563  break;
564  case FRAME_ARITH_YV12:
565  avctx->pix_fmt = PIX_FMT_YUV420P;
566 
567  if (avctx->get_buffer(avctx, p) < 0) {
568  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
569  return -1;
570  }
571 
572  if (offset_ry >= buf_size ||
573  offset_gu >= buf_size ||
574  offset_bv >= buf_size) {
575  av_log(avctx, AV_LOG_ERROR,
576  "Invalid frame offsets\n");
577  return AVERROR_INVALIDDATA;
578  }
579 
580  lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height,
581  p->linesize[0], buf + offset_ry,
582  buf_size - offset_ry);
583  lag_decode_arith_plane(l, p->data[2], avctx->width / 2,
584  avctx->height / 2, p->linesize[2],
585  buf + offset_gu, buf_size - offset_gu);
586  lag_decode_arith_plane(l, p->data[1], avctx->width / 2,
587  avctx->height / 2, p->linesize[1],
588  buf + offset_bv, buf_size - offset_bv);
589  break;
590  default:
591  av_log(avctx, AV_LOG_ERROR,
592  "Unsupported Lagarith frame type: %#x\n", frametype);
593  return -1;
594  }
595 
596  *picture = *p;
597  *data_size = sizeof(AVFrame);
598 
599  return buf_size;
600 }
601 
603 {
604  LagarithContext *l = avctx->priv_data;
605  l->avctx = avctx;
606 
607  dsputil_init(&l->dsp, avctx);
608 
609  return 0;
610 }
611 
613 {
614  LagarithContext *l = avctx->priv_data;
615 
616  if (l->picture.data[0])
617  avctx->release_buffer(avctx, &l->picture);
618  av_freep(&l->rgb_planes);
619 
620  return 0;
621 }
622 
624  .name = "lagarith",
625  .type = AVMEDIA_TYPE_VIDEO,
626  .id = CODEC_ID_LAGARITH,
627  .priv_data_size = sizeof(LagarithContext),
631  .capabilities = CODEC_CAP_DR1,
632  .long_name = NULL_IF_CONFIG_SMALL("Lagarith lossless"),
633 };