morton-arithmetic

A small, header-only C++17 library for Morton (Z-order) codes whose distinguishing feature is arithmetic directly in Morton space.

Most Morton libraries only encode (interleave coordinates into a code) and decode (the inverse). This one adds the operations you actually want when you navigate a Z-ordered grid:

increment / decrement / add along a single axis,
find a neighbour,
step to the next or previous cell in Z-order,
sweep an axis-aligned region,

…all without the usual decode → modify → re-encode round trip. Each is a handful of branchless integer instructions.

#include "morton/morton.hpp"
using morton::Morton;

Morton<2, 32> m = Morton<2, 32>::encode(x, y);  // interleave (PDEP)
m.inc(0);          // x += 1, in place, leaving y's interleaved bits untouched
m.add(1, 10);      // y += 10
auto n = m.neighbor(0, -1);   // the cell at (x-1, y+10)
auto [xx, yy] = m.decode();   // back to coordinates (PEXT)

Why this is faster

Holding a Morton code and needing a neighbour is extremely common: stencils, finite-difference sweeps, octree/quadtree traversal, ray marching, spatial hashing. The conventional approach decodes to coordinates, changes one, and re-encodes. This library mutates the relevant axis' bits in place.

Measured on this machine (Intel x86-64 with BMI2, g++ 14, -O3), 2D 32-bit:

operation	this library	conventional (decode+encode)	speedup
encode	1398 Mops/s	1400 Mops/s (libmorton)	parity
decode	2040 Mops/s	2012 Mops/s (libmorton)	parity
single neighbour (+1 on an axis)	2721 Mops/s	1110 Mops/s	2.5×
4-neighbour stencil (scattered)	6718 Mops/s	2245 Mops/s	3.0×

Encode/decode are at parity with libmorton (both use the hardware PDEP/PEXT instructions). The win is in the arithmetic operations, which libmorton and similar libraries do not provide.

Honest caveat (from profiling): for a dense, contiguous full-region sweep, simply re-encoding each (x, y) from scratch is actually faster than the arithmetic walk, because independent encodes pipeline while the arithmetic walk has a loop-carried dependency. The arithmetic advantage is for scattered / data-dependent neighbour access, where you already hold a code and cannot batch. See docs/EVALUATION.md.

Design

Header-only, C++17, no dependencies. #include "morton/morton.hpp".
Morton<Dim, Bits> interleaves Dim coordinates of Bits bits each; the code is stored in the smallest unsigned integer that fits. Dim * Bits ≤ 64 uses a built-in integer; 65–128 bits use __uint128_t where available, so 3D 32-bit (Morton3D32, 96-bit) and 2D 64-bit (Morton2D64, 128-bit) work too.
Encode/decode use BMI2 PDEP/PEXT when compiled with -mbmi2, with a portable software fallback otherwise. Both paths are tested for agreement.
constexpr: the software path runs at compile time (selected via __builtin_is_constant_evaluated()), so you can build lookup tables in constexpr.
Arithmetic wraps modulo 2^Bits per axis (branchless); add_sat/sub_sat/ try_add/try_sub clamp or refuse instead of wrapping.

Headers

header	provides
`morton/morton.hpp`	`Morton<Dim,Bits>`: encode/decode, axis arithmetic, saturating ops, `face_neighbors`/`all_neighbors`, `ancestor`/`child` hierarchy, Z-order `++/--`
`morton/iterate.hpp`	`for_each_in_box` (row-major), `for_each_in_box_zorder` (Z-order), and the Tropf-Herzog range-search pair `bigmin_in_box` / `litmax_in_box`
`morton/batch.hpp`	vectorised bulk `add`/`sub`/`step`/`encode` over arrays (AVX2 auto-vectorised)
`morton/wide_uint.hpp`	fixed-width word-array unsigned backing codes wider than 128 bits (pulled in automatically)

Convenience aliases: Morton2D32, Morton2D16, Morton3D21, Morton3D16, Morton3D32, Morton2D64. Codes wider than 128 bits (up to MORTON_MAX_BITS, default 256) work too, e.g. Morton<3,64> (192-bit), Morton<2,128> (256-bit).

