Partitioner.h

Go to the documentation of this file.

#ifndef ROSE_DISASSEMBLER_PARTITIONER_H
#define ROSE_DISASSEMBLER_PARTITIONER_H

#include "callbacks.h"
#include "Disassembler.h"

#ifndef NAN
#define INFINITY (DBL_MAX+DBL_MAX)
#define NAN (INFINITY-INFINITY)
#endif

class Partitioner {
    /*************************************************************************************************************************
     *                                        Public Exceptions
     *************************************************************************************************************************/
public:
    struct Exception {
        std::string mesg;
        Exception(const std::string &mesg): mesg(mesg) {}
        void print(std::ostream &o) const { o <<mesg; }
        friend std::ostream& operator<<(std::ostream &o, const Exception &e);
    };

    /*************************************************************************************************************************
     *                                        Data Structures Useful to Subclasses
     *************************************************************************************************************************/
protected:

    struct Function;
    struct DataBlock;
    struct BasicBlock;

    class Instruction {
    public:
        Instruction(SgAsmInstruction *node): node(node), bblock(NULL) { assert(node!=NULL); }
        SgAsmInstruction *node;                 
        BasicBlock *bblock;                     
        /* These methods are forwarded to the underlying instruction node for convenience. */
        Disassembler::AddressSet get_successors(bool *complete) const { return node->get_successors(complete); }
        rose_addr_t get_address() const { return node->get_address(); }
        size_t get_size() const { return node->get_size(); }
        bool terminates_basic_block() const { return node->terminates_basic_block(); }
        SgUnsignedCharList get_raw_bytes() const { return node->get_raw_bytes(); } // FIXME: should return const ref?
    };

    typedef std::map<rose_addr_t, Instruction*> InstructionMap;
    typedef std::vector<Instruction*> InstructionVector;

    static SgAsmInstruction *isSgAsmInstruction(const Instruction *);
    static SgAsmInstruction *isSgAsmInstruction(SgNode*);
    static SgAsmx86Instruction *isSgAsmx86Instruction(const Instruction*);
    static SgAsmx86Instruction *isSgAsmx86Instruction(SgNode*);
    class BlockAnalysisCache {
    public:
        BlockAnalysisCache(): age(0), sucs_complete(false), is_function_call(false), call_target(NO_TARGET),
                              function_return(false), alias_for(0) {}
        void clear() {
            age = 0;
            sucs.clear();
            sucs_complete = false;
            is_function_call = false;
            call_target = NO_TARGET;
            function_return = false;
            alias_for = 0;
        }

        size_t age;                             
        Disassembler::AddressSet sucs;          
        bool sucs_complete;                     
        bool is_function_call;                  
        rose_addr_t call_target;                
        bool function_return;                   
        rose_addr_t alias_for;                  
    };

    struct BasicBlock {
        BasicBlock(): reason(SgAsmBlock::BLK_NONE), function(NULL), code_likelihood(1.0) {}

        ~BasicBlock() {}

        bool valid_cache() const { return cache.age==insns.size(); }

        void invalidate_cache() { cache.age=0; }

        void validate_cache() { cache.age=insns.size(); }

        void clear_data_blocks();

        Instruction* last_insn() const;         
        rose_addr_t address() const;            /* Return the address of the basic block's first (entry) instruction. */
        unsigned reason;                        
        std::vector<Instruction*> insns;        
        std::set<DataBlock*> data_blocks;       
        BlockAnalysisCache cache;               
        Function* function;                     
        double code_likelihood;                 
    };
    typedef std::map<rose_addr_t, BasicBlock*> BasicBlocks;

    struct DataBlock {
        DataBlock(): reason(SgAsmBlock::BLK_NONE), function(NULL), basic_block(NULL) {}

        ~DataBlock() {}

        rose_addr_t address() const;            /* Return the address of the first node of a data block. */
        std::vector<SgAsmStaticData*> nodes;    
        unsigned reason;                        
        Function *function;                     
        BasicBlock *basic_block;                
    };
    typedef std::map<rose_addr_t, DataBlock*> DataBlocks;

    class Function {
    public:
        Function(rose_addr_t entry_va)
            : reason(0), pending(true), entry_va(entry_va),
              may_return_cur(SgAsmFunction::RET_UNKNOWN), may_return_old(SgAsmFunction::RET_UNKNOWN) {}
        Function(rose_addr_t entry_va, unsigned r)
            : reason(r), pending(true), entry_va(entry_va),
              may_return_cur(SgAsmFunction::RET_UNKNOWN), may_return_old(SgAsmFunction::RET_UNKNOWN) {}
        Function(rose_addr_t entry_va, unsigned r, const std::string& name)
            : reason(r), name(name), pending(true), entry_va(entry_va),
              may_return_cur(SgAsmFunction::RET_UNKNOWN), may_return_old(SgAsmFunction::RET_UNKNOWN) {}

