tapirus 1.2.1

Embedded multi-model database with SQL, vector search and local AI memory
Documentation
//! Pure Safe Rust LZ4 Block Compression Engine.
//!
//! Provides transparent, high-throughput lossless compression for 4KB/8KB slotted
//! pages in TapirusDB without any external dependencies or unsafe code.
//!
//! Complies strictly with `#![forbid(unsafe_code)]`.

#![forbid(unsafe_code)]

use crate::error::{Error, Result};

const MIN_MATCH: usize = 4;
const HASH_TABLE_BITS: usize = 11;
const HASH_TABLE_SIZE: usize = 1 << HASH_TABLE_BITS; // 2048 slots: 4 KB for u16, 8 KB for u32 (fits L1)
const MAX_DISTANCE: usize = 65535;

/// Magic tag identifying a TapirusDB compressed page payload
pub const COMPRESSED_PAGE_MAGIC: u8 = 0x54; // 'T'
/// Flag indicating that page payload bytes are uncompressed
pub const UNCOMPRESSED_PAGE_FLAG: u8 = 0x00;
/// Flag indicating that page payload bytes are compressed using LZ4
pub const LZ4_COMPRESSED_PAGE_FLAG: u8 = 0x01;

/// Hash a 4-byte sequence for hash table lookup
#[inline(always)]
fn hash_4(bytes: &[u8]) -> usize {
    let val = u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
    // Knuth multiplicative hash mapped to HASH_TABLE_SIZE bits
    ((val.wrapping_mul(2654435761)) >> (32 - HASH_TABLE_BITS)) as usize
}

/// Compress an arbitrary byte slice using LZ4 block encoding in pure safe Rust.
pub fn compress_lz4_block(src: &[u8]) -> Vec<u8> {
    if src.len() < MIN_MATCH {
        let mut out = Vec::with_capacity(src.len() + 2);
        let lit_len = src.len();
        out.push((lit_len.min(15) << 4) as u8);
        if lit_len >= 15 {
            let mut rem = lit_len - 15;
            while rem >= 255 {
                out.push(255);
                rem -= 255;
            }
            out.push(rem as u8);
        }
        out.extend_from_slice(src);
        return out;
    }

    // Use a 4 KB stack hash table for <=64 KB buffers (all standard 4K-32K DB pages)
    // and an 8 KB table for larger inputs instead of zeroing 32 KB on every page.
    if src.len() <= u16::MAX as usize {
        let mut hash_table = [0u16; HASH_TABLE_SIZE];
        compress_lz4_with_table(src, &mut hash_table)
    } else {
        let mut hash_table = [0usize; HASH_TABLE_SIZE];
        compress_lz4_with_table(src, &mut hash_table)
    }
}

trait Lz4HashSlot: Copy {
    fn from_pos(pos: usize) -> Self;
    fn to_pos(self) -> usize;
}

impl Lz4HashSlot for u16 {
    #[inline(always)]
    fn from_pos(pos: usize) -> Self {
        pos as u16
    }
    #[inline(always)]
    fn to_pos(self) -> usize {
        self as usize
    }
}

impl Lz4HashSlot for usize {
    #[inline(always)]
    fn from_pos(pos: usize) -> Self {
        pos
    }
    #[inline(always)]
    fn to_pos(self) -> usize {
        self
    }
}

fn compress_lz4_with_table<S: Lz4HashSlot>(
    src: &[u8],
    hash_table: &mut [S; HASH_TABLE_SIZE],
) -> Vec<u8> {
    let mut out = Vec::with_capacity(src.len());

    let mut anchor = 0;
    let mut ip = 0;
    let end = src.len();
    let mflimit = end.saturating_sub(12);

    while ip < mflimit {
        let h = hash_4(&src[ip..ip + 4]);
        let match_pos = hash_table[h].to_pos();
        hash_table[h] = S::from_pos(ip);

        // Verify if match exists within MAX_DISTANCE and has at least 4 identical bytes
        if match_pos < ip
            && ip - match_pos <= MAX_DISTANCE
            && src[match_pos..match_pos + 4] == src[ip..ip + 4]
        {
            // Found a match!
            let lit_len = ip - anchor;

            // Determine length of match
            let mut match_len = 4;
            while (ip + match_len < end) && (src[match_pos + match_len] == src[ip + match_len]) {
                match_len += 1;
            }

            let token_lit = lit_len.min(15);
            let token_match = (match_len - 4).min(15);
            let token = ((token_lit << 4) | token_match) as u8;
            out.push(token);

            // Encode literal length overflow
            if lit_len >= 15 {
                let mut rem = lit_len - 15;
                while rem >= 255 {
                    out.push(255);
                    rem -= 255;
                }
                out.push(rem as u8);
            }

            // Write literals
            out.extend_from_slice(&src[anchor..ip]);

            // Write 2-byte little-endian offset
            let offset = (ip - match_pos) as u16;
            out.extend_from_slice(&offset.to_le_bytes());

            // Encode match length overflow
            if match_len - 4 >= 15 {
                let mut rem = (match_len - 4) - 15;
                while rem >= 255 {
                    out.push(255);
                    rem -= 255;
                }
                out.push(rem as u8);
            }

            ip += match_len;
            anchor = ip;

            // Update hash for boundary
            if ip < mflimit {
                let h_next = hash_4(&src[ip - 2..ip + 2]);
                hash_table[h_next] = S::from_pos(ip - 2);
            }
        } else {
            ip += 1;
        }
    }

    // Write trailing literals
    let last_lit_len = end - anchor;
    let token = ((last_lit_len.min(15)) << 4) as u8;
    out.push(token);
    if last_lit_len >= 15 {
        let mut rem = last_lit_len - 15;
        while rem >= 255 {
            out.push(255);
            rem -= 255;
        }
        out.push(rem as u8);
    }
    out.extend_from_slice(&src[anchor..end]);

    out
}

