jumptable.hh

Go to the documentation of this file.

/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef __CPUI_JUMPTABLE__
#define __CPUI_JUMPTABLE__

#include "emulateutil.hh"
#include "rangeutil.hh"

class EmulateFunction;

struct JumptableThunkError : public LowlevelError {
  JumptableThunkError(const string &s) : LowlevelError(s) {}    
};

struct JumptableNotReachableError : public LowlevelError {
  JumptableNotReachableError(const string &s) : LowlevelError(s) {} 
};

class LoadTable {
  friend class EmulateFunction;
  Address addr;         
  int4 size;            
  int4 num;         
public:
  LoadTable(void) {}        // Constructor for use with restoreXml
  LoadTable(const Address &ad,int4 sz) { addr = ad, size = sz; num = 1; }   
  LoadTable(const Address &ad,int4 sz,int4 nm) { addr = ad; size = sz; num = nm; }  
  bool operator<(const LoadTable &op2) const { return (addr < op2.addr); }  
  void saveXml(ostream &s) const;               
  void restoreXml(const Element *el,Architecture *glb);     
  static void collapseTable(vector<LoadTable> &table);      
};

class PathMeld {

  struct RootedOp {
    PcodeOp *op;    
    int4 rootVn;    
    RootedOp(PcodeOp *o,int4 root) { op = o; rootVn = root; }   
  };
  vector<Varnode *> commonVn;       
  vector<RootedOp> opMeld;      
  void internalIntersect(vector<int4> &parentMap);
  int4 meldOps(const vector<PcodeOp *> &path,int4 cutOff,const vector<int4> &parentMap);
  void truncatePaths(int4 cutPoint);
public:
  void set(const PathMeld &op2);    
  void set(const vector<PcodeOp *> &path,const vector<int4> &slot); 
  void set(PcodeOp *op,Varnode *vn);    
  void append(const PathMeld &op2); 
  void clear(void);         
  void meld(vector<PcodeOp *> &path,vector<int4> &slot);    
  void markPaths(bool val,int4 startVarnode);           
  int4 numCommonVarnode(void) const { return commonVn.size(); } 
  int4 numOps(void) const { return opMeld.size(); }     
  Varnode *getVarnode(int4 i) const { return commonVn[i]; } 
  Varnode *getOpParent(int4 i) const { return commonVn[ opMeld[i].rootVn ]; }   
  PcodeOp *getOp(int4 i) const { return opMeld[i].op; }     
  PcodeOp *getEarliestOp(int4 pos) const;       
  bool empty(void) const { return commonVn.empty(); }   
};

class EmulateFunction : public EmulatePcodeOp {
  Funcdata *fd;             
  map<Varnode *,uintb> varnodeMap;  
  bool collectloads;            
  vector<LoadTable> loadpoints;     
  virtual void executeLoad(void);
  virtual void executeBranch(void);
  virtual void executeBranchind(void);
  virtual void executeCall(void);
  virtual void executeCallind(void);
  virtual void executeCallother(void);
  virtual void fallthruOp(void);
public:
  EmulateFunction(Funcdata *f);     
  void setLoadCollect(bool val) { collectloads = val; } 
  virtual void setExecuteAddress(const Address &addr);
  virtual uintb getVarnodeValue(Varnode *vn) const;
  virtual void setVarnodeValue(Varnode *vn,uintb val);
  uintb emulatePath(uintb val,const PathMeld &pathMeld,PcodeOp *startop,Varnode *startvn);
  void collectLoadPoints(vector<LoadTable> &res) const; 
};

class FlowInfo;
class JumpTable;

class GuardRecord {
  PcodeOp *cbranch;     
  PcodeOp *readOp;      
  int4 indpath;         
  CircleRange range;        
  Varnode *vn;          
  Varnode *baseVn;      
  int4 bitsPreserved;       
public:
  GuardRecord(PcodeOp *bOp,PcodeOp *rOp,int4 path,const CircleRange &rng,Varnode *v);   
  PcodeOp *getBranch(void) const { return cbranch; }    
  PcodeOp *getReadOp(void) const { return readOp; } 
  int4 getPath(void) const { return indpath; }      
  const CircleRange &getRange(void) const { return range; } 
  void clear(void) { cbranch = (PcodeOp *)0; }      
  int4 valueMatch(Varnode *vn2,Varnode *baseVn2,int4 bitsPreserved2) const;
  static int4 oneOffMatch(PcodeOp *op1,PcodeOp *op2);
  static Varnode *quasiCopy(Varnode *vn,int4 &bitsPreserved);
};

class JumpValues {
public:
  virtual ~JumpValues(void) {}
  virtual void truncate(int4 nm)=0; 
  virtual uintb getSize(void) const=0;  
  virtual bool contains(uintb val) const=0; 