        void clear_basic_blocks();

        void clear_data_blocks();

        void move_basic_blocks_from(Function *other);

        void move_data_blocks_from(Function *other);

        SgAsmFunction::MayReturn get_may_return() const { return may_return_cur; }
        void set_may_return(SgAsmFunction::MayReturn may_return) { may_return_cur = may_return; }
        bool changed_may_return() const { return may_return_cur != may_return_old; }
        void commit_may_return() { may_return_old = may_return_cur; }
        bool possible_may_return() const {
            return SgAsmFunction::RET_SOMETIMES==get_may_return() || SgAsmFunction::RET_ALWAYS==get_may_return();
        }

        void promote_may_return(SgAsmFunction::MayReturn new_value);

        Function *init_properties(const Function &other);

        void show_properties(FILE*) const;

        BasicBlock *entry_basic_block() const;

    public:
        /* If you add more data members, also update detach_thunk() and/or init_properties() */
        unsigned reason;                        
        std::string name;                       
        BasicBlocks basic_blocks;               
        DataBlocks data_blocks;                 
        bool pending;                           
        rose_addr_t entry_va;                   
        Disassembler::AddressSet heads;         
    private:
        /* If you add more data members, also update detach_thunk() and/or init_properties() */
        SgAsmFunction::MayReturn may_return_cur; 
        SgAsmFunction::MayReturn may_return_old; 
    };
    typedef std::map<rose_addr_t, Function*> Functions;

    typedef void (*FunctionDetector)(Partitioner*, SgAsmGenericHeader*);

    struct BlockConfig {
        BlockConfig(): ninsns(0), alias_for(0), sucs_specified(false), sucs_complete(false) {}
        size_t ninsns;                          
        rose_addr_t alias_for;                  
        bool sucs_specified;                    
        Disassembler::AddressSet sucs;          
        bool sucs_complete;                     
        SgUnsignedCharList sucs_program;        
    };
    typedef std::map<rose_addr_t, BlockConfig*> BlockConfigMap;

    /*************************************************************************************************************************
     *                                                     Deprecated
     *************************************************************************************************************************/
public:

    /* FIXME: Backward compatibility stuff prior to 2010-01-01. These are deprecated and should eventually be removed. They
     *        are currently used by src/midend/binaryAnalyses/binary_analysis.C for some of the CFG and call graph functions. */

    typedef std::map<rose_addr_t, Disassembler::AddressSet> BasicBlockStarts;

    BasicBlockStarts detectBasicBlocks(const Disassembler::InstructionMap&) const __attribute__((deprecated));

    struct FunctionStart {
        FunctionStart(unsigned reason, std::string name): reason(reason), name(name) {}
        unsigned reason;                        
        std::string name;                       
    };

    typedef std::map<rose_addr_t, FunctionStart> FunctionStarts;

    FunctionStarts detectFunctions(SgAsmInterpretation*, const Disassembler::InstructionMap &insns,
                                   BasicBlockStarts &bb_starts/*out*/) const __attribute__((deprecated));


    /*************************************************************************************************************************
     *                                                 Constructors, etc.
     *************************************************************************************************************************/
public:

    Partitioner()
        : aggregate_mean(NULL), aggregate_variance(NULL), code_criteria(NULL), disassembler(NULL), map(NULL),
          func_heuristics(SgAsmFunction::FUNC_DEFAULT), debug(NULL), allow_discont_blocks(true)
        {}
    virtual ~Partitioner() { clear(); }

    /*************************************************************************************************************************
     *                                              Accessors for Properties
     *************************************************************************************************************************/
public:

    virtual void set_search(unsigned heuristics) {
        func_heuristics = heuristics;
    }

    virtual unsigned get_search() const {
        return func_heuristics;
    }

    void set_allow_discontiguous_blocks(bool b) {
        allow_discont_blocks = b;
    }

    bool get_allow_discontiguous_blocks() const {
        return allow_discont_blocks;
    }

    void set_debug(FILE *f) {
        debug = f;
    }

    FILE *get_debug() const {
        return debug;
    }

    void set_map(MemoryMap *mmap, MemoryMap *ro_mmap=NULL);
    MemoryMap *get_map() const {
        return map;
    }
    void set_progress_reporting(FILE*, unsigned min_interval);

    /*************************************************************************************************************************
     *                                                High-level Functions
     *************************************************************************************************************************/
public:

    void add_function_detector(FunctionDetector f) {
        user_detectors.push_back(f);
    }

    static unsigned parse_switches(const std::string&, unsigned initial_flags);

    virtual SgAsmBlock* partition(SgAsmInterpretation*, const Disassembler::InstructionMap&, MemoryMap *mmap=NULL);

    virtual SgAsmBlock* partition(SgAsmInterpretation*, Disassembler*, MemoryMap*);

    virtual void clear();

    virtual void load_config(const std::string &filename);

    virtual void add_instructions(const Disassembler::InstructionMap& insns);

    Disassembler::InstructionMap get_instructions() const;

    const Disassembler::BadMap& get_disassembler_errors() const {
        return bad_insns;
    }

    void clear_disassembler_errors() {
        bad_insns.clear();
    }

    virtual Instruction* find_instruction(rose_addr_t, bool create=true);

    virtual Instruction* discard(Instruction*, bool discard_entire_block=false);

    virtual BasicBlock *discard(BasicBlock*);

    virtual Function* add_function(rose_addr_t entry_va, unsigned reasons, std::string name="");

    virtual Function* find_function(rose_addr_t entry_va);

    virtual SgAsmBlock* build_ast(SgAsmInterpretation *interp=NULL);

    virtual void fixup_cfg_edges(SgNode *ast);

    virtual void fixup_pointers(SgNode *ast, SgAsmInterpretation *interp=NULL);

    static void disassembleInterpretation(SgAsmInterpretation*);

    /**************************************************************************************************************************
     *                                  Range maps relating address ranges to objects
     **************************************************************************************************************************/
public:
    class FunctionRangeMapValue: public RangeMapValue<Extent, Function*> {
    public:
        FunctionRangeMapValue():            RangeMapValue<Extent, Function*>(NULL) {}
        FunctionRangeMapValue(Function *f): RangeMapValue<Extent, Function*>(f)    {} // implicit

        FunctionRangeMapValue split(const Extent &my_range, const Extent::Value &new_end) {
            assert(my_range.contains(Extent(new_end)));
            return *this;
        }

        void print(std::ostream &o) const {
            if (NULL==value) {
                o <<"(null)";
            } else {
                o <<"F" <<StringUtility::addrToString(value->entry_va);
            }
        }
    };

    typedef RangeMap<Extent, FunctionRangeMapValue> FunctionRangeMap;

    class DataRangeMapValue: public RangeMapValue<Extent, DataBlock*> {
    public:
        DataRangeMapValue():             RangeMapValue<Extent, DataBlock*>(NULL) {}
        DataRangeMapValue(DataBlock *d): RangeMapValue<Extent, DataBlock*>(d)    {} // implicit

        DataRangeMapValue split(const Extent &my_range, const Extent::Value &new_end) {
            assert(my_range.contains(Extent(new_end)));
            return *this;
        }

        void print(std::ostream &o) const {
            if (NULL==value) {
                o <<"(null)";
            } else {
                o <<"D" <<StringUtility::addrToString(value->address());
            }
        }
    };

    typedef RangeMap<Extent, DataRangeMapValue> DataRangeMap;

    /**************************************************************************************************************************
     *                                  Methods for characterizing whether something is code
     **************************************************************************************************************************/
public:

    class RegionStats {
    private:
        struct DictionaryEntry {
            DictionaryEntry(): weight(0.0) {}
            DictionaryEntry(const std::string &name, const std::string &desc, double weight)
                : name(name), desc(desc), weight(weight) {}
            std::string name;
            std::string desc;
            double weight;                                      
        };

        struct AnalysisResult {
            AnalysisResult(): sum(0), nsamples(0) {}
            AnalysisResult(double d): sum(d), nsamples(1) {} // implicit
            double sum;
            size_t nsamples;
        };

        static std::vector<DictionaryEntry> dictionary;
        std::vector<AnalysisResult> results;

    public:
        enum AnalysisEnum {
            RA_NBYTES=0, RA_NINSNS, RA_NCOVERAGE, RA_RCOVERAGE, RA_NSTARTS, RA_NFAILS, RA_RFAILS, RA_NOVERLAPS, RA_ROVERLAPS,
            RA_NINCOMPLETE, RA_RINCOMPLETE, RA_NBRANCHES, RA_RBRANCHES, RA_NCALLS, RA_RCALLS, RA_NNONCALLS, RA_RNONCALLS,
            RA_NINTERNAL, RA_RINTERNAL, RA_NICFGEDGES, RA_RICFGEDGES, RA_NCOMPS, RA_RCOMPS, RA_NIUNIQUE, RA_RIUNIQUE,
            RA_NREGREFS, RA_RREGREFS, RA_REGSZ, RA_REGVAR, RA_NPRIV, RA_RPRIV, RA_NFLOAT, RA_RFLOAT
        };

