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