A linear octree/quadtree built on this library lives in the sibling octree/ project (morton_octree::Octree) — it is being split into its own repository; see octree/PLAN.md.

GPU (Kokkos)

A portable Kokkos backend lives in include/morton/kokkos.hpp (morton::kokkos). Because the core marks its functions with MORTON_HD (which defers to KOKKOS_FUNCTION), the device kernels run the same Morton<Dim,Bits> code as the CPU — no separate implementation — on any Kokkos backend (CUDA / HIP / OpenMP / Serial); the backend and architecture come from the Kokkos build, not the source. It offers Kokkos::View-based bulk ops (encode2/3, decode2/3, per-axis add/sub/step) plus *_host raw-pointer convenience wrappers. On an RTX 5080 (CUDA backend), 2D-32 encode hits ~51,000 Mops/s when data is resident on the GPU (~33× one CPU core); a one-shot call on host data is PCIe-transfer-bound and no faster than the CPU, so the GPU pays off only when codes live on-device across a pipeline. Opt in with -DMORTON_ENABLE_KOKKOS=ON (see DEVELOPMENT.md).

Build, test, benchmark

Full per-platform setup (incl. Python wheels and the GPU build) is in DEVELOPMENT.md. Quick start:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure   # or: ./build/tests/morton_tests
./build/benchmarks/morton_bench

As a header-only dependency in another CMake project — either vendored:

add_subdirectory(morton_arithmetic)
target_link_libraries(your_target PRIVATE morton::morton)

…or installed and found via find_package (an install exports a CMake package config; Conan recipe in conanfile.py, vcpkg port in packaging/vcpkg/morton/):

find_package(morton CONFIG REQUIRED)
target_link_libraries(your_target PRIVATE morton::morton)

The test suite cross-checks every encode/decode against both a bit-by-bit reference and libmorton, validates all arithmetic exhaustively on small grids and against decode/modify/encode on large random inputs, and validates the region iterators against brute force (>1M assertions).

Python

A vectorised NumPy interface (pure ctypes, no pybind11/native build deps beyond a C++ compiler), published on PyPI as peclet-morton and imported as peclet.morton (part of the peclet suite namespace). Install as a wheel with scikit-build-core:

pip install .            # builds the extension and bundles it into the wheel
python -m pytest bindings/python/tests -q

import numpy as np, peclet.morton as ma
x = np.arange(1000, dtype=np.uint32); y = x * 2
codes = ma.encode(x, y, bits=32)
shifted = ma.shift(codes, axis=0, delta=+1, dims=2, bits=32)  # +1 in x, no decode
print(ma.decode(shifted, dims=2, bits=32))

For a quick dev loop without installing, drop the .so next to the package and use PYTHONPATH:

cmake --build build --target mortonarith_c
PYTHONPATH=bindings/python python3 -m pytest bindings/python/tests -q

Every call runs over whole arrays in compiled code. The arithmetic shift is ~3× faster than decode+encode in Python too (see bindings/python/bench_python.py).

Repository layout

include/morton/      the library: morton.hpp, iterate.hpp, batch.hpp, simd.hpp,
                     wide_uint.hpp, kokkos.hpp (portable GPU backend)
tests/               doctest suite (encode/decode, arithmetic, constexpr, wide,
                     neighbours, batch, iterate)
benchmarks/          C++ micro-benchmarks (vs libmorton) + batch/SIMD benchmark
bindings/python/     ctypes + NumPy wrapper and pytest tests
pyproject.toml       scikit-build-core wheel build + cibuildwheel config
conanfile.py         Conan recipe;  packaging/vcpkg/  vcpkg port
cmake/               CMake package-config template (find_package(morton))
.github/workflows/   ci.yml (build matrix) + release.yml (PyPI wheels on tag)
docs/                EVALUATION.md, ROADMAP.md, HILBERT_GPU_NOTES.md, Doxyfile
octree/              sibling project: linear octree on this library (being split out)
legacy/              the original arbitrary-width BitArray + octree prototype
third_party/         vendored doctest and libmorton (tests/benchmarks only)

