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