convert_base/
lib.rs

1#![doc=include_str!("../readme.md")]
2use std::ops::{Add,Div,Rem};
3
4/// Convert the radix (base) of digits stored in a vector.
5pub struct Convert {
6  from: u64,
7  to: u64,
8  ratio: (usize,usize)
9}
10
11impl Convert {
12  /// Create a new converter with `from` and `to` bases.
13  pub fn new (from: u64, to: u64) -> Self {
14    let mut ratio = (0,0);
15    if from % to == 0 || to % from == 0 {
16      let max_i = 128 / ulog2(to.max(from));
17      let mut j = 0;
18      let mut k = 0;
19      let f = from as u128;
20      let t = to as u128;
21      for i in 0..max_i {
22        let f_j = f.pow(j);
23        let t_k = t.pow(k);
24        if i > 0 && f_j == t_k {
25          ratio.0 = j as usize;
26          ratio.1 = k as usize;
27          break
28        } else if f_j < t_k || (i == 0 && from > to) {
29          j += 1
30        } else { k+=1 }
31      }
32    }
33    Convert { from, to, ratio }
34  }
35  /// Create a new converter but don't test for alignment.
36  pub fn new_unaligned (from: u64, to: u64) -> Self {
37    Convert { from, to, ratio: (0,0) }
38  }
39  /// Perform the conversion on `input` which contains digits in base
40  /// `self.from`. You should specify the `Output` type so that the target base
41  /// (`self.to`) fits. There are no checks to ensure the `Output` type has
42  /// room.
43  ///
44  /// For input and output vectors, the least significant digit is at the
45  /// beginning of the array.
46  pub fn convert<Input,Output> (&mut self, input: &[Input]) -> Vec<Output>
47  where Output: Copy+Into<u64>+From<u8>+FromU64
48  +Add<Output,Output=Output>+Div<Output,Output=Output>+Rem<Output,Output=Output>,
49  Input: Copy+Into<u64> {
50    let len = input.len();
51    let cap = len*ulog2(self.from)/ulog2(self.to);
52    let mut output: Vec<Output> = Vec::with_capacity(cap);
53    let mut base: Vec<Output> = vec![1u8.into()];
54    let mut v0: Vec<Output> = vec![];
55    let step = self.ratio.0;
56    let mut offset = 0;
57    for (i,x) in input.iter().enumerate() {
58      v0.clear();
59      v0.extend(&base);
60      self.multiply_scalar_into(&mut v0, (*x).into());
61      self.add_into(&mut output, &v0, offset);
62      if i+1 < input.len() {
63        self.multiply_scalar_into(&mut base, self.from);
64      }
65      if step > 0 && i%step == step-1 {
66        base.clear();
67        base.push(1u8.into());
68        offset += self.ratio.1;
69      }
70    }
71    output
72  }
73  fn multiply_scalar_into<T> (&self, dst: &mut Vec<T>, x: u64) -> ()
74  where T: Copy+Into<u64>+FromU64 {
75    let mut carry = 0u64;
76    for i in 0..dst.len() {
77      let res = dst[i].into() * x + carry;
78      carry = res / self.to;
79      dst[i] = FromU64::from(res % (self.to as u64));
80    }
81    while carry > 0 {
82      dst.push(FromU64::from(carry % self.to));
83      carry /= self.to;
84    }
85  }
86  fn add_into<T> (&self, dst: &mut Vec<T>, src: &Vec<T>, offset: usize) -> ()
87  where T: Copy+Into<u64>+FromU64
88  +Add<T,Output=T>+Div<T,Output=T>+Rem<T,Output=T> {
89    let mut carry = 0u64;
90    let mut i = 0;
91    while dst.len().max(offset)-offset < src.len() {
92      dst.push(FromU64::from(0));
93    }
94    loop {
95      let j = i + offset;
96      if i < src.len() && j < dst.len() {
97        let res = src[i].into() + dst[j].into() + carry;
98        carry = res / self.to;
99        dst[j] = FromU64::from(res % self.to);
100      } else if j < dst.len() {
101        let res = dst[j].into() + carry;
102        carry = res / self.to;
103        dst[j] = FromU64::from(res % self.to);
104      } else if i < src.len() {
105        let res = src[i].into() + carry;
106        carry = res / self.to;
107        dst.push(FromU64::from(res % self.to));
108      } else if carry > 0 {
109        let res = carry;
110        carry = res / self.to;
111        dst.push(FromU64::from(res % self.to));
112      } else {
113        break;
114      }
115      i += 1;
116    }
117  }
118}
119
120fn ulog2 (x: u64) -> usize { (63-x.leading_zeros()) as usize }
121
122// custom trait because TryFrom is difficult:
123#[doc(hidden)]
124pub trait FromU64 { fn from (n: u64) -> Self; }
125impl FromU64 for u8 { fn from (n: u64) -> Self { n as u8 } }
126impl FromU64 for u16 { fn from (n: u64) -> Self { n as u16 } }
127impl FromU64 for u32 { fn from (n: u64) -> Self { n as u32 } }
128impl FromU64 for u64 { fn from (n: u64) -> Self { n as u64 } }
convert_base/lib.rs

convert_base/
lib.rs
