Module bitwise::word::morton

Encoding/decoding of Morton Z-curve indices.

The encode/decode 2d/3d functions in this module expose the fastest algorithm for the target and set of target features enabled when a nightly compiler is used.

Correctness

The default implementation is loss-less, that is, it preserve all information when encoding/decoding. This means that the encoding/decoding functions are invertible: encode(decode(m)) == m).

The bitmask and lut implementations in the sub-modules are lossy (not loss-less).

The decode/encode_3d_high_bits functions can be used to wrap a lossy implementation into a loss-less one.

Performance of the default algorithm

The default implementation is loss-less. It uses the bitmask-based everywhere except on x86 targets that support the BMI 2.0 instruction set.

Choice of default algorithms

This decision was based on the following facts:

• The bmi2 algorithm is the fastest on machines with the BMI 2.0 instruction set, but very slow otherwise.
• The performance of the bitmask and the look-up table (lut) algorithms in the micro-benchmarks is comparable.
• The lut version requires more memory than the bitmask version.

and this hypothesis:

The bitmask version might deliver better performance on real applications than the lut version because it uses less cache.

Since every real application is different, all implementations are still provided in the sub-modules. So when in doubt, benchmark your application with the different implementations and make an informed choice.

Choice of loss-less by default

The cost of making a lossy algorithm loss-less is within the measurement error. The trend shows a positive cost, but this cost is negligible, and the correctness/reliability gains are worth it.

Still, the higher bits that get lost by the lossy implementations are probably completely irrelevant in practice unless one is dealing with insanely large z-Curves.

Negligibly faster lossy implementations are provided in the bitmask and lut sub-modules.

The bmi2 implementation is always loss-less.

Modules

bitmask	Encoding/decoding of Morton Z-curve indices using precomputed bitmasks.
bmi2	Encoding/decoding of Morton Z-curve indices using BMI2 pdep/pext instructions.
lut	Encoding/decoding of Morton Z-curve indices using a look-up table.

Functions

decode_2d	Decodes an interleaved Morton index for a Z-Curve into two-dimensional coordinates.
decode_3d	Decodes an interleaved Morton index for a Z-Curve into three-dimensional coordinates.
decode_3d_high_bits	Decodes the high-bits of b into the coordinates x and y.
encode_2d	Encode coordinates x and y into an interleaved Morton index for a z-Curve.
encode_3d	Encode coordinates x, y, and z into an interleaved Morton index for a z-Curve.
encode_3d_high_bits	Encodes the high-bits of x and y into the Morton index v.