librsyncr 0.1.1

/*
 * Copyright 2018 Jordan Miner
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 */

use std::num::Wrapping;

const CHAR_OFFSET: Wrapping<u16> = Wrapping(31);

#[derive(Clone,Debug)]
pub struct RollingChecksum {
    a: Wrapping<u16>,
    b: Wrapping<u16>,
    count: u64,
}

impl RollingChecksum {
    pub fn new() -> Self {
        RollingChecksum {
            a: Wrapping(0),
            b: Wrapping(0),
            count: 0,
        }
    }

    #[inline]
    #[allow(dead_code)]
    pub fn add(&mut self, in_byte: u8) {
        let in_byte = Wrapping(in_byte as u16);

        self.a += in_byte + CHAR_OFFSET;
        self.b += self.a;
        self.count += 1;
    }

    pub fn add_slice(&mut self, bytes: &[u8]) {
        // slower implementation
        //for &in_byte in bytes {
        //    self.add(in_byte);
        //}
        //return;

        // Without using locals, the compiler does keep a and b in registers, but it still
        // copies them to the struct every loop iteration. Using locals removes the two mov
        // instructions from the loop.
        let mut a = self.a;
        let mut b = self.b;
        for &in_byte in bytes {
            a += Wrapping(in_byte as u16);
            b += a;
        }
        let in_count = bytes.len() as u64;
        a += CHAR_OFFSET * Wrapping(in_count as u16);
        b += CHAR_OFFSET * Wrapping((in_count * (in_count + 1) / 2) as u16);
        self.count += in_count;
        self.a = a;
        self.b = b;
    }

    #[inline]
    #[allow(dead_code)]
    pub fn remove(&mut self, out_byte: u8) {
        let out_byte = Wrapping(out_byte as u16);

        self.a -= out_byte + CHAR_OFFSET;
        self.b -= Wrapping(self.count as u16) * (out_byte + CHAR_OFFSET);
        self.count -= 1;
    }

    #[inline]
    pub fn rotate(&mut self, in_byte: u8, out_byte: u8) {
        let in_byte = Wrapping(in_byte as u16);
        let out_byte = Wrapping(out_byte as u16);

        self.a += in_byte - out_byte;
        self.b += self.a - Wrapping(self.count as u16) * (out_byte + CHAR_OFFSET);
    }

    #[inline]
    pub fn get(&self) -> u32 {
        ((self.b.0 as u32) << 16) | self.a.0 as u32
    }
}

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

    #[test]
    fn test_add_slice_2047() {
        let data = &[5; 2047];
        let mut rc = RollingChecksum::new();
        for &b in &data[..] {
            rc.add(b);
        }
        let val = rc.get();

        rc = RollingChecksum::new();
        rc.add_slice(data);
        let slice_val = rc.get();

        assert_eq!(slice_val, val);
    }
}