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  memset(dst, 0, count);
330  l->zeros_rem -= count;
331  dst += count;
332  }
333 
334  while (dst < end) {
335  i = 0;
336  while (!zero_run && dst + i < end) {
337  i++;
338  if (src + i >= src_end)
339  return AVERROR_INVALIDDATA;
340  zero_run =
341  !(src[i] | (src[i + 1] & mask1) | (src[i + 2] & mask2));
342  }
343  if (zero_run) {
344  zero_run = 0;
345  i += esc_count;
346  memcpy(dst, src, i);
347  dst += i;
348  l->zeros_rem = lag_calc_zero_run(src[i]);
349 
350  src += i + 1;
351  goto output_zeros;
352  } else {
353  memcpy(dst, src, i);
354  src += i;
355  dst += i;
356  }
357  }
358  return src_start - src;
359 }
360 
361 
362 
363 static int lag_decode_arith_plane(LagarithContext *l, uint8_t *dst,
364  int width, int height, int stride,
365  const uint8_t *src, int src_size)
366 {
367  int i = 0;
368  int read = 0;
369  uint32_t length;
370  uint32_t offset = 1;
371  int esc_count = src[0];
372  GetBitContext gb;
373  lag_rac rac;
374  const uint8_t *src_end = src + src_size;
375 
376  rac.avctx = l->avctx;
377  l->zeros = 0;
378 
379  if (esc_count < 4) {
380  length = width * height;
381  if (esc_count && AV_RL32(src + 1) < length) {
382  length = AV_RL32(src + 1);
383  offset += 4;
384  }
385 
386  init_get_bits(&gb, src + offset, src_size * 8);
387 
388  if (lag_read_prob_header(&rac, &gb) < 0)
389  return -1;
390 
391  lag_rac_init(&rac, &gb, length - stride);
392 
393  for (i = 0; i < height; i++)
394  read += lag_decode_line(l, &rac, dst + (i * stride), width,
395  stride, esc_count);
396 
397  if (read > length)
399  "Output more bytes than length (%d of %d)\n", read,
400  length);
401  } else if (esc_count < 8) {
402  esc_count -= 4;
403  if (esc_count > 0) {
404  /* Zero run coding only, no range coding. */
405  for (i = 0; i < height; i++) {
406  int res = lag_decode_zero_run_line(l, dst + (i * stride), src,
407  src_end, width, esc_count);
408  if (res < 0)
409  return res;
410  src += res;
411  }
412  } else {
413  if (src_size < width * height)
414  return AVERROR_INVALIDDATA; // buffer not big enough
415  /* Plane is stored uncompressed */
416  for (i = 0; i < height; i++) {
417  memcpy(dst + (i * stride), src, width);
418  src += width;
419  }
420  }
421  } else if (esc_count == 0xff) {
422  /* Plane is a solid run of given value */
423  for (i = 0; i < height; i++)
424  memset(dst + i * stride, src[1], width);
425  /* Do not apply prediction.
426  Note: memset to 0 above, setting first value to src[1]
427  and applying prediction gives the same result. */
428  return 0;
429  } else {
431  "Invalid zero run escape code! (%#x)\n", esc_count);
432  return -1;
433  }
434 
435  for (i = 0; i < height; i++) {
436  lag_pred_line(l, dst, width, stride, i);
437  dst += stride;
438  }
439 
440  return 0;
441 }
442 
452  void *data, int *data_size, AVPacket *avpkt)
453 {
454  const uint8_t *buf = avpkt->data;
455  int buf_size = avpkt->size;
456  LagarithContext *l = avctx->priv_data;
457  AVFrame *const p = &l->picture;
458  uint8_t frametype = 0;
459  uint32_t offset_gu = 0, offset_bv = 0, offset_ry = 9;
460  int offs[4];
461  uint8_t *srcs[4], *dst;
462  int i, j, planes = 3;
463 
464  AVFrame *picture = data;
465 
466  if (p->data[0])
467  avctx->release_buffer(avctx, p);
468 
469  p->reference = 0;
470  p->key_frame = 1;
471 
472  frametype = buf[0];
473 
474  offset_gu = AV_RL32(buf + 1);
475  offset_bv = AV_RL32(buf + 5);
476 
477  switch (frametype) {
478  case FRAME_SOLID_RGBA:
479  avctx->pix_fmt = PIX_FMT_RGB32;
480 
481  if (avctx->get_buffer(avctx, p) < 0) {
482  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
483  return -1;
484  }
485 
486  dst = p->data[0];
487  for (j = 0; j < avctx->height; j++) {
488  for (i = 0; i < avctx->width; i++)
489  AV_WN32(dst + i * 4, offset_gu);
490  dst += p->linesize[0];
491  }
492  break;
493  case FRAME_ARITH_RGBA:
494  avctx->pix_fmt = PIX_FMT_RGB32;
495  planes = 4;
496  offset_ry += 4;
497  offs[3] = AV_RL32(buf + 9);
498  case FRAME_ARITH_RGB24:
499  if (frametype == FRAME_ARITH_RGB24)
500  avctx->pix_fmt = PIX_FMT_RGB24;
501 
502  if (avctx->get_buffer(avctx, p) < 0) {
503  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
504  return -1;
505  }
506 
507  offs[0] = offset_bv;
508  offs[1] = offset_gu;
509  offs[2] = offset_ry;
510 
511  if (!l->rgb_planes) {
512  l->rgb_stride = FFALIGN(avctx->width, 16);
513  l->rgb_planes = av_malloc(l->rgb_stride * avctx->height * planes);
514  if (!l->rgb_planes) {
515  av_log(avctx, AV_LOG_ERROR, "cannot allocate temporary buffer\n");
516  return AVERROR(ENOMEM);
517  }
518  }
519  for (i = 0; i < planes; i++)
520  srcs[i] = l->rgb_planes + (i + 1) * l->rgb_stride * avctx->height - l->rgb_stride;
521  if (offset_ry >= buf_size ||
522  offset_gu >= buf_size ||
523  offset_bv >= buf_size ||
524  (planes == 4 && offs[3] >= buf_size)) {
525  av_log(avctx, AV_LOG_ERROR,
526  "Invalid frame offsets\n");
527  return AVERROR_INVALIDDATA;
528  }
529  for (i = 0; i < planes; i++)
530  lag_decode_arith_plane(l, srcs[i],
531  avctx->width, avctx->height,
532  -l->rgb_stride, buf + offs[i],
533  buf_size - offs[i]);
534  dst = p->data[0];
535  for (i = 0; i < planes; i++)
536  srcs[i] = l->rgb_planes + i * l->rgb_stride * avctx->height;
537  for (j = 0; j < avctx->height; j++) {
538  for (i = 0; i < avctx->width; i++) {
539  uint8_t r, g, b, a;
540  r = srcs[0][i];
541  g = srcs[1][i];
542  b = srcs[2][i];
543  r += g;
544  b += g;
545  if (frametype == FRAME_ARITH_RGBA) {
546  a = srcs[3][i];
547  AV_WN32(dst + i * 4, MKBETAG(a, r, g, b));
548  } else {
549  dst[i * 3 + 0] = r;
550  dst[i * 3 + 1] = g;
551  dst[i * 3 + 2] = b;
552  }
553  }
554  dst += p->linesize[0];
555  for (i = 0; i < planes; i++)
556  srcs[i] += l->rgb_stride;
557  }
558  break;
559  case FRAME_ARITH_YV12:
560  avctx->pix_fmt = PIX_FMT_YUV420P;
561 
562  if (avctx->get_buffer(avctx, p) < 0) {
563  av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
564  return -1;
565  }
566 
567  if (offset_ry >= buf_size ||
568  offset_gu >= buf_size ||
569  offset_bv >= buf_size) {
570  av_log(avctx, AV_LOG_ERROR,
571  "Invalid frame offsets\n");
572  return AVERROR_INVALIDDATA;
573  }
574 
575  lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height,
576  p->linesize[0], buf + offset_ry,
577  buf_size - offset_ry);
578  lag_decode_arith_plane(l, p->data[2], avctx->width / 2,
579  avctx->height / 2, p->linesize[2],
580  buf + offset_gu, buf_size - offset_gu);
581  lag_decode_arith_plane(l, p->data[1], avctx->width / 2,
582  avctx->height / 2, p->linesize[1],
583  buf + offset_bv, buf_size - offset_bv);
584  break;
585  default:
586  av_log(avctx, AV_LOG_ERROR,
587  "Unsupported Lagarith frame type: %#x\n", frametype);
588  return -1;
589  }
590 
591  *picture = *p;
592  *data_size = sizeof(AVFrame);
593 
594  return buf_size;
595 }
596 
598 {
599  LagarithContext *l = avctx->priv_data;
600  l->avctx = avctx;
601 
602  dsputil_init(&l->dsp, avctx);
603 
604  return 0;
605 }
606 
608 {
609  LagarithContext *l = avctx->priv_data;
610 
611  if (l->picture.data[0])
612  avctx->release_buffer(avctx, &l->picture);
613  av_freep(&l->rgb_planes);
614 
615  return 0;
616 }
617 
619  .name = "lagarith",
620  .type = AVMEDIA_TYPE_VIDEO,
621  .id = CODEC_ID_LAGARITH,
622  .priv_data_size = sizeof(LagarithContext),
626  .capabilities = CODEC_CAP_DR1,
627  .long_name = NULL_IF_CONFIG_SMALL("Lagarith lossless"),
628 };