BinaryString.h

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

#include <Diagnostics.h>
#include <MemoryMap.h>
#include <RoseException.h>
#include <Sawyer/CommandLine.h>
#include <Sawyer/Optional.h>

namespace Rose {
namespace BinaryAnalysis {

namespace Strings {

extern Sawyer::Message::Facility mlog;

typedef uint8_t Octet;                                  
typedef std::vector<Octet> Octets;                      
typedef unsigned CodeValue;                             
typedef std::vector<CodeValue> CodeValues;              
typedef unsigned CodePoint;                             
typedef std::vector<CodePoint> CodePoints;              
class Exception: public Rose::Exception {
public:
    Exception(const std::string &s): Rose::Exception(s) {}
};

enum State {
    FINAL_STATE      = -1,                              
    COMPLETED_STATE  = -2,                              
    INITIAL_STATE    = -3,                              
    ERROR_STATE      = -4,                              
    USER_DEFINED_0   = 0,                               
    USER_DEFINED_1   = 1,                               
    USER_DEFINED_2   = 2,                               
    USER_DEFINED_MAX = 128                              
};

bool isDone(State st);

void initDiagnostics();

class ROSE_DLL_API CharacterEncodingForm: public Sawyer::SharedObject {
protected:
    State state_;
public:
    CharacterEncodingForm(): state_(INITIAL_STATE) {}
    virtual ~CharacterEncodingForm() {}

    typedef Sawyer::SharedPointer<CharacterEncodingForm> Ptr;

    virtual Ptr clone() const = 0;

    virtual std::string name() const = 0;

    virtual CodeValues encode(CodePoint) = 0;

    State state() const { return state_; }

    virtual State decode(CodeValue) = 0;

    virtual CodePoint consume() = 0;

    virtual void reset() = 0;
};

class ROSE_DLL_API NoopCharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
protected:
    NoopCharacterEncodingForm(): cp_(0) {}
public:
    typedef Sawyer::SharedPointer<NoopCharacterEncodingForm> Ptr;

    static Ptr instance() { return Ptr(new NoopCharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const ROSE_OVERRIDE { return Ptr(new NoopCharacterEncodingForm(*this)); }
    virtual std::string name() const ROSE_OVERRIDE { return "no-op"; }
    virtual CodeValues encode(CodePoint cp) ROSE_OVERRIDE;
    virtual State decode(CodeValue) ROSE_OVERRIDE;
    virtual CodePoint consume() ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;
};

NoopCharacterEncodingForm::Ptr noopCharacterEncodingForm();

class ROSE_DLL_API Utf8CharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
protected:
    Utf8CharacterEncodingForm(): cp_(0) {}
public:
    typedef Sawyer::SharedPointer<Utf8CharacterEncodingForm> Ptr;

    static Ptr instance() { return Ptr(new Utf8CharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const ROSE_OVERRIDE { return Ptr(new Utf8CharacterEncodingForm(*this)); }
    virtual std::string name() const ROSE_OVERRIDE { return "UTF-8"; }
    virtual CodeValues encode(CodePoint cp) ROSE_OVERRIDE;
    virtual State decode(CodeValue) ROSE_OVERRIDE;
    virtual CodePoint consume() ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;
};

Utf8CharacterEncodingForm::Ptr utf8CharacterEncodingForm();

class ROSE_DLL_API Utf16CharacterEncodingForm: public CharacterEncodingForm {
    CodePoint cp_;
protected:
    Utf16CharacterEncodingForm(): cp_(0) {}
public:
    typedef Sawyer::SharedPointer<Utf16CharacterEncodingForm> Ptr;

    static Ptr instance() { return Ptr(new Utf16CharacterEncodingForm); }
    virtual CharacterEncodingForm::Ptr clone() const ROSE_OVERRIDE { return Ptr(new Utf16CharacterEncodingForm(*this)); }
    virtual std::string name() const ROSE_OVERRIDE { return "UTF-16"; }
    virtual CodeValues encode(CodePoint cp) ROSE_OVERRIDE;
    virtual State decode(CodeValue) ROSE_OVERRIDE;
    virtual CodePoint consume() ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;
};

Utf16CharacterEncodingForm::Ptr utf16CharacterEncodingForm();

class ROSE_DLL_API CharacterEncodingScheme: public Sawyer::SharedObject {
protected:
    State state_;
public:
    CharacterEncodingScheme(): state_(INITIAL_STATE) {}
    virtual ~CharacterEncodingScheme() {}

    typedef Sawyer::SharedPointer<CharacterEncodingScheme> Ptr;

    virtual Ptr clone() const = 0;

    virtual std::string name() const = 0;

    virtual Octets encode(CodeValue) = 0;

    State state() const { return state_; }

    virtual State decode(Octet) = 0;

    virtual CodeValue consume() = 0;

    virtual void reset() = 0;
};

class ROSE_DLL_API BasicCharacterEncodingScheme: public CharacterEncodingScheme {
    size_t octetsPerValue_;
    ByteOrder::Endianness sex_;
    CodeValue cv_;
protected:
    BasicCharacterEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex)
        : octetsPerValue_(octetsPerValue), sex_(sex), cv_(0) {
        ASSERT_require(1==octetsPerValue || sex!=ByteOrder::ORDER_UNSPECIFIED);
        ASSERT_require(octetsPerValue <= sizeof(CodeValue));
    }
public:
    static Ptr instance(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED) {
        return Ptr(new BasicCharacterEncodingScheme(octetsPerValue, sex));
    }
    virtual Ptr clone() const ROSE_OVERRIDE {
        return Ptr(new BasicCharacterEncodingScheme(*this));
    }
    virtual std::string name() const ROSE_OVERRIDE;
    virtual Octets encode(CodeValue) ROSE_OVERRIDE;
    virtual State decode(Octet) ROSE_OVERRIDE;
    virtual CodeValue consume() ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;
};

BasicCharacterEncodingScheme::Ptr basicCharacterEncodingScheme(size_t octetsPerValue,
                                                               ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);

class ROSE_DLL_API LengthEncodingScheme: public Sawyer::SharedObject {
protected:
    State state_;
public:
    LengthEncodingScheme(): state_(INITIAL_STATE) {}
    virtual ~LengthEncodingScheme() {}

    typedef Sawyer::SharedPointer<LengthEncodingScheme> Ptr;

    virtual Ptr clone() const = 0;

    virtual std::string name() const = 0;

    virtual Octets encode(size_t) = 0;

    State state() const { return state_; }

    virtual State decode(Octet) = 0;

    virtual size_t consume() = 0;

    virtual void reset() = 0;
};

class ROSE_DLL_API BasicLengthEncodingScheme: public LengthEncodingScheme {
    size_t octetsPerValue_;
    ByteOrder::Endianness sex_;
    size_t length_;
protected:
    BasicLengthEncodingScheme(size_t octetsPerValue, ByteOrder::Endianness sex)
        : octetsPerValue_(octetsPerValue), sex_(sex), length_(0) {
        ASSERT_require(1==octetsPerValue || sex!=ByteOrder::ORDER_UNSPECIFIED);
        ASSERT_require(octetsPerValue <= sizeof(size_t));
    }
public:
    static Ptr instance(size_t octetsPerValue, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED) {
        return Ptr(new BasicLengthEncodingScheme(octetsPerValue, sex));
    }
    virtual Ptr clone() const ROSE_OVERRIDE {
        return Ptr(new BasicLengthEncodingScheme(*this));
    }
    virtual std::string name() const ROSE_OVERRIDE;
    virtual Octets encode(size_t) ROSE_OVERRIDE;
    virtual State decode(Octet) ROSE_OVERRIDE;
    virtual size_t consume() ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;
};

BasicLengthEncodingScheme::Ptr basicLengthEncodingScheme(size_t octetsPerValue,
                                                         ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);

class ROSE_DLL_API CodePointPredicate: public Sawyer::SharedObject {
public:
    virtual ~CodePointPredicate() {}

    typedef Sawyer::SharedPointer<CodePointPredicate> Ptr;

    virtual std::string name() const = 0;

    virtual bool isValid(CodePoint) = 0;
};

class ROSE_DLL_API PrintableAscii: public CodePointPredicate {
protected:
    PrintableAscii() {}
public:
    static Ptr instance() {
        return Ptr(new PrintableAscii);
    }
    virtual std::string name() const ROSE_OVERRIDE { return "printable ASCII"; }
    virtual bool isValid(CodePoint) ROSE_OVERRIDE;
};

PrintableAscii::Ptr printableAscii();

class ROSE_DLL_API AnyCodePoint: public CodePointPredicate {
protected:
    AnyCodePoint() {}
public:
    static Ptr instance() { return Ptr(new AnyCodePoint); }
    virtual std::string name() const ROSE_OVERRIDE { return "any code point"; }
    virtual bool isValid(CodePoint) ROSE_OVERRIDE { return true; }
};

AnyCodePoint::Ptr anyCodePoint();

class ROSE_DLL_API StringEncodingScheme: public Sawyer::SharedObject {
protected:
    State state_;                                       // decoding state
    CodePoints codePoints_;                             // unconsumed code points
    size_t nCodePoints_;                                // number of code points decoded since reset
    CharacterEncodingForm::Ptr cef_;
    CharacterEncodingScheme::Ptr ces_;
    CodePointPredicate::Ptr cpp_;

protected:
    StringEncodingScheme(): state_(INITIAL_STATE), nCodePoints_(0) {}

    StringEncodingScheme(const CharacterEncodingForm::Ptr &cef, const CharacterEncodingScheme::Ptr &ces,
                         const CodePointPredicate::Ptr &cpp)
        : cef_(cef), ces_(ces), cpp_(cpp) {}

public:
    virtual ~StringEncodingScheme() {}

    typedef Sawyer::SharedPointer<StringEncodingScheme> Ptr;

    virtual std::string name() const = 0;

    virtual Ptr clone() const = 0;

    virtual Octets encode(const CodePoints&) = 0;

    State state() const { return state_; }

    virtual State decode(Octet) = 0;

    CodePoints consume();

    const CodePoints& codePoints() const { return codePoints_; }

    size_t length() const { return nCodePoints_; }

    virtual void reset();

    CharacterEncodingForm::Ptr characterEncodingForm() const { return cef_; }
    void characterEncodingForm(const CharacterEncodingForm::Ptr &cef) { cef_ = cef; }
    CharacterEncodingScheme::Ptr characterEncodingScheme() const { return ces_; }
    void characterEncodingScheme(const CharacterEncodingScheme::Ptr &ces) { ces_ = ces; }
    CodePointPredicate::Ptr codePointPredicate() const { return cpp_; }
    void codePointPredicate(const CodePointPredicate::Ptr &cpp) { cpp_ = cpp; }
};

class ROSE_DLL_API LengthEncodedString: public StringEncodingScheme {
    LengthEncodingScheme::Ptr les_;
    Sawyer::Optional<size_t> declaredLength_;           // decoded length
protected:
    LengthEncodedString(const LengthEncodingScheme::Ptr &les, const CharacterEncodingForm::Ptr &cef,
                        const CharacterEncodingScheme::Ptr &ces, const CodePointPredicate::Ptr &cpp)
        : StringEncodingScheme(cef, ces, cpp), les_(les) {}
public:
    typedef Sawyer::SharedPointer<LengthEncodedString> Ptr;

    static Ptr instance(const LengthEncodingScheme::Ptr &les, const CharacterEncodingForm::Ptr &cef,
                        const CharacterEncodingScheme::Ptr &ces, const CodePointPredicate::Ptr &cpp) {
        return Ptr(new LengthEncodedString(les, cef, ces, cpp));
    }
    virtual StringEncodingScheme::Ptr clone() const ROSE_OVERRIDE {
        LengthEncodingScheme::Ptr les = les_->clone();
        CharacterEncodingForm::Ptr cef = cef_->clone();
        CharacterEncodingScheme::Ptr ces = ces_->clone();
        CodePointPredicate::Ptr cpp = cpp_;             // not cloned since they have no state
        LengthEncodedString *inst = new LengthEncodedString(les, cef, ces, cpp);
        inst->state_ = state_;
        inst->codePoints_ = codePoints_;
        inst->nCodePoints_ = nCodePoints_;
        inst->declaredLength_ = declaredLength_;
        return Ptr(inst);
    }
    virtual std::string name() const ROSE_OVERRIDE;
    virtual Octets encode(const CodePoints&) ROSE_OVERRIDE;
    virtual State decode(Octet) ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;

    Sawyer::Optional<size_t> declaredLength() const { return declaredLength_; }

    LengthEncodingScheme::Ptr lengthEncodingScheme() const { return les_; }
    void lengthEncodingScheme(const LengthEncodingScheme::Ptr &les) { les_ = les; }
};

LengthEncodedString::Ptr lengthEncodedString(const LengthEncodingScheme::Ptr &les, const CharacterEncodingForm::Ptr &cef,
                                             const CharacterEncodingScheme::Ptr &ces, const CodePointPredicate::Ptr &cpp);

LengthEncodedString::Ptr lengthEncodedPrintableAscii(size_t lengthSize,
                                                     ByteOrder::Endianness order = ByteOrder::ORDER_UNSPECIFIED);

LengthEncodedString::Ptr lengthEncodedPrintableAsciiWide(size_t lengthSize, ByteOrder::Endianness order, size_t charSize);

class ROSE_DLL_API TerminatedString: public StringEncodingScheme {
    CodePoints terminators_;
    Sawyer::Optional<CodePoint> terminated_;            // decoded termination
protected:
    TerminatedString(const CharacterEncodingForm::Ptr &cef, const CharacterEncodingScheme::Ptr &ces,
                     const CodePointPredicate::Ptr &cpp, const CodePoints &terminators)
        : StringEncodingScheme(cef, ces, cpp), terminators_(terminators) {}
public:
    typedef Sawyer::SharedPointer<TerminatedString> Ptr;

    static Ptr instance(const CharacterEncodingForm::Ptr &cef, const CharacterEncodingScheme::Ptr &ces,
                        const CodePointPredicate::Ptr &cpp, const CodePoints &terminators) {
        return Ptr(new TerminatedString(cef, ces, cpp, terminators));
    }
    static Ptr instance(const CharacterEncodingForm::Ptr &cef, const CharacterEncodingScheme::Ptr &ces,
                        const CodePointPredicate::Ptr &cpp, CodePoint terminator = 0) {
        return Ptr(new TerminatedString(cef, ces, cpp, CodePoints(1, terminator)));
    }
    virtual StringEncodingScheme::Ptr clone() const ROSE_OVERRIDE {
        CharacterEncodingForm::Ptr cef = cef_->clone();
        CharacterEncodingScheme::Ptr ces = ces_->clone();
        CodePointPredicate::Ptr cpp = cpp_;             // not cloned since they have no state
        TerminatedString *inst = new TerminatedString(cef, ces, cpp, terminators_);
        inst->state_ = state_;
        inst->codePoints_ = codePoints_;
        inst->nCodePoints_ = nCodePoints_;
        inst->terminated_ = terminated_;
        return Ptr(inst);
    }
    virtual std::string name() const ROSE_OVERRIDE;
    virtual Octets encode(const CodePoints&) ROSE_OVERRIDE;
    virtual State decode(Octet) ROSE_OVERRIDE;
    virtual void reset() ROSE_OVERRIDE;

    Sawyer::Optional<CodePoint> terminated() const { return terminated_; }

    const CodePoints& terminators() const { return terminators_; }
    CodePoints& terminators() { return terminators_; }
};

TerminatedString::Ptr nulTerminatedPrintableAscii();

TerminatedString::Ptr nulTerminatedPrintableAsciiWide(size_t charSize, ByteOrder::Endianness order);

class ROSE_DLL_API EncodedString {
    StringEncodingScheme::Ptr encoder_;             // how string is encoded
    AddressInterval where_;                         // where encoded string is located
public:
    EncodedString() {}
    EncodedString(const StringEncodingScheme::Ptr &encoder, const AddressInterval &where)
        : encoder_(encoder), where_(where) {}

    StringEncodingScheme::Ptr encoder() const { return encoder_; }

    const AddressInterval& where() const { return where_; }

    rose_addr_t address() const { return where_.least(); }

    size_t size() const { return where_.size(); }

    size_t length() const { return encoder_->length(); }

    const CodePoints& codePoints() const { return encoder_->codePoints(); }

    std::string narrow() const;

    std::wstring wide() const;

    void decode(const MemoryMap&);
};

class ROSE_DLL_API StringFinder {
public:
    struct Settings {
        size_t minLength;

        size_t maxLength;
        
        size_t maxOverlap;

        bool keepingOnlyLongest;

        Settings(): minLength(5), maxLength(-1), maxOverlap(8), keepingOnlyLongest(true) {}
    };
    
private:
    Settings settings_;                                 // command-line settings for this analysis
    bool discardingCodePoints_;                         // whether to store decoded code points
    std::vector<StringEncodingScheme::Ptr> encoders_;   // encodings to use when searching
    std::vector<EncodedString> strings_;                // strings that have been found

public:
    StringFinder(): discardingCodePoints_(false) {}

    const Settings& settings() const { return settings_; }
    Settings& settings() { return settings_; }
    bool discardingCodePoints() const { return discardingCodePoints_; }
    StringFinder& discardingCodePoints(bool b) { discardingCodePoints_=b; return *this; }
    const std::vector<StringEncodingScheme::Ptr>& encoders() const { return encoders_; }
    std::vector<StringEncodingScheme::Ptr>& encoders() { return encoders_; }
    static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings&);
    Sawyer::CommandLine::SwitchGroup commandLineSwitches();
    StringFinder& insertCommonEncoders(ByteOrder::Endianness);

    StringFinder& insertUncommonEncoders(ByteOrder::Endianness);

    StringFinder& reset() { strings_.clear(); return *this; }

    StringFinder& find(const MemoryMap::ConstConstraints&, Sawyer::Container::MatchFlags flags=0);

    const std::vector<EncodedString>& strings() const { return strings_; }
    std::vector<EncodedString>& strings() { return strings_; }
    std::ostream& print(std::ostream&) const;
};

std::ostream& operator<<(std::ostream&, const StringFinder&);

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

#endif
#endif