        RegionStats() { init_class(); }
        virtual ~RegionStats() {}
        virtual RegionStats* create() const;                    
        static size_t define_analysis(const std::string &name, const std::string &desc, double weight, size_t id=(size_t)(-1));
        static size_t find_analysis(const std::string &name);   
        static size_t get_nanalyses();                          
        static const std::string& get_name(size_t id);          
        static const std::string& get_desc(size_t id);          
        static double get_weight(size_t id);                    
        virtual void add_sample(size_t id, double val, size_t nsamples=1);  
        virtual size_t get_nsamples(size_t id) const;           
        virtual double get_sum(size_t id) const;                
        virtual double get_value(size_t id) const;              
        virtual void compute_ratios();                          
        virtual void set_value(size_t id, double val);          
        double divnan(size_t num_id, size_t den_id) const;      
        void add_samples(const RegionStats*);                   
        void square_diff(const RegionStats*);                   
        virtual void print(std::ostream&) const;
        friend std::ostream& operator<<(std::ostream&, const RegionStats&);
    protected:
        static void init_class();

    };

    class CodeCriteria {
    private:
        struct DictionaryEntry {
            DictionaryEntry() {}
            DictionaryEntry(const std::string &name, const std::string &desc): name(name), desc(desc) {}
            std::string name;
            std::string desc;
        };

        struct Criterion {
            Criterion(): mean(0.0), variance(0.0), weight(0.0) {}
            double mean;
            double variance;
            double weight;
        };

        static std::vector<DictionaryEntry> dictionary;
        std::vector<Criterion> criteria;
        double threshold;

    public:
        CodeCriteria(): threshold(0.5) { init_class(); }
        CodeCriteria(const RegionStats *mean, const RegionStats *variance, double threshold) {
            init_class();
            init(mean, variance, threshold);
        }
        virtual ~CodeCriteria() {}
        virtual CodeCriteria* create() const;

        static size_t define_criterion(const std::string &name, const std::string &desc, size_t id=(size_t)(-1));
        static size_t find_criterion(const std::string &name);
        static size_t get_ncriteria();
        static const std::string& get_name(size_t id);
        static const std::string& get_desc(size_t id);

        virtual double get_mean(size_t id) const;
        virtual void set_mean(size_t id, double mean);
        virtual double get_variance(size_t id) const;
        virtual void set_variance(size_t id, double variance);
        virtual double get_weight(size_t id) const;
        virtual void set_weight(size_t id, double weight);
        void set_value(size_t id, double mean, double variance, double weight) {
            set_mean(id, mean);
            set_variance(id, variance);
            set_weight(id, weight);
        }

        double get_threshold() const { return threshold; }
        void set_threshold(double th) { threshold=th; }
        virtual double get_vote(const RegionStats*, std::vector<double> *votes=NULL) const;
        virtual bool satisfied_by(const RegionStats*, double *raw_vote_ptr=NULL, std::ostream *debug=NULL) const;

        virtual void print(std::ostream&, const RegionStats *stats=NULL, const std::vector<double> *votes=NULL,
                           const double *total_vote=NULL) const;
        friend std::ostream& operator<<(std::ostream&, const CodeCriteria&);

    protected:
        static void init_class();
        virtual void init(const RegionStats *mean, const RegionStats *variance, double threshold);
        
    };

    virtual RegionStats *new_region_stats() {
        return new RegionStats;
    }

    virtual CodeCriteria *new_code_criteria() {
        return new CodeCriteria;
    }
    virtual CodeCriteria *new_code_criteria(const RegionStats *mean, const RegionStats *variance, double threshold) {
        return new CodeCriteria(mean, variance, threshold);
    }
    virtual RegionStats *region_statistics(const ExtentMap&);
    virtual RegionStats *region_statistics(Function*);
    virtual RegionStats *region_statistics();
    virtual RegionStats *aggregate_statistics(bool do_variance=true);

    virtual RegionStats *get_aggregate_mean() const { return aggregate_mean; }
    virtual RegionStats *get_aggregate_variance() const { return aggregate_variance; }
    virtual void clear_aggregate_statistics() {
        delete aggregate_mean;       aggregate_mean = NULL;
        delete aggregate_variance;   aggregate_variance = NULL;
    }

