polynomial.hpp

#pragma once
#include "barretenberg/common/mem.hpp"
#include "barretenberg/crypto/sha256/sha256.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "evaluation_domain.hpp"
#include "polynomial_arithmetic.hpp"
#include <fstream>
 
namespace barretenberg {
enum class DontZeroMemory { FLAG };
 
template <typename Fr> class Polynomial {
  public:
    using value_type = Fr;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    // NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays)
    using pointer = std::shared_ptr<value_type[]>;
    using const_pointer = pointer;
    using iterator = Fr*;
    using const_iterator = Fr const*;
    using FF = Fr;
 
    Polynomial(size_t initial_size);
    // Constructor that does not initialize values, use with caution to save time.
    Polynomial(size_t initial_size, DontZeroMemory flag);
    Polynomial(const Polynomial& other);
    Polynomial(const Polynomial& other, size_t target_size);
 
    Polynomial(Polynomial&& other) noexcept;
 
    // Create a polynomial from the given fields.
    Polynomial(std::span<const Fr> coefficients);
 
    // Allow polynomials to be entirely reset/dormant
    Polynomial() = default;
 
    Polynomial(std::span<const Fr> interpolation_points, std::span<const Fr> evaluations);
 
    // move assignment
    Polynomial& operator=(Polynomial&& other) noexcept;
    Polynomial& operator=(std::span<const Fr> coefficients) noexcept;
    Polynomial& operator=(const Polynomial& other);
    ~Polynomial() = default;
 
    Polynomial share() const;
 
    std::array<uint8_t, 32> hash() const { return sha256::sha256(byte_span()); }
 
    void clear()
    {
        // to keep the invariant that backing_memory_ can handle capacity() we do NOT reset backing_memory_
        // backing_memory_.reset();
        coefficients_ = nullptr;
        size_ = 0;
    }
 
    bool operator==(Polynomial const& rhs) const;
 
    // Const and non const versions of coefficient accessors
    Fr const& operator[](const size_t i) const { return coefficients_[i]; }
 
    Fr& operator[](const size_t i) { return coefficients_[i]; }
 
    Fr const& at(const size_t i) const
    {
        ASSERT(i < capacity());
        return coefficients_[i];
    };
 
    Fr& at(const size_t i)
    {
        ASSERT(i < capacity());
        return coefficients_[i];
    };
 
    Fr evaluate(const Fr& z, size_t target_size) const;
    Fr evaluate(const Fr& z) const;
 
    Fr compute_barycentric_evaluation(const Fr& z, const EvaluationDomain<Fr>& domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    Fr evaluate_from_fft(const EvaluationDomain<Fr>& large_domain,
                         const Fr& z,
                         const EvaluationDomain<Fr>& small_domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void fft(const EvaluationDomain<Fr>& domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void partial_fft(const EvaluationDomain<Fr>& domain, Fr constant = 1, bool is_coset = false)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void coset_fft(const EvaluationDomain<Fr>& domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void coset_fft(const EvaluationDomain<Fr>& domain,
                   const EvaluationDomain<Fr>& large_domain,
                   size_t domain_extension)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void coset_fft_with_constant(const EvaluationDomain<Fr>& domain, const Fr& constant)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void coset_fft_with_generator_shift(const EvaluationDomain<Fr>& domain, const Fr& constant)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void ifft(const EvaluationDomain<Fr>& domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void ifft_with_constant(const EvaluationDomain<Fr>& domain, const Fr& constant)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    void coset_ifft(const EvaluationDomain<Fr>& domain)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
    Fr compute_kate_opening_coefficients(const Fr& z)
        requires polynomial_arithmetic::SupportsFFT<Fr>;
 
    bool is_empty() const { return size_ == 0; }
 
    Polynomial shifted() const;
 
    void set_to_right_shifted(std::span<Fr> coeffs_in, size_t shift_size = 1);
 
    void add_scaled(std::span<const Fr> other, Fr scaling_factor);
 
    Polynomial& operator+=(std::span<const Fr> other);
 
    Polynomial& operator-=(std::span<const Fr> other);
 
    Polynomial& operator*=(Fr scaling_factor);
 
    Fr evaluate_mle(std::span<const Fr> evaluation_points, bool shift = false) const;
 
    Polynomial<Fr> partial_evaluate_mle(std::span<const Fr> evaluation_points) const;
 
    void factor_roots(std::span<const Fr> roots) { polynomial_arithmetic::factor_roots(std::span{ *this }, roots); };
    void factor_roots(const Fr& root) { polynomial_arithmetic::factor_roots(std::span{ *this }, root); };
 
    iterator begin() { return coefficients_; }
    iterator end() { return coefficients_ + size_; }
    pointer data() { return backing_memory_; }
 
    std::span<uint8_t> byte_span() const
    {
        // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
        return { reinterpret_cast<uint8_t*>(coefficients_), size_ * sizeof(Fr) };
    }
 
    const_iterator begin() const { return coefficients_; }
    const_iterator end() const { return coefficients_ + size_; }
    const_pointer data() const { return backing_memory_; }
 
    std::size_t size() const { return size_; }
    std::size_t capacity() const { return size_ + MAXIMUM_COEFFICIENT_SHIFT; }
 
  private:
    // allocate a fresh memory pointer for backing memory
    // DOES NOT initialize memory
    void allocate_backing_memory(size_t n_elements);
 
    // safety check for in place operations
    bool in_place_operation_viable(size_t domain_size = 0) { return (size() >= domain_size); }
 
    void zero_memory_beyond(size_t start_position);
    // When a polynomial is instantiated from a size alone, the memory allocated corresponds to
    // input size + MAXIMUM_COEFFICIENT_SHIFT to support 'shifted' coefficients efficiently.
    const static size_t MAXIMUM_COEFFICIENT_SHIFT = 1;
 
    // The memory
    // NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays)
    std::shared_ptr<Fr[]> backing_memory_;
    // A pointer into backing_memory_ to support std::span-like functionality. This allows for coefficient subsets
    // and shifts.
    Fr* coefficients_ = nullptr;
    // The size_ effectively represents the 'usable' length of the coefficients array but may be less than the true
    // 'capacity' of the array. It is not explicitly tied to the degree and is not changed by any operations on the
    // polynomial.
    size_t size_ = 0;
};
 
template <typename Fr> inline std::ostream& operator<<(std::ostream& os, Polynomial<Fr> const& p)
{
    if (p.size() == 0) {
        return os << "[]";
    }
    if (p.size() == 1) {
        return os << "[ data " << p[0] << "]";
    }
    return os << "[ data\n"
              << "  " << p[0] << ",\n"
              << "  " << p[1] << ",\n"
              << "  ... ,\n"
              << "  " << p[p.size() - 2] << ",\n"
              << "  " << p[p.size() - 1] << ",\n"
              << "]";
}
 
extern template class Polynomial<barretenberg::fr>;
// N.B. grumpkin polynomials don't support fast fourier transforms using roots of unity!
extern template class Polynomial<grumpkin::fr>;
 
using polynomial = Polynomial<barretenberg::fr>;
 
} // namespace barretenberg