media/filters/vp8_bool_decoder.cc

   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 <algorithm>
  44
  45 #include "base/numerics/safe_conversions.h"
  46 #include "media/filters/vp8_bool_decoder.h"
  47
  48 namespace media {
  49
  50 #define VP8_BD_VALUE_BIT \
  51   static_cast<int>(sizeof(Vp8BoolDecoder::value_) * CHAR_BIT)
  52
  53 static const int kDefaultProbability = 0x80;  // 0x80 / 256 = 0.5
  54
  55 // This is meant to be a large, positive constant that can still be efficiently
  56 // loaded as an immediate (on platforms like ARM, for example). Even relatively
  57 // modest values like 100 would work fine.
  58 #define VP8_LOTS_OF_BITS (0x40000000)
  59
  60 // The number of leading zeros.
  61 static const unsigned char kVp8Norm[256] = {
  62     0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
  63     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  64     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  65     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  66     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  67     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  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     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  71     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  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 };
  79
  80 Vp8BoolDecoder::Vp8BoolDecoder()
  81     : user_buffer_(NULL),
  82       user_buffer_end_(NULL),
  83       value_(0),
  84       count_(-8),
  85       range_(255) {
  86 }
  87
  88 bool Vp8BoolDecoder::Initialize(const uint8_t* data, size_t size) {
  89   if (data == NULL || size == 0)
  90     return false;
  91   user_buffer_start_ = data;
  92   user_buffer_ = data;
  93   user_buffer_end_ = data + size;
  94   value_ = 0;
  95   count_ = -8;
  96   range_ = 255;
  97   return true;
  98 }
  99
 100 void Vp8BoolDecoder::FillDecoder() {
 101   DCHECK(user_buffer_ != NULL);
 102   int shift = VP8_BD_VALUE_BIT - CHAR_BIT - (count_ + CHAR_BIT);
 103   size_t bytes_left = user_buffer_end_ - user_buffer_;
 104   size_t bits_left = bytes_left * CHAR_BIT;
 105   int x = static_cast<int>(shift + CHAR_BIT - bits_left);
 106   int loop_end = 0;
 107
 108   if (x >= 0) {
 109     count_ += VP8_LOTS_OF_BITS;
 110     loop_end = x;
 111   }
 112
 113   if (x < 0 || bits_left) {
 114     while (shift >= loop_end) {
 115       count_ += CHAR_BIT;
 116       value_ |= static_cast<size_t>(*user_buffer_) << shift;
 117       ++user_buffer_;
 118       shift -= CHAR_BIT;
 119     }
 120   }
 121 }
 122
 123 int Vp8BoolDecoder::ReadBit(int probability) {
 124   int bit = 0;
 125   size_t split = 1 + (((range_ - 1) * probability) >> 8);
 126   if (count_ < 0)
 127     FillDecoder();
 128   size_t bigsplit = static_cast<size_t>(split) << (VP8_BD_VALUE_BIT - 8);
 129
 130   if (value_ >= bigsplit) {
 131     range_ -= split;
 132     value_ -= bigsplit;
 133     bit = 1;
 134   } else {
 135     range_ = split;
 136   }
 137
 138   size_t shift = kVp8Norm[range_];
 139   range_ <<= shift;
 140   value_ <<= shift;
 141   count_ -= shift;
 142
 143   DCHECK_EQ(1U, (range_ >> 7));  // In the range [128, 255].
 144
 145   return bit;
 146 }
 147
 148 bool Vp8BoolDecoder::ReadLiteral(size_t num_bits, int* out) {
 149   DCHECK_LE(num_bits, sizeof(int) * CHAR_BIT);
 150   *out = 0;
 151   for (; num_bits > 0; --num_bits)
 152     *out = (*out << 1) | ReadBit(kDefaultProbability);
 153   return !OutOfBuffer();
 154 }
 155
 156 bool Vp8BoolDecoder::ReadBool(bool* out, uint8_t probability) {
 157   *out = !!ReadBit(probability);
 158   return !OutOfBuffer();
 159 }
 160
 161 bool Vp8BoolDecoder::ReadBool(bool* out) {
 162   return ReadBool(out, kDefaultProbability);
 163 }
 164
 165 bool Vp8BoolDecoder::ReadLiteralWithSign(size_t num_bits, int* out) {
 166   ReadLiteral(num_bits, out);
 167   // Read sign.
 168   if (ReadBit(kDefaultProbability))
 169     *out = -*out;
 170   return !OutOfBuffer();
 171 }
 172
 173 size_t Vp8BoolDecoder::BitOffset() {
 174   int bit_count = count_ + 8;
 175   if (bit_count > VP8_BD_VALUE_BIT)
 176     // Capped at 0 to ignore buffer underrun.
 177     bit_count = std::max(0, bit_count - VP8_LOTS_OF_BITS);
 178   return (user_buffer_ - user_buffer_start_) * 8 - bit_count;
 179 }
 180
 181 uint8_t Vp8BoolDecoder::GetRange() {
 182   return base::checked_cast<uint8_t>(range_);
 183 }
 184
 185 uint8_t Vp8BoolDecoder::GetBottom() {
 186   if (count_ < 0)
 187     FillDecoder();
 188   return static_cast<uint8_t>(value_ >> (VP8_BD_VALUE_BIT - 8));
 189 }
 190
 191 inline bool Vp8BoolDecoder::OutOfBuffer() {
 192   // Check if we have reached the end of the buffer.
 193   //
 194   // Variable |count_| stores the number of bits in the |value_| buffer, minus
 195   // 8. The top byte is part of the algorithm and the remainder is buffered to
 196   // be shifted into it. So, if |count_| == 8, the top 16 bits of |value_| are
 197   // occupied, 8 for the algorithm and 8 in the buffer.
 198   //
 199   // When reading a byte from the user's buffer, |count_| is filled with 8 and
 200   // one byte is filled into the |value_| buffer. When we reach the end of the
 201   // data, |count_| is additionally filled with VP8_LOTS_OF_BITS. So when
 202   // |count_| == VP8_LOTS_OF_BITS - 1, the user's data has been exhausted.
 203   return (count_ > VP8_BD_VALUE_BIT) && (count_ < VP8_LOTS_OF_BITS);
 204 }
 205
 206 }  // namespace media