PowersOf2.hpp

#ifndef _SNARKFRONT_POWERS_OF_2_HPP_
#define _SNARKFRONT_POWERS_OF_2_HPP_

#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <gmp.h>
#include <vector>

#include <snarklib/BigInt.hpp>
#include <snarklib/Field.hpp>

namespace snarkfront {

// look up table for powers of 2 for BigInt/field/group
template <typename T>
class PowersOf2
{
public:
    PowersOf2()
        : m_lut(1, T::one())
    {}

    const T& lookUp(const std::size_t index) 
    {
        // protect against huge index from accidental pointer argument
#ifdef USE_ASSERT
        assert(index < 1024);
#endif

        for (std::size_t i = m_lut.size(); i <= index; ++i) {
            // m_lut[i] = 2 * m_lut[i - 1];
            m_lut.emplace_back(m_lut.back() + m_lut.back());
        }

        return m_lut[index];
    }

    T getNumber(const std::size_t number) {
        T accum = T::zero();

        auto b = number;
        std::size_t i = 0;
        while (b) {
            if (b & 0x1)
                accum = accum + lookUp(i);

            b >>= 1;
            ++i;
        }

        return accum;
    }

    T getNumber(const std::vector<int>& bits) {
        T accum = T::zero();

        for (std::size_t i = 0; i < bits.size(); ++i) {
            if (bits[i])
                accum = accum + lookUp(i);
        }

        return accum;
    }

private:
    std::vector<T> m_lut; // index -> T(2^index)
};

// convert Boolean to one and zero
bool zero_internal(const bool& dummy);
bool one_internal(const bool& dummy);

template <typename T, std::size_t N>
static snarklib::Field<T, N> zero_internal(const snarklib::Field<T, N>& dummy) {
    return snarklib::Field<T, N>::zero();
}

template <typename T, std::size_t N>
static snarklib::Field<T, N> one_internal(const snarklib::Field<T, N>& dummy) {
    return snarklib::Field<T, N>::one();
}

template <typename T>
T boolTo(const bool a) {
    T dummy;
    return a ? one_internal(dummy) : zero_internal(dummy);
}

// size of type in bits
std::size_t sizeBits(const bool& dummy);
std::size_t sizeBits(const std::uint8_t& dummy);
std::size_t sizeBits(const std::uint32_t& dummy);
std::size_t sizeBits(const std::uint64_t& dummy);

template <mp_size_t N>
std::size_t sizeBits(const snarklib::BigInt<N>& dummy) {
    return snarklib::BigInt<N>::maxBits();
}

template <typename T, std::size_t N>
std::size_t sizeBits(const snarklib::Field<T, N>& dummy) {
    return snarklib::Field<T, N>::sizeInBits();
}

// returns number of matching bits starting from most significant bit
template <typename BIT>
int matchMSB(const std::vector<BIT>& a,
             const std::vector<BIT>& b)
{
    if (a.size() != b.size())
        return -1; // a and b are different sizes, no matching bits

    for (int i = a.size() - 1; i >= 0; --i) {
        if (bool(a[i] != b[i]))
            return a.size() - 1 - i; // some bits match
    }

    return a.size(); // all bits match
}

// convert value to bits
std::vector<int> valueBits(const bool& a);
std::vector<int> valueBits(const std::uint8_t& a);
std::vector<int> valueBits(const std::uint32_t& a);
std::vector<int> valueBits(const std::uint64_t& a);

template <mp_size_t N>
std::vector<int> valueBits(const snarklib::BigInt<N>& a) {
    std::vector<int> v;
    v.reserve(sizeBits(a));

    for (std::size_t i = 0; i < sizeBits(a); ++i) {
        v.push_back(a.testBit(i));
    }

    return v;
}

template <typename T, std::size_t N>
std::vector<int> valueBits(const snarklib::Field<T, N>& a) {
#ifdef USE_ASSERT
    assert(1 == a.dimension()); // always true for elliptic curve
                                // scalar field
#endif
    return valueBits(a[0].asBigInt());
}

// convert bits to value
template <typename UINT_N>
std::vector<int> bitsValue(UINT_N& a, const std::vector<int>& b)
{
    UINT_N result = 0;
    const std::size_t N = std::min(sizeBits(a), b.size());
    for (std::size_t i = 0; i < N; ++i) {
        result |= (UINT_N(b[i]) << i);
    }

    a = result;

    std::vector<int> v;
    for (std::size_t i = N; i < b.size(); ++i) {
        v.push_back(b[i]);
    }

    return v;
}

// count number of set bits
std::size_t countBits(const std::vector<int>& v);

// overflow addition (uint8_t, uint32_t and uint64_t)
template <typename UINT_N>
void addover(UINT_N& a1, UINT_N& a0, const UINT_N& b) 
{
    // a0 = 2 * a0_half + a0_bit
    // b = 2 * b_half + b_bit
    const UINT_N
        a0_half = a0 >> 1, a0_bit = a0 & 0x1,
        b_half = b >> 1, b_bit = b & 0x1;

    // a0 + b = 2 * (a0_half + b_half) + (a0_bit + b_bit)
    //        = 2 * halfsum + a0_bit + b_bit
    const UINT_N halfsum = a0_half + b_half;

    // (high, low) = a0 + b
    UINT_N
        high = halfsum >> (sizeBits(high) - 1), // carry bit
        low = (halfsum << 1) + a0_bit;

    const UINT_N lowOriginal = low;
    low += b_bit;
    if ((0 == low) && (-1 == lowOriginal)) ++high; // handle carry

    // accumulate result
    a1 += high;
    a0 = low;
}

// overflow multiplication (uint8_t, uint32_t and uint64_t)
#define DEFN_MULOVER(T) void mulover(T& c1, T& c0, const T& a, const T& b);

DEFN_MULOVER(std::uint8_t)
DEFN_MULOVER(std::uint32_t)
DEFN_MULOVER(std::uint64_t)

#undef DEFN_MULOVER

} // namespace snarkfront

#endif