ps_pint16/

lib.rs

//! Packs unsigned integers into a `u16` via variable precision.
//!
//! A [`PackedInt`] keeps nine significant bits and a scale, so any value up to
//! `511 × 2²⁵⁴` fits in two bytes. Packing is lossy above 255: the value is
//! rounded **up** to the nearest representable one, never by more than one part
//! in 256.
//!
//! ```
//! use ps_pint16::PackedInt;
//!
//! // Values below 256 survive exactly.
//! assert_eq!(PackedInt::from_u64(255).to_u64(), 255);
//!
//! // Larger ones round up to the nearest representable value.
//! assert_eq!(PackedInt::from_u64(1_000_000).to_u64(), 1_001_472);
//!
//! // Two bytes, whatever the width of the input.
//! assert_eq!(core::mem::size_of::<PackedInt>(), 2);
//! ```
//!
//! # Encoding
//!
//! The high byte of the representation is an exponent `e`, the low byte a
//! mantissa `m`:
//!
//! | exponent | value       | range                | step    |
//! |----------|-------------|----------------------|---------|
//! | `0`      | `m`         | `0 ..= 255`          | `1`     |
//! | `e ≥ 1`  | `2ᵉ⁺⁷ + m × 2ᵉ⁻¹` | `2ᵉ⁺⁷ ..= 511 × 2ᵉ⁻¹` | `2ᵉ⁻¹` |
//!
//! Consecutive exponents meet exactly one step apart, so the 65 536
//! representations form a strictly increasing sequence with no gaps and no
//! duplicates. Two consequences follow:
//!
//! * Every `u16` is a valid [`PackedInt`], so [`from_inner_u16`] cannot fail.
//! * The derived [`Ord`] agrees with the order of the values represented, so
//!   packed integers can be sorted and compared without unpacking.
//!
//! # Rounding and saturation
//!
//! Packing rounds up, so unpacking never returns less than was packed. When a
//! packed value exceeds the target type, unpacking saturates at that type's
//! maximum instead of wrapping. Both directions are total: no input panics.
//!
//! [`from_inner_u16`]: PackedInt::from_inner_u16
#![cfg_attr(not(test), no_std)]
#![deny(missing_docs)]

/// Runs the examples in `README.md` as doctests. Not part of the public API.
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct Readme;

/// An unsigned integer packed into 16 bits with variable precision.
///
/// See the [crate-level documentation](crate) for the encoding, the rounding
/// behaviour, and the ordering guarantee.
#[repr(transparent)]
#[derive(Clone, Copy, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct PackedInt {
    inner: u16,
}

macro_rules! impl_from_type {
    ($type:ty, $name:ident) => {
        #[doc = concat!("Packs a [`", stringify!($type), "`], rounding up.")]
        ///
        /// Returns the smallest representable value greater than or equal to
        /// `value`, which is `value` itself whenever it is below 256.
        pub const fn $name(mut value: $type) -> Self {
            let mut prefix = 0u16;

            // Halve, rounding up, until the value fits in nine bits. Written
            // this way rather than as `(value + 1) >> 1` so that `<$type>::MAX`
            // does not overflow.
            while value > 0x1ff {
                prefix += 1;
                value = (value >> 1) + (value & 1);
            }

            // The ninth bit of a normalized value is always set, so it carries
            // into the exponent and need not be stored.
            Self {
                inner: (prefix << 8) + (value as u16),
            }
        }
    };
}

macro_rules! impl_into_type {
    ($type:ty, $name:ident) => {
        #[doc = concat!("Unpacks into a [`", stringify!($type), "`], saturating at [`", stringify!($type), "::MAX`].")]
        ///
        /// Values that do not fit in the target type saturate rather than wrap.
        pub const fn $name(self) -> $type {
            let prefix = (self.inner >> 8) as $type;
            let suffix = (self.inner & 0xff) as $type;

            if prefix == 0 {
                suffix
            } else if 7 + prefix >= <$type>::BITS as $type {
                <$type>::MAX
            } else {
                (1 << (7 + prefix)) | (suffix << (prefix - 1))
            }
        }
    };
}

macro_rules! impl_traits {
    ($type:ty, $from:ident, $into:ident) => {
        impl From<$type> for PackedInt {
            fn from(value: $type) -> Self {
                Self::$from(value)
            }
        }

        impl From<PackedInt> for $type {
            fn from(packed: PackedInt) -> $type {
                packed.$into()
            }
        }
    };
}

impl PackedInt {
    /// Reads a packed value from 12 bits: all of `bits[0]`, and the high
    /// nibble of `bits[1]`.
    ///
    /// The low nibble of `bits[1]` is reserved for the caller and is ignored.
    pub const fn from_12_bits(bits: &[u8; 2]) -> Self {
        Self {
            inner: (((bits[1] & 0xf0) as u16) << 4) | (bits[0] as u16),
        }
    }

