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
12 namespace media {
13
14 namespace {
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
23 const 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
Vp9BoolDecoder()38 Vp9BoolDecoder::Vp9BoolDecoder() {}
39
~Vp9BoolDecoder()40 Vp9BoolDecoder::~Vp9BoolDecoder() {}
41
42 // 9.2.1 Initialization process for Boolean decoder
Initialize(const uint8_t * data,size_t size)43 bool 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.
Fill()67 bool 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
ReadBool(int prob)90 bool 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
ReadLiteral(int bits)125 uint8_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
ConsumePaddingBits()136 bool 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