BitPattern.h

#ifndef ROSE_BitPattern_H
#define ROSE_BitPattern_H
 
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
 
#include "integerOps.h"
#include <Rose/StringUtility.h>
 
#include <iostream>
#include <vector>
 
namespace Rose {
 
template<typename T>
class BitPattern {
    typedef std::vector<T> Words;
    typedef std::vector<Words> Alternatives;
    Words mask_;                                // significant bits
    Alternatives patterns_;                     // set of alternative patterns; each pattern has the same size as the mask
 
public:
    BitPattern() {}
 
    BitPattern(T msk, T pat, size_t wordnum) {
        insert(msk, pat, wordnum);
    }
 
    BitPattern(size_t lo_bit, size_t hi_bit, T pat, size_t wordnum) {
        bits(lo_bit, hi_bit, pat, wordnum);
    }
 
    bool is_consistent() const {
        for (size_t i=0; i<patterns_.size(); ++i) {
            if (patterns_[i].size()!=mask_.size()) {
                std::cerr <<"BitPattern::is_consistent failed\n"
                          <<"    mask_.size() = " <<mask_.size() <<"\n"
                          <<"    patterns_[" <<i <<"].size() = " <<patterns_[i].size() <<"\n"
                          <<"    these two vectors should have been the same size\n";
                std::cerr <<"    this = ";
                print(std::cerr);                       // printing might fail
                std::cerr <<"\n";
                return false;
            }
        }
        return true;
    }
 
    size_t nsignificant() const {
        size_t retval = 0;
        for (size_t i=0; i<mask_.size(); ++i)
            retval += IntegerOps::countSet(mask_[i]);
        return retval;
    }
 
    size_t nwords() const {
        return mask_.size();
    }
 
    size_t width() const {
        if (0==mask_.size())
            return 0;
        assert(mask_.back()!=0);
        return 8*sizeof(T)*(mask_.size()-1) + IntegerOps::msb_set(mask_.back()).get() + 1;
    }
 
    T mask(size_t wordnum) {
        if (wordnum >= mask_.size())
            return 0;
        return mask_[wordnum];
    }
 
    std::pair<T, T> invariants(T msk, size_t wordnum) {
        if (msk==0 || wordnum>mask_.size() || patterns_.empty())
            return std::pair<T, T>(0, 0);
        T retmsk = msk & mask_[wordnum];
        T retpat = retmsk & patterns_[0][wordnum];
        for (size_t i=1; i<patterns_.size() && retmsk!=0; ++i)
            retmsk &= ~(retpat ^ patterns_[i][wordnum]); // retmsk reduced to set of bits that are the same
        return std::pair<T, T>(retpat & retmsk, retmsk);
    }
    
    size_t nalternatives() const {
        return patterns_.size();
    }
 
    T conflict(T msk, T pat, size_t wordnum, size_t altnum) const {
        if (wordnum < mask_.size()) {
            if (T overlap = mask_[wordnum] & msk) {
                assert(altnum < patterns_.size());
                if (T differ = (patterns_[altnum][wordnum] & overlap) ^ (pat & overlap))
                    return differ;
            }
        }
        return 0;
    }
    
    T conflict(T msk, T pat, size_t wordnum) const {
        if (wordnum < mask_.size()) {
            for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
                if (T differ = conflict(msk, pat, wordnum, altnum))
                    return differ;
            }
        }
        return 0;
    }
 
    void check_insertion(T msk, T pat, size_t wordnum) const {
        if (0!=msk && wordnum<mask_.size()) {
            if (T differ = conflict(msk, pat, wordnum)) {
                std::cerr <<"BitPattern::insert(msk=" <<Rose::StringUtility::addrToString(msk, 8*sizeof(T))
                          <<", pat=" <<Rose::StringUtility::addrToString(pat, 8*sizeof(T))
                          <<", wordnum=" <<wordnum <<") conflicts with existing pattern ";
                print(std::cerr);
                std::cerr <<" at bits " <<Rose::StringUtility::addrToString(differ, 8*sizeof(T)) <<"\n";
                assert(!"new bit pattern conflicts with existing pattern");
                abort();
            }
        }
    }
 
