variable.hpp

Go to the documentation of this file.

 
#ifndef LIBSNARK_GADGETLIB2_INCLUDE_GADGETLIB2_VARIABLE_HPP_
#define LIBSNARK_GADGETLIB2_INCLUDE_GADGETLIB2_VARIABLE_HPP_
 
#include <cstddef>
#include <iostream>
#include <libsnark/gadgetlib2/infrastructure.hpp>
#include <libsnark/gadgetlib2/pp.hpp>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
 
namespace gadgetlib2
{
 
class GadgetLibAdapter;
 
// Forward declarations
class Protoboard;
class FElemInterface;
class FElem;
class FConst;
class Variable;
class VariableArray;
 
typedef enum { R1P, AGNOSTIC } FieldType;
 
typedef ::std::shared_ptr<Variable> VariablePtr;
typedef ::std::shared_ptr<VariableArray> VariableArrayPtr;
typedef ::std::unique_ptr<FElemInterface> FElemInterfacePtr;
typedef ::std::shared_ptr<Protoboard> ProtoboardPtr;
typedef unsigned long VarIndex_t;
 
// Naming Conventions:
// R1P == Rank 1 Prime characteristic
 
class FElemInterface
{
public:
    virtual FElemInterface &operator=(const long n) = 0;
    virtual FElemInterface &operator=(const FConst &src) = 0;
    virtual ::std::string asString() const = 0;
    virtual FieldType fieldType() const = 0;
    virtual FElemInterface &operator+=(const FElemInterface &other) = 0;
    virtual FElemInterface &operator-=(const FElemInterface &other) = 0;
    virtual FElemInterface &operator*=(const FElemInterface &other) = 0;
    virtual bool operator==(const FElemInterface &other) const = 0;
    virtual bool operator==(const FConst &other) const = 0;
    virtual bool operator==(const long n) const = 0;
    virtual FElemInterfacePtr clone() const = 0;
    virtual FElemInterfacePtr inverse() const = 0;
    virtual long asLong() const = 0;
    virtual int getBit(unsigned int i) const = 0;
    virtual FElemInterface &power(long exponent) = 0;
    virtual ~FElemInterface(){};
}; // class FElemInterface
 
inline bool operator==(const long first, const FElemInterface &second)
{
    return second == first;
}
inline bool operator!=(const long first, const FElemInterface &second)
{
    return !(first == second);
}
inline bool operator!=(const FElemInterface &first, const long second)
{
    return !(first == second);
}
inline bool operator!=(
    const FElemInterface &first, const FElemInterface &second)
{
    return !(first == second);
}
 
class FElem
{
private:
    FElemInterfacePtr elem_;
 
public:
    explicit FElem(const FElemInterface &elem);
    void promoteToFieldType(FieldType type);
    FElem();
    FElem(const long n);
    FElem(const int i);
    FElem(const size_t n);
    FElem(const Fp &elem);
    FElem(const FElem &src);
 
    FElem &operator=(const FElem &other);
    FElem &operator=(FElem &&other);
    FElem &operator=(const long i)
    {
        *elem_ = i;
        return *this;
    }
    ::std::string asString() const { return elem_->asString(); }
    FieldType fieldType() const { return elem_->fieldType(); }
    bool operator==(const FElem &other) const { return *elem_ == *other.elem_; }
    FElem &operator*=(const FElem &other);
    FElem &operator+=(const FElem &other);
    FElem &operator-=(const FElem &other);
    FElem operator-() const
    {
        FElem retval(0);
        retval -= FElem(*elem_);
        return retval;
    }
    FElem inverse(const FieldType &fieldType);
    long asLong() const { return elem_->asLong(); }
    int getBit(unsigned int i, const FieldType &fieldType);
    friend FElem power(const FElem &base, long exponent);
 
    inline friend ::std::ostream &operator<<(
        ::std::ostream &os, const FElem &elem)
    {
        return os << elem.elem_->asString();
    }
 