    virtual size_t count_kinds(const InstructionMap&);
    virtual size_t count_kinds() { return count_privileged(insns); }
    virtual size_t count_privileged(const InstructionMap&);
    virtual size_t count_privileged() { return count_privileged(insns); }
    virtual double ratio_privileged() { return insns.empty() ? NAN : (double)count_privileged(insns) / insns.size(); }
    virtual size_t count_floating_point(const InstructionMap&);
    virtual size_t count_floating_point() { return count_floating_point(insns); }
    virtual double ratio_floating_point() { return insns.empty() ? NAN : (double)count_floating_point(insns) / insns.size(); }
    virtual size_t count_registers(const InstructionMap&, double *mean=NULL, double *variance=NULL);
    virtual size_t count_registers(double *mean=NULL, double *variance=NULL) { return count_registers(insns, mean, variance); }
    virtual double ratio_registers(double *mean=NULL, double *variance=NULL) {
        return insns.empty() ? NAN : (double)count_registers(mean, variance) / insns.size();
    }
    virtual double count_size_variance(const InstructionMap &insns);
    virtual double count_size_variance() { return count_size_variance(insns); }
    virtual bool is_code(const ExtentMap &region, double *raw_vote_ptr=NULL, std::ostream *debug=NULL);

    virtual CodeCriteria *get_code_criteria() const { return code_criteria; }
    virtual void set_code_criteria(CodeCriteria *cc) { code_criteria = cc; }
protected:
    RegionStats *aggregate_mean;                
    RegionStats *aggregate_variance;            
    CodeCriteria *code_criteria;                
    /**************************************************************************************************************************
     *                                  Functions for scanning through memory
     **************************************************************************************************************************/
public:

    class InsnRangeCallback {
    public:
        struct Args {
            Args(Partitioner *partitioner, Instruction *insn_prev, Instruction *insn_begin,
                 Instruction *insn_end, size_t ninsns)
                : partitioner(partitioner), insn_prev(insn_prev), insn_begin(insn_begin), insn_end(insn_end),
                  ninsns(ninsns) {}
            Partitioner *partitioner;
            Instruction *insn_prev;                     
            Instruction *insn_begin;                    
            Instruction *insn_end;                      
            size_t ninsns;                              
        };

        virtual ~InsnRangeCallback() {}

        virtual bool operator()(bool enabled, const Args &args) = 0;
    };
    typedef ROSE_Callbacks::List<InsnRangeCallback> InsnRangeCallbacks;

    class ByteRangeCallback {
    public:
        struct Args {
            Args(Partitioner *partitioner, MemoryMap *restrict_map, const FunctionRangeMap &ranges, const Extent &range)
                : partitioner(partitioner), restrict_map(restrict_map), ranges(ranges), range(range) {}
            Partitioner *partitioner;
            MemoryMap *restrict_map;                    
            const FunctionRangeMap &ranges;             
            Extent range;                               
        };

        virtual ~ByteRangeCallback() {}

        virtual bool operator()(bool enabled, const Args &args) = 0;
    };
    typedef ROSE_Callbacks::List<ByteRangeCallback> ByteRangeCallbacks;

