3 files changed, 215 insertions, 0 deletions
diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
new file mode 100644
index 0000000..705917a
--- /dev/null
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -0,0 +1,65 @@
+use std::convert::TryInto;
+
+use self::remainders::CalcRemainders;
+
+mod remainders;
+mod remainders_impl;
+
+/// Converts an input to a different base (which fits in usize). Returns the digits starting at the most significant one.
+pub(super) trait BaseConversion {
+    // return type is subject to change. Hopefully soon the math will be rewritten, so we can skip the Vec and IntoIter.
+    // will have to remain an ExactSizeIterator though.
+    fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>>;
+}
+
+impl<const N : usize, T> BaseConversion for T where T : ToI32Array<Output = [u32;N]>{
+    fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> {
+        self.to_int_array().calc_remainders(base).collect::<Vec<_>>().into_iter().rev()
+    }
+}
+
+impl BaseConversion for [u8;16]{
+    fn convert_to_base(self, base : usize) -> std::iter::Rev<std::vec::IntoIter<usize>> {
+        u128::from_be_bytes(self).calc_remainders(base as u128).map(|ll| ll as usize).collect::<Vec<_>>().into_iter().rev()
+    }
+}
+
+
+
+// Rust 1.52 only has a very limited support for const generics. This means, we'll have to live with this not-too-constrained solution...
+// Well, it's private, so no big loss.
+trait ToI32Array {
+    type Output;
+    fn to_int_array(self) -> Self::Output;
+}
+
+//this could of course be done in a generic manner, but it's ugly without array_mut, which we don't have in Rust 1.52.
+//Soo, pedestrian's approach :D 
+impl ToI32Array for [u8;20] {
+    type Output = [u32; 5];
+    fn to_int_array(self) -> [u32; 5] {
+        [
+            u32::from_be_bytes(self[0..4].try_into().unwrap()),
+            u32::from_be_bytes(self[4..8].try_into().unwrap()),
+            u32::from_be_bytes(self[8..12].try_into().unwrap()),
+            u32::from_be_bytes(self[12..16].try_into().unwrap()),
+            u32::from_be_bytes(self[16..20].try_into().unwrap()),
+        ]
+    }
+}
+
+impl ToI32Array for [u8;32] {
+    type Output = [u32; 8];
+    fn to_int_array(self) -> [u32; 8] {
+        [
+            u32::from_be_bytes(self[0..4].try_into().unwrap()),
+            u32::from_be_bytes(self[4..8].try_into().unwrap()),
+            u32::from_be_bytes(self[8..12].try_into().unwrap()),
+            u32::from_be_bytes(self[12..16].try_into().unwrap()),
+            u32::from_be_bytes(self[16..20].try_into().unwrap()),
+            u32::from_be_bytes(self[20..24].try_into().unwrap()),
+            u32::from_be_bytes(self[24..28].try_into().unwrap()),
+            u32::from_be_bytes(self[28..32].try_into().unwrap()),
+        ]
+    }
+}
+\ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/remainders.rs b/src/passwordmaker/base_conversion/remainders.rs
new file mode 100644
index 0000000..93570a1
--- /dev/null
+++ b/src/passwordmaker/base_conversion/remainders.rs
@@ -0,0 +1,74 @@
+/// Adds `calc_remainders(divisor)` method to types that have some implementation of the Division trait.
+pub(super) trait CalcRemainders<T, D>{
+    fn calc_remainders(self, divisor : D) -> Remainders<T,D>;
+}
+
+/// Implement `Division` to enable the `calc_remainders()` method for your type.
+pub(super) trait Division<D> where Self:Sized {
+    /// does in-place arbitrary-length division. Returns remainder.
+    fn divide(self, divisor : &D) -> DivisionResult<Self, D>;
+    fn is_zero(&self) -> bool;
+}
+
+/// Or mark your type as `UseGenericDivision` to just use `/` and `%` operators for types. Makes only sense for integers.
+pub(super) trait UseGenericDivision : Clone 
+    + for <'a> std::ops::Div<&'a Self, Output = Self> 
+    + for <'a> std::ops::Rem<&'a Self, Output = Self> 
+    + Default
+    + Eq {}
+
+impl<T, D> CalcRemainders<T, D> for T 
+    where T:Division<D>
+{
+    fn calc_remainders(self, divisor : D) -> Remainders<T, D> {
+        Remainders::new(self,divisor)
+    }
+}
+
+pub(super) struct Remainders<T, U>{
+    value : Option<T>,
+    divisor : U,
+}
+
+impl<U, T:Division<U>> Remainders<T, U> {
+    fn new(value : T, divisor : U) -> Self {
+        let value = if value.is_zero() { None } else { Some(value) };
+        Remainders {
+            value,
+            divisor,
+        }
+    }
+}
+
+impl<U, T:Division<U>> Iterator for Remainders<T,U>{
+    type Item=U;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(v) = self.value.take() {
+            let DivisionResult{result, remainder} = v.divide(&self.divisor);
+            self.value = if result.is_zero() { None } else { Some(result) };
+            Some(remainder)
+        } else {
+            None
+        }
+    }
+}
+
+pub(super) struct DivisionResult<T:Division<U>, U> {
+    pub result : T,
+    pub remainder : U,
+}
+
+impl<U> Division<U> for U
+    where U: UseGenericDivision
+{
+    fn divide(self, divisor : &Self) -> DivisionResult<Self, Self> {
+        DivisionResult { 
+            result: self.clone().div(divisor),
+            remainder: self.rem(divisor)
+        }
+    }
+    fn is_zero(&self) -> bool {
+        *self == Self::default()
+    }
+}
+\ No newline at end of file
diff --git a/src/passwordmaker/base_conversion/remainders_impl.rs b/src/passwordmaker/base_conversion/remainders_impl.rs
new file mode 100644
index 0000000..7de2189
--- /dev/null
+++ b/src/passwordmaker/base_conversion/remainders_impl.rs
@@ -0,0 +1,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;
+        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().fold(0 as UsizeAndFour,|carry, current| {
+            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;
+            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
+        });
+        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);
+    }
+
+}
+\ No newline at end of file