repeated_commitments_data.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Completed, auditors: [Sergei], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/common/throw_or_abort.hpp"
#include <array>
#include <cstddef>
#include <span>
 
namespace bb {
 
// Non-constexpr no-return helper used to fail constant evaluation with a readable diagnostic
// when `repeated_commitments_from_pairs` is invoked on a layout it can't represent. Calling a
// non-constexpr function from a constexpr context is ill-formed, so the compiler emits an error
// pointing at this name (and the body's `throw_or_abort` runs at runtime in the unlikely event
// the function is reached non-constexpr).
[[noreturn]] inline void repeated_commitments_too_many_runs()
{
    throw_or_abort("repeated_commitments_from_pairs: layout produces more than 2 non-contiguous runs");
}
 
struct DuplicateRange {
    size_t original_start = 0;  // start index of the original (unshifted) polynomials in AllEntities
    size_t duplicate_start = 0; // start index of the duplicate (shifted) entries in AllEntities
    size_t count = 0;           // number of polynomials in this range
};
 
struct RepeatedCommitmentsData {
    DuplicateRange first;
    DuplicateRange second;
 
    RepeatedCommitmentsData() = default;
 
    constexpr RepeatedCommitmentsData(size_t first_original_start, size_t first_duplicate_start, size_t first_count)
        : first{ first_original_start, first_duplicate_start, first_count }
    {}
 
    constexpr RepeatedCommitmentsData(size_t first_original_start,
                                      size_t first_duplicate_start,
                                      size_t first_count,
                                      size_t second_original_start,
                                      size_t second_duplicate_start,
                                      size_t second_count)
        : first{ first_original_start, first_duplicate_start, first_count }
        , second{ second_original_start, second_duplicate_start, second_count }
    {}
};
 
struct DuplicatePair {
    size_t original = 0;
    size_t duplicate = 0;
};
 
constexpr RepeatedCommitmentsData repeated_commitments_from_pairs(std::span<const DuplicatePair> pairs)
{
    if (pairs.empty()) {
        return {};
    }
    std::array<DuplicateRange, 2> ranges{};
    size_t range_count = 0;
    DuplicateRange current{ pairs[0].original, pairs[0].duplicate, 1 };
    const auto close_range = [&](DuplicateRange r) constexpr {
        if (range_count == 2) {
            // More than two non-contiguous runs — RepeatedCommitmentsData can't represent this.
            // Calling a non-constexpr function from a constexpr context fails compilation; if
            // this fires, either reorder the layout to merge runs or extend
            // RepeatedCommitmentsData to hold more ranges.
            repeated_commitments_too_many_runs();
        }
        ranges[range_count++] = r;
    };
    for (size_t i = 1; i < pairs.size(); ++i) {
        const auto& p = pairs[i];
        if (p.original == current.original_start + current.count &&
            p.duplicate == current.duplicate_start + current.count) {
            ++current.count;
        } else {
            close_range(current);
            current = { p.original, p.duplicate, 1 };
        }
    }
    close_range(current);
    if (range_count == 1) {
        return RepeatedCommitmentsData{ ranges[0].original_start, ranges[0].duplicate_start, ranges[0].count };
    }
    return RepeatedCommitmentsData{ ranges[0].original_start, ranges[0].duplicate_start, ranges[0].count,
                                    ranges[1].original_start, ranges[1].duplicate_start, ranges[1].count };
}
 
} // namespace bb