Crate zorder

This crate provides functions to convert N-dimensional¹ coordinates to Z-order curve indexes and back. Z-order curve, also known as Morton code, is a mapping of N-dimensional coordinates to 1D index which preverses locality. It is cache-efficient way of storing N-dimensional data in 1D array.

This crate provides two implementations of the Z-order curve, one using a software implementation supported by all platforms and one using bmi2 instructions supported by modern x86_64 CPUs.

Examples

Basic usage with software implementation:

use zorder::{coord_of, index_of};

let idx = index_of([1u16, 1u16]);
assert_eq!(idx, 3u32);

let coord = coord_of(idx);
assert_eq!(coord, [1u16, 1u16]);

Basic usage with bmi2 implementation:

use zorder::bmi2::{coord_of, coord_of_unchecked, HardwareSupportToken, index_of, index_of_unchecked};

// Safe interface with hardware support token.
let support_token = HardwareSupportToken::new();
if let Some(support_token) = support_token {
    let idx = index_of([1u16, 1u16], support_token);
    assert_eq!(idx, 3u32);

    let coord = coord_of(idx, support_token);
    assert_eq!(coord, [1u16, 1u16]);
}

// Unsafe interface with hardware support check.
// Only works on x86_64 CPUs.
if zorder::bmi2::has_hardware_support() {
    let idx = unsafe { index_of_unchecked([1u16, 1u16]) };
    assert_eq!(idx, 3u32);

    let coord = unsafe { coord_of_unchecked(idx) };
    assert_eq!(coord, [1u16, 1u16]);
}

---

1. Maximum number of dimensions is limited by the largest unsigned integer type, u128, which is able to store 16 8-bit coordinates. bmi2 based approach is limited to u64. ↩

Modules

• bmi2
  bmi2 module provides Z-order curve index and coordinate calculations using the bmi2 instruction set.

Traits

• Deinterleave
  Deinterleave a single number from a set of interleaved numbers. Inverse of Interleave.
• Interleave
  Interleaves the bits of the given number, while taking output dimension into account.

Functions

• coord_of
  Returns the N-dimensional coordinates of the given Z-order curve index.
• index_of
  Calculates Z-order curve index for given sequence of coordinates.