utils.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include <tuple>
#include <type_traits>
#include <utility>
 
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/common/tuple.hpp"
#include "barretenberg/polynomials/gate_separator.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/relation_tuple_helpers.hpp"
#include "barretenberg/relations/relation_types.hpp"
 
namespace bb {
 
template <typename Flavor> class RelationUtils {
  public:
    using FF = typename Flavor::FF;
    using Relations = typename Flavor::Relations;
    using PolynomialEvaluations = typename Flavor::AllValues;
    using RelationEvaluations = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>());
 
    static constexpr size_t NUM_RELATIONS = Flavor::NUM_RELATIONS;
    static constexpr size_t NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS;
 
    using SubrelationSeparators = std::array<FF, NUM_SUBRELATIONS - 1>;
 
    template <class Operation> static void apply_to_tuple_of_tuples(auto& tuple, Operation&& operation)
    {
        constexpr size_t outer_tuple_size = std::tuple_size_v<std::decay_t<decltype(tuple)>>;
        constexpr_for<0, outer_tuple_size, 1>([&]<size_t outer_idx>() {
            auto& inner_tuple = std::get<outer_idx>(tuple);
            constexpr size_t inner_tuple_size = std::tuple_size_v<std::decay_t<decltype(inner_tuple)>>;
            constexpr_for<0, inner_tuple_size, 1>([&]<size_t inner_idx>() {
                std::forward<Operation>(operation).operator()(std::get<inner_idx>(inner_tuple));
            });
        });
    }
 
    static void zero_univariates(auto& tuple)
    {
        auto set_to_zero = [](auto&&... elements) {
            (std::fill(elements.evaluations.begin(), elements.evaluations.end(), FF(0)), ...);
        };
        flat_tuple::apply([&](auto&&... args) { (flat_tuple::apply(set_to_zero, args), ...); }, tuple);
    }
 
    static void scale_univariates(auto& tuple, const SubrelationSeparators& subrelation_separators)
    {
        size_t idx = 0;
        auto scale_by_challenges = [&](auto& element) {
            // Don't need to scale first univariate
            if (idx != 0) {
                element *= subrelation_separators[idx - 1];
            }
            idx++;
        };
        apply_to_tuple_of_tuples(tuple, scale_by_challenges);
    }
 
    template <typename Tuple> static constexpr void add_tuples(Tuple& tuple_1, const Tuple& tuple_2)
    {
        auto add_tuples_helper = [&]<std::size_t... I>(std::index_sequence<I...>) {
            ((std::get<I>(tuple_1) += std::get<I>(tuple_2)), ...);
        };
 
        add_tuples_helper(std::make_index_sequence<std::tuple_size_v<Tuple>>{});
    }
 
    template <typename Tuple> static constexpr void add_nested_tuples(Tuple& tuple_1, const Tuple& tuple_2)
    {
        constexpr_for<0, std::tuple_size_v<Tuple>, 1>(
            [&]<size_t Index>() { add_tuples(std::get<Index>(tuple_1), std::get<Index>(tuple_2)); });
    }
 
    template <typename Parameters>
    inline static void accumulate_relation_evaluations_without_skipping(const PolynomialEvaluations& evaluations,
                                                                        RelationEvaluations& relation_evaluations,
                                                                        const Parameters& relation_parameters,
                                                                        const FF& partial_evaluation_result)
    {
        constexpr_for<0, NUM_RELATIONS, 1>([&]<size_t rel_index>() {
            // Skipping is disabled here because this path evaluates the relations at the random sumcheck
            // challenge: the per-row skip optimization is only valid on the boolean hypercube (where a
            // witness selector may be exactly zero), not at an arbitrary evaluation point.
            accumulate_single_relation<Parameters, rel_index, /*consider_skipping=*/false>(
                evaluations, relation_evaluations, relation_parameters, partial_evaluation_result);
        });
    }
 
