Skip to content

Instantly share code, notes, and snippets.

@Swoorup
Created May 28, 2024 11:31
Show Gist options
  • Save Swoorup/6fce2daf20385181e5dd4d674d9ae374 to your computer and use it in GitHub Desktop.
Save Swoorup/6fce2daf20385181e5dd4d674d9ae374 to your computer and use it in GitHub Desktop.
64-bit, 128-bit bit interleaved with (+/-) axis.
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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment