//! This crate provides traits for working with finite fields.

#![no_std]

#![cfg_attr(docsrs, feature(doc_cfg))]

// Catch documentation errors caused by code changes.

#![deny(rustdoc::broken_intra_doc_links)]

#![forbid(unsafe_code)]

#[cfg(feature = "alloc")]

extern crate alloc;

mod batch;

pub use batch::*;

pub mod helpers;

#[cfg(feature = "derive")]

#[cfg_attr(docsrs, doc(cfg(feature = "derive")))]

pub use ff_derive::PrimeField;

#[cfg(feature = "bits")]

#[cfg_attr(docsrs, doc(cfg(feature = "bits")))]

pub use bitvec::view::BitViewSized;

#[cfg(feature = "bits")]

use bitvec::{array::BitArray, order::Lsb0};

use core::fmt;

use core::iter::{Product, Sum};

use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};

use rand_core::RngCore;

use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};

/// Bit representation of a field element.

#[cfg(feature = "bits")]

#[cfg_attr(docsrs, doc(cfg(feature = "bits")))]

pub type FieldBits<V> = BitArray<V, Lsb0>;

/// This trait represents an element of a field.

pub trait Field:

    Sized

    + Eq

    + Copy

    + Clone

    + Default

    + Send

    + Sync

    + fmt::Debug

    + 'static

    + ConditionallySelectable

    + ConstantTimeEq

    + Neg<Output = Self>

    + Add<Output = Self>

    + Sub<Output = Self>

    + Mul<Output = Self>

    + Sum

    + Product

    + for<'a> Add<&'a Self, Output = Self>

    + for<'a> Sub<&'a Self, Output = Self>

    + for<'a> Mul<&'a Self, Output = Self>

    + for<'a> Sum<&'a Self>

    + for<'a> Product<&'a Self>

    + AddAssign

    + SubAssign

    + MulAssign

    + for<'a> AddAssign<&'a Self>

    + for<'a> SubAssign<&'a Self>

    + for<'a> MulAssign<&'a Self>

{

    /// The zero element of the field, the additive identity.

    const ZERO: Self;

    /// The one element of the field, the multiplicative identity.

    const ONE: Self;

    /// Returns an element chosen uniformly at random using a user-provided RNG.

    fn random(rng: impl RngCore) -> Self;

    /// Returns true iff this element is zero.

    fn is_zero(&self) -> Choice {

        self.ct_eq(&Self::ZERO)

    }

    /// Returns true iff this element is zero.

    ///

    /// # Security

    ///

    /// This method provides **no** constant-time guarantees. Implementors of the

    /// `Field` trait **may** optimise this method using non-constant-time logic.

    fn is_zero_vartime(&self) -> bool {

        self.is_zero().into()

    }

    /// Squares this element.

    #[must_use]

    fn square(&self) -> Self;

    /// Cubes this element.

    #[must_use]

    fn cube(&self) -> Self {

        self.square() * self

    }

    /// Doubles this element.

    #[must_use]

    fn double(&self) -> Self;

    /// Computes the multiplicative inverse of this element,

    /// failing if the element is zero.

    fn invert(&self) -> CtOption<Self>;

    /// Computes:

    ///

    /// - $(\textsf{true}, \sqrt{\textsf{num}/\textsf{div}})$, if $\textsf{num}$ and

    ///   $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is a square in the

    ///   field;

    /// - $(\textsf{true}, 0)$, if $\textsf{num}$ is zero;

    /// - $(\textsf{false}, 0)$, if $\textsf{num}$ is nonzero and $\textsf{div}$ is zero;

    /// - $(\textsf{false}, \sqrt{G_S \cdot \textsf{num}/\textsf{div}})$, if

    ///   $\textsf{num}$ and $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is

    ///   a nonsquare in the field;

    ///

    /// where $G_S$ is a non-square.

    ///

    /// # Warnings

    ///

    /// - The choice of root from `sqrt` is unspecified.

    /// - The value of $G_S$ is unspecified, and cannot be assumed to have any specific

    ///   value in a generic context.

    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self);

    /// Equivalent to `Self::sqrt_ratio(self, one())`.

    ///

    /// The provided method is implemented in terms of [`Self::sqrt_ratio`].

    fn sqrt_alt(&self) -> (Choice, Self) {

        Self::sqrt_ratio(self, &Self::ONE)

    }

    /// Returns the square root of the field element, if it is

    /// quadratic residue.

    ///

    /// The provided method is implemented in terms of [`Self::sqrt_ratio`].

    fn sqrt(&self) -> CtOption<Self> {

        let (is_square, res) = Self::sqrt_ratio(self, &Self::ONE);

        CtOption::new(res, is_square)

    }

    /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer

    /// exponent.

    ///

    /// # Guarantees

    ///

    /// This operation is constant time with respect to `self`, for all exponents with the

    /// same number of digits (`exp.as_ref().len()`). It is variable time with respect to

    /// the number of digits in the exponent.

    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {

        let mut res = Self::ONE;

        for e in exp.as_ref().iter().rev() {

            for i in (0..64).rev() {

                res = res.square();

                let mut tmp = res;

                tmp *= self;

                res.conditional_assign(&tmp, (((*e >> i) & 1) as u8).into());

            }

        }

        res

    }

    /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer

    /// exponent.

    ///

    /// # Guarantees

    ///

    /// **This operation is variable time with respect to `self`, for all exponent.** If

    /// the exponent is fixed, this operation is effectively constant time. However, for

    /// stronger constant-time guarantees, [`Field::pow`] should be used.

    fn pow_vartime<S: AsRef<[u64]>>(&self, exp: S) -> Self {

        let mut res = Self::ONE;

        for e in exp.as_ref().iter().rev() {

            for i in (0..64).rev() {

                res = res.square();

                if ((*e >> i) & 1) == 1 {

                    res.mul_assign(self);

                }

            }

        }

        res

    }

}

/// This represents an element of a non-binary prime field.

pub trait PrimeField: Field + From<u64> {

    /// The prime field can be converted back and forth into this binary

    /// representation.

    type Repr: Copy + Default + Send + Sync + 'static + AsRef<[u8]> + AsMut<[u8]>;

    /// Interpret a string of numbers as a (congruent) prime field element.

    /// Does not accept unnecessary leading zeroes or a blank string.

    ///

    /// # Security

    ///

    /// This method provides **no** constant-time guarantees.

    fn from_str_vartime(s: &str) -> Option<Self> {

        if s.is_empty() {

            return None;

        }

        if s == "0" {

            return Some(Self::ZERO);

        }

        let mut res = Self::ZERO;

        let ten = Self::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 None;

                        }

                        first_digit = false;

                    }

                    res.mul_assign(&ten);

                    res.add_assign(&Self::from(u64::from(c)));

                }

                None => {

                    return None;

                }

            }

        }

        Some(res)

    }

    /// Obtains a field element congruent to the integer `v`.

    ///

    /// For fields where `Self::CAPACITY >= 128`, this is injective and will produce a

    /// unique field element.

    ///

    /// For fields where `Self::CAPACITY < 128`, this is surjective; some field elements

    /// will be produced by multiple values of `v`.

    ///

    /// If you want to deterministically sample a field element representing a value, use

    /// [`FromUniformBytes`] instead.

    fn from_u128(v: u128) -> Self {

        let lower = v as u64;

        let upper = (v >> 64) as u64;

        let mut tmp = Self::from(upper);

        for _ in 0..64 {

            tmp = tmp.double();

        }

        tmp + Self::from(lower)

    }

    /// Attempts to convert a byte representation of a field element into an element of

    /// this prime field, failing if the input is not canonical (is not smaller than the

    /// field's modulus).

    ///

    /// The byte representation is interpreted with the same endianness as elements

    /// returned by [`PrimeField::to_repr`].

    fn from_repr(repr: Self::Repr) -> CtOption<Self>;

    /// Attempts to convert a byte representation of a field element into an element of

    /// this prime field, failing if the input is not canonical (is not smaller than the

    /// field's modulus).

    ///

    /// The byte representation is interpreted with the same endianness as elements

    /// returned by [`PrimeField::to_repr`].

    ///

    /// # Security

    ///

    /// This method provides **no** constant-time guarantees. Implementors of the

    /// `PrimeField` trait **may** optimise this method using non-constant-time logic.

    fn from_repr_vartime(repr: Self::Repr) -> Option<Self> {

        Self::from_repr(repr).into()

    }

    /// Converts an element of the prime field into the standard byte representation for

    /// this field.

    ///

    /// The endianness of the byte representation is implementation-specific. Generic

    /// encodings of field elements should be treated as opaque.

    fn to_repr(&self) -> Self::Repr;

    /// Returns true iff this element is odd.

    fn is_odd(&self) -> Choice;

    /// Returns true iff this element is even.

    #[inline(always)]

    fn is_even(&self) -> Choice {

        !self.is_odd()

    }

    /// Modulus of the field written as a string for debugging purposes.

    ///

    /// The encoding of the modulus is implementation-specific. Generic users of the

    /// `PrimeField` trait should treat this string as opaque.

    const MODULUS: &'static str;

    /// How many bits are needed to represent an element of this field.

    const NUM_BITS: u32;

    /// How many bits of information can be reliably stored in the field element.

    ///

    /// This is usually `Self::NUM_BITS - 1`.

    const CAPACITY: u32;

    /// Inverse of $2$ in the field.

    const TWO_INV: Self;

    /// A fixed multiplicative generator of `modulus - 1` order. This element must also be

    /// a quadratic nonresidue.

    ///

    /// It can be calculated using [SageMath] as `GF(modulus).primitive_element()`.

    ///

    /// Implementations of this trait MUST ensure that this is the generator used to

    /// derive `Self::ROOT_OF_UNITY`.

    ///

    /// [SageMath]: https://www.sagemath.org/

    const MULTIPLICATIVE_GENERATOR: Self;

    /// An integer `s` satisfying the equation `2^s * t = modulus - 1` with `t` odd.

    ///

    /// This is the number of leading zero bits in the little-endian bit representation of

    /// `modulus - 1`.

    const S: u32;

    /// The `2^s` root of unity.

    ///

    /// It can be calculated by exponentiating `Self::MULTIPLICATIVE_GENERATOR` by `t`,

    /// where `t = (modulus - 1) >> Self::S`.

    const ROOT_OF_UNITY: Self;

    /// Inverse of [`Self::ROOT_OF_UNITY`].

    const ROOT_OF_UNITY_INV: Self;

    /// Generator of the `t-order` multiplicative subgroup.

    ///

    /// It can be calculated by exponentiating [`Self::MULTIPLICATIVE_GENERATOR`] by `2^s`,

    /// where `s` is [`Self::S`].

    const DELTA: Self;

}

