64-bit, 128-bit bit interleaved with (+/-) axis.

morton_space_fill.rs

mod bit_util_u64 {

  const SIGN_BIT_FLIP: u64 = 0x8000_0000_0000_0000;

  // magic numbers for bit interleaving
  const MAGIC: [u128; 7] = [
    0x5555555555555555_5555555555555555,
    0x3333333333333333_3333333333333333,
    0x0F0F0F0F0F0F0F0F_0F0F0F0F0F0F0F0F,
    0x00FF00FF00FF00FF_00FF00FF00FF00FF,
    0x0000FFFF0000FFFF_0000FFFF0000FFFF,
    0x00000000FFFFFFFF_00000000FFFFFFFF,
    0x0000000000000000_FFFFFFFFFFFFFFFF,
  ];

  // shift values for bit interleaving
  const SHIFT: [u16; 6] = [1, 2, 4, 8, 16, 32];

  fn encode(x: i64, y: i64) -> u128 {
    interleave_bits(x as u64 ^ SIGN_BIT_FLIP, y as u64 ^ SIGN_BIT_FLIP)
  }

  // https://github.com/Diffblue-benchmarks/Apache-lucene-solr/blob/master/lucene/core/src/java/org/apache/lucene/util/BitUtil.java#L22
  fn interleave_bits(even: u64, odd: u64) -> u128 {
    let mut v1: u128 = even as u128;
    let mut v2: u128 = odd as u128;
    v1 = (v1 | (v1 << SHIFT[5])) & MAGIC[5];
    v1 = (v1 | (v1 << SHIFT[4])) & MAGIC[4];
    v1 = (v1 | (v1 << SHIFT[3])) & MAGIC[3];
    v1 = (v1 | (v1 << SHIFT[2])) & MAGIC[2];
    v1 = (v1 | (v1 << SHIFT[1])) & MAGIC[1];
    v1 = (v1 | (v1 << SHIFT[0])) & MAGIC[0];
    v2 = (v2 | (v2 << SHIFT[5])) & MAGIC[5];
    v2 = (v2 | (v2 << SHIFT[4])) & MAGIC[4];
    v2 = (v2 | (v2 << SHIFT[3])) & MAGIC[3];
    v2 = (v2 | (v2 << SHIFT[2])) & MAGIC[2];
    v2 = (v2 | (v2 << SHIFT[1])) & MAGIC[1];
    v2 = (v2 | (v2 << SHIFT[0])) & MAGIC[0];

    return (v2 << 1) | v1;
  }

  fn deinterleave_bits(mut b: u128) -> u64 {
    b &= MAGIC[0];
    for i in 0..SHIFT.len() {
      b = (b ^ (b >> SHIFT[i])) & MAGIC[i + 1];
    }
    return b as u64;
  }

  fn decode(hash: u128) -> (i64, i64) {
    let x = deinterleave_bits(hash) ^ SIGN_BIT_FLIP;
    let y = deinterleave_bits(hash >> 1) ^ SIGN_BIT_FLIP;
    (x as i64, y as i64)
  }
}

mod bit_util_u32 {

  const SIGN_BIT_FLIP: u32 = 0x8000_0000;

  // magic numbers for bit interleaving
  const MAGIC: [u64; 6] = [
    0x5555555555555555,
    0x3333333333333333,
    0x0F0F0F0F0F0F0F0F,
    0x00FF00FF00FF00FF,
    0x0000FFFF0000FFFF,
    0x00000000FFFFFFFF,
  ];
  // shift values for bit interleaving
  const SHIFT: [u16; 5] = [1, 2, 4, 8, 16];

  fn encode(x: i32, y: i32) -> u64 {
    interleave_bits(x as u32 ^ SIGN_BIT_FLIP, y as u32 ^ SIGN_BIT_FLIP)
  }

  // https://github.com/Diffblue-benchmarks/Apache-lucene-solr/blob/master/lucene/core/src/java/org/apache/lucene/util/BitUtil.java#L22
  fn interleave_bits(even: u32, odd: u32) -> u64 {
    let mut v1: u64 = even as u64;
    let mut v2: u64 = odd as u64;
    v1 = (v1 | (v1 << SHIFT[4])) & MAGIC[4];
    v1 = (v1 | (v1 << SHIFT[3])) & MAGIC[3];
    v1 = (v1 | (v1 << SHIFT[2])) & MAGIC[2];
    v1 = (v1 | (v1 << SHIFT[1])) & MAGIC[1];
    v1 = (v1 | (v1 << SHIFT[0])) & MAGIC[0];
    v2 = (v2 | (v2 << SHIFT[4])) & MAGIC[4];
    v2 = (v2 | (v2 << SHIFT[3])) & MAGIC[3];
    v2 = (v2 | (v2 << SHIFT[2])) & MAGIC[2];
    v2 = (v2 | (v2 << SHIFT[1])) & MAGIC[1];
    v2 = (v2 | (v2 << SHIFT[0])) & MAGIC[0];

    return (v2 << 1) | v1;
  }

  fn deinterleave_bits(mut b: u64) -> u32 {
    b &= MAGIC[0];
    for i in 0..5 {
      b = (b ^ (b >> SHIFT[i])) & MAGIC[i + 1];
    }
    return b as u32;
  }

  fn decode(hash: u64) -> (i32, i32) {
    let x = deinterleave_bits(hash) ^ SIGN_BIT_FLIP;
    let y = deinterleave_bits(hash >> 1) ^ SIGN_BIT_FLIP;
    (x as i32, y as i32)
  }
}