field_gt_trace.cpp

Go to the documentation of this file.

#include "barretenberg/vm2/tracegen/field_gt_trace.hpp"
 
#include "barretenberg/vm2/common/field.hpp"
#include "barretenberg/vm2/generated/relations/lookups_ff_gt.hpp"
#include "barretenberg/vm2/simulation/lib/uint_decomposition.hpp"
#include "barretenberg/vm2/tracegen/lib/interaction_def.hpp"
 
namespace bb::avm2::tracegen {
 
using simulation::LimbsComparisonWitness;
using simulation::U256Decomposition;
 
void FieldGreaterThanTraceBuilder::process(
    const simulation::EventEmitterInterface<simulation::FieldGreaterThanEvent>::Container& events,
    TraceContainer& trace)
{
    using C = Column;
 
    // We precompute the inverses up to 4.
    std::array<FF, 5> precomputed_ctr_inverses = { 0, 1, 2, 3, 4 };
    FF::batch_invert(precomputed_ctr_inverses);
 
    uint32_t row = 1;
    for (const auto& event : events) {
        // Copy the things that will need range checks since we'll mutate them in the shifts
        U256Decomposition a_limbs = event.a_limbs;
        LimbsComparisonWitness p_sub_a_witness = event.p_sub_a_witness;
        U256Decomposition b_limbs = event.b_limbs;
        LimbsComparisonWitness p_sub_b_witness = event.p_sub_b_witness;
        LimbsComparisonWitness res_witness = event.res_witness;
 
        bool sel_gt = event.operation == simulation::FieldGreaterOperation::GREATER_THAN;
        bool sel_dec = event.operation == simulation::FieldGreaterOperation::CANONICAL_DECOMPOSITION;
 
        for (int cmp_rng_ctr = event.operation == simulation::FieldGreaterOperation::GREATER_THAN ? 4 : 1;
             cmp_rng_ctr >= 0;
             cmp_rng_ctr--) {
 
            const FF& cmp_rng_ctr_inv = precomputed_ctr_inverses.at(static_cast<size_t>(cmp_rng_ctr));
            trace.set(row,
                      { { { C::ff_gt_sel, 1 },
                          { C::ff_gt_a, event.a },
                          { C::ff_gt_b, event.b },
                          { C::ff_gt_result, event.gt_result },
                          { C::ff_gt_sel_dec, sel_dec ? 1 : 0 },
                          { C::ff_gt_sel_gt, sel_gt ? 1 : 0 },
                          { C::ff_gt_constant_128, 128 },
                          { C::ff_gt_a_lo, a_limbs.lo },
                          { C::ff_gt_a_hi, a_limbs.hi },
                          { C::ff_gt_p_a_borrow, p_sub_a_witness.borrow ? 1 : 0 },
                          { C::ff_gt_p_sub_a_lo, p_sub_a_witness.lo },
                          { C::ff_gt_p_sub_a_hi, p_sub_a_witness.hi },
                          { C::ff_gt_b_lo, b_limbs.lo },
                          { C::ff_gt_b_hi, b_limbs.hi },
                          { C::ff_gt_p_b_borrow, p_sub_b_witness.borrow ? 1 : 0 },
                          { C::ff_gt_p_sub_b_lo, p_sub_b_witness.lo },
                          { C::ff_gt_p_sub_b_hi, p_sub_b_witness.hi },
                          { C::ff_gt_borrow, res_witness.borrow ? 1 : 0 },
                          { C::ff_gt_res_lo, res_witness.lo },
                          { C::ff_gt_res_hi, res_witness.hi },
                          { C::ff_gt_cmp_rng_ctr, cmp_rng_ctr },
                          { C::ff_gt_sel_shift_rng, cmp_rng_ctr > 0 ? 1 : 0 },
                          { C::ff_gt_cmp_rng_ctr_inv, cmp_rng_ctr_inv } } });
 
            row++;
 
            // After the first row, sel_gt and sel_dec are no longer active.
            // Subsequent rows are shift rows for completing the range checks.
            sel_gt = false;
            sel_dec = false;
 
            // Shift the limbs left for range checking in the next row.
            // The shifting pattern ensures all limbs are eventually range-checked via a_lo and a_hi columns:
            //   p_sub_a → a_limbs
            //   b_limbs → p_sub_a_witness
            //   p_sub_b_witness → b_limbs
            //   res_witness → p_sub_b_witness
            // This corresponds to the PIL shift constraints (SHIFT_P_SUB_A_TO_A_LO, etc.)
            a_limbs.lo = p_sub_a_witness.lo;
            a_limbs.hi = p_sub_a_witness.hi;
            p_sub_a_witness.lo = b_limbs.lo;
            p_sub_a_witness.hi = b_limbs.hi;
            b_limbs.lo = p_sub_b_witness.lo;
            b_limbs.hi = p_sub_b_witness.hi;
            p_sub_b_witness.lo = res_witness.lo;
            p_sub_b_witness.hi = res_witness.hi;
            res_witness.lo = 0;
            res_witness.hi = 0;
        }
    }
}
 
const InteractionDefinition FieldGreaterThanTraceBuilder::interactions =
    InteractionDefinition()
        .add<lookup_ff_gt_a_lo_range_settings, InteractionType::LookupGeneric>()
        .add<lookup_ff_gt_a_hi_range_settings, InteractionType::LookupGeneric>();
 
} // namespace bb::avm2::tracegen