10eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// Copyright 2015 The Chromium Authors. All rights reserved. 20eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// Use of this source code is governed by a BSD-style license that can be 30eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// found in the LICENSE file. 40eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// 50eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 60eed94a55c7764e527386696f54465048dd75688Pin-chih Lin/* 70eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * Copyright (c) 2010, The WebM Project authors. All rights reserved. 80eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * 90eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * Redistribution and use in source and binary forms, with or without 100eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * modification, are permitted provided that the following conditions are 110eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * met: 120eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * 130eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * * Redistributions of source code must retain the above copyright 140eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * notice, this list of conditions and the following disclaimer. 150eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * 160eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * * Redistributions in binary form must reproduce the above copyright 170eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * notice, this list of conditions and the following disclaimer in 180eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * the documentation and/or other materials provided with the 190eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * distribution. 200eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * 210eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * * Neither the name of Google, nor the WebM Project, nor the names 220eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * of its contributors may be used to endorse or promote products 230eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * derived from this software without specific prior written 240eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * permission. 250eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * 260eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 270eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 280eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 290eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 300eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 310eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 320eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 330eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 340eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 350eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 360eed94a55c7764e527386696f54465048dd75688Pin-chih Lin * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 370eed94a55c7764e527386696f54465048dd75688Pin-chih Lin */ 380eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 390eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// This file is modified from the dboolhuff.{c,h} from the WebM's libvpx 400eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// project. (http://www.webmproject.org/code) 410eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// It is used to decode bits from a vp8 stream. 420eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 430eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#include <limits.h> 440eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 450eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#include <algorithm> 460eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 470eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#include "base/numerics/safe_conversions.h" 480eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#include "vp8_bool_decoder.h" 490eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 500eed94a55c7764e527386696f54465048dd75688Pin-chih Linnamespace media { 510eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 520eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#define VP8_BD_VALUE_BIT \ 530eed94a55c7764e527386696f54465048dd75688Pin-chih Lin static_cast<int>(sizeof(Vp8BoolDecoder::value_) * CHAR_BIT) 540eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 550eed94a55c7764e527386696f54465048dd75688Pin-chih Linstatic const int kDefaultProbability = 0x80; // 0x80 / 256 = 0.5 560eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 570eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// This is meant to be a large, positive constant that can still be efficiently 580eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// loaded as an immediate (on platforms like ARM, for example). Even relatively 590eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// modest values like 100 would work fine. 600eed94a55c7764e527386696f54465048dd75688Pin-chih Lin#define VP8_LOTS_OF_BITS (0x40000000) 610eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 620eed94a55c7764e527386696f54465048dd75688Pin-chih Lin// The number of leading zeros. 630eed94a55c7764e527386696f54465048dd75688Pin-chih Linstatic const unsigned char kVp8Norm[256] = { 640eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 650eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 660eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 670eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 680eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 690eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 700eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 710eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 720eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 730eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 740eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 750eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 760eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 770eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 780eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 790eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 800eed94a55c7764e527386696f54465048dd75688Pin-chih Lin}; 810eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 820eed94a55c7764e527386696f54465048dd75688Pin-chih LinVp8BoolDecoder::Vp8BoolDecoder() 830eed94a55c7764e527386696f54465048dd75688Pin-chih Lin : user_buffer_(NULL), 840eed94a55c7764e527386696f54465048dd75688Pin-chih Lin user_buffer_end_(NULL), 850eed94a55c7764e527386696f54465048dd75688Pin-chih Lin value_(0), 860eed94a55c7764e527386696f54465048dd75688Pin-chih Lin count_(-8), 870eed94a55c7764e527386696f54465048dd75688Pin-chih Lin range_(255) { 880eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 890eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 900eed94a55c7764e527386696f54465048dd75688Pin-chih Linbool Vp8BoolDecoder::Initialize(const uint8_t* data, size_t size) { 910eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (data == NULL || size == 0) 920eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return false; 930eed94a55c7764e527386696f54465048dd75688Pin-chih Lin user_buffer_start_ = data; 940eed94a55c7764e527386696f54465048dd75688Pin-chih Lin user_buffer_ = data; 950eed94a55c7764e527386696f54465048dd75688Pin-chih Lin user_buffer_end_ = data + size; 960eed94a55c7764e527386696f54465048dd75688Pin-chih Lin value_ = 0; 970eed94a55c7764e527386696f54465048dd75688Pin-chih Lin count_ = -8; 980eed94a55c7764e527386696f54465048dd75688Pin-chih Lin range_ = 255; 990eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return true; 1000eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1010eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1020eed94a55c7764e527386696f54465048dd75688Pin-chih Linvoid Vp8BoolDecoder::FillDecoder() { 1030eed94a55c7764e527386696f54465048dd75688Pin-chih Lin DCHECK(user_buffer_ != NULL); 1040eed94a55c7764e527386696f54465048dd75688Pin-chih Lin int shift = VP8_BD_VALUE_BIT - CHAR_BIT - (count_ + CHAR_BIT); 1050eed94a55c7764e527386696f54465048dd75688Pin-chih Lin size_t bytes_left = user_buffer_end_ - user_buffer_; 1060eed94a55c7764e527386696f54465048dd75688Pin-chih Lin size_t bits_left = bytes_left * CHAR_BIT; 1070eed94a55c7764e527386696f54465048dd75688Pin-chih Lin int x = static_cast<int>(shift + CHAR_BIT - bits_left); 1080eed94a55c7764e527386696f54465048dd75688Pin-chih Lin int loop_end = 0; 1090eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1100eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (x >= 0) { 1110eed94a55c7764e527386696f54465048dd75688Pin-chih Lin count_ += VP8_LOTS_OF_BITS; 1120eed94a55c7764e527386696f54465048dd75688Pin-chih Lin loop_end = x; 1130eed94a55c7764e527386696f54465048dd75688Pin-chih Lin } 1140eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1150eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (x < 0 || bits_left) { 1160eed94a55c7764e527386696f54465048dd75688Pin-chih Lin while (shift >= loop_end) { 1170eed94a55c7764e527386696f54465048dd75688Pin-chih Lin count_ += CHAR_BIT; 1180eed94a55c7764e527386696f54465048dd75688Pin-chih Lin value_ |= static_cast<size_t>(*user_buffer_) << shift; 1190eed94a55c7764e527386696f54465048dd75688Pin-chih Lin ++user_buffer_; 1200eed94a55c7764e527386696f54465048dd75688Pin-chih Lin shift -= CHAR_BIT; 1210eed94a55c7764e527386696f54465048dd75688Pin-chih Lin } 1220eed94a55c7764e527386696f54465048dd75688Pin-chih Lin } 1230eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1240eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1250eed94a55c7764e527386696f54465048dd75688Pin-chih Linint Vp8BoolDecoder::ReadBit(int probability) { 1260eed94a55c7764e527386696f54465048dd75688Pin-chih Lin int bit = 0; 1270eed94a55c7764e527386696f54465048dd75688Pin-chih Lin size_t split = 1 + (((range_ - 1) * probability) >> 8); 1280eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (count_ < 0) 1290eed94a55c7764e527386696f54465048dd75688Pin-chih Lin FillDecoder(); 1300eed94a55c7764e527386696f54465048dd75688Pin-chih Lin size_t bigsplit = static_cast<size_t>(split) << (VP8_BD_VALUE_BIT - 8); 1310eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1320eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (value_ >= bigsplit) { 1330eed94a55c7764e527386696f54465048dd75688Pin-chih Lin range_ -= split; 1340eed94a55c7764e527386696f54465048dd75688Pin-chih Lin value_ -= bigsplit; 1350eed94a55c7764e527386696f54465048dd75688Pin-chih Lin bit = 1; 1360eed94a55c7764e527386696f54465048dd75688Pin-chih Lin } else { 1370eed94a55c7764e527386696f54465048dd75688Pin-chih Lin range_ = split; 1380eed94a55c7764e527386696f54465048dd75688Pin-chih Lin } 1390eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1400eed94a55c7764e527386696f54465048dd75688Pin-chih Lin size_t shift = kVp8Norm[range_]; 1410eed94a55c7764e527386696f54465048dd75688Pin-chih Lin range_ <<= shift; 1420eed94a55c7764e527386696f54465048dd75688Pin-chih Lin value_ <<= shift; 1430eed94a55c7764e527386696f54465048dd75688Pin-chih Lin count_ -= shift; 1440eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1450eed94a55c7764e527386696f54465048dd75688Pin-chih Lin DCHECK_EQ(1U, (range_ >> 7)); // In the range [128, 255]. 1460eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1470eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return bit; 1480eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1490eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1500eed94a55c7764e527386696f54465048dd75688Pin-chih Linbool Vp8BoolDecoder::ReadLiteral(size_t num_bits, int* out) { 1510eed94a55c7764e527386696f54465048dd75688Pin-chih Lin DCHECK_LE(num_bits, sizeof(int) * CHAR_BIT); 1520eed94a55c7764e527386696f54465048dd75688Pin-chih Lin *out = 0; 1530eed94a55c7764e527386696f54465048dd75688Pin-chih Lin for (; num_bits > 0; --num_bits) 1540eed94a55c7764e527386696f54465048dd75688Pin-chih Lin *out = (*out << 1) | ReadBit(kDefaultProbability); 1550eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return !OutOfBuffer(); 1560eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1570eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1580eed94a55c7764e527386696f54465048dd75688Pin-chih Linbool Vp8BoolDecoder::ReadBool(bool* out, uint8_t probability) { 1590eed94a55c7764e527386696f54465048dd75688Pin-chih Lin *out = !!ReadBit(probability); 1600eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return !OutOfBuffer(); 1610eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1620eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1630eed94a55c7764e527386696f54465048dd75688Pin-chih Linbool Vp8BoolDecoder::ReadBool(bool* out) { 1640eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return ReadBool(out, kDefaultProbability); 1650eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1660eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1670eed94a55c7764e527386696f54465048dd75688Pin-chih Linbool Vp8BoolDecoder::ReadLiteralWithSign(size_t num_bits, int* out) { 1680eed94a55c7764e527386696f54465048dd75688Pin-chih Lin ReadLiteral(num_bits, out); 1690eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // Read sign. 1700eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (ReadBit(kDefaultProbability)) 1710eed94a55c7764e527386696f54465048dd75688Pin-chih Lin *out = -*out; 1720eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return !OutOfBuffer(); 1730eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1740eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1750eed94a55c7764e527386696f54465048dd75688Pin-chih Linsize_t Vp8BoolDecoder::BitOffset() { 1760eed94a55c7764e527386696f54465048dd75688Pin-chih Lin int bit_count = count_ + 8; 1770eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (bit_count > VP8_BD_VALUE_BIT) 1780eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // Capped at 0 to ignore buffer underrun. 1790eed94a55c7764e527386696f54465048dd75688Pin-chih Lin bit_count = std::max(0, bit_count - VP8_LOTS_OF_BITS); 1800eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return (user_buffer_ - user_buffer_start_) * 8 - bit_count; 1810eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1820eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1830eed94a55c7764e527386696f54465048dd75688Pin-chih Linuint8_t Vp8BoolDecoder::GetRange() { 1840eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return base::checked_cast<uint8_t>(range_); 1850eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1860eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1870eed94a55c7764e527386696f54465048dd75688Pin-chih Linuint8_t Vp8BoolDecoder::GetBottom() { 1880eed94a55c7764e527386696f54465048dd75688Pin-chih Lin if (count_ < 0) 1890eed94a55c7764e527386696f54465048dd75688Pin-chih Lin FillDecoder(); 1900eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return static_cast<uint8_t>(value_ >> (VP8_BD_VALUE_BIT - 8)); 1910eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 1920eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 1930eed94a55c7764e527386696f54465048dd75688Pin-chih Lininline bool Vp8BoolDecoder::OutOfBuffer() { 1940eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // Check if we have reached the end of the buffer. 1950eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // 1960eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // Variable |count_| stores the number of bits in the |value_| buffer, minus 1970eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // 8. The top byte is part of the algorithm and the remainder is buffered to 1980eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // be shifted into it. So, if |count_| == 8, the top 16 bits of |value_| are 1990eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // occupied, 8 for the algorithm and 8 in the buffer. 2000eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // 2010eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // When reading a byte from the user's buffer, |count_| is filled with 8 and 2020eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // one byte is filled into the |value_| buffer. When we reach the end of the 2030eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // data, |count_| is additionally filled with VP8_LOTS_OF_BITS. So when 2040eed94a55c7764e527386696f54465048dd75688Pin-chih Lin // |count_| == VP8_LOTS_OF_BITS - 1, the user's data has been exhausted. 2050eed94a55c7764e527386696f54465048dd75688Pin-chih Lin return (count_ > VP8_BD_VALUE_BIT) && (count_ < VP8_LOTS_OF_BITS); 2060eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} 2070eed94a55c7764e527386696f54465048dd75688Pin-chih Lin 2080eed94a55c7764e527386696f54465048dd75688Pin-chih Lin} // namespace media 209