#![no_std]
pub const fn encode<const D: usize>(coords: [usize; D]) -> Option<usize> {
let limit = max_index_size::<D>();
let mut i = 0;
let mut result = 0;
while i < D {
if coords[i] > limit {
return None;
}
result |= expand_bits::<D>(coords[i]) << i;
i += 1;
}
Some(result)
}
pub const unsafe fn encode_unchecked<const D: usize>(coords: [usize; D]) -> usize {
let mut i = 0;
let mut result = 0;
while i < D {
result |= expand_bits::<D>(coords[i]) << i;
i += 1;
}
result
}
pub const fn decode<const D: usize>(mut x: usize) -> [usize; D] {
x &= max_index_size::<D>();
let mut arr = [0; D];
let mut i = 0;
while i < D {
arr[i] = contract_bits::<D>(x >> i);
i += 1;
}
arr
}
pub const fn max_index_size<const D: usize>() -> usize {
debug_assert!(D > 0 && D <= usize::BITS as usize);
usize::MAX >> (usize::BITS - (usize::BITS / D as u32))
}
const fn expand_bits<const D: usize>(mut x: usize) -> usize {
debug_assert!(
x <= max_index_size::<D>(),
"Attempting to encode value that is too large! Check `max_index_size`",
);
x &= max_index_size::<D>();
let mut i = usize::BITS.ilog2() as usize - 1;
while i > 0 {
let shift = (1 << (i - 1)) * (D - 1);
let shifted_x = x.unbounded_shl(shift as u32);
let mask = magic_bits(i, D);
x = (x | shifted_x) & mask;
i -= 1;
}
x
}
const fn contract_bits<const D: usize>(mut x: usize) -> usize {
let mut i = 1;
x &= magic_bits(1, D);
while i < usize::BITS.ilog2() as usize {
let shift = (1 << (i - 1)) * (D - 1);
let shifted_x = x.unbounded_shr(shift as u32);
let mask = magic_bits(i + 1, D);
x = (x ^ shifted_x) & mask;
i += 1;
}
x
}
const fn magic_bits(level: usize, dimension: usize) -> usize {
let mut result = 0;
let divisor: usize = 1 << (level - 1);
let mut i = 0;
while i < usize::BITS as usize {
if (i / divisor).is_multiple_of(dimension) {
result |= 1 << i;
}
i += 1;
}
result
}
#[cfg(test)]
mod test {
use super::*;
extern crate std;
#[test]
fn test_max_input_size() {
assert_eq!(
Some(usize::MAX),
encode([max_index_size::<2>(), max_index_size::<2>()])
);
}
#[test]
fn test_contract() {
assert_eq!(0b0, contract_bits::<2>(0b0));
assert_eq!(0b1, contract_bits::<2>(0b1));
assert_eq!(0b101, contract_bits::<2>(0b10001));
assert_eq!(0b111, contract_bits::<2>(0b10101));
assert_eq!(0b0, contract_bits::<3>(0b0));
assert_eq!(0b1, contract_bits::<3>(0b1));
assert_eq!(0b111, contract_bits::<3>(0b1001001));
assert_eq!(0b0, contract_bits::<2>(0b10));
assert_eq!(0b0, contract_bits::<2>(0b101010));
assert_eq!(0b0, contract_bits::<3>(0b110));
assert_eq!(0b0, contract_bits::<3>(0b110110110));
}
#[test]
fn test_encode_decode_reversibility() {
for x in 0..64 {
for y in 0..64 {
assert_eq!([x, y], decode::<2>(encode([x, y]).unwrap()));
}
}
for x in 0..32 {
for y in 0..32 {
for z in 0..32 {
assert_eq!([x, y, z], decode::<3>(encode([x, y, z]).unwrap()));
}
}
}
for x in 0..16 {
for y in 0..16 {
for z in 0..16 {
for w in 0..16 {
assert_eq!([x, y, z, w], decode::<4>(encode([x, y, z, w]).unwrap()));
}
}
}
}
}
#[test]
fn test_expansion_contraction_reversiblity() {
for i in 0..256 {
assert_eq!(i, contract_bits::<2>(expand_bits::<2>(i)));
}
for i in 0..256 {
assert_eq!(i, contract_bits::<3>(expand_bits::<3>(i)));
}
for i in 0..256 {
assert_eq!(i, contract_bits::<4>(expand_bits::<4>(i)));
}
for i in 0..=max_index_size::<5>() {
assert_eq!(i, contract_bits::<5>(expand_bits::<5>(i)));
}
}
#[test]
fn test_encode_unsafe() {
for x in 0..64 {
for y in 0..64 {
assert_eq!(encode([x, y]).unwrap(), unsafe { encode_unchecked([x, y]) });
}
}
}
#[test]
fn encode_large_idx() {
assert_eq!(None, encode([0xFFFFFFF, 10, 10, 10, 10, 10]));
}
#[test]
fn encode_1d() {
for i in 0..1000 {
assert_eq!(Some(i), encode([i]));
}
}
#[test]
fn encode_2d() {
assert_eq!(Some(0), encode([0, 0]));
assert_eq!(Some(1), encode([1, 0]));
assert_eq!(Some(2), encode([0, 1]));
assert_eq!(Some(3), encode([1, 1]));
assert_eq!(Some(4), encode([2, 0]));
assert_eq!(Some(5), encode([3, 0]));
assert_eq!(Some(6), encode([2, 1]));
assert_eq!(Some(7), encode([3, 1]));
assert_eq!(Some(8), encode([0, 2]));
assert_eq!(Some(9), encode([1, 2]));
assert_eq!(Some(10), encode([0, 3]));
assert_eq!(Some(11), encode([1, 3]));
assert_eq!(Some(12), encode([2, 2]));
assert_eq!(Some(13), encode([3, 2]));
assert_eq!(Some(14), encode([2, 3]));
assert_eq!(Some(15), encode([3, 3]));
}
#[test]
fn encode_3d() {
assert_eq!(Some(0), encode([0, 0, 0]));
assert_eq!(Some(1), encode([1, 0, 0]));
assert_eq!(Some(2), encode([0, 1, 0]));
assert_eq!(Some(4), encode([0, 0, 1]));
assert_eq!(Some(3), encode([1, 1, 0]));
assert_eq!(Some(5), encode([1, 0, 1]));
assert_eq!(Some(6), encode([0, 1, 1]));
assert_eq!(Some(7), encode([1, 1, 1]));
}
#[test]
fn encode_4d() {
for x in 0..=1 {
for y in 0..=1 {
for z in 0..=1 {
for w in 0..=1 {
let coords = [x, y, z, w];
let expected = x | (y << 1) | (z << 2) | (w << 3);
assert_eq!(Some(expected), encode(coords));
}
}
}
}
}
}