weavatrix-git 0.3.1

use crate::{GitError, Result, error::invalid};

pub(super) fn apply(base: &[u8], delta: &[u8], limit: usize) -> Result<Vec<u8>> {
    let mut cursor = 0;
    let base_size = read_varint(delta, &mut cursor)?;
    if base_size != base.len() {
        return Err(invalid("pack delta base size mismatch"));
    }
    let result_size = read_varint(delta, &mut cursor)?;
    if result_size > limit {
        return Err(GitError::LimitExceeded {
            resource: "delta result bytes",
            limit,
        });
    }
    let mut result = Vec::with_capacity(result_size);
    while cursor < delta.len() {
        let opcode = delta[cursor];
        cursor += 1;
        if opcode & 0x80 != 0 {
            copy(base, delta, &mut cursor, opcode, &mut result, limit)?;
        } else if opcode != 0 {
            let count = usize::from(opcode);
            let end = cursor
                .checked_add(count)
                .ok_or_else(|| invalid("delta insert overflow"))?;
            let bytes = delta
                .get(cursor..end)
                .ok_or_else(|| invalid("truncated delta insert"))?;
            extend(&mut result, bytes, limit)?;
            cursor = end;
        } else {
            return Err(invalid("reserved pack delta opcode"));
        }
    }
    if result.len() != result_size {
        return Err(invalid("pack delta result size mismatch"));
    }
    Ok(result)
}

fn copy(
    base: &[u8],
    delta: &[u8],
    cursor: &mut usize,
    opcode: u8,
    output: &mut Vec<u8>,
    limit: usize,
) -> Result<()> {
    let mut offset = 0_usize;
    let mut size = 0_usize;
    for index in 0..4 {
        if opcode & (1 << index) != 0 {
            offset |= usize::from(take(delta, cursor)?) << (index * 8);
        }
    }
    for index in 0..3 {
        if opcode & (1 << (index + 4)) != 0 {
            size |= usize::from(take(delta, cursor)?) << (index * 8);
        }
    }
    if size == 0 {
        size = 0x1_0000;
    }
    let end = offset
        .checked_add(size)
        .ok_or_else(|| invalid("delta copy overflow"))?;
    let bytes = base
        .get(offset..end)
        .ok_or_else(|| invalid("delta copy exceeds base"))?;
    extend(output, bytes, limit)
}

fn take(input: &[u8], cursor: &mut usize) -> Result<u8> {
    let value = *input
        .get(*cursor)
        .ok_or_else(|| invalid("truncated pack delta"))?;
    *cursor += 1;
    Ok(value)
}

fn read_varint(input: &[u8], cursor: &mut usize) -> Result<usize> {
    let mut value = 0_usize;
    let mut shift = 0;
    loop {
        let byte = take(input, cursor)?;
        value = value
            .checked_add(usize::from(byte & 0x7f) << shift)
            .ok_or_else(|| invalid("pack delta varint overflow"))?;
        if byte & 0x80 == 0 {
            return Ok(value);
        }
        shift += 7;
        if shift >= usize::BITS {
            return Err(invalid("pack delta varint is too long"));
        }
    }
}

fn extend(output: &mut Vec<u8>, bytes: &[u8], limit: usize) -> Result<()> {
    if output
        .len()
        .checked_add(bytes.len())
        .is_none_or(|size| size > limit)
    {
        return Err(GitError::LimitExceeded {
            resource: "delta result bytes",
            limit,
        });
    }
    output.extend_from_slice(bytes);
    Ok(())
}

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

    #[test]
    fn applies_insert_and_copy_delta() {
        let delta = [5, 11, 0x91, 0, 5, 6, b' ', b'w', b'o', b'r', b'l', b'd'];
        assert_eq!(apply(b"hello", &delta, 20).unwrap(), b"hello world");
    }

    #[test]
    fn rejects_malformed_delta_programs() {
        assert!(apply(b"hello", &[4, 0], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 0], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 2, b'a'], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 1, b'a'], 0).is_err());
        assert!(apply(b"hello", &[5, 1, 0x91], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 0x91, 9, 1], 20).is_err());
        assert!(apply(b"hello", &[0x80; 20], 20).is_err());
    }
}