    template <typename Parameters>
    inline static RelationEvaluations accumulate_relation_evaluations(const PolynomialEvaluations& evaluations,
                                                                      const Parameters& relation_parameters,
                                                                      const FF& scaling_factor)
    {
        RelationEvaluations result{};
        constexpr_for<0, NUM_RELATIONS, 1>([&]<size_t rel_index>() {
            accumulate_single_relation<Parameters, rel_index>(evaluations, result, relation_parameters, scaling_factor);
        });
        return result;
    }
 
    template <typename Parameters, size_t relation_idx, bool consider_skipping = true>
    inline static void accumulate_single_relation(const PolynomialEvaluations& evaluations,
                                                  RelationEvaluations& relation_evaluations,
                                                  const Parameters& relation_parameters,
                                                  const FF& scaling_factor)
    {
        using Relation = std::tuple_element_t<relation_idx, Relations>;
 
        // Check if the relation is skippable to speed up accumulation
        if constexpr (!consider_skipping || !isSkippable<Relation, decltype(evaluations)> ||
                      !std::is_same_v<FF, bb::fr>) {
            // If not, accumulate normally
            Relation::accumulate(
                std::get<relation_idx>(relation_evaluations), evaluations, relation_parameters, scaling_factor);
        } else {
            // If so, only compute the contribution if the relation is active
            if (!Relation::skip(evaluations)) {
                Relation::accumulate(
                    std::get<relation_idx>(relation_evaluations), evaluations, relation_parameters, scaling_factor);
            }
        }
    }
 
    static void zero_elements(auto& tuple)
    {
        auto set_to_zero = [](auto& element) { std::fill(element.begin(), element.end(), FF(0)); };
        apply_to_tuple_of_arrays(set_to_zero, tuple);
    };
 
    static FF scale_and_batch_elements(auto& tuple,
                                       const SubrelationSeparators& subrelation_separators,
                                       const FF& main_factor = FF{ 1 },
                                       const FF& offset_factor = FF{ 0 })
    {
        FF result{ 0 };
        size_t idx = 0;
 
        auto process = [&]<size_t outer_idx, size_t inner_idx>(auto& element) {
            using Relation = std::tuple_element_t<outer_idx, Relations>;
            const FF& rd_factor = IsOffsetOnlyRelation<Relation> ? offset_factor : main_factor;
            if constexpr (outer_idx == 0 && inner_idx == 0) {
                // α_{0,0} = 1 by convention.
                result += element * rd_factor;
            } else {
                result += element * subrelation_separators[idx++] * rd_factor;
            }
        };
        apply_to_tuple_of_arrays_elements(process, tuple);
        return result;
    }
 
    template <typename Operation> static void apply_to_tuple_of_arrays(Operation&& operation, auto& tuple)
    {
        flat_tuple::apply(
            [&operation](auto&... elements_ref) {
                // The comma operator ensures sequential application of the operation to each element.
                // (void) cast is used to discard the result of std::invoke if it's not void,
                // to prevent issues with overloaded comma operators.
                ((void)std::invoke(std::forward<Operation>(operation), elements_ref), ...);
            },
            tuple);
    }
 
    template <typename Operation, typename tuple_type>
    static void apply_to_tuple_of_arrays_elements(Operation&& operation, const tuple_type& tuple)
    {
        // Iterate over each array in the outer tuple.
        // OuterIdx is the compile-time index of the current array in the tuple.
        constexpr_for<0, std::tuple_size_v<tuple_type>, 1>([&]<size_t OuterIdx>() {
            // Get a const reference to the current array from the tuple.
            const auto& current_array = std::get<OuterIdx>(tuple);
            constexpr size_t num_elements_in_current_array = std::tuple_size_v<std::decay_t<decltype(current_array)>>;
 
            // Iterate over each element within the current_array.
            // InnerIdx is the compile-time index of the element within this specific array.
            constexpr_for<0, num_elements_in_current_array, 1>([&]<size_t InnerIdx>() {
                // Invoke the operation.
                // The operation is called with OuterIdx (array index in the tuple) and
                // InnerIdx (element index in the current array) as template arguments.
                // The current element (e.g., an FF value) is passed as an argument.
                std::forward<Operation>(operation).template operator()<OuterIdx, InnerIdx>(current_array[InnerIdx]);
            });
        });
    }
};
 
} // namespace bb