zerotrie 0.2.4

// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).

//! Varint spec for [`ZeroTrie`](crate::ZeroTrie):
//!
//! - Lead byte: top M (2 or 3) bits are metadata; next is varint extender; rest is value
//! - Trail bytes: top bit is varint extender; rest are low bits of value
//! - Guaranteed uniqueness of varint by adding "latent value" for each extender byte
//! - No maximum, but high bits will be dropped if they don't fit in the platform's `usize`
//!
//! This is best shown by examples.
//!
//! ```txt
//! xxx0'1010 = 10
//! xxx0'1111 = 15 (largest single-byte value with M=3)
//! xxx1'0000 0000'0000 must be 16 (smallest two-byte value with M=3)
//! xxx1'0000 0000'0001 = 17
//! xxx1'1111 0111'1111 = 2063 (largest two-byte value with M=3)
//! xxx1'0000 1000'0000 0000'0000 must be 2064 (smallest three-byte value with M=3)
//! xxx1'0000 1000'0000 0000'0001 = 2065
//! ```
//!
//! The latent values by number of bytes for M=3 are:
//!
//! - 1 byte: 0
//! - 2 bytes: 16 = 0x10 = 0b10000
//! - 3 bytes: 2064 = 0x810 = 0b100000010000
//! - 4 bytes: 264208 = 0x40810 = 0b1000000100000010000
//! - 5 bytes: 33818640 = 0x2040810 = 0b10000001000000100000010000
//! - …
//!
//! For M=2, the latent values are:
//!
//! - 1 byte: 0
//! - 2 bytes: 32 = 0x20 = 0b100000
//! - 3 bytes: 4128 = 0x1020 = 0b1000000100000
//! - 4 bytes: 524320 = 0x81020 = 0b10000001000000100000
//! - 5 bytes: 67637280 = 0x4081020 = 0b100000010000001000000100000
//! - …

use crate::builder::konst::ConstArrayBuilder;

#[cfg(feature = "alloc")]
use crate::builder::nonconst::TrieBuilderStore;

/// Reads a varint with 2 bits of metadata in the lead byte.
///
/// Returns the varint value and a subslice of `remainder` with the varint bytes removed.
///
/// If the varint spills off the end of the slice, a debug assertion will fail,
/// and the function will return the value up to that point.
pub const fn read_varint_meta2(start: u8, remainder: &[u8]) -> (usize, &[u8]) {
    let mut value = (start & 0b00011111) as usize;
    let mut remainder = remainder;
    if (start & 0b00100000) != 0 {
        loop {
            let next;
            (next, remainder) = debug_unwrap!(remainder.split_first(), break, "invalid varint");
            // Note: value << 7 could drop high bits. The first addition can't overflow.
            // The second addition could overflow; in such a case we just inform the
            // developer via the debug assertion.
            value = (value << 7) + ((*next & 0b01111111) as usize) + 32;
            if (*next & 0b10000000) == 0 {
                break;
            }
        }
    }
    (value, remainder)
}

/// Reads a varint with 3 bits of metadata in the lead byte.
///
/// Returns the varint value and a subslice of `remainder` with the varint bytes removed.
///
/// If the varint spills off the end of the slice, a debug assertion will fail,
/// and the function will return the value up to that point.
pub const fn read_varint_meta3(start: u8, remainder: &[u8]) -> (usize, &[u8]) {
    let mut value = (start & 0b00001111) as usize;
    let mut remainder = remainder;
    if (start & 0b00010000) != 0 {
        loop {
            let next;
            (next, remainder) = debug_unwrap!(remainder.split_first(), break, "invalid varint");
            // Note: value << 7 could drop high bits. The first addition can't overflow.
            // The second addition could overflow; in such a case we just inform the
            // developer via the debug assertion.
            value = (value << 7) + ((*next & 0b01111111) as usize) + 16;
            if (*next & 0b10000000) == 0 {
                break;
            }
        }
    }
    (value, remainder)
}

