1 /*
2 * Copyright 2021 The WebRTC Project Authors. All rights reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "rtc_base/bitstream_reader.h"
12
13 #include <stddef.h>
14 #include <stdint.h>
15
16 #include <array>
17 #include <limits>
18
19 #include "absl/numeric/bits.h"
20 #include "absl/types/optional.h"
21 #include "api/array_view.h"
22 #include "rtc_base/checks.h"
23 #include "test/gmock.h"
24 #include "test/gtest.h"
25
26 namespace webrtc {
27 namespace {
28
TEST(BitstreamReaderTest,InDebugModeRequiresToCheckOkStatusBeforeDestruction)29 TEST(BitstreamReaderTest, InDebugModeRequiresToCheckOkStatusBeforeDestruction) {
30 const uint8_t bytes[32] = {};
31 absl::optional<BitstreamReader> reader(absl::in_place, bytes);
32
33 EXPECT_GE(reader->ReadBits(7), 0u);
34 #if RTC_DCHECK_IS_ON && GTEST_HAS_DEATH_TEST && !defined(OS_ANDROID)
35 EXPECT_DEATH(reader = absl::nullopt, "");
36 #endif
37 EXPECT_TRUE(reader->Ok());
38 reader = absl::nullopt;
39 }
40
TEST(BitstreamReaderTest,InDebugModeMayCheckRemainingBitsInsteadOfOkStatus)41 TEST(BitstreamReaderTest, InDebugModeMayCheckRemainingBitsInsteadOfOkStatus) {
42 const uint8_t bytes[32] = {};
43 absl::optional<BitstreamReader> reader(absl::in_place, bytes);
44
45 EXPECT_GE(reader->ReadBit(), 0);
46 #if RTC_DCHECK_IS_ON && GTEST_HAS_DEATH_TEST && !defined(OS_ANDROID)
47 EXPECT_DEATH(reader = absl::nullopt, "");
48 #endif
49 EXPECT_GE(reader->RemainingBitCount(), 0);
50 reader = absl::nullopt;
51 }
52
TEST(BitstreamReaderTest,ConsumeBits)53 TEST(BitstreamReaderTest, ConsumeBits) {
54 const uint8_t bytes[32] = {};
55 BitstreamReader reader(bytes);
56
57 int total_bits = 32 * 8;
58 EXPECT_EQ(reader.RemainingBitCount(), total_bits);
59 reader.ConsumeBits(3);
60 total_bits -= 3;
61 EXPECT_EQ(reader.RemainingBitCount(), total_bits);
62 reader.ConsumeBits(3);
63 total_bits -= 3;
64 EXPECT_EQ(reader.RemainingBitCount(), total_bits);
65 reader.ConsumeBits(15);
66 total_bits -= 15;
67 EXPECT_EQ(reader.RemainingBitCount(), total_bits);
68 reader.ConsumeBits(67);
69 total_bits -= 67;
70 EXPECT_EQ(reader.RemainingBitCount(), total_bits);
71 EXPECT_TRUE(reader.Ok());
72
73 reader.ConsumeBits(32 * 8);
74 EXPECT_FALSE(reader.Ok());
75 EXPECT_LT(reader.RemainingBitCount(), 0);
76 }
77
TEST(BitstreamReaderTest,ConsumeLotsOfBits)78 TEST(BitstreamReaderTest, ConsumeLotsOfBits) {
79 const uint8_t bytes[1] = {};
80 BitstreamReader reader(bytes);
81
82 reader.ConsumeBits(std::numeric_limits<int>::max());
83 reader.ConsumeBits(std::numeric_limits<int>::max());
84 EXPECT_GE(reader.ReadBit(), 0);
85 EXPECT_FALSE(reader.Ok());
86 }
87
TEST(BitstreamReaderTest,ReadBit)88 TEST(BitstreamReaderTest, ReadBit) {
89 const uint8_t bytes[] = {0b0100'0001, 0b1011'0001};
90 BitstreamReader reader(bytes);
91 // First byte.
92 EXPECT_EQ(reader.ReadBit(), 0);
93 EXPECT_EQ(reader.ReadBit(), 1);
94 EXPECT_EQ(reader.ReadBit(), 0);
95 EXPECT_EQ(reader.ReadBit(), 0);
96
97 EXPECT_EQ(reader.ReadBit(), 0);
98 EXPECT_EQ(reader.ReadBit(), 0);
99 EXPECT_EQ(reader.ReadBit(), 0);
100 EXPECT_EQ(reader.ReadBit(), 1);
101
102 // Second byte.
103 EXPECT_EQ(reader.ReadBit(), 1);
104 EXPECT_EQ(reader.ReadBit(), 0);
105 EXPECT_EQ(reader.ReadBit(), 1);
106 EXPECT_EQ(reader.ReadBit(), 1);
107
108 EXPECT_EQ(reader.ReadBit(), 0);
109 EXPECT_EQ(reader.ReadBit(), 0);
110 EXPECT_EQ(reader.ReadBit(), 0);
111 EXPECT_EQ(reader.ReadBit(), 1);
112
113 EXPECT_TRUE(reader.Ok());
114 // Try to read beyound the buffer.
115 EXPECT_EQ(reader.ReadBit(), 0);
116 EXPECT_FALSE(reader.Ok());
117 }
118
TEST(BitstreamReaderTest,ReadBoolConsumesSingleBit)119 TEST(BitstreamReaderTest, ReadBoolConsumesSingleBit) {
120 const uint8_t bytes[] = {0b1010'1010};
121 BitstreamReader reader(bytes);
122 ASSERT_EQ(reader.RemainingBitCount(), 8);
123 EXPECT_TRUE(reader.Read<bool>());
124 EXPECT_EQ(reader.RemainingBitCount(), 7);
125 }
126
TEST(BitstreamReaderTest,ReadBytesAligned)127 TEST(BitstreamReaderTest, ReadBytesAligned) {
128 const uint8_t bytes[] = {0x0A, //
129 0xBC, //
130 0xDE, 0xF1, //
131 0x23, 0x45, 0x67, 0x89};
132 BitstreamReader reader(bytes);
133 EXPECT_EQ(reader.Read<uint8_t>(), 0x0Au);
134 EXPECT_EQ(reader.Read<uint8_t>(), 0xBCu);
135 EXPECT_EQ(reader.Read<uint16_t>(), 0xDEF1u);
136 EXPECT_EQ(reader.Read<uint32_t>(), 0x23456789u);
137 EXPECT_TRUE(reader.Ok());
138 }
139
TEST(BitstreamReaderTest,ReadBytesOffset4)140 TEST(BitstreamReaderTest, ReadBytesOffset4) {
141 const uint8_t bytes[] = {0x0A, 0xBC, 0xDE, 0xF1, 0x23,
142 0x45, 0x67, 0x89, 0x0A};
143 BitstreamReader reader(bytes);
144 reader.ConsumeBits(4);
145
146 EXPECT_EQ(reader.Read<uint8_t>(), 0xABu);
147 EXPECT_EQ(reader.Read<uint8_t>(), 0xCDu);
148 EXPECT_EQ(reader.Read<uint16_t>(), 0xEF12u);
149 EXPECT_EQ(reader.Read<uint32_t>(), 0x34567890u);
150 EXPECT_TRUE(reader.Ok());
151 }
152
TEST(BitstreamReaderTest,ReadBytesOffset3)153 TEST(BitstreamReaderTest, ReadBytesOffset3) {
154 // The pattern we'll check against is counting down from 0b1111. It looks
155 // weird here because it's all offset by 3.
156 // Byte pattern is:
157 // 56701234
158 // 0b00011111,
159 // 0b11011011,
160 // 0b10010111,
161 // 0b01010011,
162 // 0b00001110,
163 // 0b11001010,
164 // 0b10000110,
165 // 0b01000010
166 // xxxxx <-- last 5 bits unused.
167
168 // The bytes. It almost looks like counting down by two at a time, except the
169 // jump at 5->3->0, since that's when the high bit is turned off.
170 const uint8_t bytes[] = {0x1F, 0xDB, 0x97, 0x53, 0x0E, 0xCA, 0x86, 0x42};
171
172 BitstreamReader reader(bytes);
173 reader.ConsumeBits(3);
174 EXPECT_EQ(reader.Read<uint8_t>(), 0xFEu);
175 EXPECT_EQ(reader.Read<uint16_t>(), 0xDCBAu);
176 EXPECT_EQ(reader.Read<uint32_t>(), 0x98765432u);
177 EXPECT_TRUE(reader.Ok());
178
179 // 5 bits left unread. Not enough to read a uint8_t.
180 EXPECT_EQ(reader.RemainingBitCount(), 5);
181 EXPECT_EQ(reader.Read<uint8_t>(), 0);
182 EXPECT_FALSE(reader.Ok());
183 }
184
TEST(BitstreamReaderTest,ReadBits)185 TEST(BitstreamReaderTest, ReadBits) {
186 const uint8_t bytes[] = {0b010'01'101, 0b0011'00'1'0};
187 BitstreamReader reader(bytes);
188 EXPECT_EQ(reader.ReadBits(3), 0b010u);
189 EXPECT_EQ(reader.ReadBits(2), 0b01u);
190 EXPECT_EQ(reader.ReadBits(7), 0b101'0011u);
191 EXPECT_EQ(reader.ReadBits(2), 0b00u);
192 EXPECT_EQ(reader.ReadBits(1), 0b1u);
193 EXPECT_EQ(reader.ReadBits(1), 0b0u);
194 EXPECT_TRUE(reader.Ok());
195
196 EXPECT_EQ(reader.ReadBits(1), 0u);
197 EXPECT_FALSE(reader.Ok());
198 }
199
TEST(BitstreamReaderTest,ReadZeroBits)200 TEST(BitstreamReaderTest, ReadZeroBits) {
201 BitstreamReader reader(rtc::ArrayView<const uint8_t>(nullptr, 0));
202
203 EXPECT_EQ(reader.ReadBits(0), 0u);
204 EXPECT_TRUE(reader.Ok());
205 }
206
TEST(BitstreamReaderTest,ReadBitFromEmptyArray)207 TEST(BitstreamReaderTest, ReadBitFromEmptyArray) {
208 BitstreamReader reader(rtc::ArrayView<const uint8_t>(nullptr, 0));
209
210 // Trying to read from the empty array shouldn't dereference the pointer,
211 // i.e. shouldn't crash.
212 EXPECT_EQ(reader.ReadBit(), 0);
213 EXPECT_FALSE(reader.Ok());
214 }
215
TEST(BitstreamReaderTest,ReadBitsFromEmptyArray)216 TEST(BitstreamReaderTest, ReadBitsFromEmptyArray) {
217 BitstreamReader reader(rtc::ArrayView<const uint8_t>(nullptr, 0));
218
219 // Trying to read from the empty array shouldn't dereference the pointer,
220 // i.e. shouldn't crash.
221 EXPECT_EQ(reader.ReadBits(1), 0u);
222 EXPECT_FALSE(reader.Ok());
223 }
224
TEST(BitstreamReaderTest,ReadBits64)225 TEST(BitstreamReaderTest, ReadBits64) {
226 const uint8_t bytes[] = {0x4D, 0x32, 0xAB, 0x54, 0x00, 0xFF, 0xFE, 0x01,
227 0xAB, 0xCD, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x89};
228 BitstreamReader reader(bytes);
229
230 EXPECT_EQ(reader.ReadBits(33), 0x4D32AB5400FFFE01u >> (64 - 33));
231
232 constexpr uint64_t kMask31Bits = (1ull << 32) - 1;
233 EXPECT_EQ(reader.ReadBits(31), 0x4D32AB5400FFFE01ull & kMask31Bits);
234
235 EXPECT_EQ(reader.ReadBits(64), 0xABCDEF0123456789ull);
236 EXPECT_TRUE(reader.Ok());
237
238 // Nothing more to read.
239 EXPECT_EQ(reader.ReadBit(), 0);
240 EXPECT_FALSE(reader.Ok());
241 }
242
TEST(BitstreamReaderTest,CanPeekBitsUsingCopyConstructor)243 TEST(BitstreamReaderTest, CanPeekBitsUsingCopyConstructor) {
244 // BitstreamReader doesn't have peek function. To simulate it, user may use
245 // cheap BitstreamReader copy constructor.
246 const uint8_t bytes[] = {0x0A, 0xBC};
247 BitstreamReader reader(bytes);
248 reader.ConsumeBits(4);
249 ASSERT_EQ(reader.RemainingBitCount(), 12);
250
251 BitstreamReader peeker = reader;
252 EXPECT_EQ(peeker.ReadBits(8), 0xABu);
253 EXPECT_EQ(peeker.RemainingBitCount(), 4);
254
255 EXPECT_EQ(reader.RemainingBitCount(), 12);
256 // Can resume reading from before peeker was created.
257 EXPECT_EQ(reader.ReadBits(4), 0xAu);
258 EXPECT_EQ(reader.RemainingBitCount(), 8);
259 }
260
TEST(BitstreamReaderTest,ReadNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2)261 TEST(BitstreamReaderTest,
262 ReadNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2) {
263 const uint8_t bytes[2] = {0xf3, 0xa0};
264 BitstreamReader reader(bytes);
265
266 ASSERT_EQ(reader.RemainingBitCount(), 16);
267 EXPECT_EQ(reader.ReadNonSymmetric(/*num_values=*/1 << 4), 0xfu);
268 EXPECT_EQ(reader.ReadNonSymmetric(/*num_values=*/1 << 4), 0x3u);
269 EXPECT_EQ(reader.ReadNonSymmetric(/*num_values=*/1 << 4), 0xau);
270 EXPECT_EQ(reader.ReadNonSymmetric(/*num_values=*/1 << 4), 0x0u);
271 EXPECT_EQ(reader.RemainingBitCount(), 0);
272 EXPECT_TRUE(reader.Ok());
273 }
274
TEST(BitstreamReaderTest,ReadNonSymmetricOnlyValueConsumesZeroBits)275 TEST(BitstreamReaderTest, ReadNonSymmetricOnlyValueConsumesZeroBits) {
276 const uint8_t bytes[2] = {};
277 BitstreamReader reader(bytes);
278
279 ASSERT_EQ(reader.RemainingBitCount(), 16);
280 EXPECT_EQ(reader.ReadNonSymmetric(/*num_values=*/1), 0u);
281 EXPECT_EQ(reader.RemainingBitCount(), 16);
282 }
283
GolombEncoded(uint32_t val)284 std::array<uint8_t, 8> GolombEncoded(uint32_t val) {
285 int val_width = absl::bit_width(val + 1);
286 int total_width = 2 * val_width - 1;
287 uint64_t representation = (uint64_t{val} + 1) << (64 - total_width);
288 std::array<uint8_t, 8> result;
289 for (int i = 0; i < 8; ++i) {
290 result[i] = representation >> (7 - i) * 8;
291 }
292 return result;
293 }
294
TEST(BitstreamReaderTest,GolombUint32Values)295 TEST(BitstreamReaderTest, GolombUint32Values) {
296 // Test over the uint32_t range with a large enough step that the test doesn't
297 // take forever. Around 20,000 iterations should do.
298 const int kStep = std::numeric_limits<uint32_t>::max() / 20000;
299 for (uint32_t i = 0; i < std::numeric_limits<uint32_t>::max() - kStep;
300 i += kStep) {
301 std::array<uint8_t, 8> buffer = GolombEncoded(i);
302 BitstreamReader reader(buffer);
303 // Use assert instead of EXPECT to avoid spamming thousands of failed
304 // expectation when this test fails.
305 ASSERT_EQ(reader.ReadExponentialGolomb(), i);
306 EXPECT_TRUE(reader.Ok());
307 }
308 }
309
TEST(BitstreamReaderTest,SignedGolombValues)310 TEST(BitstreamReaderTest, SignedGolombValues) {
311 uint8_t golomb_bits[][1] = {
312 {0b1'0000000}, {0b010'00000}, {0b011'00000}, {0b00100'000}, {0b00111'000},
313 };
314 int expected[] = {0, 1, -1, 2, -3};
315 for (size_t i = 0; i < sizeof(golomb_bits); ++i) {
316 BitstreamReader reader(golomb_bits[i]);
317 EXPECT_EQ(reader.ReadSignedExponentialGolomb(), expected[i])
318 << "Mismatch in expected/decoded value for golomb_bits[" << i
319 << "]: " << static_cast<int>(golomb_bits[i][0]);
320 EXPECT_TRUE(reader.Ok());
321 }
322 }
323
TEST(BitstreamReaderTest,NoGolombOverread)324 TEST(BitstreamReaderTest, NoGolombOverread) {
325 const uint8_t bytes[] = {0x00, 0xFF, 0xFF};
326 // Make sure the bit buffer correctly enforces byte length on golomb reads.
327 // If it didn't, the above buffer would be valid at 3 bytes.
328 BitstreamReader reader1(rtc::MakeArrayView(bytes, 1));
329 // When parse fails, `ReadExponentialGolomb` may return any number.
330 reader1.ReadExponentialGolomb();
331 EXPECT_FALSE(reader1.Ok());
332
333 BitstreamReader reader2(rtc::MakeArrayView(bytes, 2));
334 reader2.ReadExponentialGolomb();
335 EXPECT_FALSE(reader2.Ok());
336
337 BitstreamReader reader3(bytes);
338 // Golomb should have read 9 bits, so 0x01FF, and since it is golomb, the
339 // result is 0x01FF - 1 = 0x01FE.
340 EXPECT_EQ(reader3.ReadExponentialGolomb(), 0x01FEu);
341 EXPECT_TRUE(reader3.Ok());
342 }
343
344 } // namespace
345 } // namespace webrtc
346