morton 0.3.1

Morton space filling curve functions
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/// Convert 2D spatial coordinates to Morton z-order value
///
/// Uses bithacks as described in:
/// <http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN>
#[inline]
pub const fn interleave_morton(x: u16, y: u16) -> u32 {
    if cfg!(target_pointer_width = "64") {
        let x = x as u64;
        let y = y as u64;

        let z = y << 32 | x;
        let z = (z | (z << 8)) & 0x00FF00FF_00FF00FF;
        let z = (z | (z << 4)) & 0x0F0F0F0F_0F0F0F0F;
        let z = (z | (z << 2)) & 0x33333333_33333333;
        let z = (z | (z << 1)) & 0x55555555_55555555;

        let z = z | ((z >> 32) << 1);
        z as u32
    } else {
        let x = x as u32;
        let x = (x | (x << 8)) & 0x00FF00FF;
        let x = (x | (x << 4)) & 0x0F0F0F0F;
        let x = (x | (x << 2)) & 0x33333333;
        let x = (x | (x << 1)) & 0x55555555;

        let y = y as u32;
        let y = (y | (y << 8)) & 0x00FF00FF;
        let y = (y | (y << 4)) & 0x0F0F0F0F;
        let y = (y | (y << 2)) & 0x33333333;
        let y = (y | (y << 1)) & 0x55555555;

        x | (y << 1)
    }
}

/// Convert Morton z-order value to 2D spatial coordinates
///
/// Uses bithacks as described in:
/// <http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton>
#[inline]
pub const fn deinterleave_morton(z: u32) -> (u16, u16) {
    if cfg!(target_pointer_width = "64") {
        let z = z as u64;

        let z = (z | ((z >> 1) << 32)) & 0x55555555_55555555;
        let z = (z | (z >> 1)) & 0x33333333_33333333;
        let z = (z | (z >> 2)) & 0x0F0F0F0F_0F0F0F0F;
        let z = (z | (z >> 4)) & 0x00FF00FF_00FF00FF;
        let z = (z | (z >> 8)) & 0x0000FFFF_0000FFFF;

        let x = (z & 0x00000000_0000FFFF) as u16;
        let y = ((z >> 32) & 0x00000000_0000FFFF) as u16;

        (x, y)
    } else {
        let x = z & 0x55555555;
        let x = (x | (x >> 1)) & 0x33333333;
        let x = (x | (x >> 2)) & 0x0F0F0F0F;
        let x = (x | (x >> 4)) & 0x00FF00FF;
        let x = ((x | (x >> 8)) & 0x0000FFFF) as u16;

        let y = (z >> 1) & 0x55555555;
        let y = (y | (y >> 1)) & 0x33333333;
        let y = (y | (y >> 2)) & 0x0F0F0F0F;
        let y = (y | (y >> 4)) & 0x00FF00FF;
        let y = ((y | (y >> 8)) & 0x0000FFFF) as u16;

        (x, y)
    }
}

/// Private test and bench helper functions
#[doc(hidden)]
pub mod utils {
    pub fn idx_tile_tuple(xy: (u16, u16), stride: usize) -> usize {
        let (x, y) = xy;
        stride * y as usize + x as usize
    }

    pub fn idx_tile(x: usize, y: usize, stride: usize) -> usize {
        stride * y + x
    }
}