    bool any_same(const BitPattern &other, std::pair<size_t, size_t> *alternatives=NULL) const {
        if (nwords()!=other.nwords())
            return false;
        for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
            if (mask_[wordnum]!=other.mask_[wordnum])
                return false;
        }
        for (size_t a1=0; a1<nalternatives(); ++a1) {
            for (size_t a2=0; a2<other.nalternatives(); ++a2) {
                bool are_same = true;
                for (size_t wordnum=0; are_same && wordnum<nwords(); ++wordnum)
                    are_same = patterns_[a1][wordnum] == other.patterns_[a2][wordnum];
                if (are_same) {
                    if (alternatives!=NULL)
                        *alternatives = std::make_pair(a1, a2);
                    return true;
                }
            }
        }
        return false;
    }
    
    BitPattern& insert(T msk, T pat, size_t wordnum=0) {
        assert(is_consistent());
        assert(0 == (pat & ~msk));
        check_insertion(msk, pat, wordnum);
        if (msk != 0) {
            if (wordnum >= mask_.size())
                mask_.resize(wordnum+1, T(0));
            mask_[wordnum] |= msk;
            if (patterns_.empty()) {
                patterns_.resize(1);
                patterns_[0].resize(wordnum+1, T(0));
                patterns_[0][wordnum] = pat;
            } else {
                for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
                    if (wordnum >= patterns_[altnum].size())
                        patterns_[altnum].resize(wordnum+1, T(0));
                    patterns_[altnum][wordnum] |= pat;
                }
            }
        }
        assert(is_consistent());
        return *this;
    }
 
    BitPattern& bits(size_t lo_bit, size_t hi_bit, T value, size_t wordnum) {
        T msk = IntegerOps::genMask<T>(lo_bit, hi_bit);
        value = IntegerOps::shiftLeft2(value, lo_bit);
        return insert(msk, value, wordnum);
    }
 
    BitPattern shift_left(size_t nbits) const {
        assert(is_consistent());
        if (0==nbits || patterns_.empty())
            return *this;
        static const size_t word_size = 8*sizeof(T);
        size_t need_nbits = width() + nbits;
        size_t need_nwords = (need_nbits + word_size - 1) / word_size;
        size_t word_delta = nbits / word_size;
        size_t bit_delta_lt = nbits % word_size;
        size_t bit_delta_rt = word_size - bit_delta_lt;
        BitPattern retval;
 
        // shift the mask
        retval.mask_.resize(need_nwords, 0);
        for (size_t i=0; i<mask_.size(); ++i) {
            retval.mask_[i+word_delta] |= IntegerOps::shiftLeft2(mask_[i], bit_delta_lt);
            if (i+word_delta+1<need_nwords)
                retval.mask_[i+word_delta+1] = IntegerOps::shiftRightLogical2(mask_[i], bit_delta_rt);
        }
 
        // shift each pattern
        retval.patterns_.resize(patterns_.size());
        for (size_t i=0; i<patterns_.size(); ++i) {
            retval.patterns_[i].resize(need_nwords, 0);
            for (size_t j=0; j<patterns_[i].size(); ++j) {
                retval.patterns_[i][j+word_delta] |= IntegerOps::shiftLeft2(patterns_[i][j], bit_delta_lt);
                if (j+word_delta+1<need_nwords)
                    retval.patterns_[i][j+word_delta+1] = IntegerOps::shiftRightLogical2(patterns_[i][j], bit_delta_rt);
            }
        }
        assert(is_consistent());
        return retval;
    }
    
    BitPattern& conjunction(const BitPattern &other) {
        assert(is_consistent());
        assert(other.is_consistent());
        // check that the operation is possible
        for (size_t altnum=0; altnum<other.nalternatives(); ++altnum) {
            for (size_t wordnum=0; wordnum<other.nwords(); ++wordnum)
                check_insertion(other.mask_[wordnum], other.patterns_[altnum][wordnum], wordnum);
        }
 
        // merge masks
        size_t this_nwords = mask_.size();
        size_t result_nwords = std::max(this_nwords, other.mask_.size());
        mask_.resize(result_nwords, T(0));
        for (size_t wordnum=0; wordnum<other.mask_.size(); ++wordnum)
            mask_[wordnum] |= other.mask_[wordnum];
 
        // do the conjunction
        Alternatives retval;
        for (size_t a1=0; a1<patterns_.size(); ++a1) {
            for (size_t a2=0; a2<other.patterns_.size(); ++a2) {
                retval.push_back(Words(result_nwords, T(0)));
                for (size_t i=0; i<this_nwords; ++i)
                    retval.back()[i] = patterns_[a1][i];
                for (size_t i=0; i<other.nwords(); ++i)
                    retval.back()[i] |= other.patterns_[a2][i];
 
                // check for and remove duplicate pattern
                for (size_t a3=0; a3+1<retval.size(); ++a3) {
                    bool isdup = true;
                    for (size_t i=0; isdup && i<result_nwords; ++i)
                        isdup = retval[a3][i] == retval.back()[i];
                    if (isdup) {
                        retval.pop_back();
                        break;
                    }
                }
            }
        }
        patterns_ = retval;
        assert(is_consistent());
        return *this;
    }
 
    BitPattern& disjunction(const BitPattern &other) {
        assert(is_consistent());
        assert(other.is_consistent());
        if (0==nalternatives()) {
            *this = other;
        } else if (0==other.nalternatives()) {
            // void
        } else {
            assert(nwords()==other.nwords());
            for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
                assert(mask_[wordnum]==other.mask_[wordnum]);
            size_t na = nalternatives();
            for (size_t a1=0; a1<other.nalternatives(); ++a1) {
                bool isdup = false;
                for (size_t a2=0; !isdup && a2<na; ++a2) {
                    isdup = true;
                    for (size_t wordnum=0; isdup && wordnum<nwords(); ++wordnum)
                        isdup = patterns_[a2][wordnum] == other.patterns_[a1][wordnum];
                }
                if (!isdup)
                    patterns_.push_back(other.patterns_[a1]);
            }
        }
        assert(is_consistent());
        return *this;
    }
 
    BitPattern operator&(const BitPattern &other) const {
        BitPattern retval = *this;
        return retval.conjunction(other);
    }
    BitPattern& operator&=(const BitPattern &other) {
        return conjunction(other);
    }
    BitPattern operator|(const BitPattern &other) const {
        BitPattern retval = *this;
        return retval.disjunction(other);
    }
    BitPattern& operator|=(const BitPattern &other) {
        return disjunction(other);
    }
    bool matches(const std::vector<T> value_words) const {
        if (0==nalternatives())
            return true;
        if (value_words.size() < nwords())
            return false;
        for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
            bool eq = true;
            for (size_t wordnum=0; eq && wordnum<nwords(); ++wordnum)
                eq = (value_words[wordnum] & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]);
            if (eq)
                return true;
        }
        return false;
    }
    bool matches(const T *value_words, size_t sz) const {
        std::vector<T> vv;
        for (size_t i=0; i<sz; ++i)
            vv.push_back(value_words[i]);
        return matches(vv);
    }
    bool matches_word(T value, size_t wordnum) const {
        if (0==nalternatives() || wordnum>=nwords())
            return true;
        for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
            if ((value & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]))
                return true;
        }
        return false;
    }
 
    void print(std::ostream &o, size_t altnum, bool with_mask=true) const {
        assert(altnum<nalternatives());
        o <<(1==nwords()?"":"{");
        for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
            o <<(0==wordnum?"":",") <<Rose::StringUtility::addrToString(patterns_[altnum][wordnum], 8*sizeof(T));
            if (with_mask)
                o <<"/" <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
        }
        o <<(1==nwords()?"":"}");
    }
 
    void print(std::ostream &o) const {
        if (0==nwords()) {
            o <<"empty";
        } else {
            o <<(1==nalternatives()?"":"(");
            for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
                o <<(0==altnum?"":" | ");
                print(o, altnum, false);
            }
            o <<(1==nalternatives()?"":")");
            o <<"/" <<(1==nwords()?"":"{");
            for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
                o <<(wordnum>0?",":"") <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
            o <<(1==nwords()?"":"}");
        }
    }
};
 
} // namespace
 
template<typename T>
std::ostream& operator<<(std::ostream &o, const Rose::BitPattern<T> &bp) 
{
    bp.print(o);
    return o;
}
 
#endif
#endif