    /// Writes the packed value into 12 bits: all of `bits[0]`, and the high
    /// nibble of `bits[1]`.
    ///
    /// The low nibble of `bits[1]` is left zero for the caller to use.
    ///
    /// Twelve bits hold only the low nibble of the exponent, so this is
    /// lossless for values up to `511 × 2¹⁴` (8 372 224) and no further.
    /// Beyond that the exponent is truncated and the value reads back as an
    /// unrelated number.
    pub const fn to_12_bits(self) -> [u8; 2] {
        [self.inner as u8, 0xF0 & (self.inner >> 4) as u8]
    }

    /// Reads a packed value from two little-endian bytes.
    pub const fn from_16_bits(bits: &[u8; 2]) -> Self {
        Self {
            inner: u16::from_le_bytes(*bits),
        }
    }

    /// Writes the packed value as two little-endian bytes.
    pub const fn to_16_bits(self) -> [u8; 2] {
        self.inner.to_le_bytes()
    }

    /// Reinterprets a `u16` as a packed value.
    ///
    /// Every `u16` is a valid representation, so this cannot fail. It is the
    /// inverse of [`to_inner_u16`](Self::to_inner_u16).
    pub const fn from_inner_u16(inner: u16) -> Self {
        Self { inner }
    }

    /// Returns the underlying representation.
    pub const fn to_inner_u16(self) -> u16 {
        self.inner
    }

    impl_from_type!(usize, from_usize);
    impl_from_type!(u128, from_u128);
    impl_from_type!(u64, from_u64);
    impl_from_type!(u32, from_u32);
    impl_from_type!(u16, from_u16);

    impl_into_type!(usize, to_usize);
    impl_into_type!(u128, to_u128);
    impl_into_type!(u64, to_u64);
    impl_into_type!(u32, to_u32);
    impl_into_type!(u16, to_u16);
}

impl_traits!(usize, from_usize, to_usize);
impl_traits!(u128, from_u128, to_u128);
impl_traits!(u64, from_u64, to_u64);
impl_traits!(u32, from_u32, to_u32);

#[cfg(test)]
mod tests {
    use crate::PackedInt;

    /// The first representation whose value exceeds [`u128::MAX`].
    const U128_SATURATION: u16 = 0x7900;

    /// Independent implementation of the encoding documented at the crate
    /// root, against which the crate's own arithmetic is checked.
    ///
    /// Returns [`None`] if the represented value exceeds [`u128::MAX`].
    fn reference_value(inner: u16) -> Option<u128> {
        let exponent = u32::from(inner >> 8);
        let mantissa = u128::from(inner & 0xff);

        if exponent == 0 {
            return Some(mantissa);
        }

        if exponent + 7 >= u128::BITS {
            return None;
        }

        Some((1 << (exponent + 7)) + (mantissa << (exponent - 1)))
    }

    macro_rules! assert_unpacks_or_saturates {
        ($packed:expr, $expected:expr, $type:ty, $to:ident) => {
            let actual = $packed.$to();

            match $expected {
                Some(value) if value <= <$type>::MAX as u128 => assert_eq!(
                    actual as u128, value,
                    concat!(stringify!($to), " of {:?} should be {}"),
                    $packed, value
                ),
                _ => assert_eq!(
                    actual,
                    <$type>::MAX,
                    concat!(stringify!($to), " of {:?} should saturate"),
                    $packed
                ),
            }
        };
    }

    #[test]
    fn every_representation_decodes_per_the_specification() {
        for inner in 0..=u16::MAX {
            let packed = PackedInt::from_inner_u16(inner);
            let expected = reference_value(inner);

            assert_unpacks_or_saturates!(packed, expected, u16, to_u16);
            assert_unpacks_or_saturates!(packed, expected, u32, to_u32);
            assert_unpacks_or_saturates!(packed, expected, u64, to_u64);
            assert_unpacks_or_saturates!(packed, expected, usize, to_usize);

            assert_eq!(packed.to_u128(), expected.unwrap_or(u128::MAX));
        }
    }

    #[test]
    fn values_increase_strictly_and_without_gaps() {
        for inner in 0..U128_SATURATION - 1 {
            let lower = reference_value(inner).expect("below the saturation point");
            let upper = reference_value(inner + 1).expect("below the saturation point");

            let exponent = u32::from(inner >> 8);
            let step = 1u128 << exponent.saturating_sub(1);

            assert_eq!(
                upper - lower,
                step,
                "{inner:#06x} and its successor are not one step apart"
            );

            assert!(
                PackedInt::from_inner_u16(inner) < PackedInt::from_inner_u16(inner + 1),
                "Ord disagrees with the value order at {inner:#06x}"
            );
        }
    }