/// The subset of prime-order fields such that `(modulus - 1)` is divisible by `N`.

///

/// If `N` is prime, there will be `N - 1` valid choices of [`Self::ZETA`]. Similarly to

/// [`PrimeField::MULTIPLICATIVE_GENERATOR`], the specific choice does not matter, as long

/// as the choice is consistent across all uses of the field.

pub trait WithSmallOrderMulGroup<const N: u8>: PrimeField {

    /// A field element of small multiplicative order $N$.

    ///

    /// The presence of this element allows you to perform (certain types of)

    /// endomorphisms on some elliptic curves.

    ///

    /// It can be calculated using [SageMath] as

    /// `GF(modulus).primitive_element() ^ ((modulus - 1) // N)`.

    /// Choosing the element of order $N$ that is smallest, when considered

    /// as an integer, may help to ensure consistency.

    ///

    /// [SageMath]: https://www.sagemath.org/

    const ZETA: Self;

}

/// Trait for constructing a [`PrimeField`] element from a fixed-length uniform byte

/// array.

///

/// "Uniform" means that the byte array's contents must be indistinguishable from the

/// [discrete uniform distribution]. Suitable byte arrays can be obtained:

/// - from a cryptographically-secure randomness source (which makes this constructor

///   equivalent to [`Field::random`]).

/// - from a cryptographic hash function output, which enables a "random" field element to

///   be selected deterministically. This is the primary use case for `FromUniformBytes`.

///

/// The length `N` of the byte array is chosen by the trait implementer such that the loss

/// of uniformity in the mapping from byte arrays to field elements is cryptographically

/// negligible.

///

/// [discrete uniform distribution]: https://en.wikipedia.org/wiki/Discrete_uniform_distribution

///

/// # Examples

///

/// ```

/// # #[cfg(feature = "derive")] {

/// # // Fake this so we don't actually need a dev-dependency on bls12_381.

/// # mod bls12_381 {

/// #     use ff::{Field, PrimeField};

/// #

/// #     #[derive(PrimeField)]

/// #     #[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"]

/// #     #[PrimeFieldGenerator = "7"]

