delsum_lib/fletcher/
mod.rs

1//! A builder for a Fletcher-like algorithm.
2//!
3//! The basic functionality of this algorithm is:
4//! * there is a sum which is just the bytes summed modulo some number
5//! * there is also a second sum which the sum of all of the normal sums (modulo the same number)
6//!
7//! Note that text word sizes are currently only `u8`.
8//!
9//! It works roughly like this:
10//! ```
11//! # fn check(file: &[u8]) -> u32 {
12//! # let modulus = 0xfff1u32;
13//! # let init = 1;
14//! # let (addout1, addout2) = (0, 0);
15//! # let hwidth = 16;
16//! let mut sum1 = init;
17//! let mut sum2 = 0;
18//! for byte in file {
19//!     sum1 = (sum1 + *byte as u32) % modulus;
20//!     sum2 = (sum2 + sum1) % modulus;
21//! }
22//! return (sum2 + addout2) % modulus << hwidth | (sum1 + addout1) % modulus;
23//! # }
24//! ```
25//! Normally, the sum is represented as the cumulative sum bitshifted to be above the regular sum.
26//! This representation will be referred to as "compact".
27//!
28//! These are the parameters:
29//! * width: Total number of bits of the checksum (twice the amount of bits of the individual sums)
30//! * modulus: The number by which both sums get reduced
31//! * init: The initial value of the regular sum
32//! * addout: The value that gets added at the end, compact
33//! * swap: Whether to swap the values in the compact representation, i.e. put the regular sum above the cumulative sum
34//! * check: The checksum of the bytes "123456789", checked to be correct on build
35//! * name: The name to be used when displaying the algorithm (optional)
36//!
37//! Note that the `init` parameter, unlike the `addout` parameter, is not compact and is only added to the regular sum,
38//! as for the cumulative sum, it is equivalent to the addout (so you can just add the cumulative `init` to the cumulative `addout`).
39
40mod rev;
41use crate::bitnum::{BitNum, Modnum};
42use crate::checksum::{CheckBuilderErr, Checksum, Digest, LinearCheck, parse_hex};
43use crate::endian::{Endian, SignedInt, Signedness, WordSpec};
44use crate::keyval::KeyValIter;
45use num_traits::{One, Zero};
46pub use rev::reverse_fletcher;
47#[cfg(feature = "parallel")]
48pub use rev::reverse_fletcher_para;
49use std::fmt::Display;
50use std::str::FromStr;
51
52/// A builder for a fletcher.
53///
54/// One can use it for specifying a fletcher algorithm, which can be used for checksumming.
55///
56/// Example:
57/// ```
58/// # use delsum_lib::fletcher::Fletcher;
59/// let adler32 = Fletcher::<u32>::with_options()
60///     .width(32)
61///     .init(1)
62///     .modulus(65521)
63///     .check(0x091e01de)
64///     .name("adler32")
65///     .build()
66///     .is_ok();
67/// ```
68#[derive(Clone, Debug)]
69pub struct FletcherBuilder<Sum: Modnum> {
70    width: Option<usize>,
71    modulus: Option<Sum>,
72    init: Option<Sum>,
73    addout: Option<Sum::Double>,
74    swap: Option<bool>,
75    input_endian: Option<Endian>,
76    output_endian: Option<Endian>,
77    signedness: Option<Signedness>,
78    wordsize: Option<usize>,
79    check: Option<Sum::Double>,
80    name: Option<String>,
81}
82
83impl<S: Modnum> FletcherBuilder<S> {
84    /// Sets the width of the type (both sums included, must be even, mandatory)
85    pub fn width(&mut self, w: usize) -> &mut Self {
86        self.width = Some(w);
87        self
88    }
89    /// Sets the modulus of both sums (mandatory)
90    pub fn modulus(&mut self, m: S) -> &mut Self {
91        self.modulus = Some(m);
92        self
93    }
94    /// Sets the initial value
95    ///
96    /// Contains one value for the regular sum.
97    pub fn init(&mut self, i: S) -> &mut Self {
98        self.init = Some(i);
99        self
100    }
101    /// Sets a value that gets added after the checksum is finished
102    ///
103    /// Contains separate values for both sums, the cumulative one is bitshifted
104    pub fn addout(&mut self, o: S::Double) -> &mut Self {
105        self.addout = Some(o);
106        self
107    }
108    /// Normally, the cumulative sum is saved on the higher bits and the normal sum in the lower bits.
109    /// Setting this option to true swaps the positions.
110    pub fn swap(&mut self, s: bool) -> &mut Self {
111        self.swap = Some(s);
112        self
113    }
114    /// The endian of the words of the input file
115    pub fn inendian(&mut self, e: Endian) -> &mut Self {
116        self.input_endian = Some(e);
117        self
118    }
119    /// The number of bits in a word of the input file
120    pub fn wordsize(&mut self, n: usize) -> &mut Self {
121        self.wordsize = Some(n);
122        self
123    }
124    /// The endian of the checksum
125    pub fn outendian(&mut self, e: Endian) -> &mut Self {
126        self.output_endian = Some(e);
127        self
128    }
129    /// The signedness of the input words
130    pub fn signedness(&mut self, s: Signedness) -> &mut Self {
131        self.signedness = Some(s);
132        self
133    }
134    /// Checks whether c is the same as the checksum of "123456789" on creation
135    pub fn check(&mut self, c: S::Double) -> &mut Self {
136        self.check = Some(c);
137        self
138    }
139    /// A name to be displayed
140    pub fn name(&mut self, n: &str) -> &mut Self {
141        self.name = Some(String::from(n));
142        self
143    }
144    /// Returns the Fletcher object after verifying correctness
145    pub fn build(&self) -> Result<Fletcher<S>, CheckBuilderErr> {
146        let init = self.init.unwrap_or_else(S::zero);
147        let addout = self.addout.unwrap_or_else(S::Double::zero);
148        // note: we only store the half width because it is more useful to us
149        let hwidth = match self.width {
150            None => return Err(CheckBuilderErr::MissingParameter("width")),
151            Some(w) => {
152                if w % 2 != 0 || w > addout.bits() {
153                    return Err(CheckBuilderErr::ValueOutOfRange("width"));
154                } else {
155                    w / 2
156                }
157            }
158        };
159        if hwidth > 64 {
160            return Err(CheckBuilderErr::ValueOutOfRange("width"));
161        }
162
163        let mask = (S::Double::one() << hwidth) - S::Double::one();
164        let modulus = self.modulus.unwrap_or_else(S::zero);
165        let wordsize = self.wordsize.unwrap_or(8);
166        if wordsize == 0 || wordsize % 8 != 0 || wordsize > 64 {
167            return Err(CheckBuilderErr::ValueOutOfRange("wordsize"));
168        }
169        let wordspec = WordSpec {
170            input_endian: self.input_endian.unwrap_or(Endian::Big),
171            wordsize,
172            output_endian: self.output_endian.unwrap_or(Endian::Big),
173            signedness: self.signedness.unwrap_or(Signedness::Unsigned),
174        };
175        let mut fletch = Fletcher {
176            hwidth,
177            modulus,
178            init,
179            addout,
180            swap: self.swap.unwrap_or(false),
181            wordspec,
182            mask,
183            name: self.name.clone(),
184        };
185        let (mut s, mut c) = fletch.convert_from_compact(addout);
186        if !modulus.is_zero() {
187            s = s % modulus;
188            c = c % modulus;
189            fletch.init = init % modulus;
190        } else {
191            fletch.init = init;
192        };
193        fletch.addout = fletch.to_compact((s, c));
194        match self.check {
195            Some(chk) => {
196                if fletch.digest(&b"123456789"[..]).unwrap() != chk {
197                    println!("{:x?}", fletch.digest(&b"123456789"[..]).unwrap());
198                    Err(CheckBuilderErr::CheckFail)
199                } else {
200                    Ok(fletch)
201                }
202            }
203            None => Ok(fletch),
204        }
205    }
206}
207
208#[derive(Clone, Debug, Eq, PartialEq)]
209pub struct Fletcher<Sum: Modnum> {
210    hwidth: usize,
211    modulus: Sum,
212    init: Sum,
213    addout: Sum::Double,
214    swap: bool,
215    wordspec: WordSpec,
216    mask: Sum::Double,
217    name: Option<String>,
218}
219
220impl<Sum: Modnum> Display for Fletcher<Sum> {
221    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
222        match &self.name {
223            Some(n) => write!(f, "{}", n),
224            None => {
225                write!(
226                    f,
227                    "fletcher width={} modulus={:#x} init={:#x} addout={:#x} swap={} signedness={}",
228                    2 * self.hwidth,
229                    self.modulus,
230                    self.init,
231                    self.addout,
232                    self.swap,
233                    self.wordspec.signedness
234                )?;
235                if self.wordspec.word_bytes() != 1 || self.wordspec.input_endian != Endian::Little {
236                    write!(
237                        f,
238                        " in_endian={} wordsize={}",
239                        self.wordspec.input_endian, self.wordspec.wordsize
240                    )?;
241                };
242                if self.hwidth * 2 > 8 {
243                    write!(f, " out_endian={}", self.wordspec.output_endian)?;
244                };
245                Ok(())
246            }
247        }
248    }
249}
250
251impl<Sum: Modnum> Fletcher<Sum> {
252    /// Creates a `FletcherBuilder`, see `FletcherBuilder` documentation for more details.
253    pub fn with_options() -> FletcherBuilder<Sum> {
254        FletcherBuilder {
255            width: None,
256            modulus: None,
257            init: None,
258            addout: None,
259            swap: None,
260            input_endian: None,
261            output_endian: None,
262            signedness: None,
263            wordsize: None,
264            check: None,
265            name: None,
266        }
267    }
268    fn convert_from_compact(&self, x: Sum::Double) -> (Sum, Sum) {
269        let l = Sum::from_double(x & self.mask);
270        let h = Sum::from_double((x >> self.hwidth) & self.mask);
271        if self.swap { (h, l) } else { (l, h) }
272    }
273    fn to_compact(&self, (s, c): (Sum, Sum)) -> Sum::Double {
274        let (l, h) = if self.swap { (c, s) } else { (s, c) };
275        (Sum::Double::from(l) & self.mask) ^ (Sum::Double::from(h) & self.mask) << self.hwidth
276    }
277}
278
279impl<Sum: Modnum> FromStr for FletcherBuilder<Sum> {
280    /// See documentation of FromStr on Fletcher<Sum>
281    fn from_str(s: &str) -> Result<FletcherBuilder<Sum>, CheckBuilderErr> {
282        let mut fletch = Fletcher::<Sum>::with_options();
283        for x in KeyValIter::new(s) {
284            let (current_key, current_val) = match x {
285                Err(key) => return Err(CheckBuilderErr::MalformedString(key)),
286                Ok(s) => s,
287            };
288            let fletch_op = match current_key.as_str() {
289                "width" => usize::from_str(&current_val).ok().map(|x| fletch.width(x)),
290                "modulus" => Some(fletch.modulus(parse_hex::<Sum>(&current_val, "modulus")?)),
291                "init" => Some(fletch.init(parse_hex::<Sum>(&current_val, "init")?)),
292                "addout" => Some(fletch.addout(parse_hex::<Sum::Double>(&current_val, "addout")?)),
293                "swap" => bool::from_str(&current_val).ok().map(|x| fletch.swap(x)),
294                "in_endian" => Endian::from_str(&current_val)
295                    .ok()
296                    .map(|x| fletch.inendian(x)),
297                "wordsize" => usize::from_str(&current_val)
298                    .ok()
299                    .map(|x| fletch.wordsize(x)),
300                "out_endian" => Endian::from_str(&current_val)
301                    .ok()
302                    .map(|x| fletch.outendian(x)),
303                "signedness" => Signedness::from_str(&current_val)
304                    .ok()
305                    .map(|x| fletch.signedness(x)),
306                "check" => Some(fletch.check(parse_hex::<Sum::Double>(&current_val, "check")?)),
307                "name" => Some(fletch.name(&current_val)),
308                _ => return Err(CheckBuilderErr::UnknownKey(current_key)),
309            };
310            match fletch_op {
311                Some(f) => fletch = f.clone(),
312                None => return Err(CheckBuilderErr::MalformedString(current_key)),
313            }
314        }
315        Ok(fletch)
316    }
317    type Err = CheckBuilderErr;
318}
319
320impl<Sum: Modnum> FromStr for Fletcher<Sum> {
321    /// Construct a new fletcher sum algorithm from a string.
322    /// Note that all parameters except width are in hexadecimal.
323    ///
324    /// Example:
325    ///
326    /// ```
327    /// # use delsum_lib::fletcher::Fletcher;
328    /// # use std::str::FromStr;
329    /// Fletcher::<u32>::from_str("width=32 init=1 modulus=0xfff1 name=\"adler-32\"").is_ok();
330    /// ```
331    fn from_str(s: &str) -> Result<Fletcher<Sum>, CheckBuilderErr> {
332        FletcherBuilder::<Sum>::from_str(s)?.build()
333    }
334    type Err = CheckBuilderErr;
335}
336
337impl<S: Modnum> Digest for Fletcher<S> {
338    type Sum = S::Double;
339    fn init(&self) -> Self::Sum {
340        self.to_compact((self.init, S::zero()))
341    }
342    fn dig_word(&self, sum: Self::Sum, word: SignedInt<u64>) -> Self::Sum {
343        let (mut s, mut c) = self.convert_from_compact(sum);
344        let modword = S::mod_from_signed(word, &self.modulus);
345        s = S::add_mod(s, &modword, &self.modulus);
346        c = S::add_mod(c, &s, &self.modulus);
347        self.to_compact((s, c))
348    }
349    fn finalize(&self, sum: Self::Sum) -> Self::Sum {
350        self.add(sum, &self.addout)
351    }
352
353    fn to_bytes(&self, s: Self::Sum) -> Vec<u8> {
354        self.wordspec.output_to_bytes(s, 2 * self.hwidth)
355    }
356
357    fn checksum_from_bytes(&self, bytes: &[u8]) -> Option<Self::Sum> {
358        Checksum::from_bytes(bytes, self.wordspec.output_endian, self.hwidth * 2)
359    }
360
361    fn wordspec(&self) -> WordSpec {
362        self.wordspec
363    }
364}
365
366impl<S: Modnum> LinearCheck for Fletcher<S> {
367    type Shift = S;
368    fn init_shift(&self) -> Self::Shift {
369        S::zero()
370    }
371    fn inc_shift(&self, shift: Self::Shift) -> Self::Shift {
372        S::add_mod(shift, &S::one(), &self.modulus)
373    }
374    fn shift(&self, sum: Self::Sum, shift: &Self::Shift) -> Self::Sum {
375        let (s, mut c) = self.convert_from_compact(sum);
376        let shift_diff = S::mul_mod(s, shift, &self.modulus);
377        c = S::add_mod(c, &shift_diff, &self.modulus);
378        self.to_compact((s, c))
379    }
380    fn add(&self, sum_a: Self::Sum, sum_b: &Self::Sum) -> Self::Sum {
381        let (sa, ca) = self.convert_from_compact(sum_a);
382        let (sb, cb) = self.convert_from_compact(*sum_b);
383        let sum_s = sa.add_mod(&sb, &self.modulus);
384        let sum_c = ca.add_mod(&cb, &self.modulus);
385        self.to_compact((sum_s, sum_c))
386    }
387    fn negate(&self, sum: Self::Sum) -> Self::Sum {
388        let (s, c) = self.convert_from_compact(sum);
389        self.to_compact((s.neg_mod(&self.modulus), c.neg_mod(&self.modulus)))
390    }
391}
392#[cfg(test)]
393mod tests {
394    use super::*;
395    use crate::checksum::tests::{check_example, test_find, test_prop, test_shifts};
396    use std::str::FromStr;
397    #[test]
398    fn adler32() {
399        let adel = Fletcher::<u16>::with_options()
400            .width(32)
401            .init(1)
402            .modulus(65521)
403            .check(0x091e01de)
404            .build()
405            .unwrap();
406        test_shifts(&adel);
407        test_find(&adel);
408        test_prop(&adel);
409        check_example(&adel, 0x81bfd25f);
410        let nobel = Fletcher::with_options()
411            .width(32)
412            .init(1u32)
413            .modulus(65521)
414            .check(0x091e01de)
415            .build()
416            .unwrap();
417        test_shifts(&nobel);
418        test_find(&nobel);
419        test_prop(&adel);
420        check_example(&nobel, 0x81bfd25f);
421    }
422    #[test]
423    fn fletcher16() {
424        let f16 = Fletcher::with_options()
425            .width(16)
426            .modulus(0xffu8)
427            .check(0x1ede)
428            .build()
429            .unwrap();
430        test_shifts(&f16);
431        test_find(&f16);
432        test_prop(&f16);
433        check_example(&f16, 0x7815);
434    }
435    #[test]
436    fn fletcher8() {
437        let f8 = Fletcher::<u8>::from_str(
438            "width=8 modulus=0xf init=0x0 addout=0x0 swap=false check=0xc",
439        )
440        .unwrap();
441        test_shifts(&f8);
442        test_prop(&f8);
443        check_example(&f8, 0x6);
444    }
445}
delsum_lib/fletcher/mod.rs

delsum_lib/fletcher/
mod.rs
