wnaf.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include <cstdint>
 
// NOLINTBEGIN(readability-implicit-bool-conversion)
 
namespace bb::wnaf {
constexpr size_t SCALAR_BITS = 127;
 
#define WNAF_SIZE(x) ((bb::wnaf::SCALAR_BITS + (x) - 1) / (x)) // NOLINT(cppcoreguidelines-macro-usage)
 
template <size_t bits, size_t bit_position> inline uint64_t get_wnaf_bits_const(const uint64_t* scalar) noexcept
{
    if constexpr (bits == 0) {
        return 0ULL;
    } else {
        constexpr size_t lo_limb_idx = bit_position / 64;
        constexpr size_t hi_limb_idx = (bit_position + bits - 1) / 64;
        constexpr uint64_t lo_shift = bit_position & 63UL;
        constexpr uint64_t bit_mask = (1UL << static_cast<uint64_t>(bits)) - 1UL;
 
        uint64_t lo = (scalar[lo_limb_idx] >> lo_shift);
        if constexpr (lo_limb_idx == hi_limb_idx) {
            return lo & bit_mask;
        } else {
            constexpr uint64_t hi_shift = 64UL - (bit_position & 63UL);
            uint64_t hi = ((scalar[hi_limb_idx] << (hi_shift)));
            return (lo | hi) & bit_mask;
        }
    }
}
 
inline uint64_t get_wnaf_bits(const uint64_t* scalar, const uint64_t bits, const uint64_t bit_position) noexcept
{
 
    const auto lo_limb_idx = static_cast<size_t>(bit_position >> 6);
    const auto hi_limb_idx = static_cast<size_t>((bit_position + bits - 1) >> 6);
    const uint64_t lo_shift = bit_position & 63UL;
    const uint64_t bit_mask = (1UL << static_cast<uint64_t>(bits)) - 1UL;
 
    const uint64_t lo = (scalar[lo_limb_idx] >> lo_shift);
    const uint64_t hi_shift = bit_position ? 64UL - (bit_position & 63UL) : 0;
    const uint64_t hi = ((scalar[hi_limb_idx] << (hi_shift)));
    const uint64_t hi_mask = bit_mask & (0ULL - (lo_limb_idx != hi_limb_idx));
 
    return (lo & bit_mask) | (hi & hi_mask);
}
 
inline void fixed_wnaf(const uint64_t* scalar,
                       uint64_t* wnaf,
                       bool& skew_map,
                       const uint64_t point_index,
                       const uint64_t num_points,
                       const size_t wnaf_bits) noexcept
{
    // If the scalar is even, we set the skew map to true. The skew is used to subtract a base point from the msm result
    // in case scalar is even.
    skew_map = ((scalar[0] & 1) == 0);
    // The first slice is the least significant slice of the scalar.
    uint64_t previous = get_wnaf_bits(scalar, wnaf_bits, 0) + static_cast<uint64_t>(skew_map);
    const size_t wnaf_entries = (SCALAR_BITS + wnaf_bits - 1) / wnaf_bits;
 
    // For the rest we start a rolling window of wnaf_bits bits, and compute the wnaf slice.
    for (size_t round_i = 1; round_i < wnaf_entries - 1; ++round_i) {
        uint64_t slice = get_wnaf_bits(scalar, wnaf_bits, round_i * wnaf_bits);
        // Check if the slice is even. This will be used to borrow from the previous slice.
        uint64_t predicate = ((slice & 1UL) == 0UL);
        // If the current slice is odd (predicate=0), the WNAF digit is simply `previous`.
        // If even (predicate=1), we borrow: subtract 2^wnaf_bits from `previous` to get a
        // negative value, then negate via XOR with all-ones (two's complement identity:
        // -x = ~x + 1, but we immediately shift right by 1, absorbing the +1 since the
        // result is guaranteed odd). The >> 1 converts from the raw odd value to a bucket
        // index (e.g., value 5 → bucket 2, value 7 → bucket 3). Bit 31 stores the sign
        // (1 = negative), and the upper bits carry point_index for multi-scalar indexing.
        wnaf[(wnaf_entries - round_i) * num_points] =
            ((((previous - (predicate << wnaf_bits)) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) |
            (point_index);
        // Carry the borrow into the next window: if we borrowed, add 1 to the current slice.
        previous = slice + predicate;
    }
    size_t final_bits = SCALAR_BITS - (wnaf_bits * (wnaf_entries - 1));
    uint64_t slice = get_wnaf_bits(scalar, final_bits, (wnaf_entries - 1) * wnaf_bits);
    uint64_t predicate = ((slice & 1UL) == 0UL);
 
    wnaf[num_points] =
        ((((previous - (predicate << (wnaf_bits))) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) | (point_index);
    wnaf[0] = ((slice + predicate) >> 1UL) | (point_index);
}
 
template <size_t num_points, size_t wnaf_bits, size_t round_i>
inline void wnaf_round(uint64_t* scalar, uint64_t* wnaf, const uint64_t point_index, const uint64_t previous) noexcept
{
    constexpr size_t wnaf_entries = (SCALAR_BITS + wnaf_bits - 1) / wnaf_bits;
    constexpr auto log2_num_points = static_cast<size_t>(numeric::get_msb(static_cast<uint32_t>(num_points)));
 
    if constexpr (round_i < wnaf_entries - 1) {
        uint64_t slice = get_wnaf_bits(scalar, wnaf_bits, round_i * wnaf_bits);
        uint64_t predicate = ((slice & 1UL) == 0UL);
        wnaf[(wnaf_entries - round_i) << log2_num_points] =
            ((((previous - (predicate << wnaf_bits)) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) |
            (point_index << 32UL);
        wnaf_round<num_points, wnaf_bits, round_i + 1>(scalar, wnaf, point_index, slice + predicate);
    } else {
        constexpr size_t final_bits = SCALAR_BITS - (SCALAR_BITS / wnaf_bits) * wnaf_bits;
        uint64_t slice = get_wnaf_bits(scalar, final_bits, (wnaf_entries - 1) * wnaf_bits);
        uint64_t predicate = ((slice & 1UL) == 0UL);
        wnaf[num_points] =
            ((((previous - (predicate << wnaf_bits)) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) |
            (point_index << 32UL);
        wnaf[0] = ((slice + predicate) >> 1UL) | (point_index << 32UL);
    }
}
 
template <size_t scalar_bits, size_t num_points, size_t wnaf_bits, size_t round_i>
inline void wnaf_round(uint64_t* scalar, uint64_t* wnaf, const uint64_t point_index, const uint64_t previous) noexcept
{
    constexpr size_t wnaf_entries = (scalar_bits + wnaf_bits - 1) / wnaf_bits;
    constexpr auto log2_num_points = static_cast<uint64_t>(numeric::get_msb(static_cast<uint32_t>(num_points)));
 
    if constexpr (round_i < wnaf_entries - 1) {
        uint64_t slice = get_wnaf_bits_const<wnaf_bits, round_i * wnaf_bits>(scalar);
        uint64_t predicate = ((slice & 1UL) == 0UL);
        wnaf[(wnaf_entries - round_i) << log2_num_points] =
            ((((previous - (predicate << wnaf_bits)) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) |
            (point_index << 32UL);
        wnaf_round<scalar_bits, num_points, wnaf_bits, round_i + 1>(scalar, wnaf, point_index, slice + predicate);
    } else {
        constexpr size_t final_bits = ((scalar_bits / wnaf_bits) * wnaf_bits == scalar_bits)
                                          ? wnaf_bits
                                          : scalar_bits - (scalar_bits / wnaf_bits) * wnaf_bits;
        uint64_t slice = get_wnaf_bits_const<final_bits, (wnaf_entries - 1) * wnaf_bits>(scalar);
        uint64_t predicate = ((slice & 1UL) == 0UL);
        wnaf[num_points] =
            ((((previous - (predicate << wnaf_bits)) ^ (0UL - predicate)) >> 1UL) | (predicate << 31UL)) |
            (point_index << 32UL);
        wnaf[0] = ((slice + predicate) >> 1UL) | (point_index << 32UL);
    }
}
 
template <size_t num_points, size_t wnaf_bits>
inline void fixed_wnaf(uint64_t* scalar, uint64_t* wnaf, bool& skew_map, const size_t point_index) noexcept
{
    skew_map = ((scalar[0] & 1) == 0);
    uint64_t previous = get_wnaf_bits_const<wnaf_bits, 0>(scalar) + static_cast<uint64_t>(skew_map);
    wnaf_round<num_points, wnaf_bits, 1UL>(scalar, wnaf, point_index, previous);
}
 
template <size_t num_bits, size_t num_points, size_t wnaf_bits>
inline void fixed_wnaf(uint64_t* scalar, uint64_t* wnaf, bool& skew_map, const size_t point_index) noexcept
{
    skew_map = ((scalar[0] & 1) == 0);
    uint64_t previous = get_wnaf_bits_const<wnaf_bits, 0>(scalar) + static_cast<uint64_t>(skew_map);
    wnaf_round<num_bits, num_points, wnaf_bits, 1UL>(scalar, wnaf, point_index, previous);
}
 
} // namespace bb::wnaf
 
// NOLINTEND(readability-implicit-bool-conversion)