wedb_embed 0.1.1

//! 保序变长整型编码（Order-Preserving Prefix Varint - OPPV）
//! 保证对任意 u64 a < b，其二进制编码在字节字典序上恒满足 a_bytes < b_bytes（支持 memcmp/LSM Range Seek 直接保序）

/// 编码 u64 到已有 Vec 缓冲区
#[inline]
pub fn encode_oppv_u64(val: u64, buf: &mut Vec<u8>) {
    if val < 0x80 {
        // [0..127]: 1 字节 (最高位 0)
        buf.push(val as u8);
    } else if val < 0x4000 {
        // [128..16383]: 2 字节 (高 2 位 10)
        buf.push(0x80 | ((val >> 8) as u8));
        buf.push((val & 0xFF) as u8);
    } else if val < 0x20_0000 {
        // [16384..2097151]: 3 字节 (高 3 位 110)
        buf.push(0xC0 | ((val >> 16) as u8));
        buf.push(((val >> 8) & 0xFF) as u8);
        buf.push((val & 0xFF) as u8);
    } else if val < 0x1000_0000 {
        // [2097152..268435455]: 4 字节 (高 4 位 1110)
        buf.push(0xE0 | ((val >> 24) as u8));
        buf.push(((val >> 16) & 0xFF) as u8);
        buf.push(((val >> 8) & 0xFF) as u8);
        buf.push((val & 0xFF) as u8);
    } else {
        // 大数值：0xF8 + 8 字节大端序
        buf.push(0xF8);
        buf.extend_from_slice(&val.to_be_bytes());
    }
}

/// 解码字节切片开头的 OPPV u64，返回 (解码数值, 消耗字节数)
#[inline]
pub fn decode_oppv_u64(slice: &[u8]) -> Option<(u64, usize)> {
    let first = *slice.first()?;
    if first < 0x80 {
        Some((first as u64, 1))
    } else if first < 0xC0 {
        if slice.len() < 2 {
            return None;
        }
        let val = (((first & 0x3F) as u64) << 8) | (slice[1] as u64);
        Some((val, 2))
    } else if first < 0xE0 {
        if slice.len() < 3 {
            return None;
        }
        let val = (((first & 0x1F) as u64) << 16) | ((slice[1] as u64) << 8) | (slice[2] as u64);
        Some((val, 3))
    } else if first < 0xF0 {
        if slice.len() < 4 {
            return None;
        }
        let val = (((first & 0x0F) as u64) << 24)
            | ((slice[1] as u64) << 16)
            | ((slice[2] as u64) << 8)
            | (slice[3] as u64);
        Some((val, 4))
    } else if first == 0xF8 {
        if slice.len() < 9 {
            return None;
        }
        let mut bytes = [0u8; 8];
        bytes.copy_from_slice(&slice[1..9]);
        Some((u64::from_be_bytes(bytes), 9))
    } else {
        None
    }
}

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

    #[test]
    fn test_oppv_strict_order_preservation() {
        let test_values = [
            0u64,
            1,
            2,
            127,
            128,
            129,
            1000,
            16383,
            16384,
            100_000,
            1_000_000,
            268_435_455,
            268_435_456,
            1_000_000_000,
            u64::MAX - 1,
            u64::MAX,
        ];

        let mut encoded_list = Vec::new();
        for &v in &test_values {
            let mut buf = Vec::new();
            encode_oppv_u64(v, &mut buf);
            let (decoded, consumed) = decode_oppv_u64(&buf).unwrap();
            assert_eq!(decoded, v);
            assert_eq!(consumed, buf.len());
            encoded_list.push((v, buf));
        }

        // 验证二进制字典序必须与数值大小完全等价
        for i in 0..encoded_list.len() - 1 {
            let (v1, ref b1) = encoded_list[i];
            let (v2, ref b2) = encoded_list[i + 1];
            assert!(
                v1 < v2,
                "Value {v1} should be strictly less than value {v2}"
            );
            assert!(
                b1 < b2,
                "Encoded bytes {b1:?} should be strictly less than bytes {b2:?}"
            );
        }
    }
}