src/third_party/libwebp/utils/bit_reader.c

   1 // Copyright 2010 Google Inc. All Rights Reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the COPYING file in the root of the source
   5 // tree. An additional intellectual property rights grant can be found
   6 // in the file PATENTS. All contributing project authors may
   7 // be found in the AUTHORS file in the root of the source tree.
   8 // -----------------------------------------------------------------------------
   9 //
  10 // Boolean decoder
  11 //
  12 // Author: Skal (pascal.massimino@gmail.com)
  13
  14 #include "./bit_reader.h"
  15
  16 #ifndef USE_RIGHT_JUSTIFY
  17 #define MK(X) (((range_t)(X) << (BITS)) | (MASK))
  18 #else
  19 #define MK(X) ((range_t)(X))
  20 #endif
  21
  22 //------------------------------------------------------------------------------
  23 // VP8BitReader
  24
  25 void VP8InitBitReader(VP8BitReader* const br,
  26                       const uint8_t* const start, const uint8_t* const end) {
  27   assert(br != NULL);
  28   assert(start != NULL);
  29   assert(start <= end);
  30   br->range_   = MK(255 - 1);
  31   br->buf_     = start;
  32   br->buf_end_ = end;
  33   br->value_   = 0;
  34   br->bits_    = -8;   // to load the very first 8bits
  35   br->eof_     = 0;
  36 }
  37
  38 const uint8_t kVP8Log2Range[128] = {
  39      7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
  40   3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  41   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  42   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  43   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  44   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  45   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  46   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  47   0
  48 };
  49
  50 // range = (range << kVP8Log2Range[range]) + trailing 1's
  51 const range_t kVP8NewRange[128] = {
  52   MK(127), MK(127), MK(191), MK(127), MK(159), MK(191), MK(223), MK(127),
  53   MK(143), MK(159), MK(175), MK(191), MK(207), MK(223), MK(239), MK(127),
  54   MK(135), MK(143), MK(151), MK(159), MK(167), MK(175), MK(183), MK(191),
  55   MK(199), MK(207), MK(215), MK(223), MK(231), MK(239), MK(247), MK(127),
  56   MK(131), MK(135), MK(139), MK(143), MK(147), MK(151), MK(155), MK(159),
  57   MK(163), MK(167), MK(171), MK(175), MK(179), MK(183), MK(187), MK(191),
  58   MK(195), MK(199), MK(203), MK(207), MK(211), MK(215), MK(219), MK(223),
  59   MK(227), MK(231), MK(235), MK(239), MK(243), MK(247), MK(251), MK(127),
  60   MK(129), MK(131), MK(133), MK(135), MK(137), MK(139), MK(141), MK(143),
  61   MK(145), MK(147), MK(149), MK(151), MK(153), MK(155), MK(157), MK(159),
  62   MK(161), MK(163), MK(165), MK(167), MK(169), MK(171), MK(173), MK(175),
  63   MK(177), MK(179), MK(181), MK(183), MK(185), MK(187), MK(189), MK(191),
  64   MK(193), MK(195), MK(197), MK(199), MK(201), MK(203), MK(205), MK(207),
  65   MK(209), MK(211), MK(213), MK(215), MK(217), MK(219), MK(221), MK(223),
  66   MK(225), MK(227), MK(229), MK(231), MK(233), MK(235), MK(237), MK(239),
  67   MK(241), MK(243), MK(245), MK(247), MK(249), MK(251), MK(253), MK(127)
  68 };
  69
  70 #undef MK
  71
  72 void VP8LoadFinalBytes(VP8BitReader* const br) {
  73   assert(br != NULL && br->buf_ != NULL);
  74   // Only read 8bits at a time
  75   if (br->buf_ < br->buf_end_) {
  76 #ifndef USE_RIGHT_JUSTIFY
  77     br->value_ |= (bit_t)(*br->buf_++) << ((BITS) - 8 - br->bits_);
  78 #else
  79     br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8);
  80 #endif
  81     br->bits_ += 8;
  82   } else if (!br->eof_) {
  83 #ifdef USE_RIGHT_JUSTIFY
  84     // These are not strictly needed, but it makes the behaviour
  85     // consistent for both USE_RIGHT_JUSTIFY and !USE_RIGHT_JUSTIFY.
  86     br->value_ <<= 8;
  87     br->bits_ += 8;
  88 #endif
  89     br->eof_ = 1;
  90   }
  91 }
  92
  93 //------------------------------------------------------------------------------
  94 // Higher-level calls
  95
  96 uint32_t VP8GetValue(VP8BitReader* const br, int bits) {
  97   uint32_t v = 0;
  98   while (bits-- > 0) {
  99     v |= VP8GetBit(br, 0x80) << bits;
 100   }
 101   return v;
 102 }
 103
 104 int32_t VP8GetSignedValue(VP8BitReader* const br, int bits) {
 105   const int value = VP8GetValue(br, bits);
 106   return VP8Get(br) ? -value : value;
 107 }
 108
 109 //------------------------------------------------------------------------------
 110 // VP8LBitReader
 111
 112 #define MAX_NUM_BIT_READ 25
 113
 114 #define LBITS 64      // Number of bits prefetched.
 115 #define WBITS 32      // Minimum number of bytes needed after VP8LFillBitWindow.
 116 #define LOG8_WBITS 4  // Number of bytes needed to store WBITS bits.
 117
 118 static const uint32_t kBitMask[MAX_NUM_BIT_READ] = {
 119   0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
 120   65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
 121 };
 122
 123 void VP8LInitBitReader(VP8LBitReader* const br,
 124                        const uint8_t* const start,
 125                        size_t length) {
 126   size_t i;
 127   assert(br != NULL);
 128   assert(start != NULL);
 129   assert(length < 0xfffffff8u);   // can't happen with a RIFF chunk.
 130
 131   br->buf_ = start;
 132   br->len_ = length;
 133   br->val_ = 0;
 134   br->pos_ = 0;
 135   br->bit_pos_ = 0;
 136   br->eos_ = 0;
 137   br->error_ = 0;
 138   for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) {
 139     br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (8 * i);
 140     ++br->pos_;
 141   }
 142 }
 143
 144 // Special version that assumes br->pos_ <= br_len_.
 145 static int IsEndOfStreamSpecial(const VP8LBitReader* const br) {
 146   assert(br->pos_ <= br->len_);
 147   return br->pos_ == br->len_ && br->bit_pos_ >= LBITS;
 148 }
 149
 150 static int IsEndOfStream(const VP8LBitReader* const br) {
 151   return (br->pos_ > br->len_) || IsEndOfStreamSpecial(br);
 152 }
 153
 154 void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
 155                             const uint8_t* const buf, size_t len) {
 156   assert(br != NULL);
 157   assert(buf != NULL);
 158   assert(len < 0xfffffff8u);   // can't happen with a RIFF chunk.
 159   br->buf_ = buf;
 160   br->len_ = len;
 161   br->eos_ = IsEndOfStream(br);
 162 }
 163
 164 // If not at EOS, reload up to LBITS byte-by-byte
 165 static void ShiftBytes(VP8LBitReader* const br) {
 166   while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
 167     br->val_ >>= 8;
 168     br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (LBITS - 8);
 169     ++br->pos_;
 170     br->bit_pos_ -= 8;
 171   }
 172 }
 173
 174 void VP8LFillBitWindow(VP8LBitReader* const br) {
 175   if (br->bit_pos_ >= WBITS) {
 176 #if (defined(__x86_64__) || defined(_M_X64))
 177     if (br->pos_ + sizeof(br->val_) < br->len_) {
 178       br->val_ >>= WBITS;
 179       br->bit_pos_ -= WBITS;
 180       // The expression below needs a little-endian arch to work correctly.
 181       // This gives a large speedup for decoding speed.
 182       br->val_ |= *(const vp8l_val_t*)(br->buf_ + br->pos_) << (LBITS - WBITS);
 183       br->pos_ += LOG8_WBITS;
 184       return;
 185     }
 186 #endif
 187     ShiftBytes(br);       // Slow path.
 188     br->eos_ = IsEndOfStreamSpecial(br);
 189   }
 190 }
 191
 192 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) {
 193   assert(n_bits >= 0);
 194   // Flag an error if end_of_stream or n_bits is more than allowed limit.
 195   if (!br->eos_ && n_bits < MAX_NUM_BIT_READ) {
 196     const uint32_t val =
 197         (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
 198     const int new_bits = br->bit_pos_ + n_bits;
 199     br->bit_pos_ = new_bits;
 200     // If this read is going to cross the read buffer, set the eos flag.
 201     br->eos_ = IsEndOfStreamSpecial(br);
 202     ShiftBytes(br);
 203     return val;
 204   } else {
 205     br->error_ = 1;
 206     return 0;
 207   }
 208 }
 209
 210 //------------------------------------------------------------------------------
 211