123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188 |
- #ifndef SIMPLE_COMPRESS_BITS_HPP
- #define SIMPLE_COMPRESS_BITS_HPP
- #include <type_traits> // std::enable_if_t std::is_integral_v std::is_same_v std::make_unsigned_t std::underlying_type_t std::is_unsigned_v std::is_enum_v std::is_enum_v
- #include <cstddef> // std::size_t
- #include <limits> // std::numeric_limits
- #include <iterator> // std::iterator_traits
- #include <algorithm> // std::min
- #include <string> // std::string
- #include "simple/support/type_traits.hpp" // support::remove_cvref_t
- namespace simple::compress
- {
- template <typename T,
- std::enable_if_t<std::is_integral_v<T>>* = nullptr>
- constexpr std::size_t bit_count(const T&) noexcept
- {
- if constexpr (std::is_same_v<T,bool>)
- return 1;
- else
- return std::numeric_limits<std::make_unsigned_t<T>>::digits;
- }
- template <typename T,
- std::enable_if_t<std::is_enum_v<T>>* = nullptr>
- constexpr std::size_t bit_count(const T& x) noexcept
- { return bit_count(static_cast<std::underlying_type_t<T>>(x)); }
- template <typename T,
- std::enable_if_t<std::is_integral_v<T>>* = nullptr>
- constexpr std::size_t bit_offset(const T&) noexcept
- {
- if constexpr (std::is_same_v<T,bool>)
- return std::numeric_limits<unsigned>::digits - 1;
- else
- return 0;
- }
- template <typename T,
- std::enable_if_t<std::is_enum_v<T>>* = nullptr>
- constexpr std::size_t bit_offset(const T& x) noexcept
- { return bit_offset(static_cast<std::underlying_type_t<T>>(x)); }
- template <typename T,
- std::enable_if_t<std::is_integral_v<T>>* = nullptr>
- constexpr auto get_bits(const T& t) noexcept
- {
- if constexpr (std::is_same_v<T,bool>)
- return static_cast<unsigned>(t);
- else
- return static_cast<std::make_unsigned_t<T>>(t);
- }
- template <typename T,
- std::enable_if_t<std::is_enum_v<T>>* = nullptr>
- constexpr auto get_bits(const T& t) noexcept
- { return get_bits(static_cast<std::underlying_type_t<T>>(t)); }
- template <typename It>
- struct bit_iterator
- {
- It iterator;
- std::size_t bit_index;
- };
- template <typename I> bit_iterator(I,std::size_t) -> bit_iterator<I>;
- // TODO: It end
- template <typename T, typename It>
- bit_iterator<It> read_bits(bit_iterator<It> it, T& to)
- {
- auto count = bit_count(to);
- auto type_offset = bit_offset(to);
- auto bits = decltype(get_bits(to)){};
- constexpr auto type_width = std::numeric_limits<decltype(bits)>::digits;
- constexpr auto read_width = std::numeric_limits<std::underlying_type_t<typename std::iterator_traits<support::remove_cvref_t<It>>::value_type>>::digits;
- if constexpr (type_width >= read_width)
- {
- constexpr auto type_shift = type_width - read_width;
- auto value = static_cast<decltype(bits)>(*it.iterator);
- std::size_t i = 0;
- while(i != count)
- {
- bits |= value
- << (type_shift + it.bit_index)
- >> (i + type_offset)
- ;
- using std::min;
- auto read = min(count - i, read_width - it.bit_index);
- i += read;
- it.bit_index += read;
- if(it.bit_index == read_width)
- {
- ++it.iterator;
- value = static_cast<decltype(bits)>(*it.iterator);
- it.bit_index = 0;
- }
- }
- auto tail = type_width - count - type_offset;
- bits = bits >> tail << tail;
- }
- else
- {
- // TODO:
- static_assert(type_width < read_width, "not implemented");
- }
- if constexpr (std::is_enum_v<T>)
- to = static_cast<T>(bits);
- else
- to = bits;
- return it;
- }
- // TODO: It end
- template <typename T, typename It>
- bit_iterator<It> read_bits(It it, T& to)
- {
- return read_bits(bit_iterator{it,0}, to);
- }
- template <typename T = unsigned, std::enable_if_t<std::is_unsigned_v<T>>* = nullptr>
- struct bits
- {
- T value{};
- std::size_t count{};
- using value_type = T;
- static constexpr std::size_t capacity = std::numeric_limits<value_type>::digits;
- constexpr bool full() const noexcept { return count == capacity; }
- constexpr bool empty() const noexcept { return count == 0; }
- constexpr void insert(bool bit) noexcept
- {
- assert(not full());
- ++count;
- value >>= 1;
- value |= value_type{bit} << (capacity - 1);
- }
- constexpr bits& operator=(const T& x) noexcept
- {
- // TODO: assert x has no junk outside of count
- value = x;
- return *this;
- }
- constexpr bool operator==(const bits& other) const noexcept
- { return value == other.value && count == other.count; }
- constexpr bool operator!=(const bits& other) const noexcept
- { return not ((*this) == other); }
- };
- template <typename T>
- constexpr auto get_bits(const bits<T>& b) noexcept
- { return b.value; }
- template <typename T>
- constexpr auto bit_count(const bits<T>& b) noexcept
- { return b.count; }
- template <typename T>
- constexpr std::size_t bit_offset(const bits<T>&) noexcept
- { return 0; }
- template <typename T>
- std::string to_string(const bits<T>& b) noexcept
- {
- std::string str{};
- auto count = bit_count(b);
- auto bits = get_bits(b);
- constexpr decltype(bits) first_bit = decltype(bits){1} << (std::numeric_limits<decltype(bits)>::digits - 1);
- while(count --> 0)
- {
- str += (bits & first_bit) ? '1' : '0';
- bits <<= 1;
- }
- return str;
- }
- } // namespace simple::compress
- #endif /* end of include guard */
|