meshopt-rs 0.1.2

//! **Experimental** index sequence encoding and decoding

use std::io::Write;

use super::{decode_v_byte, encode_v_byte, read_byte, write_byte, DecodeError, IndexEncodingVersion};

const SEQUENCE_HEADER: u8 = 0xd0;

/// Encodes index sequence into an array of bytes that is generally smaller and compresses better compared to original.
///
/// Input index sequence can represent arbitrary topology; for triangle lists [encode_index_buffer](crate::index::buffer::encode_index_buffer) is likely to be better.
///
/// Returns encoded data size on success, 0 on error; the only error condition is if buffer doesn't have enough space
///
/// # Arguments
///
/// * `buffer`: must contain enough space for the encoded index sequence (use [encode_index_sequence_bound] to compute worst case size)
pub fn encode_index_sequence(buffer: &mut [u8], indices: &[u32], version: IndexEncodingVersion) -> usize {
    let buffer_len = buffer.len();

    // the minimum valid encoding is header, 1 byte per index and a 4-byte tail
    if buffer_len < 1 + indices.len() + 4 {
        return 0;
    }

    let version: u8 = version.into();

    let mut data = buffer;
    write_byte(&mut data, SEQUENCE_HEADER | (version as u8));

    let mut last: [u32; 2] = [0; 2];
    let mut current = 0;

    for index in indices {
        // make sure we have enough data to write
        // each index writes at most 5 bytes of data; there's a 4 byte tail after data_safe_end
        // after this we can be sure we can write without extra bounds checks
        if data.len() < 4 {
            return 0;
        }

        // this is a heuristic that switches between baselines when the delta grows too large
        // we want the encoded delta to fit into one byte (7 bits), but 2 bits are used for sign and baseline index
        // for now we immediately switch the baseline when delta grows too large - this can be adjusted arbitrarily
        let cd = (*index).wrapping_sub(last[current]) as i32;
        current ^= if cd.abs() >= 30 { 1 } else { 0 };

        // encode delta from the last index
        let d = index.wrapping_sub(last[current]);
        let v = (d << 1) ^ (((d as i32) >> 31) as u32);

        // note: low bit encodes the index of the last baseline which will be used for reconstruction
        encode_v_byte(&mut data, (v << 1) | (current as u32));

        // update last for the next iteration that uses it
        last[current] = *index;
    }

    // make sure we have enough space to write tail
    if data.len() < 4 {
        return 0;
    }

    data.write(&[0; 4]).unwrap();

    buffer_len - data.len()
}

/// Returns worst case size requirement for [encode_index_sequence].
pub fn encode_index_sequence_bound(index_count: usize, vertex_count: usize) -> usize {
    // compute number of bits required for each index
    let mut vertex_bits = 1;

    while vertex_bits < 32 && vertex_count > (1 << vertex_bits) {
        vertex_bits += 1;
    }

    // worst-case encoding is 1 varint-7 encoded index delta for a K bit value and an extra bit
    let vertex_groups = (vertex_bits + 1 + 1 + 6) / 7;

    return 1 + index_count * vertex_groups + 4;
}

