libavcodec/lagarith.c

   1 /*
   2  * Lagarith Decoder
   3  * Copyright (c) 2009 Nathan Caldwell
   4  * Copyright (c) 2009 David Conrad
   5  *
   6  * This file is part of FFmpeg.
   7  *
   8  * FFmpeg is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * FFmpeg is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with FFmpeg; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 /**
  24  * @file libavcodec/lagarith.c
  25  * Lagarith Lossless Decoder
  26  * @author Nathan Caldwell
  27  * @author David Conrad
  28  *
  29  */
  30
  31 #include "avcodec.h"
  32 #include "lagarith.h"
  33 #include "libavutil/internal.h"
  34 #include "get_bits.h"
  35 #include "mathops.h"
  36
  37
  38
  39 typedef struct lag_rac {
  40     AVCodecContext *avctx;
  41     unsigned low;
  42     unsigned range;
  43     unsigned scale;
  44     unsigned hash_shift;
  45
  46     uint8_t *bytestream_start;
  47     uint8_t *bytestream;
  48     uint8_t *bytestream_end;
  49
  50     int prob[257];
  51     int range_hash[256];
  52 } lag_rac;
  53
  54 /**
  55 * local variable storage
  56 */
  57 typedef struct LagarithContext{
  58     AVCodecContext *avctx;
  59     AVFrame picture;
  60     int i_zeros;
  61     int i_zeros_rem;
  62     int i_frame;
  63 } LagarithContext;
  64
  65 /**
  66 * initializes decoder
  67 * @param avctx codec context
  68 * @return 0 on success or negative if fails
  69 */
  70 static av_cold int lag_decode_init(AVCodecContext *avctx)
  71 {
  72     LagarithContext *p_ctx = avctx->priv_data;
  73
  74     avctx->pix_fmt= PIX_FMT_NONE;
  75
  76     p_ctx->avctx = avctx;
  77
  78     av_log_set_level(AV_LOG_DEBUG);
  79
  80     return 0;
  81 }
  82
  83 static void lag_rac_init(lag_rac *l, GetBitContext *gb, int length)
  84 {
  85     /* According to reference decoder "1st byte is garbage" */
  86 //    skip_bits(gb, 8);
  87     align_get_bits(gb);
  88     l->bytestream_start =
  89     l->bytestream       = gb->buffer + get_bits_count(gb)/8;
  90     l->bytestream_end   = l->bytestream_start + length;
  91
  92     l->range = 0x80;
  93     l->low = *l->bytestream >> 1;
  94     l->hash_shift = FFMAX(l->scale-8, 0);
  95
  96 /*
  97     for (i = 0, j = 0; i < 257; i++) {
  98         unsigned r = i << l->hash_shift;
  99         while (l->prob[j + 1] <= r)
 100             j++;
 101         l->range_hash[i] = j;
 102     }
 103 */
 104 }
 105
 106 /* TODO: Optimize */
 107 static inline void lag_rac_refill(struct lag_rac *l)
 108 {
 109     while (l->range <= 0x800000) {
 110         l->low   <<= 8;
 111         l->range <<= 8;
 112         l->low |= 0xff & (l->bytestream[0] << 7 | l->bytestream[1] >> 1);
 113         l->bytestream++;
 114     }
 115 }
 116
 117 /* TODO: Optimize */
 118 // decodes a byte
 119 static inline int lag_get_rac(struct lag_rac *l)
 120 {
 121     unsigned range_scaled, low_scaled;
 122     int val = 0;
 123
 124     lag_rac_refill(l);
 125
 126     range_scaled = l->range >> l->scale;
 127     low_scaled = l->low / range_scaled;
 128
 129     if (low_scaled < l->prob[255]) {
 130 /*        val = l->range_hash[low_scaled >> l->hash_shift];     */
 131         val=0;
 132         while (l->prob[val+1] <= low_scaled)
 133             val++;
 134
 135         l->low  -= range_scaled * l->prob[val];
 136         l->range = range_scaled * (l->prob[val+1] - l->prob[val]);
 137     } else {
 138         val = 255;
 139         l->low   -= range_scaled * l->prob[255];
 140         l->range -= range_scaled * l->prob[255];
 141     }
 142     return val;
 143 }
 144
 145 void lag_memset(uint8_t *s, uint8_t c, size_t n, int i_step)
 146 {
 147     if(n == 0) return;
 148     if(i_step == 1) {
 149         memset(s, c, n);
 150         return;
 151     }
 152
 153     for(int i=0; i < n*i_step; i+=i_step)
 154         s[i] = c;
 155     return;
 156 }
 157
 158 static inline int lag_predict(uint8_t *p_src, int i_stride, int i_step)
 159 {
 160     int T  = p_src[-i_stride];
 161     int L  = p_src[-i_step];
 162     int TL = p_src[-i_stride - i_step];
 163
 164     return mid_pred( T, L, L + T - TL);
 165 }
 166
 167 static uint32_t lag_decode_prob(GetBitContext *p_gb)
 168 {
 169         unsigned int bit=0;
 170         unsigned int series[]={1,2,3,5,8,13,21,34};
 171         unsigned int prevbit=0;
 172         unsigned int bits=0;
 173         unsigned int i=0;
 174         unsigned int value=1;
 175
 176     for( i=0 ; !( prevbit && bit ); i++)
 177     {
 178         prevbit = bit;
 179         bit = get_bits1(p_gb);
 180                 if ( bit && !prevbit )
 181                         bits+=series[i];
 182     }
 183     bits--;
 184     if (bits == 0) return 0;
 185
 186     value = get_bits_long(p_gb, bits);
 187     value |= 1 << bits;
 188
 189     return value-1;
 190 }
 191
 192 /* Fast round up to least power of 2 >= to x */
 193 static inline uint32_t clp2(uint32_t x)
 194 {
 195     x--;
 196     x |= (x >> 1);
 197     x |= (x >> 2);
 198     x |= (x >> 4);
 199     x |= (x >> 8);
 200     x |= (x >> 16);
 201     return x+1;
 202 }
 203
 204 static uint32_t lag_read_prob_header(lag_rac *p_rac, GetBitContext *p_gb)
 205 {
 206     unsigned int freq = 0;
 207     unsigned int i,j;
 208     unsigned int cumul_prob = 0;
 209     unsigned int temp = 1;
 210     double scale_factor = 0;
 211     unsigned int scaled_cumul_prob = 0;
 212
 213     p_rac->prob[0] = 0;
 214     /* Read probabilities from bitstream */
 215     for(i=1; i<257; i++) {
 216         p_rac->prob[i] = lag_decode_prob(p_gb);
 217         cumul_prob += p_rac->prob[i];
 218         if(p_rac->prob[i] == 0) {
 219             freq = lag_decode_prob(p_gb);
 220             if(i+freq >= 258)
 221                 freq = 257-i;
 222             for(j=0; j < freq; j++)
 223                 p_rac->prob[++i] = 0;
 224         }
 225     }
 226
 227     /* Scale probabilities so cumulative probability is a power of 2. */
 228     temp = clp2(cumul_prob);
 229
 230     scale_factor = temp/(double)cumul_prob;
 231
 232     for(i=1; i<257; i++)
 233     {
 234         p_rac->prob[i] = (unsigned int)(p_rac->prob[i] * scale_factor);
 235         scaled_cumul_prob += p_rac->prob[i];
 236     }
 237
 238     scaled_cumul_prob = temp - scaled_cumul_prob;
 239
 240     if ( (signed int)scaled_cumul_prob < 0 ){
 241         /* TODO
 242          * This should never happen an any real situation.
 243          */
 244     }
 245
 246     i=0;
 247     while(scaled_cumul_prob)
 248     {
 249         if( p_rac->prob[i+1] ) {
 250             p_rac->prob[i+1]++;
 251             scaled_cumul_prob--;
 252         }
 253
 254         /* Comment from reference source:
 255                  * if ( b&0x80==0 ){    // order of operations is 'wrong'; it has been left this way
 256                  *                                      // since the compression change is negligable and fixing it
 257                  *                                      // breaks backwards compatibilty
 258                  *      b=-(signed int)b;
 259                  *      b&=0xFF;
 260                  * } else{
 261                  */
 262
 263         i++;
 264         i &= 0x7f;
 265     }
 266
 267     for( i=0; temp; i++)
 268         temp >>= 1;
 269
 270     p_rac->scale = i-1;
 271
 272     /* Fill probability array with cumulative probability for each symbol. */
 273     for( i=1; i<257; i++ )
 274         p_rac->prob[i] += p_rac->prob[i-1];
 275
 276     return 0;
 277 }
 278
 279 static void lag_pred_line(LagarithContext *l, uint8_t *p_buf, int i_width, int i_stride, int i_step, int i_mode)
 280 {
 281     int i=0;
 282     int width_scaled = i_width * i_step;
 283
 284     if(i_mode == 0) {
 285         /* Left prediction only for first line */
 286         for(i = i_step; i < width_scaled; i+=i_step)
 287             p_buf[i] += p_buf[i-i_step];
 288     } else if(i_mode == 1) {
 289         /* Second line, left predict first pixel, the rest of the line is median predicted */
 290         /* FIXME: Can also be top predicted */
 291         p_buf[i] += p_buf[width_scaled-i_stride-i_step];
 292         i += i_step;
 293     } else {
 294         /* Special case for first pixel in a row */
 295         int T  = p_buf[-i_stride];
 296         /* Left pixel is actually prev_row[width] */
 297         int L  = p_buf[width_scaled-i_stride-i_step];
 298         /* Top left is 2 rows back, last pixel */
 299         int TL = p_buf[width_scaled-(2*i_stride)-i_step];
 300
 301         p_buf[i] += mid_pred( T, L, L + T - TL);
 302         i += i_step;
 303     }
 304
 305     while( i < width_scaled ) {
 306         p_buf[i] += lag_predict(p_buf+i, i_stride, i_step);
 307         i += i_step;
 308     }
 309
 310
 311     return;
 312 }
 313
 314 static int lag_decode_line(LagarithContext *l, lag_rac *rac, uint8_t *p_dst, int i_width, int i_stride,
 315                             int i_step, int i_esc_count)
 316 {
 317     int i = 0;
 318     int ret = 0;
 319     int width_scaled = i_width * i_step;
 320
 321     /* Output any zeros remaining from the previous run */
 322     if(l->i_zeros_rem)
 323     {
 324         int count = l->i_zeros_rem;
 325         if(l->i_zeros_rem > i_width)
 326             count = i_width;
 327         lag_memset(p_dst+i, 0, count, i_step);
 328         i += count*i_step;
 329         l->i_zeros_rem -= count;
 330     }
 331
 332     while(i < width_scaled)
 333     {
 334
 335         p_dst[i] = lag_get_rac(rac);
 336         ret++;
 337
 338         if(p_dst[i])
 339             l->i_zeros = 0;
 340         else
 341             l->i_zeros++;
 342
 343         i+=i_step;
 344         if(i_esc_count && (l->i_zeros == i_esc_count))
 345         {
 346             int count;
 347             int index = lag_get_rac(rac);
 348             ret++;
 349
 350             l->i_zeros = 0;
 351
 352             l->i_zeros_rem =
 353                 count = run_table[index];
 354
 355             if(i+count*i_step > width_scaled)
 356                 count = (width_scaled - i)/i_step;
 357
 358             lag_memset(p_dst+i, 0, count, i_step);
 359             i += count*i_step;
 360             l->i_zeros_rem -= count;
 361         }
 362     }
 363     return ret;
 364 }
 365
 366 static int lag_decode_arith_plane(LagarithContext *l, uint8_t *p_dst, int i_width, int i_height, int i_stride,
 367                                   int i_step, const uint8_t *p_src, int i_src, int b_obsolete)
 368 {
 369     int esc_count = p_src[0];
 370     int i=0;
 371     int read = 0;
 372     uint32_t offset = 1;
 373     uint32_t length;
 374     GetBitContext gb;
 375     lag_rac rac;
 376
 377     rac.avctx = l->avctx;
 378
 379     if (esc_count < 4)
 380     {
 381         if(esc_count != 0)
 382         {
 383             length = *(const uint32_t*)(p_src+1);
 384             if(length < i_width * i_height)
 385                 offset += 4;
 386             else
 387                 length = i_width * i_height;
 388         }
 389         else
 390             length = i_width * i_height;
 391
 392         init_get_bits(&gb, p_src+offset, i_src*8);
 393
 394         offset += lag_read_prob_header(&rac, &gb);
 395
 396         lag_rac_init(&rac, &gb, length-i_stride);
 397
 398         for(i = 0; i < i_height; i++)
 399         {
 400             read += lag_decode_line(l, &rac, p_dst, i_width, i_stride, i_step, esc_count);
 401             lag_pred_line(l, p_dst, i_width, i_stride, i_step, i);
 402             p_dst += i_stride;
 403         }
 404
 405         if(read > length)
 406             av_log(l->avctx, AV_LOG_WARNING, "Read more bytes than length (%d of %d)\n", read, length);
 407     } else {
 408         /* TODO */
 409         av_log(l->avctx, AV_LOG_ERROR, "Unhandled zero run escape code! (%#x)", esc_count);
 410         return -1;
 411     }
 412
 413     return 0;
 414 }
 415
 416 /**
 417 * decode a frame
 418 * @param avctx codec context
 419 * @param data output AVFrame
 420 * @param data_size size of output data or 0 if no picture is returned
 421 * @param avpkt input packet
 422 * @return number of consumed bytes on success or negative if decode fails
 423 */
 424 static int lag_decode_frame(AVCodecContext *avctx,
 425                              void *data, int *data_size,
 426                              AVPacket *avpkt)
 427 {
 428     const uint8_t *buf = avpkt->data;
 429     int buf_size = avpkt->size;
 430     LagarithContext *l = avctx->priv_data;
 431     AVFrame * const p= &l->picture;
 432     uint8_t i_frametype = 0;
 433     uint32_t offset_gu = 0, offset_bv = 0,
 434              offset_ry = 9, offset_a = 0;
 435
 436     AVFrame *picture = data;
 437
 438     if(p->data[0])
 439         avctx->release_buffer(avctx, p);
 440
 441     p->reference = 0;
 442     p->key_frame = 1;
 443
 444     i_frametype = buf[0];
 445
 446     offset_gu = *(const uint32_t*)(buf+1);
 447     offset_bv = *(const uint32_t*)(buf+5);
 448
 449     switch(i_frametype) {
 450         case FRAME_ARITH_RGBA:
 451             offset_a = *(const uint32_t*)(buf+9);
 452             offset_ry += 4;
 453         case FRAME_ARITH_RGB24:
 454             avctx->pix_fmt = PIX_FMT_RGB24;
 455
 456             if(avctx->get_buffer(avctx, p) < 0){
 457                 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 458                 return -1;
 459             }
 460
 461             lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height, p->linesize[0], 3,
 462                                    buf+offset_ry, buf_size, 0);
 463             lag_decode_arith_plane(l, (p->data[0])+1, avctx->width, avctx->height, p->linesize[0], 3,
 464                                    buf+offset_ry, buf_size, 0);
 465             lag_decode_arith_plane(l, (p->data[0])+2, avctx->width, avctx->height, p->linesize[0], 3,
 466                                    buf+offset_ry, buf_size, 0);
 467
 468             break;
 469         case FRAME_ARITH_YV12:
 470             avctx->pix_fmt = PIX_FMT_YUV420P;
 471
 472             if(avctx->get_buffer(avctx, p) < 0){
 473                 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 474                 return -1;
 475             }
 476
 477             lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height, p->linesize[0], 1,
 478                                    buf+offset_ry, buf_size, 0);
 479             lag_decode_arith_plane(l, p->data[2], avctx->width/2, avctx->height/2, p->linesize[2], 1,
 480                                    buf+offset_gu, buf_size, 0);
 481             lag_decode_arith_plane(l, p->data[1], avctx->width/2, avctx->height/2, p->linesize[1], 1,
 482                                    buf+offset_bv, buf_size, 0);
 483             break;
 484         default:
 485             av_log(avctx, AV_LOG_ERROR, "Unsupported Lagarith frame type: %#x\n", i_frametype);
 486             return -1;
 487     }
 488
 489     *picture= *(AVFrame*)&l->picture;
 490     *data_size = sizeof(AVPicture);
 491
 492     return buf_size;
 493 }
 494
 495 /**
 496 * closes decoder
 497 * @param avctx codec context
 498 * @return 0 on success or negative if fails
 499 */
 500 static av_cold int lag_decode_end(AVCodecContext *avctx)
 501 {
 502
 503     return 0;
 504 }
 505
 506 AVCodec lagarith_decoder = {
 507     "lagarith",
 508     CODEC_TYPE_VIDEO,
 509     CODEC_ID_LAGARITH,
 510     sizeof(LagarithContext),
 511     lag_decode_init,
 512     NULL,
 513     lag_decode_end,
 514     lag_decode_frame,
 515     CODEC_CAP_DR1,
 516     .long_name = NULL_IF_CONFIG_SMALL("Lagarith"),
 517 };