use crate::biguint;
use num_traits::Zero;
use sp_std::{cmp::{min, max}, convert::TryInto, mem};
pub fn gcd(a: u128, b: u128) -> u128 {
match ((a, b), (a & 1, b & 1)) {
((x, y), _) if x == y => y,
((0, x), _) | ((x, 0), _) => x,
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y),
((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1,
((x, y), (1, 1)) => {
let (x, y) = (min(x, y), max(x, y));
gcd((y - x) >> 1, x)
},
_ => unreachable!(),
}
}
pub fn split(a: u128) -> (u64, u64) {
let al = a as u64;
let ah = (a >> 64) as u64;
(ah, al)
}
pub fn to_big_uint(x: u128) -> biguint::BigUint {
let (xh, xl) = split(x);
let (xhh, xhl) = biguint::split(xh);
let (xlh, xll) = biguint::split(xl);
let mut n = biguint::BigUint::from_limbs(&[xhh, xhl, xlh, xll]);
n.lstrip();
n
}
pub fn multiply_by_rational(mut a: u128, mut b: u128, mut c: u128) -> Result<u128, &'static str> {
if a.is_zero() || b.is_zero() { return Ok(Zero::zero()); }
c = c.max(1);
if b > a {
mem::swap(&mut a, &mut b);
}
if a % c == 0 {
a /= c;
c = 1;
} else if b % c == 0 {
b /= c;
c = 1;
}
if let Some(x) = a.checked_mul(b) {
Ok(x / c)
} else {
let a_num = to_big_uint(a);
let b_num = to_big_uint(b);
let c_num = to_big_uint(c);
let mut ab = a_num * b_num;
ab.lstrip();
let mut q = if c_num.len() == 1 {
ab.div_unit(c as biguint::Single)
} else {
let (mut q, r) = ab.div(&c_num, true).unwrap_or((Zero::zero(), Zero::zero()));
let r: u128 = r.try_into()
.expect("reminder of div by c is always less than c; qed");
if r > (c / 2) { q = q.add(&to_big_uint(1)); }
q
};
q.lstrip();
q.try_into().map_err(|_| "result cannot fit in u128")
}
}