hash-roll 0.3.0

Rolling hashes & Content Defined Chunking (cdc)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#![cfg(feature = "pigz")]
use crate::{Chunk, ChunkIncr, ToChunkIncr};

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PigzRsyncable {
    bits: u8,

    /// directly derived from `bits`
    mask: u32,
    /// directly derived from `mask`
    hit: u32,
}

impl PigzRsyncable {
    pub fn with_bits(bits: u8) -> PigzRsyncable {
        let mask = (1 << bits) - 1;
        let hit = mask >> 1;
        PigzRsyncable { bits, mask, hit }
    }
}

impl Default for PigzRsyncable {
    fn default() -> Self {
        Self::with_bits(12)
    }
}

impl Chunk for PigzRsyncable {
    type SearchState = PigzRsyncableSearchState;

    fn to_search_state(&self) -> Self::SearchState {
        self.into()
    }

    fn find_chunk_edge(
        &self,
        state: &mut Self::SearchState,
        data: &[u8],
    ) -> (Option<usize>, usize) {
        for i in 0..data.len() {
            let v = data[i];

            if state.state.add(self, v) {
                *state = self.to_search_state();
                return (Some(i + 1), i + 1);
            }
        }

        (None, data.len())
    }
}

impl From<&PigzRsyncable> for PigzRsyncableIncr {
    fn from(src: &PigzRsyncable) -> Self {
        src.clone().into()
    }
}

impl ToChunkIncr for PigzRsyncable {
    type Incr = PigzRsyncableIncr;
    fn to_chunk_incr(&self) -> Self::Incr {
        self.into()
    }
}

#[derive(Debug, Clone)]
struct PigzRsyncableState {
    hash: u32,
}

impl From<&PigzRsyncable> for PigzRsyncableState {
    fn from(params: &PigzRsyncable) -> Self {
        PigzRsyncableState { hash: params.hit }
    }
}

/// Intermediate state for [`PigzRsyncable::find_chunk_edge`]
///
/// Using this avoids re-computation of data when no edge is found
#[derive(Debug, Clone)]
pub struct PigzRsyncableSearchState {
    state: PigzRsyncableState,
}

impl From<&PigzRsyncable> for PigzRsyncableSearchState {
    fn from(params: &PigzRsyncable) -> Self {
        PigzRsyncableSearchState {
            state: params.into(),
        }
    }
}

/// Provides an incremental interface to [`PigzRsyncable`]
///
/// Performance Note: [`PigzRsyncable`] requires look-back. As a result, [`PigzRsyncableIncr`] internally
/// buffers data up to the window size. This additional copying may affect performance. If
/// possible for your use case, use the non-incremental interface.
///
/// See [`PigzRsyncable`] for details on the underlying algorithm
#[derive(Debug, Clone)]
pub struct PigzRsyncableIncr {
    params: PigzRsyncable,
    state: PigzRsyncableState,
}

impl PigzRsyncableIncr {}

impl From<PigzRsyncable> for PigzRsyncableIncr {
    fn from(params: PigzRsyncable) -> Self {
        let state = (&params).into();
        PigzRsyncableIncr { params, state }
    }
}

impl PigzRsyncableState {
    fn add(&mut self, parent: &PigzRsyncable, v: u8) -> bool {
        self.hash = ((self.hash << 1) ^ (v as u32)) & parent.mask;
        self.hash == parent.hit
    }
}

impl ChunkIncr for PigzRsyncableIncr {
    fn push(&mut self, data: &[u8]) -> Option<usize> {
        for (i, &v) in data.iter().enumerate() {
            if self.state.add(&self.params, v) {
                self.state = (&self.params).into();
                return Some(i + 1);
            }
        }

        None
    }
}