The legacy/ directory holds the project's original prototype: an arbitrary-width BitArray, a wide-code Morton, and an octree built on it. The new core supersedes it for codes that fit in 64 bits; see the roadmap for how the octree could be ported.

License

MIT — see LICENSE.

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

peclet_morton-0.2.1.tar.gz (169.4 kB view details)

Uploaded Jul 25, 2026 Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

The dropdown lists show the available interpreters, ABIs, and platforms. Enable javascript to be able to filter the list of wheel files.

peclet_morton-0.2.1-cp313-cp313-win_amd64.whl (22.6 kB view details)

Uploaded Jul 25, 2026 CPython 3.13Windows x86-64

peclet_morton-0.2.1-cp313-cp313-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded Jul 25, 2026 CPython 3.13musllinux: musl 1.2+ x86-64

peclet_morton-0.2.1-cp313-cp313-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (35.2 kB view details)

Uploaded Jul 25, 2026 CPython 3.13manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

peclet_morton-0.2.1-cp313-cp313-macosx_11_0_arm64.whl (28.4 kB view details)

Uploaded Jul 25, 2026 CPython 3.13macOS 11.0+ ARM64

peclet_morton-0.2.1-cp312-cp312-win_amd64.whl (22.6 kB view details)

Uploaded Jul 25, 2026 CPython 3.12Windows x86-64

peclet_morton-0.2.1-cp312-cp312-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded Jul 25, 2026 CPython 3.12musllinux: musl 1.2+ x86-64

peclet_morton-0.2.1-cp312-cp312-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (35.2 kB view details)

Uploaded Jul 25, 2026 CPython 3.12manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

peclet_morton-0.2.1-cp312-cp312-macosx_11_0_arm64.whl (28.4 kB view details)

Uploaded Jul 25, 2026 CPython 3.12macOS 11.0+ ARM64

peclet_morton-0.2.1-cp311-cp311-win_amd64.whl (22.6 kB view details)

Uploaded Jul 25, 2026 CPython 3.11Windows x86-64

peclet_morton-0.2.1-cp311-cp311-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded Jul 25, 2026 CPython 3.11musllinux: musl 1.2+ x86-64

peclet_morton-0.2.1-cp311-cp311-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (35.2 kB view details)

Uploaded Jul 25, 2026 CPython 3.11manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

peclet_morton-0.2.1-cp311-cp311-macosx_11_0_arm64.whl (28.4 kB view details)

Uploaded Jul 25, 2026 CPython 3.11macOS 11.0+ ARM64

peclet_morton-0.2.1-cp310-cp310-win_amd64.whl (22.6 kB view details)

Uploaded Jul 25, 2026 CPython 3.10Windows x86-64

peclet_morton-0.2.1-cp310-cp310-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded Jul 25, 2026 CPython 3.10musllinux: musl 1.2+ x86-64

peclet_morton-0.2.1-cp310-cp310-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (35.2 kB view details)

Uploaded Jul 25, 2026 CPython 3.10manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

peclet_morton-0.2.1-cp310-cp310-macosx_11_0_arm64.whl (28.4 kB view details)

Uploaded Jul 25, 2026 CPython 3.10macOS 11.0+ ARM64

peclet_morton-0.2.1-cp39-cp39-win_amd64.whl (22.6 kB view details)

Uploaded Jul 25, 2026 CPython 3.9Windows x86-64

peclet_morton-0.2.1-cp39-cp39-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded Jul 25, 2026 CPython 3.9musllinux: musl 1.2+ x86-64

peclet_morton-0.2.1-cp39-cp39-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (35.2 kB view details)

Uploaded Jul 25, 2026 CPython 3.9manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

peclet_morton-0.2.1-cp39-cp39-macosx_11_0_arm64.whl (28.4 kB view details)

Uploaded Jul 25, 2026 CPython 3.9macOS 11.0+ ARM64

File details

Details for the file peclet_morton-0.2.1.tar.gz.

File metadata

