diff options
Diffstat (limited to 'src/lib/util/coretmpl.h')
-rw-r--r-- | src/lib/util/coretmpl.h | 673 |
1 files changed, 172 insertions, 501 deletions
diff --git a/src/lib/util/coretmpl.h b/src/lib/util/coretmpl.h index 6c8ac39b45c..87f8cfbf09e 100644 --- a/src/lib/util/coretmpl.h +++ b/src/lib/util/coretmpl.h @@ -13,39 +13,22 @@ #pragma once #include "osdcomm.h" -#include "osdcore.h" -#include "corealloc.h" +#include "vecstream.h" #include <array> -#include <cassert> #include <cstddef> -#include <functional> -#include <initializer_list> #include <iterator> -#include <list> -#include <map> -#include <memory> -#include <set> +#include <numeric> #include <stdexcept> -#include <tuple> +#include <string_view> #include <type_traits> #include <utility> -#include <vector> - -// Generate a N-bit mask at compile time. N better be constant. -// Works even for signed types - -template<typename T> constexpr T make_bitmask(unsigned int N) -{ - return T((N < (8 * sizeof(T)) ? (std::make_unsigned_t<T>(1) << N) : std::make_unsigned_t<T>(0)) - 1); -} - // ======================> simple_list // a simple_list is a singly-linked list whose 'next' pointer is owned // by the object -template<class _ElementType> +template<class ElementType> class simple_list final { public: @@ -53,36 +36,31 @@ public: { public: typedef int difference_type; - typedef _ElementType value_type; - typedef _ElementType *pointer; - typedef _ElementType &reference; + typedef ElementType value_type; + typedef ElementType *pointer; + typedef ElementType &reference; typedef std::forward_iterator_tag iterator_category; // construction/destruction auto_iterator() noexcept : m_current(nullptr) { } - auto_iterator(_ElementType *ptr) noexcept : m_current(ptr) { } + auto_iterator(ElementType *ptr) noexcept : m_current(ptr) { } // required operator overloads bool operator==(const auto_iterator &iter) const noexcept { return m_current == iter.m_current; } bool operator!=(const auto_iterator &iter) const noexcept { return m_current != iter.m_current; } - _ElementType &operator*() const noexcept { return *m_current; } - _ElementType *operator->() const noexcept { return m_current; } - // note that _ElementType::next() must not return a const ptr + ElementType &operator*() const noexcept { return *m_current; } + ElementType *operator->() const noexcept { return m_current; } + // note that ElementType::next() must not return a const ptr auto_iterator &operator++() noexcept { m_current = m_current->next(); return *this; } auto_iterator operator++(int) noexcept { auto_iterator result(*this); m_current = m_current->next(); return result; } private: // private state - _ElementType *m_current; + ElementType *m_current; }; // construction/destruction - simple_list() noexcept - : m_head(nullptr) - , m_tail(nullptr) - , m_count(0) - { - } + simple_list() noexcept { } ~simple_list() noexcept { reset(); } // we don't support deep copying @@ -90,18 +68,19 @@ public: simple_list &operator=(const simple_list &) = delete; // but we do support cheap swap/move - simple_list(simple_list &&list) : simple_list() { operator=(std::move(list)); } + simple_list(simple_list &&list) noexcept { operator=(std::move(list)); } simple_list &operator=(simple_list &&list) { using std::swap; swap(m_head, list.m_head); swap(m_tail, list.m_tail); swap(m_count, list.m_count); + return *this; } // simple getters - _ElementType *first() const noexcept { return m_head; } - _ElementType *last() const noexcept { return m_tail; } + ElementType *first() const noexcept { return m_head; } + ElementType *last() const noexcept { return m_tail; } int count() const noexcept { return m_count; } bool empty() const noexcept { return m_count == 0; } @@ -117,7 +96,7 @@ public: } // add the given object to the head of the list - _ElementType &prepend(_ElementType &object) noexcept + ElementType &prepend(ElementType &object) noexcept { object.m_next = m_head; m_head = &object; @@ -128,13 +107,13 @@ public: } // add the given list to the head of the list - void prepend_list(simple_list<_ElementType> &list) noexcept + void prepend_list(simple_list<ElementType> &list) noexcept { int count = list.count(); if (count == 0) return; - _ElementType *tail = list.last(); - _ElementType *head = list.detach_all(); + ElementType *tail = list.last(); + ElementType *head = list.detach_all(); tail->m_next = m_head; m_head = head; if (m_tail == nullptr) @@ -143,7 +122,7 @@ public: } // add the given object to the tail of the list - _ElementType &append(_ElementType &object) noexcept + ElementType &append(ElementType &object) noexcept { object.m_next = nullptr; if (m_tail != nullptr) @@ -155,13 +134,13 @@ public: } // add the given list to the tail of the list - void append_list(simple_list<_ElementType> &list) noexcept + void append_list(simple_list<ElementType> &list) noexcept { int count = list.count(); if (count == 0) return; - _ElementType *tail = list.last(); - _ElementType *head = list.detach_all(); + ElementType *tail = list.last(); + ElementType *head = list.detach_all(); if (m_tail != nullptr) m_tail->m_next = head; else @@ -171,7 +150,7 @@ public: } // insert the given object after a particular object (nullptr means prepend) - _ElementType &insert_after(_ElementType &object, _ElementType *insert_after) noexcept + ElementType &insert_after(ElementType &object, ElementType *insert_after) noexcept { if (insert_after == nullptr) return prepend(object); @@ -184,11 +163,11 @@ public: } // insert the given object before a particular object (nullptr means append) - _ElementType &insert_before(_ElementType &object, _ElementType *insert_before) noexcept + ElementType &insert_before(ElementType &object, ElementType *insert_before) noexcept { if (insert_before == nullptr) return append(object); - for (_ElementType **curptr = &m_head; *curptr != nullptr; curptr = &(*curptr)->m_next) + for (ElementType **curptr = &m_head; *curptr != nullptr; curptr = &(*curptr)->m_next) if (*curptr == insert_before) { object.m_next = insert_before; @@ -202,10 +181,10 @@ public: } // replace an item in the list at the same location, and remove it - _ElementType &replace_and_remove(_ElementType &object, _ElementType &toreplace) noexcept + ElementType &replace_and_remove(ElementType &object, ElementType &toreplace) noexcept { - _ElementType *prev = nullptr; - for (_ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next) + ElementType *prev = nullptr; + for (ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next) if (cur == &toreplace) { if (prev != nullptr) @@ -215,16 +194,16 @@ public: if (m_tail == &toreplace) m_tail = &object; object.m_next = toreplace.m_next; - global_free(&toreplace); + delete &toreplace; return object; } return append(object); } // detach the head item from the list, but don't free its memory - _ElementType *detach_head() noexcept + ElementType *detach_head() noexcept { - _ElementType *result = m_head; + ElementType *result = m_head; if (result != nullptr) { m_head = result->m_next; @@ -236,10 +215,10 @@ public: } // detach the given item from the list, but don't free its memory - _ElementType &detach(_ElementType &object) noexcept + ElementType &detach(ElementType &object) noexcept { - _ElementType *prev = nullptr; - for (_ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next) + ElementType *prev = nullptr; + for (ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next) if (cur == &object) { if (prev != nullptr) @@ -255,34 +234,34 @@ public: } // detach the entire list, returning the head, but don't free memory - _ElementType *detach_all() noexcept + ElementType *detach_all() noexcept { - _ElementType *result = m_head; + ElementType *result = m_head; m_head = m_tail = nullptr; m_count = 0; return result; } // remove the given object and free its memory - void remove(_ElementType &object) noexcept + void remove(ElementType &object) noexcept { - global_free(&detach(object)); + delete &detach(object); } // find an object by index in the list - _ElementType *find(int index) const noexcept + ElementType *find(int index) const noexcept { - for (_ElementType *cur = m_head; cur != nullptr; cur = cur->m_next) + for (ElementType *cur = m_head; cur != nullptr; cur = cur->m_next) if (index-- == 0) return cur; return nullptr; } // return the index of the given object in the list - int indexof(const _ElementType &object) const noexcept + int indexof(const ElementType &object) const noexcept { int index = 0; - for (_ElementType *cur = m_head; cur != nullptr; cur = cur->m_next) + for (ElementType *cur = m_head; cur != nullptr; cur = cur->m_next) { if (cur == &object) return index; @@ -293,49 +272,16 @@ public: private: // internal state - _ElementType * m_head; // head of the singly-linked list - _ElementType * m_tail; // tail of the singly-linked list - int m_count; // number of objects in the list -}; - - -// ======================> simple_list_wrapper - -// a simple_list_wrapper wraps an existing object with a next pointer so it -// can live in a simple_list without requiring the object to have a next -// pointer -template<class _ObjectType> -class simple_list_wrapper -{ -public: - template<class U> friend class simple_list; - - // construction/destruction - simple_list_wrapper(_ObjectType *object) - : m_next(nullptr), - m_object(object) { } - - // operators - operator _ObjectType *() { return m_object; } - operator _ObjectType *() const { return m_object; } - _ObjectType *operator *() { return m_object; } - _ObjectType *operator *() const { return m_object; } - - // getters - simple_list_wrapper *next() const { return m_next; } - _ObjectType *object() const { return m_object; } - -private: - // internal state - simple_list_wrapper * m_next; - _ObjectType * m_object; + ElementType * m_head = nullptr; // head of the singly-linked list + ElementType * m_tail = nullptr; // tail of the singly-linked list + int m_count = 0; // number of objects in the list }; // ======================> fixed_allocator // a fixed_allocator is a simple class that maintains a free pool of objects -template<class _ItemType> +template<class ItemType> class fixed_allocator { // we don't support deep copying @@ -347,24 +293,24 @@ public: fixed_allocator() { } // allocate a new item, either by recycling an old one, or by allocating a new one - _ItemType *alloc() + ItemType *alloc() { - _ItemType *result = m_freelist.detach_head(); + ItemType *result = m_freelist.detach_head(); if (result == nullptr) - result = global_alloc(_ItemType); + result = new ItemType; return result; } // reclaim an item by adding it to the free list - void reclaim(_ItemType *item) { if (item != nullptr) m_freelist.append(*item); } - void reclaim(_ItemType &item) { m_freelist.append(item); } + void reclaim(ItemType *item) { if (item != nullptr) m_freelist.append(*item); } + void reclaim(ItemType &item) { m_freelist.append(item); } // reclaim all items from a list - void reclaim_all(simple_list<_ItemType> &_list) { m_freelist.append_list(_list); } + void reclaim_all(simple_list<ItemType> &_list) { m_freelist.append_list(_list); } private: // internal state - simple_list<_ItemType> m_freelist; // list of free objects + simple_list<ItemType> m_freelist; // list of free objects }; @@ -450,383 +396,6 @@ private: }; -// LRU cache that behaves like std::map with differences: -// * drops least-recently used items if necessary on insert to prevent size from exceeding max_size -// * operator[], at, insert, emplace and find freshen existing entries -// * iterates from least- to most-recently used rather than in order by key -// * iterators to dropped items are invalidated -// * not all map interfaces implemented -// * copyable and swappable but not movable -// * swap may invalidate past-the-end iterator, other iterators refer to new container -template <typename Key, typename T, typename Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key const, T> > > -class lru_cache_map -{ -private: - class iterator_compare; - typedef std::list<std::pair<Key const, T>, Allocator> value_list; - typedef typename std::allocator_traits<Allocator>::template rebind_alloc<typename value_list::iterator> iterator_allocator_type; - typedef std::set<typename value_list::iterator, iterator_compare, iterator_allocator_type> iterator_set; - - class iterator_compare - { - public: - typedef std::true_type is_transparent; - iterator_compare(Compare const &comp) : m_comp(comp) { } - iterator_compare(iterator_compare const &that) = default; - iterator_compare(iterator_compare &&that) = default; - Compare key_comp() const { return m_comp; } - iterator_compare &operator=(iterator_compare const &that) = default; - iterator_compare &operator=(iterator_compare &&that) = default; - bool operator()(typename value_list::iterator const &lhs, typename value_list::iterator const &rhs) const { return m_comp(lhs->first, rhs->first); } - template <typename K> bool operator()(typename value_list::iterator const &lhs, K const &rhs) const { return m_comp(lhs->first, rhs); } - template <typename K> bool operator()(K const &lhs, typename value_list::iterator const &rhs) const { return m_comp(lhs, rhs->first); } - private: - Compare m_comp; - }; - -public: - typedef Key key_type; - typedef T mapped_type; - typedef std::pair<Key const, T> value_type; - typedef typename value_list::size_type size_type; - typedef typename value_list::difference_type difference_type; - typedef Compare key_compare; - typedef Allocator allocator_type; - typedef value_type &reference; - typedef value_type const &const_reference; - typedef typename std::allocator_traits<Allocator>::pointer pointer; - typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer; - typedef typename value_list::iterator iterator; - typedef typename value_list::const_iterator const_iterator; - typedef typename value_list::reverse_iterator reverse_iterator; - typedef typename value_list::const_reverse_iterator const_reverse_iterator; - - explicit lru_cache_map(size_type max_size) - : lru_cache_map(max_size, key_compare()) - { - } - lru_cache_map(size_type max_size, key_compare const &comp, allocator_type const &alloc = allocator_type()) - : m_max_size(max_size) - , m_size(0U) - , m_elements(alloc) - , m_mapping(iterator_compare(comp), iterator_allocator_type(alloc)) - { - assert(0U < m_max_size); - } - lru_cache_map(lru_cache_map const &that) - : m_max_size(that.m_max_size) - , m_size(that.m_size) - , m_elements(that.m_elements) - , m_mapping(that.m_mapping.key_comp(), that.m_mapping.get_allocator()) - { - for (iterator it = m_elements.begin(); it != m_elements.end(); ++it) - m_mapping.insert(it); - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - } - - allocator_type get_allocator() const { return m_elements.get_allocator(); } - - iterator begin() { return m_elements.begin(); } - const_iterator begin() const { return m_elements.cbegin(); } - const_iterator cbegin() const { return m_elements.cbegin(); } - iterator end() { return m_elements.end(); } - const_iterator end() const { return m_elements.cend(); } - const_iterator cend() const { return m_elements.cend(); } - reverse_iterator rbegin() { return m_elements.rbegin(); } - const_reverse_iterator rbegin() const { return m_elements.crbegin(); } - const_reverse_iterator crbegin() const { return m_elements.crbegin(); } - reverse_iterator rend() { return m_elements.end(); } - const_reverse_iterator rend() const { return m_elements.crend(); } - const_reverse_iterator crend() const { return m_elements.crend(); } - - bool empty() const { return !m_size; } - size_type size() const { return m_size; } - size_type max_size() const { return m_max_size; } - - mapped_type &operator[](key_type const &key) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(key)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(key, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>())); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return inserted->second; - } - mapped_type &operator[](key_type &&key) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(key)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(key, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>())); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return inserted->second; - } - mapped_type &at(key_type const &key) - { - typename iterator_set::iterator existing(m_mapping.find(key)); - if (m_mapping.end() != existing) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - else - { - throw std::out_of_range("lru_cache_map::at"); - } - } - mapped_type const &at(key_type const &key) const - { - typename iterator_set::iterator existing(m_mapping.find(key)); - if (m_mapping.end() != existing) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - else - { - throw std::out_of_range("lru_cache_map::at"); - } - } - - void clear() - { - m_size = 0U; - m_elements.clear(); - m_mapping.clear(); - } - std::pair<iterator, bool> insert(value_type const &value) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(value.first)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(value.first, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return std::pair<iterator, bool>(*existing, false); - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), value)); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return std::pair<iterator, bool>(inserted, true); - } - std::pair<iterator, bool> insert(value_type &&value) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(value.first)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(value.first, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return std::pair<iterator, bool>(*existing, false); - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::move(value))); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return std::pair<iterator, bool>(inserted, true); - } - template <typename P> - std::enable_if_t<std::is_constructible<value_type, P>::value, std::pair<iterator, bool> > insert(P &&value) - { - return emplace(std::forward<P>(value)); - } - template <typename InputIt> - void insert(InputIt first, InputIt last) - { - while (first != last) - { - insert(*first); - ++first; - } - } - void insert(std::initializer_list<value_type> ilist) - { - for (value_type const &value : ilist) - insert(value); - } - template <typename... Params> - std::pair<iterator, bool> emplace(Params &&... args) - { - // TODO: is there a more efficient way than depending on value_type being efficiently movable? - return insert(value_type(std::forward<Params>(args)...)); - } - iterator erase(const_iterator pos) - { - m_mapping.erase(m_elements.erase(pos, pos)); - iterator const result(m_elements.erase(pos)); - --m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return result; - } - iterator erase(const_iterator first, const_iterator last) - { - iterator pos(m_elements.erase(first, first)); - while (pos != last) - { - m_mapping.erase(pos); - pos = m_elements.erase(pos); - --m_size; - } - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return pos; - } - size_type erase(key_type const &key) - { - typename iterator_set::iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return 0U; - } - else - { - m_elements.erase(*found); - m_mapping.erase(found); - --m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return 1U; - } - } - void swap(lru_cache_map &that) - { - using std::swap; - swap(m_max_size, that.m_max_size); - swap(m_size, that.m_size); - swap(m_elements, that.m_elements); - swap(m_mapping, that.m_mapping); - } - - size_type count(key_type const &key) const - { - // TODO: perhaps this should freshen an element - return m_mapping.count(key); - } - template <typename K> - size_type count(K const &x) const - { - // FIXME: should only enable this overload if Compare::is_transparent - // TODO: perhaps this should freshen an element - return m_mapping.count(x); - } - iterator find(key_type const &key) - { - typename iterator_set::const_iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - iterator find(key_type const &key) const - { - typename iterator_set::const_iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - template <typename K> - iterator find(K const &x) - { - // FIXME: should only enable this overload if Compare::is_transparent - typename iterator_set::const_iterator const found(m_mapping.find(x)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - template <typename K> - iterator find(K const &x) const - { - // FIXME: should only enable this overload if Compare::is_transparent - typename iterator_set::const_iterator const found(m_mapping.find(x)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - - key_compare key_comp() const - { - return m_mapping.key_comp().key_comp(); - } - - lru_cache_map &operator=(lru_cache_map const &that) - { - m_max_size = that.m_max_size; - m_size = that.m_size; - m_elements = that.m_elements; - m_mapping.clear(); - for (iterator it = m_elements.begin(); it != m_elements.end(); ++it) - m_mapping.insert(it); - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - } - -private: - void make_space(typename iterator_set::iterator &existing) - { - while (m_max_size <= m_size) - { - if ((m_mapping.end() != existing) && (m_elements.begin() == *existing)) - existing = m_mapping.erase(existing); - else - m_mapping.erase(m_elements.begin()); - m_elements.erase(m_elements.begin()); - --m_size; - } - } - - size_type m_max_size; - size_type m_size; - mutable value_list m_elements; - iterator_set m_mapping; -}; - -template <typename Key, typename T, typename Compare, class Allocator> -void swap(lru_cache_map<Key, T, Compare, Allocator> &lhs, lru_cache_map<Key, T, Compare, Allocator> &rhs) -{ - lhs.swap(rhs); -} - - template <typename T, std::size_t N, bool WriteWrap = false, bool ReadWrap = WriteWrap> class fifo : protected std::array<T, N> { @@ -957,6 +526,25 @@ private: }; +// extract a string_view from an ovectorstream buffer +template <typename CharT, typename Traits, typename Allocator> +std::basic_string_view<CharT, Traits> buf_to_string_view(basic_ovectorstream<CharT, Traits, Allocator> &stream) +{ + // this works on the assumption that the value tellp returns is the same both before and after vec is called + return std::basic_string_view<CharT, Traits>(&stream.vec()[0], stream.tellp()); +} + + +// For declaring an array of the same dimensions as another array (including multi-dimensional arrays) +template <typename T, typename U> struct equivalent_array_or_type { typedef T type; }; +template <typename T, typename U, std::size_t N> struct equivalent_array_or_type<T, U[N]> { typedef typename equivalent_array_or_type<T, U>::type type[N]; }; +template <typename T, typename U> using equivalent_array_or_type_t = typename equivalent_array_or_type<T, U>::type; +template <typename T, typename U> struct equivalent_array { }; +template <typename T, typename U, std::size_t N> struct equivalent_array<T, U[N]> { typedef equivalent_array_or_type_t<T, U> type[N]; }; +template <typename T, typename U> using equivalent_array_t = typename equivalent_array<T, U>::type; +#define EQUIVALENT_ARRAY(a, T) util::equivalent_array_t<T, std::remove_reference_t<decltype(a)> > + + template <typename E> using enable_enum_t = typename std::enable_if_t<std::is_enum<E>::value, typename std::underlying_type_t<E> >; @@ -975,24 +563,114 @@ constexpr typename std::enable_if_t<std::is_enum<E>::value && std::is_integral<T } -// useful functions to deal with bit shuffling +/// \defgroup bitutils Useful functions for bit shuffling +/// \{ + +/// \brief Generate a right-aligned bit mask +/// +/// Generates a right aligned mask of the specified width. Works with +/// signed and unsigned integer types. +/// \tparam T Desired output type. +/// \tparam U Type of the input (generally resolved by the compiler). +/// \param [in] n Width of the mask to generate in bits. +/// \return Right-aligned mask of the specified width. + +template <typename T, typename U> constexpr T make_bitmask(U n) +{ + return T((n < (8 * sizeof(T)) ? (std::make_unsigned_t<T>(1) << n) : std::make_unsigned_t<T>(0)) - 1); +} + + +/// \brief Extract a single bit from an integer +/// +/// Extracts a single bit from an integer into the least significant bit +/// position. +/// +/// \param [in] x The integer to extract the bit from. +/// \param [in] n The bit to extract, where zero is the least +/// significant bit of the input. +/// \return Zero if the specified bit is unset, or one if it is set. +/// \sa bitswap template <typename T, typename U> constexpr T BIT(T x, U n) noexcept { return (x >> n) & T(1); } -template <typename T, typename U> constexpr T bitswap(T val, U b) noexcept { return BIT(val, b) << 0U; } +/// \brief Extract a bit field from an integer +/// +/// Extracts and right-aligns a bit field from an integer. +/// +/// \param [in] x The integer to extract the bit field from. +/// \param [in] n The least significant bit position of the field to +/// extract, where zero is the least significant bit of the input. +/// \param [in] w The width of the field to extract in bits. +/// \return The field [n..(n+w-1)] from the input. +/// \sa bitswap +template <typename T, typename U, typename V> constexpr T BIT(T x, U n, V w) +{ + return (x >> n) & make_bitmask<T>(w); +} + + +/// \brief Extract bits in arbitrary order +/// +/// Extracts bits from an integer. Specify the bits in the order they +/// should be arranged in the output, from most significant to least +/// significant. The extracted bits will be packed into a right-aligned +/// field in the output. +/// +/// \param [in] val The integer to extract bits from. +/// \param [in] b The first bit to extract from the input +/// extract, where zero is the least significant bit of the input. +/// This bit will appear in the most significant position of the +/// right-aligned output field. +/// \param [in] c The remaining bits to extract, where zero is the +/// least significant bit of the input. +/// \return The extracted bits packed into a right-aligned field. template <typename T, typename U, typename... V> constexpr T bitswap(T val, U b, V... c) noexcept { - return (BIT(val, b) << sizeof...(c)) | bitswap(val, c...); + if constexpr (sizeof...(c) > 0U) + return (BIT(val, b) << sizeof...(c)) | bitswap(val, c...); + else + return BIT(val, b); } -// explicit version that checks number of bit position arguments -template <unsigned B, typename T, typename... U> T bitswap(T val, U... b) noexcept + +/// \brief Extract bits in arbitrary order with explicit count +/// +/// Extracts bits from an integer. Specify the bits in the order they +/// should be arranged in the output, from most significant to least +/// significant. The extracted bits will be packed into a right-aligned +/// field in the output. The number of bits to extract must be supplied +/// as a template argument. +/// +/// A compile error will be generated if the number of bit positions +/// supplied does not match the specified number of bits to extract, or +/// if the output type is too small to hold the extracted bits. This +/// guards against some simple errors. +/// +/// \tparam B The number of bits to extract. Must match the number of +/// bit positions supplied. +/// \param [in] val The integer to extract bits from. +/// \param [in] b Bits to extract, where zero is the least significant +/// bit of the input. Specify bits in the order they should appear in +/// the output field, from most significant to least significant. +/// \return The extracted bits packed into a right-aligned field. +template <unsigned B, typename T, typename... U> constexpr T bitswap(T val, U... b) noexcept { static_assert(sizeof...(b) == B, "wrong number of bits"); static_assert((sizeof(std::remove_reference_t<T>) * 8) >= B, "return type too small for result"); return bitswap(val, b...); } +/// \} + + +// utility function for sign-extending values of arbitrary width +template <typename T, typename U> +constexpr std::make_signed_t<T> sext(T value, U width) noexcept +{ + return std::make_signed_t<T>(value << (8 * sizeof(value) - width)) >> (8 * sizeof(value) - width); +} + // constexpr absolute value of an integer template <typename T> @@ -1002,18 +680,11 @@ constexpr std::enable_if_t<std::is_signed<T>::value, T> iabs(T v) noexcept } -// returns greatest common divisor of a and b using the Euclidean algorithm -template <typename M, typename N> -constexpr std::common_type_t<M, N> euclid_gcd(M a, N b) -{ - return b ? euclid_gcd(b, a % b) : a; -} - // reduce a fraction template <typename M, typename N> inline void reduce_fraction(M &num, N &den) { - auto const div(euclid_gcd(num, den)); + auto const div(std::gcd(num, den)); if (div) { num /= div; @@ -1021,6 +692,6 @@ inline void reduce_fraction(M &num, N &den) } } -}; // namespace util +} // namespace util #endif // MAME_UTIL_CORETMPL_H |