vp8_bool_decoder.cc 6.8 KB

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