Download URL: peclet_morton-0.2.1.tar.gz
Upload date: Jul 25, 2026
Size: 169.4 kB
Tags: Source
Uploaded using Trusted Publishing? Yes
Uploaded via: twine/6.1.0 CPython/3.13.14

File hashes

Hashes for peclet_morton-0.2.1.tar.gz
Algorithm	Hash digest
SHA256	`4073a328e552fb280ea407839dabae8a72846fed46fe350f626a1f918d9ce467`
MD5	`7f05f763295e610652c746ab9faad884`
BLAKE2b-256	`a09f38cf1b5f86e6f00e4a60ccb2dc8c8ea44bc909fe843377e39d5272770498`

Algorithm	Hash digest
SHA256	`86096868ce3499e7c51ed08772df5906af40738762afcdf3eaa833c6fa6142ad`
MD5	`1b6343810c5e6759a011d95e2715f3a5`
BLAKE2b-256	`db2697e1ea1c51eecad7b139eead770710a049d8e09b40741a176423b51de454`

Algorithm	Hash digest
SHA256	`ea58bc816cb12fbf73184957ba4094bb93d6b0640f9578d94ff6ac79ae0b57be`
MD5	`5775443cd832b86d9964e194a225a818`
BLAKE2b-256	`e49617e1c92a7db45a8aaec94936749eb155bf6f95b54aa922895e4bf1e29af9`

Algorithm	Hash digest
SHA256	`f382ec94daae555408e94003bd97bd9b43e52894a7ff4d273f344c824180dce8`
MD5	`d515a93f83c36240200335042ee3a11f`
BLAKE2b-256	`5ffd0d7a5f01ffca994f596cbb1db1716253d64bd0794f4aefb5a6f86cbb686c`

Algorithm	Hash digest
SHA256	`fbc7afe69e3c3fd22b9f8fbc8fb4efef3d5be5bf4f57a84fac12949302e883f9`
MD5	`c10f15ffefc5543b584ce5931c0ced1b`
BLAKE2b-256	`14604af48ca56c053a507cf0125556f1e28d61d0c9403da483d971ade762d78c`

Algorithm	Hash digest
SHA256	`677c95f480c1ec9b3d63e2a2608ef59c3e4105faae200913f278d48ba5d0e7ee`
MD5	`3c3a7bf8d9598a864db30f494c0217e3`
BLAKE2b-256	`9d5c8bd3b8f07ee0f7ccc06ec82885e9600f71fb1b4b532a090e3d4b1a16510e`

Algorithm	Hash digest
SHA256	`7c55005df29e2c1482c9e3e17110daa9c01a546f49ec83060ff744ac2546c0c0`
MD5	`c53ab56740933e7773aff1c47717b46e`
BLAKE2b-256	`6c385dc337b2ddb1f4371a4a93c1d3734946665f25e5a81928db08d76e529897`

Algorithm	Hash digest
SHA256	`740d6b25fae4fc466156174d42524e06e35de7fe63e6c569a4f8e935863f8f0d`
MD5	`158dc6ed9e56d17efcfe8584723f198d`
BLAKE2b-256	`b600a04d19769c0d842fc12a801756e8155c627c501f6e075365a8a0cf2c99aa`

Algorithm	Hash digest
SHA256	`c0a9d546b859f0b7a1690e9cb34a329a1f375073bcf390f164cc59f053ce48c1`
MD5	`7a28ba0a136db418a7c87497687d89f1`
BLAKE2b-256	`7fb07749e672812b0089124398ba92391c427dcc0349e59cf0f05867a5458f5b`

Algorithm	Hash digest
SHA256	`6cf8b7a1719b4036bd11ef1518a7113fc13a1c65b40ac8b2e85b3fdc62186b7f`
MD5	`9357647143698ad57f364cb60c01ffdd`
BLAKE2b-256	`3201a131ed8b91d785dd4cac220fadfba2158777674ffc37b8498c4c96a9cbd2`

Algorithm	Hash digest
SHA256	`fb67f6acc4507ce6a9ddaf77fb74bfb006b927f9ee07e0f59b03afbb506ba4ab`
MD5	`b4415cd78710f41e3bf838b5ad9815d8`
BLAKE2b-256	`19585237732015fc0b6436020ae2bd2130103da43833cf6d064c202112cc830b`

