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