diff options
Diffstat (limited to 'common')
| -rw-r--r-- | common/bits.cc | 14 | ||||
| -rw-r--r-- | common/bits.h | 13 | ||||
| -rw-r--r-- | common/dynamic_bitarray.h | 79 |
3 files changed, 95 insertions, 11 deletions
diff --git a/common/bits.cc b/common/bits.cc index 1fe65544..36c7539a 100644 --- a/common/bits.cc +++ b/common/bits.cc @@ -24,7 +24,8 @@ namespace nextpnr { -int Bits::generic_popcount(unsigned int v) { +int Bits::generic_popcount(unsigned int v) +{ unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set @@ -33,13 +34,14 @@ int Bits::generic_popcount(unsigned int v) { return c; } -int Bits::generic_ctz(unsigned int x) { - if(x == 0) { +int Bits::generic_ctz(unsigned int x) +{ + if (x == 0) { throw std::runtime_error("Cannot call ctz with arg = 0"); } - for(size_t i = 0; i < std::numeric_limits<unsigned int>::digits; ++i) { - if((x & (1 << i)) != 0) { + for (size_t i = 0; i < std::numeric_limits<unsigned int>::digits; ++i) { + if ((x & (1 << i)) != 0) { return i; } } @@ -48,4 +50,4 @@ int Bits::generic_ctz(unsigned int x) { throw std::runtime_error("Unreachable!"); } -}; +}; // namespace nextpnr diff --git a/common/bits.h b/common/bits.h index 1abf6735..d1598a8e 100644 --- a/common/bits.h +++ b/common/bits.h @@ -34,18 +34,20 @@ #if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) #include <intrin.h> -#pragma intrinsic(_BitScanForward,_BitScanReverse,__popcnt) +#pragma intrinsic(_BitScanForward, _BitScanReverse, __popcnt) #endif // Uses plain nextpnr namespace to avoid header inclusion nightmare that is // "nextpnr.h". namespace nextpnr { -struct Bits { +struct Bits +{ static int generic_popcount(unsigned int x); static int generic_ctz(unsigned int x); - static int popcount(unsigned int x) { + static int popcount(unsigned int x) + { #if defined(__GNUC__) || defined(__clang__) return __builtin_popcount(x); #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) @@ -55,7 +57,8 @@ struct Bits { #endif } - static int ctz(unsigned int x) { + static int ctz(unsigned int x) + { #if defined(__GNUC__) || defined(__clang__) return __builtin_ctz(x); #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) @@ -68,6 +71,6 @@ struct Bits { } }; -}; +}; // namespace nextpnr #endif /* BITS_H */ diff --git a/common/dynamic_bitarray.h b/common/dynamic_bitarray.h new file mode 100644 index 00000000..10a85fbc --- /dev/null +++ b/common/dynamic_bitarray.h @@ -0,0 +1,79 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include <cstdint> +#include <limits> +#include <vector> + +// This class implements a simple dynamic bitarray, backed by some resizable +// random access storage. The default is to use a std::vector<uint8_t>. + +#ifndef DYNAMIC_BITARRAY_H +#define DYNAMIC_BITARRAY_H + +namespace nextpnr { + +template <typename Storage = std::vector<uint8_t>> class DynamicBitarray +{ + public: + static_assert(!std::numeric_limits<typename Storage::value_type>::is_signed, "Storage must be unsigned!"); + + void fill(bool value) + { + std::fill(storage.begin(), storage.end(), value ? std::numeric_limits<typename Storage::value_type>::max() : 0); + } + + constexpr size_t bits_per_value() const { return std::numeric_limits<typename Storage::value_type>::digits; } + + bool get(size_t bit) const + { + size_t element_index = bit / bits_per_value(); + size_t bit_offset = bit % bits_per_value(); + + auto element = storage.at(element_index); + return (element & (1 << bit_offset)) != 0; + } + + void set(size_t bit, bool value) + { + size_t element_index = bit / bits_per_value(); + size_t bit_offset = bit % bits_per_value(); + + if (value) { + storage.at(element_index) |= (1 << bit_offset); + } else { + storage.at(element_index) &= ~(1 << bit_offset); + } + } + + void resize(size_t number_bits) + { + size_t required_storage = (number_bits + bits_per_value() - 1) / bits_per_value(); + storage.resize(required_storage); + } + + size_t size() const { return storage.size() * bits_per_value(); } + + private: + Storage storage; +}; + +}; // namespace nextpnr + +#endif /* DYNAMIC_BITARRAY_H */ |