morton_transcoding 0.1.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 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
///
/// # Safety
/// panics in debug mode if any coordinate in coords is > `max_index_size::<D>()`
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
}

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

/// 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))
}

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() {
        // `max_input_size` should be encodeable
        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));

        // 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 {
                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));
                    }
                }
            }
        }
    }
}