use core::fmt::{self, Debug, Display, Formatter};
use core::hash::{Hash, Hasher};
use core::iter::{Product, Sum};
use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
use num::{BigUint, Integer};
use plonky2_util::{assume, branch_hint};
use serde::{Deserialize, Serialize};
use crate::inversion::try_inverse_u64;
use crate::types::{Field, Field64, PrimeField, PrimeField64, Sample};
const EPSILON: u64 = (1 << 32) - 1;
#[derive(Copy, Clone, Serialize, Deserialize)]
#[repr(transparent)]
pub struct GoldilocksField(pub u64);
impl Default for GoldilocksField {
fn default() -> Self {
Self::ZERO
}
}
impl PartialEq for GoldilocksField {
fn eq(&self, other: &Self) -> bool {
self.to_canonical_u64() == other.to_canonical_u64()
}
}
impl Eq for GoldilocksField {}
impl Hash for GoldilocksField {
fn hash<H: Hasher>(&self, state: &mut H) {
state.write_u64(self.to_canonical_u64())
}
}
impl Display for GoldilocksField {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
Display::fmt(&self.0, f)
}
}
impl Debug for GoldilocksField {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
Debug::fmt(&self.0, f)
}
}
impl Sample for GoldilocksField {
#[inline]
fn sample<R>(rng: &mut R) -> Self
where
R: rand::RngCore + ?Sized,
{
use rand::Rng;
Self::from_canonical_u64(rng.gen_range(0..Self::ORDER))
}
}
impl Field for GoldilocksField {
const ZERO: Self = Self(0);
const ONE: Self = Self(1);
const TWO: Self = Self(2);
const NEG_ONE: Self = Self(Self::ORDER - 1);
const TWO_ADICITY: usize = 32;
const CHARACTERISTIC_TWO_ADICITY: usize = Self::TWO_ADICITY;
const MULTIPLICATIVE_GROUP_GENERATOR: Self = Self(7);
const POWER_OF_TWO_GENERATOR: Self = Self(1753635133440165772);
const BITS: usize = 64;
fn order() -> BigUint {
Self::ORDER.into()
}
fn characteristic() -> BigUint {
Self::order()
}
#[inline(always)]
fn try_inverse(&self) -> Option<Self> {
try_inverse_u64(self)
}
fn from_noncanonical_biguint(n: BigUint) -> Self {
Self(n.mod_floor(&Self::order()).to_u64_digits()[0])
}
#[inline(always)]
fn from_canonical_u64(n: u64) -> Self {
debug_assert!(n < Self::ORDER);
Self(n)
}
fn from_noncanonical_u128(n: u128) -> Self {
reduce128(n)
}
#[inline]
fn multiply_accumulate(&self, x: Self, y: Self) -> Self {
reduce128((self.0 as u128) + (x.0 as u128) * (y.0 as u128))
}
}
impl PrimeField for GoldilocksField {
fn to_canonical_biguint(&self) -> BigUint {
self.to_canonical_u64().into()
}
}
impl Field64 for GoldilocksField {
const ORDER: u64 = 0xFFFFFFFF00000001;
#[inline]
fn from_noncanonical_u64(n: u64) -> Self {
Self(n)
}
#[inline]
fn from_noncanonical_i64(n: i64) -> Self {
Self::from_canonical_u64(if n < 0 {
Self::ORDER.wrapping_add(n as u64)
} else {
n as u64
})
}
#[inline]
unsafe fn add_canonical_u64(&self, rhs: u64) -> Self {
let (res_wrapped, carry) = self.0.overflowing_add(rhs);
Self(res_wrapped + EPSILON * (carry as u64))
}
#[inline]
unsafe fn sub_canonical_u64(&self, rhs: u64) -> Self {
let (res_wrapped, borrow) = self.0.overflowing_sub(rhs);
Self(res_wrapped - EPSILON * (borrow as u64))
}
}
impl PrimeField64 for GoldilocksField {
#[inline]
fn to_canonical_u64(&self) -> u64 {
let mut c = self.0;
if c >= Self::ORDER {
c -= Self::ORDER;
}
c
}
#[inline(always)]
fn to_noncanonical_u64(&self) -> u64 {
self.0
}
}
impl Neg for GoldilocksField {
type Output = Self;
#[inline]
fn neg(self) -> Self {
if self.is_zero() {
Self::ZERO
} else {
Self(Self::ORDER - self.to_canonical_u64())
}
}
}
impl Add for GoldilocksField {
type Output = Self;
#[inline]
#[allow(clippy::suspicious_arithmetic_impl)]
fn add(self, rhs: Self) -> Self {
let (sum, over) = self.0.overflowing_add(rhs.0);
let (mut sum, over) = sum.overflowing_add((over as u64) * EPSILON);
if over {
assume(self.0 > Self::ORDER && rhs.0 > Self::ORDER);
branch_hint();
sum += EPSILON; }
Self(sum)
}
}
impl AddAssign for GoldilocksField {
#[inline]
fn add_assign(&mut self, rhs: Self) {
*self = *self + rhs;
}
}
impl Sum for GoldilocksField {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::ZERO, |acc, x| acc + x)
}
}
impl Sub for GoldilocksField {
type Output = Self;
#[inline]
#[allow(clippy::suspicious_arithmetic_impl)]
fn sub(self, rhs: Self) -> Self {
let (diff, under) = self.0.overflowing_sub(rhs.0);
let (mut diff, under) = diff.overflowing_sub((under as u64) * EPSILON);
if under {
assume(self.0 < EPSILON - 1 && rhs.0 > Self::ORDER);
branch_hint();
diff -= EPSILON; }
Self(diff)
}
}
impl SubAssign for GoldilocksField {
#[inline]
fn sub_assign(&mut self, rhs: Self) {
*self = *self - rhs;
}
}
impl Mul for GoldilocksField {
type Output = Self;
#[inline]
fn mul(self, rhs: Self) -> Self {
reduce128((self.0 as u128) * (rhs.0 as u128))
}
}
impl MulAssign for GoldilocksField {
#[inline]
fn mul_assign(&mut self, rhs: Self) {
*self = *self * rhs;
}
}
impl Product for GoldilocksField {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::ONE, |acc, x| acc * x)
}
}
impl Div for GoldilocksField {
type Output = Self;
#[allow(clippy::suspicious_arithmetic_impl)]
fn div(self, rhs: Self) -> Self::Output {
self * rhs.inverse()
}
}
impl DivAssign for GoldilocksField {
fn div_assign(&mut self, rhs: Self) {
*self = *self / rhs;
}
}
#[inline(always)]
#[cfg(target_arch = "x86_64")]
unsafe fn add_no_canonicalize_trashing_input(x: u64, y: u64) -> u64 {
let res_wrapped: u64;
let adjustment: u64;
core::arch::asm!(
"add {0}, {1}",
"sbb {1:e}, {1:e}",
inlateout(reg) x => res_wrapped,
inlateout(reg) y => adjustment,
options(pure, nomem, nostack),
);
assume(x != 0 || (res_wrapped == y && adjustment == 0));
assume(y != 0 || (res_wrapped == x && adjustment == 0));
res_wrapped + adjustment
}
#[inline(always)]
#[cfg(not(target_arch = "x86_64"))]
unsafe fn add_no_canonicalize_trashing_input(x: u64, y: u64) -> u64 {
let (res_wrapped, carry) = x.overflowing_add(y);
res_wrapped + EPSILON * (carry as u64)
}
#[inline]
fn reduce128(x: u128) -> GoldilocksField {
let (x_lo, x_hi) = split(x); let x_hi_hi = x_hi >> 32;
let x_hi_lo = x_hi & EPSILON;
let (mut t0, borrow) = x_lo.overflowing_sub(x_hi_hi);
if borrow {
branch_hint(); t0 -= EPSILON; }
let t1 = x_hi_lo * EPSILON;
let t2 = unsafe { add_no_canonicalize_trashing_input(t0, t1) };
GoldilocksField(t2)
}
#[inline]
fn split(x: u128) -> (u64, u64) {
(x as u64, (x >> 64) as u64)
}
#[inline(always)]
pub(crate) unsafe fn reduce160(x_lo: u128, x_hi: u32) -> GoldilocksField {
let x_hi = (x_lo >> 96) as u64 + ((x_hi as u64) << 32); let x_mid = (x_lo >> 64) as u32; let x_lo = x_lo as u64;
let (mut t0, borrow) = x_lo.overflowing_sub(x_hi);
if borrow {
branch_hint();
t0 -= EPSILON; }
let t1 = (x_mid as u64) * EPSILON;
let t2 = add_no_canonicalize_trashing_input(t0, t1);
GoldilocksField(t2)
}
#[cfg(test)]
mod tests {
use crate::{test_field_arithmetic, test_prime_field_arithmetic};
test_prime_field_arithmetic!(crate::goldilocks_field::GoldilocksField);
test_field_arithmetic!(crate::goldilocks_field::GoldilocksField);
}