    #[test]
    fn packing_returns_the_least_representable_upper_bound() {
        assert_eq!(PackedInt::from_u128(0).to_inner_u16(), 0);

        for inner in 1..U128_SATURATION {
            let value = reference_value(inner).expect("below the saturation point");
            let previous = reference_value(inner - 1).expect("below the saturation point");

            assert_eq!(
                PackedInt::from_u128(value).to_inner_u16(),
                inner,
                "{value} is representable and should pack to {inner:#06x}"
            );

            assert_eq!(
                PackedInt::from_u128(previous + 1).to_inner_u16(),
                inner,
                "{} should round up to {inner:#06x}",
                previous + 1
            );
        }
    }

    #[test]
    fn packing_is_exact_below_256_and_rounds_up_above() {
        for value in 0..256u128 {
            assert_eq!(PackedInt::from_u128(value).to_u128(), value);
        }

        for inner in 1..U128_SATURATION {
            let representable = reference_value(inner).expect("below the saturation point");

            for value in [representable - 1, representable] {
                let rounded = PackedInt::from_u128(value).to_u128();

                assert!(rounded >= value, "{value} rounded down to {rounded}");

                assert!(
                    rounded - value <= value >> 8,
                    "{value} rounded to {rounded}, further than one part in 256"
                );
            }
        }
    }

    #[test]
    fn packing_is_independent_of_the_input_width() {
        for value in 0..=u16::MAX {
            let packed = PackedInt::from_u16(value);

            assert_eq!(PackedInt::from_u32(u32::from(value)), packed);
            assert_eq!(PackedInt::from_u64(u64::from(value)), packed);
            assert_eq!(PackedInt::from_u128(u128::from(value)), packed);
            assert_eq!(PackedInt::from_usize(usize::from(value)), packed);
        }
    }

    #[test]
    fn packing_the_type_maximum_round_trips() {
        assert_eq!(PackedInt::from_u16(u16::MAX).to_u16(), u16::MAX);
        assert_eq!(PackedInt::from_u32(u32::MAX).to_u32(), u32::MAX);
        assert_eq!(PackedInt::from_u64(u64::MAX).to_u64(), u64::MAX);
        assert_eq!(PackedInt::from_u128(u128::MAX).to_u128(), u128::MAX);
        assert_eq!(PackedInt::from_usize(usize::MAX).to_usize(), usize::MAX);
    }

    #[test]
    fn powers_of_two_survive_packing() {
        for shift in 0..u128::BITS {
            let value = 1u128 << shift;

            assert_eq!(PackedInt::from_u128(value).to_u128(), value);
        }
    }

    #[test]
    fn sixteen_bit_round_trip_is_lossless() {
        for inner in 0..=u16::MAX {
            let packed = PackedInt::from_inner_u16(inner);

            assert_eq!(PackedInt::from_16_bits(&packed.to_16_bits()), packed);
        }
    }

    #[test]
    fn twelve_bit_round_trip_ignores_the_reserved_nibble() {
        for inner in 0..0x1000 {
            let packed = PackedInt::from_inner_u16(inner);
            let bits = packed.to_12_bits();

            assert_eq!(bits[1] & 0x0f, 0, "{inner:#06x} wrote the reserved nibble");

            for reserved in 0..0x10 {
                let dirty = [bits[0], bits[1] | reserved];

                assert_eq!(
                    PackedInt::from_12_bits(&dirty),
                    packed,
                    "{inner:#06x} was corrupted by reserved nibble {reserved:#03x}"
                );
            }
        }
    }

    #[test]
    fn twelve_bits_hold_values_up_to_the_documented_bound() {
        let largest = PackedInt::from_inner_u16(0x0fff);

        assert_eq!(largest.to_u128(), 511 * (1 << 14));
        assert_eq!(largest.to_u128(), 8_372_224);
        assert_eq!(PackedInt::from_12_bits(&largest.to_12_bits()), largest);
    }

    #[test]
    fn conversions_are_usable_in_const_context() {
        const PACKED: PackedInt = PackedInt::from_u64(1_000_000);
        const UNPACKED: u64 = PACKED.to_u64();
        const BYTES: [u8; 2] = PACKED.to_16_bits();

        assert_eq!(UNPACKED, 1_001_472);
        assert_eq!(PackedInt::from_16_bits(&BYTES), PACKED);
    }

    #[test]
    fn from_impls_agree_with_the_inherent_methods() {
        for shift in 0..u128::BITS {
            let value = 1u128 << shift;
            let packed = PackedInt::from(value);

            assert_eq!(packed, PackedInt::from_u128(value));
            assert_eq!(u128::from(packed), packed.to_u128());
            assert_eq!(u64::from(packed), packed.to_u64());
            assert_eq!(u32::from(packed), packed.to_u32());
            assert_eq!(usize::from(packed), packed.to_usize());
        }
    }
}