rangeutil.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 __RANGEUTIL__
#define __RANGEUTIL__

#include "op.hh"

class CircleRange {
  uintb left;           
  uintb right;          
  uintb mask;           
  bool isempty;         
  int4 step;            
  static const char arrange[];  
  void normalize(void);     
  void complement(void);    
  bool convertToBoolean(void);  
  static bool newStride(uintb mask,int4 step,int4 oldStep,uint4 rem,uintb &myleft,uintb &myright);
  static bool newDomain(uintb newMask,int4 newStep,uintb &myleft,uintb &myright);
  static char encodeRangeOverlaps(uintb op1left,uintb op1right,uintb op2left,uintb op2right);   
public:
  CircleRange(void) { isempty=true; }       
  CircleRange(uintb lft,uintb rgt,int4 size,int4 stp);  
  CircleRange(bool val);            
  CircleRange(uintb val,int4 size);     
  void setRange(uintb lft,uintb rgt,int4 size,int4 step);   
  void setRange(uintb val,int4 size);       
  void setFull(int4 size);          
  bool isEmpty(void) const { return isempty; }  
  bool isFull(void) const { return ((!isempty) && (step == 1) && (left == right)); }    
  bool isSingle(void) const { return (!isempty) && (right == ((left + step)& mask)); }  
  uintb getMin(void) const { return left; } 
  uintb getMax(void) const { return (right-step)&mask; }    
  uintb getEnd(void) const { return right; }    
  uintb getMask(void) const { return mask; }    
  uintb getSize(void) const;            
  int4 getStep(void) const { return step; } 
  int4 getMaxInfo(void) const;          
  bool operator==(const CircleRange &op2) const;    
  bool getNext(uintb &val) const { val = (val+step)&mask; return (val!=right); }    
  bool contains(const CircleRange &op2) const;  
  bool contains(uintb val) const;       
  int4 intersect(const CircleRange &op2);   
  bool setNZMask(uintb nzmask,int4 size);   
  int4 circleUnion(const CircleRange &op2); 
  bool minimalContainer(const CircleRange &op2,int4 maxStep);   
  int4 invert(void);                
  void setStride(int4 newStep,uintb rem);   
  bool pullBackUnary(OpCode opc,int4 inSize,int4 outSize);  
  bool pullBackBinary(OpCode opc,uintb val,int4 slot,int4 inSize,int4 outSize); 
  Varnode *pullBack(PcodeOp *op,Varnode **constMarkup,bool usenzmask);  
  bool pushForwardUnary(OpCode opc,const CircleRange &in1,int4 inSize,int4 outSize);    
  bool pushForwardBinary(OpCode opc,const CircleRange &in1,const CircleRange &in2,int4 inSize,int4 outSize,int4 maxStep);
  bool pushForwardTrinary(OpCode opc,const CircleRange &in1,const CircleRange &in2,const CircleRange &in3,
              int4 inSize,int4 outSize,int4 maxStep);
  void widen(const CircleRange &op2,bool leftIsStable); 
  int4 translate2Op(OpCode &opc,uintb &c,int4 &cslot) const;    
  void printRaw(ostream &s) const;      
};

class Partition;        // Forward declaration
class Widener;          // Forward declaration

class ValueSet {
public:
  static const int4 MAX_STEP;   
  class Equation {
    friend class ValueSet;
    int4 slot;          
    int4 typeCode;      
    CircleRange range;      
  public:
    Equation(int4 s,int4 tc,const CircleRange &rng) { slot=s; typeCode = tc; range = rng; } 
  };
private:
  friend class ValueSetSolver;
  int4 typeCode;    
  int4 numParams;   
  int4 count;       
  OpCode opCode;    
  bool leftIsStable;    
  bool rightIsStable;   
  Varnode *vn;      
  CircleRange range;    
  vector<Equation> equations;   
  Partition *partHead;  
  ValueSet *next;   
  bool doesEquationApply(int4 num,int4 slot) const; 
  void setFull(void) { range.setFull(vn->getSize()); typeCode = 0; }    
  void setVarnode(Varnode *v,int4 tCode);   
  void addEquation(int4 slot,int4 type,const CircleRange &constraint);  
  void addLandmark(int4 type,const CircleRange &constraint) { addEquation(numParams,type,constraint); } 
  bool computeTypeCode(void);   
  bool iterate(Widener &widener);   
public:
  int4 getCount(void) const { return count; }       
  const CircleRange *getLandMark(void) const;       
  int4 getTypeCode(void) const { return typeCode; } 
  Varnode *getVarnode(void) const { return vn; }    
  const CircleRange &getRange(void) const { return range; } 
  bool isLeftStable(void) const { return leftIsStable; }    
  bool isRightStable(void) const { return rightIsStable; }  
  void printRaw(ostream &s) const;      
};

class Partition {
  friend class ValueSetSolver;
  ValueSet *startNode;      
  ValueSet *stopNode;       
  bool isDirty;         
public:
  Partition(void) {
    startNode = (ValueSet *)0; stopNode = (ValueSet *)0; isDirty = false;
  }             
};

class ValueSetRead {
  friend class ValueSetSolver;
  int4 typeCode;    
  int4 slot;        
  PcodeOp *op;      
  CircleRange range;    
  CircleRange equationConstraint;   
  int4 equationTypeCode;    
  bool leftIsStable;    
  bool rightIsStable;   
  void setPcodeOp(PcodeOp *o,int4 slt); 
  void addEquation(int4 slt,int4 type,const CircleRange &constraint);   
public:
  int4 getTypeCode(void) const { return typeCode; } 
  const CircleRange &getRange(void) const { return range; } 
  bool isLeftStable(void) const { return leftIsStable; }    
  bool isRightStable(void) const { return rightIsStable; }  
  void compute(void);           
  void printRaw(ostream &s) const;  
};

