1 /*
2 * Copyright 2015 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/bit_buffer.h"
12
13 #include <limits>
14
15 #include "rtc_base/arraysize.h"
16 #include "rtc_base/byte_buffer.h"
17 #include "test/gmock.h"
18 #include "test/gtest.h"
19
20 namespace rtc {
21
22 using ::testing::ElementsAre;
23
TEST(BitBufferTest,ConsumeBits)24 TEST(BitBufferTest, ConsumeBits) {
25 const uint8_t bytes[64] = {0};
26 BitBuffer buffer(bytes, 32);
27 uint64_t total_bits = 32 * 8;
28 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
29 EXPECT_TRUE(buffer.ConsumeBits(3));
30 total_bits -= 3;
31 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
32 EXPECT_TRUE(buffer.ConsumeBits(3));
33 total_bits -= 3;
34 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
35 EXPECT_TRUE(buffer.ConsumeBits(15));
36 total_bits -= 15;
37 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
38 EXPECT_TRUE(buffer.ConsumeBits(37));
39 total_bits -= 37;
40 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
41
42 EXPECT_FALSE(buffer.ConsumeBits(32 * 8));
43 EXPECT_EQ(total_bits, buffer.RemainingBitCount());
44 }
45
TEST(BitBufferTest,ReadBytesAligned)46 TEST(BitBufferTest, ReadBytesAligned) {
47 const uint8_t bytes[] = {0x0A, 0xBC, 0xDE, 0xF1, 0x23, 0x45, 0x67, 0x89};
48 uint8_t val8;
49 uint16_t val16;
50 uint32_t val32;
51 BitBuffer buffer(bytes, 8);
52 EXPECT_TRUE(buffer.ReadUInt8(&val8));
53 EXPECT_EQ(0x0Au, val8);
54 EXPECT_TRUE(buffer.ReadUInt8(&val8));
55 EXPECT_EQ(0xBCu, val8);
56 EXPECT_TRUE(buffer.ReadUInt16(&val16));
57 EXPECT_EQ(0xDEF1u, val16);
58 EXPECT_TRUE(buffer.ReadUInt32(&val32));
59 EXPECT_EQ(0x23456789u, val32);
60 }
61
TEST(BitBufferTest,ReadBytesOffset4)62 TEST(BitBufferTest, ReadBytesOffset4) {
63 const uint8_t bytes[] = {0x0A, 0xBC, 0xDE, 0xF1, 0x23,
64 0x45, 0x67, 0x89, 0x0A};
65 uint8_t val8;
66 uint16_t val16;
67 uint32_t val32;
68 BitBuffer buffer(bytes, 9);
69 EXPECT_TRUE(buffer.ConsumeBits(4));
70
71 EXPECT_TRUE(buffer.ReadUInt8(&val8));
72 EXPECT_EQ(0xABu, val8);
73 EXPECT_TRUE(buffer.ReadUInt8(&val8));
74 EXPECT_EQ(0xCDu, val8);
75 EXPECT_TRUE(buffer.ReadUInt16(&val16));
76 EXPECT_EQ(0xEF12u, val16);
77 EXPECT_TRUE(buffer.ReadUInt32(&val32));
78 EXPECT_EQ(0x34567890u, val32);
79 }
80
TEST(BitBufferTest,ReadBytesOffset3)81 TEST(BitBufferTest, ReadBytesOffset3) {
82 // The pattern we'll check against is counting down from 0b1111. It looks
83 // weird here because it's all offset by 3.
84 // Byte pattern is:
85 // 56701234
86 // 0b00011111,
87 // 0b11011011,
88 // 0b10010111,
89 // 0b01010011,
90 // 0b00001110,
91 // 0b11001010,
92 // 0b10000110,
93 // 0b01000010
94 // xxxxx <-- last 5 bits unused.
95
96 // The bytes. It almost looks like counting down by two at a time, except the
97 // jump at 5->3->0, since that's when the high bit is turned off.
98 const uint8_t bytes[] = {0x1F, 0xDB, 0x97, 0x53, 0x0E, 0xCA, 0x86, 0x42};
99
100 uint8_t val8;
101 uint16_t val16;
102 uint32_t val32;
103 BitBuffer buffer(bytes, 8);
104 EXPECT_TRUE(buffer.ConsumeBits(3));
105 EXPECT_TRUE(buffer.ReadUInt8(&val8));
106 EXPECT_EQ(0xFEu, val8);
107 EXPECT_TRUE(buffer.ReadUInt16(&val16));
108 EXPECT_EQ(0xDCBAu, val16);
109 EXPECT_TRUE(buffer.ReadUInt32(&val32));
110 EXPECT_EQ(0x98765432u, val32);
111 // 5 bits left unread. Not enough to read a uint8_t.
112 EXPECT_EQ(5u, buffer.RemainingBitCount());
113 EXPECT_FALSE(buffer.ReadUInt8(&val8));
114 }
115
TEST(BitBufferTest,ReadBits)116 TEST(BitBufferTest, ReadBits) {
117 // Bit values are:
118 // 0b01001101,
119 // 0b00110010
120 const uint8_t bytes[] = {0x4D, 0x32};
121 uint32_t val;
122 BitBuffer buffer(bytes, 2);
123 EXPECT_TRUE(buffer.ReadBits(&val, 3));
124 // 0b010
125 EXPECT_EQ(0x2u, val);
126 EXPECT_TRUE(buffer.ReadBits(&val, 2));
127 // 0b01
128 EXPECT_EQ(0x1u, val);
129 EXPECT_TRUE(buffer.ReadBits(&val, 7));
130 // 0b1010011
131 EXPECT_EQ(0x53u, val);
132 EXPECT_TRUE(buffer.ReadBits(&val, 2));
133 // 0b00
134 EXPECT_EQ(0x0u, val);
135 EXPECT_TRUE(buffer.ReadBits(&val, 1));
136 // 0b1
137 EXPECT_EQ(0x1u, val);
138 EXPECT_TRUE(buffer.ReadBits(&val, 1));
139 // 0b0
140 EXPECT_EQ(0x0u, val);
141
142 EXPECT_FALSE(buffer.ReadBits(&val, 1));
143 }
144
TEST(BitBufferDeathTest,SetOffsetValues)145 TEST(BitBufferDeathTest, SetOffsetValues) {
146 uint8_t bytes[4] = {0};
147 BitBufferWriter buffer(bytes, 4);
148
149 size_t byte_offset, bit_offset;
150 // Bit offsets are [0,7].
151 EXPECT_TRUE(buffer.Seek(0, 0));
152 EXPECT_TRUE(buffer.Seek(0, 7));
153 buffer.GetCurrentOffset(&byte_offset, &bit_offset);
154 EXPECT_EQ(0u, byte_offset);
155 EXPECT_EQ(7u, bit_offset);
156 EXPECT_FALSE(buffer.Seek(0, 8));
157 buffer.GetCurrentOffset(&byte_offset, &bit_offset);
158 EXPECT_EQ(0u, byte_offset);
159 EXPECT_EQ(7u, bit_offset);
160 // Byte offsets are [0,length]. At byte offset length, the bit offset must be
161 // 0.
162 EXPECT_TRUE(buffer.Seek(0, 0));
163 EXPECT_TRUE(buffer.Seek(2, 4));
164 buffer.GetCurrentOffset(&byte_offset, &bit_offset);
165 EXPECT_EQ(2u, byte_offset);
166 EXPECT_EQ(4u, bit_offset);
167 EXPECT_TRUE(buffer.Seek(4, 0));
168 EXPECT_FALSE(buffer.Seek(5, 0));
169 buffer.GetCurrentOffset(&byte_offset, &bit_offset);
170 EXPECT_EQ(4u, byte_offset);
171 EXPECT_EQ(0u, bit_offset);
172 EXPECT_FALSE(buffer.Seek(4, 1));
173
174 // Disable death test on Android because it relies on fork() and doesn't play
175 // nicely.
176 #if GTEST_HAS_DEATH_TEST
177 #if !defined(WEBRTC_ANDROID)
178 // Passing a null out parameter is death.
179 EXPECT_DEATH(buffer.GetCurrentOffset(&byte_offset, nullptr), "");
180 #endif
181 #endif
182 }
183
TEST(BitBufferTest,ReadNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2)184 TEST(BitBufferTest, ReadNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2) {
185 const uint8_t bytes[2] = {0xf3, 0xa0};
186 BitBuffer reader(bytes, 2);
187
188 uint32_t values[4];
189 ASSERT_EQ(reader.RemainingBitCount(), 16u);
190 EXPECT_TRUE(reader.ReadNonSymmetric(&values[0], /*num_values=*/1 << 4));
191 EXPECT_TRUE(reader.ReadNonSymmetric(&values[1], /*num_values=*/1 << 4));
192 EXPECT_TRUE(reader.ReadNonSymmetric(&values[2], /*num_values=*/1 << 4));
193 EXPECT_TRUE(reader.ReadNonSymmetric(&values[3], /*num_values=*/1 << 4));
194 ASSERT_EQ(reader.RemainingBitCount(), 0u);
195
196 EXPECT_THAT(values, ElementsAre(0xf, 0x3, 0xa, 0x0));
197 }
198
TEST(BitBufferWriterTest,WriteNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2)199 TEST(BitBufferWriterTest,
200 WriteNonSymmetricSameNumberOfBitsWhenNumValuesPowerOf2) {
201 uint8_t bytes[2] = {};
202 BitBufferWriter writer(bytes, 2);
203
204 ASSERT_EQ(writer.RemainingBitCount(), 16u);
205 EXPECT_TRUE(writer.WriteNonSymmetric(0xf, /*num_values=*/1 << 4));
206 ASSERT_EQ(writer.RemainingBitCount(), 12u);
207 EXPECT_TRUE(writer.WriteNonSymmetric(0x3, /*num_values=*/1 << 4));
208 ASSERT_EQ(writer.RemainingBitCount(), 8u);
209 EXPECT_TRUE(writer.WriteNonSymmetric(0xa, /*num_values=*/1 << 4));
210 ASSERT_EQ(writer.RemainingBitCount(), 4u);
211 EXPECT_TRUE(writer.WriteNonSymmetric(0x0, /*num_values=*/1 << 4));
212 ASSERT_EQ(writer.RemainingBitCount(), 0u);
213
214 EXPECT_THAT(bytes, ElementsAre(0xf3, 0xa0));
215 }
216
TEST(BitBufferWriterTest,NonSymmetricReadsMatchesWrites)217 TEST(BitBufferWriterTest, NonSymmetricReadsMatchesWrites) {
218 uint8_t bytes[2] = {};
219 BitBufferWriter writer(bytes, 2);
220
221 EXPECT_EQ(BitBufferWriter::SizeNonSymmetricBits(/*val=*/1, /*num_values=*/6),
222 2u);
223 EXPECT_EQ(BitBufferWriter::SizeNonSymmetricBits(/*val=*/2, /*num_values=*/6),
224 3u);
225 // Values [0, 1] can fit into two bit.
226 ASSERT_EQ(writer.RemainingBitCount(), 16u);
227 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/0, /*num_values=*/6));
228 ASSERT_EQ(writer.RemainingBitCount(), 14u);
229 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/1, /*num_values=*/6));
230 ASSERT_EQ(writer.RemainingBitCount(), 12u);
231 // Values [2, 5] require 3 bits.
232 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/2, /*num_values=*/6));
233 ASSERT_EQ(writer.RemainingBitCount(), 9u);
234 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/3, /*num_values=*/6));
235 ASSERT_EQ(writer.RemainingBitCount(), 6u);
236 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/4, /*num_values=*/6));
237 ASSERT_EQ(writer.RemainingBitCount(), 3u);
238 EXPECT_TRUE(writer.WriteNonSymmetric(/*val=*/5, /*num_values=*/6));
239 ASSERT_EQ(writer.RemainingBitCount(), 0u);
240
241 // Bit values are
242 // 00.01.100.101.110.111 = 00011001|01110111 = 0x19|77
243 EXPECT_THAT(bytes, ElementsAre(0x19, 0x77));
244
245 rtc::BitBuffer reader(bytes, 2);
246 uint32_t values[6];
247 EXPECT_TRUE(reader.ReadNonSymmetric(&values[0], /*num_values=*/6));
248 EXPECT_TRUE(reader.ReadNonSymmetric(&values[1], /*num_values=*/6));
249 EXPECT_TRUE(reader.ReadNonSymmetric(&values[2], /*num_values=*/6));
250 EXPECT_TRUE(reader.ReadNonSymmetric(&values[3], /*num_values=*/6));
251 EXPECT_TRUE(reader.ReadNonSymmetric(&values[4], /*num_values=*/6));
252 EXPECT_TRUE(reader.ReadNonSymmetric(&values[5], /*num_values=*/6));
253
254 EXPECT_THAT(values, ElementsAre(0, 1, 2, 3, 4, 5));
255 }
256
TEST(BitBufferTest,ReadNonSymmetricOnlyValueConsumesNoBits)257 TEST(BitBufferTest, ReadNonSymmetricOnlyValueConsumesNoBits) {
258 const uint8_t bytes[2] = {};
259 BitBuffer reader(bytes, 2);
260 uint32_t value = 0xFFFFFFFF;
261 ASSERT_EQ(reader.RemainingBitCount(), 16u);
262
263 EXPECT_TRUE(reader.ReadNonSymmetric(&value, /*num_values=*/1));
264
265 EXPECT_EQ(value, 0u);
266 EXPECT_EQ(reader.RemainingBitCount(), 16u);
267 }
268
TEST(BitBufferWriterTest,WriteNonSymmetricOnlyValueConsumesNoBits)269 TEST(BitBufferWriterTest, WriteNonSymmetricOnlyValueConsumesNoBits) {
270 uint8_t bytes[2] = {};
271 BitBufferWriter writer(bytes, 2);
272 ASSERT_EQ(writer.RemainingBitCount(), 16u);
273
274 EXPECT_TRUE(writer.WriteNonSymmetric(0, /*num_values=*/1));
275
276 EXPECT_EQ(writer.RemainingBitCount(), 16u);
277 }
278
GolombEncoded(uint32_t val)279 uint64_t GolombEncoded(uint32_t val) {
280 val++;
281 uint32_t bit_counter = val;
282 uint64_t bit_count = 0;
283 while (bit_counter > 0) {
284 bit_count++;
285 bit_counter >>= 1;
286 }
287 return static_cast<uint64_t>(val) << (64 - (bit_count * 2 - 1));
288 }
289
TEST(BitBufferTest,GolombUint32Values)290 TEST(BitBufferTest, GolombUint32Values) {
291 ByteBufferWriter byteBuffer;
292 byteBuffer.Resize(16);
293 BitBuffer buffer(reinterpret_cast<const uint8_t*>(byteBuffer.Data()),
294 byteBuffer.Capacity());
295 // Test over the uint32_t range with a large enough step that the test doesn't
296 // take forever. Around 20,000 iterations should do.
297 const int kStep = std::numeric_limits<uint32_t>::max() / 20000;
298 for (uint32_t i = 0; i < std::numeric_limits<uint32_t>::max() - kStep;
299 i += kStep) {
300 uint64_t encoded_val = GolombEncoded(i);
301 byteBuffer.Clear();
302 byteBuffer.WriteUInt64(encoded_val);
303 uint32_t decoded_val;
304 EXPECT_TRUE(buffer.Seek(0, 0));
305 EXPECT_TRUE(buffer.ReadExponentialGolomb(&decoded_val));
306 EXPECT_EQ(i, decoded_val);
307 }
308 }
309
TEST(BitBufferTest,SignedGolombValues)310 TEST(BitBufferTest, SignedGolombValues) {
311 uint8_t golomb_bits[] = {
312 0x80, // 1
313 0x40, // 010
314 0x60, // 011
315 0x20, // 00100
316 0x38, // 00111
317 };
318 int32_t expected[] = {0, 1, -1, 2, -3};
319 for (size_t i = 0; i < sizeof(golomb_bits); ++i) {
320 BitBuffer buffer(&golomb_bits[i], 1);
321 int32_t decoded_val;
322 ASSERT_TRUE(buffer.ReadSignedExponentialGolomb(&decoded_val));
323 EXPECT_EQ(expected[i], decoded_val)
324 << "Mismatch in expected/decoded value for golomb_bits[" << i
325 << "]: " << static_cast<int>(golomb_bits[i]);
326 }
327 }
328
TEST(BitBufferTest,NoGolombOverread)329 TEST(BitBufferTest, NoGolombOverread) {
330 const uint8_t bytes[] = {0x00, 0xFF, 0xFF};
331 // Make sure the bit buffer correctly enforces byte length on golomb reads.
332 // If it didn't, the above buffer would be valid at 3 bytes.
333 BitBuffer buffer(bytes, 1);
334 uint32_t decoded_val;
335 EXPECT_FALSE(buffer.ReadExponentialGolomb(&decoded_val));
336
337 BitBuffer longer_buffer(bytes, 2);
338 EXPECT_FALSE(longer_buffer.ReadExponentialGolomb(&decoded_val));
339
340 BitBuffer longest_buffer(bytes, 3);
341 EXPECT_TRUE(longest_buffer.ReadExponentialGolomb(&decoded_val));
342 // Golomb should have read 9 bits, so 0x01FF, and since it is golomb, the
343 // result is 0x01FF - 1 = 0x01FE.
344 EXPECT_EQ(0x01FEu, decoded_val);
345 }
346
TEST(BitBufferWriterTest,SymmetricReadWrite)347 TEST(BitBufferWriterTest, SymmetricReadWrite) {
348 uint8_t bytes[16] = {0};
349 BitBufferWriter buffer(bytes, 4);
350
351 // Write some bit data at various sizes.
352 EXPECT_TRUE(buffer.WriteBits(0x2u, 3));
353 EXPECT_TRUE(buffer.WriteBits(0x1u, 2));
354 EXPECT_TRUE(buffer.WriteBits(0x53u, 7));
355 EXPECT_TRUE(buffer.WriteBits(0x0u, 2));
356 EXPECT_TRUE(buffer.WriteBits(0x1u, 1));
357 EXPECT_TRUE(buffer.WriteBits(0x1ABCDu, 17));
358 // That should be all that fits in the buffer.
359 EXPECT_FALSE(buffer.WriteBits(1, 1));
360
361 EXPECT_TRUE(buffer.Seek(0, 0));
362 uint32_t val;
363 EXPECT_TRUE(buffer.ReadBits(&val, 3));
364 EXPECT_EQ(0x2u, val);
365 EXPECT_TRUE(buffer.ReadBits(&val, 2));
366 EXPECT_EQ(0x1u, val);
367 EXPECT_TRUE(buffer.ReadBits(&val, 7));
368 EXPECT_EQ(0x53u, val);
369 EXPECT_TRUE(buffer.ReadBits(&val, 2));
370 EXPECT_EQ(0x0u, val);
371 EXPECT_TRUE(buffer.ReadBits(&val, 1));
372 EXPECT_EQ(0x1u, val);
373 EXPECT_TRUE(buffer.ReadBits(&val, 17));
374 EXPECT_EQ(0x1ABCDu, val);
375 // And there should be nothing left.
376 EXPECT_FALSE(buffer.ReadBits(&val, 1));
377 }
378
TEST(BitBufferWriterTest,SymmetricBytesMisaligned)379 TEST(BitBufferWriterTest, SymmetricBytesMisaligned) {
380 uint8_t bytes[16] = {0};
381 BitBufferWriter buffer(bytes, 16);
382
383 // Offset 3, to get things misaligned.
384 EXPECT_TRUE(buffer.ConsumeBits(3));
385 EXPECT_TRUE(buffer.WriteUInt8(0x12u));
386 EXPECT_TRUE(buffer.WriteUInt16(0x3456u));
387 EXPECT_TRUE(buffer.WriteUInt32(0x789ABCDEu));
388
389 buffer.Seek(0, 3);
390 uint8_t val8;
391 uint16_t val16;
392 uint32_t val32;
393 EXPECT_TRUE(buffer.ReadUInt8(&val8));
394 EXPECT_EQ(0x12u, val8);
395 EXPECT_TRUE(buffer.ReadUInt16(&val16));
396 EXPECT_EQ(0x3456u, val16);
397 EXPECT_TRUE(buffer.ReadUInt32(&val32));
398 EXPECT_EQ(0x789ABCDEu, val32);
399 }
400
TEST(BitBufferWriterTest,SymmetricGolomb)401 TEST(BitBufferWriterTest, SymmetricGolomb) {
402 char test_string[] = "my precious";
403 uint8_t bytes[64] = {0};
404 BitBufferWriter buffer(bytes, 64);
405 for (size_t i = 0; i < arraysize(test_string); ++i) {
406 EXPECT_TRUE(buffer.WriteExponentialGolomb(test_string[i]));
407 }
408 buffer.Seek(0, 0);
409 for (size_t i = 0; i < arraysize(test_string); ++i) {
410 uint32_t val;
411 EXPECT_TRUE(buffer.ReadExponentialGolomb(&val));
412 EXPECT_LE(val, std::numeric_limits<uint8_t>::max());
413 EXPECT_EQ(test_string[i], static_cast<char>(val));
414 }
415 }
416
TEST(BitBufferWriterTest,WriteClearsBits)417 TEST(BitBufferWriterTest, WriteClearsBits) {
418 uint8_t bytes[] = {0xFF, 0xFF};
419 BitBufferWriter buffer(bytes, 2);
420 EXPECT_TRUE(buffer.ConsumeBits(3));
421 EXPECT_TRUE(buffer.WriteBits(0, 1));
422 EXPECT_EQ(0xEFu, bytes[0]);
423 EXPECT_TRUE(buffer.WriteBits(0, 3));
424 EXPECT_EQ(0xE1u, bytes[0]);
425 EXPECT_TRUE(buffer.WriteBits(0, 2));
426 EXPECT_EQ(0xE0u, bytes[0]);
427 EXPECT_EQ(0x7F, bytes[1]);
428 }
429
430 } // namespace rtc
431