morton.hpp File Reference

Core Morton<Dim,Bits> type — Z-order codes with O(1) arithmetic in Morton space. More...

#include <array>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include "morton/wide_uint.hpp"
#include <immintrin.h>
#include "morton/hd.hpp"

Include dependency graph for morton.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	morton::detail::uint_for< NBits >
class	morton::Morton< Dim, Bits >
	A Morton (Z-order) code interleaving Dim unsigned coordinates of Bits bits each. More...

Namespaces
namespace	morton
namespace	morton::detail

Macros
#define	MORTON_X86   0
#define	MORTON_ENABLE_RUNTIME_DISPATCH   0
#define	MORTON_X86_RUNTIME_DISPATCH   0
#define	MORTON_HAS_INT128   1
#define	MORTON_MAX_BITS   256

Typedefs
using	morton::detail::uint128_t = unsigned __int128
template<unsigned NBits>
using	morton::detail::uint_for_t = typename uint_for< NBits >::type
using	morton::Morton2D32 = Morton< 2, 32 >
using	morton::Morton2D16 = Morton< 2, 16 >
using	morton::Morton3D21 = Morton< 3, 21 >
using	morton::Morton3D16 = Morton< 3, 16 >
using	morton::Morton3D32 = Morton< 3, 32 >
using	morton::Morton2D64 = Morton< 2, 64 >

Functions
MORTON_HD constexpr bool	morton::detail::is_consteval () noexcept
MORTON_HD constexpr unsigned	morton::detail::pow3 (unsigned n)
template<unsigned Dim, unsigned Bits, typename Code >
MORTON_HD constexpr Code	morton::detail::axis_mask (unsigned d)
template<unsigned Dim, unsigned Bits, typename Code , typename Coord >
MORTON_HD constexpr Code	morton::detail::spread_sw (Coord x, unsigned d)
template<unsigned Dim, unsigned Bits, typename Code , typename Coord >
MORTON_HD constexpr Coord	morton::detail::compact_sw (Code c, unsigned d)

Detailed Description

Core Morton<Dim,Bits> type — Z-order codes with O(1) arithmetic in Morton space.

A small, header-only C++17 library for Morton (Z-order) codes whose distinguishing feature is arithmetic directly in Morton space: you can increment, decrement, add to or step along a single axis, or find a neighbour, in a handful of branchless instructions — without decoding to coordinates and re-encoding.

Encoding/decoding uses the BMI2 PDEP/PEXT instructions when available (-mbmi2, codes up to 64 bits) and a portable software implementation otherwise. The software path is constexpr, so encode/decode/arithmetic can run at compile time (e.g. to build lookup tables).

Codes up to 64 bits are stored in a built-in unsigned integer; codes from 65 to 128 bits use __uint128_t where the compiler provides it (GCC/Clang), so 3D 32-bit (96 bits) and 2D 64-bit (128 bits) work too. Wider codes use wide_uint.hpp.

SPDX-License-Identifier: MIT

Macro Definition Documentation

MORTON_X86

#define MORTON_X86   0

MORTON_ENABLE_RUNTIME_DISPATCH

#define MORTON_ENABLE_RUNTIME_DISPATCH   0

MORTON_X86_RUNTIME_DISPATCH

#define MORTON_X86_RUNTIME_DISPATCH   0

MORTON_HAS_INT128

#define MORTON_HAS_INT128   1

MORTON_MAX_BITS

#define MORTON_MAX_BITS   256