mkups 0.1.0

//! Functions for creating UPS patches

use std::io::prelude::*;
use crc::{Crc, Digest, CRC_32_ISO_HDLC};

/// Creates an UPS patch containing the difference between `input` and `patched`.
pub fn create(input: &[u8], patched: &[u8], writer: &mut impl Write) -> std::io::Result<()> {
    let patch_crc = new_crc();
    let mut writer = std::io::BufWriter::new(CrcWrite::new(writer, patch_crc.digest()));

    writer.write_all(b"UPS1")?;
    write_vlq(&mut writer, input.len())?;
    write_vlq(&mut writer, patched.len())?;
    diff(input, patched, &mut writer)?;

    writer.write_all(&new_crc().checksum(input).to_le_bytes())?;
    writer.write_all(&new_crc().checksum(patched).to_le_bytes())?;
    writer.flush()?;
    let (writer, patch_crc) = writer.into_inner()?.into_inner();
    writer.write_all(&patch_crc.to_le_bytes())?;
    Ok(())
}

#[derive(Clone, Copy)]
enum State {
    Copy(usize),
    Patch,
}
fn diff(input: &[u8], patched: &[u8], writer: &mut impl Write) -> std::io::Result<()> {
    let len = input.len().max(patched.len());
    let mut state = State::Copy(0);
    for i in 0..len {
        let x = rd(input, i) ^ rd(patched, i);
        match (state, x) {
            (State::Copy(_), 0) => {
                // nop
            },
            (State::Copy(since), xor) => {
                write_vlq(writer, i - since)?;
                write(writer, xor)?;
                state = State::Patch;
            },
            (State::Patch, 0) => {
                write(writer, 0)?;
                state = State::Copy(i+1);
            }
            (State::Patch, xor) => {
                write(writer, xor)?;
            },
        }
    }
    if let State::Patch = state {
        write(writer, 0)?;
    }
    Ok(())
}

fn new_crc() -> Crc<u32> {
    Crc::<u32>::new(&CRC_32_ISO_HDLC)
}

fn rd(xs: &[u8], i: usize) -> u8 {
    if i < xs.len() { xs[i] } else { 0 }
}

fn write(w: &mut impl Write, x: u8) -> std::io::Result<()> {
    w.write_all(&[x])?;
    Ok(())
}

fn write_vlq(w: &mut impl Write, x: usize) -> std::io::Result<()> {
    let mut x = x;
    loop {
        let octet = (x & 0x7f) as u8;
        x >>= 7;
        if x == 0 {
            write(w, 0x80 | octet)?;
            break;
        }
        write(w, octet)?;
        x -= 1;
    }
    Ok(())
}

struct CrcWrite<'a, W: Write> {
    w: W,
    digest: Digest<'a, u32>,
}

impl<'a, W: Write> CrcWrite<'a, W> {
    fn new(w: W, digest: Digest<'a, u32>) -> Self {
        Self {
            w,
            digest,
        }
    }

    fn into_inner(self) -> (W, u32) {
        (self.w, self.digest.finalize())
    }
}

impl<W: Write> Write for CrcWrite<'_, W> {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        let n = self.w.write(buf)?;
        self.digest.update(&buf[0..n]);
        Ok(n)
    }

    fn flush(&mut self) -> std::io::Result<()> {
        self.w.flush()
    }
}

#[test]
fn test_write_vlq_inmem() {
    assert_eq!(write_vlq_inmem(1).unwrap(), vec![0x81]);
    assert_eq!(write_vlq_inmem(4849).unwrap(), vec![0x71, 0xa4]);
}

#[cfg(test)]
fn write_vlq_inmem(x: usize) -> std::io::Result<Vec<u8>> {
    let mut cursor = std::io::Cursor::new(Vec::new());
    write_vlq(&mut cursor, x)?;
    Ok(cursor.into_inner())
}

#[test]
fn test_crc_write() {
    let cursor = std::io::Cursor::new(Vec::new());
    let crc = new_crc();
    let mut crc_write = CrcWrite::new(cursor, crc.digest());
    crc_write.write_all(b"hello").unwrap();
    let (cursor, crc) = crc_write.into_inner();
    let vec = cursor.into_inner();
    assert_eq!(vec, b"hello");
    assert_eq!(crc, 0x3610a686);
}

#[test]
fn test_diff_simple() {
    test_diff(b"foo", b"fOo", b"\x81\x20\x00");
    test_diff(b"foo", b"foO", b"\x82\x20\x00");
    test_diff(b"foo", b"foobar", b"\x83bar\x00");
    test_diff(b"foobar", b"foo", b"\x83bar\x00");
}

#[test]
fn test_diff_multiple() {
    test_diff(b"hello, world", b"Hello, World", b"\x80\x20\x00\x85\x20\x00");
}

#[cfg(test)]
fn test_diff(input: &[u8], patched: &[u8], expected: &[u8]) {
    let mut cursor = std::io::Cursor::new(Vec::new());
    diff(input, patched, &mut cursor).unwrap();
    assert_eq!(cursor.into_inner(), expected);
}