expression.hpp

#ifndef EXPRESSION_H
#define EXPRESSION_H
 
#include <cstdint>
#include <string>
#include <vector>
#include <memory>
#include <ostream>
#include <map>
#include <set>
#include <variant>
#include "exception.hpp"
#include "number.hpp"
#include "types.hpp"
 
namespace maat
{
 
enum class ExprType
{
    VAR, 
    MEM, 
    EXTRACT, 
    CONCAT, 
    UNOP, 
    BINOP, 
    ITE, 
    CST, 
    NONE
};
 
bool operator<(ExprType t1, ExprType t2);
 
enum class ITECond
{
    EQ, 
    LT, 
    LE, 
    SLT, 
    SLE, 
    FEQ, 
    FLT, 
    FLE 
};
 
// TODO, remove THE MULH/SMULH ???
enum class Op
{
    ADD=0, 
    MUL, 
    MULH, 
    SMULL, 
    SMULH, 
    DIV, 
    SDIV, 
    NEG, 
    AND, 
    OR, 
    XOR, 
    SHL, 
    SHR, 
    SAR, 
    MOD, 
    SMOD, 
    NOT, 
    NONE
};
 
std::string op_to_str(Op op);
bool operator<(Op op1, Op op2);
bool op_is_symetric(Op op);
bool op_is_associative(Op op);
bool op_is_left_associative(Op op);
bool op_is_distributive_over(Op op1, Op op2);
bool op_is_multiplication(Op op);
 
enum class ExprStatus: uint8_t
{
    CONCRETE, 
    SYMBOLIC, 
    CONCOLIC, 
    NOT_COMPUTED 
};
 
ExprStatus operator|(ExprStatus s1, ExprStatus s2);
 
enum class Taint: uint8_t
{
    NOT_TAINTED = 0, 
    TAINTED = 1, 
    NOT_COMPUTED = 2 
};
 
static const uint64_t default_expr_taint_mask = 0xffffffffffffffff;
 
class ValueSet
{
    protected:
    static const uint64_t vs_min  = 0; 
    static const uint64_t vs_max = 0xffffffffffffffff; 
 
    public:
    int size;
    ucst_t min;  
    ucst_t max; 
    ucst_t stride; 
 
    ValueSet();
    ValueSet(size_t size);
    ValueSet(size_t size, ucst_t min, ucst_t max, ucst_t stride);
 
    void set(ucst_t min, ucst_t max, ucst_t stride);
    void set_cst(ucst_t val); 
    bool is_cst(); 
    void set_all(); 
    ucst_t range(); 
 
    bool contains(ucst_t val);
 
    void set_not(ValueSet& vs);
    void set_neg(ValueSet& vs);
    void set_add(ValueSet& vs1, ValueSet& vs2);
    void set_or(ValueSet& vs1, ValueSet& vs2);
    void set_and(ValueSet& vs1, ValueSet& vs2);
    void set_xor(ValueSet& vs1, ValueSet& vs2);
    void set_mod(ValueSet& vs1, ValueSet& vs2);
    void set_smod(ValueSet& vs1, ValueSet& vs2);
    void set_shl(ValueSet& vs1, ValueSet& vs2);
    void set_shr(ValueSet& vs1, ValueSet& vs2);
    void set_sar(ValueSet& vs1, ValueSet& vs2);
    void set_mul(ValueSet& vs1, ValueSet& vs2);
    void set_mulh(ValueSet& vs1, ValueSet& vs2);
    void set_div(ValueSet& vs1, ValueSet& vs2);
    void set_concat(ValueSet& high, ValueSet& low);    
    void set_union(ValueSet& vs1, ValueSet& vs2);
 
};
 
 
class ExprObject;
class VarContext;
 
typedef std::shared_ptr<ExprObject> Expr;
 
class ExprObject
{
friend class ExprSimplifier;
 
protected:
    // ValueSet
    ValueSet _value_set;
    bool _value_set_computed;
    // Hash
    bool _hashed;
    hash_t _hash;
    // Simplification
    Expr _simplified_expr; 
    bool _is_simplified; 
    int _simplifier_id; 
    // Taint
    Taint _taint;
    int _taint_ctx_id; 
    ucst_t _taint_mask; 
    // Concretization
    maat::Number _concrete; 
    int _concrete_ctx_id = -1; 
    // State
    ExprStatus _status;
    int _status_ctx_id; 
 
public:
    ExprObject(
        ExprType type, size_t size, 
        bool _is_simp=false, 
        Taint _t = Taint::NOT_COMPUTED, 
        ucst_t _taint_mask=maat::default_expr_taint_mask
    );
    virtual ~ExprObject() = default;
protected:
    virtual const maat::Number& concretize(const VarContext* ctx = nullptr){throw runtime_exception("No implementation");};
 
public:
    const ExprType type; 
    const size_t size; 
    std::vector<Expr> args; 
 
public:
    virtual void get_associative_args(Op op, std::vector<Expr>& vec){};
    virtual void get_left_associative_args(Op op, std::vector<Expr>& vec, Expr& leftmost){};
 