class Widener {
public:
  virtual ~Widener(void) {} 

  virtual int4 determineIterationReset(const ValueSet &valueSet)=0;

  virtual bool checkFreeze(const ValueSet &valueSet)=0;

  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange)=0;
};

class WidenerFull : public Widener {
  int4 widenIteration;      
  int4 fullIteration;       
public:
  WidenerFull(void) { widenIteration = 2; fullIteration = 5; }  
  WidenerFull(int4 wide,int4 full) { widenIteration = wide; fullIteration = full; } 
  virtual int4 determineIterationReset(const ValueSet &valueSet);
  virtual bool checkFreeze(const ValueSet &valueSet);
  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange);
};

class WidenerNone : public Widener {
  int4 freezeIteration;     
public:
  WidenerNone(void) { freezeIteration = 3; }
  virtual int4 determineIterationReset(const ValueSet &valueSet);
  virtual bool checkFreeze(const ValueSet &valueSet);
  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange);
};

class ValueSetSolver {
  class ValueSetEdge {
    const vector<ValueSet *> *rootEdges;        
    int4 rootPos;                   
    Varnode *vn;                    
    list<PcodeOp *>::const_iterator iter;       
  public:
    ValueSetEdge(ValueSet *node,const vector<ValueSet *> &roots);
    ValueSet *getNext(void);
  };

  list<ValueSet> valueNodes;        
  map<SeqNum,ValueSetRead> readNodes;   
  Partition orderPartition;     
  list<Partition> recordStorage;    
  vector<ValueSet *> rootNodes;     
  vector<ValueSet *> nodeStack;     
  int4 depthFirstIndex;         
  int4 numIterations;           
  int4 maxIterations;           
  void newValueSet(Varnode *vn,int4 tCode);     
  static void partitionPrepend(ValueSet *vertex,Partition &part);   
  static void partitionPrepend(const Partition &head,Partition &part);  
  void partitionSurround(Partition &part);              
  void component(ValueSet *vertex,Partition &part);     
  int4 visit(ValueSet *vertex,Partition &part);         
  void establishTopologicalOrder(void);             
  void generateTrueEquation(Varnode *vn,PcodeOp *op,int4 slot,int4 type,const CircleRange &range);
  void generateFalseEquation(Varnode *vn,PcodeOp *op,int4 slot,int4 type,const CircleRange &range);
  void applyConstraints(Varnode *vn,int4 type,const CircleRange &range,PcodeOp *cbranch);
  void constraintsFromPath(int4 type,CircleRange &lift,Varnode *startVn,Varnode *endVn,PcodeOp *cbranch);
  void constraintsFromCBranch(PcodeOp *cbranch);        
  void generateConstraints(const vector<Varnode *> &worklist,const vector<PcodeOp *> &reads);   
  bool checkRelativeConstant(Varnode *vn,int4 &typeCode,uintb &value) const;    
  void generateRelativeConstraint(PcodeOp *compOp,PcodeOp *cbranch);    
public:
  void establishValueSets(const vector<Varnode *> &sinks,const vector<PcodeOp *> &reads,Varnode *stackReg,bool indirectAsCopy);
  int4 getNumIterations(void) const { return numIterations; }   
  void solve(int4 max,Widener &widener);            
  list<ValueSet>::const_iterator beginValueSets(void) const { return valueNodes.begin(); }  
  list<ValueSet>::const_iterator endValueSets(void) const { return valueNodes.end(); }  
  map<SeqNum,ValueSetRead>::const_iterator beginValueSetReads(void) const { return readNodes.begin(); } 
  map<SeqNum,ValueSetRead>::const_iterator endValueSetReads(void) const { return readNodes.end(); } 
  const ValueSetRead &getValueSetRead(const SeqNum &seq) { return (*readNodes.find(seq)).second; }  
#ifdef CPUI_DEBUG
  void dumpValueSets(ostream &s) const;
#endif
};

inline bool CircleRange::operator==(const CircleRange &op2) const

{
  if (isempty != op2.isempty) return false;
  if (isempty) return true;
  return (left == op2.left) && (right == op2.right) && (mask == op2.mask) && (step == op2.step);
}

inline char CircleRange::encodeRangeOverlaps(uintb op1left, uintb op1right, uintb op2left, uintb op2right)

{
  int4 val = (op1left <= op1right) ? 0x20 : 0;
  val |= (op1left <= op2left) ? 0x10 : 0;
  val |= (op1left <= op2right) ? 0x8 : 0;
  val |= (op1right <= op2left) ? 4 : 0;
  val |= (op1right <= op2right) ? 2 : 0;
  val |= (op2left <= op2right) ? 1 : 0;
  return arrange[val];
}

inline bool ValueSet::doesEquationApply(int4 num,int4 slot) const

{
  if (num < equations.size()) {
    if (equations[num].slot == slot) {
      if (equations[num].typeCode == typeCode)
    return true;
    }
  }
  return false;
}

inline void ValueSetSolver::partitionPrepend(ValueSet *vertex,Partition &part)

{
  vertex->next = part.startNode;    // Attach new vertex to beginning of list
  part.startNode = vertex;      // Change the first value set to be the new vertex
  if (part.stopNode == (ValueSet *)0)
    part.stopNode = vertex;
}

inline void ValueSetSolver::partitionPrepend(const Partition &head,Partition &part)

{
  head.stopNode->next = part.startNode;
  part.startNode = head.startNode;
  if (part.stopNode == (ValueSet *)0)
    part.stopNode = head.stopNode;
}

#endif