keccak_output.hpp

#pragma once
 
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/numeric/bitop/pow.hpp"
#include "barretenberg/numeric/bitop/sparse_form.hpp"
 
#include "../sparse.hpp"
#include "../types.hpp"
 
namespace plookup {
namespace keccak_tables {
 
class KeccakOutput {
 
  public:
    static constexpr uint64_t BASE = 11;
 
    // effective base = maximum value each input 'quasi-bit' can reach
    // (the input is in base-11 representation, but at this point in the Keccak algorithm each 'quasi-bit' can only
    // take values [0, 1] not [0, ..., 10]
    static constexpr uint64_t EFFECTIVE_BASE = 2;
    static constexpr size_t TABLE_BITS = 8;
 
    static constexpr uint64_t OUTPUT_NORMALIZATION_TABLE[2]{ 0, 1 };
 
    static constexpr std::array<uint64_t, TABLE_BITS> get_scaled_bases()
    {
        std::array<uint64_t, TABLE_BITS> result;
        uint64_t acc = 1;
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            result[i] = acc;
            acc *= BASE;
        }
        return result;
    }
 
    static std::array<uint64_t, 2> get_column_values_for_next_row(std::array<size_t, TABLE_BITS>& counts)
    {
        static constexpr auto scaled_bases = get_scaled_bases();
 
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            if (counts[i] == EFFECTIVE_BASE - 1) {
                counts[i] = 0;
            } else {
                counts[i] += 1;
                break;
            }
        }
 
        uint64_t value = 0;
        uint64_t normalized_value = 0;
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            value += counts[i] * scaled_bases[i];
            normalized_value += (OUTPUT_NORMALIZATION_TABLE[counts[i]]) << i;
        }
        return { value, normalized_value };
    }
 
    static BasicTable generate_keccak_output_table(BasicTableId id, const size_t table_index)
    {
        BasicTable table;
        table.id = id;
        table.table_index = table_index;
        table.use_twin_keys = false;
        table.size = numeric::pow64(static_cast<uint64_t>(EFFECTIVE_BASE), TABLE_BITS);
 
        std::array<size_t, TABLE_BITS> counts{};
        std::array<uint64_t, 2> column_values{ 0, 0 };
 
        for (size_t i = 0; i < table.size; ++i) {
            table.column_1.emplace_back(column_values[0]);
            table.column_2.emplace_back(column_values[1]);
            table.column_3.emplace_back(0);
            column_values = get_column_values_for_next_row(counts);
        }
 
        table.get_values_from_key = &sparse_tables::get_sparse_normalization_values<BASE, OUTPUT_NORMALIZATION_TABLE>;
 
        table.column_1_step_size = barretenberg::fr(numeric::pow64(static_cast<size_t>(BASE), TABLE_BITS));
        table.column_2_step_size = barretenberg::fr(((uint64_t)1 << TABLE_BITS));
        table.column_3_step_size = 0;
        return table;
    }
 
    static MultiTable get_keccak_output_table(const MultiTableId id = KECCAK_FORMAT_OUTPUT)
    {
        constexpr size_t num_tables_per_multitable =
            64 / TABLE_BITS + (64 % TABLE_BITS == 0 ? 0 : 1); // 64 bits, 8 bits per entry
 
        uint64_t column_multiplier = numeric::pow64(BASE, TABLE_BITS);
        MultiTable table(column_multiplier, (1ULL << TABLE_BITS), 0, num_tables_per_multitable);
 
        table.id = id;
        for (size_t i = 0; i < num_tables_per_multitable; ++i) {
            table.slice_sizes.emplace_back(numeric::pow64(BASE, TABLE_BITS));
            table.lookup_ids.emplace_back(KECCAK_OUTPUT);
            table.get_table_values.emplace_back(
                &sparse_tables::get_sparse_normalization_values<BASE, OUTPUT_NORMALIZATION_TABLE>);
        }
        return table;
    }
};
 
} // namespace keccak_tables
} // namespace plookup