    bool contains_vars(std::set<std::string>& var_names);
    void get_vars(std::set<std::string>& var_names);
 
    virtual hash_t hash(){throw runtime_exception("No implementation");};
 
    bool is_type(ExprType t, Op op=Op::NONE);
 
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask){throw runtime_exception("No implementation");};
    void make_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    ucst_t taint_mask();
 
public:
    ucst_t as_uint();
    ucst_t as_uint(const VarContext& ctx);
    cst_t as_int();
    cst_t as_int(const VarContext& ctx);
    const maat::Number& as_number();
    const maat::Number& as_number(const VarContext& ctx);
    fcst_t as_float();
    fcst_t as_float(const VarContext& ctx);
 
public:
    virtual ValueSet& value_set(){throw runtime_exception("No implementation");};
 
    virtual ExprStatus status(const VarContext& ctx){throw runtime_exception("No implementation");};
    virtual bool is_symbolic(const VarContext& ctx);
    bool is_concrete(const VarContext& ctx);
    virtual bool is_concolic(const VarContext& ctx);
 
    /* Simplification */
    bool already_simplified_by(int simplifier_id);
 
    bool eq(Expr other);
    bool neq(Expr other);
    bool inf(Expr other);
    
    /* Accessors for child classes functions */
    virtual cst_t cst(){throw runtime_exception("No implementation");};
    virtual const std::string& name(){throw runtime_exception("No implementation");};
    virtual Op op(){throw runtime_exception("No implementation");};
    virtual cst_t mode(){throw runtime_exception("No implementation");};
    virtual unsigned int access_count(){throw runtime_exception("No implementation");};
    virtual Expr cond_left(){throw runtime_exception("No implementation");};
    virtual Expr cond_right(){throw runtime_exception("No implementation");};
    virtual Expr if_true(){throw runtime_exception("No implementation");};
    virtual Expr if_false(){throw runtime_exception("No implementation");};
    virtual ITECond cond_op(){throw runtime_exception("No implementation");};
    virtual Expr base_expr(){throw runtime_exception("No implementation");};
    
    // Printing
    virtual void print(std::ostream& out){out << "???";};
};
 
