morton_transcoding 0.2.0

N-Dimensional `const` and `no_std` Morton encoding and decoding for `usize`
Documentation
#![no_std]

/// Encodes a D-Dimensional morton code
/// returns `None` if any coordinate is too large to encode in a `usize`. See `max_index_size`
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)
}

/// Encodes a D-Dimensional morton code.
/// Bits may truncate if too large to encode in a `usize`. Use `checked_encode` or `max_index_size` to check for truncation.
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
}

/// Converts a morton code to a D-Dimensional coordinate
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
}

/// The largest size a single dimension can be without truncating bits
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))
}

/// The largest size an encoded value can be, when created from coordinates less than `max_index_size`
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>() {
        // Does it convert back and forth?
        test_roundtrip([max_index_size::<C>(); C]);

        // Does it encode to the expected value?
        assert_eq!(max_encoded_size::<C>(), encode([max_index_size::<C>(); C]));
    }

    #[test]
    fn test_max_input_size() {
        // `max_input_size` should be encodeable

        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>(); // usize is only guarenteed to be 16 bits wide
    }

    #[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])); // usize is only guarenteed to be 16 bits wide
    }

    #[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));

        // Other bits should be ignored
        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;