Added bit stream utils
Also added generalized zigzag coding.
- Due to signed integers being mostly non-negative, improved zigzag coding
to favor positive values.
diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt
index 2214fee..61671e3 100644
--- a/source/CMakeLists.txt
+++ b/source/CMakeLists.txt
@@ -190,6 +190,7 @@
${spirv-tools_SOURCE_DIR}/include/spirv-tools/libspirv.h
${CMAKE_CURRENT_SOURCE_DIR}/util/bitutils.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/util/bit_stream.h
${CMAKE_CURRENT_SOURCE_DIR}/util/hex_float.h
${CMAKE_CURRENT_SOURCE_DIR}/util/parse_number.h
${CMAKE_CURRENT_SOURCE_DIR}/util/string_utils.h
@@ -218,6 +219,7 @@
${CMAKE_CURRENT_SOURCE_DIR}/text_handler.h
${CMAKE_CURRENT_SOURCE_DIR}/validate.h
+ ${CMAKE_CURRENT_SOURCE_DIR}/util/bit_stream.cpp
${CMAKE_CURRENT_SOURCE_DIR}/util/parse_number.cpp
${CMAKE_CURRENT_SOURCE_DIR}/util/string_utils.cpp
${CMAKE_CURRENT_SOURCE_DIR}/assembly_grammar.cpp
diff --git a/source/util/bit_stream.cpp b/source/util/bit_stream.cpp
new file mode 100644
index 0000000..5dac563
--- /dev/null
+++ b/source/util/bit_stream.cpp
@@ -0,0 +1,387 @@
+// Copyright (c) 2017 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <algorithm>
+#include <cassert>
+#include <cstring>
+#include <sstream>
+#include <type_traits>
+
+#include "util/bit_stream.h"
+
+namespace spvutils {
+
+namespace {
+
+// Returns if the system is little-endian. Unfortunately only works during
+// runtime.
+bool IsLittleEndian() {
+ // This constant value allows the detection of the host machine's endianness.
+ // Accessing it as an array of bytes is valid due to C++11 section 3.10
+ // paragraph 10.
+ static const uint16_t kFF00 = 0xff00;
+ return reinterpret_cast<const unsigned char*>(&kFF00)[0] == 0;
+}
+
+// Copies uint8_t buffer to a uint64_t buffer.
+// Motivation: casting uint64_t* to uint8_t* is ok. Casting in the other
+// direction is only advisable if uint8_t* is aligned to 64-bit word boundary.
+std::vector<uint64_t> ToBuffer64(const std::vector<uint8_t>& in) {
+ std::vector<uint64_t> out;
+ out.resize((in.size() + 7) / 8, 0);
+ memcpy(out.data(), in.data(), in.size());
+ return out;
+}
+
+// Returns uint64_t containing the same bits as |val|.
+// Type size must be less than 8 bytes.
+template <typename T>
+uint64_t ToU64(T val) {
+ static_assert(sizeof(T) <= 8, "Type size too big");
+ uint64_t val64 = 0;
+ std::memcpy(&val64, &val, sizeof(T));
+ return val64;
+}
+
+// Returns value of type T containing the same bits as |val64|.
+// Type size must be less than 8 bytes. Upper (unused) bits of |val64| must be
+// zero (irrelevant, but is checked with assertion).
+template <typename T>
+T FromU64(uint64_t val64) {
+ assert(sizeof(T) == 8 || (val64 >> (sizeof(T) * 8)) == 0);
+ static_assert(sizeof(T) <= 8, "Type size too big");
+ T val = 0;
+ std::memcpy(&val, &val64, sizeof(T));
+ return val;
+}
+
+// Writes bits from |val| to |writer| in chunks of size |chunk_length|.
+// Signal bit is used to signal if the reader should expect another chunk:
+// 0 - no more chunks to follow
+// 1 - more chunks to follow
+// If number of written bits reaches |max_payload| last chunk is truncated.
+void WriteVariableWidthInternal(BitWriterInterface* writer, uint64_t val,
+ size_t chunk_length, size_t max_payload) {
+ assert(chunk_length > 0);
+ assert(chunk_length < max_payload);
+ assert(max_payload == 64 || (val >> max_payload) == 0);
+
+ if (val == 0) {
+ writer->WriteBits(0, chunk_length + 1);
+ return;
+ }
+
+ size_t payload_written = 0;
+
+ while (val) {
+ if (payload_written + chunk_length >= max_payload) {
+ // This has to be the last chunk.
+ // There is no need for the signal bit and the chunk can be truncated.
+ const size_t left_to_write = max_payload - payload_written;
+ assert((val >> left_to_write) == 0);
+ writer->WriteBits(val, left_to_write);
+ break;
+ }
+
+ writer->WriteBits(val, chunk_length);
+ payload_written += chunk_length;
+ val = val >> chunk_length;
+
+ // Write a single bit to signal if there is more to come.
+ writer->WriteBits(val ? 1 : 0, 1);
+ }
+}
+
+// Reads data written with WriteVariableWidthInternal. |chunk_length| and
+// |max_payload| should be identical to those used to write the data.
+// Returns false if the stream ends prematurely.
+bool ReadVariableWidthInternal(BitReaderInterface* reader, uint64_t* val,
+ size_t chunk_length, size_t max_payload) {
+ assert(chunk_length > 0);
+ assert(chunk_length <= max_payload);
+ size_t payload_read = 0;
+
+ while (payload_read + chunk_length < max_payload) {
+ uint64_t bits = 0;
+ if (reader->ReadBits(&bits, chunk_length) != chunk_length)
+ return false;
+
+ *val |= bits << payload_read;
+ payload_read += chunk_length;
+
+ uint64_t more_to_come = 0;
+ if (reader->ReadBits(&more_to_come, 1) != 1)
+ return false;
+
+ if (!more_to_come) {
+ return true;
+ }
+ }
+
+ // Need to read the last chunk which may be truncated. No signal bit follows.
+ uint64_t bits = 0;
+ const size_t left_to_read = max_payload - payload_read;
+ if (reader->ReadBits(&bits, left_to_read) != left_to_read)
+ return false;
+
+ *val |= bits << payload_read;
+ return true;
+}
+
+// Calls WriteVariableWidthInternal with the right max_payload argument.
+template <typename T>
+void WriteVariableWidthUnsigned(BitWriterInterface* writer, T val,
+ size_t chunk_length) {
+ static_assert(std::is_unsigned<T>::value, "Type must be unsigned");
+ static_assert(std::is_integral<T>::value, "Type must be integral");
+ WriteVariableWidthInternal(writer, val, chunk_length, sizeof(T) * 8);
+}
+
+// Calls ReadVariableWidthInternal with the right max_payload argument.
+template <typename T>
+bool ReadVariableWidthUnsigned(BitReaderInterface* reader, T* val,
+ size_t chunk_length) {
+ static_assert(std::is_unsigned<T>::value, "Type must be unsigned");
+ static_assert(std::is_integral<T>::value, "Type must be integral");
+ uint64_t val64 = 0;
+ if (!ReadVariableWidthInternal(reader, &val64, chunk_length, sizeof(T) * 8))
+ return false;
+ *val = static_cast<T>(val64);
+ assert(*val == val64);
+ return true;
+}
+
+// Encodes signed |val| to an unsigned value and calls
+// WriteVariableWidthInternal with the right max_payload argument.
+template <typename T>
+void WriteVariableWidthSigned(BitWriterInterface* writer, T val,
+ size_t chunk_length, size_t zigzag_exponent) {
+ static_assert(std::is_signed<T>::value, "Type must be signed");
+ static_assert(std::is_integral<T>::value, "Type must be integral");
+ WriteVariableWidthInternal(writer, EncodeZigZag(val, zigzag_exponent),
+ chunk_length, sizeof(T) * 8);
+}
+
+// Calls ReadVariableWidthInternal with the right max_payload argument
+// and decodes the value.
+template <typename T>
+bool ReadVariableWidthSigned(BitReaderInterface* reader, T* val,
+ size_t chunk_length, size_t zigzag_exponent) {
+ static_assert(std::is_signed<T>::value, "Type must be signed");
+ static_assert(std::is_integral<T>::value, "Type must be integral");
+ uint64_t encoded = 0;
+ if (!ReadVariableWidthInternal(reader, &encoded, chunk_length, sizeof(T) * 8))
+ return false;
+
+ const int64_t decoded = DecodeZigZag(encoded, zigzag_exponent);
+
+ *val = static_cast<T>(decoded);
+ assert(*val == decoded);
+ return true;
+}
+
+} // namespace
+
+void BitWriterInterface::WriteVariableWidthU64(uint64_t val,
+ size_t chunk_length) {
+ WriteVariableWidthUnsigned(this, val, chunk_length);
+}
+
+void BitWriterInterface::WriteVariableWidthU32(uint32_t val,
+ size_t chunk_length) {
+ WriteVariableWidthUnsigned(this, val, chunk_length);
+}
+
+void BitWriterInterface::WriteVariableWidthU16(uint16_t val,
+ size_t chunk_length) {
+ WriteVariableWidthUnsigned(this, val, chunk_length);
+}
+
+void BitWriterInterface::WriteVariableWidthU8(uint8_t val,
+ size_t chunk_length) {
+ WriteVariableWidthUnsigned(this, val, chunk_length);
+}
+
+void BitWriterInterface::WriteVariableWidthS64(int64_t val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ WriteVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+void BitWriterInterface::WriteVariableWidthS32(int32_t val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ WriteVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+void BitWriterInterface::WriteVariableWidthS16(int16_t val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ WriteVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+void BitWriterInterface::WriteVariableWidthS8(int8_t val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ WriteVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+BitWriterWord64::BitWriterWord64(size_t reserve_bits) : end_(0) {
+ buffer_.reserve(NumBitsToNumWords<64>(reserve_bits));
+}
+
+void BitWriterWord64::WriteBits(uint64_t bits, size_t num_bits) {
+ // Check that |bits| and |num_bits| are valid and consistent.
+ assert(num_bits <= 64);
+ const bool is_little_endian = IsLittleEndian();
+ assert(is_little_endian && "Big-endian architecture support not implemented");
+ if (!is_little_endian) return;
+
+ bits = GetLowerBits(bits, num_bits);
+
+ // Offset from the start of the current word.
+ const size_t offset = end_ % 64;
+
+ if (offset == 0) {
+ // If no offset, simply add |bits| as a new word to the buffer_.
+ buffer_.push_back(bits);
+ } else {
+ // Shift bits and add them to the current word after offset.
+ const uint64_t first_word = bits << offset;
+ buffer_.back() |= first_word;
+
+ // If we don't overflow to the next word, there is nothing more to do.
+
+ if (offset + num_bits > 64) {
+ // We overflow to the next word.
+ const uint64_t second_word = bits >> (64 - offset);
+ // Add remaining bits as a new word to buffer_.
+ buffer_.push_back(second_word);
+ }
+ }
+
+ // Move end_ into position for next write.
+ end_ += num_bits;
+ assert(buffer_.size() * 64 >= end_);
+}
+
+bool BitReaderInterface::ReadVariableWidthU64(uint64_t* val,
+ size_t chunk_length) {
+ return ReadVariableWidthUnsigned(this, val, chunk_length);
+}
+
+bool BitReaderInterface::ReadVariableWidthU32(uint32_t* val,
+ size_t chunk_length) {
+ return ReadVariableWidthUnsigned(this, val, chunk_length);
+}
+
+bool BitReaderInterface::ReadVariableWidthU16(uint16_t* val,
+ size_t chunk_length) {
+ return ReadVariableWidthUnsigned(this, val, chunk_length);
+}
+
+bool BitReaderInterface::ReadVariableWidthU8(uint8_t* val,
+ size_t chunk_length) {
+ return ReadVariableWidthUnsigned(this, val, chunk_length);
+}
+
+bool BitReaderInterface::ReadVariableWidthS64(int64_t* val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ return ReadVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+bool BitReaderInterface::ReadVariableWidthS32(int32_t* val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ return ReadVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+bool BitReaderInterface::ReadVariableWidthS16(int16_t* val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ return ReadVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+bool BitReaderInterface::ReadVariableWidthS8(int8_t* val,
+ size_t chunk_length,
+ size_t zigzag_exponent) {
+ return ReadVariableWidthSigned(this, val, chunk_length, zigzag_exponent);
+}
+
+BitReaderWord64::BitReaderWord64(std::vector<uint64_t>&& buffer)
+ : buffer_(std::move(buffer)), pos_(0) {}
+
+BitReaderWord64::BitReaderWord64(const std::vector<uint8_t>& buffer)
+ : buffer_(ToBuffer64(buffer)), pos_(0) {}
+
+size_t BitReaderWord64::ReadBits(uint64_t* bits, size_t num_bits) {
+ assert(num_bits <= 64);
+ const bool is_little_endian = IsLittleEndian();
+ assert(is_little_endian && "Big-endian architecture support not implemented");
+ if (!is_little_endian) return 0;
+
+ if (ReachedEnd())
+ return 0;
+
+ // Index of the current word.
+ const size_t index = pos_ / 64;
+
+ // Bit position in the current word where we start reading.
+ const size_t offset = pos_ % 64;
+
+ // Read all bits from the current word (it might be too much, but
+ // excessive bits will be removed later).
+ *bits = buffer_[index] >> offset;
+
+ const size_t num_read_from_first_word = std::min(64 - offset, num_bits);
+ pos_ += num_read_from_first_word;
+
+ if (pos_ >= buffer_.size() * 64) {
+ // Reached end of buffer_.
+ return num_read_from_first_word;
+ }
+
+ if (offset + num_bits > 64) {
+ // Requested |num_bits| overflows to next word.
+ // Write all bits from the beginning of next word to *bits after offset.
+ *bits |= buffer_[index + 1] << (64 - offset);
+ pos_ += offset + num_bits - 64;
+ }
+
+ // We likely have written more bits than requested. Clear excessive bits.
+ *bits = GetLowerBits(*bits, num_bits);
+ return num_bits;
+}
+
+bool BitReaderWord64::ReachedEnd() const {
+ return pos_ >= buffer_.size() * 64;
+}
+
+bool BitReaderWord64::OnlyZeroesLeft() const {
+ if (ReachedEnd())
+ return true;
+
+ const size_t index = pos_ / 64;
+ if (index < buffer_.size() - 1)
+ return false;
+
+ assert(index == buffer_.size() - 1);
+
+ const size_t offset = pos_ % 64;
+ const uint64_t remaining_bits = buffer_[index] >> offset;
+ return !remaining_bits;
+}
+
+} // namespace spvutils
diff --git a/source/util/bit_stream.h b/source/util/bit_stream.h
new file mode 100644
index 0000000..a139b63
--- /dev/null
+++ b/source/util/bit_stream.h
@@ -0,0 +1,378 @@
+// Copyright (c) 2017 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Contains utils for reading, writing and debug printing bit streams.
+
+#ifndef LIBSPIRV_UTIL_BIT_STREAM_H_
+#define LIBSPIRV_UTIL_BIT_STREAM_H_
+
+#include <bitset>
+#include <cstdint>
+#include <string>
+#include <sstream>
+#include <vector>
+
+namespace spvutils {
+
+// Terminology:
+// Bits - usually used for a uint64 word, first bit is the lowest.
+// Stream - std::string of '0' and '1', read left-to-right,
+// i.e. first bit is at the front and not at the end as in
+// std::bitset::to_string().
+// Bitset - std::bitset corresponding to uint64 bits and to reverse(stream).
+
+// Converts number of bits to a respective number of chunks of size N.
+// For example NumBitsToNumWords<8> returns how many bytes are needed to store
+// |num_bits|.
+template <size_t N>
+inline size_t NumBitsToNumWords(size_t num_bits) {
+ return (num_bits + (N - 1)) / N;
+}
+
+// Returns value of the same type as |in|, where all but the first |num_bits|
+// are set to zero.
+template <typename T>
+inline T GetLowerBits(T in, size_t num_bits) {
+ return sizeof(T) * 8 == num_bits ? in : in & T((T(1) << num_bits) - T(1));
+}
+
+// Encodes signed integer as unsigned in zigzag order:
+// 0 -> 0
+// -1 -> 1
+// 1 -> 2
+// -2 -> 3
+// 2 -> 4
+// Motivation: -1 is 0xFF...FF what doesn't work very well with
+// WriteVariableWidth which prefers to have as many 0 bits as possible.
+inline uint64_t EncodeZigZag(int64_t val) {
+ return (val << 1) ^ (val >> 63);
+}
+
+// Decodes signed integer encoded with EncodeZigZag.
+inline int64_t DecodeZigZag(uint64_t val) {
+ if (val & 1) {
+ // Negative.
+ // 1 -> -1
+ // 3 -> -2
+ // 5 -> -3
+ return -1 - (val >> 1);
+ } else {
+ // Non-negative.
+ // 0 -> 0
+ // 2 -> 1
+ // 4 -> 2
+ return val >> 1;
+ }
+}
+
+// Encodes signed integer as unsigned. This is a generalized version of
+// EncodeZigZag, designed to favor small positive numbers.
+// Values are transformed in blocks of 2^|block_exponent|.
+// If |block_exponent| is zero, then this degenerates into normal EncodeZigZag.
+// Example when |block_exponent| is 1 (return value is the index):
+// 0, 1, -1, -2, 2, 3, -3, -4, 4, 5, -5, -6, 6, 7, -7, -8
+// Example when |block_exponent| is 2:
+// 0, 1, 2, 3, -1, -2, -3, -4, 4, 5, 6, 7, -5, -6, -7, -8
+inline uint64_t EncodeZigZag(int64_t val, size_t block_exponent) {
+ assert(block_exponent < 64);
+ const uint64_t uval = static_cast<uint64_t>(val >= 0 ? val : -val - 1);
+ const uint64_t block_num = ((uval >> block_exponent) << 1) + (val >= 0 ? 0 : 1);
+ const uint64_t pos = GetLowerBits(uval, block_exponent);
+ return (block_num << block_exponent) + pos;
+}
+
+// Decodes signed integer encoded with EncodeZigZag. |block_exponent| must be
+// the same.
+inline int64_t DecodeZigZag(uint64_t val, size_t block_exponent) {
+ assert(block_exponent < 64);
+ const uint64_t block_num = val >> block_exponent;
+ const uint64_t pos = GetLowerBits(val, block_exponent);
+ if (block_num & 1) {
+ // Negative.
+ return -1LL - ((block_num >> 1) << block_exponent) - pos;
+ } else {
+ // Positive.
+ return ((block_num >> 1) << block_exponent) + pos;
+ }
+}
+
+// Converts |buffer| to a stream of '0' and '1'.
+template <typename T>
+std::string BufferToStream(const std::vector<T>& buffer) {
+ std::stringstream ss;
+ for (auto it = buffer.begin(); it != buffer.end(); ++it) {
+ std::string str = std::bitset<sizeof(T) * 8>(*it).to_string();
+ // Strings generated by std::bitset::to_string are read right to left.
+ // Reversing to left to right.
+ std::reverse(str.begin(), str.end());
+ ss << str;
+ }
+ return ss.str();
+}
+
+// Converts a left-to-right input string of '0' and '1' to a buffer of |T|
+// words.
+template <typename T>
+std::vector<T> StreamToBuffer(std::string str) {
+ // The input string is left-to-right, the input argument of std::bitset needs
+ // to right-to-left. Instead of reversing tokens, reverse the entire string
+ // and iterate tokens from end to begin.
+ std::reverse(str.begin(), str.end());
+ const int word_size = static_cast<int>(sizeof(T) * 8);
+ const int str_length = static_cast<int>(str.length());
+ std::vector<T> buffer;
+ buffer.reserve(NumBitsToNumWords<sizeof(T)>(str.length()));
+ for (int index = str_length - word_size; index >= 0; index -= word_size) {
+ buffer.push_back(static_cast<T>(std::bitset<sizeof(T) * 8>(
+ str, index, word_size).to_ullong()));
+ }
+ const size_t suffix_length = str.length() % word_size;
+ if (suffix_length != 0) {
+ buffer.push_back(static_cast<T>(std::bitset<sizeof(T) * 8>(
+ str, 0, suffix_length).to_ullong()));
+ }
+ return buffer;
+}
+
+// Adds '0' chars at the end of the string until the size is a multiple of N.
+template <size_t N>
+inline std::string PadToWord(std::string&& str) {
+ const size_t tail_length = str.size() % N;
+ if (tail_length != 0)
+ str += std::string(N - tail_length, '0');
+ return str;
+}
+
+// Adds '0' chars at the end of the string until the size is a multiple of N.
+template <size_t N>
+inline std::string PadToWord(const std::string& str) {
+ return PadToWord<N>(std::string(str));
+}
+
+// Converts a left-to-right stream of bits to std::bitset.
+template <size_t N>
+inline std::bitset<N> StreamToBitset(std::string str) {
+ std::reverse(str.begin(), str.end());
+ return std::bitset<N>(str);
+}
+
+// Converts first |num_bits| of std::bitset to a left-to-right stream of bits.
+template <size_t N>
+inline std::string BitsetToStream(const std::bitset<N>& bits, size_t num_bits = N) {
+ std::string str = bits.to_string().substr(N - num_bits);
+ std::reverse(str.begin(), str.end());
+ return str;
+}
+
+// Converts a left-to-right stream of bits to uint64.
+inline uint64_t StreamToBits(std::string str) {
+ std::reverse(str.begin(), str.end());
+ return std::bitset<64>(str).to_ullong();
+}
+
+// Converts first |num_bits| stored in uint64 to a left-to-right stream of bits.
+inline std::string BitsToStream(uint64_t bits, size_t num_bits = 64) {
+ std::bitset<64> bitset(bits);
+ return BitsetToStream(bitset, num_bits);
+}
+
+// Base class for writing sequences of bits.
+class BitWriterInterface {
+ public:
+ BitWriterInterface() {}
+ virtual ~BitWriterInterface() {}
+
+ // Writes lower |num_bits| in |bits| to the stream.
+ // |num_bits| must be no greater than 64.
+ virtual void WriteBits(uint64_t bits, size_t num_bits) = 0;
+
+ // Writes left-to-right string of '0' and '1' to stream.
+ // String length must be no greater than 64.
+ // Note: "01" will be writen as 0x2, not 0x1. The string doesn't represent
+ // numbers but a stream of bits in the order they come from encoder.
+ virtual void WriteStream(const std::string& bits) {
+ WriteBits(StreamToBits(bits), bits.length());
+ }
+
+ // Writes lower |num_bits| in |bits| to the stream.
+ // |num_bits| must be no greater than 64.
+ template <size_t N>
+ void WriteBitset(const std::bitset<N>& bits, size_t num_bits = N) {
+ WriteBits(bits.to_ullong(), num_bits);
+ }
+
+ // Writes |val| in chunks of size |chunk_length| followed by a signal bit:
+ // 0 - no more chunks to follow
+ // 1 - more chunks to follow
+ // for example 255 is encoded into 1111 1 1111 0 for chunk length 4.
+ // The last chunk can be truncated and signal bit omitted, if the entire
+ // payload (for example 16 bit for uint16_t has already been written).
+ void WriteVariableWidthU64(uint64_t val, size_t chunk_length);
+ void WriteVariableWidthU32(uint32_t val, size_t chunk_length);
+ void WriteVariableWidthU16(uint16_t val, size_t chunk_length);
+ void WriteVariableWidthU8(uint8_t val, size_t chunk_length);
+ void WriteVariableWidthS64(
+ int64_t val, size_t chunk_length, size_t zigzag_exponent);
+ void WriteVariableWidthS32(
+ int32_t val, size_t chunk_length, size_t zigzag_exponent);
+ void WriteVariableWidthS16(
+ int16_t val, size_t chunk_length, size_t zigzag_exponent);
+ void WriteVariableWidthS8(
+ int8_t val, size_t chunk_length, size_t zigzag_exponent);
+
+ // Returns number of bits written.
+ virtual size_t GetNumBits() const = 0;
+
+ // Provides direct access to the buffer data if implemented.
+ virtual const uint8_t* GetData() const {
+ return nullptr;
+ }
+
+ // Returns buffer size in bytes.
+ size_t GetDataSizeBytes() const {
+ return NumBitsToNumWords<8>(GetNumBits());
+ }
+
+ // Generates and returns byte array containing written bits.
+ virtual std::vector<uint8_t> GetDataCopy() const = 0;
+
+ BitWriterInterface(const BitWriterInterface&) = delete;
+ BitWriterInterface& operator=(const BitWriterInterface&) = delete;
+};
+
+// This class is an implementation of BitWriterInterface, using
+// std::vector<uint64_t> to store written bits.
+class BitWriterWord64 : public BitWriterInterface {
+ public:
+ explicit BitWriterWord64(size_t reserve_bits = 64);
+
+ void WriteBits(uint64_t bits, size_t num_bits) override;
+
+ size_t GetNumBits() const override {
+ return end_;
+ }
+
+ const uint8_t* GetData() const override {
+ return reinterpret_cast<const uint8_t*>(buffer_.data());
+ }
+
+ std::vector<uint8_t> GetDataCopy() const override {
+ return std::vector<uint8_t>(GetData(), GetData() + GetDataSizeBytes());
+ }
+
+ // Returns written stream as std::string, padded with zeroes so that the
+ // length is a multiple of 64.
+ std::string GetStreamPadded64() const {
+ return BufferToStream(buffer_);
+ }
+
+ private:
+ std::vector<uint64_t> buffer_;
+ // Total number of bits written so far. Named 'end' as analogy to std::end().
+ size_t end_;
+};
+
+// Base class for reading sequences of bits.
+class BitReaderInterface {
+ public:
+ BitReaderInterface() {}
+ virtual ~BitReaderInterface() {}
+
+ // Reads |num_bits| from the stream, stores them in |bits|.
+ // Returns number of read bits. |num_bits| must be no greater than 64.
+ virtual size_t ReadBits(uint64_t* bits, size_t num_bits) = 0;
+
+ // Reads |num_bits| from the stream, stores them in |bits|.
+ // Returns number of read bits. |num_bits| must be no greater than 64.
+ template <size_t N>
+ size_t ReadBitset(std::bitset<N>* bits, size_t num_bits = N) {
+ uint64_t val = 0;
+ size_t num_read = ReadBits(&val, num_bits);
+ if (num_read) {
+ *bits = std::bitset<N>(val);
+ }
+ return num_read;
+ }
+
+ // Reads |num_bits| from the stream, returns string in left-to-right order.
+ // The length of the returned string may be less than |num_bits| if end was
+ // reached.
+ std::string ReadStream(size_t num_bits) {
+ uint64_t bits = 0;
+ size_t num_read = ReadBits(&bits, num_bits);
+ return BitsToStream(bits, num_read);
+ }
+
+ // These two functions define 'hard' and 'soft' EOF.
+ //
+ // Returns true if the end of the buffer was reached.
+ virtual bool ReachedEnd() const = 0;
+ // Returns true if we reached the end of the buffer or are nearing it and only
+ // zero bits are left to read. Implementations of this function are allowed to
+ // commit a "false negative" error if the end of the buffer was not reached,
+ // i.e. it can return false even if indeed only zeroes are left.
+ // It is assumed that the consumer expects that
+ // the buffer stream ends with padding zeroes, and would accept this as a
+ // 'soft' EOF. Implementations of this class do not necessarily need to
+ // implement this, default behavior can simply delegate to ReachedEnd().
+ virtual bool OnlyZeroesLeft() const {
+ return ReachedEnd();
+ }
+
+ // Reads value encoded with WriteVariableWidthXXX (see BitWriterInterface).
+ // Reader and writer must use the same |chunk_length| and variable type.
+ // Returns true on success, false if the bit stream ends prematurely.
+ bool ReadVariableWidthU64(uint64_t* val, size_t chunk_length);
+ bool ReadVariableWidthU32(uint32_t* val, size_t chunk_length);
+ bool ReadVariableWidthU16(uint16_t* val, size_t chunk_length);
+ bool ReadVariableWidthU8(uint8_t* val, size_t chunk_length);
+ bool ReadVariableWidthS64(
+ int64_t* val, size_t chunk_length, size_t zigzag_exponent);
+ bool ReadVariableWidthS32(
+ int32_t* val, size_t chunk_length, size_t zigzag_exponent);
+ bool ReadVariableWidthS16(
+ int16_t* val, size_t chunk_length, size_t zigzag_exponent);
+ bool ReadVariableWidthS8(
+ int8_t* val, size_t chunk_length, size_t zigzag_exponent);
+
+ BitReaderInterface(const BitReaderInterface&) = delete;
+ BitReaderInterface& operator=(const BitReaderInterface&) = delete;
+};
+
+// This class is an implementation of BitReaderInterface which accepts both
+// uint8_t and uint64_t buffers as input. uint64_t buffers are consumed and
+// owned. uint8_t buffers are copied.
+class BitReaderWord64 : public BitReaderInterface {
+ public:
+ // Consumes and owns the buffer.
+ explicit BitReaderWord64(std::vector<uint64_t>&& buffer);
+
+ // Copies the buffer and casts it to uint64.
+ // Consuming the original buffer and casting it to uint64 is difficult,
+ // as it would potentially cause data misalignment and poor performance.
+ explicit BitReaderWord64(const std::vector<uint8_t>& buffer);
+
+ size_t ReadBits(uint64_t* bits, size_t num_bits) override;
+ bool ReachedEnd() const override;
+ bool OnlyZeroesLeft() const override;
+
+ BitReaderWord64() = delete;
+ private:
+ const std::vector<uint64_t> buffer_;
+ size_t pos_;
+};
+
+} // namespace spvutils
+
+#endif // LIBSPIRV_UTIL_BIT_STREAM_H_
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index dfddd09..926dade 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -164,6 +164,11 @@
SRCS preserve_numeric_ids_test.cpp
LIBS ${SPIRV_TOOLS})
+add_spvtools_unittest(
+ TARGET bit_stream
+ SRCS bit_stream.cpp
+ LIBS ${SPIRV_TOOLS})
+
add_subdirectory(opt)
add_subdirectory(val)
add_subdirectory(stats)
diff --git a/test/bit_stream.cpp b/test/bit_stream.cpp
new file mode 100644
index 0000000..7e18e64
--- /dev/null
+++ b/test/bit_stream.cpp
@@ -0,0 +1,1138 @@
+// Copyright (c) 2017 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "util/bit_stream.h"
+
+namespace {
+
+using spvutils::BitWriterInterface;
+using spvutils::BitReaderInterface;
+using spvutils::BitWriterWord64;
+using spvutils::BitReaderWord64;
+using spvutils::StreamToBuffer;
+using spvutils::BufferToStream;
+using spvutils::NumBitsToNumWords;
+using spvutils::PadToWord;
+using spvutils::StreamToBitset;
+using spvutils::BitsetToStream;
+using spvutils::BitsToStream;
+using spvutils::StreamToBits;
+using spvutils::GetLowerBits;
+using spvutils::EncodeZigZag;
+using spvutils::DecodeZigZag;
+
+// A simple and inefficient implementatition of BitWriterInterface,
+// using std::stringstream. Intended for tests only.
+class BitWriterStringStream : public BitWriterInterface {
+ public:
+ void WriteStream(const std::string& bits) override {
+ ss_ << bits;
+ }
+
+ void WriteBits(uint64_t bits, size_t num_bits) override {
+ assert(num_bits <= 64);
+ ss_ << BitsToStream(bits, num_bits);
+ }
+
+ size_t GetNumBits() const override {
+ return ss_.str().size();
+ }
+
+ std::vector<uint8_t> GetDataCopy() const override {
+ return StreamToBuffer<uint8_t>(ss_.str());
+ }
+
+ std::string GetStreamRaw() const {
+ return ss_.str();
+ }
+
+ private:
+ std::stringstream ss_;
+};
+
+// A simple and inefficient implementatition of BitReaderInterface.
+// Intended for tests only.
+class BitReaderFromString : public BitReaderInterface {
+ public:
+ explicit BitReaderFromString(std::string&& str)
+ : str_(std::move(str)), pos_(0) {}
+
+ explicit BitReaderFromString(const std::vector<uint64_t>& buffer)
+ : str_(BufferToStream(buffer)), pos_(0) {}
+
+ explicit BitReaderFromString(const std::vector<uint8_t>& buffer)
+ : str_(PadToWord<64>(BufferToStream(buffer))), pos_(0) {}
+
+ size_t ReadBits(uint64_t* bits, size_t num_bits) override {
+ if (ReachedEnd())
+ return 0;
+ std::string sub = str_.substr(pos_, num_bits);
+ *bits = StreamToBits(sub);
+ pos_ += sub.length();
+ return sub.length();
+ }
+
+ bool ReachedEnd() const override {
+ return pos_ >= str_.length();
+ }
+
+ const std::string& GetStreamPadded64() const {
+ return str_;
+ }
+
+ private:
+ std::string str_;
+ size_t pos_;
+};
+
+TEST(NumBitsToNumWords, Word8) {
+ EXPECT_EQ(0u, NumBitsToNumWords<8>(0));
+ EXPECT_EQ(1u, NumBitsToNumWords<8>(1));
+ EXPECT_EQ(1u, NumBitsToNumWords<8>(7));
+ EXPECT_EQ(1u, NumBitsToNumWords<8>(8));
+ EXPECT_EQ(2u, NumBitsToNumWords<8>(9));
+ EXPECT_EQ(2u, NumBitsToNumWords<8>(16));
+ EXPECT_EQ(3u, NumBitsToNumWords<8>(17));
+ EXPECT_EQ(3u, NumBitsToNumWords<8>(23));
+ EXPECT_EQ(3u, NumBitsToNumWords<8>(24));
+ EXPECT_EQ(4u, NumBitsToNumWords<8>(25));
+}
+
+TEST(NumBitsToNumWords, Word64) {
+ EXPECT_EQ(0u, NumBitsToNumWords<64>(0));
+ EXPECT_EQ(1u, NumBitsToNumWords<64>(1));
+ EXPECT_EQ(1u, NumBitsToNumWords<64>(64));
+ EXPECT_EQ(2u, NumBitsToNumWords<64>(65));
+ EXPECT_EQ(2u, NumBitsToNumWords<64>(128));
+ EXPECT_EQ(3u, NumBitsToNumWords<64>(129));
+}
+
+TEST(ZigZagCoding, Encode) {
+ EXPECT_EQ(0u, EncodeZigZag(0));
+ EXPECT_EQ(1u, EncodeZigZag(-1));
+ EXPECT_EQ(2u, EncodeZigZag(1));
+ EXPECT_EQ(3u, EncodeZigZag(-2));
+ EXPECT_EQ(4u, EncodeZigZag(2));
+ EXPECT_EQ(5u, EncodeZigZag(-3));
+ EXPECT_EQ(6u, EncodeZigZag(3));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::max()));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ EncodeZigZag(std::numeric_limits<int64_t>::min()));
+}
+
+TEST(ZigZagCoding, Decode) {
+ EXPECT_EQ(0, DecodeZigZag(0));
+ EXPECT_EQ(-1, DecodeZigZag(1));
+ EXPECT_EQ(1, DecodeZigZag(2));
+ EXPECT_EQ(-2, DecodeZigZag(3));
+ EXPECT_EQ(2, DecodeZigZag(4));
+ EXPECT_EQ(-3, DecodeZigZag(5));
+ EXPECT_EQ(3, DecodeZigZag(6));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max()));
+ EXPECT_EQ(std::numeric_limits<int64_t>::max(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1));
+}
+
+TEST(ZigZagCoding, Encode0) {
+ EXPECT_EQ(0u, EncodeZigZag(0, 0));
+ EXPECT_EQ(1u, EncodeZigZag(-1, 0));
+ EXPECT_EQ(2u, EncodeZigZag(1, 0));
+ EXPECT_EQ(3u, EncodeZigZag(-2, 0));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::max(), 0));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ EncodeZigZag(std::numeric_limits<int64_t>::min(), 0));
+}
+
+TEST(ZigZagCoding, Decode0) {
+ EXPECT_EQ(0, DecodeZigZag(0, 0));
+ EXPECT_EQ(-1, DecodeZigZag(1, 0));
+ EXPECT_EQ(1, DecodeZigZag(2, 0));
+ EXPECT_EQ(-2, DecodeZigZag(3, 0));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max(), 0));
+ EXPECT_EQ(std::numeric_limits<int64_t>::max(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 0));
+}
+
+TEST(ZigZagCoding, Decode0SameAsNormalZigZag) {
+ for (int32_t i = -10000; i < 10000; i += 123) {
+ ASSERT_EQ(DecodeZigZag(i), DecodeZigZag(i, 0));
+ }
+}
+
+TEST(ZigZagCoding, Encode0SameAsNormalZigZag) {
+ for (uint32_t i = 0; i < 10000; i += 123) {
+ ASSERT_EQ(EncodeZigZag(i), EncodeZigZag(i, 0));
+ }
+}
+
+TEST(ZigZagCoding, Encode1) {
+ EXPECT_EQ(0u, EncodeZigZag(0, 1));
+ EXPECT_EQ(1u, EncodeZigZag(1, 1));
+ EXPECT_EQ(2u, EncodeZigZag(-1, 1));
+ EXPECT_EQ(3u, EncodeZigZag(-2, 1));
+ EXPECT_EQ(4u, EncodeZigZag(2, 1));
+ EXPECT_EQ(5u, EncodeZigZag(3, 1));
+ EXPECT_EQ(6u, EncodeZigZag(-3, 1));
+ EXPECT_EQ(7u, EncodeZigZag(-4, 1));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 2,
+ EncodeZigZag(std::numeric_limits<int64_t>::max(), 1));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 1));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ EncodeZigZag(std::numeric_limits<int64_t>::min(), 1));
+}
+
+TEST(ZigZagCoding, Decode1) {
+ EXPECT_EQ(0, DecodeZigZag(0, 1));
+ EXPECT_EQ(1, DecodeZigZag(1, 1));
+ EXPECT_EQ(-1, DecodeZigZag(2, 1));
+ EXPECT_EQ(-2, DecodeZigZag(3, 1));
+ EXPECT_EQ(2, DecodeZigZag(4, 1));
+ EXPECT_EQ(3, DecodeZigZag(5, 1));
+ EXPECT_EQ(-3, DecodeZigZag(6, 1));
+ EXPECT_EQ(-4, DecodeZigZag(7, 1));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max(), 1));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min() + 1,
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 1));
+ EXPECT_EQ(std::numeric_limits<int64_t>::max(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 2, 1));
+}
+
+TEST(ZigZagCoding, Encode2) {
+ EXPECT_EQ(0u, EncodeZigZag(0, 2));
+ EXPECT_EQ(1u, EncodeZigZag(1, 2));
+ EXPECT_EQ(2u, EncodeZigZag(2, 2));
+ EXPECT_EQ(3u, EncodeZigZag(3, 2));
+ EXPECT_EQ(4u, EncodeZigZag(-1, 2));
+ EXPECT_EQ(5u, EncodeZigZag(-2, 2));
+ EXPECT_EQ(6u, EncodeZigZag(-3, 2));
+ EXPECT_EQ(7u, EncodeZigZag(-4, 2));
+ EXPECT_EQ(8u, EncodeZigZag(4, 2));
+ EXPECT_EQ(9u, EncodeZigZag(5, 2));
+ EXPECT_EQ(10u, EncodeZigZag(6, 2));
+ EXPECT_EQ(11u, EncodeZigZag(7, 2));
+ EXPECT_EQ(12u, EncodeZigZag(-5, 2));
+ EXPECT_EQ(13u, EncodeZigZag(-6, 2));
+ EXPECT_EQ(14u, EncodeZigZag(-7, 2));
+ EXPECT_EQ(15u, EncodeZigZag(-8, 2));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 4,
+ EncodeZigZag(std::numeric_limits<int64_t>::max(), 2));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 3,
+ EncodeZigZag(std::numeric_limits<int64_t>::min() + 3, 2));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 2,
+ EncodeZigZag(std::numeric_limits<int64_t>::min() + 2, 2));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 2));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ EncodeZigZag(std::numeric_limits<int64_t>::min(), 2));
+}
+
+TEST(ZigZagCoding, Decode2) {
+ EXPECT_EQ(0, DecodeZigZag(0, 2));
+ EXPECT_EQ(1, DecodeZigZag(1, 2));
+ EXPECT_EQ(2, DecodeZigZag(2, 2));
+ EXPECT_EQ(3, DecodeZigZag(3, 2));
+ EXPECT_EQ(-1, DecodeZigZag(4, 2));
+ EXPECT_EQ(-2, DecodeZigZag(5, 2));
+ EXPECT_EQ(-3, DecodeZigZag(6, 2));
+ EXPECT_EQ(-4, DecodeZigZag(7, 2));
+ EXPECT_EQ(4, DecodeZigZag(8, 2));
+ EXPECT_EQ(5, DecodeZigZag(9, 2));
+ EXPECT_EQ(6, DecodeZigZag(10, 2));
+ EXPECT_EQ(7, DecodeZigZag(11, 2));
+ EXPECT_EQ(-5, DecodeZigZag(12, 2));
+ EXPECT_EQ(-6, DecodeZigZag(13, 2));
+ EXPECT_EQ(-7, DecodeZigZag(14, 2));
+ EXPECT_EQ(-8, DecodeZigZag(15, 2));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max(), 2));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min() + 1,
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 1, 2));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min() + 2,
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 2, 2));
+ EXPECT_EQ(std::numeric_limits<int64_t>::min() + 3,
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 3, 2));
+ EXPECT_EQ(std::numeric_limits<int64_t>::max(),
+ DecodeZigZag(std::numeric_limits<uint64_t>::max() - 4, 2));
+}
+
+TEST(ZigZagCoding, Encode63) {
+ EXPECT_EQ(0u, EncodeZigZag(0, 63));
+
+ for (int64_t i = 0; i < 0xFFFFFFFF; i += 1234567) {
+ const int64_t positive_val = GetLowerBits(i * i * i + i * i, 63) | 1UL;
+ ASSERT_EQ(static_cast<uint64_t>(positive_val),
+ EncodeZigZag(positive_val, 63));
+ ASSERT_EQ((1ULL << 63) - 1 + positive_val, EncodeZigZag(-positive_val, 63));
+ }
+
+ EXPECT_EQ((1ULL << 63) - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::max(), 63));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max() - 1,
+ EncodeZigZag(std::numeric_limits<int64_t>::min() + 1, 63));
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ EncodeZigZag(std::numeric_limits<int64_t>::min(), 63));
+}
+
+TEST(BufToStream, UInt8_Empty) {
+ const std::string expected_bits = "";
+ std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
+ EXPECT_TRUE(buffer.empty());
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(BufToStream, UInt8_OneWord) {
+ const std::string expected_bits = "00101100";
+ std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
+ EXPECT_EQ(
+ std::vector<uint8_t>(
+ {static_cast<uint8_t>(StreamToBitset<8>(expected_bits).to_ulong())}),
+ buffer);
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(BufToStream, UInt8_MultipleWords) {
+ const std::string expected_bits = "00100010""01101010""01111101""00100010";
+ std::vector<uint8_t> buffer = StreamToBuffer<uint8_t>(expected_bits);
+ EXPECT_EQ(
+ std::vector<uint8_t>({
+ static_cast<uint8_t>(StreamToBitset<8>("00100010").to_ulong()),
+ static_cast<uint8_t>(StreamToBitset<8>("01101010").to_ulong()),
+ static_cast<uint8_t>(StreamToBitset<8>("01111101").to_ulong()),
+ static_cast<uint8_t>(StreamToBitset<8>("00100010").to_ulong()),
+ }), buffer);
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(BufToStream, UInt64_Empty) {
+ const std::string expected_bits = "";
+ std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
+ EXPECT_TRUE(buffer.empty());
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(BufToStream, UInt64_OneWord) {
+ const std::string expected_bits =
+ "0001000111101110011001101010101000100010110011000100010010001000";
+ std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
+ ASSERT_EQ(1u, buffer.size());
+ EXPECT_EQ(0x1122334455667788u, buffer[0]);
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(BufToStream, UInt64_Unaligned) {
+ const std::string expected_bits =
+ "0010001001101010011111010010001001001010000111110010010010010101"
+ "0010001001101010011111111111111111111111";
+ std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
+ EXPECT_EQ(std::vector<uint64_t>({
+ StreamToBits(expected_bits.substr(0, 64)),
+ StreamToBits(expected_bits.substr(64, 64)),
+ }), buffer);
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(PadToWord<64>(expected_bits), result_bits);
+}
+
+TEST(BufToStream, UInt64_MultipleWords) {
+ const std::string expected_bits =
+ "0010001001101010011111010010001001001010000111110010010010010101"
+ "0010001001101010011111111111111111111111000111110010010010010111"
+ "0000000000000000000000000000000000000000000000000010010011111111";
+ std::vector<uint64_t> buffer = StreamToBuffer<uint64_t>(expected_bits);
+ EXPECT_EQ(std::vector<uint64_t>({
+ StreamToBits(expected_bits.substr(0, 64)),
+ StreamToBits(expected_bits.substr(64, 64)),
+ StreamToBits(expected_bits.substr(128, 64)),
+ }), buffer);
+ const std::string result_bits = BufferToStream(buffer);
+ EXPECT_EQ(expected_bits, result_bits);
+}
+
+TEST(PadToWord, Test) {
+ EXPECT_EQ("10100000", PadToWord<8>("101"));
+ EXPECT_EQ("10100000""00000000", PadToWord<16>("101"));
+ EXPECT_EQ("10100000""00000000""00000000""00000000",
+ PadToWord<32>("101"));
+ EXPECT_EQ("10100000""00000000""00000000""00000000"
+ "00000000""00000000""00000000""00000000",
+ PadToWord<64>("101"));
+}
+
+TEST(BitWriterStringStream, Empty) {
+ BitWriterStringStream writer;
+ EXPECT_EQ(0u, writer.GetNumBits());
+ EXPECT_EQ(0u, writer.GetDataSizeBytes());
+ EXPECT_EQ("", writer.GetStreamRaw());
+}
+
+TEST(BitWriterStringStream, WriteStream) {
+ BitWriterStringStream writer;
+ const std::string bits1 = "1011111111111111111";
+ writer.WriteStream(bits1);
+ EXPECT_EQ(19u, writer.GetNumBits());
+ EXPECT_EQ(3u, writer.GetDataSizeBytes());
+ EXPECT_EQ(bits1, writer.GetStreamRaw());
+
+ const std::string bits2 = "10100001010101010000111111111111111111111111111";
+ writer.WriteStream(bits2);
+ EXPECT_EQ(66u, writer.GetNumBits());
+ EXPECT_EQ(9u, writer.GetDataSizeBytes());
+ EXPECT_EQ(bits1 + bits2, writer.GetStreamRaw());
+}
+
+TEST(BitWriterStringStream, WriteBitSet) {
+ BitWriterStringStream writer;
+ const std::string bits1 = "10101";
+ writer.WriteBitset(StreamToBitset<16>(bits1));
+ EXPECT_EQ(16u, writer.GetNumBits());
+ EXPECT_EQ(2u, writer.GetDataSizeBytes());
+ EXPECT_EQ(PadToWord<16>(bits1), writer.GetStreamRaw());
+}
+
+TEST(BitWriterStringStream, WriteBits) {
+ BitWriterStringStream writer;
+ const uint64_t bits1 = 0x1 | 0x2 | 0x10;
+ writer.WriteBits(bits1, 5);
+ EXPECT_EQ(5u, writer.GetNumBits());
+ EXPECT_EQ(1u, writer.GetDataSizeBytes());
+ EXPECT_EQ("11001", writer.GetStreamRaw());
+}
+
+TEST(BitWriterStringStream, WriteMultiple) {
+ BitWriterStringStream writer;
+
+ std::string expected_result;
+ const std::string bits1 = "101001111111001100010000001110001111111100";
+ writer.WriteStream(bits1);
+
+ const std::string bits2 = "10100011000010010101";
+ writer.WriteBitset(StreamToBitset<20>(bits2));
+
+ const uint64_t val = 0x1 | 0x2 | 0x10;
+ const std::string bits3 = BitsToStream(val, 8);
+ writer.WriteBits(val, 8);
+
+ const std::string expected = bits1 + bits2 + bits3;
+
+ EXPECT_EQ(expected.length(), writer.GetNumBits());
+ EXPECT_EQ(9u, writer.GetDataSizeBytes());
+ EXPECT_EQ(expected, writer.GetStreamRaw());
+
+ EXPECT_EQ(PadToWord<8>(expected), BufferToStream(writer.GetDataCopy()));
+}
+
+TEST(BitWriterWord64, Empty) {
+ BitWriterWord64 writer;
+ EXPECT_EQ(0u, writer.GetNumBits());
+ EXPECT_EQ(0u, writer.GetDataSizeBytes());
+ EXPECT_EQ("", writer.GetStreamPadded64());
+}
+
+TEST(BitWriterWord64, WriteStream) {
+ BitWriterWord64 writer;
+ std::string expected;
+
+ {
+ const std::string bits = "101";
+ expected += bits;
+ writer.WriteStream(bits);
+ EXPECT_EQ(expected.length(), writer.GetNumBits());
+ EXPECT_EQ(1u, writer.GetDataSizeBytes());
+ EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
+ }
+
+ {
+ const std::string bits = "10000111111111110000000";
+ expected += bits;
+ writer.WriteStream(bits);
+ EXPECT_EQ(expected.length(), writer.GetNumBits());
+ EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
+ }
+
+ {
+ const std::string bits = "101001111111111100000111111111111100";
+ expected += bits;
+ writer.WriteStream(bits);
+ EXPECT_EQ(expected.length(), writer.GetNumBits());
+ EXPECT_EQ(PadToWord<64>(expected), writer.GetStreamPadded64());
+ }
+}
+
+TEST(BitWriterWord64, WriteBitset) {
+ BitWriterWord64 writer;
+ const std::string bits1 = "10101";
+ writer.WriteBitset(StreamToBitset<16>(bits1), 12);
+ EXPECT_EQ(12u, writer.GetNumBits());
+ EXPECT_EQ(2u, writer.GetDataSizeBytes());
+ EXPECT_EQ(PadToWord<64>(bits1), writer.GetStreamPadded64());
+}
+
+TEST(BitWriterWord64, WriteBits) {
+ BitWriterWord64 writer;
+ const uint64_t bits1 = 0x1 | 0x2 | 0x10;
+ writer.WriteBits(bits1, 5);
+ writer.WriteBits(bits1, 5);
+ writer.WriteBits(bits1, 5);
+ EXPECT_EQ(15u, writer.GetNumBits());
+ EXPECT_EQ(2u, writer.GetDataSizeBytes());
+ EXPECT_EQ(PadToWord<64>("110011100111001"), writer.GetStreamPadded64());
+}
+
+TEST(BitWriterWord64, ComparisonTestWriteLotsOfBits) {
+ BitWriterStringStream writer1;
+ BitWriterWord64 writer2(16384);
+
+ for (uint64_t i = 0; i < 65000; i += 25) {
+ writer1.WriteBits(i, 16);
+ writer2.WriteBits(i, 16);
+ ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
+ }
+
+ EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
+ writer2.GetStreamPadded64());
+}
+
+TEST(BitWriterWord64, ComparisonTestWriteLotsOfStreams) {
+ BitWriterStringStream writer1;
+ BitWriterWord64 writer2(16384);
+
+ for (int i = 0; i < 1000; ++i) {
+ std::string bits = "1111100000";
+ if (i % 2)
+ bits += "101010";
+ if (i % 3)
+ bits += "1110100";
+ if (i % 5)
+ bits += "1110100111111111111";
+ writer1.WriteStream(bits);
+ writer2.WriteStream(bits);
+ ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
+ }
+
+ EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
+ writer2.GetStreamPadded64());
+}
+
+TEST(BitWriterWord64, ComparisonTestWriteLotsOfBitsets) {
+ BitWriterStringStream writer1;
+ BitWriterWord64 writer2(16384);
+
+ for (uint64_t i = 0; i < 65000; i += 25) {
+ std::bitset<16> bits1(i);
+ std::bitset<24> bits2(i);
+ writer1.WriteBitset(bits1);
+ writer1.WriteBitset(bits2);
+ writer2.WriteBitset(bits1);
+ writer2.WriteBitset(bits2);
+ ASSERT_EQ(writer1.GetNumBits(), writer2.GetNumBits());
+ }
+
+ EXPECT_EQ(PadToWord<64>(writer1.GetStreamRaw()),
+ writer2.GetStreamPadded64());
+}
+
+TEST(GetLowerBits, Test) {
+ EXPECT_EQ(0u, GetLowerBits<uint8_t>(255, 0));
+ EXPECT_EQ(1u, GetLowerBits<uint8_t>(255, 1));
+ EXPECT_EQ(3u, GetLowerBits<uint8_t>(255, 2));
+ EXPECT_EQ(7u, GetLowerBits<uint8_t>(255, 3));
+ EXPECT_EQ(15u, GetLowerBits<uint8_t>(255, 4));
+ EXPECT_EQ(31u, GetLowerBits<uint8_t>(255, 5));
+ EXPECT_EQ(63u, GetLowerBits<uint8_t>(255, 6));
+ EXPECT_EQ(127u, GetLowerBits<uint8_t>(255, 7));
+ EXPECT_EQ(255u, GetLowerBits<uint8_t>(255, 8));
+ EXPECT_EQ(0xFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 8));
+ EXPECT_EQ(0xFFFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 16));
+ EXPECT_EQ(0xFFFFFFu, GetLowerBits<uint32_t>(0xFFFFFFFF, 24));
+ EXPECT_EQ(0xFFFFFFu, GetLowerBits<uint64_t>(0xFFFFFFFFFFFF, 24));
+ EXPECT_EQ(0xFFFFFFFFFFFFFFFFu,
+ GetLowerBits<uint64_t>(0xFFFFFFFFFFFFFFFFu, 64));
+ EXPECT_EQ(StreamToBits("1010001110"),
+ GetLowerBits<uint64_t>(
+ StreamToBits("1010001110111101111111"), 10));
+}
+
+TEST(BitReaderFromString, FromU8) {
+ std::vector<uint8_t> buffer = {
+ 0xAA, 0xBB, 0xCC, 0xDD,
+ };
+
+ const std::string total_stream =
+ "01010101""11011101""00110011""10111011";
+
+ BitReaderFromString reader(buffer);
+ EXPECT_EQ(PadToWord<64>(total_stream), reader.GetStreamPadded64());
+
+ uint64_t bits = 0;
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(PadToWord<64>("01"), BitsToStream(bits));
+ EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
+ EXPECT_EQ(PadToWord<64>("01010111011101001100"), BitsToStream(bits));
+ EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
+ EXPECT_EQ(PadToWord<64>("11101110110000000000"), BitsToStream(bits));
+ EXPECT_EQ(22u, reader.ReadBits(&bits, 30));
+ EXPECT_EQ(PadToWord<64>("0000000000000000000000"), BitsToStream(bits));
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderFromString, FromU64) {
+ std::vector<uint64_t> buffer = {
+ 0xAAAAAAAAAAAAAAAA,
+ 0xBBBBBBBBBBBBBBBB,
+ 0xCCCCCCCCCCCCCCCC,
+ 0xDDDDDDDDDDDDDDDD,
+ };
+
+ const std::string total_stream =
+ "0101010101010101010101010101010101010101010101010101010101010101"
+ "1101110111011101110111011101110111011101110111011101110111011101"
+ "0011001100110011001100110011001100110011001100110011001100110011"
+ "1011101110111011101110111011101110111011101110111011101110111011";
+
+ BitReaderFromString reader(buffer);
+ EXPECT_EQ(total_stream, reader.GetStreamPadded64());
+
+ uint64_t bits = 0;
+ size_t pos = 0;
+ size_t to_read = 5;
+ while (reader.ReadBits(&bits, to_read) > 0) {
+ EXPECT_EQ(BitsToStream(bits),
+ PadToWord<64>(total_stream.substr(pos, to_read)));
+ pos += to_read;
+ to_read = (to_read + 35) % 64 + 1;
+ }
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, ReadBitsSingleByte) {
+ BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xF0)}));
+ EXPECT_FALSE(reader.ReachedEnd());
+
+ uint64_t bits = 0;
+ EXPECT_EQ(1u, reader.ReadBits(&bits, 1));
+ EXPECT_EQ(0u, bits);
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(0u, bits);
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(2u, bits);
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(3u, bits);
+ EXPECT_FALSE(reader.OnlyZeroesLeft());
+ EXPECT_FALSE(reader.ReachedEnd());
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(1u, bits);
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+ EXPECT_FALSE(reader.ReachedEnd());
+ EXPECT_EQ(55u, reader.ReadBits(&bits, 64));
+ EXPECT_EQ(0u, bits);
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, ReadBitsetSingleByte) {
+ BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xCC)}));
+ std::bitset<4> bits;
+ EXPECT_EQ(2u, reader.ReadBitset(&bits, 2));
+ EXPECT_EQ(0u, bits.to_ullong());
+ EXPECT_EQ(2u, reader.ReadBitset(&bits, 2));
+ EXPECT_EQ(3u, bits.to_ullong());
+ EXPECT_FALSE(reader.OnlyZeroesLeft());
+ EXPECT_EQ(4u, reader.ReadBitset(&bits, 4));
+ EXPECT_EQ(12u, bits.to_ullong());
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+}
+
+TEST(BitReaderWord64, ReadStreamSingleByte) {
+ BitReaderWord64 reader(std::vector<uint8_t>({uint8_t(0xAA)}));
+ EXPECT_EQ("", reader.ReadStream(0));
+ EXPECT_EQ("0", reader.ReadStream(1));
+ EXPECT_EQ("101", reader.ReadStream(3));
+ EXPECT_EQ("01010000", reader.ReadStream(8));
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+ EXPECT_EQ("0000000000000000000000000000000000000000000000000000",
+ reader.ReadStream(64));
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, ReadStreamEmpty) {
+ std::vector<uint64_t> buffer;
+ BitReaderWord64 reader(std::move(buffer));
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+ EXPECT_TRUE(reader.ReachedEnd());
+ EXPECT_EQ("", reader.ReadStream(10));
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, ReadBitsTwoWords) {
+ std::vector<uint64_t> buffer = {
+ 0x0000000000000001,
+ 0x0000000000FFFFFF
+ };
+
+ BitReaderWord64 reader(std::move(buffer));
+
+ uint64_t bits = 0;
+ EXPECT_EQ(1u, reader.ReadBits(&bits, 1));
+ EXPECT_EQ(1u, bits);
+ EXPECT_EQ(62u, reader.ReadBits(&bits, 62));
+ EXPECT_EQ(0u, bits);
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(2u, bits);
+ EXPECT_EQ(3u, reader.ReadBits(&bits, 3));
+ EXPECT_EQ(7u, bits);
+ EXPECT_FALSE(reader.OnlyZeroesLeft());
+ EXPECT_EQ(32u, reader.ReadBits(&bits, 32));
+ EXPECT_EQ(0xFFFFFu, bits);
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+ EXPECT_FALSE(reader.ReachedEnd());
+ EXPECT_EQ(28u, reader.ReadBits(&bits, 32));
+ EXPECT_EQ(0u, bits);
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, FromU8) {
+ std::vector<uint8_t> buffer = {
+ 0xAA, 0xBB, 0xCC, 0xDD,
+ };
+
+ BitReaderWord64 reader(std::move(buffer));
+
+ uint64_t bits = 0;
+ EXPECT_EQ(2u, reader.ReadBits(&bits, 2));
+ EXPECT_EQ(PadToWord<64>("01"), BitsToStream(bits));
+ EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
+ EXPECT_EQ(PadToWord<64>("01010111011101001100"), BitsToStream(bits));
+ EXPECT_EQ(20u, reader.ReadBits(&bits, 20));
+ EXPECT_EQ(PadToWord<64>("11101110110000000000"), BitsToStream(bits));
+ EXPECT_EQ(22u, reader.ReadBits(&bits, 30));
+ EXPECT_EQ(PadToWord<64>("0000000000000000000000"), BitsToStream(bits));
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, FromU64) {
+ std::vector<uint64_t> buffer = {
+ 0xAAAAAAAAAAAAAAAA,
+ 0xBBBBBBBBBBBBBBBB,
+ 0xCCCCCCCCCCCCCCCC,
+ 0xDDDDDDDDDDDDDDDD,
+ };
+
+ const std::string total_stream =
+ "0101010101010101010101010101010101010101010101010101010101010101"
+ "1101110111011101110111011101110111011101110111011101110111011101"
+ "0011001100110011001100110011001100110011001100110011001100110011"
+ "1011101110111011101110111011101110111011101110111011101110111011";
+
+ BitReaderWord64 reader(std::move(buffer));
+
+ uint64_t bits = 0;
+ size_t pos = 0;
+ size_t to_read = 5;
+ while (reader.ReadBits(&bits, to_read) > 0) {
+ EXPECT_EQ(BitsToStream(bits),
+ PadToWord<64>(total_stream.substr(pos, to_read)));
+ pos += to_read;
+ to_read = (to_read + 35) % 64 + 1;
+ }
+ EXPECT_TRUE(reader.ReachedEnd());
+}
+
+TEST(BitReaderWord64, ComparisonLotsOfU8) {
+ std::vector<uint8_t> buffer;
+ for(uint32_t i = 0; i < 10003; ++i) {
+ buffer.push_back(static_cast<uint8_t>(i % 255));
+ }
+
+ BitReaderFromString reader1(buffer);
+ BitReaderWord64 reader2(std::move(buffer));
+
+ uint64_t bits1 = 0, bits2 = 0;
+ size_t to_read = 5;
+ while (reader1.ReadBits(&bits1, to_read) > 0) {
+ reader2.ReadBits(&bits2, to_read);
+ EXPECT_EQ(bits1, bits2);
+ to_read = (to_read + 35) % 64 + 1;
+ }
+
+ EXPECT_EQ(0u, reader2.ReadBits(&bits2, 1));
+}
+
+TEST(BitReaderWord64, ComparisonLotsOfU64) {
+ std::vector<uint64_t> buffer;
+ for(uint64_t i = 0; i < 1000; ++i) {
+ buffer.push_back(i);
+ }
+
+ BitReaderFromString reader1(buffer);
+ BitReaderWord64 reader2(std::move(buffer));
+
+ uint64_t bits1 = 0, bits2 = 0;
+ size_t to_read = 5;
+ while (reader1.ReadBits(&bits1, to_read) > 0) {
+ reader2.ReadBits(&bits2, to_read);
+ EXPECT_EQ(bits1, bits2);
+ to_read = (to_read + 35) % 64 + 1;
+ }
+
+ EXPECT_EQ(0u, reader2.ReadBits(&bits2, 1));
+}
+
+TEST(ReadWriteWord64, ReadWriteLotsOfBits) {
+ BitWriterWord64 writer(16384);
+ for (uint64_t i = 0; i < 65000; i += 25) {
+ const size_t num_bits = i % 64 + 1;
+ const uint64_t bits = i >> (64 - num_bits);
+ writer.WriteBits(bits, num_bits);
+ }
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ for (uint64_t i = 0; i < 65000; i += 25) {
+ const size_t num_bits = i % 64 + 1;
+ const uint64_t expected_bits = i >> (64 - num_bits);
+ uint64_t bits = 0;
+ reader.ReadBits(&bits, num_bits);
+ EXPECT_EQ(expected_bits, bits);
+ }
+
+ EXPECT_TRUE(reader.OnlyZeroesLeft());
+}
+
+TEST(VariableWidthWrite, Write0U) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU64(0, 2);
+ EXPECT_EQ("000", writer.GetStreamRaw ());
+ writer.WriteVariableWidthU32(0, 2);
+ EXPECT_EQ("000""000", writer.GetStreamRaw());
+ writer.WriteVariableWidthU16(0, 2);
+ EXPECT_EQ("000""000""000", writer.GetStreamRaw());
+ writer.WriteVariableWidthU8(0, 2);
+ EXPECT_EQ("000""000""000""000", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, Write0S) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthS64(0, 2, 0);
+ EXPECT_EQ("000", writer.GetStreamRaw ());
+ writer.WriteVariableWidthS32(0, 2, 0);
+ EXPECT_EQ("000""000", writer.GetStreamRaw());
+ writer.WriteVariableWidthS16(0, 2, 0);
+ EXPECT_EQ("000""000""000", writer.GetStreamRaw());
+ writer.WriteVariableWidthS8(0, 2, 0);
+ EXPECT_EQ("000""000""000""000", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, WriteSmallUnsigned) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU64(1, 2);
+ EXPECT_EQ("100", writer.GetStreamRaw ());
+ writer.WriteVariableWidthU32(2, 2);
+ EXPECT_EQ("100""010", writer.GetStreamRaw());
+ writer.WriteVariableWidthU16(3, 2);
+ EXPECT_EQ("100""010""110", writer.GetStreamRaw());
+ writer.WriteVariableWidthU8(4, 2);
+ EXPECT_EQ("100""010""110""001100", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, WriteSmallSigned) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthS64(1, 2, 0);
+ EXPECT_EQ("010", writer.GetStreamRaw ());
+ writer.WriteVariableWidthS64(-1, 2, 0);
+ EXPECT_EQ("010""100", writer.GetStreamRaw());
+ writer.WriteVariableWidthS16(3, 2, 0);
+ EXPECT_EQ("010""100""011100", writer.GetStreamRaw());
+ writer.WriteVariableWidthS8(-4, 2, 0);
+ EXPECT_EQ("010""100""011100""111100", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, U64Val127ChunkLength7) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU64(127, 7);
+ EXPECT_EQ("1111111""0", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, U32Val255ChunkLength7) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU32(255, 7);
+ EXPECT_EQ("1111111""1""1000000""0", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, U16Val2ChunkLength4) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU16(2, 4);
+ EXPECT_EQ("0100""0", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, U8Val128ChunkLength7) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU8(128, 7);
+ EXPECT_EQ("0000000""1""1", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, U64ValAAAAChunkLength2) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthU64(0xAAAA, 2);
+ EXPECT_EQ("01""1""01""1""01""1""01""1"
+ "01""1""01""1""01""1""01""0", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthWrite, S8ValM128ChunkLength7) {
+ BitWriterStringStream writer;
+ writer.WriteVariableWidthS8(-128, 7, 0);
+ EXPECT_EQ("1111111""1""1", writer.GetStreamRaw());
+}
+
+TEST(VariableWidthRead, U64Val127ChunkLength7) {
+ BitReaderFromString reader("1111111""0");
+ uint64_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 7));
+ EXPECT_EQ(127u, val);
+}
+
+TEST(VariableWidthRead, U32Val255ChunkLength7) {
+ BitReaderFromString reader("1111111""1""1000000""0");
+ uint32_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU32(&val, 7));
+ EXPECT_EQ(255u, val);
+}
+
+TEST(VariableWidthRead, U16Val2ChunkLength4) {
+ BitReaderFromString reader("0100""0");
+ uint16_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU16(&val, 4));
+ EXPECT_EQ(2u, val);
+}
+
+TEST(VariableWidthRead, U8Val128ChunkLength7) {
+ BitReaderFromString reader("0000000""1""1");
+ uint8_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU8(&val, 7));
+ EXPECT_EQ(128u, val);
+}
+
+TEST(VariableWidthRead, U64ValAAAAChunkLength2) {
+ BitReaderFromString reader("01""1""01""1""01""1""01""1"
+ "01""1""01""1""01""1""01""0");
+ uint64_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 2));
+ EXPECT_EQ(0xAAAAu, val);
+}
+
+TEST(VariableWidthRead, S8ValM128ChunkLength7) {
+ BitReaderFromString reader("1111111""1""1");
+ int8_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthS8(&val, 7, 0));
+ EXPECT_EQ(-128, val);
+}
+
+TEST(VariableWidthRead, FailTooShort) {
+ BitReaderFromString reader("00000001100000");
+ uint64_t val = 0;
+ ASSERT_FALSE(reader.ReadVariableWidthU64(&val, 7));
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadU64) {
+ for (uint64_t i = 0; i < 1000000; i += 1234) {
+ const uint64_t val = i * i * i;
+ const size_t chunk_length = i % 16 + 1;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthU64(val, chunk_length);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ uint64_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU64(&read_val, chunk_length));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadS64) {
+ for (int64_t i = 0; i < 1000000; i += 4321) {
+ const int64_t val = i * i * (i % 2 ? -i : i);
+ const size_t chunk_length = i % 16 + 1;
+ const size_t zigzag_exponent = i % 13;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthS64(val, chunk_length, zigzag_exponent);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ int64_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthS64(&read_val, chunk_length,
+ zigzag_exponent));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadU32) {
+ for (uint32_t i = 0; i < 100000; i += 123) {
+ const uint32_t val = i * i;
+ const size_t chunk_length = i % 16 + 1;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthU32(val, chunk_length);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ uint32_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU32(&read_val, chunk_length));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadS32) {
+ for (int32_t i = 0; i < 100000; i += 123) {
+ const int32_t val = i * (i % 2 ? -i : i);
+ const size_t chunk_length = i % 16 + 1;
+ const size_t zigzag_exponent = i % 11;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthS32(val, chunk_length, zigzag_exponent);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ int32_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthS32(
+ &read_val, chunk_length, zigzag_exponent));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadU16) {
+ for (int i = 0; i < 65536; i += 123) {
+ const uint16_t val = static_cast<int16_t>(i);
+ const size_t chunk_length = val % 10 + 1;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthU16(val, chunk_length);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ uint16_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU16(&read_val, chunk_length));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadS16) {
+ for (int i = -32768; i < 32768; i += 123) {
+ const int16_t val = static_cast<int16_t>(i);
+ const size_t chunk_length = std::abs(i) % 10 + 1;
+ const size_t zigzag_exponent = std::abs(i) % 7;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthS16(val, chunk_length, zigzag_exponent);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ int16_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthS16(&read_val, chunk_length,
+ zigzag_exponent));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadU8) {
+ for (int i = 0; i < 256; ++i) {
+ const uint8_t val = static_cast<uint8_t>(i);
+ const size_t chunk_length = val % 5 + 1;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthU8(val, chunk_length);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ uint8_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU8(&read_val, chunk_length));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SingleWriteReadS8) {
+ for (int i = -128; i < 128; ++i) {
+ const int8_t val = static_cast<int8_t>(i);
+ const size_t chunk_length = std::abs(i) % 5 + 1;
+ const size_t zigzag_exponent = std::abs(i) % 3;
+
+ BitWriterWord64 writer;
+ writer.WriteVariableWidthS8(val, chunk_length, zigzag_exponent);
+
+ BitReaderWord64 reader(writer.GetDataCopy());
+ int8_t read_val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthS8(&read_val, chunk_length,
+ zigzag_exponent));
+
+ ASSERT_EQ(val, read_val) << "Chunk length " << chunk_length;
+ }
+}
+
+TEST(VariableWidthWriteRead, SmallNumbersChunkLength4) {
+ const std::vector<uint64_t> expected_values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+ BitWriterWord64 writer;
+ for (uint64_t val : expected_values) {
+ writer.WriteVariableWidthU64(val, 4);
+ }
+
+ EXPECT_EQ(50u, writer.GetNumBits());
+
+ std::vector<uint64_t> actual_values;
+ BitReaderWord64 reader(writer.GetDataCopy());
+ while(!reader.OnlyZeroesLeft()) {
+ uint64_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 4));
+ actual_values.push_back(val);
+ }
+
+ EXPECT_EQ(expected_values, actual_values);
+}
+
+TEST(VariableWidthWriteRead, VariedNumbersChunkLength8) {
+ const std::vector<uint64_t> expected_values = {1000, 0, 255, 4294967296};
+ const size_t kExpectedNumBits = 9 * (2 + 1 + 1 + 5);
+
+ BitWriterWord64 writer;
+ for (uint64_t val : expected_values) {
+ writer.WriteVariableWidthU64(val, 8);
+ }
+
+ EXPECT_EQ(kExpectedNumBits, writer.GetNumBits());
+
+ std::vector<uint64_t> actual_values;
+ BitReaderWord64 reader(writer.GetDataCopy());
+ while (!reader.OnlyZeroesLeft()) {
+ uint64_t val = 0;
+ ASSERT_TRUE(reader.ReadVariableWidthU64(&val, 8));
+ actual_values.push_back(val);
+ }
+
+ EXPECT_EQ(expected_values, actual_values);
+}
+
+} // anonymous namespace