/// Reads and removes a varint with 3 bits of metadata from a [`TrieBuilderStore`].
///
/// Returns the varint value.
#[cfg(feature = "alloc")]
pub(crate) fn try_read_varint_meta3_from_tstore<S: TrieBuilderStore>(
    start: u8,
    remainder: &mut S,
) -> Option<usize> {
    let mut value = (start & 0b00001111) as usize;
    if (start & 0b00010000) != 0 {
        loop {
            let next = remainder.atbs_pop_front()?;
            // Note: value << 7 could drop high bits. The first addition can't overflow.
            // The second addition could overflow; in such a case we just inform the
            // developer via the debug assertion.
            value = (value << 7) + ((next & 0b01111111) as usize) + 16;
            if (next & 0b10000000) == 0 {
                break;
            }
        }
    }
    Some(value)
}

#[cfg(test)]
const MAX_VARINT: usize = usize::MAX;

// *Upper Bound:* Each trail byte stores 7 bits of data, plus the latent value.
// Add an extra 1 since the lead byte holds only 5 bits of data.
const MAX_VARINT_LENGTH: usize = 1 + usize::BITS as usize / 7;

/// Returns a new [`ConstArrayBuilder`] containing a varint with 2 bits of metadata.
#[allow(clippy::indexing_slicing)] // Okay so long as MAX_VARINT_LENGTH is correct
pub(crate) const fn write_varint_meta2(value: usize) -> ConstArrayBuilder<MAX_VARINT_LENGTH, u8> {
    let mut result = [0; MAX_VARINT_LENGTH];
    let mut i = MAX_VARINT_LENGTH - 1;
    let mut value = value;
    let mut last = true;
    loop {
        if value < 32 {
            result[i] = value as u8;
            if !last {
                result[i] |= 0b00100000;
            }
            break;
        }
        value -= 32;
        result[i] = (value as u8) & 0b01111111;
        if !last {
            result[i] |= 0b10000000;
        } else {
            last = false;
        }
        value >>= 7;
        i -= 1;
    }
    // The bytes are from i to the end.
    ConstArrayBuilder::from_manual_slice(result, i, MAX_VARINT_LENGTH)
}

/// Returns a new [`ConstArrayBuilder`] containing a varint with 3 bits of metadata.
#[allow(clippy::indexing_slicing)] // Okay so long as MAX_VARINT_LENGTH is correct
pub(crate) const fn write_varint_meta3(value: usize) -> ConstArrayBuilder<MAX_VARINT_LENGTH, u8> {
    let mut result = [0; MAX_VARINT_LENGTH];
    let mut i = MAX_VARINT_LENGTH - 1;
    let mut value = value;
    let mut last = true;
    loop {
        if value < 16 {
            result[i] = value as u8;
            if !last {
                result[i] |= 0b00010000;
            }
            break;
        }
        value -= 16;
        result[i] = (value as u8) & 0b01111111;
        if !last {
            result[i] |= 0b10000000;
        } else {
            last = false;
        }
        value >>= 7;
        i -= 1;
    }
    // The bytes are from i to the end.
    ConstArrayBuilder::from_manual_slice(result, i, MAX_VARINT_LENGTH)
}