/// Decompress an LZ4 block byte slice into a target output buffer in pure safe Rust.
pub fn decompress_lz4_block(src: &[u8], target_len: usize) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(target_len);
    let mut ip = 0;

    while ip < src.len() && out.len() < target_len {
        let token = src[ip];
        ip += 1;

        // 1. Literal length
        let mut lit_len = (token >> 4) as usize;
        if lit_len == 15 {
            while ip < src.len() {
                let extra = src[ip] as usize;
                ip += 1;
                lit_len += extra;
                if extra != 255 {
                    break;
                }
            }
        }

        // Copy literals
        if ip + lit_len > src.len() || out.len().saturating_add(lit_len) > target_len {
            return Err(Error::Corrupted("LZ4 literal run out of bounds".into()));
        }
        out.extend_from_slice(&src[ip..ip + lit_len]);
        ip += lit_len;

        if out.len() >= target_len || ip >= src.len() {
            break;
        }

        // 2. Match offset (2 bytes LE)
        if ip + 2 > src.len() {
            return Err(Error::Corrupted("LZ4 match offset truncated".into()));
        }
        let offset = u16::from_le_bytes([src[ip], src[ip + 1]]) as usize;
        ip += 2;

        if offset == 0 || offset > out.len() {
            return Err(Error::Corrupted(format!(
                "LZ4 invalid back-reference offset: {offset} (current out len: {})",
                out.len()
            )));
        }

        // 3. Match length
        let mut match_len = ((token & 0x0F) as usize) + 4;
        if (token & 0x0F) == 15 {
            while ip < src.len() {
                let extra = src[ip] as usize;
                ip += 1;
                match_len += extra;
                if extra != 255 {
                    break;
                }
            }
        }

        if out.len().saturating_add(match_len) > target_len {
            return Err(Error::Corrupted(
                "LZ4 match exceeds declared output size".into(),
            ));
        }
        // Copy match from previous output buffer bytes
        let match_start = out.len() - offset;
        for i in 0..match_len {
            let byte = out[match_start + i];
            out.push(byte);
        }
    }

    Ok(out)
}

/// Compress a page only when the frame fits before the reserved crypto trailer.
/// Incompressible pages remain raw, preserving their fixed page size and contents.
pub fn compress_page_frame(raw_page: &[u8]) -> Vec<u8> {
    let compressed = compress_lz4_block(raw_page);
    let original_len = raw_page.len() as u16;

    // We need 4 bytes header: [COMPRESSED_PAGE_MAGIC, FLAG, LEN_LO, LEN_HI]
    if compressed.len() + 4
        <= raw_page
            .len()
            .saturating_sub(crate::btree::PAGE_RESERVED_TRAILER)
    {
        let mut out = Vec::with_capacity(4 + compressed.len());
        out.push(COMPRESSED_PAGE_MAGIC);
        out.push(LZ4_COMPRESSED_PAGE_FLAG);
        out.extend_from_slice(&original_len.to_le_bytes());
        out.extend_from_slice(&compressed);
        out
    } else {
        raw_page.to_vec()
    }
}

/// Decompress a page frame back to its full original page size.
pub fn decompress_page_frame(frame: &[u8], default_page_size: usize) -> Result<Vec<u8>> {
    if frame.len() < 4 || frame[0] != COMPRESSED_PAGE_MAGIC {
        // Plain uncompressed page image
        return Ok(frame.to_vec());
    }

    let flag = frame[1];
    let original_len = u16::from_le_bytes([frame[2], frame[3]]) as usize;
    // Overflow pages start with a next-page ID. Its low byte may equal 'T';
    // a lone magic byte must never shift an ordinary page's payload.
    if original_len != default_page_size {
        return Ok(frame.to_vec());
    }
    let expected_len = default_page_size;

    match flag {
        UNCOMPRESSED_PAGE_FLAG => Ok(frame[4..].to_vec()),
        LZ4_COMPRESSED_PAGE_FLAG => {
            let result = decompress_lz4_block(&frame[4..], expected_len)?;
            if result.len() != expected_len {
                return Err(Error::Corrupted("Compressed page length mismatch".into()));
            }
            Ok(result)
        }
        _ => Ok(frame.to_vec()),
    }
}

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

    #[test]
    fn test_lz4_roundtrip_slotted_page() {
        // Create synthetic 4096-byte page with repeated JSON and text
        let mut page = vec![0u8; 4096];
        let sample = b"{\"id\": 42, \"name\": \"TapirusDB Industrial Supremacy\", \"active\": true, \"scores\": [1.0, 2.5]}";
        for chunk in page.chunks_mut(sample.len()) {
            let len = chunk.len().min(sample.len());
            chunk[..len].copy_from_slice(&sample[..len]);
        }

        let compressed_frame = compress_page_frame(&page);
        assert!(
            compressed_frame.len() < page.len() / 2,
            "LZ4 should compress repetitive page by >50%"
        );

        let decompressed =
            decompress_page_frame(&compressed_frame, 4096).expect("Decompression should succeed");
        assert_eq!(decompressed.len(), 4096);
        assert_eq!(decompressed, page);
    }

    #[test]
    fn test_lz4_incompressible_fallback() {
        // High entropy pseudo-random sequence
        let mut page = vec![0u8; 512];
        for (i, byte) in page.iter_mut().enumerate() {
            *byte = ((i * 199 + 37) % 256) as u8;
        }

        let compressed_frame = compress_page_frame(&page);
        let decompressed =
            decompress_page_frame(&compressed_frame, 512).expect("Decompression fallback succeeds");
        assert_eq!(decompressed, page);
    }
}