Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Lagarith range decoder
  3.  * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
  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
  25.  * Lagarith range decoder
  26.  * @author Nathan Caldwell
  27.  * @author David Conrad
  28.  */
  29.  
  30. #ifndef AVCODEC_LAGARITHRAC_H
  31. #define AVCODEC_LAGARITHRAC_H
  32.  
  33. #include <stdint.h>
  34. #include "libavutil/common.h"
  35. #include "libavutil/intreadwrite.h"
  36. #include "avcodec.h"
  37. #include "get_bits.h"
  38.  
  39. typedef struct lag_rac {
  40.     AVCodecContext *avctx;
  41.     unsigned low;
  42.     unsigned range;
  43.     unsigned scale;             /**< Number of bits of precision in range. */
  44.     unsigned hash_shift;        /**< Number of bits to shift to calculate hash for radix search. */
  45.  
  46.     const uint8_t *bytestream_start;  /**< Start of input bytestream. */
  47.     const uint8_t *bytestream;        /**< Current position in input bytestream. */
  48.     const uint8_t *bytestream_end;    /**< End position of input bytestream. */
  49.  
  50.     uint32_t prob[258];         /**< Table of cumulative probability for each symbol. */
  51.     uint8_t  range_hash[256];   /**< Hash table mapping upper byte to approximate symbol. */
  52. } lag_rac;
  53.  
  54. void ff_lag_rac_init(lag_rac *l, GetBitContext *gb, int length);
  55.  
  56. /* TODO: Optimize */
  57. static inline void lag_rac_refill(lag_rac *l)
  58. {
  59.     while (l->range <= 0x800000) {
  60.         l->low   <<= 8;
  61.         l->range <<= 8;
  62.         l->low |= 0xff & (AV_RB16(l->bytestream) >> 1);
  63.         if (l->bytestream < l->bytestream_end)
  64.             l->bytestream++;
  65.     }
  66. }
  67.  
  68. /**
  69.  * Decode a single byte from the compressed plane described by *l.
  70.  * @param l pointer to lag_rac for the current plane
  71.  * @return next byte of decoded data
  72.  */
  73. static inline uint8_t lag_get_rac(lag_rac *l)
  74. {
  75.     unsigned range_scaled, low_scaled, div;
  76.     int val;
  77.     uint8_t shift;
  78.  
  79.     lag_rac_refill(l);
  80.  
  81.     range_scaled = l->range >> l->scale;
  82.  
  83.     if (l->low < range_scaled * l->prob[255]) {
  84.         /* val = 0 is frequent enough to deserve a shortcut */
  85.         if (l->low < range_scaled * l->prob[1]) {
  86.             val = 0;
  87.         } else {
  88.             /* FIXME __builtin_clz is ~20% faster here, but not allowed in generic code. */
  89.             shift = 30 - av_log2(range_scaled);
  90.             div = ((range_scaled << shift) + (1 << 23) - 1) >> 23;
  91.             /* low>>24 ensures that any cases too big for exact FASTDIV are
  92.              * under- rather than over-estimated
  93.              */
  94.             low_scaled = FASTDIV(l->low - (l->low >> 24), div);
  95.             shift -= l->hash_shift;
  96.             shift &= 31;
  97.             low_scaled = (low_scaled << shift) | (low_scaled >> (32 - shift));
  98.             /* low_scaled is now a lower bound of low/range_scaled */
  99.             val = l->range_hash[(uint8_t) low_scaled];
  100.             while (l->low >= range_scaled * l->prob[val + 1])
  101.                 val++;
  102.         }
  103.  
  104.         l->range = range_scaled * (l->prob[val + 1] - l->prob[val]);
  105.     } else {
  106.         val = 255;
  107.         l->range -= range_scaled * l->prob[255];
  108.     }
  109.  
  110.     if (!l->range)
  111.         l->range = 0x80;
  112.  
  113.     l->low -= range_scaled * l->prob[val];
  114.  
  115.     return val;
  116. }
  117.  
  118.  
  119. #endif /* AVCODEC_LAGARITHRAC_H */
  120.