morton/
lib.rs

1/// Convert 2D spatial coordinates to Morton z-order value
2///
3/// Uses bithacks as described in:
4/// http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
5#[inline]
6pub fn interleave_morton(x: u16, y: u16) -> u32 {
7    if cfg!(target_pointer_width = "64") {
8        let x = x as u64;
9        let y = y as u64;
10
11        let z = y << 32 | x;
12        let z = (z | (z << 8)) & 0x00FF00FF_00FF00FF;
13        let z = (z | (z << 4)) & 0x0F0F0F0F_0F0F0F0F;
14        let z = (z | (z << 2)) & 0x33333333_33333333;
15        let z = (z | (z << 1)) & 0x55555555_55555555;
16
17        let z = z | ((z >> 32) << 1);
18        z as u32
19    } else {
20        let x = x as u32;
21        let x = (x | (x << 8)) & 0x00FF00FF;
22        let x = (x | (x << 4)) & 0x0F0F0F0F;
23        let x = (x | (x << 2)) & 0x33333333;
24        let x = (x | (x << 1)) & 0x55555555;
25
26        let y = y as u32;
27        let y = (y | (y << 8)) & 0x00FF00FF;
28        let y = (y | (y << 4)) & 0x0F0F0F0F;
29        let y = (y | (y << 2)) & 0x33333333;
30        let y = (y | (y << 1)) & 0x55555555;
31
32        x | (y << 1)
33    }
34}
35
36/// Convert Morton z-order value to 2D spatial coordinates
37///
38/// Uses bithacks as described in:
39/// http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton
40#[inline]
41pub fn deinterleave_morton(z: u32) -> (u16, u16) {
42    if cfg!(target_pointer_width = "64") {
43        let z = z as u64;
44
45        let z = (z | ((z >> 1) << 32)) & 0x55555555_55555555;
46        let z = (z | (z >> 1)) & 0x33333333_33333333;
47        let z = (z | (z >> 2)) & 0x0F0F0F0F_0F0F0F0F;
48        let z = (z | (z >> 4)) & 0x00FF00FF_00FF00FF;
49        let z = (z | (z >> 8)) & 0x0000FFFF_0000FFFF;
50
51        let x = (z & 0x00000000_0000FFFF) as u16;
52        let y = ((z >> 32) & 0x00000000_0000FFFF) as u16;
53
54        (x, y)
55    } else {
56        let x = z & 0x55555555;
57        let x = (x | (x >> 1)) & 0x33333333;
58        let x = (x | (x >> 2)) & 0x0F0F0F0F;
59        let x = (x | (x >> 4)) & 0x00FF00FF;
60        let x = ((x | (x >> 8)) & 0x0000FFFF) as u16;
61
62        let y = (z >> 1) & 0x55555555;
63        let y = (y | (y >> 1)) & 0x33333333;
64        let y = (y | (y >> 2)) & 0x0F0F0F0F;
65        let y = (y | (y >> 4)) & 0x00FF00FF;
66        let y = ((y | (y >> 8)) & 0x0000FFFF) as u16;
67
68        (x, y)
69    }
70}
71
72/// Private test and bench helper functions
73#[doc(hidden)]
74pub mod utils {
75    pub fn idx_tile_tuple(xy: (u16, u16), stride: usize) -> usize {
76        let (x, y) = xy;
77        stride * y as usize + x as usize
78    }
79
80    pub fn idx_tile(x: usize, y: usize, stride: usize) -> usize {
81        stride * y + x
82    }
83}
morton/lib.rs

morton/
lib.rs