    virtual void scan_contiguous_insns(InstructionMap insns, InsnRangeCallbacks &cblist,
                                       Instruction *insn_prev, Instruction *insn_end);
    void scan_contiguous_insns(const InstructionMap &insns, InsnRangeCallback *callback,
                               Instruction *insn_prev, Instruction *insn_end) {
        InsnRangeCallbacks cblist(callback);
        scan_contiguous_insns(insns, cblist, insn_prev, insn_end);
    }
    virtual void scan_unassigned_insns(InsnRangeCallbacks &callbacks);
    void scan_unassigned_insns(InsnRangeCallback *callback) {
        InsnRangeCallbacks cblist(callback);
        scan_unassigned_insns(cblist);
    }
    virtual void scan_intrafunc_insns(InsnRangeCallbacks &callbacks);
    void scan_intrafunc_insns(InsnRangeCallback *callback) {
        InsnRangeCallbacks cblist(callback);
        scan_intrafunc_insns(cblist);
    }
    virtual void scan_interfunc_insns(InsnRangeCallbacks &callbacks);
    void scan_interfunc_insns(InsnRangeCallback *callback) {
        InsnRangeCallbacks cblist(callback);
        scan_interfunc_insns(cblist);
    }
    virtual void scan_unassigned_bytes(ByteRangeCallbacks &callbacks, MemoryMap *restrict_map=NULL);
    void scan_unassigned_bytes(ByteRangeCallback *callback, MemoryMap *restrict_map=NULL) {
        ByteRangeCallbacks cblist(callback);
        scan_unassigned_bytes(cblist, restrict_map);
    }
    virtual void scan_intrafunc_bytes(ByteRangeCallbacks &callbacks, MemoryMap *restrict_map=NULL);
    void scan_intrafunc_bytes(ByteRangeCallback *callback, MemoryMap *restrict_map=NULL) {
        ByteRangeCallbacks cblist(callback);
        scan_intrafunc_bytes(cblist, restrict_map);
    }
    virtual void scan_interfunc_bytes(ByteRangeCallbacks &callbacks, MemoryMap *restrict_map=NULL);
    void scan_interfunc_bytes(ByteRangeCallback *callback, MemoryMap *restrict_map=NULL) {
        ByteRangeCallbacks cblist(callback);
        scan_interfunc_bytes(cblist, restrict_map);
    }
    struct FindDataPadding: public ByteRangeCallback {
        std::vector<SgUnsignedCharList> patterns;       
        size_t minimum_nrep;                            
        size_t maximum_nrep;                            
        bool begins_contiguously;                       
        bool ends_contiguously;                         
        rose_addr_t maximum_range_size;                 
        size_t nfound;                                  
        FindDataPadding()
            : minimum_nrep(2), maximum_nrep(1024*1024), begins_contiguously(false), ends_contiguously(true),
              maximum_range_size(100*1024*1024),  nfound(0) {}
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindData: public ByteRangeCallback {
        unsigned excluded_reasons;                      
        DataRangeMap *padding_ranges;                   
        size_t nfound;                                  
        FindData(): excluded_reasons(SgAsmFunction::FUNC_PADDING|SgAsmFunction::FUNC_THUNK), padding_ranges(NULL), nfound(0) {}
        ~FindData() { delete padding_ranges; }
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindInsnPadding: public InsnRangeCallback {
        std::set<X86InstructionKind> x86_kinds;                 
        std::vector<SgUnsignedCharList> byte_patterns;          
        bool begins_contiguously;                               
        bool ends_contiguously;                                 
        size_t minimum_size;                                    
        bool add_as_data;                                       
        size_t nfound;                                          
        FindInsnPadding()
            : begins_contiguously(true), ends_contiguously(true), minimum_size(0), add_as_data(true), nfound(0) {}
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindFunctionFragments: public ByteRangeCallback {
        bool require_noninterleaved;                            
        bool require_intrafunction;                             
        double threshold;                                       
        unsigned excluded_reasons;                              
        size_t nfound;                                          
        FunctionRangeMap *function_extents;                     
        CodeCriteria *code_criteria;                            
        FindFunctionFragments()
            : require_noninterleaved(true), require_intrafunction(false), threshold(0.7),
              excluded_reasons(SgAsmFunction::FUNC_PADDING|SgAsmFunction::FUNC_THUNK),
              nfound(0), function_extents(NULL), code_criteria(NULL)
            {}
        virtual ~FindFunctionFragments() {
            delete function_extents;
            delete code_criteria;
        }
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindThunks: public InsnRangeCallback {
        size_t validate_targets;        
        size_t nfound;                  
        FindThunks(): validate_targets(true), nfound(0) {}
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindThunkTables: public ByteRangeCallback {
        bool begins_contiguously;       
        bool ends_contiguously;         
        size_t minimum_nthunks;         
        bool validate_targets;          
        size_t nfound;                  
        FindThunkTables()
            : begins_contiguously(false), ends_contiguously(false), minimum_nthunks(3), validate_targets(true), nfound(0) {}
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindInterPadFunctions: public ByteRangeCallback {
        DataRangeMap *padding_ranges;   
        size_t nfound;                  
        FindInterPadFunctions(): padding_ranges(NULL), nfound(0) {}
        ~FindInterPadFunctions() { delete padding_ranges; }
        virtual bool operator()(bool enabled, const Args &args);
    };

    struct FindPostFunctionInsns: public InsnRangeCallback {
        size_t nfound;                  
        FindPostFunctionInsns(): nfound(0) {}
        virtual bool operator()(bool enabled, const Args &args);
    };

    /**************************************************************************************************************************
     *                                  Methods for finding functions by patterns
     **************************************************************************************************************************/
protected:
    static InstructionMap::const_iterator pattern1(const InstructionMap& insns, InstructionMap::const_iterator first,
                                                   Disassembler::AddressSet &exclude);

#if 0 /* Definitions are also commented out */

    static InstructionMap::const_iterator pattern2(const InstructionMap& insns, InstructionMap::const_iterator first,
                                                   Disassembler::AddressSet &exclude);

    static InstructionMap::const_iterator pattern3(const InstructionMap& insns, InstructionMap::const_iterator first,
                                                   Disassembler::AddressSet &exclude);
#endif

    /*************************************************************************************************************************
     *                                                 Low-level Functions
     *
     * These are public because they might need to be called by the partitioner's instruction or address traversal callbacks,
     * and its often convenient to declare those functors outside any Partitioner subclass.
     *************************************************************************************************************************/
public:
    /* NOTE: Some of these are documented at their implementation because the documentation is more than what conveniently
     *       fits here. */
    struct AbandonFunctionDiscovery {};                         
    virtual void append(BasicBlock*, Instruction*);             
    virtual void append(BasicBlock*, DataBlock*, unsigned reasons); /* Add a data block to a basic block. */
    virtual void append(Function*, BasicBlock*, unsigned reasons, bool keep=false); /* Append a basic block to a function */
    virtual void append(Function*, DataBlock*, unsigned reasons, bool force=false); /* Append a data block to a function */
    virtual void remove(Function*, BasicBlock*);                /* Remove a basic block from a function. */
    virtual void remove(Function*, DataBlock*);                 /* Remove a data block from a function. */
    virtual void remove(BasicBlock*, DataBlock*);               /* Remove association between basic block and data block. */
    virtual BasicBlock* find_bb_containing(rose_addr_t, bool create=true); /* Find basic block containing instruction address */
    virtual BasicBlock* find_bb_starting(rose_addr_t, bool create=true);   /* Find or create block starting at specified address */
    virtual DataBlock* find_db_starting(rose_addr_t, size_t size); /* Find (or create if size>0) a data block */
    virtual Disassembler::AddressSet successors(BasicBlock*, bool *complete=NULL); /* Calculates known successors */
    virtual rose_addr_t call_target(BasicBlock*);               /* Returns address if block could be a function call */
    virtual void truncate(BasicBlock*, rose_addr_t);            /* Remove instructions from the end of a basic block. */
    virtual void discover_first_block(Function*);               /* Adds first basic block to empty function to start discovery. */
    virtual void discover_blocks(Function*, unsigned reason);   /* Start to recursively discover blocks of a function. */
    virtual void discover_blocks(Function*, rose_addr_t, unsigned reason); /* Recursively discovers blocks of a function. */
    virtual void pre_cfg(SgAsmInterpretation *interp=NULL);     
    virtual void analyze_cfg(SgAsmBlock::Reason);               
    virtual void post_cfg(SgAsmInterpretation *interp=NULL);    
    virtual SgAsmFunction* build_ast(Function*);                
    virtual SgAsmBlock* build_ast(BasicBlock*);                 
    virtual SgAsmBlock* build_ast(DataBlock*);                  
    virtual bool pops_return_address(rose_addr_t);              
    virtual void update_analyses(BasicBlock*);                  /* Makes sure cached analysis results are current. */
    virtual rose_addr_t canonic_block(rose_addr_t);             
    virtual bool is_function_call(BasicBlock*, rose_addr_t*);   /* True if basic block appears to call a function. */
    virtual bool is_thunk(Function*);                           /* True if function is a thunk. */
    virtual Function *effective_function(DataBlock*);           /* Function to which a data block is currently bound. */

    virtual void mark_call_insns();                             
    virtual void mark_ipd_configuration();                      
    virtual void mark_entry_targets(SgAsmGenericHeader*);       
    virtual void mark_export_entries(SgAsmGenericHeader*);      
    virtual void mark_eh_frames(SgAsmGenericHeader*);           
    virtual void mark_elf_plt_entries(SgAsmGenericHeader*);     
    virtual void mark_func_symbols(SgAsmGenericHeader*);        
    virtual void mark_func_patterns();                          /* Seeds functions according to instruction patterns */
    virtual void name_plt_entries(SgAsmGenericHeader*);         /* Assign names to ELF PLT functions */
    virtual void name_import_entries(SgAsmGenericHeader*);      /* Assign names to PE import functions */
    virtual void find_pe_iat_extents(SgAsmGenericHeader*);      /* Find addresses for all PE Import Address Tables */

    virtual size_t function_extent(FunctionRangeMap *extents);

    virtual size_t function_extent(Function*,
                                   FunctionRangeMap *extents=NULL/*in,out*/,
                                   rose_addr_t *lo_addr=NULL/*out*/, rose_addr_t *hi_addr=NULL/*out*/);

    virtual size_t datablock_extent(DataBlock*,
                                    DataRangeMap *extents=NULL/*in,out*/,
                                    rose_addr_t *lo_addr=NULL/*out*/, rose_addr_t *hi_addr=NULL/*out*/);

    virtual size_t datablock_extent(DataRangeMap *extent/*in,out*/);

    virtual size_t padding_extent(DataRangeMap *extent/*in,out*/);

    virtual bool is_contiguous(Function*, bool strict=false);

    static rose_addr_t get_indirection_addr(SgAsmInstruction*, rose_addr_t offset);

    static rose_addr_t value_of(SgAsmValueExpression*);

    void progress(FILE*, const char *fmt, ...) const __attribute__((format(printf, 3, 4)));

    virtual size_t detach_thunks();

    virtual bool detach_thunk(Function*);

    bool is_pe_dynlink_thunk(Instruction*);
    bool is_pe_dynlink_thunk(BasicBlock*);
    bool is_pe_dynlink_thunk(Function*);
    void name_pe_dynlink_thunks(SgAsmInterpretation *interp/*=NULL*/);
    
    virtual void adjust_padding();

    virtual void merge_function_fragments();

    virtual void merge_functions(Function *parent, Function *other);

    Disassembler::AddressSet discover_jump_table(BasicBlock *bb, bool do_create=true, ExtentMap *table_addresses=NULL);

    /*************************************************************************************************************************
     *                                   IPD Parser for initializing the Partitioner
     *************************************************************************************************************************/
public:

    class IPDParser {
    private:
        Partitioner *partitioner;               
        const char *input;                      
        size_t len;                             
        std::string input_name;                 
        size_t at;                              
        Function *cur_func;                     
        BlockConfig *cur_block;                 
    public:
        IPDParser(Partitioner *p, const char *input, size_t len, const std::string &input_name="")
            : partitioner(p), input(input), len(len), input_name(input_name), at(0), cur_func(NULL), cur_block(NULL) {}

        class Exception: public std::runtime_error {
        public:
            Exception(const std::string &mesg)
                : std::runtime_error(mesg), lnum(0) {}
            Exception(const std::string &mesg, const std::string &name, unsigned lnum=0)
                : std::runtime_error(mesg), name(name), lnum(lnum) {}
            ~Exception() throw() {}
            std::string format() const;         
            friend std::ostream& operator<<(std::ostream&, const Exception &e);

            std::string name;                   
            unsigned lnum;                      
        };

        void parse();                           
        static void unparse(std::ostream&, SgNode *ast); 
        /*************************************************************************************************************************
         * Lexical analysis functions.
         *************************************************************************************************************************/
    private:
        void skip_space();

        /* The is_* functions return true if the next token after white space and comments is of the specified type. */
        bool is_terminal(const char *to_match);
        bool is_symbol(const char *to_match);
        bool is_string();
        bool is_number();

        /* The match_* functions skip over white space and comments and attempt to match (and consume) the next token. If the next
         * token is not as expected then an exception is thrown. */
        void match_terminal(const char *to_match);
        void match_symbol(const char *to_match);
        std::string match_symbol();
        std::string match_string();
        rose_addr_t match_number();
        std::string match_asm();        /* assembly code inside nested curly braces */


        /*************************************************************************************************************************
         * Parsing functions (see rules above). Each returns true if the construct is present and was parsed, false if the
         * construct was not present. They throw an exception if the construct was partially present but an error occurred during
         * parsing.
         *************************************************************************************************************************/
    private:
        bool parse_File();
        bool parse_Declaration();
        bool parse_FuncDecl();
        bool parse_FuncBody();
        bool parse_FuncStmtList();
        bool parse_FuncStmt();
        bool parse_ReturnSpec();
        bool parse_BlockDecl();
        bool parse_BlockBody();
        bool parse_BlockStmtList();
        bool parse_BlockStmt();
        bool parse_Alias();
        bool parse_Successors();
    };

    /*************************************************************************************************************************
     *                                                     Data Members
     *
     * These are public so they can be accessed by user-defined traversal callbacks that might be declared outside any
     * Partitioner subclass.
     *************************************************************************************************************************/
public:
    Disassembler *disassembler;                         
    InstructionMap insns;                               
    MemoryMap *map;                                     
    MemoryMap ro_map;                                   
    ExtentMap pe_iat_extents;                           
    Disassembler::BadMap bad_insns;                     
    BasicBlocks basic_blocks;                           
    Functions functions;                                
    DataBlocks data_blocks;                             
    unsigned func_heuristics;                           
    std::vector<FunctionDetector> user_detectors;       
    FILE *debug;                                        
    bool allow_discont_blocks;                          
    BlockConfigMap block_config;                        
    static time_t progress_interval;                    
    static time_t progress_time;                        
    static FILE *progress_file;                         
public:
    static const rose_addr_t NO_TARGET = (rose_addr_t)-1;
};

#endif