    friend class GadgetLibAdapter;
}; // class FElem
 
inline bool operator!=(const FElem &first, const FElem &second)
{
    return !(first == second);
}
 
inline bool operator==(const FElem &first, const long second)
{
    return first == FElem(second);
}
inline bool operator==(const long first, const FElem &second)
{
    return second == first;
}
inline bool operator!=(const FElem &first, const long second)
{
    return !(first == second);
}
inline bool operator!=(const long first, const FElem &second)
{
    return !(first == second);
}
 
class FConst : public FElemInterface
{
private:
    long contents_;
    explicit FConst(const long n) : contents_(n) {}
 
public:
    FConst(const FConst &src) : contents_(src.contents_) {}
    virtual FConst &operator=(const long n)
    {
        contents_ = n;
        return *this;
    }
    virtual FConst &operator=(const FConst &src)
    {
        contents_ = src.contents_;
        return *this;
    }
    virtual ::std::string asString() const
    {
        return GADGETLIB2_FMT("%ld", contents_);
    }
    virtual FieldType fieldType() const { return AGNOSTIC; }
    virtual FConst &operator+=(const FElemInterface &other);
    virtual FConst &operator-=(const FElemInterface &other);
    virtual FConst &operator*=(const FElemInterface &other);
    virtual bool operator==(const FElemInterface &other) const
    {
        return other == *this;
    }
    virtual bool operator==(const FConst &other) const
    {
        return contents_ == other.contents_;
    }
    virtual bool operator==(const long n) const { return contents_ == n; }
    virtual FElemInterfacePtr clone() const
    {
        return FElemInterfacePtr(new FConst(*this));
    }
    virtual FElemInterfacePtr inverse() const;
    long asLong() const { return contents_; }
    int getBit(unsigned int i) const
    {
        libff::UNUSED(i);
        GADGETLIB_FATAL("Cannot get bit from FConst.");
    }
    virtual FElemInterface &power(long exponent);
 
    friend class FElem; // allow constructor call
};                      // class FConst
 
class R1P_Elem : public FElemInterface
{
private:
    Fp elem_;
 
public:
    explicit R1P_Elem(const Fp &elem) : elem_(elem) {}
    virtual R1P_Elem &operator=(const FConst &src)
    {
        elem_ = src.asLong();
        return *this;
    }
    virtual R1P_Elem &operator=(const long n)
    {
        elem_ = Fp(n);
        return *this;
    }
    virtual ::std::string asString() const
    {
        return GADGETLIB2_FMT("%u", elem_.as_ulong());
    }
    virtual FieldType fieldType() const { return R1P; }
    virtual R1P_Elem &operator+=(const FElemInterface &other);
    virtual R1P_Elem &operator-=(const FElemInterface &other);
    virtual R1P_Elem &operator*=(const FElemInterface &other);
    virtual bool operator==(const FElemInterface &other) const;
    virtual bool operator==(const FConst &other) const
    {
        return elem_ == Fp(other.asLong());
    }
    virtual bool operator==(const long n) const { return elem_ == Fp(n); }
    virtual FElemInterfacePtr clone() const
    {
        return FElemInterfacePtr(new R1P_Elem(*this));
    }
    virtual FElemInterfacePtr inverse() const;
    long asLong() const;
    int getBit(unsigned int i) const { return elem_.as_bigint().test_bit(i); }
    virtual FElemInterface &power(long exponent)
    {
        elem_ ^= exponent;
        return *this;
    }
 
    friend class FElem; // allow constructor call
    friend class GadgetLibAdapter;
};
 
class Variable
{
private:
    VarIndex_t index_; 
    static VarIndex_t nextFreeIndex_; 
#ifdef DEBUG
    ::std::string name_;
#endif
 
public:
    explicit Variable(const ::std::string &name = "");
    virtual ~Variable();
 
    ::std::string name() const;
 
    struct VariableStrictOrder {
        bool operator()(const Variable &first, const Variable &second) const
        {
            return first.index_ < second.index_;
        }
    };
 
    typedef ::std::map<Variable, FElem, Variable::VariableStrictOrder>
        VariableAssignment;
    FElem eval(const VariableAssignment &assignment) const;
 
    typedef ::std::set<Variable, VariableStrictOrder> set;
    typedef ::std::multiset<Variable, VariableStrictOrder> multiset;
 