  virtual bool initializeForReading(void) const=0;

  virtual bool next(void) const=0;      
  virtual uintb getValue(void) const=0;     
  virtual Varnode *getStartVarnode(void) const=0;   
  virtual PcodeOp *getStartOp(void) const=0;        
  virtual bool isReversible(void) const=0;  
  virtual JumpValues *clone(void) const=0;  
};

class JumpValuesRange : public JumpValues {
protected:
  CircleRange range;        
  Varnode *normqvn;     
  PcodeOp *startop;     
  mutable uintb curval;     
public:
  void setRange(const CircleRange &rng) { range = rng; }    
  void setStartVn(Varnode *vn) { normqvn = vn; }        
  void setStartOp(PcodeOp *op) { startop = op; }        
  virtual void truncate(int4 nm);
  virtual uintb getSize(void) const;
  virtual bool contains(uintb val) const;
  virtual bool initializeForReading(void) const;
  virtual bool next(void) const;
  virtual uintb getValue(void) const;
  virtual Varnode *getStartVarnode(void) const;
  virtual PcodeOp *getStartOp(void) const;
  virtual bool isReversible(void) const { return true; }
  virtual JumpValues *clone(void) const;
};

class JumpValuesRangeDefault : public JumpValuesRange {
  uintb extravalue;     
  Varnode *extravn;     
  PcodeOp *extraop;     
  mutable bool lastvalue;   
public:
  void setExtraValue(uintb val) { extravalue = val; }   
  void setDefaultVn(Varnode *vn) { extravn = vn; }  
  void setDefaultOp(PcodeOp *op) { extraop = op; }  
  virtual uintb getSize(void) const;
  virtual bool contains(uintb val) const;
  virtual bool initializeForReading(void) const;
  virtual bool next(void) const;
  virtual Varnode *getStartVarnode(void) const;
  virtual PcodeOp *getStartOp(void) const;
  virtual bool isReversible(void) const { return !lastvalue; }  // The -extravalue- is not reversible
  virtual JumpValues *clone(void) const;
};

class JumpModel {
protected:
  JumpTable *jumptable;     
public:
  JumpModel(JumpTable *jt) { jumptable = jt; }  
  virtual ~JumpModel(void) {}           
  virtual bool isOverride(void) const=0;    
  virtual int4 getTableSize(void) const=0;  

  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize)=0;

  virtual void buildAddresses(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable,vector<LoadTable> *loadpoints) const=0;

  virtual void findUnnormalized(uint4 maxaddsub,uint4 maxleftright,uint4 maxext)=0;

  virtual void buildLabels(Funcdata *fd,vector<Address> &addresstable,vector<uintb> &label,const JumpModel *orig) const=0;

  virtual Varnode *foldInNormalization(Funcdata *fd,PcodeOp *indop)=0;

  virtual bool foldInGuards(Funcdata *fd,JumpTable *jump)=0;

  virtual bool sanityCheck(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable)=0;

  virtual JumpModel *clone(JumpTable *jt) const=0;  
  virtual void clear(void) {}           
  virtual void saveXml(ostream &s) const {}     
  virtual void restoreXml(const Element *el,Architecture *glb) {} 
};

class JumpModelTrivial : public JumpModel {
  uint4 size;           
public:
  JumpModelTrivial(JumpTable *jt) : JumpModel(jt) { size = 0; } 
  virtual bool isOverride(void) const { return false; }
  virtual int4 getTableSize(void) const { return size; }
  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize);
  virtual void buildAddresses(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable,vector<LoadTable> *loadpoints) const;
  virtual void findUnnormalized(uint4 maxaddsub,uint4 maxleftright,uint4 maxext) {}
  virtual void buildLabels(Funcdata *fd,vector<Address> &addresstable,vector<uintb> &label,const JumpModel *orig) const;
  virtual Varnode *foldInNormalization(Funcdata *fd,PcodeOp *indop) { return (Varnode *)0; }
  virtual bool foldInGuards(Funcdata *fd,JumpTable *jump) { return false; }
  virtual bool sanityCheck(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable) { return true; }
  virtual JumpModel *clone(JumpTable *jt) const;
};

