macro_rules! impl_prime_field_serializer {
($field: ident, $params: ident, $byte_size: expr) => {
impl<P: $params> CanonicalSerializeWithFlags for $field<P> {
fn serialize_with_flags<W: ark_std::io::Write, F: Flags>(
&self,
mut writer: W,
flags: F,
) -> Result<(), SerializationError> {
if F::BIT_SIZE > 8 {
return Err(SerializationError::NotEnoughSpace);
}
let output_byte_size = buffer_byte_size(P::MODULUS_BITS as usize + F::BIT_SIZE);
let mut bytes = [0u8; $byte_size + 1];
self.write(&mut bytes[..$byte_size])?;
bytes[output_byte_size - 1] |= flags.u8_bitmask();
writer.write_all(&bytes[..output_byte_size])?;
Ok(())
}
fn serialized_size_with_flags<F: Flags>(&self) -> usize {
buffer_byte_size(P::MODULUS_BITS as usize + F::BIT_SIZE)
}
}
impl<P: $params> CanonicalSerialize for $field<P> {
#[inline]
fn serialize<W: ark_std::io::Write>(
&self,
writer: W,
) -> Result<(), SerializationError> {
self.serialize_with_flags(writer, EmptyFlags)
}
#[inline]
fn serialized_size(&self) -> usize {
self.serialized_size_with_flags::<EmptyFlags>()
}
}
impl<P: $params> CanonicalDeserializeWithFlags for $field<P> {
fn deserialize_with_flags<R: ark_std::io::Read, F: Flags>(
mut reader: R,
) -> Result<(Self, F), SerializationError> {
if F::BIT_SIZE > 8 {
return Err(SerializationError::NotEnoughSpace);
}
let output_byte_size = buffer_byte_size(P::MODULUS_BITS as usize + F::BIT_SIZE);
let mut masked_bytes = [0; $byte_size + 1];
reader.read_exact(&mut masked_bytes[..output_byte_size])?;
let flags = F::from_u8_remove_flags(&mut masked_bytes[output_byte_size - 1])
.ok_or(SerializationError::UnexpectedFlags)?;
Ok((Self::read(&masked_bytes[..])?, flags))
}
}
impl<P: $params> CanonicalDeserialize for $field<P> {
fn deserialize<R: ark_std::io::Read>(reader: R) -> Result<Self, SerializationError> {
Self::deserialize_with_flags::<R, EmptyFlags>(reader).map(|(r, _)| r)
}
}
};
}
macro_rules! impl_Fp {
($Fp:ident, $FpParameters:ident, $BigInteger:ident, $BigIntegerType:ty, $limbs:expr) => {
pub trait $FpParameters: FpParameters<BigInt = $BigIntegerType> {}
#[derive(Derivative)]
#[derivative(
Default(bound = ""),
Hash(bound = ""),
Clone(bound = ""),
Copy(bound = ""),
Debug(bound = ""),
PartialEq(bound = ""),
Eq(bound = "")
)]
pub struct $Fp<P>(
pub $BigIntegerType,
#[derivative(Debug = "ignore")]
#[doc(hidden)]
pub PhantomData<P>,
);
impl<P> $Fp<P> {
#[inline]
pub const fn new(element: $BigIntegerType) -> Self {
Self(element, PhantomData)
}
#[ark_ff_asm::unroll_for_loops]
const fn const_is_zero(&self) -> bool {
let mut is_zero = true;
for i in 0..$limbs {
is_zero &= (self.0).0[i] == 0;
}
is_zero
}
const fn const_neg(self, modulus: $BigIntegerType) -> Self {
if !self.const_is_zero() {
Self::new(Self::sub_noborrow(&modulus, &self.0))
} else {
self
}
}
#[doc(hidden)]
pub const fn const_from_str(limbs: &[u64], is_positive: bool, r2: $BigIntegerType, modulus: $BigIntegerType, inv: u64) -> Self {
let mut repr = $BigInteger([0; $limbs]);
let mut i = 0;
while i < limbs.len() {
repr.0[i] = limbs[i];
i += 1;
}
let res = Self::const_from_repr(repr, r2, modulus, inv);
if is_positive {
res
} else {
res.const_neg(modulus)
}
}
#[inline]
pub(crate) const fn const_from_repr(repr: $BigIntegerType, r2: $BigIntegerType, modulus: $BigIntegerType, inv: u64) -> Self {
let mut r = Self::new(repr);
if r.const_is_zero() {
r
} else {
r = r.const_mul(&$Fp(r2, PhantomData), modulus, inv);
r
}
}
#[ark_ff_asm::unroll_for_loops]
const fn mul_without_reduce(mut self, other: &Self, modulus: $BigIntegerType, inv: u64) -> Self {
let mut r = [0u64; $limbs * 2];
for i in 0..$limbs {
let mut carry = 0;
for j in 0..$limbs {
r[j + i] = mac_with_carry!(r[j + i], (self.0).0[i], (other.0).0[j], &mut carry);
}
r[$limbs + i] = carry;
}
let mut _carry2 = 0;
for i in 0..$limbs {
let k = r[i].wrapping_mul(inv);
let mut carry = 0;
mac_with_carry!(r[i], k, modulus.0[0], &mut carry);
for j in 1..$limbs {
r[j + i] = mac_with_carry!(r[j + i], k, modulus.0[j], &mut carry);
}
r[$limbs + i] = adc!(r[$limbs + i], _carry2, &mut carry);
_carry2 = carry;
}
for i in 0..$limbs {
(self.0).0[i] = r[$limbs + i];
}
self
}
#[ark_ff_asm::unroll_for_loops]
const fn const_mul(mut self, other: &Self, modulus: $BigIntegerType, inv: u64) -> Self {
self = self.mul_without_reduce(other, modulus, inv);
self.const_reduce(modulus)
}
#[ark_ff_asm::unroll_for_loops]
const fn const_is_valid(&self, modulus: $BigIntegerType) -> bool {
for i in 0..$limbs {
if (self.0).0[($limbs - i - 1)] < modulus.0[($limbs - i - 1)] {
return true
} else if (self.0).0[($limbs - i - 1)] > modulus.0[($limbs - i - 1)] {
return false
}
}
false
}
#[inline]
const fn const_reduce(mut self, modulus: $BigIntegerType) -> Self {
if !self.const_is_valid(modulus) {
self.0 = Self::sub_noborrow(&self.0, &modulus);
}
self
}
#[ark_ff_asm::unroll_for_loops]
#[allow(unused_assignments)]
const fn sub_noborrow(a: &$BigIntegerType, b: &$BigIntegerType) -> $BigInteger {
let mut a = *a;
let mut borrow = 0;
for i in 0..$limbs {
a.0[i] = sbb!(a.0[i], b.0[i], &mut borrow);
}
a
}
}
impl<P: $FpParameters> $Fp<P> {
#[inline(always)]
pub(crate) fn is_valid(&self) -> bool {
self.0 < P::MODULUS
}
#[inline]
fn reduce(&mut self) {
if !self.is_valid() {
self.0.sub_noborrow(&P::MODULUS);
}
}
}
impl<P: $FpParameters> Zero for $Fp<P> {
#[inline]
fn zero() -> Self {
$Fp::<P>($BigInteger::from(0), PhantomData)
}
#[inline]
fn is_zero(&self) -> bool {
self.0.is_zero()
}
}
impl<P: $FpParameters> One for $Fp<P> {
#[inline]
fn one() -> Self {
$Fp::<P>(P::R, PhantomData)
}
#[inline]
fn is_one(&self) -> bool {
self.0 == P::R
}
}
impl<P: $FpParameters> Field for $Fp<P> {
type BasePrimeField = Self;
fn extension_degree() -> u64 {
1
}
fn from_base_prime_field_elems(elems: &[Self::BasePrimeField]) -> Option<Self> {
if elems.len() != (Self::extension_degree() as usize) {
return None;
}
Some(elems[0])
}
#[inline]
fn double(&self) -> Self {
let mut temp = *self;
temp.double_in_place();
temp
}
#[inline]
fn double_in_place(&mut self) -> &mut Self {
self.0.mul2();
self.reduce();
self
}
#[inline]
fn characteristic<'a>() -> &'a [u64] {
P::MODULUS.as_ref()
}
#[inline]
fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)> {
if F::BIT_SIZE > 8 {
return None
} else {
let mut result_bytes = [0u8; $limbs * 8 + 1];
result_bytes.iter_mut().zip(bytes).for_each(|(result, input)| {
*result = *input;
});
let last_limb_mask = (u64::MAX >> P::REPR_SHAVE_BITS).to_le_bytes();
let mut last_bytes_mask = [0u8; 9];
last_bytes_mask[..8].copy_from_slice(&last_limb_mask);
let output_byte_size = buffer_byte_size(P::MODULUS_BITS as usize + F::BIT_SIZE);
let flag_location = output_byte_size - 1;
let flag_location_in_last_limb = flag_location - (8 * ($limbs - 1));
let last_bytes = &mut result_bytes[8 * ($limbs - 1)..];
let flags_mask = u8::MAX.checked_shl(8 - (F::BIT_SIZE as u32)).unwrap_or(0);
let mut flags: u8 = 0;
for (i, (b, m)) in last_bytes.iter_mut().zip(&last_bytes_mask).enumerate() {
if i == flag_location_in_last_limb {
flags = *b & flags_mask
}
*b &= m;
}
Self::deserialize(&result_bytes[..($limbs * 8)])
.ok()
.and_then(|f| F::from_u8(flags).map(|flag| (f, flag)))
}
}
#[inline]
fn square(&self) -> Self {
let mut temp = self.clone();
temp.square_in_place();
temp
}
impl_field_square_in_place!($limbs);
#[inline]
fn inverse(&self) -> Option<Self> {
if self.is_zero() {
None
} else {
let one = $BigInteger::from(1);
let mut u = self.0;
let mut v = P::MODULUS;
let mut b = $Fp::<P>(P::R2, PhantomData);
let mut c = Self::zero();
while u != one && v != one {
while u.is_even() {
u.div2();
if b.0.is_even() {
b.0.div2();
} else {
b.0.add_nocarry(&P::MODULUS);
b.0.div2();
}
}
while v.is_even() {
v.div2();
if c.0.is_even() {
c.0.div2();
} else {
c.0.add_nocarry(&P::MODULUS);
c.0.div2();
}
}
if v < u {
u.sub_noborrow(&v);
b.sub_assign(&c);
} else {
v.sub_noborrow(&u);
c.sub_assign(&b);
}
}
if u == one {
Some(b)
} else {
Some(c)
}
}
}
fn inverse_in_place(&mut self) -> Option<&mut Self> {
if let Some(inverse) = self.inverse() {
*self = inverse;
Some(self)
} else {
None
}
}
#[inline]
fn frobenius_map(&mut self, _: usize) {
}
}
impl<P: $FpParameters> PrimeField for $Fp<P> {
type Params = P;
type BigInt = $BigIntegerType;
#[inline]
fn from_repr(r: $BigIntegerType) -> Option<Self> {
let mut r = $Fp(r, PhantomData);
if r.is_zero() {
Some(r)
} else if r.is_valid() {
r *= &$Fp(P::R2, PhantomData);
Some(r)
} else {
None
}
}
impl_field_into_repr!($limbs, $BigIntegerType);
}
impl<P: $FpParameters> FftField for $Fp<P> {
type FftParams = P;
#[inline]
fn two_adic_root_of_unity() -> Self {
$Fp::<P>(P::TWO_ADIC_ROOT_OF_UNITY, PhantomData)
}
#[inline]
fn large_subgroup_root_of_unity() -> Option<Self> {
Some($Fp::<P>(P::LARGE_SUBGROUP_ROOT_OF_UNITY?, PhantomData))
}
#[inline]
fn multiplicative_generator() -> Self {
$Fp::<P>(P::GENERATOR, PhantomData)
}
}
impl<P: $FpParameters> SquareRootField for $Fp<P> {
#[inline]
fn legendre(&self) -> LegendreSymbol {
use crate::fields::LegendreSymbol::*;
let s = self.pow(P::MODULUS_MINUS_ONE_DIV_TWO);
if s.is_zero() {
Zero
} else if s.is_one() {
QuadraticResidue
} else {
QuadraticNonResidue
}
}
#[inline]
fn sqrt(&self) -> Option<Self> {
sqrt_impl!(Self, P, self)
}
fn sqrt_in_place(&mut self) -> Option<&mut Self> {
(*self).sqrt().map(|sqrt| {
*self = sqrt;
self
})
}
}
impl<P: $FpParameters> Ord for $Fp<P> {
#[inline(always)]
fn cmp(&self, other: &Self) -> Ordering {
self.into_repr().cmp(&other.into_repr())
}
}
impl<P: $FpParameters> PartialOrd for $Fp<P> {
#[inline(always)]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl_prime_field_from_int!($Fp, u128, $FpParameters, $limbs);
impl_prime_field_from_int!($Fp, u64, $FpParameters, $limbs);
impl_prime_field_from_int!($Fp, u32, $FpParameters, $limbs);
impl_prime_field_from_int!($Fp, u16, $FpParameters, $limbs);
impl_prime_field_from_int!($Fp, u8, $FpParameters, $limbs);
impl_prime_field_from_int!($Fp, bool, $FpParameters, $limbs);
impl_prime_field_standard_sample!($Fp, $FpParameters);
impl_prime_field_serializer!($Fp, $FpParameters, $limbs * 8);
impl<P: $FpParameters> ToBytes for $Fp<P> {
#[inline]
fn write<W: Write>(&self, writer: W) -> IoResult<()> {
self.into_repr().write(writer)
}
}
impl<P: $FpParameters> FromBytes for $Fp<P> {
#[inline]
fn read<R: Read>(reader: R) -> IoResult<Self> {
$BigInteger::read(reader).and_then(|b|
match $Fp::from_repr(b) {
Some(f) => Ok(f),
None => Err(crate::error("FromBytes::read failed")),
})
}
}
impl<P: $FpParameters> FromStr for $Fp<P> {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s.is_empty() {
return Err(());
}
if s == "0" {
return Ok(Self::zero());
}
let mut res = Self::zero();
let ten = Self::from(<Self as PrimeField>::BigInt::from(10));
let mut first_digit = true;
for c in s.chars() {
match c.to_digit(10) {
Some(c) => {
if first_digit {
if c == 0 {
return Err(());
}
first_digit = false;
}
res.mul_assign(&ten);
let digit = Self::from(u64::from(c));
res.add_assign(&digit);
},
None => {
return Err(());
},
}
}
if !res.is_valid() {
Err(())
} else {
Ok(res)
}
}
}
impl<P: $FpParameters> Display for $Fp<P> {
#[inline]
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
write!(f, stringify!($Fp"({})"), self.into_repr())
}
}
impl<P: $FpParameters> Neg for $Fp<P> {
type Output = Self;
#[inline]
#[must_use]
fn neg(self) -> Self {
if !self.is_zero() {
let mut tmp = P::MODULUS;
tmp.sub_noborrow(&self.0);
$Fp::<P>(tmp, PhantomData)
} else {
self
}
}
}
impl<'a, P: $FpParameters> Add<&'a $Fp<P>> for $Fp<P> {
type Output = Self;
#[inline]
fn add(mut self, other: &Self) -> Self {
self.add_assign(other);
self
}
}
impl<'a, P: $FpParameters> Sub<&'a $Fp<P>> for $Fp<P> {
type Output = Self;
#[inline]
fn sub(mut self, other: &Self) -> Self {
self.sub_assign(other);
self
}
}
impl<'a, P: $FpParameters> Mul<&'a $Fp<P>> for $Fp<P> {
type Output = Self;
#[inline]
fn mul(mut self, other: &Self) -> Self {
self.mul_assign(other);
self
}
}
impl<'a, P: $FpParameters> Div<&'a $Fp<P>> for $Fp<P> {
type Output = Self;
#[inline]
fn div(mut self, other: &Self) -> Self {
self.mul_assign(&other.inverse().unwrap());
self
}
}
impl_additive_ops_from_ref!($Fp, $FpParameters);
impl_multiplicative_ops_from_ref!($Fp, $FpParameters);
impl<'a, P: $FpParameters> AddAssign<&'a Self> for $Fp<P> {
#[inline]
fn add_assign(&mut self, other: &Self) {
self.0.add_nocarry(&other.0);
self.reduce();
}
}
impl<'a, P: $FpParameters> SubAssign<&'a Self> for $Fp<P> {
#[inline]
fn sub_assign(&mut self, other: &Self) {
if other.0 > self.0 {
self.0.add_nocarry(&P::MODULUS);
}
self.0.sub_noborrow(&other.0);
}
}
impl<'a, P: $FpParameters> MulAssign<&'a Self> for $Fp<P> {
impl_field_mul_assign!($limbs);
}
impl<'a, P: $FpParameters> DivAssign<&'a Self> for $Fp<P> {
#[inline]
fn div_assign(&mut self, other: &Self) {
self.mul_assign(&other.inverse().unwrap());
}
}
impl<P: $FpParameters> zeroize::Zeroize for $Fp<P> {
fn zeroize(&mut self) {
self.0.zeroize();
}
}
}
}