    friend class GadgetLibAdapter;
}; // class Variable
 
typedef ::std::map<Variable, FElem, Variable::VariableStrictOrder>
    VariableAssignment;
 
typedef ::std::vector<Variable> VariableArrayContents;
 
class VariableArray : public VariableArrayContents
{
private:
#ifdef DEBUG
    ::std::string name_;
#endif
public:
    explicit VariableArray(const ::std::string &name = "");
    explicit VariableArray(const int size, const ::std::string &name = "");
    explicit VariableArray(const size_t size, const ::std::string &name = "");
    explicit VariableArray(const size_t size, const Variable &contents)
        : VariableArrayContents(size, contents)
    {
    }
 
    using VariableArrayContents::operator[];
    using VariableArrayContents::at;
    using VariableArrayContents::push_back;
    using VariableArrayContents::size;
 
    ::std::string name() const;
}; // class VariableArray
 
typedef Variable FlagVariable;
typedef VariableArray FlagVariableArray;
 
typedef Variable PackedWord;
typedef VariableArray PackedWordArray;
 
class UnpackedWord : public VariableArray
{
public:
    UnpackedWord() : VariableArray() {}
    UnpackedWord(const size_t numBits, const ::std::string &name)
        : VariableArray(numBits, name)
    {
    }
}; // class UnpackedWord
 
typedef ::std::vector<UnpackedWord> UnpackedWordArray;
 
class MultiPackedWord : public VariableArray
{
private:
    size_t numBits_;
    FieldType fieldType_;
    size_t getMultipackedSize() const;
 
public:
    MultiPackedWord(const FieldType &fieldType = AGNOSTIC);
    MultiPackedWord(
        const size_t numBits,
        const FieldType &fieldType,
        const ::std::string &name);
    void resize(const size_t numBits);
    ::std::string name() const { return VariableArray::name(); }
}; // class MultiPackedWord
 
typedef ::std::vector<MultiPackedWord> MultiPackedWordArray;
 
class DualWord
{
private:
    MultiPackedWord multipacked_;
    UnpackedWord unpacked_;
 
public:
    DualWord(const FieldType &fieldType) : multipacked_(fieldType), unpacked_()
    {
    }
    DualWord(
        const size_t numBits,
        const FieldType &fieldType,
        const ::std::string &name);
    DualWord(const MultiPackedWord &multipacked, const UnpackedWord &unpacked);
    MultiPackedWord multipacked() const { return multipacked_; }
    UnpackedWord unpacked() const { return unpacked_; }
    FlagVariable bit(size_t i) const
    {
        return unpacked_[i];
    } // syntactic sugar, same as unpacked()[i]
    size_t numBits() const { return unpacked_.size(); }
    void resize(size_t newSize);
}; // class DualWord
 
class DualWordArray
{
private:
    // kept as 2 separate arrays because the more common usecase will be to
    // request one of these, and not dereference a specific DualWord
    MultiPackedWordArray multipackedContents_;
    UnpackedWordArray unpackedContents_;
    size_t numElements_;
 
public:
    DualWordArray(const FieldType &fieldType);
    DualWordArray(
        const MultiPackedWordArray &multipackedContents, // TODO delete, for dev
        const UnpackedWordArray &unpackedContents);
    MultiPackedWordArray multipacked() const;
    UnpackedWordArray unpacked() const;
    // For cases in which we can assume each unpacked value fits < in 1 packed
    // Variable
    PackedWordArray packed() const;
    void push_back(const DualWord &dualWord);
    DualWord at(size_t i) const;
    size_t size() const;
}; // class DualWordArray
 
class LinearTerm
{
private:
    Variable variable_;
    FElem coeff_;
 
public:
    LinearTerm(const Variable &v) : variable_(v), coeff_(1) {}
    LinearTerm(const Variable &v, const FElem &coeff)
        : variable_(v), coeff_(coeff)
    {
    }
    LinearTerm(const Variable &v, long n) : variable_(v), coeff_(n) {}
    LinearTerm operator-() const { return LinearTerm(variable_, -coeff_); }
    LinearTerm &operator*=(const FElem &other)
    {
        coeff_ *= other;
        return *this;
    }
    FieldType fieldtype() const { return coeff_.fieldType(); }
    ::std::string asString() const;
    FElem eval(const VariableAssignment &assignment) const;
    Variable variable() const { return variable_; }
 
