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