/// Decodes index data from an array of bytes generated by [encode_index_sequence].
///
/// Returns `Ok` if decoding was successful, and an error otherwise.
///
/// The decoder is safe to use for untrusted input, but it may produce garbage data (e.g. out of range indices).
///
/// # Arguments
///
/// * `destination`: must contain the exact space for the resulting index sequence
pub fn decode_index_sequence<T>(destination: &mut [T], buffer: &[u8]) -> Result<(), DecodeError>
where
    T: From<u32>,
{
    // the minimum valid encoding is header, 1 byte per index and a 4-byte tail
    if buffer.len() < 1 + destination.len() + 4 {
        return Err(DecodeError::UnexpectedEof);
    }

    let mut data = buffer;
    let first = read_byte(&mut data);

    if (first & 0xf0) != SEQUENCE_HEADER {
        return Err(DecodeError::InvalidHeader);
    }

    let version = first & 0x0f;
    if version > 1 {
        return Err(DecodeError::UnsupportedVersion);
    }

    let mut last: [u32; 2] = Default::default();

    for i in 0..destination.len() {
        let mut v = decode_v_byte(&mut data);

        // decode the index of the last baseline
        let current = (v & 1) as usize;
        v >>= 1;

        // reconstruct index as a delta
        let d = (v >> 1) ^ (-((v & 1) as i32) as u32);
        let index = last[current].wrapping_add(d);

        // update last for the next iteration that uses it
        last[current] = index;

        destination[i] = T::from(index);
    }

    if data.len() == 4 {
        Ok(())
    } else {
        // we should've read all data bytes and stopped at the boundary between data and tail
        Err(DecodeError::ExtraBytes)
    }
}

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

    const INDEX_SEQUENCE: [u32; 6] = [0, 1, 51, 2, 49, 1000];
    const INDEX_SEQUENCE_V1: [u8; 13] = [
        0xd1, 0x00, 0x04, 0xcd, 0x01, 0x04, 0x07, 0x98, 0x1f, 0x00, 0x00, 0x00, 0x00,
    ];

    #[test]
    fn test_decode_index_sequence() {
        let mut decoded: [u32; INDEX_SEQUENCE.len()] = Default::default();

        assert!(decode_index_sequence(&mut decoded, &INDEX_SEQUENCE_V1).is_ok());
        assert_eq!(decoded, INDEX_SEQUENCE);
    }

    #[test]
    fn test_decode_index_sequence_16() {
        let buffer = encode_test_index_sequence();

        #[derive(Clone, Copy, Default)]
        struct U16(u16);

        impl From<u32> for U16 {
            fn from(index: u32) -> Self {
                Self { 0: index as u16 }
            }
        }

        let mut decoded = [U16::default(); INDEX_SEQUENCE.len()];
        assert!(decode_index_sequence(&mut decoded, &buffer).is_ok());

        assert!(decoded.iter().enumerate().all(|(i, v)| v.0 as u32 == INDEX_SEQUENCE[i]));
    }

    fn encode_test_index_sequence() -> Vec<u8> {
        let mut buffer: Vec<u8> = Vec::new();
        buffer.resize_with(
            encode_index_sequence_bound(INDEX_SEQUENCE.len(), 1001),
            Default::default,
        );

        let written = encode_index_sequence(&mut buffer, &INDEX_SEQUENCE, IndexEncodingVersion::V1);
        buffer.resize_with(written, Default::default);

        buffer
    }

    #[test]
    fn test_encode_index_sequence_memory_safe() {
        let mut buffer = encode_test_index_sequence();

        // check that encode is memory-safe
        for i in 0..=buffer.len() {
            let result = encode_index_sequence(&mut buffer[0..i], &INDEX_SEQUENCE, IndexEncodingVersion::V1);

            if i == buffer.len() {
                assert_eq!(result, buffer.len());
            } else {
                assert_eq!(result, 0);
            }
        }
    }

    #[test]
    fn test_decode_index_sequence_memory_safe() {
        let buffer = encode_test_index_sequence();

        // check that decode is memory-safe
        let mut decoded: [u32; INDEX_SEQUENCE.len()] = Default::default();

        for i in 0..=buffer.len() {
            let result = decode_index_sequence(&mut decoded, &buffer[0..i]);

            if i == buffer.len() {
                assert!(result.is_ok());
            } else {
                assert!(result.is_err());
            }
        }
    }

    #[test]
    fn test_decode_index_sequence_reject_extra_bytes() {
        let mut buffer = encode_test_index_sequence();

        // check that decoder doesn't accept extra bytes after a valid stream
        buffer.push(0);

        let mut decoded: [u32; INDEX_SEQUENCE.len()] = Default::default();
        assert!(decode_index_sequence(&mut decoded, &buffer).is_err());
    }

    #[test]
    fn test_decode_index_sequence_reject_malformed_headers() {
        let mut buffer = encode_test_index_sequence();

        // check that decoder doesn't accept malformed headers
        buffer[0] = 0;

        let mut decoded: [u32; INDEX_SEQUENCE.len()] = Default::default();
        assert!(decode_index_sequence(&mut decoded, &buffer).is_err());
    }

    #[test]
    fn test_decode_index_sequence_reject_invalid_version() {
        let mut buffer = encode_test_index_sequence();

        // check that decoder doesn't accept invalid version
        buffer[0] |= 0x0f;

        let mut decoded: [u32; INDEX_SEQUENCE.len()] = Default::default();
        assert!(decode_index_sequence(&mut decoded, &buffer).is_err());
    }

    #[test]
    fn test_encode_index_sequence_empty() {
        let mut buffer = Vec::new();
        buffer.resize_with(encode_index_sequence_bound(0, 0), Default::default);

        let written = encode_index_sequence(&mut buffer, &[], IndexEncodingVersion::V1);
        buffer.resize_with(written, Default::default);

        assert!(decode_index_sequence::<u32>(&mut [], &buffer).is_ok());
    }
}