class JumpBasic : public JumpModel {
protected:
  JumpValuesRange *jrange;      
  PathMeld pathMeld;            
  vector<GuardRecord> selectguards; 
  int4 varnodeIndex;            
  Varnode *normalvn;            
  Varnode *switchvn;            
  static bool isprune(Varnode *vn); 
  static bool ispoint(Varnode *vn); 
  static int4 getStride(Varnode *vn);   
  static uintb backup2Switch(Funcdata *fd,uintb output,Varnode *outvn,Varnode *invn);
  void findDeterminingVarnodes(PcodeOp *op,int4 slot);
  void analyzeGuards(BlockBasic *bl,int4 pathout);
  void calcRange(Varnode *vn,CircleRange &rng) const;
  void findSmallestNormal(uint4 matchsize);
  void findNormalized(Funcdata *fd,BlockBasic *rootbl,int4 pathout,uint4 matchsize,uint4 maxtablesize);
  void markFoldableGuards();
  void markModel(bool val);     
  bool flowsOnlyToModel(Varnode *vn,PcodeOp *trailOp);  

  virtual bool foldInOneGuard(Funcdata *fd,GuardRecord &guard,JumpTable *jump);
public:
  JumpBasic(JumpTable *jt) : JumpModel(jt) { jrange = (JumpValuesRange *)0; }   
  const PathMeld &getPathMeld(void) const { return pathMeld; }      
  const JumpValuesRange *getValueRange(void) const { return jrange; }   
  virtual ~JumpBasic(void);
  virtual bool isOverride(void) const { return false; }
  virtual int4 getTableSize(void) const { return jrange->getSize(); }
  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize);
  virtual void buildAddresses(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable,vector<LoadTable> *loadpoints) const;
  virtual void findUnnormalized(uint4 maxaddsub,uint4 maxleftright,uint4 maxext);
  virtual void buildLabels(Funcdata *fd,vector<Address> &addresstable,vector<uintb> &label,const JumpModel *orig) const;
  virtual Varnode *foldInNormalization(Funcdata *fd,PcodeOp *indop);
  virtual bool foldInGuards(Funcdata *fd,JumpTable *jump);
  virtual bool sanityCheck(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable);
  virtual JumpModel *clone(JumpTable *jt) const;
  virtual void clear(void);
};

class JumpBasic2 : public JumpBasic {
  Varnode *extravn;     
  PathMeld origPathMeld;    
  bool checkNormalDominance(void) const;
  virtual bool foldInOneGuard(Funcdata *fd,GuardRecord &guard,JumpTable *jump);
public:
  JumpBasic2(JumpTable *jt) : JumpBasic(jt) {}  
  void initializeStart(const PathMeld &pathMeld);   
  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize);
  virtual void findUnnormalized(uint4 maxaddsub,uint4 maxleftright,uint4 maxext);
  virtual JumpModel *clone(JumpTable *jt) const;
  virtual void clear(void);
};

class JumpBasicOverride : public JumpBasic {
  set<Address> adset;       
  vector<uintb> values;     
  vector<Address> addrtable;    
  uintb startingvalue;      
  Address normaddress;      
  uint8 hash;           
  bool istrivial;       
  int4 findStartOp(Varnode *vn);
  int4 trialNorm(Funcdata *fd,Varnode *trialvn,uint4 tolerance);
  void setupTrivial(void);
  Varnode *findLikelyNorm(void);
  void clearCopySpecific(void);
public:
  JumpBasicOverride(JumpTable *jt);     
  void setAddresses(const vector<Address> &adtable);    
  void setNorm(const Address &addr,uintb h) { normaddress = addr; hash = h; }   
  void setStartingValue(uintb val) { startingvalue = val; }     
  virtual bool isOverride(void) const { return true; }
  virtual int4 getTableSize(void) const { return addrtable.size(); }
  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize);
  virtual void buildAddresses(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable,vector<LoadTable> *loadpoints) const;
  // findUnnormalized inherited from JumpBasic
  virtual void buildLabels(Funcdata *fd,vector<Address> &addresstable,vector<uintb> &label,const JumpModel *orig) const;
  // foldInNormalization inherited from JumpBasic
  virtual bool foldInGuards(Funcdata *fd,JumpTable *jump) { return false; }
  virtual bool sanityCheck(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable) { return true; }
  virtual JumpModel *clone(JumpTable *jt) const;
  virtual void clear(void);
  virtual void saveXml(ostream &s) const;
  virtual void restoreXml(const Element *el,Architecture *glb);
};

class JumpAssistOp;

