IntervalSemantics.h

#ifndef ROSE_BinaryAnalysis_InstructionSemantics_IntervalSemantics_H
#define ROSE_BinaryAnalysis_InstructionSemantics_IntervalSemantics_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include <stdint.h>

#ifndef __STDC_FORMAT_MACROS
#define __STDC_FORMAT_MACROS
#endif
#include <inttypes.h>

#include <Rose/BinaryAnalysis/BasicTypes.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics.h>
#include "integerOps.h"

namespace Rose {
namespace BinaryAnalysis {              // documented elsewhere
namespace InstructionSemantics {       // documented elsewhere


namespace IntervalSemantics {

/* Single contiguous interval. */
typedef Sawyer::Container::Interval<uint64_t> Interval;

typedef Sawyer::Container::IntervalSet<Interval> Intervals;

//                                      Semantic values

typedef Sawyer::SharedPointer<class SValue> SValuePtr;

class SValue: public BaseSemantics::SValue {
public:
    using Super = BaseSemantics::SValue;

    using Ptr = SValuePtr;

protected:
    Intervals intervals_;
    bool isBottom_;

protected:
    // Protected constructors. See base class and public members for documentation
    explicit SValue(size_t nbits):
        BaseSemantics::SValue(nbits), isBottom_(false){
        intervals_.insert(Interval::hull(0, IntegerOps::genMask<uint64_t>(nbits)));
    }
    SValue(size_t nbits, uint64_t number)
        : BaseSemantics::SValue(nbits), isBottom_(false) {
        number &= IntegerOps::genMask<uint64_t>(nbits);
        intervals_.insert(number);
    }
    SValue(size_t nbits, uint64_t v1, uint64_t v2):
        BaseSemantics::SValue(nbits), isBottom_(false) {
        v1 &= IntegerOps::genMask<uint64_t>(nbits);
        v2 &= IntegerOps::genMask<uint64_t>(nbits);
        ASSERT_require(v1<=v2);
        intervals_.insert(Interval::hull(v1, v2));
    }
    SValue(size_t nbits, const Intervals &intervals):
        BaseSemantics::SValue(nbits), isBottom_(false) {
        ASSERT_require(!intervals.isEmpty());
        ASSERT_require((intervals.greatest() <= IntegerOps::genMask<uint64_t>(nbits)));
        intervals_ = intervals;
    }

    // Static allocating constructors
public:
    static SValuePtr instance() {
        return SValuePtr(new SValue(1));
    }

    static SValuePtr instance_bottom(size_t nbits) {
        SValue *self = new SValue(nbits);
        self->isBottom_ = true;
        return SValuePtr(self);
    }

    static SValuePtr instance_undefined(size_t nbits) {
        return SValuePtr(new SValue(nbits));
    }

    static SValuePtr instance_unspecified(size_t nbits) {
        return SValuePtr(new SValue(nbits));
    }

    static SValuePtr instance_integer(size_t nbits, uint64_t number) {
        return SValuePtr(new SValue(nbits, number));
    }

    static SValuePtr instance_intervals(size_t nbits, const Intervals &intervals) {
        return SValuePtr(new SValue(nbits, intervals));
    }

    static SValuePtr instance_hull(size_t nbits, uint64_t v1, uint64_t v2) {
        return SValuePtr(new SValue(nbits, v1, v2));
    }

    static SValuePtr instance_copy(const SValuePtr &other) {
        return SValuePtr(new SValue(*other));
    }
    
    static SValuePtr instance_from_bits(size_t nbits, uint64_t possible_bits);

    static SValuePtr promote(const BaseSemantics::SValuePtr &v) { // hot
        SValuePtr retval = v.dynamicCast<SValue>();
        ASSERT_not_null(retval);
        return retval;
    }
    
    // Virtual allocating constructors inherited from the super class
public:
    virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override {
        return instance_bottom(nbits);
    }
    virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override {
        return instance_undefined(nbits);
    }
    virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override {
        return instance_unspecified(nbits);
    }

    virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t number) const override {
        return instance_integer(nbits, number);
    }
    virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override {
        SValuePtr retval(new SValue(*this));
        if (new_width!=0 && new_width!=retval->nBits())
            retval->set_width(new_width);
        return retval;
    }

    virtual Sawyer::Optional<BaseSemantics::SValuePtr>
    createOptionalMerge(const BaseSemantics::SValuePtr &other, const BaseSemantics::MergerPtr&,
                        const SmtSolverPtr&) const override;

    // Virtual allocating constructors first defined at this level of the class hierarchy
public:
    virtual SValuePtr create(size_t nbits, uint64_t v1, uint64_t v2) {
        return instance_hull(nbits, v1, v2);
    }

    virtual SValuePtr create(size_t nbits, const Intervals &intervals) {
        return instance_intervals(nbits, intervals); 
    }

    virtual SValuePtr create_from_bits(size_t nbits, uint64_t possible_bits) {
        return instance_from_bits(nbits, possible_bits);
    }
            

    // Override virtual methods...
public:
    virtual void hash(Combinatorics::Hasher&) const override;

    virtual bool isBottom() const override {
        return isBottom_;
    }

    virtual void print(std::ostream &output, BaseSemantics::Formatter&) const override;

    // Override legacy methods. Override these, but always call the camelCase versions from BaseSemantics::SValue. These
    // snake_case names may eventually go away, so be sure to make good use of "override" in your own code.
public:
    // See mayEqual
    virtual bool may_equal(const BaseSemantics::SValuePtr &other,
                           const SmtSolverPtr &solver = SmtSolverPtr()) const override;

    // See mustEqual
    virtual bool must_equal(const BaseSemantics::SValuePtr &other,
                            const SmtSolverPtr &solver = SmtSolverPtr()) const override;

    // See isConcrete
    virtual bool is_number() const override {
        return 1==intervals_.size();
    }

    // See toUnsigned and toSigned
    virtual uint64_t get_number() const override {
        ASSERT_require(1==intervals_.size());
        return intervals_.least();
    }

    // Additional methods introduced at this level of the class hierarchy
public:
    const Intervals& get_intervals() const {
        return intervals_;
    }

    void set_intervals(const Intervals &intervals) {
        intervals_ = intervals;
    }

    uint64_t possible_bits() const;

};


//                                      Register state

typedef BaseSemantics::RegisterStateGeneric RegisterState;
typedef BaseSemantics::RegisterStateGenericPtr RegisterStateGenericPtr;


//                                      Memory state

typedef boost::shared_ptr<class MemoryState> MemoryStatePtr;

class MemoryState: public BaseSemantics::MemoryCellList {
public:
    using Super = BaseSemantics::MemoryCellList;

    using Ptr = MemoryStatePtr;

    // Real constructors
protected:
    MemoryState(const BaseSemantics::MemoryCellPtr &protocell)
        : BaseSemantics::MemoryCellList(protocell) {}

    MemoryState(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval)
        : BaseSemantics::MemoryCellList(addrProtoval, valProtoval) {}

    MemoryState(const MemoryState &other)
        : BaseSemantics::MemoryCellList(other) {}

    // Static allocating constructors
public:
    static MemoryStatePtr instance(const BaseSemantics::MemoryCellPtr &protocell) {
        return MemoryStatePtr(new MemoryState(protocell));
    }

    static  MemoryStatePtr instance(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval) {
        return MemoryStatePtr(new MemoryState(addrProtoval, valProtoval));
    }
    
    // Virtual constructors
public:
    virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::MemoryCellPtr &protocell) const override {
        return instance(protocell);
    }

    virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::SValuePtr &addrProtoval,
                                                 const BaseSemantics::SValuePtr &valProtoval) const override {
        return instance(addrProtoval, valProtoval);
    }

    virtual BaseSemantics::MemoryStatePtr clone() const override {
        return MemoryStatePtr(new MemoryState(*this));
    }
    
    // Methods we inherited
public:
    virtual BaseSemantics::SValuePtr
    readMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt,
               BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override;