/// #     #[PrimeFieldReprEndianness = "little"]

/// #     pub struct Scalar([u64; 4]);

/// #

/// #     impl ff::FromUniformBytes<64> for Scalar {

/// #         fn from_uniform_bytes(_bytes: &[u8; 64]) -> Self {

/// #             // Fake impl for doctest

/// #             Scalar::ONE

/// #         }

/// #     }

/// # }

/// #

/// use blake2b_simd::blake2b;

/// use bls12_381::Scalar;

/// use ff::FromUniformBytes;

///

/// // `bls12_381::Scalar` implements `FromUniformBytes<64>`, and BLAKE2b (by default)

/// // produces a 64-byte hash.

/// let hash = blake2b(b"Some message");

/// let val = Scalar::from_uniform_bytes(hash.as_array());

/// # }

/// ```

///

/// # Implementing `FromUniformBytes`

///

/// [`Self::from_uniform_bytes`] should always be implemented by interpreting the provided

/// byte array as the little endian unsigned encoding of an integer, and then reducing that

/// integer modulo the field modulus.

///

/// For security, `N` must be chosen so that `N * 8 >= Self::NUM_BITS + 128`. A larger

/// value of `N` may be chosen for convenience; for example, for a field with a 255-bit

/// modulus, `N = 64` is convenient as it matches the output length of several common

/// cryptographic hash functions (such as SHA-512 and BLAKE2b).

///

/// ## Trait design

///

/// This trait exists because `PrimeField::from_uniform_bytes([u8; N])` cannot currently

/// exist (trait methods cannot use associated constants in the const positions of their

/// type signature, and we do not want `PrimeField` to require a generic const parameter).

/// However, this has the side-effect that `FromUniformBytes` can be implemented multiple

/// times for different values of `N`. Most implementations of [`PrimeField`] should only

/// need to implement `FromUniformBytes` trait for one value of `N` (chosen following the

/// above considerations); if you find yourself needing to implement it multiple times,

/// please [let us know about your use case](https://github.com/zkcrypto/ff/issues/new) so

/// we can take it into consideration for future evolutions of the `ff` traits.

pub trait FromUniformBytes<const N: usize>: PrimeField {

    /// Returns a field element that is congruent to the provided little endian unsigned

    /// byte representation of an integer.

    fn from_uniform_bytes(bytes: &[u8; N]) -> Self;

}

/// This represents the bits of an element of a prime field.

#[cfg(feature = "bits")]

#[cfg_attr(docsrs, doc(cfg(feature = "bits")))]

pub trait PrimeFieldBits: PrimeField {

    /// The backing store for a bit representation of a prime field element.

    type ReprBits: BitViewSized + Send + Sync;

    /// Converts an element of the prime field into a little-endian sequence of bits.

    fn to_le_bits(&self) -> FieldBits<Self::ReprBits>;

    /// Returns the bits of the field characteristic (the modulus) in little-endian order.

    fn char_le_bits() -> FieldBits<Self::ReprBits>;

}

/// Functions and re-exported crates used by the [`PrimeField`] derive macro.

#[cfg(feature = "derive")]

#[cfg_attr(docsrs, doc(cfg(feature = "derive")))]

pub mod derive {

    pub use crate::arith_impl::*;

    pub use {byteorder, rand_core, subtle};

    #[cfg(feature = "bits")]

    pub use bitvec;

}

#[cfg(feature = "derive")]

mod arith_impl {

    /// Computes `a - (b + borrow)`, returning the result and the new borrow.

    #[inline(always)]

    pub const fn sbb(a: u64, b: u64, borrow: u64) -> (u64, u64) {

        let ret = (a as u128).wrapping_sub((b as u128) + ((borrow >> 63) as u128));

        (ret as u64, (ret >> 64) as u64)

    }

    /// Computes `a + b + carry`, returning the result and the new carry over.

    #[inline(always)]

    pub const fn adc(a: u64, b: u64, carry: u64) -> (u64, u64) {

        let ret = (a as u128) + (b as u128) + (carry as u128);

        (ret as u64, (ret >> 64) as u64)

    }

    /// Computes `a + (b * c) + carry`, returning the result and the new carry over.

    #[inline(always)]

    pub const fn mac(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64) {

        let ret = (a as u128) + ((b as u128) * (c as u128)) + (carry as u128);

        (ret as u64, (ret >> 64) as u64)

    }

}