1 // Copyright 2015 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 // 5 6 /* 7 * Copyright (c) 2010, The WebM Project authors. All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions are 11 * met: 12 * 13 * * Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 16 * * Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in 18 * the documentation and/or other materials provided with the 19 * distribution. 20 * 21 * * Neither the name of Google, nor the WebM Project, nor the names 22 * of its contributors may be used to endorse or promote products 23 * derived from this software without specific prior written 24 * permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 27 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 28 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 29 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 30 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 31 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 32 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 33 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 34 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 35 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 36 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 // This file is modified from the dboolhuff.{c,h} from the WebM's libvpx 40 // project. (http://www.webmproject.org/code) 41 // It is used to decode bits from a vp8 stream. 42 43 #include <limits.h> 44 45 #include <algorithm> 46 47 #include "base/numerics/safe_conversions.h" 48 #include "vp8_bool_decoder.h" 49 50 namespace media { 51 52 #define VP8_BD_VALUE_BIT \ 53 static_cast<int>(sizeof(Vp8BoolDecoder::value_) * CHAR_BIT) 54 55 static const int kDefaultProbability = 0x80; // 0x80 / 256 = 0.5 56 57 // This is meant to be a large, positive constant that can still be efficiently 58 // loaded as an immediate (on platforms like ARM, for example). Even relatively 59 // modest values like 100 would work fine. 60 #define VP8_LOTS_OF_BITS (0x40000000) 61 62 // The number of leading zeros. 63 static const unsigned char kVp8Norm[256] = { 64 0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 65 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 66 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 67 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 68 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 69 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 70 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 71 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 72 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 73 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 74 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 75 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 76 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 77 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 78 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 79 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 80 }; 81 82 Vp8BoolDecoder::Vp8BoolDecoder() 83 : user_buffer_(NULL), 84 user_buffer_end_(NULL), 85 value_(0), 86 count_(-8), 87 range_(255) { 88 } 89 90 bool Vp8BoolDecoder::Initialize(const uint8_t* data, size_t size) { 91 if (data == NULL || size == 0) 92 return false; 93 user_buffer_start_ = data; 94 user_buffer_ = data; 95 user_buffer_end_ = data + size; 96 value_ = 0; 97 count_ = -8; 98 range_ = 255; 99 return true; 100 } 101 102 void Vp8BoolDecoder::FillDecoder() { 103 DCHECK(user_buffer_ != NULL); 104 int shift = VP8_BD_VALUE_BIT - CHAR_BIT - (count_ + CHAR_BIT); 105 size_t bytes_left = user_buffer_end_ - user_buffer_; 106 size_t bits_left = bytes_left * CHAR_BIT; 107 int x = static_cast<int>(shift + CHAR_BIT - bits_left); 108 int loop_end = 0; 109 110 if (x >= 0) { 111 count_ += VP8_LOTS_OF_BITS; 112 loop_end = x; 113 } 114 115 if (x < 0 || bits_left) { 116 while (shift >= loop_end) { 117 count_ += CHAR_BIT; 118 value_ |= static_cast<size_t>(*user_buffer_) << shift; 119 ++user_buffer_; 120 shift -= CHAR_BIT; 121 } 122 } 123 } 124 125 int Vp8BoolDecoder::ReadBit(int probability) { 126 int bit = 0; 127 size_t split = 1 + (((range_ - 1) * probability) >> 8); 128 if (count_ < 0) 129 FillDecoder(); 130 size_t bigsplit = static_cast<size_t>(split) << (VP8_BD_VALUE_BIT - 8); 131 132 if (value_ >= bigsplit) { 133 range_ -= split; 134 value_ -= bigsplit; 135 bit = 1; 136 } else { 137 range_ = split; 138 } 139 140 size_t shift = kVp8Norm[range_]; 141 range_ <<= shift; 142 value_ <<= shift; 143 count_ -= shift; 144 145 DCHECK_EQ(1U, (range_ >> 7)); // In the range [128, 255]. 146 147 return bit; 148 } 149 150 bool Vp8BoolDecoder::ReadLiteral(size_t num_bits, int* out) { 151 DCHECK_LE(num_bits, sizeof(int) * CHAR_BIT); 152 *out = 0; 153 for (; num_bits > 0; --num_bits) 154 *out = (*out << 1) | ReadBit(kDefaultProbability); 155 return !OutOfBuffer(); 156 } 157 158 bool Vp8BoolDecoder::ReadBool(bool* out, uint8_t probability) { 159 *out = !!ReadBit(probability); 160 return !OutOfBuffer(); 161 } 162 163 bool Vp8BoolDecoder::ReadBool(bool* out) { 164 return ReadBool(out, kDefaultProbability); 165 } 166 167 bool Vp8BoolDecoder::ReadLiteralWithSign(size_t num_bits, int* out) { 168 ReadLiteral(num_bits, out); 169 // Read sign. 170 if (ReadBit(kDefaultProbability)) 171 *out = -*out; 172 return !OutOfBuffer(); 173 } 174 175 size_t Vp8BoolDecoder::BitOffset() { 176 int bit_count = count_ + 8; 177 if (bit_count > VP8_BD_VALUE_BIT) 178 // Capped at 0 to ignore buffer underrun. 179 bit_count = std::max(0, bit_count - VP8_LOTS_OF_BITS); 180 return (user_buffer_ - user_buffer_start_) * 8 - bit_count; 181 } 182 183 uint8_t Vp8BoolDecoder::GetRange() { 184 return base::checked_cast<uint8_t>(range_); 185 } 186 187 uint8_t Vp8BoolDecoder::GetBottom() { 188 if (count_ < 0) 189 FillDecoder(); 190 return static_cast<uint8_t>(value_ >> (VP8_BD_VALUE_BIT - 8)); 191 } 192 193 inline bool Vp8BoolDecoder::OutOfBuffer() { 194 // Check if we have reached the end of the buffer. 195 // 196 // Variable |count_| stores the number of bits in the |value_| buffer, minus 197 // 8. The top byte is part of the algorithm and the remainder is buffered to 198 // be shifted into it. So, if |count_| == 8, the top 16 bits of |value_| are 199 // occupied, 8 for the algorithm and 8 in the buffer. 200 // 201 // When reading a byte from the user's buffer, |count_| is filled with 8 and 202 // one byte is filled into the |value_| buffer. When we reach the end of the 203 // data, |count_| is additionally filled with VP8_LOTS_OF_BITS. So when 204 // |count_| == VP8_LOTS_OF_BITS - 1, the user's data has been exhausted. 205 return (count_ > VP8_BD_VALUE_BIT) && (count_ < VP8_LOTS_OF_BITS); 206 } 207 208 } // namespace media 209
