1 // Copyright (c) 2017 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <sstream>
16 #include <string>
17 #include <vector>
18
19 #include "gmock/gmock.h"
20 #include "util/bit_stream.h"
21
22 namespace {
23
24 using spvutils::BitWriterInterface;
25 using spvutils::BitReaderInterface;
26 using spvutils::BitWriterWord64;
27 using spvutils::BitReaderWord64;
28 using spvutils::StreamToBuffer;
29 using spvutils::BufferToStream;
30 using spvutils::NumBitsToNumWords;
31 using spvutils::PadToWord;
32 using spvutils::StreamToBitset;
33 using spvutils::BitsetToStream;
34 using spvutils::BitsToStream;
35 using spvutils::StreamToBits;
36 using spvutils::GetLowerBits;
37 using spvutils::EncodeZigZag;
38 using spvutils::DecodeZigZag;
39 using spvutils::Log2U64;
40
41 // A simple and inefficient implementatition of BitWriterInterface,
42 // using std::stringstream. Intended for tests only.
43 class BitWriterStringStream : public BitWriterInterface {
44 public:
WriteStream(const std::string & bits)45 void WriteStream(const std::string& bits) override {
46 ss_ << bits;
47 }
48
WriteBits(uint64_t bits,size_t num_bits)49 void WriteBits(uint64_t bits, size_t num_bits) override {
50 assert(num_bits <= 64);
51 ss_ << BitsToStream(bits, num_bits);
52 }
53
GetNumBits() const54 size_t GetNumBits() const override {
55 return ss_.str().size();
56 }
57
GetDataCopy() const58 std::vector<uint8_t> GetDataCopy() const override {
59 return StreamToBuffer<uint8_t>(ss_.str());
60 }
61
GetStreamRaw() const62 std::string GetStreamRaw() const {
63 return ss_.str();
64 }
65
66 private:
67 std::stringstream ss_;
68 };
69
70 // A simple and inefficient implementatition of BitReaderInterface.
71 // Intended for tests only.
72 class BitReaderFromString : public BitReaderInterface {
73 public:
BitReaderFromString(std::string && str)74 explicit BitReaderFromString(std::string&& str)
75 : str_(std::move(str)), pos_(0) {}
76
BitReaderFromString(const std::vector<uint64_t> & buffer)77 explicit BitReaderFromString(const std::vector<uint64_t>& buffer)
78 : str_(BufferToStream(buffer)), pos_(0) {}
79
BitReaderFromString(const std::vector<uint8_t> & buffer)80 explicit BitReaderFromString(const std::vector<uint8_t>& buffer)
81 : str_(PadToWord<64>(BufferToStream(buffer))), pos_(0) {}
82
ReadBits(uint64_t * bits,size_t num_bits)83 size_t ReadBits(uint64_t* bits, size_t num_bits) override {
84 if (ReachedEnd())
85 return 0;
86 std::string sub = str_.substr(pos_, num_bits);
87 *bits = StreamToBits(sub);
88 pos_ += sub.length();
89 return sub.length();
90 }
91
GetNumReadBits() const92 size_t GetNumReadBits() const override {
93 return pos_;
94 }
95
ReachedEnd() const96 bool ReachedEnd() const override {
97 return pos_ >= str_.length();
98 }
99
GetStreamPadded64() const100 const std::string& GetStreamPadded64() const {
101 return str_;
102 }
103
104 private:
105 std::string str_;
106 size_t pos_;
107 };
108
TEST(Log2U16,Test)109 TEST(Log2U16, Test) {
110 EXPECT_EQ(0u, Log2U64(0));
111 EXPECT_EQ(0u, Log2U64(1));
112 EXPECT_EQ(1u, Log2U64(2));
113 EXPECT_EQ(1u, Log2U64(3));
114 EXPECT_EQ(2u, Log2U64(4));
115 EXPECT_EQ(2u, Log2U64(5));
116 EXPECT_EQ(2u, Log2U64(6));
117 EXPECT_EQ(2u, Log2U64(7));
118 EXPECT_EQ(3u, Log2U64(8));
119 EXPECT_EQ(3u, Log2U64(9));
120 EXPECT_EQ(3u, Log2U64(10));
121 EXPECT_EQ(3u, Log2U64(11));
122 EXPECT_EQ(3u, Log2U64(12));
123 EXPECT_EQ(3u, Log2U64(13));
124 EXPECT_EQ(3u, Log2U64(14));
125 EXPECT_EQ(3u, Log2U64(15));
126 EXPECT_EQ(4u, Log2U64(16));
127 EXPECT_EQ(4u, Log2U64(17));
128 EXPECT_EQ(5u, Log2U64(35));
129 EXPECT_EQ(6u, Log2U64(72));
130 EXPECT_EQ(7u, Log2U64(255));
131 EXPECT_EQ(8u, Log2U64(256));
132 EXPECT_EQ(15u, Log2U64(65535));
133 EXPECT_EQ(16u, Log2U64(65536));
134 EXPECT_EQ(19u, Log2U64(0xFFFFF));
135 EXPECT_EQ(23u, Log2U64(0xFFFFFF));
136 EXPECT_EQ(27u, Log2U64(0xFFFFFFF));
137 EXPECT_EQ(31u, Log2U64(0xFFFFFFFF));
138 EXPECT_EQ(35u, Log2U64(0xFFFFFFFFF));
139 EXPECT_EQ(39u, Log2U64(0xFFFFFFFFFF));
140 EXPECT_EQ(43u, Log2U64(0xFFFFFFFFFFF));
141 EXPECT_EQ(47u, Log2U64(0xFFFFFFFFFFFF));
142 EXPECT_EQ(51u, Log2U64(0xFFFFFFFFFFFFF));
143 EXPECT_EQ(55u, Log2U64(0xFFFFFFFFFFFFFF));
144 EXPECT_EQ(59u, Log2U64(0xFFFFFFFFFFFFFFF));
145 EXPECT_EQ(63u, Log2U64(0xFFFFFFFFFFFFFFFF));
146 }
147
TEST(NumBitsToNumWords,Word8)148 TEST(NumBitsToNumWords, Word8) {
149 EXPECT_EQ(0u, NumBitsToNumWords<8>(0));
150 EXPECT_EQ(1u, NumBitsToNumWords<8>(1));
151 EXPECT_EQ(1u, NumBitsToNumWords<8>(7));
152 EXPECT_EQ(1u, NumBitsToNumWords<8>(8));
153 EXPECT_EQ(2u, NumBitsToNumWords<8>(9));
154 EXPECT_EQ(2u, NumBitsToNumWords<8>(16));
155 EXPECT_EQ(3u, NumBitsToNumWords<8>(17));
156 EXPECT_EQ(3u, NumBitsToNumWords<8>(23));
157 EXPECT_EQ(3u, NumBitsToNumWords<8>(24));
158 EXPECT_EQ(4u, NumBitsToNumWords<8>(25));
159 }
160
TEST(NumBitsToNumWords,Word64)161 TEST(NumBitsToNumWords, Word64) {
162 EXPECT_EQ(0u, NumBitsToNumWords<64>(0));
163 EXPECT_EQ(1u, NumBitsToNumWords<64>(1));
164 EXPECT_EQ(1u, NumBitsToNumWords<64>(64));
165 EXPECT_EQ(2u, NumBitsToNumWords<64>(65));
166 EXPECT_EQ(2u, NumBitsToNumWords<64>(128));
167 EXPECT_EQ(3u, NumBitsToNumWords<64>(129));
168 }
169
TEST(ZigZagCoding,Encode)170 TEST(ZigZagCoding, Encode) {
171 EXPECT_EQ(0u, EncodeZigZag(0));
172 EXPECT_EQ(1u, EncodeZigZag(-1));
173 EXPECT_EQ(2u, EncodeZigZag(1));
174 EXPECT_EQ(3u, EncodeZigZag(-2));
175 EXPECT_EQ(4u, EncodeZigZag(2));
176 EXPECT_EQ(5u, EncodeZigZag(-3));
177 EXPECT_EQ(6u, EncodeZigZag(3));
178 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
179 EncodeZigZag(std::numeric_limits<int64_t>::max()));
180 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
181 EncodeZigZag(std::numeric_limits<int64_t>::min()));
182 }
183
TEST(ZigZagCoding,Decode)184 TEST(ZigZagCoding, Decode) {
185 EXPECT_EQ(0, DecodeZigZag(0));
186 EXPECT_EQ(-1, DecodeZigZag(1));
187 EXPECT_EQ(1, DecodeZigZag(2));
188 EXPECT_EQ(-2, DecodeZigZag(3));
189 EXPECT_EQ(2, DecodeZigZag(4));
190 EXPECT_EQ(-3, DecodeZigZag(5));
191 EXPECT_EQ(3, DecodeZigZag(6));
192 EXPECT_EQ(std::numeric_limits<int64_t>::min(),
193 DecodeZigZag(std::numeric_limits<uint64_t>::max()));
194 EXPECT_EQ(std::numeric_limits<int64_t>::max(),
195 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1));
196 }
197
TEST(ZigZagCoding,Encode0)198 TEST(ZigZagCoding, Encode0) {
199 EXPECT_EQ(0u, EncodeZigZag(0, 0));
200 EXPECT_EQ(1u, EncodeZigZag(-1, 0));
201 EXPECT_EQ(2u, EncodeZigZag(1, 0));
202 EXPECT_EQ(3u, EncodeZigZag(-2, 0));
203 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
204 EncodeZigZag(std::numeric_limits<int64_t>::max(), 0));
205 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
206 EncodeZigZag(std::numeric_limits<int64_t>::min(), 0));
207 }
208
TEST(ZigZagCoding,Decode0)209 TEST(ZigZagCoding, Decode0) {
210 EXPECT_EQ(0, DecodeZigZag(0, 0));
211 EXPECT_EQ(-1, DecodeZigZag(1, 0));
212 EXPECT_EQ(1, DecodeZigZag(2, 0));
213 EXPECT_EQ(-2, DecodeZigZag(3, 0));
214 EXPECT_EQ(std::numeric_limits<int64_t>::min(),
215 DecodeZigZag(std::numeric_limits<uint64_t>::max(), 0));
216 EXPECT_EQ(std::numeric_limits<int64_t>::max(),
217 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 0));
218 }
219
TEST(ZigZagCoding,Decode0SameAsNormalZigZag)220 TEST(ZigZagCoding, Decode0SameAsNormalZigZag) {
221 for (int32_t i = -10000; i < 10000; i += 123) {
222 ASSERT_EQ(DecodeZigZag(i), DecodeZigZag(i, 0));
223 }
224 }
225
TEST(ZigZagCoding,Encode0SameAsNormalZigZag)226 TEST(ZigZagCoding, Encode0SameAsNormalZigZag) {
227 for (uint32_t i = 0; i < 10000; i += 123) {
228 ASSERT_EQ(EncodeZigZag(i), EncodeZigZag(i, 0));
229 }
230 }
231
TEST(ZigZagCoding,Encode1)232 TEST(ZigZagCoding, Encode1) {
233 EXPECT_EQ(0u, EncodeZigZag(0, 1));
234 EXPECT_EQ(1u, EncodeZigZag(1, 1));
235 EXPECT_EQ(2u, EncodeZigZag(-1, 1));
236 EXPECT_EQ(3u, EncodeZigZag(-2, 1));
237 EXPECT_EQ(4u, EncodeZigZag(2, 1));
238 EXPECT_EQ(5u, EncodeZigZag(3, 1));
239 EXPECT_EQ(6u, EncodeZigZag(-3, 1));
240 EXPECT_EQ(7u, EncodeZigZag(-4, 1));
241 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 2,
242 EncodeZigZag(std::numeric_limits<int64_t>::max(), 1));
243 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
244 EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 1));
245 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
246 EncodeZigZag(std::numeric_limits<int64_t>::min(), 1));
247 }
248
TEST(ZigZagCoding,Decode1)249 TEST(ZigZagCoding, Decode1) {
250 EXPECT_EQ(0, DecodeZigZag(0, 1));
251 EXPECT_EQ(1, DecodeZigZag(1, 1));
252 EXPECT_EQ(-1, DecodeZigZag(2, 1));
253 EXPECT_EQ(-2, DecodeZigZag(3, 1));
254 EXPECT_EQ(2, DecodeZigZag(4, 1));
255 EXPECT_EQ(3, DecodeZigZag(5, 1));
256 EXPECT_EQ(-3, DecodeZigZag(6, 1));
257 EXPECT_EQ(-4, DecodeZigZag(7, 1));
258 EXPECT_EQ(std::numeric_limits<int64_t>::min(),
259 DecodeZigZag(std::numeric_limits<uint64_t>::max(), 1));
260 EXPECT_EQ(std::numeric_limits<int64_t>::min() + 1,
261 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 1));
262 EXPECT_EQ(std::numeric_limits<int64_t>::max(),
263 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 2, 1));
264 }
265
TEST(ZigZagCoding,Encode2)266 TEST(ZigZagCoding, Encode2) {
267 EXPECT_EQ(0u, EncodeZigZag(0, 2));
268 EXPECT_EQ(1u, EncodeZigZag(1, 2));
269 EXPECT_EQ(2u, EncodeZigZag(2, 2));
270 EXPECT_EQ(3u, EncodeZigZag(3, 2));
271 EXPECT_EQ(4u, EncodeZigZag(-1, 2));
272 EXPECT_EQ(5u, EncodeZigZag(-2, 2));
273 EXPECT_EQ(6u, EncodeZigZag(-3, 2));
274 EXPECT_EQ(7u, EncodeZigZag(-4, 2));
275 EXPECT_EQ(8u, EncodeZigZag(4, 2));
276 EXPECT_EQ(9u, EncodeZigZag(5, 2));
277 EXPECT_EQ(10u, EncodeZigZag(6, 2));
278 EXPECT_EQ(11u, EncodeZigZag(7, 2));
279 EXPECT_EQ(12u, EncodeZigZag(-5, 2));
280 EXPECT_EQ(13u, EncodeZigZag(-6, 2));
281 EXPECT_EQ(14u, EncodeZigZag(-7, 2));
282 EXPECT_EQ(15u, EncodeZigZag(-8, 2));
283 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 4,
284 EncodeZigZag(std::numeric_limits<int64_t>::max(), 2));
285 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 3,
286 EncodeZigZag(std::numeric_limits<int64_t>::min() + 3, 2));
287 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 2,
288 EncodeZigZag(std::numeric_limits<int64_t>::min() + 2, 2));
289 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
290 EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 2));
291 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
292 EncodeZigZag(std::numeric_limits<int64_t>::min(), 2));
293 }
294
TEST(ZigZagCoding,Decode2)295 TEST(ZigZagCoding, Decode2) {
296 EXPECT_EQ(0, DecodeZigZag(0, 2));
297 EXPECT_EQ(1, DecodeZigZag(1, 2));
298 EXPECT_EQ(2, DecodeZigZag(2, 2));
299 EXPECT_EQ(3, DecodeZigZag(3, 2));
300 EXPECT_EQ(-1, DecodeZigZag(4, 2));
301 EXPECT_EQ(-2, DecodeZigZag(5, 2));
302 EXPECT_EQ(-3, DecodeZigZag(6, 2));
303 EXPECT_EQ(-4, DecodeZigZag(7, 2));
304 EXPECT_EQ(4, DecodeZigZag(8, 2));
305 EXPECT_EQ(5, DecodeZigZag(9, 2));
306 EXPECT_EQ(6, DecodeZigZag(10, 2));
307 EXPECT_EQ(7, DecodeZigZag(11, 2));
308 EXPECT_EQ(-5, DecodeZigZag(12, 2));
309 EXPECT_EQ(-6, DecodeZigZag(13, 2));
310 EXPECT_EQ(-7, DecodeZigZag(14, 2));
311 EXPECT_EQ(-8, DecodeZigZag(15, 2));
312 EXPECT_EQ(std::numeric_limits<int64_t>::min(),
313 DecodeZigZag(std::numeric_limits<uint64_t>::max(), 2));
314 EXPECT_EQ(std::numeric_limits<int64_t>::min() + 1,
315 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 2));
316 EXPECT_EQ(std::numeric_limits<int64_t>::min() + 2,
317 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 2, 2));
318 EXPECT_EQ(std::numeric_limits<int64_t>::min() + 3,
319 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 3, 2));
320 EXPECT_EQ(std::numeric_limits<int64_t>::max(),
321 DecodeZigZag(std::numeric_limits<uint64_t>::max() - 4, 2));
322 }
323
TEST(ZigZagCoding,Encode63)324 TEST(ZigZagCoding, Encode63) {
325 EXPECT_EQ(0u, EncodeZigZag(0, 63));
326
327 for (int64_t i = 0; i < 0xFFFFFFFF; i += 1234567) {
328 const int64_t positive_val = GetLowerBits(i * i * i + i * i, 63) | 1UL;
329 ASSERT_EQ(static_cast<uint64_t>(positive_val),
330 EncodeZigZag(positive_val, 63));
331 ASSERT_EQ((1ULL << 63) - 1 + positive_val, EncodeZigZag(-positive_val, 63));
332 }
333
334 EXPECT_EQ((1ULL << 63) - 1,
335 EncodeZigZag(std::numeric_limits<int64_t>::max(), 63));
336 EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
337 EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 63));
338 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
339 EncodeZigZag(std::numeric_limits<int64_t>::min(), 63));
340 }
341
TEST(BufToStream,UInt8_Empty)342 TEST(BufToStream, UInt8_Empty) {
343 const std::string expected_bits = "";
344 std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
345 EXPECT_TRUE(buffer.empty());
346 const std::string result_bits = BufferToStream(buffer);
347 EXPECT_EQ(expected_bits, result_bits);
348 }
349
TEST(BufToStream,UInt8_OneWord)350 TEST(BufToStream, UInt8_OneWord) {
351 const std::string expected_bits = "00101100";
352 std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
353 EXPECT_EQ(
354 std::vector<uint8_t>(
355 {static_cast<uint8_t>(StreamToBitset<8>(expected_bits).to_ulong())}),
356 buffer);
357 const std::string result_bits = BufferToStream(buffer);
358 EXPECT_EQ(expected_bits, result_bits);
359 }
360
TEST(BufToStream,UInt8_MultipleWords)361 TEST(BufToStream, UInt8_MultipleWords) {
362 const std::string expected_bits = "00100010""01101010""01111101""00100010";
363 std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
364 EXPECT_EQ(
365 std::vector<uint8_t>({
366 static_cast<uint8_t>(StreamToBitset<8>("00100010").to_ulong()),
367 static_cast<uint8_t>(StreamToBitset<8>("01101010").to_ulong()),
368 static_cast<uint8_t>(StreamToBitset<8>("01111101").to_ulong()),
369 static_cast<uint8_t>(StreamToBitset<8>("00100010").to_ulong()),
370 }), buffer);
371 const std::string result_bits = BufferToStream(buffer);
372 EXPECT_EQ(expected_bits, result_bits);
373 }
374
TEST(BufToStream,UInt64_Empty)375 TEST(BufToStream, UInt64_Empty) {
376 const std::string expected_bits = "";
377 std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
378 EXPECT_TRUE(buffer.empty());
379 const std::string result_bits = BufferToStream(buffer);
380 EXPECT_EQ(expected_bits, result_bits);
381 }
382
TEST(BufToStream,UInt64_OneWord)383 TEST(BufToStream, UInt64_OneWord) {
384 const std::string expected_bits =
385 "0001000111101110011001101010101000100010110011000100010010001000";
386 std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
387 ASSERT_EQ(1u, buffer.size());
388 EXPECT_EQ(0x1122334455667788u, buffer[0]);
389 const std::string result_bits = BufferToStream(buffer);
390 EXPECT_EQ(expected_bits, result_bits);
391 }
392
TEST(BufToStream,UInt64_Unaligned)393 TEST(BufToStream, UInt64_Unaligned) {
394 const std::string expected_bits =
395 "0010001001101010011111010010001001001010000111110010010010010101"
396 "0010001001101010011111111111111111111111";
397 std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
398 EXPECT_EQ(std::vector<uint64_t>({
399 StreamToBits(expected_bits.substr(0, 64)),
400 StreamToBits(expected_bits.substr(64, 64)),
401 }), buffer);
402 const std::string result_bits = BufferToStream(buffer);
403 EXPECT_EQ(PadToWord<64>(expected_bits), result_bits);
404 }
405
TEST(BufToStream,UInt64_MultipleWords)406 TEST(BufToStream, UInt64_MultipleWords) {
407 const std::string expected_bits =
408 "0010001001101010011111010010001001001010000111110010010010010101"
409 "0010001001101010011111111111111111111111000111110010010010010111"
410 "0000000000000000000000000000000000000000000000000010010011111111";
411 std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
412 EXPECT_EQ(std::vector<uint64_t>({
413 StreamToBits(expected_bits.substr(0, 64)),
414 StreamToBits(expected_bits.substr(64, 64)),
415 StreamToBits(expected_bits.substr(128, 64)),
416 }), buffer);
417 const std::string result_bits = BufferToStream(buffer);
418 EXPECT_EQ(expected_bits, result_bits);
419 }
420
TEST(PadToWord,Test)421 TEST(PadToWord, Test) {
422 EXPECT_EQ("10100000", PadToWord<8>("101"));
423 EXPECT_EQ("10100000""00000000", PadToWord<16>("101"));
424 EXPECT_EQ("10100000""00000000""00000000""00000000",
425 PadToWord<32>("101"));
426 EXPECT_EQ("10100000""00000000""00000000""00000000"
427 "00000000""00000000""00000000""00000000",
428 PadToWord<64>("101"));
429 }
430
TEST(BitWriterStringStream,Empty)431 TEST(BitWriterStringStream, Empty) {
432 BitWriterStringStream writer;
433 EXPECT_EQ(0u, writer.GetNumBits());
434 EXPECT_EQ(0u, writer.GetDataSizeBytes());
435 EXPECT_EQ("", writer.GetStreamRaw());
436 }
437
TEST(BitWriterStringStream,WriteStream)438 TEST(BitWriterStringStream, WriteStream) {
439 BitWriterStringStream writer;
440 const std::string bits1 = "1011111111111111111";
441 writer.WriteStream(bits1);
442 EXPECT_EQ(19u, writer.GetNumBits());
443 EXPECT_EQ(3u, writer.GetDataSizeBytes());
444 EXPECT_EQ(bits1, writer.GetStreamRaw());
445
446 const std::string bits2 = "10100001010101010000111111111111111111111111111";
447 writer.WriteStream(bits2);
448 EXPECT_EQ(66u, writer.GetNumBits());
449 EXPECT_EQ(9u, writer.GetDataSizeBytes());
450 EXPECT_EQ(bits1 + bits2, writer.GetStreamRaw());
451 }
452
TEST(BitWriterStringStream,WriteBitSet)453 TEST(BitWriterStringStream, WriteBitSet) {
454 BitWriterStringStream writer;
455 const std::string bits1 = "10101";
456 writer.WriteBitset(StreamToBitset<16>(bits1));
457 EXPECT_EQ(16u, writer.GetNumBits());
458 EXPECT_EQ(2u, writer.GetDataSizeBytes());
459 EXPECT_EQ(PadToWord<16>(bits1), writer.GetStreamRaw());
460 }
461
TEST(BitWriterStringStream,WriteBits)462 TEST(BitWriterStringStream, WriteBits) {
463 BitWriterStringStream writer;
464 const uint64_t bits1 = 0x1 | 0x2 | 0x10;
465 writer.WriteBits(bits1, 5);
466 EXPECT_EQ(5u, writer.GetNumBits());
467 EXPECT_EQ(1u, writer.GetDataSizeBytes());
468 EXPECT_EQ("11001", writer.GetStreamRaw());
469 }
470
TEST(BitWriterStringStream,WriteUnencodedU8)471 TEST(BitWriterStringStream, WriteUnencodedU8) {
472 BitWriterStringStream writer;
473 const uint8_t bits = 127;
474 writer.WriteUnencoded(bits);
475 EXPECT_EQ(8u, writer.GetNumBits());
476 EXPECT_EQ("11111110", writer.GetStreamRaw());
477 }
478
TEST(BitWriterStringStream,WriteUnencodedS64)479 TEST(BitWriterStringStream, WriteUnencodedS64) {
480 BitWriterStringStream writer;
481 const int64_t bits = std::numeric_limits<int64_t>::min() + 7;
482 writer.WriteUnencoded(bits);
483 EXPECT_EQ(64u, writer.GetNumBits());
484 EXPECT_EQ("1110000000000000000000000000000000000000000000000000000000000001",
485 writer.GetStreamRaw());
486 }
487
TEST(BitWriterStringStream,WriteMultiple)488 TEST(BitWriterStringStream, WriteMultiple) {
489 BitWriterStringStream writer;
490
491 std::string expected_result;
492 const std::string bits1 = "101001111111001100010000001110001111111100";
493 writer.WriteStream(bits1);
494
495 const std::string bits2 = "10100011000010010101";
496 writer.WriteBitset(StreamToBitset<20>(bits2));
497
498 const uint64_t val = 0x1 | 0x2 | 0x10;
499 const std::string bits3 = BitsToStream(val, 8);
500 writer.WriteBits(val, 8);
501
502 const std::string expected = bits1 + bits2 + bits3;
503
504 EXPECT_EQ(expected.length(), writer.GetNumBits());
505 EXPECT_EQ(9u, writer.GetDataSizeBytes());
506 EXPECT_EQ(expected, writer.GetStreamRaw());
507
508 EXPECT_EQ(PadToWord<8>(expected), BufferToStream(writer.GetDataCopy()));
509 }
510
TEST(BitWriterWord64,Empty)511 TEST(BitWriterWord64, Empty) {
512 BitWriterWord64 writer;
513 EXPECT_EQ(0u, writer.GetNumBits());
514 EXPECT_EQ(0u, writer.GetDataSizeBytes());
515 EXPECT_EQ("", writer.GetStreamPadded64());
516 }
517
TEST(BitWriterWord64,WriteStream)518 TEST(BitWriterWord64, WriteStream) {
519 BitWriterWord64 writer;
520 std::string expected;
521
522 {
523 const std::string bits = "101";
524 expected += bits;
525 writer.WriteStream(bits);
526 EXPECT_EQ(expected.length(), writer.GetNumBits());
527 EXPECT_EQ(1u, writer.GetDataSizeBytes());
528 EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
529 }
530
531 {
532 const std::string bits = "10000111111111110000000";
533 expected += bits;
534 writer.WriteStream(bits);
535 EXPECT_EQ(expected.length(), writer.GetNumBits());
536 EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
537 }
538
539 {
540 const std::string bits = "101001111111111100000111111111111100";
541 expected += bits;
542 writer.WriteStream(bits);
543 EXPECT_EQ(expected.length(), writer.GetNumBits());
544 EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
545 }
546 }
547
TEST(BitWriterWord64,WriteBitset)548 TEST(BitWriterWord64, WriteBitset) {
549 BitWriterWord64 writer;
550 const std::string bits1 = "10101";
551 writer.WriteBitset(StreamToBitset<16>(bits1), 12);
552 EXPECT_EQ(12u, writer.GetNumBits());
553 EXPECT_EQ(2u, writer.GetDataSizeBytes());
554 EXPECT_EQ(PadToWord<64>(bits1), writer.GetStreamPadded64());
555 }
556
TEST(BitWriterWord64,WriteBits)557 TEST(BitWriterWord64, WriteBits) {
558 BitWriterWord64 writer;
559 const uint64_t bits1 = 0x1 | 0x2 | 0x10;
560 writer.WriteBits(bits1, 5);
561 writer.WriteBits(bits1, 5);
562 writer.WriteBits(bits1, 5);
563 EXPECT_EQ(15u, writer.GetNumBits());
564 EXPECT_EQ(2u, writer.GetDataSizeBytes());
565 EXPECT_EQ(PadToWord<64>("110011100111001"), writer.GetStreamPadded64());
566 }
567
TEST(BitWriterWord64,ComparisonTestWriteLotsOfBits)568 TEST(BitWriterWord64, ComparisonTestWriteLotsOfBits) {
569 BitWriterStringStream writer1;
570 BitWriterWord64 writer2(16384);
571
572 for (uint64_t i = 0; i < 65000; i += 25) {
573 writer1.WriteBits(i, 16);
574 writer2.WriteBits(i, 16);
575 ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
576 }
577
578 EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
579 writer2.GetStreamPadded64());
580 }
581
TEST(BitWriterWord64,ComparisonTestWriteLotsOfStreams)582 TEST(BitWriterWord64, ComparisonTestWriteLotsOfStreams) {
583 BitWriterStringStream writer1;
584 BitWriterWord64 writer2(16384);
585
586 for (int i = 0; i < 1000; ++i) {
587 std::string bits = "1111100000";
588 if (i % 2)
589 bits += "101010";
590 if (i % 3)
591 bits += "1110100";
592 if (i % 5)
593 bits += "1110100111111111111";
594 writer1.WriteStream(bits);
595 writer2.WriteStream(bits);
596 ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
597 }
598
599 EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
600 writer2.GetStreamPadded64());
601 }
602
TEST(BitWriterWord64,ComparisonTestWriteLotsOfBitsets)603 TEST(BitWriterWord64, ComparisonTestWriteLotsOfBitsets) {
604 BitWriterStringStream writer1;
605 BitWriterWord64 writer2(16384);
606
607 for (uint64_t i = 0; i < 65000; i += 25) {
608 std::bitset<16> bits1(i);
609 std::bitset<24> bits2(i);
610 writer1.WriteBitset(bits1);
611 writer1.WriteBitset(bits2);
612 writer2.WriteBitset(bits1);
613 writer2.WriteBitset(bits2);
614 ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
615 }
616
617 EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
618 writer2.GetStreamPadded64());
619 }
620
TEST(GetLowerBits,Test)621 TEST(GetLowerBits, Test) {
622 EXPECT_EQ(0u, GetLowerBits<uint8_t>(255, 0));
623 EXPECT_EQ(1u, GetLowerBits<uint8_t>(255, 1));
624 EXPECT_EQ(3u, GetLowerBits<uint8_t>(255, 2));
625 EXPECT_EQ(7u, GetLowerBits<uint8_t>(255, 3));
626 EXPECT_EQ(15u, GetLowerBits<uint8_t>(255, 4));
627 EXPECT_EQ(31u, GetLowerBits<uint8_t>(255, 5));
628 EXPECT_EQ(63u, GetLowerBits<uint8_t>(255, 6));
629 EXPECT_EQ(127u, GetLowerBits<uint8_t>(255, 7));
630 EXPECT_EQ(255u, GetLowerBits<uint8_t>(255, 8));
631 EXPECT_EQ(0xFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 8));
632 EXPECT_EQ(0xFFFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 16));
633 EXPECT_EQ(0xFFFFFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 24));
634 EXPECT_EQ(0xFFFFFFu, GetLowerBits<uint64_t>(0xFFFFFFFFFFFF, 24));
635 EXPECT_EQ(0xFFFFFFFFFFFFFFFFu,
636 GetLowerBits<uint64_t>(0xFFFFFFFFFFFFFFFFu, 64));
637 EXPECT_EQ(StreamToBits("1010001110"),
638 GetLowerBits<uint64_t>(
639 StreamToBits("1010001110111101111111"), 10));
640 }
641
TEST(BitReaderFromString,FromU8)642 TEST(BitReaderFromString, FromU8) {
643 std::vector<uint8_t> buffer = {
644 0xAA, 0xBB, 0xCC, 0xDD,
645 };
646
647 const std::string total_stream =
648 "01010101""11011101""00110011""10111011";
649
650 BitReaderFromString reader(buffer);
651 EXPECT_EQ(PadToWord<64>(total_stream), reader.GetStreamPadded64());
652
653 uint64_t bits = 0;
654 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
655 EXPECT_EQ(PadToWord<64>("01"), BitsToStream(bits));
656 EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
657 EXPECT_EQ(PadToWord<64>("01010111011101001100"), BitsToStream(bits));
658 EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
659 EXPECT_EQ(PadToWord<64>("11101110110000000000"), BitsToStream(bits));
660 EXPECT_EQ(22u, reader.ReadBits(&bits, 30));
661 EXPECT_EQ(PadToWord<64>("0000000000000000000000"), BitsToStream(bits));
662 EXPECT_TRUE(reader.ReachedEnd());
663 }
664
TEST(BitReaderFromString,FromU64)665 TEST(BitReaderFromString, FromU64) {
666 std::vector<uint64_t> buffer = {
667 0xAAAAAAAAAAAAAAAA,
668 0xBBBBBBBBBBBBBBBB,
669 0xCCCCCCCCCCCCCCCC,
670 0xDDDDDDDDDDDDDDDD,
671 };
672
673 const std::string total_stream =
674 "0101010101010101010101010101010101010101010101010101010101010101"
675 "1101110111011101110111011101110111011101110111011101110111011101"
676 "0011001100110011001100110011001100110011001100110011001100110011"
677 "1011101110111011101110111011101110111011101110111011101110111011";
678
679 BitReaderFromString reader(buffer);
680 EXPECT_EQ(total_stream, reader.GetStreamPadded64());
681
682 uint64_t bits = 0;
683 size_t pos = 0;
684 size_t to_read = 5;
685 while (reader.ReadBits(&bits, to_read) > 0) {
686 EXPECT_EQ(BitsToStream(bits),
687 PadToWord<64>(total_stream.substr(pos, to_read)));
688 pos += to_read;
689 to_read = (to_read + 35) % 64 + 1;
690 }
691 EXPECT_TRUE(reader.ReachedEnd());
692 }
693
TEST(BitReaderWord64,ReadBitsSingleByte)694 TEST(BitReaderWord64, ReadBitsSingleByte) {
695 BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xF0)}));
696 EXPECT_FALSE(reader.ReachedEnd());
697
698 uint64_t bits = 0;
699 EXPECT_EQ(1u, reader.ReadBits(&bits, 1));
700 EXPECT_EQ(0u, bits);
701 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
702 EXPECT_EQ(0u, bits);
703 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
704 EXPECT_EQ(2u, bits);
705 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
706 EXPECT_EQ(3u, bits);
707 EXPECT_FALSE(reader.OnlyZeroesLeft());
708 EXPECT_FALSE(reader.ReachedEnd());
709 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
710 EXPECT_EQ(1u, bits);
711 EXPECT_TRUE(reader.OnlyZeroesLeft());
712 EXPECT_FALSE(reader.ReachedEnd());
713 EXPECT_EQ(55u, reader.ReadBits(&bits, 64));
714 EXPECT_EQ(0u, bits);
715 EXPECT_TRUE(reader.ReachedEnd());
716 }
717
TEST(BitReaderWord64,ReadBitsetSingleByte)718 TEST(BitReaderWord64, ReadBitsetSingleByte) {
719 BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xCC)}));
720 std::bitset<4> bits;
721 EXPECT_EQ(2u, reader.ReadBitset(&bits, 2));
722 EXPECT_EQ(0u, bits.to_ullong());
723 EXPECT_EQ(2u, reader.ReadBitset(&bits, 2));
724 EXPECT_EQ(3u, bits.to_ullong());
725 EXPECT_FALSE(reader.OnlyZeroesLeft());
726 EXPECT_EQ(4u, reader.ReadBitset(&bits, 4));
727 EXPECT_EQ(12u, bits.to_ullong());
728 EXPECT_TRUE(reader.OnlyZeroesLeft());
729 }
730
TEST(BitReaderWord64,ReadStreamSingleByte)731 TEST(BitReaderWord64, ReadStreamSingleByte) {
732 BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xAA)}));
733 EXPECT_EQ("", reader.ReadStream(0));
734 EXPECT_EQ("0", reader.ReadStream(1));
735 EXPECT_EQ("101", reader.ReadStream(3));
736 EXPECT_EQ("01010000", reader.ReadStream(8));
737 EXPECT_TRUE(reader.OnlyZeroesLeft());
738 EXPECT_EQ("0000000000000000000000000000000000000000000000000000",
739 reader.ReadStream(64));
740 EXPECT_TRUE(reader.ReachedEnd());
741 }
742
TEST(BitReaderWord64,ReadStreamEmpty)743 TEST(BitReaderWord64, ReadStreamEmpty) {
744 std::vector<uint64_t> buffer;
745 BitReaderWord64 reader(std::move(buffer));
746 EXPECT_TRUE(reader.OnlyZeroesLeft());
747 EXPECT_TRUE(reader.ReachedEnd());
748 EXPECT_EQ("", reader.ReadStream(10));
749 EXPECT_TRUE(reader.ReachedEnd());
750 }
751
TEST(BitReaderWord64,ReadBitsTwoWords)752 TEST(BitReaderWord64, ReadBitsTwoWords) {
753 std::vector<uint64_t> buffer = {
754 0x0000000000000001,
755 0x0000000000FFFFFF
756 };
757
758 BitReaderWord64 reader(std::move(buffer));
759
760 uint64_t bits = 0;
761 EXPECT_EQ(1u, reader.ReadBits(&bits, 1));
762 EXPECT_EQ(1u, bits);
763 EXPECT_EQ(62u, reader.ReadBits(&bits, 62));
764 EXPECT_EQ(0u, bits);
765 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
766 EXPECT_EQ(2u, bits);
767 EXPECT_EQ(3u, reader.ReadBits(&bits, 3));
768 EXPECT_EQ(7u, bits);
769 EXPECT_FALSE(reader.OnlyZeroesLeft());
770 EXPECT_EQ(32u, reader.ReadBits(&bits, 32));
771 EXPECT_EQ(0xFFFFFu, bits);
772 EXPECT_TRUE(reader.OnlyZeroesLeft());
773 EXPECT_FALSE(reader.ReachedEnd());
774 EXPECT_EQ(28u, reader.ReadBits(&bits, 32));
775 EXPECT_EQ(0u, bits);
776 EXPECT_TRUE(reader.ReachedEnd());
777 }
778
TEST(BitReaderFromString,ReadUnencodedU8)779 TEST(BitReaderFromString, ReadUnencodedU8) {
780 BitReaderFromString reader("11111110");
781 uint8_t val = 0;
782 ASSERT_TRUE(reader.ReadUnencoded(&val));
783 EXPECT_EQ(8u, reader.GetNumReadBits());
784 EXPECT_EQ(127, val);
785 }
786
TEST(BitReaderFromString,ReadUnencodedU16Fail)787 TEST(BitReaderFromString, ReadUnencodedU16Fail) {
788 BitReaderFromString reader("11111110");
789 uint16_t val = 0;
790 ASSERT_FALSE(reader.ReadUnencoded(&val));
791 }
792
TEST(BitReaderFromString,ReadUnencodedS64)793 TEST(BitReaderFromString, ReadUnencodedS64) {
794 BitReaderFromString reader(
795 "1110000000000000000000000000000000000000000000000000000000000001");
796 int64_t val = 0;
797 ASSERT_TRUE(reader.ReadUnencoded(&val));
798 EXPECT_EQ(64u, reader.GetNumReadBits());
799 EXPECT_EQ(std::numeric_limits<int64_t>::min() + 7, val);
800 }
801
TEST(BitReaderWord64,FromU8)802 TEST(BitReaderWord64, FromU8) {
803 std::vector<uint8_t> buffer = {
804 0xAA, 0xBB, 0xCC, 0xDD,
805 };
806
807 BitReaderWord64 reader(std::move(buffer));
808
809 uint64_t bits = 0;
810 EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
811 EXPECT_EQ(PadToWord<64>("01"), BitsToStream(bits));
812 EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
813 EXPECT_EQ(PadToWord<64>("01010111011101001100"), BitsToStream(bits));
814 EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
815 EXPECT_EQ(PadToWord<64>("11101110110000000000"), BitsToStream(bits));
816 EXPECT_EQ(22u, reader.ReadBits(&bits, 30));
817 EXPECT_EQ(PadToWord<64>("0000000000000000000000"), BitsToStream(bits));
818 EXPECT_TRUE(reader.ReachedEnd());
819 }
820
TEST(BitReaderWord64,FromU64)821 TEST(BitReaderWord64, FromU64) {
822 std::vector<uint64_t> buffer = {
823 0xAAAAAAAAAAAAAAAA,
824 0xBBBBBBBBBBBBBBBB,
825 0xCCCCCCCCCCCCCCCC,
826 0xDDDDDDDDDDDDDDDD,
827 };
828
829 const std::string total_stream =
830 "0101010101010101010101010101010101010101010101010101010101010101"
831 "1101110111011101110111011101110111011101110111011101110111011101"
832 "0011001100110011001100110011001100110011001100110011001100110011"
833 "1011101110111011101110111011101110111011101110111011101110111011";
834
835 BitReaderWord64 reader(std::move(buffer));
836
837 uint64_t bits = 0;
838 size_t pos = 0;
839 size_t to_read = 5;
840 while (reader.ReadBits(&bits, to_read) > 0) {
841 EXPECT_EQ(BitsToStream(bits),
842 PadToWord<64>(total_stream.substr(pos, to_read)));
843 pos += to_read;
844 to_read = (to_read + 35) % 64 + 1;
845 }
846 EXPECT_TRUE(reader.ReachedEnd());
847 }
848
TEST(BitReaderWord64,ComparisonLotsOfU8)849 TEST(BitReaderWord64, ComparisonLotsOfU8) {
850 std::vector<uint8_t> buffer;
851 for(uint32_t i = 0; i < 10003; ++i) {
852 buffer.push_back(static_cast<uint8_t>(i % 255));
853 }
854
855 BitReaderFromString reader1(buffer);
856 BitReaderWord64 reader2(std::move(buffer));
857
858 uint64_t bits1 = 0, bits2 = 0;
859 size_t to_read = 5;
860 while (reader1.ReadBits(&bits1, to_read) > 0) {
861 reader2.ReadBits(&bits2, to_read);
862 EXPECT_EQ(bits1, bits2);
863 to_read = (to_read + 35) % 64 + 1;
864 }
865
866 EXPECT_EQ(0u, reader2.ReadBits(&bits2, 1));
867 }
868
TEST(BitReaderWord64,ComparisonLotsOfU64)869 TEST(BitReaderWord64, ComparisonLotsOfU64) {
870 std::vector<uint64_t> buffer;
871 for(uint64_t i = 0; i < 1000; ++i) {
872 buffer.push_back(i);
873 }
874
875 BitReaderFromString reader1(buffer);
876 BitReaderWord64 reader2(std::move(buffer));
877
878 uint64_t bits1 = 0, bits2 = 0;
879 size_t to_read = 5;
880 while (reader1.ReadBits(&bits1, to_read) > 0) {
881 reader2.ReadBits(&bits2, to_read);
882 EXPECT_EQ(bits1, bits2);
883 to_read = (to_read + 35) % 64 + 1;
884 }
885
886 EXPECT_EQ(0u, reader2.ReadBits(&bits2, 1));
887 }
888
TEST(ReadWriteWord64,ReadWriteLotsOfBits)889 TEST(ReadWriteWord64, ReadWriteLotsOfBits) {
890 BitWriterWord64 writer(16384);
891 for (uint64_t i = 0; i < 65000; i += 25) {
892 const uint64_t num_bits = i % 64 + 1;
893 const uint64_t bits = i >> (64 - num_bits);
894 writer.WriteBits(bits, size_t(num_bits));
895 }
896
897 BitReaderWord64 reader(writer.GetDataCopy());
898 for (uint64_t i = 0; i < 65000; i += 25) {
899 const uint64_t num_bits = i % 64 + 1;
900 const uint64_t expected_bits = i >> (64 - num_bits);
901 uint64_t bits = 0;
902 reader.ReadBits(&bits, size_t(num_bits));
903 EXPECT_EQ(expected_bits, bits);
904 }
905
906 EXPECT_TRUE(reader.OnlyZeroesLeft());
907 }
908
TEST(VariableWidthWrite,Write0U)909 TEST(VariableWidthWrite, Write0U) {
910 BitWriterStringStream writer;
911 writer.WriteVariableWidthU64(0, 2);
912 EXPECT_EQ("000", writer.GetStreamRaw ());
913 writer.WriteVariableWidthU32(0, 2);
914 EXPECT_EQ("000""000", writer.GetStreamRaw());
915 writer.WriteVariableWidthU16(0, 2);
916 EXPECT_EQ("000""000""000", writer.GetStreamRaw());
917 writer.WriteVariableWidthU8(0, 2);
918 EXPECT_EQ("000""000""000""000", writer.GetStreamRaw());
919 }
920
TEST(VariableWidthWrite,Write0S)921 TEST(VariableWidthWrite, Write0S) {
922 BitWriterStringStream writer;
923 writer.WriteVariableWidthS64(0, 2, 0);
924 EXPECT_EQ("000", writer.GetStreamRaw ());
925 writer.WriteVariableWidthS32(0, 2, 0);
926 EXPECT_EQ("000""000", writer.GetStreamRaw());
927 writer.WriteVariableWidthS16(0, 2, 0);
928 EXPECT_EQ("000""000""000", writer.GetStreamRaw());
929 writer.WriteVariableWidthS8(0, 2, 0);
930 EXPECT_EQ("000""000""000""000", writer.GetStreamRaw());
931 }
932
TEST(VariableWidthWrite,WriteSmallUnsigned)933 TEST(VariableWidthWrite, WriteSmallUnsigned) {
934 BitWriterStringStream writer;
935 writer.WriteVariableWidthU64(1, 2);
936 EXPECT_EQ("100", writer.GetStreamRaw ());
937 writer.WriteVariableWidthU32(2, 2);
938 EXPECT_EQ("100""010", writer.GetStreamRaw());
939 writer.WriteVariableWidthU16(3, 2);
940 EXPECT_EQ("100""010""110", writer.GetStreamRaw());
941 writer.WriteVariableWidthU8(4, 2);
942 EXPECT_EQ("100""010""110""001100", writer.GetStreamRaw());
943 }
944
TEST(VariableWidthWrite,WriteSmallSigned)945 TEST(VariableWidthWrite, WriteSmallSigned) {
946 BitWriterStringStream writer;
947 writer.WriteVariableWidthS64(1, 2, 0);
948 EXPECT_EQ("010", writer.GetStreamRaw ());
949 writer.WriteVariableWidthS64(-1, 2, 0);
950 EXPECT_EQ("010""100", writer.GetStreamRaw());
951 writer.WriteVariableWidthS16(3, 2, 0);
952 EXPECT_EQ("010""100""011100", writer.GetStreamRaw());
953 writer.WriteVariableWidthS8(-4, 2, 0);
954 EXPECT_EQ("010""100""011100""111100", writer.GetStreamRaw());
955 }
956
TEST(VariableWidthWrite,U64Val127ChunkLength7)957 TEST(VariableWidthWrite, U64Val127ChunkLength7) {
958 BitWriterStringStream writer;
959 writer.WriteVariableWidthU64(127, 7);
960 EXPECT_EQ("1111111""0", writer.GetStreamRaw());
961 }
962
TEST(VariableWidthWrite,U32Val255ChunkLength7)963 TEST(VariableWidthWrite, U32Val255ChunkLength7) {
964 BitWriterStringStream writer;
965 writer.WriteVariableWidthU32(255, 7);
966 EXPECT_EQ("1111111""1""1000000""0", writer.GetStreamRaw());
967 }
968
TEST(VariableWidthWrite,U16Val2ChunkLength4)969 TEST(VariableWidthWrite, U16Val2ChunkLength4) {
970 BitWriterStringStream writer;
971 writer.WriteVariableWidthU16(2, 4);
972 EXPECT_EQ("0100""0", writer.GetStreamRaw());
973 }
974
TEST(VariableWidthWrite,U8Val128ChunkLength7)975 TEST(VariableWidthWrite, U8Val128ChunkLength7) {
976 BitWriterStringStream writer;
977 writer.WriteVariableWidthU8(128, 7);
978 EXPECT_EQ("0000000""1""1", writer.GetStreamRaw());
979 }
980
TEST(VariableWidthWrite,U64ValAAAAChunkLength2)981 TEST(VariableWidthWrite, U64ValAAAAChunkLength2) {
982 BitWriterStringStream writer;
983 writer.WriteVariableWidthU64(0xAAAA, 2);
984 EXPECT_EQ("01""1""01""1""01""1""01""1"
985 "01""1""01""1""01""1""01""0", writer.GetStreamRaw());
986 }
987
TEST(VariableWidthWrite,S8ValM128ChunkLength7)988 TEST(VariableWidthWrite, S8ValM128ChunkLength7) {
989 BitWriterStringStream writer;
990 writer.WriteVariableWidthS8(-128, 7, 0);
991 EXPECT_EQ("1111111""1""1", writer.GetStreamRaw());
992 }
993
TEST(VariableWidthRead,U64Val127ChunkLength7)994 TEST(VariableWidthRead, U64Val127ChunkLength7) {
995 BitReaderFromString reader("1111111""0");
996 uint64_t val = 0;
997 ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 7));
998 EXPECT_EQ(127u, val);
999 }
1000
TEST(VariableWidthRead,U32Val255ChunkLength7)1001 TEST(VariableWidthRead, U32Val255ChunkLength7) {
1002 BitReaderFromString reader("1111111""1""1000000""0");
1003 uint32_t val = 0;
1004 ASSERT_TRUE(reader.ReadVariableWidthU32(&val, 7));
1005 EXPECT_EQ(255u, val);
1006 }
1007
TEST(VariableWidthRead,U16Val2ChunkLength4)1008 TEST(VariableWidthRead, U16Val2ChunkLength4) {
1009 BitReaderFromString reader("0100""0");
1010 uint16_t val = 0;
1011 ASSERT_TRUE(reader.ReadVariableWidthU16(&val, 4));
1012 EXPECT_EQ(2u, val);
1013 }
1014
TEST(VariableWidthRead,U8Val128ChunkLength7)1015 TEST(VariableWidthRead, U8Val128ChunkLength7) {
1016 BitReaderFromString reader("0000000""1""1");
1017 uint8_t val = 0;
1018 ASSERT_TRUE(reader.ReadVariableWidthU8(&val, 7));
1019 EXPECT_EQ(128u, val);
1020 }
1021
TEST(VariableWidthRead,U64ValAAAAChunkLength2)1022 TEST(VariableWidthRead, U64ValAAAAChunkLength2) {
1023 BitReaderFromString reader("01""1""01""1""01""1""01""1"
1024 "01""1""01""1""01""1""01""0");
1025 uint64_t val = 0;
1026 ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 2));
1027 EXPECT_EQ(0xAAAAu, val);
1028 }
1029
TEST(VariableWidthRead,S8ValM128ChunkLength7)1030 TEST(VariableWidthRead, S8ValM128ChunkLength7) {
1031 BitReaderFromString reader("1111111""1""1");
1032 int8_t val = 0;
1033 ASSERT_TRUE(reader.ReadVariableWidthS8(&val, 7, 0));
1034 EXPECT_EQ(-128, val);
1035 }
1036
TEST(VariableWidthRead,FailTooShort)1037 TEST(VariableWidthRead, FailTooShort) {
1038 BitReaderFromString reader("00000001100000");
1039 uint64_t val = 0;
1040 ASSERT_FALSE(reader.ReadVariableWidthU64(&val, 7));
1041 }
1042
TEST(VariableWidthWriteRead,SingleWriteReadU64)1043 TEST(VariableWidthWriteRead, SingleWriteReadU64) {
1044 for (uint64_t i = 0; i < 1000000; i += 1234) {
1045 const uint64_t val = i * i * i;
1046 const size_t chunk_length = size_t(i % 16 + 1);
1047
1048 BitWriterWord64 writer;
1049 writer.WriteVariableWidthU64(val, chunk_length);
1050
1051 BitReaderWord64 reader(writer.GetDataCopy());
1052 uint64_t read_val = 0;
1053 ASSERT_TRUE(reader.ReadVariableWidthU64(&read_val, chunk_length));
1054
1055 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1056 }
1057 }
1058
TEST(VariableWidthWriteRead,SingleWriteReadS64)1059 TEST(VariableWidthWriteRead, SingleWriteReadS64) {
1060 for (int64_t i = 0; i < 1000000; i += 4321) {
1061 const int64_t val = i * i * (i % 2 ? -i : i);
1062 const size_t chunk_length = size_t(i % 16 + 1);
1063 const size_t zigzag_exponent = size_t(i % 13);
1064
1065 BitWriterWord64 writer;
1066 writer.WriteVariableWidthS64(val, chunk_length, zigzag_exponent);
1067
1068 BitReaderWord64 reader(writer.GetDataCopy());
1069 int64_t read_val = 0;
1070 ASSERT_TRUE(reader.ReadVariableWidthS64(&read_val, chunk_length,
1071 zigzag_exponent));
1072
1073 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1074 }
1075 }
1076
TEST(VariableWidthWriteRead,SingleWriteReadU32)1077 TEST(VariableWidthWriteRead, SingleWriteReadU32) {
1078 for (uint32_t i = 0; i < 100000; i += 123) {
1079 const uint32_t val = i * i;
1080 const size_t chunk_length = i % 16 + 1;
1081
1082 BitWriterWord64 writer;
1083 writer.WriteVariableWidthU32(val, chunk_length);
1084
1085 BitReaderWord64 reader(writer.GetDataCopy());
1086 uint32_t read_val = 0;
1087 ASSERT_TRUE(reader.ReadVariableWidthU32(&read_val, chunk_length));
1088
1089 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1090 }
1091 }
1092
TEST(VariableWidthWriteRead,SingleWriteReadS32)1093 TEST(VariableWidthWriteRead, SingleWriteReadS32) {
1094 for (int32_t i = 0; i < 100000; i += 123) {
1095 const int32_t val = i * (i % 2 ? -i : i);
1096 const size_t chunk_length = i % 16 + 1;
1097 const size_t zigzag_exponent = i % 11;
1098
1099 BitWriterWord64 writer;
1100 writer.WriteVariableWidthS32(val, chunk_length, zigzag_exponent);
1101
1102 BitReaderWord64 reader(writer.GetDataCopy());
1103 int32_t read_val = 0;
1104 ASSERT_TRUE(reader.ReadVariableWidthS32(
1105 &read_val, chunk_length, zigzag_exponent));
1106
1107 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1108 }
1109 }
1110
TEST(VariableWidthWriteRead,SingleWriteReadU16)1111 TEST(VariableWidthWriteRead, SingleWriteReadU16) {
1112 for (int i = 0; i < 65536; i += 123) {
1113 const uint16_t val = static_cast<int16_t>(i);
1114 const size_t chunk_length = val % 10 + 1;
1115
1116 BitWriterWord64 writer;
1117 writer.WriteVariableWidthU16(val, chunk_length);
1118
1119 BitReaderWord64 reader(writer.GetDataCopy());
1120 uint16_t read_val = 0;
1121 ASSERT_TRUE(reader.ReadVariableWidthU16(&read_val, chunk_length));
1122
1123 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1124 }
1125 }
1126
TEST(VariableWidthWriteRead,SingleWriteReadS16)1127 TEST(VariableWidthWriteRead, SingleWriteReadS16) {
1128 for (int i = -32768; i < 32768; i += 123) {
1129 const int16_t val = static_cast<int16_t>(i);
1130 const size_t chunk_length = std::abs(i) % 10 + 1;
1131 const size_t zigzag_exponent = std::abs(i) % 7;
1132
1133 BitWriterWord64 writer;
1134 writer.WriteVariableWidthS16(val, chunk_length, zigzag_exponent);
1135
1136 BitReaderWord64 reader(writer.GetDataCopy());
1137 int16_t read_val = 0;
1138 ASSERT_TRUE(reader.ReadVariableWidthS16(&read_val, chunk_length,
1139 zigzag_exponent));
1140
1141 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1142 }
1143 }
1144
TEST(VariableWidthWriteRead,SingleWriteReadU8)1145 TEST(VariableWidthWriteRead, SingleWriteReadU8) {
1146 for (int i = 0; i < 256; ++i) {
1147 const uint8_t val = static_cast<uint8_t>(i);
1148 const size_t chunk_length = val % 5 + 1;
1149
1150 BitWriterWord64 writer;
1151 writer.WriteVariableWidthU8(val, chunk_length);
1152
1153 BitReaderWord64 reader(writer.GetDataCopy());
1154 uint8_t read_val = 0;
1155 ASSERT_TRUE(reader.ReadVariableWidthU8(&read_val, chunk_length));
1156
1157 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1158 }
1159 }
1160
TEST(VariableWidthWriteRead,SingleWriteReadS8)1161 TEST(VariableWidthWriteRead, SingleWriteReadS8) {
1162 for (int i = -128; i < 128; ++i) {
1163 const int8_t val = static_cast<int8_t>(i);
1164 const size_t chunk_length = std::abs(i) % 5 + 1;
1165 const size_t zigzag_exponent = std::abs(i) % 3;
1166
1167 BitWriterWord64 writer;
1168 writer.WriteVariableWidthS8(val, chunk_length, zigzag_exponent);
1169
1170 BitReaderWord64 reader(writer.GetDataCopy());
1171 int8_t read_val = 0;
1172 ASSERT_TRUE(reader.ReadVariableWidthS8(&read_val, chunk_length,
1173 zigzag_exponent));
1174
1175 ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
1176 }
1177 }
1178
TEST(VariableWidthWriteRead,SmallNumbersChunkLength4)1179 TEST(VariableWidthWriteRead, SmallNumbersChunkLength4) {
1180 const std::vector<uint64_t> expected_values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
1181
1182 BitWriterWord64 writer;
1183 for (uint64_t val : expected_values) {
1184 writer.WriteVariableWidthU64(val, 4);
1185 }
1186
1187 EXPECT_EQ(50u, writer.GetNumBits());
1188
1189 std::vector<uint64_t> actual_values;
1190 BitReaderWord64 reader(writer.GetDataCopy());
1191 while(!reader.OnlyZeroesLeft()) {
1192 uint64_t val = 0;
1193 ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 4));
1194 actual_values.push_back(val);
1195 }
1196
1197 EXPECT_EQ(expected_values, actual_values);
1198 }
1199
TEST(VariableWidthWriteRead,VariedNumbersChunkLength8)1200 TEST(VariableWidthWriteRead, VariedNumbersChunkLength8) {
1201 const std::vector<uint64_t> expected_values = {1000, 0, 255, 4294967296};
1202 const size_t kExpectedNumBits = 9 * (2 + 1 + 1 + 5);
1203
1204 BitWriterWord64 writer;
1205 for (uint64_t val : expected_values) {
1206 writer.WriteVariableWidthU64(val, 8);
1207 }
1208
1209 EXPECT_EQ(kExpectedNumBits, writer.GetNumBits());
1210
1211 std::vector<uint64_t> actual_values;
1212 BitReaderWord64 reader(writer.GetDataCopy());
1213 while (!reader.OnlyZeroesLeft()) {
1214 uint64_t val = 0;
1215 ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 8));
1216 actual_values.push_back(val);
1217 }
1218
1219 EXPECT_EQ(expected_values, actual_values);
1220 }
1221
TEST(FixedWidthWrite,Val0Max3)1222 TEST(FixedWidthWrite, Val0Max3) {
1223 BitWriterStringStream writer;
1224 writer.WriteFixedWidth(0, 3);
1225 EXPECT_EQ("00", writer.GetStreamRaw());
1226 }
1227
TEST(FixedWidthWrite,Val0Max5)1228 TEST(FixedWidthWrite, Val0Max5) {
1229 BitWriterStringStream writer;
1230 writer.WriteFixedWidth(0, 5);
1231 EXPECT_EQ("000", writer.GetStreamRaw());
1232 }
1233
TEST(FixedWidthWrite,Val0Max255)1234 TEST(FixedWidthWrite, Val0Max255) {
1235 BitWriterStringStream writer;
1236 writer.WriteFixedWidth(0, 255);
1237 EXPECT_EQ("00000000", writer.GetStreamRaw());
1238 }
1239
TEST(FixedWidthWrite,Val3Max8)1240 TEST(FixedWidthWrite, Val3Max8) {
1241 BitWriterStringStream writer;
1242 writer.WriteFixedWidth(3, 8);
1243 EXPECT_EQ("1100", writer.GetStreamRaw());
1244 }
1245
TEST(FixedWidthWrite,Val15Max127)1246 TEST(FixedWidthWrite, Val15Max127) {
1247 BitWriterStringStream writer;
1248 writer.WriteFixedWidth(15, 127);
1249 EXPECT_EQ("1111000", writer.GetStreamRaw());
1250 }
1251
TEST(FixedWidthRead,Val0Max3)1252 TEST(FixedWidthRead, Val0Max3) {
1253 BitReaderFromString reader("0011111");
1254 uint64_t val = 0;
1255 ASSERT_TRUE(reader.ReadFixedWidth(&val, 3));
1256 EXPECT_EQ(0u, val);
1257 }
1258
TEST(FixedWidthRead,Val0Max5)1259 TEST(FixedWidthRead, Val0Max5) {
1260 BitReaderFromString reader("0001010101");
1261 uint64_t val = 0;
1262 ASSERT_TRUE(reader.ReadFixedWidth(&val, 5));
1263 EXPECT_EQ(0u, val);
1264 }
1265
TEST(FixedWidthRead,Val3Max8)1266 TEST(FixedWidthRead, Val3Max8) {
1267 BitReaderFromString reader("11001010101");
1268 uint64_t val = 0;
1269 ASSERT_TRUE(reader.ReadFixedWidth(&val, 8));
1270 EXPECT_EQ(3u, val);
1271 }
1272
TEST(FixedWidthRead,Val15Max127)1273 TEST(FixedWidthRead, Val15Max127) {
1274 BitReaderFromString reader("111100010101");
1275 uint64_t val = 0;
1276 ASSERT_TRUE(reader.ReadFixedWidth(&val, 127));
1277 EXPECT_EQ(15u, val);
1278 }
1279
TEST(FixedWidthRead,Fail)1280 TEST(FixedWidthRead, Fail) {
1281 BitReaderFromString reader("111100");
1282 uint64_t val = 0;
1283 ASSERT_FALSE(reader.ReadFixedWidth(&val, 127));
1284 }
1285
1286 } // anonymous namespace
1287