Created
May 28, 2024 11:31
-
-
Save Swoorup/6fce2daf20385181e5dd4d674d9ae374 to your computer and use it in GitHub Desktop.
64-bit, 128-bit bit interleaved with (+/-) axis.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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