/// A secondary implementation that separates the latent value while computing the varint.
#[cfg(test)]
pub(crate) const fn write_varint_reference(
    value: usize,
) -> ConstArrayBuilder<MAX_VARINT_LENGTH, u8> {
    let mut result = [0; MAX_VARINT_LENGTH];
    if value < 32 {
        result[0] = value as u8;
        return ConstArrayBuilder::from_manual_slice(result, 0, 1);
    }
    result[0] = 32;
    let mut latent = 32;
    let mut steps = 2;
    loop {
        let next_latent = (latent << 7) + 32;
        if value < next_latent || next_latent == latent {
            break;
        }
        latent = next_latent;
        steps += 1;
    }
    let mut value = value - latent;
    let mut i = steps;
    while i > 0 {
        i -= 1;
        result[i] |= (value as u8) & 0b01111111;
        value >>= 7;
        if i > 0 && i < steps - 1 {
            result[i] |= 0b10000000;
        }
    }
    // The bytes are from 0 to `steps`.
    ConstArrayBuilder::from_manual_slice(result, 0, steps)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Debug)]
    struct TestCase<'a> {
        bytes: &'a [u8],
        remainder: &'a [u8],
        value: usize,
    }
    static CASES: &[TestCase] = &[
        TestCase {
            bytes: &[0b00000000],
            remainder: &[],
            value: 0,
        },
        TestCase {
            bytes: &[0b00001010],
            remainder: &[],
            value: 10,
        },
        TestCase {
            bytes: &[0b00011111],
            remainder: &[],
            value: 31,
        },
        TestCase {
            bytes: &[0b00011111, 0b10101010],
            remainder: &[0b10101010],
            value: 31,
        },
        TestCase {
            bytes: &[0b00100000, 0b00000000],
            remainder: &[],
            value: 32,
        },
        TestCase {
            bytes: &[0b00100000, 0b00000001],
            remainder: &[],
            value: 33,
        },
        TestCase {
            bytes: &[0b00100000, 0b00100000],
            remainder: &[],
            value: 64,
        },
        TestCase {
            bytes: &[0x20, 0x44],
            remainder: &[],
            value: 100,
        },
        TestCase {
            bytes: &[0b00100000, 0b01111111],
            remainder: &[],
            value: 159,
        },
        TestCase {
            bytes: &[0b00100001, 0b00000000],
            remainder: &[],
            value: 160,
        },
        TestCase {
            bytes: &[0b00100001, 0b00000001],
            remainder: &[],
            value: 161,
        },
        TestCase {
            bytes: &[0x23, 0x54],
            remainder: &[],
            value: 500,
        },
        TestCase {
            bytes: &[0b00111111, 0b01111111],
            remainder: &[],
            value: 4127, // 32 + (1 << 12) - 1
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b00000000],
            remainder: &[],
            value: 4128, // 32 + (1 << 12)
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b00000001],
            remainder: &[],
            value: 4129, // 32 + (1 << 12) + 1
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b01111111],
            remainder: &[],
            value: 4255, // 32 + (1 << 12) + 127
        },
        TestCase {
            bytes: &[0b00100000, 0b10000001, 0b00000000],
            remainder: &[],
            value: 4256, // 32 + (1 << 12) + 128
        },
        TestCase {
            bytes: &[0b00100000, 0b10000001, 0b00000001],
            remainder: &[],
            value: 4257, // 32 + (1 << 12) + 129
        },
        TestCase {
            bytes: &[0x20, 0x86, 0x68],
            remainder: &[],
            value: 5000,
        },
        TestCase {
            bytes: &[0b00100000, 0b11111111, 0b01111111],
            remainder: &[],
            value: 20511, // 32 + (1 << 12) + (1 << 14) - 1
        },
        TestCase {
            bytes: &[0b00100001, 0b10000000, 0b00000000],
            remainder: &[],
            value: 20512, // 32 + (1 << 12) + (1 << 14)
        },
        TestCase {
            bytes: &[0b00111111, 0b11111111, 0b01111111],
            remainder: &[],
            value: 528415, // 32 + (1 << 12) + (1 << 19) - 1
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b10000000, 0b00000000],
            remainder: &[],
            value: 528416, // 32 + (1 << 12) + (1 << 19)
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b10000000, 0b00000001],
            remainder: &[],
            value: 528417, // 32 + (1 << 12) + (1 << 19) + 1
        },
        TestCase {
            bytes: &[0b00111111, 0b11111111, 0b11111111, 0b01111111],
            remainder: &[],
            value: 67637279, // 32 + (1 << 12) + (1 << 19) + (1 << 26) - 1
        },
        TestCase {
            bytes: &[0b00100000, 0b10000000, 0b10000000, 0b10000000, 0b00000000],
            remainder: &[],
            value: 67637280, // 32 + (1 << 12) + (1 << 19) + (1 << 26)
        },
    ];

    #[test]
    fn test_read() {
        for cas in CASES {
            let recovered = read_varint_meta2(cas.bytes[0], &cas.bytes[1..]);
            assert_eq!(recovered, (cas.value, cas.remainder), "{cas:?}");
        }
    }

    #[test]
    fn test_read_write() {
        for cas in CASES {
            let reference_bytes = write_varint_reference(cas.value);
            assert_eq!(
                reference_bytes.len(),
                cas.bytes.len() - cas.remainder.len(),
                "{cas:?}"
            );
            assert_eq!(
                reference_bytes.as_slice(),
                &cas.bytes[0..reference_bytes.len()],
                "{cas:?}"
            );
            let recovered = read_varint_meta2(cas.bytes[0], &cas.bytes[1..]);
            assert_eq!(recovered, (cas.value, cas.remainder), "{cas:?}");
            let write_bytes = write_varint_meta2(cas.value);
            assert_eq!(
                reference_bytes.as_slice(),
                write_bytes.as_slice(),
                "{cas:?}"
            );
        }
    }

    #[test]
    fn test_roundtrip() {
        let mut i = 0usize;
        while i < MAX_VARINT {
            let bytes = write_varint_meta2(i);
            let recovered = read_varint_meta2(bytes.as_slice()[0], &bytes.as_slice()[1..]);
            assert_eq!(i, recovered.0, "{:?}", bytes.as_slice());
            i <<= 1;
            i += 1;
        }
    }

    #[test]
    fn test_extended_roundtrip() {
        let mut i = 0usize;
        while i < MAX_VARINT {
            let bytes = write_varint_meta3(i);
            let recovered = read_varint_meta3(bytes.as_slice()[0], &bytes.as_slice()[1..]);
            assert_eq!(i, recovered.0, "{:?}", bytes.as_slice());
            i <<= 1;
            i += 1;
        }
    }

    #[test]
    fn test_max() {
        let reference_bytes = write_varint_reference(MAX_VARINT);
        let write_bytes = write_varint_meta2(MAX_VARINT);
        assert_eq!(reference_bytes.len(), MAX_VARINT_LENGTH);
        assert_eq!(reference_bytes.as_slice(), write_bytes.as_slice());
        let subarray = write_bytes
            .as_const_slice()
            .get_subslice_or_panic(1, write_bytes.len());
        let (recovered_value, remainder) = read_varint_meta2(
            *write_bytes.as_const_slice().first().unwrap(),
            subarray.as_slice(),
        );
        assert!(remainder.is_empty());
        assert_eq!(recovered_value, MAX_VARINT);
        #[cfg(target_pointer_width = "64")]
        assert_eq!(
            write_bytes.as_slice(),
            &[
                0b00100001, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b01011111, //
            ]
        );
        #[cfg(target_pointer_width = "32")]
        assert_eq!(
            write_bytes.as_slice(),
            &[
                0b00101111, //
                0b11011111, //
                0b11011111, //
                0b11011111, //
                0b01011111, //
            ]
        );
    }

    #[test]
    fn text_extended_max() {
        let write_bytes = write_varint_meta3(MAX_VARINT);
        assert_eq!(write_bytes.len(), MAX_VARINT_LENGTH);
        let (lead, trailing) = write_bytes.as_slice().split_first().unwrap();
        let (recovered_value, remainder) = read_varint_meta3(*lead, trailing);
        assert!(remainder.is_empty());
        assert_eq!(recovered_value, MAX_VARINT);
        #[cfg(target_pointer_width = "64")]
        assert_eq!(
            write_bytes.as_slice(),
            &[
                0b00010001, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b01101111, //
            ]
        );
        #[cfg(target_pointer_width = "32")]
        assert_eq!(
            write_bytes.as_slice(),
            &[
                0b00011111, //
                0b11101111, //
                0b11101111, //
                0b11101111, //
                0b01101111, //
            ]
        );
    }

    #[test]
    fn test_latent_values() {
        // Same values documented in the module docs: M=2
        let m2 = read_varint_meta2;
        assert_eq!(m2(0, &[]).0, 0);
        assert_eq!(m2(0x20, &[0x00]).0, 32);
        assert_eq!(m2(0x20, &[0x80, 0x00]).0, 4128);
        assert_eq!(m2(0x20, &[0x80, 0x80, 0x00]).0, 528416);
        assert_eq!(m2(0x20, &[0x80, 0x80, 0x80, 0x00]).0, 67637280);

        // Same values documented in the module docs: M=3
        let m3 = read_varint_meta3;
        assert_eq!(m3(0, &[]).0, 0);
        assert_eq!(m3(0x10, &[0x00]).0, 16);
        assert_eq!(m3(0x10, &[0x80, 0x00]).0, 2064);
        assert_eq!(m3(0x10, &[0x80, 0x80, 0x00]).0, 264208);
        assert_eq!(m3(0x10, &[0x80, 0x80, 0x80, 0x00]).0, 33818640);
    }
}