Merge pull request #1 from soulsource/feature/heap-allocation-free-base-conversion

Feature/heap allocation free base conversion

While skipping the heap allocation is nice, the real gain is the option to early-out of password generation once the desired length has been reached.

1 files changed, 31 insertions, 23 deletions

diff --git a/src/passwordmaker/base_conversion/mod.rs b/src/passwordmaker/base_conversion/mod.rs
index 8d217ef..6415904 100644
--- a/src/passwordmaker/base_conversion/mod.rs
+++ b/src/passwordmaker/base_conversion/mod.rs
@@ -1,56 +1,64 @@
 use std::convert::TryInto;
+use iterative_conversion_impl::PaddedShiftLeft;
+pub(super) use iterative_conversion::IterativeBaseConversion;
+pub(super) use iterative_conversion_impl::{SixteenBytes, ArbitraryBytes};
 
-use self::remainders::CalcRemainders;
+use self::iterative_conversion::PrecomputedMaxPowers;
 
-mod remainders;
-mod remainders_impl;
+mod iterative_conversion;
+mod iterative_conversion_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>>;
+    type Output : ExactSizeIterator<Item=usize>;
+    fn convert_to_base(self, base : usize) -> Self::Output;
 }
 
-impl<T, const N : usize> 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()
+#[allow(clippy::trait_duplication_in_bounds)] //False positive in clippy. usize != u32.
+impl<T, const N : usize, const M : usize> BaseConversion for T 
+    where T : ToArbitraryBytes<Output = ArbitraryBytes<N>>,
+        for<'a> T::Output: From<&'a usize> + From<&'a u32> + PaddedShiftLeft<Output = ArbitraryBytes<M>> + PrecomputedMaxPowers<usize>,
+{
+    type Output = IterativeBaseConversion<ArbitraryBytes<N>, usize>;
+    fn convert_to_base(self, base : usize) -> Self::Output {
+        IterativeBaseConversion::new(self.to_arbitrary_bytes(), base)
     }
 }
 
 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()
+    type Output = IterativeBaseConversion<SixteenBytes,usize>;
+    fn convert_to_base(self, base : usize) -> IterativeBaseConversion<SixteenBytes,usize> {
+        IterativeBaseConversion::new(SixteenBytes::new(u128::from_be_bytes(self)), base)
     }
 }
 
 
 
 // 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...
-pub(super) trait ToI32Array {
+pub(super) trait ToArbitraryBytes {
     type Output;
-    fn to_int_array(self) -> Self::Output;
+    fn to_arbitrary_bytes(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] {
-        [
+impl ToArbitraryBytes for [u8;20] {
+    type Output = ArbitraryBytes<5>;
+    fn to_arbitrary_bytes(self) -> ArbitraryBytes<5> {
+        ArbitraryBytes::new([
             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] {
-        [
+impl ToArbitraryBytes for [u8;32] {
+    type Output = ArbitraryBytes<8>;
+    fn to_arbitrary_bytes(self) -> ArbitraryBytes<8> {
+        ArbitraryBytes::new([
             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()),
@@ -59,6 +67,6 @@ impl ToI32Array for [u8;32] {
             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