delsum_lib/modsum/
mod.rs

1//! A simple modular sum over bytes (i.e. `bytes.sum() % modulus`)
2//!
3//! There are a number of parameters:
4//! * width: The number of bits in the sum type, at most 64
5//! * modulus: The sum is taken modulo this number
6//! * init: The initial number
7//! * check: The checksum of "123456789" (optional, gets checked at construction)
8//! * name: An optional name that gets used for display purposes
9//!
10//! Note that a parameter to add at the end is not needed, since it is equivalent to `init`.
11mod rev;
12use crate::bitnum::Modnum;
13use crate::checksum::{CheckBuilderErr, Checksum, Digest, LinearCheck, parse_hex};
14use crate::endian::{Endian, SignedInt, Signedness, WordSpec};
15use crate::keyval::KeyValIter;
16pub(crate) use rev::find_largest_mod;
17pub use rev::reverse_modsum;
18use std::fmt::Display;
19use std::str::FromStr;
20
21/// A builder to set the various parameters for the modsum algorithm.
22///
23/// Example:
24/// ```
25/// # use delsum_lib::modsum::ModSum;
26/// ModSum::<u8>::with_options()
27///     .width(8)
28///     .check(0xdd)
29///     .build()
30///     .is_ok();
31/// ```
32/// Note that modulus = 0 is assumed to be 2^width
33#[derive(Debug, Clone)]
34pub struct ModSumBuilder<S: Modnum> {
35    width: Option<usize>,
36    modulus: Option<S>,
37    init: Option<S>,
38    input_endian: Option<Endian>,
39    output_endian: Option<Endian>,
40    signedness: Option<Signedness>,
41    negated: Option<bool>,
42    wordsize: Option<usize>,
43    check: Option<S>,
44    name: Option<String>,
45}
46
47impl<S: Modnum> ModSumBuilder<S> {
48    /// The total width, in bits, of the sum. Mandatory.
49    ///
50    /// Can actually be wider than the sum itself, important is that `2^width >= modulus`.
51    pub fn width(&mut self, w: usize) -> &mut Self {
52        self.width = Some(w);
53        self
54    }
55    /// The number by which the remainder is taken. Mandatory.
56    ///
57    /// If this is 0, it is equivalent to be `2^width`.
58    pub fn modulus(&mut self, m: S) -> &mut Self {
59        self.modulus = Some(m);
60        self
61    }
62    /// The initial value, optional, defaults to 0.
63    pub fn init(&mut self, i: S) -> &mut Self {
64        self.init = Some(i);
65        self
66    }
67    /// The endian of the words of the input file
68    pub fn inendian(&mut self, e: Endian) -> &mut Self {
69        self.input_endian = Some(e);
70        self
71    }
72    /// The number of bits in a word of the input file
73    pub fn wordsize(&mut self, n: usize) -> &mut Self {
74        self.wordsize = Some(n);
75        self
76    }
77    /// The endian of the checksum
78    pub fn outendian(&mut self, e: Endian) -> &mut Self {
79        self.output_endian = Some(e);
80        self
81    }
82    /// The signedness of the input words
83    pub fn signedness(&mut self, s: Signedness) -> &mut Self {
84        self.signedness = Some(s);
85        self
86    }
87    /// Whether the output checksum is negated
88    pub fn negated(&mut self, n: bool) -> &mut Self {
89        self.negated = Some(n);
90        self
91    }
92    /// The checksum of "123456789", gets checked on creation.
93    pub fn check(&mut self, c: S) -> &mut Self {
94        self.check = Some(c);
95        self
96    }
97    /// An optional name that gets used for display purposes.
98    pub fn name(&mut self, n: &str) -> &mut Self {
99        self.name = Some(String::from(n));
100        self
101    }
102    /// Builds the algorithm, after validating the parameters.
103    pub fn build(&self) -> Result<ModSum<S>, CheckBuilderErr> {
104        let width = self
105            .width
106            .ok_or(CheckBuilderErr::MissingParameter("width"))?;
107        if width > 64 {
108            return Err(CheckBuilderErr::ValueOutOfRange("width"));
109        }
110        let mut modulus = self.modulus.unwrap_or_else(S::zero);
111        if modulus == S::zero() && width < modulus.bits() {
112            modulus = S::one() << width
113        };
114        let mut init = self.init.unwrap_or_else(S::zero);
115        if modulus != S::zero() {
116            init = init % modulus
117        };
118        let wordsize = self.wordsize.unwrap_or(8);
119        if wordsize == 0 || wordsize % 8 != 0 || wordsize > 64 {
120            return Err(CheckBuilderErr::ValueOutOfRange("wordsize"));
121        }
122        let negated = self.negated.unwrap_or(false);
123        let wordspec = WordSpec {
124            input_endian: self.input_endian.unwrap_or(Endian::Big),
125            wordsize,
126            output_endian: self.output_endian.unwrap_or(Endian::Big),
127            signedness: self.signedness.unwrap_or(Signedness::Unsigned),
128        };
129        let s = ModSum {
130            width,
131            modulus,
132            init,
133            negated,
134            wordspec,
135            name: self.name.clone(),
136        };
137        match self.check {
138            Some(c) => {
139                let mut sum = s.init();
140                for &x in b"123456789" {
141                    sum = s.dig_word(sum, SignedInt::pos(x as u64));
142                }
143                s.finalize(sum);
144                if sum == c {
145                    return Ok(s);
146                }
147                Err(CheckBuilderErr::CheckFail)
148            }
149            None => Ok(s),
150        }
151    }
152}
153
154/// A Modsum checksum algorithm.
155///
156/// Implements LinearCheck so that finding checksummed locations in a file is efficiently possible.
157#[derive(Debug, PartialEq, Eq)]
158pub struct ModSum<S: Modnum> {
159    width: usize,
160    modulus: S,
161    init: S,
162    negated: bool,
163    wordspec: WordSpec,
164    name: Option<String>,
165}
166
167impl<S: Modnum> ModSum<S> {
168    /// Creates a `ModSumBuilder`, for more information see its documentation.
169    pub fn with_options() -> ModSumBuilder<S> {
170        ModSumBuilder {
171            width: None,
172            modulus: None,
173            init: None,
174            input_endian: None,
175            output_endian: None,
176            signedness: None,
177            negated: None,
178            wordsize: None,
179            check: None,
180            name: None,
181        }
182    }
183}
184
185impl<Sum: Modnum> Display for ModSum<Sum> {
186    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
187        match &self.name {
188            Some(n) => write!(f, "{}", n),
189            None => {
190                write!(
191                    f,
192                    "modsum width={} modulus={:#x} init={:#x} negated={} signedness={}",
193                    self.width, self.modulus, self.init, self.negated, self.wordspec.signedness
194                )?;
195                if self.wordspec.word_bytes() != 1 || self.wordspec.input_endian != Endian::Little {
196                    write!(
197                        f,
198                        " in_endian={} wordsize={}",
199                        self.wordspec.input_endian, self.wordspec.wordsize,
200                    )?;
201                };
202                if self.width > 8 {
203                    write!(f, " out_endian={}", self.wordspec.output_endian)?;
204                }
205                Ok(())
206            }
207        }
208    }
209}
210
211impl<Sum: Modnum> FromStr for ModSumBuilder<Sum> {
212    /// See FromStr for ModSum<Sum>
213    fn from_str(s: &str) -> Result<ModSumBuilder<Sum>, CheckBuilderErr> {
214        let mut sum = ModSum::<Sum>::with_options();
215        for x in KeyValIter::new(s) {
216            let (current_key, current_val) = match x {
217                Err(key) => return Err(CheckBuilderErr::MalformedString(key)),
218                Ok(s) => s,
219            };
220            let crc_op = match current_key.as_str() {
221                "width" => usize::from_str(&current_val).ok().map(|x| sum.width(x)),
222                "modulus" => Some(sum.modulus(parse_hex::<Sum>(&current_val, "modulus")?)),
223                "init" => Some(sum.init(parse_hex::<Sum>(&current_val, "init")?)),
224                "in_endian" => Endian::from_str(&current_val).ok().map(|x| sum.inendian(x)),
225                "wordsize" => usize::from_str(&current_val).ok().map(|x| sum.wordsize(x)),
226                "out_endian" => Endian::from_str(&current_val)
227                    .ok()
228                    .map(|x| sum.outendian(x)),
229                "signedness" => Signedness::from_str(&current_val)
230                    .ok()
231                    .map(|x| sum.signedness(x)),
232                "negated" => bool::from_str(&current_val).ok().map(|x| sum.negated(x)),
233                "name" => Some(sum.name(&current_val)),
234                _ => return Err(CheckBuilderErr::UnknownKey(current_key)),
235            };
236            match crc_op {
237                Some(c) => sum = c.clone(),
238                None => return Err(CheckBuilderErr::MalformedString(current_key)),
239            }
240        }
241        Ok(sum)
242    }
243    type Err = CheckBuilderErr;
244}
245
246impl<Sum: Modnum> FromStr for ModSum<Sum> {
247    /// Construct a new modular sum from a string specification.
248    ///
249    /// Example:
250    ///
251    /// width=16 modulus=0xffff init=0
252    fn from_str(s: &str) -> Result<ModSum<Sum>, CheckBuilderErr> {
253        ModSumBuilder::from_str(s)?.build()
254    }
255    type Err = CheckBuilderErr;
256}
257
258impl<S: Modnum> Digest for ModSum<S> {
259    type Sum = S;
260    fn init(&self) -> Self::Sum {
261        if self.negated {
262            self.init.neg_mod(&self.modulus)
263        } else {
264            self.init
265        }
266    }
267
268    fn dig_word(&self, sum: Self::Sum, word: SignedInt<u64>) -> Self::Sum {
269        let modword = S::mod_from_signed(word.negate_if(self.negated), &self.modulus);
270        sum.add_mod(&modword, &self.modulus)
271    }
272
273    fn finalize(&self, sum: Self::Sum) -> Self::Sum {
274        sum
275    }
276
277    fn to_bytes(&self, s: Self::Sum) -> Vec<u8> {
278        self.wordspec.output_to_bytes(s, self.width)
279    }
280
281    fn checksum_from_bytes(&self, bytes: &[u8]) -> Option<Self::Sum> {
282        Checksum::from_bytes(bytes, self.wordspec.output_endian, self.width)
283    }
284
285    fn wordspec(&self) -> WordSpec {
286        self.wordspec
287    }
288}
289
290impl<S: Modnum> LinearCheck for ModSum<S> {
291    type Shift = ();
292    // shifts are trivial in this checksum type
293    fn init_shift(&self) -> Self::Shift {}
294    fn inc_shift(&self, _: Self::Shift) -> Self::Shift {}
295    fn shift(&self, sum: Self::Sum, _: &Self::Shift) -> Self::Sum {
296        sum
297    }
298    fn shift_n(&self, _: usize) -> Self::Shift {}
299    fn add(&self, sum_a: Self::Sum, sum_b: &Self::Sum) -> Self::Sum {
300        sum_a.add_mod(sum_b, &self.modulus)
301    }
302    fn negate(&self, sum: Self::Sum) -> Self::Sum {
303        sum.neg_mod(&self.modulus)
304    }
305}
306#[cfg(test)]
307mod tests {
308    use super::*;
309    use crate::checksum::tests::{test_prop, test_shifts};
310    use crate::checksum::{Relativity, const_sum};
311    #[test]
312    fn modsum_8() {
313        let s = ModSum::<u8>::with_options()
314            .width(8)
315            .check(0xdd)
316            .build()
317            .unwrap();
318        test_shifts(&s);
319        test_prop(&s);
320        let s = ModSum::<u16>::with_options()
321            .width(8)
322            .check(0xdd)
323            .build()
324            .unwrap();
325        test_shifts(&s);
326        test_prop(&s);
327    }
328    #[test]
329    fn mod_17() {
330        let s = ModSum::<u8>::with_options()
331            .width(5)
332            .modulus(17)
333            .check(1)
334            .build()
335            .unwrap();
336        test_shifts(&s);
337        test_prop(&s);
338    }
339    #[test]
340    fn ethsum() {
341        let chk = ModSum::<u16>::with_options()
342            .width(16)
343            .init(0xff00)
344            .modulus(0xffff)
345            .check(0xde)
346            .build()
347            .unwrap();
348        test_shifts(&chk);
349        test_prop(&chk);
350        // 0xff*0x101 = 0xffff
351        let many_255: Vec<_> = std::iter::repeat(0xffu8).take(0x101).collect();
352        assert_eq!(chk.digest(many_255.as_slice()).unwrap(), 0xff00);
353        let x = Vec::from("implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR ");
354        let y = Vec::from("This program comes with ABSOLUTELY NO WARRANTY; for details type");
355        let merchantibility = chk.digest(b" MERCHANTABILITY".as_ref()).unwrap();
356        let ith_absolutely_ = chk.digest(b"with ABSOLUTELY ".as_ref()).unwrap();
357        assert_eq!(
358            chk.find_segments(
359                &[x, y],
360                &[Some(merchantibility), Some(ith_absolutely_)].map(const_sum),
361                Relativity::Start
362            ),
363            vec![(vec![19], vec![34])]
364        );
365    }
366
367    #[test]
368    fn signed_sum() {
369        let s = ModSum::<u16>::with_options()
370            .width(16)
371            .modulus(0)
372            .signedness(Signedness::Signed)
373            .build()
374            .unwrap();
375        let x = vec![0x80, 0x80];
376        assert_eq!(s.digest(x.as_slice()).unwrap(), 0xff00);
377    }
378}
delsum_lib/modsum/mod.rs

delsum_lib/modsum/
mod.rs
