Awesome

Fork Changes

This is a fork of libmorton which includes Morton ND as a Git submodule.

The purpose of this fork is to provide benchmarking for Morton ND using the libmorton validation and performance test library written by Jeroen Baert (@Forceflow). See Morton ND's README.md for a sample set of performance metrics.

As such, its test code includes various Morton ND configurations for 32-bit and 64-bit 2D and 3D applications.

The hope is that this will demonstrate:

Morton ND's N-dimensional BMI2 hardware approach does not add overhead to the minimal implementation of calling and manipulating the results of native PDEP and PEXT instructions in assembly.
Morton ND's N-dimensional compile-time LUT generation implementation is performance equivalent to a static LUT approach (hard-coded) such as the one found in libmorton.
Tuning LUT table size based on target architecture and access pattern (possible using Morton ND's compile-time LUT generation) can significantly improve performance, something infeasible for hard-coded LUT approaches.

Furthermore, this fork may provide an easy way for users to compare algorithms based on their target application and architecture.

Compiling

Note that C++14 is required to build, a requirement imposed by Morton ND. The CMakeLists.txt sets -mbmi2 to enable BMI2 (hardware encoding) test paths. If your CPU does not support the BMI2 instruction set, remove the flag to disable corresponding tests. Always ensure release build settings are used for accurate performance metrics.

Building will take a long time (2-3 minutes on a decent laptop from ~2016). This is because large LUTs are generated for these tests (some as large at 2^21 entries used to validate extreme cases).

macOS

The original libmorton LUT ET and LUT Shifted ET tests do not seem to work on macOS, and have been commented-out for now. To re-enable them, uncomment any lines in libmorton_test.cpp::registerFunctions with either of those names.

Original README.md contents below

Libmorton

Libmorton is a C++11 header-only library with methods to efficiently encode/decode 64, 32 and 16-bit Morton codes and coordinates, in 2D and 3D. Morton order is also known as Z-order or the Z-order curve.
Libmorton is a lightweight and portable library - in its most basic form it only depends on standard C++ headers. Architecture-specific optimizations are implemented incrementally.
This library is under active development. SHIT WILL BREAK.
More info and some benchmarks in these blogposts: Morton encoding, Libmorton and BMI2 instruction set

Usage

Just include libmorton/morton.h. This will always have functions that point to the most efficient way to encode/decode Morton codes. If you want to test out alternative (and possibly slower) methods, you can find them in libmorton/morton2D.h and libmorton/morton3D.h. All libmorton functionality is in the libmorton namespace.

<pre> // ENCODING 2D / 3D morton codes, of length 32 and 64 bits inline uint_fast32_t morton2D_32_encode(const uint_fast16_t x, const uint_fast16_t y); inline uint_fast64_t morton2D_64_encode(const uint_fast32_t x, const uint_fast32_t y); inline uint_fast32_t morton3D_32_encode(const uint_fast16_t x, const uint_fast16_t y, const uint_fast16_t z); inline uint_fast64_t morton3D_64_encode(const uint_fast32_t x, const uint_fast32_t y, const uint_fast32_t z); // DECODING 2D / 3D morton codes, of length 32 and 64 bits inline void morton2D_32_decode(const uint_fast32_t morton, uint_fast16_t& x, uint_fast16_t& y); inline void morton2D_64_decode(const uint_fast64_t morton, uint_fast32_t& x, uint_fast32_t& y); inline void morton3D_32_decode(const uint_fast32_t morton, uint_fast16_t& x, uint_fast16_t& y, uint_fast16_t& z); inline void morton3D_64_decode(const uint_fast64_t morton, uint_fast32_t& x, uint_fast32_t& y, uint_fast32_t& z); </pre>

If you want to take advantage of the BMI2 instruction set (only available on Intel Haswell processors and newer), make sure __BMI2__ is defined before you include morton.h.

Testing

The test folder contains tools I use to test correctness and performance of the libmorton implementation. This section is under heavy re-writing, but might contain some useful code for advanced usage.

Citation

If you use libmorton in your paper or work, please reference it, for example as follows:

<pre> @Misc{libmorton18, author = "Jeroen Baert", title = "Libmorton: C++ Morton Encoding/Decoding Library", howpublished = "\url{https://github.com/Forceflow/libmorton}", year = "2018"} </pre>

Thanks / See ALso

To @gnzlbg and his Rust implementation bitwise for finding bugs in the Magicbits code
@kevinhartman made a C++14 library that supports N-dimensional morton codes morton-nd. He upstreamed a lot of fixes back to libmorton - thanks!
Everyone making comments and suggestions on the original blogpost
Fabian Giesen's post on Morton Codes

TODO

Write better test suite (with L1/L2 trashing, better tests, ...)
A better naming system for the functions, because m3D_e_sLUT_shifted? That escalated quickly.