rom_ram_logic.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Raju], commit: 05a381f8b31ae4648e480f1369e911b148216e8b}
// external_1:  { status: Complete, auditors: [Sherlock], commit: e6694849223 }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include "barretenberg/common/assert.hpp"
#include <array>
#include <cstdint>
#include <vector>
 
namespace bb {
// Forward declaration
template <typename ExecutionTrace_> class UltraCircuitBuilder_;
 
// Constants
static constexpr uint32_t UNINITIALIZED_MEMORY_RECORD = UINT32_MAX;
 
struct RomRecord {
    enum AccessType {
        TABLE_ENTRY, // row written by set_ROM_element / set_ROM_element_pair
        READ,        // row written by read_ROM_array / read_ROM_array_pair
    };
    uint32_t index_witness = 0; // Witness value of the index in the particular ROM block that contains this row.
    uint32_t value_column1_witness = 0;
    uint32_t value_column2_witness = 0;
    uint32_t index = 0;
    AccessType access_type = AccessType::READ;
    uint32_t record_witness = 0; // Record, a.k.a. "fingerprint" of the row.
    size_t gate_index = 0;       // Index in the memory block where the ROM gate will live.
    bool operator<(const RomRecord& other) const
    {
        return index < other.index || (index == other.index && gate_index < other.gate_index);
    }
    bool operator==(const RomRecord& other) const noexcept
    {
        return index_witness == other.index_witness && value_column1_witness == other.value_column1_witness &&
               value_column2_witness == other.value_column2_witness && index == other.index &&
               access_type == other.access_type && record_witness == other.record_witness &&
               gate_index == other.gate_index;
    }
};
 
struct RamRecord {
    enum AccessType {
        READ,
        WRITE,
    };
    uint32_t index_witness = 0;
    uint32_t timestamp_witness = 0;
    uint32_t value_witness = 0;
    uint32_t index = 0;
    uint32_t timestamp = 0;
    AccessType access_type = AccessType::READ;
    uint32_t record_witness = 0; // Record, a.k.a. "fingerprint" of the row.
    size_t gate_index = 0;       // Index in the memory block where the RAM gate will live.
    bool operator<(const RamRecord& other) const
    {
        bool index_test = (index) < (other.index);
        return index_test || (index == other.index && timestamp < other.timestamp);
    }
    bool operator==(const RamRecord& other) const noexcept
    {
        return index_witness == other.index_witness && timestamp_witness == other.timestamp_witness &&
               value_witness == other.value_witness && index == other.index && timestamp == other.timestamp &&
               access_type == other.access_type && record_witness == other.record_witness &&
               gate_index == other.gate_index;
    }
};
 
struct RomTranscript {
    // Contains the value(s) of each index of the array. Note that each index/slot may contain _two_ values.
    std::vector<std::array<uint32_t, 2>> state;
    // A vector of records, each of which contains:
    // + The constant witness with the index
    // + The value in the memory slot
    // + The actual index value
    std::vector<RomRecord> records;
    // Whether this ROM array uses the LogUp scheme (single-value tables) or the sorted-trace scheme
    // (value-pair tables). Set on the first set/read call; once set, the array commits to that scheme.
    bool use_logup = false;
    // Used to check that the state hasn't changed in tests
    bool operator==(const RomTranscript& other) const noexcept
    {
        return (state == other.state && records == other.records && use_logup == other.use_logup);
    }
};
 
struct RamTranscript {
    // Contains the value of each index of the array
    std::vector<uint32_t> state;
    // A vector of records, each of which contains:
    // + The constant witness with the index
    // + The type of operation (READ or WRITE)
    // + The _current_ value in the memory slot
    // + The actual index value
    std::vector<RamRecord> records;
    // The number of times this RAM array has been touched (i.e., has had a READ or WRITE operation performed on it).
    // used for RAM records, to compute the timestamp when performing a read/write. Note that the timestamp is _not_ a
    // global timestamp; rather, it is a timestamp for the RAM array in question.
    uint32_t access_count = 0;
    // Used to check that the state hasn't changed in tests
    bool operator==(const RamTranscript& other) const noexcept
    {
        return (state == other.state && records == other.records && access_count == other.access_count);
    }
};
 
template <typename ExecutionTrace> class RomRamLogic_ {
  public:
    using FF = typename ExecutionTrace::FF;
    using CircuitBuilder = UltraCircuitBuilder_<ExecutionTrace>;
 
    // Storage
    std::vector<RamTranscript> ram_arrays;
    std::vector<RomTranscript> rom_arrays;
 
    RomRamLogic_() = default;
 
    // ROM operations
    size_t create_ROM_array(const size_t array_size);
 
    void set_ROM_element(CircuitBuilder* builder,
                         const size_t rom_id,
                         const size_t index_value,
                         const uint32_t value_witness);
    void set_ROM_element_pair(CircuitBuilder* builder,
                              const size_t rom_id,
                              const size_t index_value,
                              const std::array<uint32_t, 2>& value_witnesses);
    uint32_t read_ROM_array(CircuitBuilder* builder, const size_t rom_id, const uint32_t index_witness);
    std::array<uint32_t, 2> read_ROM_array_pair(CircuitBuilder* builder,
                                                const size_t rom_id,
                                                const uint32_t index_witness);
    void create_ROM_gate(CircuitBuilder* builder, RomRecord& record);
    void create_sorted_ROM_gate(CircuitBuilder* builder, RomRecord& record);
    void process_ROM_array(CircuitBuilder* builder, const size_t rom_id);
 
    // ---- ROM LogUp scheme (single-value tables only) ----
 
    void create_ROM_logup_gate(CircuitBuilder* builder, RomRecord& record, const size_t rom_id, const bool is_read);
 
    void process_ROM_logup_array(CircuitBuilder* builder, const size_t rom_id);
 
    void process_ROM_arrays(CircuitBuilder* builder);
 
    // RAM operations
    size_t create_RAM_array(const size_t array_size);
    void init_RAM_element(CircuitBuilder* builder,
                          const size_t ram_id,
                          const size_t index_value,
                          const uint32_t value_witness);
    uint32_t read_RAM_array(CircuitBuilder* builder, const size_t ram_id, const uint32_t index_witness);
    void write_RAM_array(CircuitBuilder* builder,
                         const size_t ram_id,
                         const uint32_t index_witness,
                         const uint32_t value_witness);
    void create_RAM_gate(CircuitBuilder* builder, RamRecord& record);
    void create_sorted_RAM_gate(CircuitBuilder* builder, RamRecord& record);
    void create_final_sorted_RAM_gate(CircuitBuilder* builder, RamRecord& record, const size_t ram_array_size);
    void process_RAM_array(CircuitBuilder* builder, const size_t ram_id);
    void process_RAM_arrays(CircuitBuilder* builder);
 
    bool operator==(const RomRamLogic_& other) const noexcept
    {
        return ram_arrays == other.ram_arrays && rom_arrays == other.rom_arrays;
    }
};
 
} // namespace bb