ram_table.cpp

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: }
// =====================
 
#include "ram_table.hpp"
 
#include "../circuit_builders/circuit_builders.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/numeric/uint256/uint256.hpp"
#include "barretenberg/transcript/origin_tag.hpp"
#include <vector>
 
namespace bb::stdlib {
 
template <typename Builder>
ram_table<Builder>::ram_table(Builder* builder, const std::vector<field_pt>& table_entries)
    : raw_entries(table_entries)
    , length(table_entries.size())
    , context(builder)
{
    index_initialized.resize(length, false);
 
    // For consistency with the other constructor, we delegate the initialization of the table to the first read
    // operation.
 
    // Store tags
    _tags.resize(length);
    for (size_t i = 0; i < length; i++) {
        _tags[i] = table_entries[i].get_origin_tag();
    }
}
 
template <typename Builder>
ram_table<Builder>::ram_table(const std::vector<field_pt>& table_entries)
    : raw_entries(table_entries)
    , length(raw_entries.size())
{
    for (const auto& entry : table_entries) {
        if (entry.get_context() != nullptr) {
            context = entry.get_context();
            break;
        }
    }
 
    index_initialized.resize(length, false);
 
    // Do not initialize the table yet. The input entries might all be constant,
    // if this is the case we might not have a valid pointer to a Builder
    // We get around this, by initializing the table when `read` or `write` operator is called
    // with a non-const field element.
 
    // Store tags
    _tags.resize(length);
    for (size_t i = 0; i < length; i++) {
        _tags[i] = table_entries[i].get_origin_tag();
    }
}
 
template <typename Builder> void ram_table<Builder>::initialize_table() const
{
    if (ram_table_generated_in_builder) {
        return;
    }
    // only call this when there is a context
    BB_ASSERT(context != nullptr);
    ram_id = context->create_RAM_array(length);
 
    if (raw_entries.size() > 0) {
        for (size_t i = 0; i < length; ++i) {
            if (!index_initialized[i]) {
                field_pt entry;
                if (raw_entries[i].is_constant()) {
                    entry = field_pt::from_witness_index(context,
                                                         context->put_constant_variable(raw_entries[i].get_value()));
                } else {
                    entry = raw_entries[i];
                }
                context->init_RAM_element(ram_id, i, entry.get_witness_index());
                index_initialized[i] = true;
            }
        }
    }
 
    // Store the tags of the original entries
    _tags.resize(length);
    if (raw_entries.size() > 0) {
        for (size_t i = 0; i < length; i++) {
            _tags[i] = raw_entries[i].get_origin_tag();
        }
    }
    ram_table_generated_in_builder = true;
}
// constructors and move operators
template <typename Builder> ram_table<Builder>::ram_table(const ram_table& other) = default;
 
template <typename Builder>
ram_table<Builder>::ram_table(ram_table&& other) noexcept
    : raw_entries(std::move(other.raw_entries))
    , _tags(std::move(other._tags))
    , index_initialized(std::move(other.index_initialized))
    , length(other.length)
    , ram_id(other.ram_id)
    , ram_table_generated_in_builder(other.ram_table_generated_in_builder)
    , all_entries_written_to_with_constant_index(other.all_entries_written_to_with_constant_index)
    , context(other.context)
{
    other.length = 0;
    other.ram_id = 0;
    other.ram_table_generated_in_builder = false;
    other.all_entries_written_to_with_constant_index = false;
    other.context = nullptr;
}
 
template <typename Builder> ram_table<Builder>& ram_table<Builder>::operator=(const ram_table& other) = default;
 
template <typename Builder> ram_table<Builder>& ram_table<Builder>::operator=(ram_table&& other) noexcept
{
    if (this != &other) {
        raw_entries = std::move(other.raw_entries);
        _tags = std::move(other._tags);
        index_initialized = std::move(other.index_initialized);
        length = other.length;
        ram_id = other.ram_id;
        ram_table_generated_in_builder = other.ram_table_generated_in_builder;
        all_entries_written_to_with_constant_index = other.all_entries_written_to_with_constant_index;
        context = other.context;
 
        other.length = 0;
        other.ram_id = 0;
        other.ram_table_generated_in_builder = false;
        other.all_entries_written_to_with_constant_index = false;
        other.context = nullptr;
    }
    return *this;
}
 
template <typename Builder> field_t<Builder> ram_table<Builder>::read(const field_pt& index) const
{
    if (context == nullptr) {
        context = index.get_context();
        BB_ASSERT_NEQ(
            context,
            nullptr,
            "ram_table: Performing a read operation without providing a context. We cannot initialize the table.");
    }
 
    // When we perform the first read operation, we initialize the table
    initialize_table();
 
    const auto native_index = uint256_t(index.get_value());
    if (native_index >= length) {
        // set a failure when the index is out of bounds. another error will be thrown when we try to call
        // `read_RAM_array`.
        context->failure("ram_table: RAM array access out of bounds");
    }
 
    if (!check_indices_initialized()) {
        context->failure("ram_table must have initialized every RAM entry before the table can be read");
    }
 
    field_pt index_wire = index;
    if (index.is_constant()) {
        index_wire = field_pt::from_witness_index(context, context->put_constant_variable(index.get_value()));
    }
 
    uint32_t output_idx = context->read_RAM_array(ram_id, index_wire.get_witness_index());
    auto element = field_pt::from_witness_index(context, output_idx);
 
    const size_t cast_index = static_cast<size_t>(static_cast<uint64_t>(native_index));
    // If the index is legitimate, restore the tag
    if (native_index < length) {
        element.set_origin_tag(_tags[cast_index]);
    }
    return element;
}
 
template <typename Builder> void ram_table<Builder>::write(const field_pt& index, const field_pt& value)
{
    if (context == nullptr) {
        context = index.get_context();
        BB_ASSERT_NEQ(
            context,
            nullptr,
            "ram_table: Performing a write operation without providing a context. We cannot initialize the table.");
    }
 
    // When we perform the first read operation, we initialize the table
    initialize_table();
 
    if (uint256_t(index.get_value()) >= length) {
        // set a failure when the index is out of bounds. an error will be thrown when we try to call either
        // `init_RAM_element` or `write_RAM_array`.
        context->failure("ram_table: RAM array access out of bounds");
    }
 
    field_pt index_wire = index;
    const auto native_index = uint256_t(index.get_value());
    if (index.is_constant()) {
        // need to write/process every array element at constant indicies before doing reads/writes at prover-defined
        // indices
        index_wire.convert_constant_to_fixed_witness(context);
    } else {
        if (!check_indices_initialized()) {
            context->failure("ram_table must have initialized every RAM entry before a write can be performed");
        }
    }
 
    field_pt value_wire = value;
    auto native_value = value.get_value();
    if (value.is_constant()) {
        value_wire = field_pt::from_witness_index(context, context->put_constant_variable(native_value));
    }
 
    const size_t cast_index = static_cast<size_t>(static_cast<uint64_t>(native_index));
    if (index.is_constant() && !index_initialized[cast_index]) {
        context->init_RAM_element(ram_id, cast_index, value_wire.get_witness_index());
 
        index_initialized[cast_index] = true;
    } else {
        context->write_RAM_array(ram_id, index_wire.get_witness_index(), value_wire.get_witness_index());
    }
    // Update the value of the stored tag, if index is legitimate
 
    if (native_index < length) {
        _tags[cast_index] = value.get_origin_tag();
    }
}
 
template class ram_table<bb::UltraCircuitBuilder>;
template class ram_table<bb::MegaCircuitBuilder>;
} // namespace bb::stdlib