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 22/** 23 * @file 24 * Lagarith lossless decoder 25 * @author Nathan Caldwell 26 */ 27 28#include "avcodec.h" 29#include "get_bits.h" 30#include "mathops.h" 31#include "dsputil.h" 32#include "lagarithrac.h" 33 34enum LagarithFrameType { 35 FRAME_RAW = 1, /**< uncompressed */ 36 FRAME_U_RGB24 = 2, /**< unaligned RGB24 */ 37 FRAME_ARITH_YUY2 = 3, /**< arithmetic coded YUY2 */ 38 FRAME_ARITH_RGB24 = 4, /**< arithmetic coded RGB24 */ 39 FRAME_SOLID_GRAY = 5, /**< solid grayscale color frame */ 40 FRAME_SOLID_COLOR = 6, /**< solid non-grayscale color frame */ 41 FRAME_OLD_ARITH_RGB = 7, /**< obsolete arithmetic coded RGB (no longer encoded by upstream since version 1.1.0) */ 42 FRAME_ARITH_RGBA = 8, /**< arithmetic coded RGBA */ 43 FRAME_SOLID_RGBA = 9, /**< solid RGBA color frame */ 44 FRAME_ARITH_YV12 = 10, /**< arithmetic coded YV12 */ 45 FRAME_REDUCED_RES = 11, /**< reduced resolution YV12 frame */ 46}; 47 48typedef struct LagarithContext { 49 AVCodecContext *avctx; 50 AVFrame picture; 51 DSPContext dsp; 52 int zeros; /**< number of consecutive zero bytes encountered */ 53 int zeros_rem; /**< number of zero bytes remaining to output */ 54 uint8_t *rgb_planes; 55 int rgb_stride; 56} LagarithContext; 57 58/** 59 * Compute the 52bit mantissa of 1/(double)denom. 60 * This crazy format uses floats in an entropy coder and we have to match x86 61 * rounding exactly, thus ordinary floats aren't portable enough. 62 * @param denom denominator 63 * @return 52bit mantissa 64 * @see softfloat_mul 65 */ 66static 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 77/** 78 * (uint32_t)(x*f), where f has the given mantissa, and exponent 0 79 * Used in combination with softfloat_reciprocal computes x/(double)denom. 80 * @param x 32bit integer factor 81 * @param mantissa mantissa of f with exponent 0 82 * @return 32bit integer value (x*f) 83 * @see softfloat_reciprocal 84 */ 85static 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 96static uint8_t lag_calc_zero_run(int8_t x) 97{ 98 return (x << 1) ^ (x >> 7); 99} 100 101static 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 135static int lag_read_prob_header(lag_rac *rac, GetBitContext *gb) 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 221static 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 245static 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 272static int lag_decode_line(LagarithContext *l, lag_rac *rac, 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 */ 283handle_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 314static 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 326output_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 368static 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) 403 av_log(l->avctx, AV_LOG_WARNING, 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 { 435 av_log(l->avctx, AV_LOG_ERROR, 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 448/** 449 * Decode a frame. 450 * @param avctx codec context 451 * @param data output AVFrame 452 * @param data_size size of output data or 0 if no picture is returned 453 * @param avpkt input packet 454 * @return number of consumed bytes on success or negative if decode fails 455 */ 456static int lag_decode_frame(AVCodecContext *avctx, 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 602static av_cold int lag_decode_init(AVCodecContext *avctx) 603{ 604 LagarithContext *l = avctx->priv_data; 605 l->avctx = avctx; 606 607 dsputil_init(&l->dsp, avctx); 608 609 return 0; 610} 611 612static av_cold int lag_decode_end(AVCodecContext *avctx) 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 623AVCodec ff_lagarith_decoder = { 624 .name = "lagarith", 625 .type = AVMEDIA_TYPE_VIDEO, 626 .id = CODEC_ID_LAGARITH, 627 .priv_data_size = sizeof(LagarithContext), 628 .init = lag_decode_init, 629 .close = lag_decode_end, 630 .decode = lag_decode_frame, 631 .capabilities = CODEC_CAP_DR1, 632 .long_name = NULL_IF_CONFIG_SMALL("Lagarith lossless"), 633}; 634