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
|
use super::remainders::{Division, UseGenericDivision, DivisionResult};
impl UseGenericDivision for u128{} //for Md4, Md5
impl<const N : usize> Division<usize> for [u32;N] {
#[allow(clippy::cast_possible_truncation)]
fn divide(mut self, divisor : &usize) -> DivisionResult<Self, usize> {
#[cfg(target_pointer_width = "64")]
type UsizeAndFour = u128;
#[cfg(not(target_pointer_width = "64"))]
type UsizeAndFour = u64;
debug_assert!((UsizeAndFour::MAX >> 32) as u128 >= usize::MAX as u128);
//uses mutation, because why not? self is owned after all :D
let divisor : UsizeAndFour = *divisor as UsizeAndFour;
let remainder = self.iter_mut().skip_while(|x| **x == 0).fold(0 as UsizeAndFour,|carry, current| {
debug_assert_eq!(carry, carry & (usize::MAX as UsizeAndFour)); //carry has to be lower than divisor, and divisor is usize.
let carry_shifted = carry << 32;
let dividend = (carry_shifted) + (*current as UsizeAndFour);
let ratio = dividend / divisor;
debug_assert_eq!(ratio, ratio & 0xffff_ffff); //this is fine. The first digit after re-adding the carry is alwys zero.
*current = (ratio) as u32;
dividend - (*current as UsizeAndFour) * divisor
});
debug_assert_eq!(remainder, remainder & (usize::MAX as UsizeAndFour));
let remainder = remainder as usize;
DivisionResult{
result: self,
remainder,
}
}
fn is_zero(&self) -> bool {
self.iter().all(|x| *x == 0)
}
}
#[cfg(test)]
mod remainders_tests{
use super::super::remainders::CalcRemainders;
use super::*;
#[test]
fn test_generic_division(){
let v = 50u128;
let d = 7u128;
let DivisionResult{result, remainder}=v.divide(&d);
assert_eq!(7, result);
assert_eq!(1, remainder);
}
#[test]
fn test_remainders() {
//relies on generic division.
let v = 141u128;
let d = 3u128;
let results : Vec<u128> = v.calc_remainders(d).collect();
assert_eq!(results, vec![0u128,2u128,0u128,2u128,1u128])
}
#[test]
fn test_array_divide() {
let dividend_int = 0xe7f1ec3a5f35af805407a8a531eefb79u128;
let dividend = [(dividend_int >> 96) as u32, ((dividend_int >> 64) & 0xffffffff) as u32, ((dividend_int >> 32) & 0xffffffff) as u32, (dividend_int & 0xffffffff) as u32];
#[cfg(target_pointer_width = "64")]
let divisor = 1531534813576487;
#[cfg(not(target_pointer_width = "64"))]
let divisor = 1531534813;
let result_int = dividend_int / (divisor as u128);
let remainder_int = dividend_int % (divisor as u128);
let result = dividend.divide(&divisor);
assert_eq!(result.result, [(result_int >> 96) as u32, ((result_int >> 64) & 0xffffffff) as u32, ((result_int >> 32) & 0xffffffff) as u32, (result_int & 0xffffffff) as u32]);
assert_eq!(remainder_int, result.remainder as u128);
}
}
|