    virtual BaseSemantics::SValuePtr
    peekMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt,
               BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override;

    virtual void writeMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &value,
                             BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override;
};


//                                      Complete state

typedef BaseSemantics::State State;
typedef BaseSemantics::StatePtr StatePtr;


//                                      RISC operators

typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;

class RiscOperators: public BaseSemantics::RiscOperators {
public:
    using Super = BaseSemantics::RiscOperators;

    using Ptr = RiscOperatorsPtr;

    // Real constructors
protected:
    explicit RiscOperators(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr&);

    explicit RiscOperators(const BaseSemantics::StatePtr&, const SmtSolverPtr&);

    // Static allocating constructors
public:
    static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr&, const SmtSolverPtr &solver = SmtSolverPtr());

    static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval,
                                                 const SmtSolverPtr &solver = SmtSolverPtr());

    static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr&, const SmtSolverPtr &solver = SmtSolverPtr());

    // Virtual constructors
public:
    virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval,
                                                   const SmtSolverPtr &solver = SmtSolverPtr()) const override;

    virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::StatePtr&,
                                                   const SmtSolverPtr &solver = SmtSolverPtr()) const override;

    // Dynamic pointer casts
public:
    static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr&);

    // Methods first introduced at this level of the class hierarchy.
public:

    virtual SValuePtr svalue_from_bits(size_t nbits, uint64_t possible_bits) {
        return SValue::promote(protoval())->create_from_bits(nbits, possible_bits);
    }

    virtual SValuePtr svalue_from_intervals(size_t nbits, const Intervals &intervals) {
        return SValue::promote(protoval())->create(nbits, intervals);
    }

    // Override methods from base class.  These are the RISC operators that are invoked by a Dispatcher.
public:
    virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_,
                                          const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr or_(const BaseSemantics::SValuePtr &a_,
                                         const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_,
                                          const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override;
    virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_,
                                             size_t begin_bit, size_t end_bit) override;
    virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_,
                                            const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) override;
    virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) override;
    virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_,
                                                const BaseSemantics::SValuePtr &sa_) override;
    virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_,
                                                 const BaseSemantics::SValuePtr &sa_) override;
    virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_,
                                               const BaseSemantics::SValuePtr &sa_) override;
    virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_,
                                                const BaseSemantics::SValuePtr &sa_) override;
    virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_,
                                                          const BaseSemantics::SValuePtr &sa_) override;
    virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) override;
    virtual BaseSemantics::SValuePtr iteWithStatus(const BaseSemantics::SValuePtr &sel_,
                                                   const BaseSemantics::SValuePtr &a_,
                                                   const BaseSemantics::SValuePtr &b_,
                                                   IteStatus&) override;
    virtual BaseSemantics::SValuePtr unsignedExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
    virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
    virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_,
                                         const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr addWithCarries(const BaseSemantics::SValuePtr &a_,
                                                    const BaseSemantics::SValuePtr &b_,
                                                    const BaseSemantics::SValuePtr &c_,
                                                    BaseSemantics::SValuePtr &carry_out/*out*/) override;
    virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override;
    virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_,
                                                  const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_,
                                                  const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_,
                                                    const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_,
                                                    const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr unsignedModulo(const BaseSemantics::SValuePtr &a_,
                                                    const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_,
                                                      const BaseSemantics::SValuePtr &b_) override;
    virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg,
                                                const BaseSemantics::SValuePtr &addr,
                                                const BaseSemantics::SValuePtr &dflt,
                                                const BaseSemantics::SValuePtr &cond) override;
    virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg,
                                                const BaseSemantics::SValuePtr &addr,
                                                const BaseSemantics::SValuePtr &dflt) override;
    virtual void writeMemory(RegisterDescriptor segreg,
                             const BaseSemantics::SValuePtr &addr,
                             const BaseSemantics::SValuePtr &data,
                             const BaseSemantics::SValuePtr &cond) override;
};

} // namespace
} // namespace
} // namespace
} // namespace

#endif
#endif