Imports name this capability’s declared dependencies, which fune builds next to it in your project; each one links to its page.
use std::cmp::Ordering;
use std::fmt;
use super::funejson::Value; ← the fune runtime: the JSON value the test vectors use; fune build keeps it only where a signature takes one
/// The largest result, in bits, that power will build: about 19,700 decimal digits.
pub const MAX_POWER_BITS: u64 = 65536;
/// An integer of any size: sign and magnitude, the magnitude in 32-bit limbs,
/// least significant first, with no high zero limbs. Zero is never negative.
///
/// TypeScript and Python have this built in (`bigint`, `int`); Rust's standard
/// library does not, and the registry takes no crates, so this is the Rust
/// side of the same arithmetic. Schoolbook multiplication and shift-subtract
/// division: quadratic, and fast enough for the few-thousand-digit numbers
/// money and rate calculations reach.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BigInt {
negative: bool,
mag: Vec<u32>,
}
fn trim(v: &mut Vec<u32>) {
while let Some(&0) = v.last() {
v.pop();
}
}
fn mag_cmp(a: &[u32], b: &[u32]) -> Ordering {
if a.len() != b.len() {
return a.len().cmp(&b.len());
}
for i in (0..a.len()).rev() {
if a[i] != b[i] {
return a[i].cmp(&b[i]);
}
}
Ordering::Equal
}
fn mag_add(a: &[u32], b: &[u32]) -> Vec<u32> {
let n = a.len().max(b.len());
let mut out = Vec::with_capacity(n + 1);
let mut carry = 0u64;
for i in 0..n {
let x = *a.get(i).unwrap_or(&0) as u64;
let y = *b.get(i).unwrap_or(&0) as u64;
let t = x + y + carry;
out.push(t as u32);
carry = t >> 32;
}
if carry > 0 {
out.push(carry as u32);
}
trim(&mut out);
out
}
/// a - b for a >= b.
fn mag_sub(a: &[u32], b: &[u32]) -> Vec<u32> {
let mut out = Vec::with_capacity(a.len());
let mut borrow = 0i64;
for i in 0..a.len() {
let mut t = a[i] as i64 - *b.get(i).unwrap_or(&0) as i64 - borrow;
if t < 0 {
t += 1i64 << 32;
borrow = 1;
} else {
borrow = 0;
}
out.push(t as u32);
}
trim(&mut out);
out
}
fn mag_mul(a: &[u32], b: &[u32]) -> Vec<u32> {
if a.is_empty() || b.is_empty() {
return Vec::new();
}
let mut out = vec![0u32; a.len() + b.len()];
for i in 0..a.len() {
let mut carry = 0u64;
let x = a[i] as u64;
for j in 0..b.len() {
let t = out[i + j] as u64 + x * b[j] as u64 + carry;
out[i + j] = t as u32;
carry = t >> 32;
}
out[i + b.len()] = carry as u32;
}
trim(&mut out);
out
}
fn mag_bits(a: &[u32]) -> u64 {
match a.last() {
None => 0,
Some(&top) => (a.len() as u64 - 1) * 32 + (32 - top.leading_zeros() as u64),
}
}
fn mag_shl(a: &[u32], bits: u64) -> Vec<u32> {
if a.is_empty() {
return Vec::new();
}
let limbs = (bits / 32) as usize;
let rem = (bits % 32) as u32;
let mut out = vec![0u32; limbs];
if rem == 0 {
out.extend_from_slice(a);
} else {
let mut carry = 0u32;
for &x in a {
out.push((x << rem) | carry);
carry = x >> (32 - rem);
}
if carry > 0 {
out.push(carry);
}
}
trim(&mut out);
out
}
/// Quotient and remainder of magnitudes, by shift and subtract.
fn mag_divrem(a: &[u32], b: &[u32]) -> (Vec<u32>, Vec<u32>) {
if b.is_empty() {
panic!("division by zero");
}
if mag_cmp(a, b) == Ordering::Less {
return (Vec::new(), a.to_vec());
}
let shift = mag_bits(a) - mag_bits(b);
let mut quotient = vec![0u32; (shift / 32 + 1) as usize];
let mut rest = a.to_vec();
let mut s = shift as i64;
while s >= 0 {
let candidate = mag_shl(b, s as u64);
if mag_cmp(&rest, &candidate) != Ordering::Less {
rest = mag_sub(&rest, &candidate);
quotient[(s / 32) as usize] |= 1u32 << (s % 32);
}
s -= 1;
}
trim(&mut quotient);
(quotient, rest)
}
fn mag_divrem_small(a: &[u32], d: u32) -> (Vec<u32>, u32) {
let mut out = vec![0u32; a.len()];
let mut rem = 0u64;
for i in (0..a.len()).rev() {
let cur = (rem << 32) | a[i] as u64;
out[i] = (cur / d as u64) as u32;
rem = cur % d as u64;
}
trim(&mut out);
(out, rem as u32)
}
impl BigInt {
fn make(negative: bool, mut mag: Vec<u32>) -> BigInt {
trim(&mut mag);
let negative = negative && !mag.is_empty();
BigInt { negative, mag }
}
pub fn zero() -> BigInt {
BigInt { negative: false, mag: Vec::new() }
}
pub fn from_i128(value: i128) -> BigInt {
let mut m = value.unsigned_abs();
let mut mag = Vec::new();
while m > 0 {
mag.push(m as u32);
m >>= 32;
}
BigInt::make(value < 0, mag)
}
pub fn from_i64(value: i64) -> BigInt {
BigInt::from_i128(value as i128)
}
pub fn is_zero(&self) -> bool {
self.mag.is_empty()
}
pub fn is_negative(&self) -> bool {
self.negative
}
/// Bits in the magnitude; 0 for zero.
pub fn bit_length(&self) -> u64 {
mag_bits(&self.mag)
}
pub fn neg(&self) -> BigInt {
BigInt::make(!self.negative, self.mag.clone())
}
pub fn abs(&self) -> BigInt {
BigInt::make(false, self.mag.clone())
}
pub fn add(&self, other: &BigInt) -> BigInt {
if self.negative == other.negative {
return BigInt::make(self.negative, mag_add(&self.mag, &other.mag));
}
match mag_cmp(&self.mag, &other.mag) {
Ordering::Equal => BigInt::zero(),
Ordering::Greater => BigInt::make(self.negative, mag_sub(&self.mag, &other.mag)),
Ordering::Less => BigInt::make(other.negative, mag_sub(&other.mag, &self.mag)),
}
}
pub fn sub(&self, other: &BigInt) -> BigInt {
self.add(&other.neg())
}
pub fn mul(&self, other: &BigInt) -> BigInt {
BigInt::make(self.negative != other.negative, mag_mul(&self.mag, &other.mag))
}
/// Quotient truncated towards zero, and the remainder with the sign of self.
///
/// # Panics
/// Panics if `other` is zero.
pub fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
let (q, r) = mag_divrem(&self.mag, &other.mag);
(
BigInt::make(self.negative != other.negative, q),
BigInt::make(self.negative, r),
)
}
/// Quotient truncated towards zero.
pub fn div(&self, other: &BigInt) -> BigInt {
self.div_rem(other).0
}
/// Quotient truncated towards zero by a small positive divisor, and the
/// remainder of the magnitude. Much faster than `div_rem` for scaling by
/// powers of ten.
///
/// # Panics
/// Panics if `divisor` is zero.
pub fn div_rem_small(&self, divisor: u32) -> (BigInt, u32) {
if divisor == 0 {
panic!("division by zero");
}
let (q, r) = mag_divrem_small(&self.mag, divisor);
(BigInt::make(self.negative, q), r)
}
/// Remainder with the sign of self.
pub fn rem(&self, other: &BigInt) -> BigInt {
self.div_rem(other).1
}
/// # Panics
/// Panics beyond MAX_POWER_BITS, as the other languages do.
pub fn pow(&self, exponent: u64) -> BigInt {
if mag_cmp(&self.mag, &[1]) != Ordering::Greater {
if exponent == 0 {
return BigInt::from_i64(1);
}
if self.negative {
return BigInt::from_i64(if exponent % 2 == 0 { 1 } else { -1 });
}
return self.clone();
}
if (self.bit_length() as u128) * (exponent as u128) > MAX_POWER_BITS as u128 {
panic!("result too large: power is limited to {} bits", MAX_POWER_BITS);
}
let mut result = BigInt::from_i64(1);
let mut base = self.clone();
let mut e = exponent;
while e > 0 {
if e & 1 == 1 {
result = result.mul(&base);
}
e >>= 1;
if e > 0 {
base = base.mul(&base);
}
}
result
}
/// # Panics
/// Panics if the value does not fit in an i128.
pub fn to_i128(&self) -> i128 {
if self.bit_length() > 127 {
panic!("value does not fit in 128 bits");
}
let mut m: u128 = 0;
for &limb in self.mag.iter().rev() {
m = (m << 32) | limb as u128;
}
if self.negative {
-(m as i128)
} else {
m as i128
}
}
/// # Panics
/// Panics if the value does not fit in an i64.
pub fn to_i64(&self) -> i64 {
let v = self.to_i128();
if v > i64::MAX as i128 || v < i64::MIN as i128 {
panic!("value does not fit in 64 bits");
}
v as i64
}
}
impl Ord for BigInt {
fn cmp(&self, other: &BigInt) -> Ordering {
match (self.negative, other.negative) {
(false, true) => Ordering::Greater,
(true, false) => Ordering::Less,
(false, false) => mag_cmp(&self.mag, &other.mag),
(true, true) => mag_cmp(&other.mag, &self.mag),
}
}
}
impl PartialOrd for BigInt {
fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl fmt::Display for BigInt {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.mag.is_empty() {
return write!(f, "0");
}
let mut chunks: Vec<u32> = Vec::new();
let mut rest = self.mag.clone();
while !rest.is_empty() {
let (q, r) = mag_divrem_small(&rest, 1_000_000_000);
chunks.push(r);
rest = q;
}
let mut text = String::new();
if self.negative {
text.push('-');
}
text.push_str(&chunks.last().unwrap().to_string());
for chunk in chunks.iter().rev().skip(1) {
text.push_str(&format!("{:09}", chunk));
}
write!(f, "{}", text)
}
}
/// Parse the registry's decimal integer form. "-0", "+1", "01" and " 1" are refused.
///
/// # Panics
/// Panics on anything else.
pub fn parse_big_integer(text: &str) -> BigInt {
let (negative, digits) = match text.strip_prefix('-') {
Some(rest) => (true, rest),
None => (false, text),
};
let valid = !digits.is_empty()
&& digits.bytes().all(|b| b.is_ascii_digit())
&& (digits == "0" || !digits.starts_with('0'))
&& !(negative && digits == "0");
if !valid {
panic!("not a whole number in decimal: \"{}\"", text);
}
let mut mag: Vec<u32> = Vec::new();
for b in digits.bytes() {
let mut carry = (b - b'0') as u64;
for limb in mag.iter_mut() {
let t = *limb as u64 * 10 + carry;
*limb = t as u32;
carry = t >> 32;
}
if carry > 0 {
mag.push(carry as u32);
}
}
BigInt::make(negative, mag)
}
/// Raise to a power, refusing results beyond MAX_POWER_BITS before building them.
///
/// # Panics
/// Panics on a negative exponent or a result that would be too large.
pub fn power_big_integer(base: &BigInt, exponent: &BigInt) -> BigInt {
if exponent.is_negative() {
panic!("exponent must not be negative");
}
if base.abs() <= BigInt::from_i64(1) {
if exponent.is_zero() {
return BigInt::from_i64(1);
}
if base.is_negative() {
let even = exponent.rem(&BigInt::from_i64(2)).is_zero();
return BigInt::from_i64(if even { 1 } else { -1 });
}
return base.clone();
}
if exponent.bit_length() > 32
|| (base.bit_length() as u128) * (exponent.to_i128() as u128) > MAX_POWER_BITS as u128
{
panic!("result too large: power is limited to {} bits", MAX_POWER_BITS);
}
base.pow(exponent.to_i64() as u64)
}
/// Exact integer arithmetic on decimal strings. Division truncates towards
/// zero and the remainder takes the sign of the dividend, as in TypeScript.
///
/// # Panics
/// Panics on malformed numbers, division by zero, a negative or oversized
/// power, or an unknown operation.
pub fn calculate_big_integer(a: &str, op: &str, b: &str) -> String {
let x = parse_big_integer(a);
let y = parse_big_integer(b);
match op {
"add" => x.add(&y).to_string(),
"subtract" => x.sub(&y).to_string(),
"multiply" => x.mul(&y).to_string(),
"divide" => {
if y.is_zero() {
panic!("division by zero");
}
x.div(&y).to_string()
}
"remainder" => {
if y.is_zero() {
panic!("division by zero");
}
x.rem(&y).to_string()
}
"power" => power_big_integer(&x, &y).to_string(),
other => panic!("unknown operation \"{}\"", other),
}
}
pub fn fune_vector(args: &[Value]) -> Value {
Value::str(&calculate_big_integer(
args[0].as_str(),
args[1].as_str(),
args[2].as_str(),
))
}