#![no_std]
pub const fn checked_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 fn encode<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>(x: usize) -> [usize; D] {
debug_assert!(D > 1);
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))
}
pub const fn max_encoded_size<const D: usize>() -> usize {
usize::MAX >> (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;
fn test_roundtrip<const D: usize>(coord: [usize; D]) {
assert_eq!(coord, decode::<D>(encode(coord)));
}
fn test_max<const C: usize>() {
test_roundtrip([max_index_size::<C>(); C]);
assert_eq!(max_encoded_size::<C>(), encode([max_index_size::<C>(); C]));
}
#[test]
fn test_max_input_size() {
test_max::<2>();
test_max::<3>();
test_max::<4>();
test_max::<5>();
test_max::<6>();
test_max::<7>();
test_max::<8>();
test_max::<9>();
test_max::<10>();
test_max::<11>();
test_max::<12>();
test_max::<13>();
test_max::<14>();
test_max::<15>();
test_max::<16>(); }
#[test]
fn test_encode_too_large() {
assert_eq!(None, checked_encode([max_index_size::<2>() + 1; 2]));
assert_eq!(None, checked_encode([max_index_size::<3>() + 1; 3]));
assert_eq!(None, checked_encode([max_index_size::<4>() + 1; 4]));
assert_eq!(None, checked_encode([max_index_size::<5>() + 1; 5]));
assert_eq!(None, checked_encode([max_index_size::<6>() + 1; 6]));
assert_eq!(None, checked_encode([max_index_size::<7>() + 1; 7]));
assert_eq!(None, checked_encode([max_index_size::<8>() + 1; 8]));
assert_eq!(None, checked_encode([max_index_size::<9>() + 1; 9]));
assert_eq!(None, checked_encode([max_index_size::<10>() + 1; 10]));
assert_eq!(None, checked_encode([max_index_size::<11>() + 1; 11]));
assert_eq!(None, checked_encode([max_index_size::<12>() + 1; 12]));
assert_eq!(None, checked_encode([max_index_size::<13>() + 1; 13]));
assert_eq!(None, checked_encode([max_index_size::<14>() + 1; 14]));
assert_eq!(None, checked_encode([max_index_size::<15>() + 1; 15]));
assert_eq!(None, checked_encode([max_index_size::<16>() + 1; 16])); }
#[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 {
test_roundtrip([x, y]);
}
}
for x in 0..32 {
for y in 0..32 {
for z in 0..32 {
test_roundtrip([x, y, z]);
}
}
}
for x in 0..16 {
for y in 0..16 {
for z in 0..16 {
for w in 0..16 {
test_roundtrip([x, y, z, w]);
}
}
}
}
}
#[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 encode_large_idx() {
assert_eq!(None, checked_encode([0xFFFFFFF, 10, 10, 10, 10, 10]));
}
#[test]
fn encode_1d() {
for i in 0..1000 {
assert_eq!(Some(i), checked_encode([i]));
}
}
#[test]
fn encode_2d() {
assert_eq!(0, encode([0, 0]));
assert_eq!(1, encode([1, 0]));
assert_eq!(2, encode([0, 1]));
assert_eq!(3, encode([1, 1]));
assert_eq!(4, encode([2, 0]));
assert_eq!(5, encode([3, 0]));
assert_eq!(6, encode([2, 1]));
assert_eq!(7, encode([3, 1]));
assert_eq!(8, encode([0, 2]));
assert_eq!(9, encode([1, 2]));
assert_eq!(10, encode([0, 3]));
assert_eq!(11, encode([1, 3]));
assert_eq!(12, encode([2, 2]));
assert_eq!(13, encode([3, 2]));
assert_eq!(14, encode([2, 3]));
assert_eq!(15, encode([3, 3]));
}
#[test]
fn encode_3d() {
assert_eq!(0, encode([0, 0, 0]));
assert_eq!(1, encode([1, 0, 0]));
assert_eq!(2, encode([0, 1, 0]));
assert_eq!(4, encode([0, 0, 1]));
assert_eq!(3, encode([1, 1, 0]));
assert_eq!(5, encode([1, 0, 1]));
assert_eq!(6, encode([0, 1, 1]));
assert_eq!(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!(expected, encode(coords));
}
}
}
}
}
#[test]
fn exampled_that_broke_my_code_at_one_point() {
let point = [4, 7, 5, 65534];
assert_eq!(point, decode::<4>(checked_encode(point).unwrap()));
}
}
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeDoctests;