use encodings::hex::{FromHex, FromHexError, ToHex};
use std::fmt;
#[cfg(feature = "rng")]
use rand::{thread_rng, Rng};
pub trait BitArray {
fn bit(&self, idx: usize) -> bool;
fn bit_slice(&self, start: usize, end: usize) -> Self;
fn mask(&self, n: usize) -> Self;
fn trailing_zeros(&self) -> usize;
fn zero() -> Self;
fn one() -> Self;
}
#[repr(C)]
pub struct Uint256(pub [u64; 4]);
impl<'a> From<&'a [u64]> for Uint256 {
fn from(data: &'a [u64]) -> Uint256 {
assert_eq!(data.len(), 4);
let mut ret = [0; 4];
ret.copy_from_slice(&data[..]);
Uint256(ret)
}
}
impl From<u32> for Uint256 {
fn from(value: u32) -> Uint256 {
let mut ret = [0; 4];
ret[0] = value as u64;
Uint256(ret)
}
}
impl From<u64> for Uint256 {
fn from(value: u64) -> Uint256 {
let mut ret = [0; 4];
ret[0] = value;
Uint256(ret)
}
}
impl From<[u8; 32]> for Uint256 {
fn from(value: [u8; 32]) -> Uint256 {
let mut ret = [0; 4];
for i in 0..4 {
let start = 0 + i * 8;
let end = 8 + i * 8;
let mut bytes = [0; 8];
bytes.copy_from_slice(&value[start..end]);
ret[i] = u64::from_be_bytes(bytes);
}
Uint256(ret)
}
}
impl FromHex for Uint256 {
type Error = FromHexError;
fn from_hex<T: AsRef<[u8]>>(hex: T) -> std::result::Result<Self, Self::Error> {
let bytes = Vec::from_hex(hex)?;
if bytes.len() != 32 {
Err(FromHexError::InvalidHexLength)
} else {
let mut ret = [0; 32];
ret.copy_from_slice(&bytes);
Ok(Uint256::from(ret))
}
}
}
impl ::std::ops::Index<usize> for Uint256 {
type Output = u64;
#[inline]
fn index(&self, index: usize) -> &u64 {
let &Uint256(ref dat) = self;
&dat[index]
}
}
impl ::std::ops::Index<::std::ops::Range<usize>> for Uint256 {
type Output = [u64];
#[inline]
fn index(&self, index: ::std::ops::Range<usize>) -> &[u64] {
&self.0[index]
}
}
impl ::std::ops::Index<::std::ops::RangeTo<usize>> for Uint256 {
type Output = [u64];
#[inline]
fn index(&self, index: ::std::ops::RangeTo<usize>) -> &[u64] {
&self.0[index]
}
}
impl ::std::ops::Index<::std::ops::RangeFrom<usize>> for Uint256 {
type Output = [u64];
#[inline]
fn index(&self, index: ::std::ops::RangeFrom<usize>) -> &[u64] {
&self.0[index]
}
}
impl ::std::ops::Index<::std::ops::RangeFull> for Uint256 {
type Output = [u64];
#[inline]
fn index(&self, _: ::std::ops::RangeFull) -> &[u64] {
&self.0[..]
}
}
impl PartialEq for Uint256 {
#[inline]
fn eq(&self, other: &Uint256) -> bool {
&self[..] == &other[..]
}
}
impl Eq for Uint256 {}
impl PartialOrd for Uint256 {
#[inline]
fn partial_cmp(&self, other: &Uint256) -> Option<::std::cmp::Ordering> {
Some(self.cmp(&other))
}
}
impl Ord for Uint256 {
#[inline]
fn cmp(&self, other: &Uint256) -> ::std::cmp::Ordering {
for i in 0..4 {
if self[4 - 1 - i] < other[4 - 1 - i] {
return ::std::cmp::Ordering::Less;
}
if self[4 - 1 - i] > other[4 - 1 - i] {
return ::std::cmp::Ordering::Greater;
}
}
::std::cmp::Ordering::Equal
}
}
#[cfg_attr(feature = "clippy", allow(expl_impl_clone_on_copy))]
impl Clone for Uint256 {
#[inline]
fn clone(&self) -> Uint256 {
Uint256::from(&self[..])
}
}
impl Copy for Uint256 {}
impl Uint256 {
#[cfg(feature = "rng")]
pub fn random() -> Self {
let mut rng = thread_rng();
let mut arr = [0_u64; 4];
rng.fill(&mut arr);
Uint256(arr)
}
#[inline]
pub fn as_ptr(&self) -> *const u64 {
let &Uint256(ref dat) = self;
dat.as_ptr()
}
#[inline]
pub fn as_mut_ptr(&mut self) -> *mut u64 {
let &mut Uint256(ref mut dat) = self;
dat.as_mut_ptr()
}
#[inline]
pub fn len(&self) -> usize {
4
}
#[inline]
pub fn is_empty(&self) -> bool {
false
}
#[inline]
pub fn as_bytes(&self) -> &[u64; 4] {
&self.0
}
#[inline]
pub fn to_bytes(&self) -> [u64; 4] {
self.0.clone()
}
#[inline]
pub fn to_le_bytes(&self) -> [u8; 32] {
let mut bytes = [0; 32];
for i in 0..4 {
let le_bytes = self.0[i].to_le_bytes();
bytes[8 * i] = le_bytes[0];
bytes[1 + 8 * i] = le_bytes[1];
bytes[2 + 8 * i] = le_bytes[2];
bytes[3 + 8 * i] = le_bytes[3];
bytes[4 + 8 * i] = le_bytes[4];
bytes[5 + 8 * i] = le_bytes[5];
bytes[6 + 8 * i] = le_bytes[6];
bytes[7 + 8 * i] = le_bytes[7];
}
bytes
}
#[inline]
pub fn max_value() -> Self {
let mut result = [0; 4];
for i in 0..4 {
result[i] = u64::max_value();
}
Uint256(result)
}
#[inline]
pub fn into_bytes(self) -> [u64; 4] {
self.0
}
#[inline]
pub fn low_u32(&self) -> u32 {
let &Uint256(ref arr) = self;
arr[0] as u32
}
#[inline]
pub fn low_u64(&self) -> u64 {
let &Uint256(ref arr) = self;
arr[0] as u64
}
#[inline]
pub fn bits(&self) -> usize {
let &Uint256(ref arr) = self;
for i in 1..4 {
if arr[4 - i] > 0 {
return (0x40 * (4 - i + 1)) - arr[4 - i].leading_zeros() as usize;
}
}
0x40 - arr[0].leading_zeros() as usize
}
pub fn mul_u32(self, other: u32) -> Uint256 {
let Uint256(ref arr) = self;
let mut carry = [0u64; 4];
let mut ret = [0u64; 4];
for i in 0..4 {
let not_last_word = i < 4 - 1;
let upper = other as u64 * (arr[i] >> 32);
let lower = other as u64 * (arr[i] & 0xFFFFFFFF);
if not_last_word {
carry[i + 1] += upper >> 32;
}
let (sum, overflow) = lower.overflowing_add(upper << 32);
ret[i] = sum;
if overflow && not_last_word {
carry[i + 1] += 1;
}
}
Uint256(ret) + Uint256(carry)
}
pub fn from_u64(init: u64) -> Option<Uint256> {
let mut ret = [0; 4];
ret[0] = init;
Some(Uint256(ret))
}
pub fn from_i64(init: i64) -> Option<Uint256> {
assert!(init >= 0);
Uint256::from_u64(init as u64)
}
pub fn from_big_endian(slice: &[u8]) -> Self {
assert!(4 * 8 >= slice.len());
assert!(slice.len() % 8 == 0);
let mut ret = [0; 4];
let length = slice.len() / 8;
for i in 0..length {
let start = 0 + i * 8;
let end = 8 + i * 8;
let mut bytes = [0; 8];
bytes.copy_from_slice(&slice[start..end]);
ret[3 - i] = u64::from_be_bytes(bytes);
}
Uint256(ret)
}
pub fn from_bytes(slice: &[u8]) -> Self {
assert!(4 * 8 >= slice.len());
assert!(slice.len() % 8 == 0);
let mut ret = [0; 4];
let length = slice.len() / 8;
for i in 0..length {
let start = 0 + i * 8;
let end = 8 + i * 8;
let mut bytes = [0; 8];
bytes.copy_from_slice(&slice[start..end]);
ret[i] = u64::from_le_bytes(bytes);
}
Uint256(ret)
}
#[inline]
pub fn increment(&mut self) {
let &mut Uint256(ref mut arr) = self;
arr[0] += 1;
if arr[0] == 0 {
arr[1] += 1;
if arr[1] == 0 {
arr[2] += 1;
if arr[2] == 0 {
arr[3] += 1;
}
}
}
}
}
impl ::std::ops::Add<Uint256> for Uint256 {
type Output = Uint256;
fn add(self, other: Uint256) -> Uint256 {
let Uint256(ref me) = self;
let Uint256(ref you) = other;
let mut ret = [0u64; 4];
let mut carry = [0u64; 4];
let mut b_carry = false;
for i in 0..4 {
ret[i] = me[i].wrapping_add(you[i]);
if i < 4 - 1 && ret[i] < me[i] {
carry[i + 1] = 1;
b_carry = true;
}
}
if b_carry {
Uint256(ret) + Uint256(carry)
} else {
Uint256(ret)
}
}
}
impl ::std::ops::Sub<Uint256> for Uint256 {
type Output = Uint256;
#[inline]
fn sub(self, other: Uint256) -> Uint256 {
self + !other + BitArray::one()
}
}
impl ::std::ops::Mul<Uint256> for Uint256 {
type Output = Uint256;
fn mul(self, other: Uint256) -> Uint256 {
let mut me = Uint256::zero();
for i in 0..(2 * 4) {
let to_mul = (other >> (32 * i)).low_u32();
me = me + (self.mul_u32(to_mul) << (32 * i));
}
me
}
}
impl ::std::ops::Div<Uint256> for Uint256 {
type Output = Uint256;
fn div(self, other: Uint256) -> Uint256 {
let mut sub_copy = self;
let mut shift_copy = other;
let mut ret = [0u64; 4];
let my_bits = self.bits();
let your_bits = other.bits();
assert!(your_bits != 0);
if my_bits < your_bits {
return Uint256(ret);
}
let mut shift = my_bits - your_bits;
shift_copy = shift_copy << shift;
loop {
if sub_copy >= shift_copy {
ret[shift / 64] |= 1 << (shift % 64);
sub_copy = sub_copy - shift_copy;
}
shift_copy = shift_copy >> 1;
if shift == 0 {
break;
}
shift -= 1;
}
Uint256(ret)
}
}
impl BitArray for Uint256 {
#[inline]
fn bit(&self, index: usize) -> bool {
let &Uint256(ref arr) = self;
arr[index / 64] & (1 << (index % 64)) != 0
}
#[inline]
fn bit_slice(&self, start: usize, end: usize) -> Uint256 {
(*self >> start).mask(end - start)
}
#[inline]
fn mask(&self, n: usize) -> Uint256 {
let &Uint256(ref arr) = self;
let mut ret = [0; 4];
for i in 0..4 {
if n >= 0x40 * (i + 1) {
ret[i] = arr[i];
} else {
ret[i] = arr[i] & ((1 << (n - 0x40 * i)) - 1);
break;
}
}
Uint256(ret)
}
#[inline]
fn trailing_zeros(&self) -> usize {
let &Uint256(ref arr) = self;
for i in 0..(4 - 1) {
if arr[i] > 0 {
return (0x40 * i) + arr[i].trailing_zeros() as usize;
}
}
(0x40 * (4 - 1)) + arr[4 - 1].trailing_zeros() as usize
}
fn zero() -> Uint256 {
Uint256([0; 4])
}
fn one() -> Uint256 {
Uint256({
let mut ret = [0; 4];
ret[0] = 1;
ret
})
}
}
impl ::std::default::Default for Uint256 {
fn default() -> Uint256 {
BitArray::zero()
}
}
impl ::std::ops::BitAnd<Uint256> for Uint256 {
type Output = Uint256;
#[inline]
fn bitand(self, other: Uint256) -> Uint256 {
let Uint256(ref arr1) = self;
let Uint256(ref arr2) = other;
let mut ret = [0u64; 4];
for i in 0..4 {
ret[i] = arr1[i] & arr2[i];
}
Uint256(ret)
}
}
impl ::std::ops::BitXor<Uint256> for Uint256 {
type Output = Uint256;
#[inline]
fn bitxor(self, other: Uint256) -> Uint256 {
let Uint256(ref arr1) = self;
let Uint256(ref arr2) = other;
let mut ret = [0u64; 4];
for i in 0..4 {
ret[i] = arr1[i] ^ arr2[i];
}
Uint256(ret)
}
}
impl ::std::ops::BitOr<Uint256> for Uint256 {
type Output = Uint256;
#[inline]
fn bitor(self, other: Uint256) -> Uint256 {
let Uint256(ref arr1) = self;
let Uint256(ref arr2) = other;
let mut ret = [0u64; 4];
for i in 0..4 {
ret[i] = arr1[i] | arr2[i];
}
Uint256(ret)
}
}
impl ::std::ops::Not for Uint256 {
type Output = Uint256;
#[inline]
fn not(self) -> Uint256 {
let Uint256(ref arr) = self;
let mut ret = [0u64; 4];
for i in 0..4 {
ret[i] = !arr[i];
}
Uint256(ret)
}
}
impl ::std::ops::Shl<usize> for Uint256 {
type Output = Uint256;
fn shl(self, shift: usize) -> Uint256 {
let Uint256(ref original) = self;
let mut ret = [0u64; 4];
let word_shift = shift / 64;
let bit_shift = shift % 64;
for i in 0..4 {
if bit_shift < 64 && i + word_shift < 4 {
ret[i + word_shift] += original[i] << bit_shift;
}
if bit_shift > 0 && i + word_shift + 1 < 4 {
ret[i + word_shift + 1] += original[i] >> (64 - bit_shift);
}
}
Uint256(ret)
}
}
impl ::std::ops::Shr<usize> for Uint256 {
type Output = Uint256;
fn shr(self, shift: usize) -> Uint256 {
let Uint256(ref original) = self;
let mut ret = [0u64; 4];
let word_shift = shift / 64;
let bit_shift = shift % 64;
for i in word_shift..4 {
ret[i - word_shift] += original[i] >> bit_shift;
if bit_shift > 0 && i < 4 - 1 {
ret[i - word_shift] += original[i + 1] << (64 - bit_shift);
}
}
Uint256(ret)
}
}
impl ToHex for Uint256 {
fn to_hex(&self) -> String {
let mut hex = "".to_owned();
for bytes in self.0.iter() {
hex.push_str(&bytes.to_le_bytes().to_vec().to_hex());
}
hex
}
}
impl fmt::Debug for Uint256 {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let &Uint256(ref data) = self;
write!(f, "0x")?;
for ch in data.iter().rev() {
write!(f, "{:016x}", ch)?;
}
Ok(())
}
}
impl fmt::Display for Uint256 {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
<fmt::Debug>::fmt(self, f)
}
}
#[cfg(feature = "serialization")]
impl serde::Serialize for Uint256 {
fn serialize<S: serde::Serializer>(&self, s: S) -> std::result::Result<S::Ok, S::Error> {
if s.is_human_readable() {
s.serialize_str(&self.to_hex())
} else {
s.serialize_bytes(&self.to_le_bytes())
}
}
}
#[cfg(feature = "serialization")]
impl<'de> serde::Deserialize<'de> for Uint256 {
fn deserialize<D: serde::Deserializer<'de>>(d: D) -> std::result::Result<Uint256, D::Error> {
if d.is_human_readable() {
struct HexVisitor;
impl<'de> serde::de::Visitor<'de> for HexVisitor {
type Value = Uint256;
fn expecting(&self, formatter: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
formatter.write_str("an ASCII hex string")
}
fn visit_bytes<E>(self, v: &[u8]) -> std::result::Result<Self::Value, E>
where
E: ::serde::de::Error,
{
if let Ok(hex) = ::std::str::from_utf8(v) {
Uint256::from_hex(hex).map_err(E::custom)
} else {
return Err(E::invalid_value(serde::de::Unexpected::Bytes(v), &self));
}
}
fn visit_str<E>(self, v: &str) -> std::result::Result<Self::Value, E>
where
E: ::serde::de::Error,
{
Uint256::from_hex(v).map_err(E::custom)
}
}
d.deserialize_str(HexVisitor)
} else {
struct BytesVisitor;
impl<'de> ::serde::de::Visitor<'de> for BytesVisitor {
type Value = Uint256;
fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
formatter.write_str("a bytestring")
}
fn visit_bytes<E>(self, v: &[u8]) -> std::result::Result<Self::Value, E>
where
E: ::serde::de::Error,
{
if v.len() != 32 {
Err(E::invalid_length(v.len(), &stringify!(32)))
} else {
let mut ret = [0; 32];
ret.copy_from_slice(v);
Ok(Uint256::from(ret))
}
}
}
d.deserialize_bytes(BytesVisitor)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
pub fn uint256_bits_test() {
assert_eq!(Uint256::from_u64(255).unwrap().bits(), 8);
assert_eq!(Uint256::from_u64(256).unwrap().bits(), 9);
assert_eq!(Uint256::from_u64(300).unwrap().bits(), 9);
assert_eq!(Uint256::from_u64(60000).unwrap().bits(), 16);
assert_eq!(Uint256::from_u64(70000).unwrap().bits(), 17);
let mut shl = Uint256::from_u64(70000).unwrap();
shl = shl << 100;
assert_eq!(shl.bits(), 117);
shl = shl << 100;
assert_eq!(shl.bits(), 217);
shl = shl << 100;
assert_eq!(shl.bits(), 0);
assert!(!Uint256::from_u64(10).unwrap().bit(0));
assert!(Uint256::from_u64(10).unwrap().bit(1));
assert!(!Uint256::from_u64(10).unwrap().bit(2));
assert!(Uint256::from_u64(10).unwrap().bit(3));
assert!(!Uint256::from_u64(10).unwrap().bit(4));
}
#[test]
pub fn uint256_display_test() {
assert_eq!(
format!("{}", Uint256::from_u64(0xDEADBEEF).unwrap()),
"0x00000000000000000000000000000000000000000000000000000000deadbeef"
);
assert_eq!(
format!("{}", Uint256::from_u64(u64::max_value()).unwrap()),
"0x000000000000000000000000000000000000000000000000ffffffffffffffff"
);
let max_val = Uint256([
0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF,
]);
assert_eq!(
format!("{}", max_val),
"0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
);
}
#[test]
pub fn uint256_comp_test() {
let small = Uint256([10u64, 0, 0, 0]);
let big = Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
let bigger = Uint256([0x9C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
let biggest = Uint256([0x5C8C3EE70C644118u64, 0x0209E7378231E632, 0, 1]);
assert!(small < big);
assert!(big < bigger);
assert!(bigger < biggest);
assert!(bigger <= biggest);
assert!(biggest <= biggest);
assert!(bigger >= big);
assert!(bigger >= small);
assert!(small <= small);
}
#[test]
pub fn uint256_arithmetic_test() {
let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
let copy = init;
let add = init + copy;
assert_eq!(add, Uint256([0xBD5B7DDFBD5B7DDEu64, 1, 0, 0]));
let shl = add << 88;
assert_eq!(shl, Uint256([0u64, 0xDFBD5B7DDE000000, 0x1BD5B7D, 0]));
let shr = shl >> 40;
assert_eq!(
shr,
Uint256([0x7DDE000000000000u64, 0x0001BD5B7DDFBD5B, 0, 0])
);
let mut incr = shr;
incr.increment();
assert_eq!(
incr,
Uint256([0x7DDE000000000001u64, 0x0001BD5B7DDFBD5B, 0, 0])
);
let sub = incr - init;
assert_eq!(
sub,
Uint256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0])
);
let mult = sub.mul_u32(300);
assert_eq!(
mult,
Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0])
);
assert_eq!(
Uint256::from_u64(105).unwrap() / Uint256::from_u64(5).unwrap(),
Uint256::from_u64(21).unwrap()
);
let div = mult / Uint256::from_u64(300).unwrap();
assert_eq!(
div,
Uint256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0])
);
}
#[test]
pub fn mul_u32_test() {
let u64_val = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
let u96_res = u64_val.mul_u32(0xFFFFFFFF);
let u128_res = u96_res.mul_u32(0xFFFFFFFF);
let u160_res = u128_res.mul_u32(0xFFFFFFFF);
let u192_res = u160_res.mul_u32(0xFFFFFFFF);
let u224_res = u192_res.mul_u32(0xFFFFFFFF);
let u256_res = u224_res.mul_u32(0xFFFFFFFF);
assert_eq!(u96_res, Uint256([0xffffffff21524111u64, 0xDEADBEEE, 0, 0]));
assert_eq!(
u128_res,
Uint256([0x21524111DEADBEEFu64, 0xDEADBEEE21524110, 0, 0])
);
assert_eq!(
u160_res,
Uint256([0xBD5B7DDD21524111u64, 0x42A4822200000001, 0xDEADBEED, 0])
);
assert_eq!(
u192_res,
Uint256([
0x63F6C333DEADBEEFu64,
0xBD5B7DDFBD5B7DDB,
0xDEADBEEC63F6C334,
0
])
);
assert_eq!(
u224_res,
Uint256([
0x7AB6FBBB21524111u64,
0xFFFFFFFBA69B4558,
0x854904485964BAAA,
0xDEADBEEB
])
);
assert_eq!(
u256_res,
Uint256([
0xA69B4555DEADBEEFu64,
0xA69B455CD41BB662,
0xD41BB662A69B4550,
0xDEADBEEAA69B455C
])
);
}
#[test]
pub fn multiplication_test() {
let u64_val = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
let u128_res = u64_val * u64_val;
assert_eq!(
u128_res,
Uint256([0x048D1354216DA321u64, 0xC1B1CD13A4D13D46, 0, 0])
);
let u256_res = u128_res * u128_res;
assert_eq!(
u256_res,
Uint256([
0xF4E166AAD40D0A41u64,
0xF5CF7F3618C2C886u64,
0x4AFCFF6F0375C608u64,
0x928D92B4D7F5DF33u64
])
);
}
#[test]
pub fn uint256_bitslice_test() {
let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
let add = init + (init << 64);
assert_eq!(add.bit_slice(64, 128), init);
assert_eq!(add.mask(64), init);
}
#[test]
pub fn uint256_extreme_bitshift_test() {
let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
assert_eq!(init << 64, Uint256([0, 0xDEADBEEFDEADBEEF, 0, 0]));
let add = (init << 64) + init;
assert_eq!(add, Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
assert_eq!(
add >> 0,
Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0])
);
assert_eq!(
add << 0,
Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0])
);
assert_eq!(add >> 64, Uint256([0xDEADBEEFDEADBEEF, 0, 0, 0]));
assert_eq!(
add << 64,
Uint256([0, 0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0])
);
}
#[cfg(feature = "rng")]
#[test]
pub fn uint256_random() {
let random = Uint256::random();
dbg!(random);
}
}