blob: a805ce20fc8d84fe3b9917ea1bf324cdf3f4223b [file]
// Copyright 2020 Google LLC
// SPDX-License-Identifier: Apache-2.0
//
// 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.
#ifndef HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_
#define HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_
// Memory allocator with support for alignment and offsets.
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <initializer_list>
#include <memory>
#include <utility>
#include <vector>
#include "hwy/base.h"
#include "hwy/per_target.h"
namespace hwy {
// Minimum alignment of allocated memory for use in HWY_ASSUME_ALIGNED, which
// requires a literal. To prevent false sharing, this should be at least the
// L1 cache line size, usually 64 bytes. However, Intel's L2 prefetchers may
// access pairs of lines, and M1 L2 and POWER8 lines are also 128 bytes.
#define HWY_ALIGNMENT 128
// `align` is in bytes.
template <typename T>
HWY_API constexpr bool IsAligned(T* ptr, size_t align = HWY_ALIGNMENT) {
return reinterpret_cast<uintptr_t>(ptr) % align == 0;
}
// Pointers to functions equivalent to malloc/free with an opaque void* passed
// to them.
using AllocPtr = void* (*)(void* opaque, size_t bytes);
using FreePtr = void (*)(void* opaque, void* memory);
// Returns null or a pointer to at least `payload_size` (which can be zero)
// bytes of newly allocated memory, aligned to the larger of HWY_ALIGNMENT and
// the vector size. Calls `alloc` with the passed `opaque` pointer to obtain
// memory or malloc() if it is null.
HWY_DLLEXPORT void* AllocateAlignedBytes(size_t payload_size,
AllocPtr alloc_ptr = nullptr,
void* opaque_ptr = nullptr);
// Frees all memory. No effect if `aligned_pointer` == nullptr, otherwise it
// must have been returned from a previous call to `AllocateAlignedBytes`.
// Calls `free_ptr` with the passed `opaque_ptr` pointer to free the memory; if
// `free_ptr` function is null, uses the default free().
HWY_DLLEXPORT void FreeAlignedBytes(const void* aligned_pointer,
FreePtr free_ptr, void* opaque_ptr);
// Class that deletes the aligned pointer passed to operator() calling the
// destructor before freeing the pointer. This is equivalent to the
// std::default_delete but for aligned objects. For a similar deleter equivalent
// to free() for aligned memory see AlignedFreer().
class AlignedDeleter {
public:
AlignedDeleter() : free_(nullptr), opaque_ptr_(nullptr) {}
AlignedDeleter(FreePtr free_ptr, void* opaque_ptr)
: free_(free_ptr), opaque_ptr_(opaque_ptr) {}
template <typename T>
void operator()(T* aligned_pointer) const {
return DeleteAlignedArray(aligned_pointer, free_, opaque_ptr_,
TypedArrayDeleter<T>);
}
private:
template <typename T>
static void TypedArrayDeleter(void* ptr, size_t size_in_bytes) {
size_t elems = size_in_bytes / sizeof(T);
for (size_t i = 0; i < elems; i++) {
// Explicitly call the destructor on each element.
(static_cast<T*>(ptr) + i)->~T();
}
}
// Function prototype that calls the destructor for each element in a typed
// array. TypeArrayDeleter<T> would match this prototype.
using ArrayDeleter = void (*)(void* t_ptr, size_t t_size);
HWY_DLLEXPORT static void DeleteAlignedArray(void* aligned_pointer,
FreePtr free_ptr,
void* opaque_ptr,
ArrayDeleter deleter);
FreePtr free_;
void* opaque_ptr_;
};
// Unique pointer to T with custom aligned deleter. This can be a single
// element U or an array of element if T is a U[]. The custom aligned deleter
// will call the destructor on U or each element of a U[] in the array case.
template <typename T>
using AlignedUniquePtr = std::unique_ptr<T, AlignedDeleter>;
// Aligned memory equivalent of make_unique<T> using the custom allocators
// alloc/free with the passed `opaque` pointer. This function calls the
// constructor with the passed Args... and calls the destructor of the object
// when the AlignedUniquePtr is destroyed.
template <typename T, typename... Args>
AlignedUniquePtr<T> MakeUniqueAlignedWithAlloc(AllocPtr alloc, FreePtr free,
void* opaque, Args&&... args) {
T* ptr = static_cast<T*>(AllocateAlignedBytes(sizeof(T), alloc, opaque));
if (HWY_UNLIKELY(ptr == nullptr)) {
return AlignedUniquePtr<T>(nullptr, AlignedDeleter(free, opaque));
}
#ifdef HWY_EXCEPTIONS_ENABLED
try {
return AlignedUniquePtr<T>(new (ptr) T(std::forward<Args>(args)...),
AlignedDeleter(free, opaque));
} catch (...) {
FreeAlignedBytes(ptr, free, opaque);
throw;
}
#else
return AlignedUniquePtr<T>(new (ptr) T(std::forward<Args>(args)...),
AlignedDeleter(free, opaque));
#endif
}
// Similar to MakeUniqueAlignedWithAlloc but using the default alloc/free
// functions.
template <typename T, typename... Args>
AlignedUniquePtr<T> MakeUniqueAligned(Args&&... args) {
T* ptr = static_cast<T*>(AllocateAlignedBytes(sizeof(T)));
if (HWY_UNLIKELY(ptr == nullptr)) {
return AlignedUniquePtr<T>(nullptr, AlignedDeleter());
}
#ifdef HWY_EXCEPTIONS_ENABLED
try {
return AlignedUniquePtr<T>(new (ptr) T(std::forward<Args>(args)...),
AlignedDeleter());
} catch (...) {
FreeAlignedBytes(ptr, nullptr, nullptr);
throw;
}
#else
return AlignedUniquePtr<T>(new (ptr) T(std::forward<Args>(args)...),
AlignedDeleter());
#endif
}
template <class T>
struct AlignedAllocator {
using value_type = T;
AlignedAllocator() = default;
template <class V>
explicit AlignedAllocator(const AlignedAllocator<V>&) noexcept {}
template <class V>
value_type* allocate(V n) {
static_assert(IsInteger<V>(),
"AlignedAllocator only supports integer types");
static_assert(sizeof(V) <= sizeof(std::size_t),
"V n must be smaller or equal size_t to avoid overflow");
const size_t count = static_cast<std::size_t>(n);
if (HWY_LIKELY(count != 0) && sizeof(value_type) > SIZE_MAX / count) {
HWY_ABORT("AlignedAllocator: allocation size overflow "
"(%zu * %zu exceeds size_t)", count, sizeof(value_type));
}
return static_cast<value_type*>(
AllocateAlignedBytes(count * sizeof(value_type)));
}
template <class V>
void deallocate(value_type* p, HWY_MAYBE_UNUSED V n) {
return FreeAlignedBytes(p, nullptr, nullptr);
}
};
template <class T, class V>
constexpr bool operator==(const AlignedAllocator<T>&,
const AlignedAllocator<V>&) noexcept {
return true;
}
template <class T, class V>
constexpr bool operator!=(const AlignedAllocator<T>&,
const AlignedAllocator<V>&) noexcept {
return false;
}
template <class T>
using AlignedVector = std::vector<T, AlignedAllocator<T>>;
// Helpers for array allocators (avoids overflow)
namespace detail {
// Returns x such that 1u << x == n (if n is a power of two).
static constexpr size_t ShiftCount(size_t n) {
return (n <= 1) ? 0 : 1 + ShiftCount(n / 2);
}
template <typename T>
T* AllocateAlignedItems(size_t items, AllocPtr alloc_ptr, void* opaque_ptr) {
constexpr size_t kSize = sizeof(T);
constexpr bool kIsPow2 = (kSize & (kSize - 1)) == 0;
constexpr size_t kBits = ShiftCount(kSize);
static_assert(!kIsPow2 || (1ull << kBits) == kSize, "ShiftCount has a bug");
const size_t bytes = kIsPow2 ? items << kBits : items * kSize;
const size_t check = kIsPow2 ? bytes >> kBits : bytes / kSize;
if (check != items) {
return nullptr; // overflowed
}
return static_cast<T*>(AllocateAlignedBytes(bytes, alloc_ptr, opaque_ptr));
}
} // namespace detail
// Aligned memory equivalent of make_unique<T[]> for array types using the
// custom allocators alloc/free. This function calls the constructor with the
// passed Args... on every created item. The destructor of each element will be
// called when the AlignedUniquePtr is destroyed.
template <typename T, typename... Args>
AlignedUniquePtr<T[]> MakeUniqueAlignedArrayWithAlloc(
size_t items, AllocPtr alloc, FreePtr free, void* opaque, Args&&... args) {
T* ptr = detail::AllocateAlignedItems<T>(items, alloc, opaque);
if (ptr != nullptr) {
for (size_t i = 0; i < items; i++) {
new (ptr + i) T(args...);
}
}
return AlignedUniquePtr<T[]>(ptr, AlignedDeleter(free, opaque));
}
template <typename T, typename... Args>
AlignedUniquePtr<T[]> MakeUniqueAlignedArray(size_t items, Args&&... args) {
return MakeUniqueAlignedArrayWithAlloc<T, Args...>(
items, nullptr, nullptr, nullptr, std::forward<Args>(args)...);
}
// Custom deleter for std::unique_ptr equivalent to using free() as a deleter
// but for aligned memory.
class AlignedFreer {
public:
// Pass address of this to ctor to skip deleting externally-owned memory.
static void DoNothing(void* /*opaque*/, void* /*aligned_pointer*/) {}
AlignedFreer() : free_(nullptr), opaque_ptr_(nullptr) {}
AlignedFreer(FreePtr free_ptr, void* opaque_ptr)
: free_(free_ptr), opaque_ptr_(opaque_ptr) {}
template <typename T>
void operator()(T* aligned_pointer) const {
FreeAlignedBytes(aligned_pointer, free_, opaque_ptr_);
}
private:
FreePtr free_;
void* opaque_ptr_;
};
// Unique pointer to single POD, or (if T is U[]) an array of POD. For non POD
// data use AlignedUniquePtr. Prefer AlignedPtr<T> for new code.
template <typename T>
using AlignedFreeUniquePtr = std::unique_ptr<T, AlignedFreer>;
namespace detail {
// Default deleter for AlignedPtr allocated via AllocateAlignedBytes.
// `free_fn` holds the custom `FreePtr` (or nullptr for default free), while
// the user's `opaque_ptr` is stored in AllocationHeader.
static inline void FreeAlignedMemory(void* free_fn, void* memory) {
FreeAlignedBytes(
memory, reinterpret_cast<FreePtr>(reinterpret_cast<uintptr_t>(free_fn)),
nullptr);
}
} // namespace detail
template <typename T>
class Span;
// Owning smart pointer to a contiguous array of `size()` trivially destructible
// elements of type `T`, with bounds-checked indexing and support for custom
// deleters (e.g. `FreeAlignedMemory` or `munmap`).
template <typename T>
class AlignedPtr {
static_assert(IsTriviallyDestructible<T>(),
"AlignedPtr requires trivially destructible T");
public:
using value_type = T;
using pointer = T*;
constexpr AlignedPtr() noexcept = default;
constexpr AlignedPtr(std::nullptr_t) noexcept {}
// Takes ownership of `[ptr, ptr + size)`. When destroyed, if `ptr != nullptr`
// and `deleter != nullptr`, calls `deleter(opaque, const_cast<...>(ptr))`.
// Passing `deleter = nullptr` wraps externally-owned memory without freeing.
explicit AlignedPtr(T* ptr, size_t size,
FreePtr deleter = &detail::FreeAlignedMemory,
void* opaque = nullptr) noexcept
: ptr_(ptr), size_(ptr ? size : 0), free_(deleter), opaque_(opaque) {}
AlignedPtr(const AlignedPtr&) = delete;
AlignedPtr& operator=(const AlignedPtr&) = delete;
AlignedPtr(AlignedPtr&& other) noexcept
: ptr_(other.ptr_),
size_(other.size_),
free_(other.free_),
opaque_(other.opaque_) {
other.ptr_ = nullptr;
other.size_ = 0;
other.free_ = nullptr;
other.opaque_ = nullptr;
}
AlignedPtr& operator=(AlignedPtr&& other) noexcept {
if (this != &other) {
reset();
ptr_ = other.ptr_;
size_ = other.size_;
free_ = other.free_;
opaque_ = other.opaque_;
other.ptr_ = nullptr;
other.size_ = 0;
other.free_ = nullptr;
other.opaque_ = nullptr;
}
return *this;
}
// Converting move from `AlignedPtr<U>` to `AlignedPtr<const U>`.
template <typename U,
EnableIf<!IsConst<U>() && IsSame<const U, T>()>* = nullptr>
AlignedPtr(AlignedPtr<U>&& other) noexcept
: ptr_(other.ptr_),
size_(other.size_),
free_(other.free_),
opaque_(other.opaque_) {
other.ptr_ = nullptr;
other.size_ = 0;
other.free_ = nullptr;
other.opaque_ = nullptr;
}
template <typename U,
EnableIf<!IsConst<U>() && IsSame<const U, T>()>* = nullptr>
AlignedPtr& operator=(AlignedPtr<U>&& other) noexcept {
reset();
ptr_ = other.ptr_;
size_ = other.size_;
free_ = other.free_;
opaque_ = other.opaque_;
other.ptr_ = nullptr;
other.size_ = 0;
other.free_ = nullptr;
other.opaque_ = nullptr;
return *this;
}
AlignedPtr& operator=(std::nullptr_t) noexcept {
reset();
return *this;
}
~AlignedPtr() { reset(); }
void reset(std::nullptr_t = nullptr) noexcept {
T* ptr = ptr_;
FreePtr deleter = free_;
void* opaque = opaque_;
ptr_ = nullptr;
size_ = 0;
free_ = nullptr;
opaque_ = nullptr;
if (ptr != nullptr && deleter != nullptr) {
void* mutable_ptr = const_cast<RemoveConst<T>*>(ptr);
deleter(opaque, mutable_ptr);
}
}
// Releases ownership and returns the raw pointer, resetting `size()` to 0.
T* release() noexcept {
T* p = ptr_;
ptr_ = nullptr;
size_ = 0;
free_ = nullptr;
opaque_ = nullptr;
return p;
}
void swap(AlignedPtr& other) noexcept {
std::swap(ptr_, other.ptr_);
std::swap(size_, other.size_);
std::swap(free_, other.free_);
std::swap(opaque_, other.opaque_);
}
friend void swap(AlignedPtr& a, AlignedPtr& b) noexcept { a.swap(b); }
T* get() const noexcept { return ptr_; }
T* data() const noexcept { return ptr_; }
size_t size() const noexcept { return size_; }
size_t size_bytes() const noexcept { return size_ * sizeof(T); }
bool empty() const noexcept { return size_ == 0; }
FreePtr free_fn() const noexcept { return free_; }
explicit operator bool() const noexcept { return ptr_ != nullptr; }
// Bounds-checked element access.
T& operator[](size_t i) const {
HWY_DASSERT(i < size_);
return ptr_[i];
}
T* begin() const noexcept { return ptr_; }
T* end() const noexcept { return ptr_ + size_; }
const T* cbegin() const noexcept { return ptr_; }
const T* cend() const noexcept { return ptr_ + size_; }
Span<T> span() const& noexcept;
void span() && = delete;
// Backward-compatible rvalue conversion for callers still using
// `AlignedFreeUniquePtr<T[]>`.
operator AlignedFreeUniquePtr<RemoveConst<T>[]>() && noexcept {
using NonConstT = RemoveConst<T>;
FreePtr freer_fn = nullptr;
if (free_ == &detail::FreeAlignedMemory) {
freer_fn =
reinterpret_cast<FreePtr>(reinterpret_cast<uintptr_t>(opaque_));
} else if (free_ == nullptr || free_ == &AlignedFreer::DoNothing) {
freer_fn = &AlignedFreer::DoNothing;
} else {
HWY_DASSERT(false &&
"AlignedFreeUniquePtr only supports AllocateAligned memory");
}
return AlignedFreeUniquePtr<NonConstT[]>(const_cast<NonConstT*>(release()),
AlignedFreer(freer_fn, nullptr));
}
friend bool operator==(const AlignedPtr& p, std::nullptr_t) noexcept {
return p.ptr_ == nullptr;
}
friend bool operator==(std::nullptr_t, const AlignedPtr& p) noexcept {
return p.ptr_ == nullptr;
}
friend bool operator!=(const AlignedPtr& p, std::nullptr_t) noexcept {
return p.ptr_ != nullptr;
}
friend bool operator!=(std::nullptr_t, const AlignedPtr& p) noexcept {
return p.ptr_ != nullptr;
}
private:
template <typename U>
friend class AlignedPtr;
T* ptr_ = nullptr;
size_t size_ = 0;
FreePtr free_ = nullptr;
void* opaque_ = nullptr;
};
// Allocate an aligned and uninitialized array of POD values as an AlignedPtr.
// Upon destruction of the AlignedPtr the aligned array will be freed.
template <typename T>
AlignedPtr<T> AllocateAligned(const size_t items, AllocPtr alloc, FreePtr free,
void* opaque) {
static_assert(IsTriviallyCopyable<T>(),
"AllocateAligned: requires trivially copyable T");
static_assert(IsTriviallyDestructible<T>(),
"AllocateAligned: requires trivially destructible T");
return AlignedPtr<T>(
detail::AllocateAlignedItems<T>(items, alloc, opaque), items,
&detail::FreeAlignedMemory,
reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(free)));
}
// Same as previous AllocateAligned(), using default allocate/free functions.
template <typename T>
AlignedPtr<T> AllocateAligned(const size_t items) {
return AllocateAligned<T>(items, nullptr, nullptr, nullptr);
}
namespace detail {
template <typename T>
struct IsSpanT {
enum { value = 0 };
};
template <typename T>
struct IsSpanT<Span<T>> {
enum { value = 1 };
};
template <typename T>
static constexpr bool IsSpan() {
return IsSpanT<RemoveCvRef<T>>::value;
}
template <typename T, typename Ptr, typename = void>
struct HasDataT {
enum { value = 0 };
};
template <typename T, typename Ptr>
struct HasDataT<
T, Ptr, EnableIf<IsConvertible<decltype(DeclVal<T&>().data()), Ptr>()>> {
enum { value = 1 };
};
template <typename T, typename = void>
struct HasSizeT {
enum { value = 0 };
};
template <typename T>
struct HasSizeT<
T, EnableIf<IsConvertible<decltype(DeclVal<T&>().size()), size_t>()>> {
enum { value = 1 };
};
template <typename T, typename C>
static constexpr bool IsCompatibleContainer() {
// Exclude Span because those are always safe to copy (view types).
return !IsSpan<C>() && HasDataT<C, T*>::value && HasSizeT<C>::value;
}
} // namespace detail
// A simple span containing data and size of data.
template <typename T>
class Span {
public:
using value_type = T;
constexpr Span() noexcept = default;
constexpr Span(T* data, size_t size) noexcept : size_(size), data_(data) {}
// Construct from pointers.
template <typename Begin, typename End,
EnableIf<!IsInteger<Begin>() && !IsInteger<End>() &&
IsConvertible<Begin, T*>() && IsConvertible<End, T*>()>* =
nullptr>
constexpr Span(Begin begin, End end) noexcept
: size_(
static_cast<size_t>(static_cast<T*>(end) - static_cast<T*>(begin))),
data_(static_cast<T*>(begin)) {
HWY_DASSERT(static_cast<T*>(end) >= static_cast<T*>(begin));
}
// Construct from C-style fixed-size array.
template <typename U, size_t N, EnableIf<IsConvertible<U*, T*>()>* = nullptr>
constexpr Span(U (&arr)[N]) noexcept : size_(N), data_(arr) {}
// Construct from compatible Span (e.g. Span<T> to Span<const T>).
template <typename U, EnableIf<IsConvertible<U*, T*>()>* = nullptr>
constexpr Span(const Span<U>& other) noexcept
: size_(other.size()), data_(other.data()) {}
// Construct from mutable lvalue container.
template <typename C,
EnableIf<detail::IsCompatibleContainer<T, C&>()>* = nullptr>
constexpr Span(C& c) : size_(c.size()), data_(c.data()) {}
// Construct from const lvalue container.
template <typename C,
EnableIf<detail::IsCompatibleContainer<T, const C&>()>* = nullptr>
constexpr Span(const C& c) : size_(c.size()), data_(c.data()) {}
// Delete rvalue container construction to prevent dangling pointers.
template <typename C,
EnableIf<detail::IsCompatibleContainer<T, const C&>()>* = nullptr>
Span(const C&&) = delete;
// Copies the contents of the non-const initializer lists to the span.
template <typename T2 = T, EnableIf<!IsConst<T2>()>* = nullptr>
Span<T>& operator=(std::initializer_list<const T2> v) {
HWY_DASSERT(size_ == v.size());
CopyBytes(v.begin(), data_, HWY_MIN(size_, v.size()) * sizeof(T));
return *this;
}
// Returns the number of elements in the span.
constexpr size_t size() const noexcept { return size_; }
// Returns the size of the contained data in bytes.
constexpr size_t size_bytes() const noexcept { return size_ * sizeof(T); }
constexpr bool empty() const noexcept { return size_ == 0; }
// Returns a pointer to the contained data.
constexpr T* data() const noexcept { return data_; }
// Returns the element at index.
constexpr T& operator[](size_t index) const {
HWY_DASSERT(index < size_);
return data_[index];
}
// Returns reference to the first element.
constexpr T& front() const {
HWY_DASSERT(!empty());
return data_[0];
}
// Returns reference to the last element.
constexpr T& back() const {
HWY_DASSERT(!empty());
return data_[size_ - 1];
}
// Returns an iterator pointing to the first element of this span.
constexpr T* begin() const noexcept { return data_; }
// Returns a const iterator pointing to the first element of this span.
constexpr const T* cbegin() const noexcept { return data_; }
// Returns an iterator pointing just beyond the last element at the
// end of this span.
constexpr T* end() const noexcept { return data_ + size_; }
// Returns a const iterator pointing just beyond the last element at the
// end of this span.
constexpr const T* cend() const noexcept { return data_ + size_; }
// Returns a subspan starting at offset with count elements.
constexpr Span<T> subspan(size_t offset, size_t count = ~size_t{0}) const {
HWY_DASSERT(offset <= size_);
HWY_DASSERT(count == ~size_t{0} || count <= size_ - offset);
return Span<T>(data_ + offset,
count == ~size_t{0} ? size_ - offset : count);
}
// Returns a subspan of the first count elements.
constexpr Span<T> first(size_t count) const {
HWY_DASSERT(count <= size_);
return Span<T>(data_, count);
}
// Returns a subspan of the last count elements.
constexpr Span<T> last(size_t count) const {
HWY_DASSERT(count <= size_);
return Span<T>(data_ + (size_ - count), count);
}
// Shrinks the span by removing the first count elements.
void remove_prefix(size_t count) {
HWY_DASSERT(count <= size_);
data_ += count;
size_ -= count;
}
// Shrinks the span by removing the last count elements.
void remove_suffix(size_t count) {
HWY_DASSERT(count <= size_);
size_ -= count;
}
private:
size_t size_ = 0;
T* data_ = nullptr;
};
template <typename T>
Span<T> AlignedPtr<T>::span() const& noexcept {
return Span<T>(ptr_, size_);
}
// Returns a read-only view of the bytes in the span.
template <typename T>
Span<const uint8_t> as_bytes(Span<T> s) noexcept {
return Span<const uint8_t>(reinterpret_cast<const uint8_t*>(s.data()),
s.size_bytes());
}
// Returns a writable view of the bytes in the span.
template <typename T, EnableIf<!IsConst<T>()>* = nullptr>
Span<uint8_t> as_writable_bytes(Span<T> s) noexcept {
return Span<uint8_t>(reinterpret_cast<uint8_t*>(s.data()), s.size_bytes());
}
// `ByteSpan` and `WritableByteSpan` return byte views of `count` elements
// starting at `ptr`, of `bytes` starting at a `void*`, of a C array, of a
// `Span<T>`, or of a container `c`. They exist for C++14 compatibility: without
// class template argument deduction (C++17) and `std::as_bytes` (C++20),
// callers would otherwise have to spell out
// `Span<const uint8_t>(reinterpret_cast<const uint8_t*>(p), n)`. Note that a
// string literal is `const char[N]`, so `ByteSpan("abc")` includes the trailing
// NUL (4 bytes); pass `std::string` or `ByteSpan("abc", 3)` to exclude it.
template <typename T, EnableIf<!IsSame<RemoveCvRef<T>, void>()>* = nullptr>
Span<const uint8_t> ByteSpan(const T* ptr, size_t count) noexcept {
static_assert(IsTriviallyCopyable<RemoveCvRef<T>>(),
"ByteSpan requires trivially copyable T");
HWY_DASSERT(count <= LimitsMax<size_t>() / sizeof(T));
return Span<const uint8_t>(reinterpret_cast<const uint8_t*>(ptr),
count * sizeof(T));
}
inline Span<const uint8_t> ByteSpan(const void* ptr, size_t bytes) noexcept {
return Span<const uint8_t>(static_cast<const uint8_t*>(ptr), bytes);
}
template <typename T, size_t N>
Span<const uint8_t> ByteSpan(const T (&arr)[N]) noexcept {
return ByteSpan(arr, N);
}
template <typename T>
Span<const uint8_t> ByteSpan(Span<T> s) noexcept {
return ByteSpan(s.data(), s.size());
}
template <typename C, EnableIf<!detail::IsSpan<C>() && !IsArray<C>() &&
detail::HasDataT<const C&, const void*>::value &&
detail::HasSizeT<const C&>::value>* = nullptr>
Span<const uint8_t> ByteSpan(const C& c) noexcept {
return ByteSpan(c.data(), c.size());
}
template <typename C, EnableIf<!detail::IsSpan<C>() && !IsArray<C>() &&
detail::HasDataT<const C&, const void*>::value &&
detail::HasSizeT<const C&>::value>* = nullptr>
void ByteSpan(const C&&) = delete;
// Mutable counterpart of `ByteSpan`.
template <typename T,
EnableIf<!IsConst<T>() && !IsSame<RemoveCvRef<T>, void>()>* = nullptr>
Span<uint8_t> WritableByteSpan(T* ptr, size_t count) noexcept {
static_assert(IsTriviallyCopyable<RemoveCvRef<T>>(),
"WritableByteSpan requires trivially copyable T");
HWY_DASSERT(count <= LimitsMax<size_t>() / sizeof(T));
return Span<uint8_t>(reinterpret_cast<uint8_t*>(ptr), count * sizeof(T));
}
inline Span<uint8_t> WritableByteSpan(void* ptr, size_t bytes) noexcept {
return Span<uint8_t>(static_cast<uint8_t*>(ptr), bytes);
}
template <typename T, size_t N, EnableIf<!IsConst<T>()>* = nullptr>
Span<uint8_t> WritableByteSpan(T (&arr)[N]) noexcept {
return WritableByteSpan(arr, N);
}
template <typename T, EnableIf<!IsConst<T>()>* = nullptr>
Span<uint8_t> WritableByteSpan(Span<T> s) noexcept {
return WritableByteSpan(s.data(), s.size());
}
template <typename C,
EnableIf<!IsConst<C>() && !detail::IsSpan<C>() && !IsArray<C>() &&
detail::HasDataT<C&, void*>::value &&
detail::HasSizeT<C&>::value>* = nullptr>
Span<uint8_t> WritableByteSpan(C& c) noexcept {
return WritableByteSpan(c.data(), c.size());
}
// Deduction guides to infer the constness of T from the constness of U
// (requires C++17)
#if HWY_CXX_LANG >= 201703L
template <typename T>
Span(T*, size_t) -> Span<T>;
template <typename T>
Span(T*, T*) -> Span<T>;
template <typename T, size_t N>
Span(T (&)[N]) -> Span<T>;
template <typename U>
Span(U&) -> Span<RemoveRef<decltype(*DeclVal<U&>().data())>>;
template <typename U>
Span(const U&) -> Span<const RemoveRef<decltype(*DeclVal<const U&>().data())>>;
#endif // HWY_CXX_LANG >= 201703L
// A multi dimensional array containing an aligned buffer.
//
// To maintain alignment, the innermost dimension will be padded to ensure all
// innermost arrays are aligned.
template <typename T, size_t axes>
class AlignedNDArray {
static_assert(IsTrivial<T>(),
"AlignedNDArray can only contain trivial types");
public:
AlignedNDArray(AlignedNDArray&& other) = default;
AlignedNDArray& operator=(AlignedNDArray&& other) = default;
// Constructs an array of the provided shape and fills it with zeros.
explicit AlignedNDArray(std::array<size_t, axes> shape) : shape_(shape) {
sizes_ = ComputeSizes(shape_);
memory_shape_ = shape_;
// Round the innermost dimension up to the number of bytes available for
// SIMD operations on this architecture to make sure that each innermost
// array is aligned from the first element.
memory_shape_[axes - 1] = RoundUpTo(memory_shape_[axes - 1], VectorBytes());
memory_sizes_ = ComputeSizes(memory_shape_);
buffer_ = hwy::AllocateAligned<T>(memory_size());
// AllocateAligned returns nullptr if the allocation failed or the byte
// count (memory_size() * sizeof(T)) overflowed size_t. ZeroBytes is memset,
// so zeroing a null buffer is a null-pointer write (UB); abort with a clear
// message instead, mirroring the overflow check in ComputeSizes().
if (HWY_UNLIKELY(buffer_.get() == nullptr)) {
HWY_ABORT("AlignedNDArray: failed to allocate %zu elements",
memory_size());
}
hwy::ZeroBytes(buffer_.get(), memory_size() * sizeof(T));
}
// Returns a span containing the innermost array at the provided indices.
Span<T> operator[](std::array<const size_t, axes - 1> indices) {
return Span<T>(buffer_.get() + Offset(indices), sizes_[indices.size()]);
}
// Returns a const span containing the innermost array at the provided
// indices.
Span<const T> operator[](std::array<const size_t, axes - 1> indices) const {
return Span<const T>(buffer_.get() + Offset(indices),
sizes_[indices.size()]);
}
// Returns the shape of the array, which might be smaller than the allocated
// buffer after padding the last axis to alignment.
const std::array<size_t, axes>& shape() const { return shape_; }
// Returns the shape of the allocated buffer, which might be larger than the
// used size of the array after padding to alignment.
const std::array<size_t, axes>& memory_shape() const { return memory_shape_; }
// Returns the size of the array, which might be smaller than the allocated
// buffer after padding the last axis to alignment.
size_t size() const { return sizes_[0]; }
// Returns the size of the allocated buffer, which might be larger than the
// used size of the array after padding to alignment.
size_t memory_size() const { return memory_sizes_[0]; }
// Returns a pointer to the allocated buffer.
T* data() { return buffer_.get(); }
// Returns a const pointer to the buffer.
const T* data() const { return buffer_.get(); }
// Truncates the array by updating its shape.
//
// The new shape must be equal to or less than the old shape in all axes.
//
// Doesn't modify underlying memory.
void truncate(const std::array<size_t, axes>& new_shape) {
#if HWY_IS_DEBUG_BUILD
for (size_t axis_index = 0; axis_index < axes; ++axis_index) {
HWY_ASSERT(new_shape[axis_index] <= shape_[axis_index]);
}
#endif
shape_ = new_shape;
sizes_ = ComputeSizes(shape_);
}
private:
std::array<size_t, axes> shape_;
std::array<size_t, axes> memory_shape_;
std::array<size_t, axes + 1> sizes_;
std::array<size_t, axes + 1> memory_sizes_;
hwy::AlignedPtr<T> buffer_;
// Computes offset in the buffer based on the provided indices.
size_t Offset(std::array<const size_t, axes - 1> indices) const {
size_t offset = 0;
size_t shape_index = 0;
for (const size_t axis_index : indices) {
if (HWY_UNLIKELY(axis_index >= shape_[shape_index])) {
HWY_ABORT("AlignedNDArray index %zu out of bounds (axis %zu, size %zu)",
axis_index, shape_index, shape_[shape_index]);
}
offset += memory_sizes_[shape_index + 1] * axis_index;
shape_index++;
}
return offset;
}
// Computes the sizes of all sub arrays based on the sizes of each axis.
//
// Does this by multiplying the size of each axis with the previous one in
// reverse order, starting with the conceptual axis of size 1 containing the
// actual elements in the array.
static std::array<size_t, axes + 1> ComputeSizes(
std::array<size_t, axes> shape) {
std::array<size_t, axes + 1> sizes;
size_t axis = shape.size();
sizes[axis] = 1;
while (axis > 0) {
--axis;
// Check for integer overflow in dimension multiplication.
if (HWY_LIKELY(shape[axis] != 0) &&
sizes[axis + 1] > SIZE_MAX / shape[axis]) {
HWY_ABORT("AlignedNDArray: dimension overflow at axis %zu "
"(%zu * %zu exceeds size_t)",
axis, sizes[axis + 1], shape[axis]);
}
sizes[axis] = sizes[axis + 1] * shape[axis];
}
return sizes;
}
};
} // namespace hwy
#endif // HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_