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