vp9_bool_decoder.cc revision c8ab179e7518f2da789ff936d8ee4def58e2160a 
1// Copyright 2016 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#include "vp9_bool_decoder.h"
6
7#include <algorithm>
8
9#include "base/logging.h"
10#include "bit_reader.h"
11
12namespace media {
13
14namespace {
15
16// This is an optimization lookup table for the loop in spec 9.2.2.
17//     while BoolRange <= 128:
18//       read 1 bit
19//       BoolRange *= 2
20// This table indicates how many iterations to run for a given BoolRange. So
21// the loop could be reduced to
22//     read (kCountToShiftTo128[BoolRange]) bits
23const int kCountToShiftTo128[256] = {
24    0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
25    3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
26    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1,
27    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
28    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
29    1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
30    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
31    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
32    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
33    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
34    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
35};
36}  // namespace
37
38Vp9BoolDecoder::Vp9BoolDecoder() {}
39
40Vp9BoolDecoder::~Vp9BoolDecoder() {}
41
42// 9.2.1 Initialization process for Boolean decoder
43bool Vp9BoolDecoder::Initialize(const uint8_t* data, size_t size) {
44  DCHECK(data);
45  if (size < 1) {
46    DVLOG(1) << "input size of bool decoder shall be at least 1";
47    valid_ = false;
48    return false;
49  }
50
51  reader_.reset(new BitReader(data, size));
52  valid_ = true;
53
54  bool_value_ = 0;
55  count_to_fill_ = 8;
56  bool_range_ = 255;
57  if (ReadLiteral(1) != 0) {
58    DVLOG(1) << "marker bit should be 0";
59    valid_ = false;
60    return false;
61  }
62  return true;
63}
64
65// Fill at least |count_to_fill_| bits and prefill remain bits of |bool_value_|
66// if data is enough.
67bool Vp9BoolDecoder::Fill() {
68  DCHECK_GE(count_to_fill_, 0);
69
70  int bits_left = reader_->bits_available();
71  if (bits_left < count_to_fill_) {
72    valid_ = false;
73    DVLOG(1) << "Vp9BoolDecoder reads beyond the end of stream";
74    return false;
75  }
76
77  DCHECK_LE(count_to_fill_, kBoolSize);
78  int max_bits_to_read = kBigBoolBitSize - kBoolSize + count_to_fill_;
79  int bits_to_read = std::min(max_bits_to_read, bits_left);
80
81  BigBool data;
82  reader_->ReadBits(bits_to_read, &data);
83  bool_value_ |= data << (max_bits_to_read - bits_to_read);
84  count_to_fill_ -= bits_to_read;
85
86  return true;
87}
88
89// 9.2.2 Boolean decoding process
90bool Vp9BoolDecoder::ReadBool(int prob) {
91  DCHECK(reader_);
92
93  if (count_to_fill_ > 0) {
94    if (!Fill())
95      return false;
96  }
97
98  unsigned int split = (bool_range_ * prob + (256 - prob)) >> kBoolSize;
99  BigBool big_split = static_cast<BigBool>(split)
100                      << (kBigBoolBitSize - kBoolSize);
101
102  bool bit;
103  if (bool_value_ < big_split) {
104    bool_range_ = split;
105    bit = false;
106  } else {
107    bool_range_ -= split;
108    bool_value_ -= big_split;
109    bit = true;
110  }
111
112  // Need to fill |count| bits next time in order to make |bool_range_| >=
113  // 128.
114  DCHECK_LT(bool_range_, arraysize(kCountToShiftTo128));
115  DCHECK_GT(bool_range_, 0u);
116  int count = kCountToShiftTo128[bool_range_];
117  bool_range_ <<= count;
118  bool_value_ <<= count;
119  count_to_fill_ += count;
120
121  return bit;
122}
123
124// 9.2.4 Parsing process for read_literal
125uint8_t Vp9BoolDecoder::ReadLiteral(int bits) {
126  DCHECK_LT(static_cast<size_t>(bits), sizeof(uint8_t) * 8);
127  DCHECK(reader_);
128
129  uint8_t x = 0;
130  for (int i = 0; i < bits; i++)
131    x = 2 * x + ReadBool(128);
132
133  return x;
134}
135
136bool Vp9BoolDecoder::ConsumePaddingBits() {
137  DCHECK(reader_);
138
139  if (count_to_fill_ > reader_->bits_available()) {
140    // 9.2.2 Boolean decoding process
141    // Although we actually don't used the value, spec says the bitstream
142    // should have enough bits to fill bool range, this should never happen.
143    DVLOG(2) << "not enough bits in bitstream to fill bool range";
144    return false;
145  }
146
147  if (bool_value_ != 0) {
148    DVLOG(1) << "prefilled padding bits are not zero";
149    return false;
150  }
151  while (reader_->bits_available() > 0) {
152    int data;
153    int size_to_read =
154        std::min(reader_->bits_available(), static_cast<int>(sizeof(data) * 8));
155    reader_->ReadBits(size_to_read, &data);
156    if (data != 0) {
157      DVLOG(1) << "padding bits are not zero";
158      return false;
159    }
160  }
161  return true;
162}
163
164}  // namespace media
165