zorder / 曲线索引转换

该包提供将N维[^1]坐标转换为Z-order曲线索引及其反向转换的函数。Z-order曲线，也称为Morton码，是一种将N维坐标映射到1D索引的映射，它保留了局部性。它是将N维数据存储在1D数组中的缓存高效方式。

[^1]: 最大维度数由最大的无符号整数类型限制，即u128，可以存储16个8位坐标。bmi2基于的方法限制为u64。

示例

软件实现

use zorder::{index_of, coord_of};

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

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

bmi2实现

这应该更快，但需要x86特定指令集支持。

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]);
}

您可以使用提供的示例验证您的CPU是否支持bmi2

$ cargo run --example bmi2_support

基准测试

以下是在两个不同的系统上使用的基准测试结果；在Ubuntu WSL2上的AMD Ryzen 9 7950X PC和Raspberry Pi 5上的Raspberry Pi OS。使用了标准的release配置文件。所有结果都四舍五入到三位有效数字。

您可以通过运行cargo bench来查看您机器上的结果。

Raspberry Pi 5具有非x86_64架构且不支持BMI2，因此没有这些基准测试的结果。

许可证

许可在以下之一下

• Apache License，版本2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• 麻省理工学院许可证（《LICENSE-MIT》或http://opensource.org/licenses/MIT）

由您选择。

除非您明确说明，否则根据Apache-2.0许可证定义，您有意提交的任何贡献，均应作为上述双许可，不附加任何额外条款或条件。