    friend class Monomial;
    friend class GadgetLibAdapter;
}; // class LinearTerm
 
class LinearCombination
{
protected:
    ::std::vector<LinearTerm> linearTerms_;
    FElem constant_;
    typedef ::std::vector<LinearTerm>::size_type size_type;
 
public:
    LinearCombination() : linearTerms_(), constant_(0) {}
    LinearCombination(const Variable &var) : linearTerms_(1, var), constant_(0)
    {
    }
    LinearCombination(const LinearTerm &linTerm)
        : linearTerms_(1, linTerm), constant_(0)
    {
    }
    LinearCombination(long i) : linearTerms_(), constant_(i) {}
    LinearCombination(const FElem &elem) : linearTerms_(), constant_(elem) {}
 
    LinearCombination &operator+=(const LinearCombination &other);
    LinearCombination &operator-=(const LinearCombination &other);
    LinearCombination &operator*=(const FElem &other);
    FElem eval(const VariableAssignment &assignment) const;
    ::std::string asString() const;
    const Variable::set getUsedVariables() const;
 
    friend class Polynomial;
    friend class GadgetLibAdapter;
}; // class LinearCombination
 
inline LinearCombination operator-(const LinearCombination &lc)
{
    return LinearCombination(0) -= lc;
}
 
LinearCombination sum(const VariableArray &inputs);
// TODO : change this to member function
LinearCombination negate(const LinearCombination &lc);
 
class Monomial
{
private:
    FElem coeff_;
    // currently just a vector of variables. This can surely be optimized e.g.
    // hold a variable-degree pair but is not needed for concrete efficiency as
    // we will only be invoking degree 2 constraints in the near future.
    Variable::multiset variables_;
 
public:
    Monomial(const Variable &var) : coeff_(1), variables_()
    {
        variables_.insert(var);
    }
    Monomial(const Variable &var, const FElem &coeff)
        : coeff_(coeff), variables_()
    {
        variables_.insert(var);
    }
    Monomial(const FElem &val) : coeff_(val), variables_() {}
    Monomial(const LinearTerm &linearTerm);
 
    FElem eval(const VariableAssignment &assignment) const;
    const Variable::set getUsedVariables() const;
    const FElem getCoefficient() const;
    ::std::string asString() const;
    Monomial operator-() const;
    Monomial &operator*=(const Monomial &other);
}; // class Monomial
 
class Polynomial
{
private:
    ::std::vector<Monomial> monomials_;
    FElem constant_;
 
public:
    Polynomial() : monomials_(), constant_(0) {}
    Polynomial(const Monomial &monomial) : monomials_(1, monomial), constant_(0)
    {
    }
    Polynomial(const Variable &var) : monomials_(1, Monomial(var)), constant_(0)
    {
    }
    Polynomial(const FElem &val) : monomials_(), constant_(val) {}
    Polynomial(const LinearCombination &linearCombination);
    Polynomial(const LinearTerm &linearTerm)
        : monomials_(1, Monomial(linearTerm)), constant_(0)
    {
    }
    Polynomial(int i) : monomials_(), constant_(i) {}
 
    FElem eval(const VariableAssignment &assignment) const;
    const Variable::set getUsedVariables() const;
    const std::vector<Monomial> &getMonomials() const;
    const FElem getConstant() const;
    ::std::string asString() const;
    Polynomial &operator+=(const Polynomial &other);
    Polynomial &operator*=(const Polynomial &other);
    Polynomial &operator-=(const Polynomial &other);
    Polynomial &operator+=(const LinearTerm &other)
    {
        return *this += Polynomial(Monomial(other));
    }
}; // class Polynomial
 
inline Polynomial operator-(const Polynomial &src)
{
    return Polynomial(FElem(0)) -= src;
}
 
} // namespace gadgetlib2
 
#include <libsnark/gadgetlib2/variable_operators.hpp>
 
#endif // LIBSNARK_GADGETLIB2_INCLUDE_GADGETLIB2_VARIABLE_HPP_