/* Child specialized classes */
class ExprCst: public ExprObject
{
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprCst(size_t size, cst_t cst);
    ExprCst(size_t size, const std::string& value, int base=16);
    ExprCst(const Number& value);
    virtual ~ExprCst() = default;
    cst_t cst();
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprVar: public ExprObject
{
private:
    const std::string _name;
    static const int max_name_length = 1024;
 
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprVar(size_t size, std::string name, Taint tainted=Taint::NOT_TAINTED);
    virtual ~ExprVar() = default;
    const std::string& name();
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprMem: public ExprObject
{
friend class SymbolicMemEngine;
    
private:
    unsigned int _access_count;
    ValueSet _addr_value_set;
    Expr _base_expr;
    // Unfolding cache
    Expr _unfolded;
    bool _unfolded_with_forced_align;
 
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprMem(size_t size, Expr addr, unsigned int access_count=0, Expr base=nullptr);
    ExprMem(size_t size, Expr addr, unsigned int access_count, Expr base, ValueSet& vs);
    virtual ~ExprMem() = default;
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    unsigned int access_count();
    virtual ValueSet& value_set();
    Expr base_expr();
};
 
class ExprUnop: public ExprObject
{
private:
    Op _op;
    
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprUnop(Op op, Expr arg);
    virtual ~ExprUnop() = default;
    Op op(); 
 
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprBinop: public ExprObject
{
private:
    Op _op;
 
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprBinop(Op op, Expr left, Expr right);
    virtual ~ExprBinop() = default;
    Op op(); 
 
    virtual hash_t hash();
    virtual void get_associative_args(Op op, std::vector<Expr>& vec);
    virtual void get_left_associative_args(Op op, std::vector<Expr>& vec, Expr& leftmost);
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprExtract: public ExprObject{
  
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprExtract(Expr arg, Expr higher, Expr lower);
    virtual ~ExprExtract() = default;
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprConcat: public ExprObject{
 
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprConcat(Expr upper, Expr lower);
    virtual ~ExprConcat() = default;
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
class ExprITE: public ExprObject{
private:
    ITECond _cond_op;
 
protected:
    virtual const Number& concretize(const VarContext* ctx=nullptr);
 
public:
    ExprITE(Expr cond1, ITECond cond_op, Expr cond2, Expr if_true, Expr if_false);
    virtual ~ExprITE() = default;
    ITECond cond_op(); 
    Expr cond_left(); 
    Expr cond_right(); 
    Expr if_true(); 
    Expr if_false(); 
 
    virtual hash_t hash();
    virtual void print(std::ostream& out);
    virtual bool is_tainted(ucst_t taint_mask=maat::default_expr_taint_mask);
    virtual ExprStatus status(const VarContext& ctx);
    virtual ValueSet& value_set();
};
 
 
/* Helper functions to create new expressions */
Expr exprcst(size_t size, cst_t cst); 
Expr exprcst(size_t size, std::string&& value, int base=16); 
Expr exprcst(const Number& value); 
Expr exprvar(size_t size, std::string name, Taint tainted = Taint::NOT_TAINTED); 
Expr exprmem(size_t size, Expr addr, unsigned int access_count = 0xffffffff, Expr base=nullptr); 
Expr exprmem(size_t size, Expr addr, unsigned int access_count, Expr base, ValueSet& addr_value_set); 
Expr exprbinop(Op op, Expr left, Expr right);
Expr extract(Expr arg, unsigned long higher, unsigned long lower); 
Expr extract(Expr arg, Expr higher, Expr lower); 
Expr concat(Expr upper, Expr lower); 
Expr ITE(Expr cond_left, ITECond cond_op, Expr cond_right, Expr if_true, Expr if_false); 
 
// Binary operations 
Expr operator+(Expr left, Expr right); 
Expr operator+(Expr left, cst_t right); 
Expr operator+(cst_t left, Expr right); 
 
Expr operator-(Expr left, Expr right); 
Expr operator-(Expr left, cst_t right); 
Expr operator-(cst_t left, Expr right); 
 
Expr operator*(Expr left, Expr right); 
Expr operator*(Expr left, cst_t right); 
Expr operator*(cst_t left, Expr right); 
 
Expr operator/(Expr left, Expr right); 
Expr operator/(Expr left, cst_t right); 
Expr operator/(cst_t left, Expr right); 
 
Expr operator&(Expr left, Expr right); 
Expr operator&(Expr left, cst_t right); 
Expr operator&(cst_t left, Expr right); 
 
Expr operator|(Expr left, Expr right); 
Expr operator|(Expr left, cst_t right); 
Expr operator|(cst_t left, Expr right); 
 
Expr operator^(Expr left, Expr right); 
Expr operator^(Expr left, cst_t right); 
Expr operator^(cst_t left, Expr right); 
 
Expr operator%(Expr val, Expr mod);  
Expr operator%(Expr val, cst_t mod); 
Expr operator%(cst_t val, Expr mod); 
 
Expr operator<<(Expr val, Expr shift); 
Expr operator<<(Expr val, cst_t shift); 
Expr operator<<(cst_t val, Expr shift); 
 
Expr operator>>(Expr val, Expr shift); 
Expr operator>>(Expr val, cst_t shift); 
Expr operator>>(cst_t val, Expr shift); 
 
Expr shl(Expr arg, Expr shift); 
Expr shl(Expr arg, cst_t shift);
Expr shl(cst_t arg, Expr shift);
 
Expr shr(Expr arg, Expr shift);
Expr shr(Expr arg, cst_t shift);
Expr shr(cst_t arg, Expr shift);
 
Expr sar(Expr arg, Expr shift); 
Expr sar(Expr arg, cst_t shift); 
Expr sar(cst_t arg, Expr shift); 
 
Expr sdiv(Expr left, Expr right); 
Expr sdiv(Expr left, cst_t right); 
Expr sdiv(cst_t left, Expr right); 
 
Expr smod(Expr val, Expr mod); 
Expr smod(Expr val, cst_t mod); 
Expr smod(cst_t val, Expr mod); 
 
Expr mulh(Expr left, Expr right); 
Expr mulh(Expr left, cst_t right); 
Expr mulh(cst_t left, Expr right); 
 
Expr smull(Expr left, Expr right); 
Expr smull(Expr left, cst_t right); 
Expr smull(cst_t left, Expr right); 
 
Expr smulh(Expr left, Expr right); 
Expr smulh(Expr left, cst_t right); 
Expr smulh(cst_t left, Expr right); 
 
Expr operator~(Expr arg); 
Expr operator-(Expr arg); 
 
std::ostream& operator<< (std::ostream& os, Expr e); 
 
/* Canonizing expressions */
Expr expr_canonize(Expr e);
cst_t cst_sign_trunc(size_t size, cst_t val);
cst_t cst_mask(size_t size);
cst_t cst_sign_extend(size_t size, cst_t val);
ucst_t cst_unsign_trunc(size_t size, cst_t val);
ucst_t cst_gcd( ucst_t c1, ucst_t c2);
ucst_t cst_lcm( ucst_t c1, ucst_t c2);
ucst_t cst_extract(ucst_t c, int high, int low);
ucst_t cst_concat(ucst_t c_1, int size_c1, ucst_t c2, int size_c2);
cst_t fcst_to_cst(size_t size, fcst_t f);
 
class VarContext
{
private:
    static unsigned int _id_cnt;
 
private:
    std::map<std::string, maat::Number> varmap;
    
public:
    VarContext(unsigned int id=0); 
    VarContext(const VarContext&) = default;
    VarContext& operator=(const VarContext&) = default;
    ~VarContext() = default;
 
public:
    unsigned int id; 
    void set(const std::string& var, cst_t value); 
    void set(const std::string& var, const Number& number); 
    cst_t get(const std::string& var) const; 
    const maat::Number& get_as_number(const std::string& var) const;
    std::vector<uint8_t> get_as_buffer(std::string var, unsigned int elem_size=1) const;
    std::string get_as_string(std::string var) const;
    void remove(const std::string& var); 
    bool contains(const std::string& var) const; 
    std::string new_name_from(const std::string& hint) const;
    std::vector<Expr> new_symbolic_buffer(
        const std::string& name,
        int nb_elems,
        int elem_size=1,
        bool null_terminated=false
    );
    std::vector<Expr> new_concolic_buffer(
        const std::string& name,
        const std::vector<cst_t>& concrete_buffer,
        int nb_elems,
        int elem_size=1,
        bool null_terminated=false
    );
    void update_from(VarContext& other);
    void print(std::ostream& os) const; 
};
 
std::ostream& operator<<(std::ostream& os, const VarContext& c);
 
// Utils functions
std::string ite_cond_to_string(ITECond c);
bool ite_evaluate(Expr left, ITECond cond, Expr right, const VarContext* ctx = nullptr);
 
inline Expr __attribute__((always_inline)) overwrite_expr_bits(Expr old_expr, Expr new_expr, size_t higher_bit) 
{
    if (new_expr->size >= old_expr->size)
        return new_expr;
    else if(higher_bit == new_expr->size-1)
    {
        return concat(extract(old_expr, old_expr->size-1, higher_bit+1), new_expr);
    }
    else if(higher_bit == old_expr->size-1)
    {
        return concat(new_expr, extract(old_expr, higher_bit-new_expr->size, 0));
    }
    else
    {
        return concat(extract(old_expr, old_expr->size-1, higher_bit+1),
                      concat(new_expr, extract(old_expr, higher_bit-new_expr->size, 0))); 
    }
}
 
} // namespace maat
 
#endif