use byteorder::{
self,
ByteOrder,
};
use std::cmp::Ordering;
use std::convert::TryFrom;
use std::fmt;
use std::marker::PhantomData;
use crate::{
bigint::{
common::{
BigEndian,
BinaryRepresentation,
Error,
LittleEndian,
U32Repr,
U8Repr,
},
t243,
utils::{
OverflowingAddExt,
SplitInteger,
},
I384,
T242,
T243,
},
Utrit,
};
mod constants;
pub use constants::{
BE_U32_0,
BE_U32_1,
BE_U32_2,
BE_U32_HALF_MAX,
BE_U32_HALF_MAX_T242,
BE_U32_MAX,
BE_U8_0,
BE_U8_1,
BE_U8_2,
BE_U8_MAX,
LE_U32_0,
LE_U32_1,
LE_U32_2,
LE_U32_HALF_MAX,
LE_U32_HALF_MAX_T242,
LE_U32_NEG_HALF_MAX_T242,
LE_U32_ONLY_T243_OCCUPIED,
LE_U32_MAX,
LE_U32_MAX_T242,
LE_U8_0,
LE_U8_1,
LE_U8_2,
LE_U8_MAX,
};
#[derive(Clone, Copy)]
pub struct U384<E, T> {
pub(crate) inner: T,
_phantom: PhantomData<E>,
}
impl<E, T> U384<E, T> {
pub fn inner_ref(&self) -> &T {
&self.inner
}
}
impl<E: fmt::Debug, R: BinaryRepresentation, D> fmt::Debug for U384<E, R>
where
E: fmt::Debug,
R: BinaryRepresentation<T = D>,
D: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("U384")
.field("inner", &self.inner.iter())
.field("_phantom", &self._phantom)
.finish()
}
}
impl U384<BigEndian, U32Repr> {
pub fn as_i384(self) -> I384<BigEndian, U32Repr> {
I384::<BigEndian, U32Repr>::from_array(self.inner)
}
pub fn shift_into_i384(mut self) -> I384<BigEndian, U32Repr> {
self.sub_inplace(*BE_U32_HALF_MAX);
self.sub_inplace(Self::one());
self.as_i384()
}
pub fn add_inplace(&mut self, other: Self) {
let mut overflown = false;
let self_iter = self.inner.iter_mut().rev();
let other_iter = other.inner.iter().rev();
for (s, o) in self_iter.zip(other_iter) {
let (sum, still_overflown) = s.overflowing_add_with_carry(*o, overflown as u32);
*s = sum;
overflown = still_overflown;
}
}
pub fn add_digit_inplace<T: Into<u32>>(&mut self, other: T) -> usize {
let other = other.into();
let mut i = self.inner.len() - 1;
let (sum, mut overflown) = self.inner[i].overflowing_add(other);
self.inner[i] = sum;
i -= 1;
while overflown {
let (sum, still_overflown) = self.inner[i].overflowing_add(1u32);
self.inner[i] = sum;
overflown = still_overflown;
i -= 1;
}
i
}
pub fn divide_by_two(&mut self) {
let mut i = self.inner.len() - 1;
while i < self.inner.len() - 1 {
let (left_slice, right_slice) = self.inner.split_at_mut(i + 1);
let left = &mut left_slice[i];
let right = &mut right_slice[0];
*left >>= 1;
*left |= *right << 31;
i -= 1;
}
self.inner[0] >>= 1;
}
pub fn from_t242(trits: T242<Utrit>) -> Self {
let u384_le = U384::<LittleEndian, U32Repr>::from_t242(trits);
u384_le.into()
}
pub fn sub_inplace(&mut self, other: Self) {
let self_iter = self.inner.iter_mut().rev();
let other_iter = other.inner.iter().rev();
let mut borrow = true;
for (s, o) in self_iter.zip(other_iter) {
let (sum, has_overflown) = s.overflowing_add_with_carry(!*o, borrow as u32);
*s = sum;
borrow = has_overflown;
}
}
pub fn try_from_t243(trits: T243<Utrit>) -> Result<Self, Error> {
let u384_le = U384::<LittleEndian, U32Repr>::try_from_t243(trits)?;
Ok(u384_le.into())
}
}
impl U384<LittleEndian, U32Repr> {
pub fn as_i384(self) -> I384<LittleEndian, U32Repr> {
I384::<LittleEndian, U32Repr>::from_array(self.inner)
}
pub fn add_inplace(&mut self, other: Self) {
let mut overflown = false;
let self_iter = self.inner.iter_mut();
let other_iter = other.inner.iter();
for (s, o) in self_iter.zip(other_iter) {
let (sum, still_overflown) = s.overflowing_add_with_carry(*o, overflown as u32);
*s = sum;
overflown = still_overflown;
}
}
pub fn add_digit_inplace<T: Into<u32>>(&mut self, other: T) -> usize {
let other = other.into();
let (sum, mut overflown) = self.inner[0].overflowing_add(other);
self.inner[0] = sum;
let mut i = 1;
while overflown {
let (sum, still_overflown) = self.inner[i].overflowing_add(1u32);
self.inner[i] = sum;
overflown = still_overflown;
i += 1;
}
i
}
pub fn divide_by_two(&mut self) {
let mut i = 0;
while i < self.inner.len() - 1 {
let (left_slice, right_slice) = self.inner.split_at_mut(i + 1);
let left = &mut left_slice[i];
let right = &mut right_slice[0];
*left >>= 1;
*left |= *right << 31;
i += 1;
}
self.inner[self.inner.len() - 1] >>= 1;
}
pub fn from_t242(trits: T242<Utrit>) -> Self {
let t243 = trits.into_t243();
Self::try_from_t243(t243).unwrap()
}
pub fn shift_into_i384(mut self) -> I384<LittleEndian, U32Repr> {
self.sub_inplace(*LE_U32_HALF_MAX);
self.sub_inplace(Self::one());
self.as_i384()
}
pub fn sub_inplace(&mut self, other: Self) {
let self_iter = self.inner.iter_mut();
let other_iter = other.inner.iter();
let mut borrow = true;
for (s, o) in self_iter.zip(other_iter) {
let (sum, has_overflown) = s.overflowing_add_with_carry(!*o, borrow as u32);
*s = sum;
borrow = has_overflown;
}
}
pub fn try_from_t243(trits: T243<Utrit>) -> Result<Self, Error> {
if trits > *t243::UTRIT_U384_MAX {
Err(Error::TernaryExceedsBinaryRange)?
}
let mut accumulator = Self::zero();
let mut accumulator_extent = 1;
let mut binary_trits_iterator = trits.inner_ref().as_i8_slice().iter().rev().peekable();
while let Some(0) = binary_trits_iterator.peek() {
binary_trits_iterator.next();
}
for binary_trit in binary_trits_iterator {
let mut carry: u32 = 0;
for digit in accumulator.inner[0..accumulator_extent].iter_mut() {
let new_digit = *digit as u64 * 3u64 + carry as u64;
*digit = new_digit.lo();
carry = new_digit.hi();
}
if carry != 0 {
unsafe {
*accumulator.inner.get_unchecked_mut(accumulator_extent) = carry;
}
accumulator_extent += 1;
}
let new_extent = accumulator.add_digit_inplace(*binary_trit as u32);
if new_extent > accumulator_extent {
accumulator_extent = new_extent;
}
}
Ok(accumulator)
}
}
impl_const_functions!(
( U384 ),
{ BigEndian, LittleEndian },
{ U8Repr, U32Repr }
);
impl_constants!(
U384<BigEndian, U8Repr> => [
(zero, BE_U8_0),
(one, BE_U8_1),
(two, BE_U8_2),
(max, BE_U8_MAX),
],
U384<LittleEndian, U8Repr> => [
(zero, LE_U8_0),
(one, LE_U8_1),
(two, LE_U8_2),
(max, LE_U8_MAX),
],
U384<BigEndian, U32Repr> => [
(zero, BE_U32_0),
(one, BE_U32_1),
(two, BE_U32_2),
(max, BE_U32_MAX),
],
U384<LittleEndian, U32Repr> => [
(zero, LE_U32_0),
(one, LE_U32_1),
(two, LE_U32_2),
(max, LE_U32_MAX),
],
);
impl From<U384<BigEndian, U32Repr>> for U384<BigEndian, U8Repr> {
fn from(value: U384<BigEndian, U32Repr>) -> Self {
let mut u384_u8 = Self::zero();
byteorder::BigEndian::write_u32_into(&value.inner, &mut u384_u8.inner);
u384_u8
}
}
impl From<U384<LittleEndian, U8Repr>> for U384<LittleEndian, U32Repr> {
fn from(value: U384<LittleEndian, U8Repr>) -> Self {
let mut u384_u32 = U384::<LittleEndian, U32Repr>::zero();
byteorder::LittleEndian::read_u32_into(&value.inner, &mut u384_u32.inner);
u384_u32
}
}
impl From<T242<Utrit>> for U384<LittleEndian, U32Repr> {
fn from(value: T242<Utrit>) -> Self {
Self::from_t242(value)
}
}
impl Eq for U384<LittleEndian, U32Repr> {}
impl PartialEq for U384<LittleEndian, U32Repr> {
fn eq(&self, other: &Self) -> bool {
self.inner == other.inner
}
}
impl PartialOrd for U384<LittleEndian, U32Repr> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
use Ordering::*;
let self_iter = self.inner.iter().rev();
let other_iter = other.inner.iter().rev();
let zipped_iter = self_iter.zip(other_iter);
for (s, o) in zipped_iter {
if s > o {
return Some(Greater);
} else if s < o {
return Some(Less);
}
}
Some(Equal)
}
}
impl Ord for U384<LittleEndian, U32Repr> {
fn cmp(&self, other: &Self) -> Ordering {
match self.partial_cmp(other) {
Some(ordering) => ordering,
None => unreachable!(),
}
}
}
impl TryFrom<T243<Utrit>> for U384<LittleEndian, U32Repr> {
type Error = Error;
fn try_from(value: T243<Utrit>) -> Result<Self, Self::Error> {
Self::try_from_t243(value)
}
}
impl_toggle_endianness!((U384), U8Repr, U32Repr);
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn half_max_plus_half_max_is_max_minus_1() {
let mut left = *LE_U32_HALF_MAX;
left.add_inplace(*LE_U32_HALF_MAX);
let mut right = LE_U32_MAX;
right.sub_inplace(LE_U32_1);
assert_eq!(left, right);
}
test_binary_op!(
[zero_plus_one_is_one, add_inplace, LE_U32_0, LE_U32_1, LE_U32_1],
[zero_plus_two_is_two, add_inplace, LE_U32_0, LE_U32_2, LE_U32_2],
[zero_minus_one_is_max, sub_inplace, LE_U32_0, LE_U32_1, LE_U32_MAX],
[zero_plus_max_is_max, add_inplace, LE_U32_0, LE_U32_MAX, LE_U32_MAX],
[one_minus_one_is_zero, sub_inplace, LE_U32_1, LE_U32_1, LE_U32_0],
[one_minus_two_is_max, sub_inplace, LE_U32_1, LE_U32_2, LE_U32_MAX],
[one_plus_one_is_two, add_inplace, LE_U32_1, LE_U32_1, LE_U32_2],
[max_minus_max_is_zero, sub_inplace, LE_U32_MAX, LE_U32_MAX, LE_U32_0],
[max_minus_zero_is_max, sub_inplace, LE_U32_MAX, LE_U32_0, LE_U32_MAX],
[max_plus_zero_is_max, add_inplace, LE_U32_MAX, LE_U32_0, LE_U32_MAX],
[max_plus_one_is_zero, add_inplace, LE_U32_MAX, LE_U32_1, LE_U32_0],
[max_plus_two_is_one, add_inplace, LE_U32_MAX, LE_U32_2, LE_U32_1],
);
test_binary_op_calc_result!([
max_plus_max_is_max_minus_one,
add_inplace,
LE_U32_MAX,
LE_U32_MAX,
sub_inplace,
LE_U32_MAX,
LE_U32_1
],);
}