class JumpAssisted : public JumpModel {
  PcodeOp *assistOp;        
  JumpAssistOp *userop;     
  int4 sizeIndices;     
  Varnode *switchvn;        
public:
  JumpAssisted(JumpTable *jt) : JumpModel(jt) { assistOp = (PcodeOp *)0; switchvn = (Varnode *)0; sizeIndices=0; }  
//  virtual ~JumpAssisted(void);
  virtual bool isOverride(void) const { return false; }
  virtual int4 getTableSize(void) const { return sizeIndices+1; }
  virtual bool recoverModel(Funcdata *fd,PcodeOp *indop,uint4 matchsize,uint4 maxtablesize);
  virtual void buildAddresses(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable,vector<LoadTable> *loadpoints) const;
  virtual void findUnnormalized(uint4 maxaddsub,uint4 maxleftright,uint4 maxext) {}
  virtual void buildLabels(Funcdata *fd,vector<Address> &addresstable,vector<uintb> &label,const JumpModel *orig) const;
  virtual Varnode *foldInNormalization(Funcdata *fd,PcodeOp *indop);
  virtual bool foldInGuards(Funcdata *fd,JumpTable *jump);
  virtual bool sanityCheck(Funcdata *fd,PcodeOp *indop,vector<Address> &addresstable) { return true; }
  virtual JumpModel *clone(JumpTable *jt) const;
  virtual void clear(void) { assistOp = (PcodeOp *)0; switchvn = (Varnode *)0; }
};

class JumpTable {
  struct IndexPair {
    int4 blockPosition;             
    int4 addressIndex;              
    IndexPair(int4 pos,int4 index) { blockPosition = pos; addressIndex = index; }   
    bool operator<(const IndexPair &op2) const; 
    static bool compareByPosition(const IndexPair &op1,const IndexPair &op2);   
  };
  Architecture *glb;        
  JumpModel *jmodel;        
  JumpModel *origmodel;     
  vector<Address> addresstable; 
  vector<IndexPair> block2addr; 
  vector<uintb> label;      
  vector<LoadTable> loadpoints; 
  Address opaddress;        
  PcodeOp *indirect;        
  uintb switchVarConsume;   
  int4 defaultBlock;        
  int4 lastBlock;       
  uint4 maxtablesize;       
  uint4 maxaddsub;      
  uint4 maxleftright;       
  uint4 maxext;         
  int4 recoverystage;       
  bool collectloads;        
  void recoverModel(Funcdata *fd);  
  void trivialSwitchOver(void); 
  void sanityCheck(Funcdata *fd);   
  int4 block2Position(const FlowBlock *bl) const;   
  static bool isReachable(PcodeOp *op); 
public:
  JumpTable(Architecture *g,Address ad=Address());  
  JumpTable(const JumpTable *op2);          
  ~JumpTable(void);                 
  bool isRecovered(void) const { return !addresstable.empty(); }    
  bool isLabelled(void) const { return !label.empty(); }        
  bool isOverride(void) const;              
  bool isPossibleMultistage(void) const { return (addresstable.size()==1); }    
  int4 getStage(void) const { return recoverystage; }   
  int4 numEntries(void) const { return addresstable.size(); }   
  uintb getSwitchVarConsume(void) const { return switchVarConsume; }    
  int4 getDefaultBlock(void) const { return defaultBlock; } 
  const Address &getOpAddress(void) const { return opaddress; } 
  PcodeOp *getIndirectOp(void) const { return indirect; }   
  void setIndirectOp(PcodeOp *ind) { opaddress = ind->getAddr(); indirect = ind; }  
  void setMaxTableSize(uint4 val) { maxtablesize = val; }   
  void setNormMax(uint4 maddsub,uint4 mleftright,uint4 mext) {
    maxaddsub = maddsub; maxleftright = mleftright; maxext = mext; }    
  void setOverride(const vector<Address> &addrtable,const Address &naddr,uintb h,uintb sv);
  int4 numIndicesByBlock(const FlowBlock *bl) const;
  int4 getIndexByBlock(const FlowBlock *bl,int4 i) const;
  Address getAddressByIndex(int4 i) const { return addresstable[i]; }   
  void setLastAsMostCommon(void);       
  void setDefaultBlock(int4 bl) { defaultBlock = bl; }      
  void setLoadCollect(bool val) { collectloads = val; }     
  void addBlockToSwitch(BlockBasic *bl,uintb lab);      
  void switchOver(const FlowInfo &flow);                
  uintb getLabelByIndex(int4 index) const { return label[index]; }  
  void foldInNormalization(Funcdata *fd);       
  bool foldInGuards(Funcdata *fd) { return jmodel->foldInGuards(fd,this); } 
  void recoverAddresses(Funcdata *fd);      
  void recoverMultistage(Funcdata *fd);     
  bool recoverLabels(Funcdata *fd);     
  bool checkForMultistage(Funcdata *fd);    
  void clear(void);             
  void saveXml(ostream &s) const;       
  void restoreXml(const Element *el);       
};  

inline bool JumpTable::IndexPair::operator<(const IndexPair &op2) const

{
  if (blockPosition != op2.blockPosition) return (blockPosition < op2.blockPosition);
  return (addressIndex < op2.addressIndex);
}

inline bool JumpTable::IndexPair::compareByPosition(const IndexPair &op1,const IndexPair &op2)

{
  return (op1.blockPosition < op2.blockPosition);
}

#endif