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
Vp8BoolDecoder()83 Vp8BoolDecoder::Vp8BoolDecoder()
84 : user_buffer_(NULL),
85 user_buffer_end_(NULL),
86 value_(0),
87 count_(-8),
88 range_(255) {
89 }
90
Initialize(const uint8_t * data,size_t size)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
FillDecoder()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
ReadBit(int probability)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
ReadLiteral(size_t num_bits,int * out)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
ReadBool(bool * out,uint8_t probability)159 bool Vp8BoolDecoder::ReadBool(bool* out, uint8_t probability) {
160 *out = !!ReadBit(probability);
161 return !OutOfBuffer();
162 }
163
ReadBool(bool * out)164 bool Vp8BoolDecoder::ReadBool(bool* out) {
165 return ReadBool(out, kDefaultProbability);
166 }
167
ReadLiteralWithSign(size_t num_bits,int * out)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
BitOffset()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
GetRange()184 uint8_t Vp8BoolDecoder::GetRange() {
185 return base::checked_cast<uint8_t>(range_);
186 }
187
GetBottom()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
OutOfBuffer()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