Algorithm	Hash digest
SHA256	`b5ef743f2f31958d42aeae72b94d0258551f61ab055b8e3f362d4276c90af8a2`
MD5	`3e54285c54b6d2ec64d7dea4ba570ccb`
BLAKE2b-256	`41d1ee44a584836f06f14947d85a0eee7b3433d91c6048e5e019a3de07569a07`

Algorithm	Hash digest
SHA256	`657c445b996fda20dfa49222fdab97792da495026f4627ad5a398f3cbf1c3753`
MD5	`470e404fd027d286676d1e34c697ebb6`
BLAKE2b-256	`af403bef74fff41bf4c4b00cf167fb6bb7042dc169b3cbad24c363f9f2fba739`

Algorithm	Hash digest
SHA256	`1beb20207c9a39a9659a8d3258995587f83e19d6c93d720e53e098f3a34f70f9`
MD5	`e302c6390eb79425add74329a1007780`
BLAKE2b-256	`10cce36dec44a1f1b15c31fdade7a823e0d7d305c6b509a9d5b8397cf11caa63`

Algorithm	Hash digest
SHA256	`e75b242e3e4c53bc426f0fdb5faec239b7e1a60c9ea366940e7a67791bbf3fdc`
MD5	`db46019996604d1455f5d1feb277e46d`
BLAKE2b-256	`41330d3279c6b99c05d72f71eaad6de545e36dde5ed1547e12e61bff4a7ad3b6`

Algorithm	Hash digest
SHA256	`df1e305314f14c611d2df5e309561fb46fdef79adb53d3070259b3fac2c0b15f`
MD5	`25dd94796e66f46ed02d2fe309f9d6c1`
BLAKE2b-256	`c1251543e58a0efd23ab057904b71663d04728cfb6d76da4de62c776c715ee02`

Algorithm	Hash digest
SHA256	`dc1a5278dc2d6372f69b9c662d700d35f323b27931d673b7a1d2007cec6739a9`
MD5	`575563d04ec83f049ce7bf9fe2cafbd5`
BLAKE2b-256	`fdcce739caeebb0bc22c0fed6935afcf8e442a7c30033a9de26ba004c03a5e24`

Algorithm	Hash digest
SHA256	`e7e6e63bdb9e598414356dc3282f74b2a5c40129657357155b6a200cd668e9c8`
MD5	`e6cdca87d28a79e20848a3d1dc639a69`
BLAKE2b-256	`bf257602cbdc9a79aa4f91875f916e3d00615feb91799abaa511f38bc12c78b8`

Algorithm	Hash digest
SHA256	`e79dadf6fe49c38d99cbade65d56757d1e5a4e272c9a0ff7d9790440f5e88093`
MD5	`b58926a6e6f20c59f3eebc2cee4ca470`
BLAKE2b-256	`9aedd0817c800bf2dbb350e493ad59f3d706fcd868a45085d6ddb44641206072`

Algorithm	Hash digest
SHA256	`dff1bcc015a48f94c6b1b088f51b4f4c2d20180209d3db44584ca4cbc03f4b23`
MD5	`709558c070902a897c3ba8d9202342af`
BLAKE2b-256	`b15be37b10edbc473836bc0505875771ee4f557e216a0b129c05acfec1d5aa4f`

Algorithm	Hash digest
SHA256	`12ebde8c411636db8cbbe61b9ba08c3d691d1d578a5fdb5b60606180f0492989`
MD5	`f3aaea6a59c41e0ea7789c4f2e379720`
BLAKE2b-256	`09b544cbd9190cdcae64a3a0afa79a409011a5f4f31ea9f8f1c61e4318057b96`

peclet-morton 0.2.1

morton-arithmetic

Why this is faster

Design

Headers

GPU (Kokkos)

Build, test, benchmark

Python

Repository layout

License

Project links

Key dates

1 maintainer

Credits

GitHub Statistics

License expression

Requires

Download files

Source Distribution

Built Distributions

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance