libavcodec/lagarith.c

   1 /*
   2  * Lagarith lossless decoder
   3  * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg 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  * FFmpeg 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 FFmpeg; 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 libavcodec/lagarith.c
  24  * Lagarith lossless decoder
  25  * @author Nathan Caldwell
  26  *
  27  */
  28
  29 #include "avcodec.h"
  30 #include "get_bits.h"
  31 #include "mathops.h"
  32 #include "lagarith.h"
  33 #include "lagrange.h"
  34
  35 typedef struct LagarithContext {
  36     AVCodecContext *avctx;
  37     AVFrame picture;
  38     int zeros;      /*!< Number of consecutave zero bytes encountered. */
  39     int zeros_rem;  /*!< Number of zero bytes remaining to output. */
  40 } LagarithContext;
  41
  42 static av_cold int lag_decode_init(AVCodecContext *avctx)
  43 {
  44     LagarithContext *l = avctx->priv_data;
  45
  46     l->avctx = avctx;
  47
  48     return 0;
  49 }
  50
  51 static void lag_memset(uint8_t *s, uint8_t c, size_t n, int step)
  52 {
  53     int i;
  54     if (step == 1) {
  55         memset(s, c, n);
  56         return;
  57     }
  58
  59     for (i = 0; i < n * step; i += step)
  60         s[i] = c;
  61 }
  62
  63 static uint8_t *lag_memcpy(uint8_t *dest, const uint8_t *src, size_t n,
  64                            int step)
  65 {
  66     int i;
  67     if (step == 1)
  68         return memcpy(dest, src, n);
  69
  70     for (i = 0; i < n * step; i += step)
  71         dest[i] = src[i];
  72     return dest;
  73 }
  74
  75 static inline int lag_predict(uint8_t *src, int stride, int step)
  76 {
  77     int T  = src[-stride];
  78     int L  = src[-step];
  79     int TL = src[-stride - step];
  80
  81     return mid_pred(T, L, L + T - TL);
  82 }
  83
  84 static uint8_t lag_calc_zero_run(int8_t x)
  85 {
  86 #if 0
  87     x <<= 1;
  88     if (x > 255) return ~x;
  89     return x;
  90 #endif
  91     return (x << 1) ^ (x >> 7);
  92 }
  93
  94 static uint32_t lag_decode_prob(GetBitContext *gb)
  95 {
  96     static const uint8_t series[] = { 1, 2, 3, 5, 8, 13, 21, 34 };
  97     int i       = 0;
  98     int bit     = 0;
  99     int bits    = 0;
 100     int prevbit = 0;
 101     unsigned value = 1;
 102
 103     for (i = 0; !(prevbit && bit); i++) {
 104         prevbit = bit;
 105         bit = get_bits1(gb);
 106         if (bit && !prevbit)
 107             bits += series[i];
 108     }
 109     bits--;
 110     if (bits <= 0)
 111         return 0;
 112     if (bits > 31) {
 113         /* This is most likely an error, just use the final 32 bits */
 114         skip_bits_long(gb, bits - 31);
 115         bits = 31;
 116     }
 117
 118     value  = get_bits_long(gb, bits);
 119     value |= 1 << bits;
 120
 121     return value - 1;
 122 }
 123
 124 static int lag_read_prob_header(lag_rac *rac, GetBitContext *gb)
 125 {
 126     int i, j;
 127     int prob = 0;
 128     double scale_factor = 0;
 129     unsigned cumul_prob = 0;
 130     unsigned cumulative_target = 1;
 131     unsigned scaled_cumul_prob = 0;
 132
 133     rac->prob[0] = 0;
 134     /* Read probabilities from bitstream */
 135     for (i = 1; i < 257; i++) {
 136         rac->prob[i] = lag_decode_prob(gb);
 137         cumul_prob += rac->prob[i];
 138         if (!rac->prob[i]) {
 139             prob = lag_decode_prob(gb);
 140             if (i + prob >= 258)
 141                 prob = 257 - i;
 142             for (j = 0; j < prob; j++)
 143                 rac->prob[++i] = 0;
 144         }
 145     }
 146
 147     /* Scale probabilities so cumulative probability is an even power of 2. */
 148     cumulative_target = 2 << av_log2(cumul_prob-1);
 149
 150     scale_factor = cumulative_target / (double) cumul_prob;
 151
 152     for (i = 1; i < 257; i++) {
 153         rac->prob[i] = (unsigned) (rac->prob[i] * scale_factor);
 154         scaled_cumul_prob += rac->prob[i];
 155     }
 156
 157     scaled_cumul_prob = cumulative_target - scaled_cumul_prob;
 158
 159     if (scaled_cumul_prob > INT_MAX) {
 160         av_log(rac->avctx, AV_LOG_ERROR,
 161                "Scaled cumulative probability is larger than target!");
 162         return -1;
 163     }
 164
 165     for (i = 1; scaled_cumul_prob; i = (i & 0x7f) + 1) {
 166         if (rac->prob[i]) {
 167             rac->prob[i]++;
 168             scaled_cumul_prob--;
 169         }
 170         /* Comment from reference source:
 171          * if (b & 0x80 == 0) {     // order of operations is 'wrong'; it has been left this way
 172          *                          // since the compression change is negligable and fixing it
 173          *                          // breaks backwards compatibilty
 174          *      b =- (signed int)b;
 175          *      b &= 0xFF;
 176          * } else {
 177          *      b++;
 178          *      b &= 0x7f;
 179          * }
 180          */
 181     }
 182
 183     rac->scale = cumulative_target ? av_log2(cumulative_target) : 0;
 184
 185     /* Fill probability array with cumulative probability for each symbol. */
 186     for (i = 1; i < 257; i++)
 187         rac->prob[i] += rac->prob[i - 1];
 188
 189     return 0;
 190 }
 191
 192 static void lag_pred_line(LagarithContext *l, uint8_t *buf,
 193                           int width, int stride, int step, int mode)
 194 {
 195     int i = 0;
 196     int width_scaled = width * step;
 197
 198     if (!mode) {
 199         /* Left prediction only for first line */
 200         for (i = step; i < width_scaled; i += step)
 201             buf[i] += buf[i - step];
 202     } else if (mode == 1) {
 203         /* Second line, left predict first pixel, the rest of the line is median predicted */
 204         /* FIXME: In the case of RGB this pixel is top predicted */
 205         buf[i] += buf[width_scaled - stride - step];
 206         i += step;
 207     } else {
 208         /* Special case for first pixel in a row */
 209         int T = buf[-stride];
 210         /* Left pixel is actually prev_row[width] */
 211         int L = buf[width_scaled - stride - step];
 212         /* Top left is 2 rows back, last pixel */
 213         int TL = buf[width_scaled - (2 * stride) - step];
 214
 215         buf[i] += mid_pred(T, L, L + T - TL);
 216         i += step;
 217     }
 218
 219     while (i < width_scaled) {
 220         buf[i] += lag_predict(buf + i, stride, step);
 221         i += step;
 222     }
 223 }
 224
 225 static int lag_decode_line(LagarithContext *l, lag_rac *rac,
 226                            uint8_t *dst, int width, int stride,
 227                            int step, int esc_count)
 228 {
 229     int i = 0;
 230     int ret = 0;
 231
 232     /* Output any zeros remaining from the previous run */
 233     if (l->zeros_rem) {
 234         int count = FFMIN(l->zeros_rem, width);
 235         lag_memset(dst + i * step, 0, count, step);
 236         i += count;
 237         l->zeros_rem -= count;
 238     }
 239
 240     while (i < width) {
 241
 242         dst[i * step] = lag_get_rac(rac);
 243         ret++;
 244
 245         if (dst[i * step])
 246             l->zeros = 0;
 247         else
 248             l->zeros++;
 249
 250         i++;
 251         if (esc_count && (l->zeros == esc_count)) {
 252             int count;
 253             int index = lag_get_rac(rac);
 254             ret++;
 255
 256             l->zeros = 0;
 257
 258             l->zeros_rem =
 259             count        = lag_calc_zero_run(index);
 260
 261             if (i + count > width)
 262                 count = width - i;
 263             if (!count)
 264                 continue;
 265
 266             lag_memset(dst + i * step, 0, count, step);
 267
 268             i += count;
 269             l->zeros_rem -= count;
 270         }
 271     }
 272     return ret;
 273 }
 274
 275 static int lag_decode_zero_run_line(LagarithContext *l, uint8_t *dst,
 276                                     const uint8_t *src, int width,
 277                                     int step, int esc_count)
 278 {
 279     int i = 0;
 280     int count;
 281     uint8_t zero_run = 1;
 282     const uint8_t *start = src;
 283     uint8_t mask1 = -(esc_count < 2);
 284     uint8_t mask2 = -(esc_count < 3);
 285     uint8_t *end = dst + (width - 2) * step;
 286
 287     if (l->zeros_rem) {
 288         count = l->zeros_rem;
 289         if (count > width)
 290             count = width;
 291         lag_memset(dst, 0, count, step);
 292         l->zeros_rem -= count;
 293         dst += count;
 294     }
 295
 296     while (dst < end) {
 297         i = 0;
 298         while (!zero_run && dst + i * step < end) {
 299             i++;
 300             zero_run =
 301                 (src[i] | (src[i + 1] & mask1) | (src[i + 2] & mask2));
 302         }
 303         if (!zero_run) {
 304             i += esc_count;
 305             lag_memcpy(dst, src, i, step);
 306             dst += i;
 307             l->zeros_rem =
 308             count        = lag_calc_zero_run(src[i]);
 309
 310             if (dst + l->zeros_rem * step > end)
 311                 count = (end - dst) / step;
 312
 313             lag_memset(dst, 0, count, step);
 314             dst += count;
 315             src += i + 1;
 316             l->zeros_rem -= count;
 317         } else {
 318             lag_memcpy(dst, src, i, step);
 319             src += i;
 320         }
 321     }
 322     return start - src;
 323 }
 324
 325
 326
 327 static int lag_decode_arith_plane(LagarithContext *l, uint8_t *dst,
 328                                   int width, int height, int stride,
 329                                   int step, const uint8_t *src,
 330                                   int src_size)
 331 {
 332     int i = 0;
 333     int read = 0;
 334     uint32_t length;
 335     uint32_t offset = 1;
 336     int esc_count = src[0];
 337     GetBitContext gb;
 338     lag_rac rac;
 339
 340     if (esc_count < 4) {
 341         if (esc_count) {
 342             length = AV_RL32(src + 1);
 343             if (length < width * height)
 344                 offset += 4;
 345             else
 346                 length = width * height;
 347         } else
 348             length = width * height;
 349
 350         init_get_bits(&gb, src + offset, src_size * 8);
 351
 352         if (lag_read_prob_header(&rac, &gb) < 0)
 353             return -1;
 354
 355         lag_rac_init(&rac, &gb, length - stride);
 356
 357         for (i = 0; i < height; i++)
 358             read +=
 359                 lag_decode_line(l, &rac, dst + (i * stride), width,
 360                                 stride, step, esc_count);
 361
 362         if (read > length)
 363             av_log(l->avctx, AV_LOG_WARNING,
 364                    "Read more bytes than length (%d of %d)\n", read,
 365                    length);
 366     } else if (esc_count < 8) {
 367         esc_count -= 4;
 368         if (esc_count > 0) {
 369             /* Zero run coding only, no range coding. */
 370             for (i = 0; i < height; i++)
 371                 src +=
 372                     lag_decode_zero_run_line(l, dst + (i * stride),
 373                                              src, width, step, esc_count);
 374         } else {
 375             /* Plane is stored uncompressed */
 376             for (i = 0; i < height; i++) {
 377                 lag_memcpy(dst + (i * stride), src, width, step);
 378                 src += width;
 379             }
 380         }
 381     } else if (esc_count == 0xff) {
 382         /* Plane is a solid run of 0 bytes */
 383         memset(dst, 0, stride * height);
 384     } else {
 385         av_log(l->avctx, AV_LOG_ERROR,
 386                "Invalid zero run escape code! (%#x)", esc_count);
 387         return -1;
 388     }
 389
 390     for (i = 0; i < height; i++) {
 391         lag_pred_line(l, dst, width, stride, step, i);
 392         dst += stride;
 393     }
 394
 395     return 0;
 396 }
 397
 398 /**
 399 * decode a frame
 400 * @param avctx codec context
 401 * @param data output AVFrame
 402 * @param data_size size of output data or 0 if no picture is returned
 403 * @param avpkt input packet
 404 * @return number of consumed bytes on success or negative if decode fails
 405 */
 406 static int lag_decode_frame(AVCodecContext *avctx,
 407                             void *data, int *data_size, AVPacket *avpkt)
 408 {
 409     const uint8_t *buf = avpkt->data;
 410     int buf_size = avpkt->size;
 411     LagarithContext *l = avctx->priv_data;
 412     AVFrame *const p = &l->picture;
 413     uint8_t frametype = 0;
 414     uint32_t offset_gu = 0, offset_bv = 0, offset_ry = 9;
 415
 416     AVFrame *picture = data;
 417
 418     if (p->data[0])
 419         avctx->release_buffer(avctx, p);
 420
 421     p->reference = 0;
 422     p->key_frame = 1;
 423
 424     frametype = buf[0];
 425
 426     offset_gu = AV_RL32(buf + 1);
 427     offset_bv = AV_RL32(buf + 5);
 428
 429     switch (frametype) {
 430     case FRAME_ARITH_YV12:
 431         avctx->pix_fmt = PIX_FMT_YUV420P;
 432
 433         if (avctx->get_buffer(avctx, p) < 0) {
 434             av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 435             return -1;
 436         }
 437
 438         lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height,
 439                                p->linesize[0], 1, buf + offset_ry,
 440                                buf_size);
 441         lag_decode_arith_plane(l, p->data[2], avctx->width / 2,
 442                                avctx->height / 2, p->linesize[2], 1,
 443                                buf + offset_gu, buf_size);
 444         lag_decode_arith_plane(l, p->data[1], avctx->width / 2,
 445                                avctx->height / 2, p->linesize[1], 1,
 446                                buf + offset_bv, buf_size);
 447         break;
 448     default:
 449         av_log(avctx, AV_LOG_ERROR,
 450                "Unsupported Lagarith frame type: %#x\n", frametype);
 451         return -1;
 452     }
 453
 454     *picture = *(AVFrame *) & l->picture;
 455     *data_size = sizeof(AVPicture);
 456
 457     return buf_size;
 458 }
 459
 460 AVCodec lagarith_decoder = {
 461     "lagarith",
 462     CODEC_TYPE_VIDEO,
 463     CODEC_ID_LAGARITH,
 464     sizeof(LagarithContext),
 465     lag_decode_init,
 466     NULL,
 467     NULL,
 468     lag_decode_frame,
 469     CODEC_CAP_DR1,
 470     .long_name = NULL_IF_CONFIG_SMALL("Lagarith"),
 471 };