Ghidra Decompiler Analysis Engine
rangeutil.hh
Go to the documentation of this file.
1 /* ###
2  * IP: GHIDRA
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
18 #ifndef __RANGEUTIL__
19 #define __RANGEUTIL__
20 
21 #include "op.hh"
22 
48 class CircleRange {
49  uintb left;
50  uintb right;
51  uintb mask;
52  bool isempty;
53  int4 step;
54  static const char arrange[];
55  void normalize(void);
56  void complement(void);
57  bool convertToBoolean(void);
58  static bool newStride(uintb mask,int4 step,int4 oldStep,uint4 rem,uintb &myleft,uintb &myright);
59  static bool newDomain(uintb newMask,int4 newStep,uintb &myleft,uintb &myright);
60  static char encodeRangeOverlaps(uintb op1left,uintb op1right,uintb op2left,uintb op2right);
61 public:
62  CircleRange(void) { isempty=true; }
63  CircleRange(uintb lft,uintb rgt,int4 size,int4 stp);
64  CircleRange(bool val);
65  CircleRange(uintb val,int4 size);
66  void setRange(uintb lft,uintb rgt,int4 size,int4 step);
67  void setRange(uintb val,int4 size);
68  void setFull(int4 size);
69  bool isEmpty(void) const { return isempty; }
70  bool isFull(void) const { return ((!isempty) && (step == 1) && (left == right)); }
71  bool isSingle(void) const { return (!isempty) && (right == ((left + step)& mask)); }
72  uintb getMin(void) const { return left; }
73  uintb getMax(void) const { return (right-step)&mask; }
74  uintb getEnd(void) const { return right; }
75  uintb getMask(void) const { return mask; }
76  uintb getSize(void) const;
77  int4 getStep(void) const { return step; }
78  int4 getMaxInfo(void) const;
79  bool operator==(const CircleRange &op2) const;
80  bool getNext(uintb &val) const { val = (val+step)&mask; return (val!=right); }
81  bool contains(const CircleRange &op2) const;
82  bool contains(uintb val) const;
83  int4 intersect(const CircleRange &op2);
84  bool setNZMask(uintb nzmask,int4 size);
85  int4 circleUnion(const CircleRange &op2);
86  bool minimalContainer(const CircleRange &op2,int4 maxStep);
87  int4 invert(void);
88  void setStride(int4 newStep,uintb rem);
89  bool pullBackUnary(OpCode opc,int4 inSize,int4 outSize);
90  bool pullBackBinary(OpCode opc,uintb val,int4 slot,int4 inSize,int4 outSize);
91  Varnode *pullBack(PcodeOp *op,Varnode **constMarkup,bool usenzmask);
92  bool pushForwardUnary(OpCode opc,const CircleRange &in1,int4 inSize,int4 outSize);
93  bool pushForwardBinary(OpCode opc,const CircleRange &in1,const CircleRange &in2,int4 inSize,int4 outSize,int4 maxStep);
94  bool pushForwardTrinary(OpCode opc,const CircleRange &in1,const CircleRange &in2,const CircleRange &in3,
95  int4 inSize,int4 outSize,int4 maxStep);
96  void widen(const CircleRange &op2,bool leftIsStable);
97  int4 translate2Op(OpCode &opc,uintb &c,int4 &cslot) const;
98  void printRaw(ostream &s) const;
99 };
100 
101 class Partition; // Forward declaration
102 class Widener; // Forward declaration
103 
111 class ValueSet {
112 public:
113  static const int4 MAX_STEP;
114  class Equation {
120  friend class ValueSet;
121  int4 slot;
122  int4 typeCode;
123  CircleRange range;
124  public:
125  Equation(int4 s,int4 tc,const CircleRange &rng) { slot=s; typeCode = tc; range = rng; }
126  };
127 private:
128  friend class ValueSetSolver;
129  int4 typeCode;
130  int4 numParams;
131  int4 count;
132  OpCode opCode;
133  bool leftIsStable;
134  bool rightIsStable;
135  Varnode *vn;
136  CircleRange range;
137  vector<Equation> equations;
138  Partition *partHead;
139  ValueSet *next;
140  bool doesEquationApply(int4 num,int4 slot) const;
141  void setFull(void) { range.setFull(vn->getSize()); typeCode = 0; }
142  void setVarnode(Varnode *v,int4 tCode);
143  void addEquation(int4 slot,int4 type,const CircleRange &constraint);
144  void addLandmark(int4 type,const CircleRange &constraint) { addEquation(numParams,type,constraint); }
145  bool computeTypeCode(void);
146  bool iterate(Widener &widener);
147 public:
148  int4 getCount(void) const { return count; }
149  const CircleRange *getLandMark(void) const;
150  int4 getTypeCode(void) const { return typeCode; }
151  Varnode *getVarnode(void) const { return vn; }
152  const CircleRange &getRange(void) const { return range; }
153  bool isLeftStable(void) const { return leftIsStable; }
154  bool isRightStable(void) const { return rightIsStable; }
155  void printRaw(ostream &s) const;
156 };
157 
159 class Partition {
160  friend class ValueSetSolver;
161  ValueSet *startNode;
162  ValueSet *stopNode;
163  bool isDirty;
164 public:
165  Partition(void) {
166  startNode = (ValueSet *)0; stopNode = (ValueSet *)0; isDirty = false;
167  }
168 };
169 
176 class ValueSetRead {
177  friend class ValueSetSolver;
178  int4 typeCode;
179  int4 slot;
180  PcodeOp *op;
181  CircleRange range;
182  CircleRange equationConstraint;
183  int4 equationTypeCode;
184  bool leftIsStable;
185  bool rightIsStable;
186  void setPcodeOp(PcodeOp *o,int4 slt);
187  void addEquation(int4 slt,int4 type,const CircleRange &constraint);
188 public:
189  int4 getTypeCode(void) const { return typeCode; }
190  const CircleRange &getRange(void) const { return range; }
191  bool isLeftStable(void) const { return leftIsStable; }
192  bool isRightStable(void) const { return rightIsStable; }
193  void compute(void);
194  void printRaw(ostream &s) const;
195 };
196 
202 class Widener {
203 public:
204  virtual ~Widener(void) {}
205 
210  virtual int4 determineIterationReset(const ValueSet &valueSet)=0;
211 
216  virtual bool checkFreeze(const ValueSet &valueSet)=0;
217 
226  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange)=0;
227 };
228 
234 class WidenerFull : public Widener {
235  int4 widenIteration;
236  int4 fullIteration;
237 public:
238  WidenerFull(void) { widenIteration = 2; fullIteration = 5; }
239  WidenerFull(int4 wide,int4 full) { widenIteration = wide; fullIteration = full; }
240  virtual int4 determineIterationReset(const ValueSet &valueSet);
241  virtual bool checkFreeze(const ValueSet &valueSet);
242  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange);
243 };
244 
252 class WidenerNone : public Widener {
253  int4 freezeIteration;
254 public:
255  WidenerNone(void) { freezeIteration = 3; }
256  virtual int4 determineIterationReset(const ValueSet &valueSet);
257  virtual bool checkFreeze(const ValueSet &valueSet);
258  virtual bool doWidening(const ValueSet &valueSet,CircleRange &range,const CircleRange &newRange);
259 };
260 
272 class ValueSetSolver {
279  class ValueSetEdge {
280  const vector<ValueSet *> *rootEdges;
281  int4 rootPos;
282  Varnode *vn;
283  list<PcodeOp *>::const_iterator iter;
284  public:
285  ValueSetEdge(ValueSet *node,const vector<ValueSet *> &roots);
286  ValueSet *getNext(void);
287  };
288 
289  list<ValueSet> valueNodes;
290  map<SeqNum,ValueSetRead> readNodes;
291  Partition orderPartition;
292  list<Partition> recordStorage;
293  vector<ValueSet *> rootNodes;
294  vector<ValueSet *> nodeStack;
295  int4 depthFirstIndex;
296  int4 numIterations;
297  int4 maxIterations;
298  void newValueSet(Varnode *vn,int4 tCode);
299  static void partitionPrepend(ValueSet *vertex,Partition &part);
300  static void partitionPrepend(const Partition &head,Partition &part);
301  void partitionSurround(Partition &part);
302  void component(ValueSet *vertex,Partition &part);
303  int4 visit(ValueSet *vertex,Partition &part);
304  void establishTopologicalOrder(void);
305  void generateTrueEquation(Varnode *vn,PcodeOp *op,int4 slot,int4 type,const CircleRange &range);
306  void generateFalseEquation(Varnode *vn,PcodeOp *op,int4 slot,int4 type,const CircleRange &range);
307  void applyConstraints(Varnode *vn,int4 type,const CircleRange &range,PcodeOp *cbranch);
308  void constraintsFromPath(int4 type,CircleRange &lift,Varnode *startVn,Varnode *endVn,PcodeOp *cbranch);
309  void constraintsFromCBranch(PcodeOp *cbranch);
310  void generateConstraints(const vector<Varnode *> &worklist,const vector<PcodeOp *> &reads);
311  bool checkRelativeConstant(Varnode *vn,int4 &typeCode,uintb &value) const;
312  void generateRelativeConstraint(PcodeOp *compOp,PcodeOp *cbranch);
313 public:
314  void establishValueSets(const vector<Varnode *> &sinks,const vector<PcodeOp *> &reads,Varnode *stackReg,bool indirectAsCopy);
315  int4 getNumIterations(void) const { return numIterations; }
316  void solve(int4 max,Widener &widener);
317  list<ValueSet>::const_iterator beginValueSets(void) const { return valueNodes.begin(); }
318  list<ValueSet>::const_iterator endValueSets(void) const { return valueNodes.end(); }
319  map<SeqNum,ValueSetRead>::const_iterator beginValueSetReads(void) const { return readNodes.begin(); }
320  map<SeqNum,ValueSetRead>::const_iterator endValueSetReads(void) const { return readNodes.end(); }
321  const ValueSetRead &getValueSetRead(const SeqNum &seq) { return (*readNodes.find(seq)).second; }
322 #ifdef CPUI_DEBUG
323  void dumpValueSets(ostream &s) const;
324 #endif
325 };
326 
329 inline bool CircleRange::operator==(const CircleRange &op2) const
330 
331 {
332  if (isempty != op2.isempty) return false;
333  if (isempty) return true;
334  return (left == op2.left) && (right == op2.right) && (mask == op2.mask) && (step == op2.step);
335 }
336 
356 inline char CircleRange::encodeRangeOverlaps(uintb op1left, uintb op1right, uintb op2left, uintb op2right)
357 
358 {
359  int4 val = (op1left <= op1right) ? 0x20 : 0;
360  val |= (op1left <= op2left) ? 0x10 : 0;
361  val |= (op1left <= op2right) ? 0x8 : 0;
362  val |= (op1right <= op2left) ? 4 : 0;
363  val |= (op1right <= op2right) ? 2 : 0;
364  val |= (op2left <= op2right) ? 1 : 0;
365  return arrange[val];
366 }
367 
373 inline bool ValueSet::doesEquationApply(int4 num,int4 slot) const
374 
375 {
376  if (num < equations.size()) {
377  if (equations[num].slot == slot) {
378  if (equations[num].typeCode == typeCode)
379  return true;
380  }
381  }
382  return false;
383 }
384 
387 inline void ValueSetSolver::partitionPrepend(ValueSet *vertex,Partition &part)
388 
389 {
390  vertex->next = part.startNode; // Attach new vertex to beginning of list
391  part.startNode = vertex; // Change the first value set to be the new vertex
392  if (part.stopNode == (ValueSet *)0)
393  part.stopNode = vertex;
394 }
395 
398 inline void ValueSetSolver::partitionPrepend(const Partition &head,Partition &part)
399 
400 {
401  head.stopNode->next = part.startNode;
402  part.startNode = head.startNode;
403  if (part.stopNode == (ValueSet *)0)
404  part.stopNode = head.stopNode;
405 }
406 
407 #endif
ValueSet::Equation
An external that can be applied to a ValueSet.
Definition: rangeutil.hh:119
CircleRange::setNZMask
bool setNZMask(uintb nzmask, int4 size)
Set the range based on a putative mask.
Definition: rangeutil.cc:670
CircleRange::getSize
uintb getSize(void) const
Get the size of this range.
Definition: rangeutil.cc:254
Widener::checkFreeze
virtual bool checkFreeze(const ValueSet &valueSet)=0
Check if the given value set has been frozen for the remainder of the iteration process.
ValueSetRead
A special form of ValueSet associated with the read point of a Varnode.
Definition: rangeutil.hh:176
CircleRange::setFull
void setFull(int4 size)
Set a completely full range.
Definition: rangeutil.cc:243
SeqNum
A class for uniquely labelling and comparing PcodeOps.
Definition: address.hh:111
ValueSet::MAX_STEP
static const int4 MAX_STEP
Definition: rangeutil.hh:113
CircleRange::invert
int4 invert(void)
Convert to complementary range.
Definition: rangeutil.cc:531
ValueSet::getLandMark
const CircleRange * getLandMark(void) const
Get any landmark range.
Definition: rangeutil.cc:1728
Widener::doWidening
virtual bool doWidening(const ValueSet &valueSet, CircleRange &range, const CircleRange &newRange)=0
For an iteration that isn't stabilizing attempt to widen the given ValueSet.
CircleRange::contains
bool contains(const CircleRange &op2) const
Check containment of another range in this.
Definition: rangeutil.cc:299
Partition
A range of nodes (within the weak topological ordering) that are iterated together.
Definition: rangeutil.hh:159
WidenerNone::checkFreeze
virtual bool checkFreeze(const ValueSet &valueSet)
Check if the given value set has been frozen for the remainder of the iteration process.
Definition: rangeutil.cc:1874
ValueSetSolver::solve
void solve(int4 max, Widener &widener)
Iterate the ValueSet system until it stabilizes.
Definition: rangeutil.cc:2510
WidenerNone::determineIterationReset
virtual int4 determineIterationReset(const ValueSet &valueSet)
Upon entering a fresh partition, determine how the given ValueSet count should be reset.
Definition: rangeutil.cc:1866
CircleRange::minimalContainer
bool minimalContainer(const CircleRange &op2, int4 maxStep)
Construct minimal range that contains both this and another range.
Definition: rangeutil.cc:452
CircleRange::pullBackBinary
bool pullBackBinary(OpCode opc, uintb val, int4 slot, int4 inSize, int4 outSize)
Pull-back this thru binary operator.
Definition: rangeutil.cc:797
CircleRange::pullBackUnary
bool pullBackUnary(OpCode opc, int4 inSize, int4 outSize)
Pull-back this through the given unary operator.
Definition: rangeutil.cc:726
WidenerFull::doWidening
virtual bool doWidening(const ValueSet &valueSet, CircleRange &range, const CircleRange &newRange)
For an iteration that isn't stabilizing attempt to widen the given ValueSet.
Definition: rangeutil.cc:1833
CircleRange::CircleRange
CircleRange(uintb lft, uintb rgt, int4 size, int4 stp)
Construct given specific boundaries.
Definition: rangeutil.cc:177
Widener
Class holding a particular widening strategy for the ValueSetSolver iteration algorithm.
Definition: rangeutil.hh:202
PcodeOp
Lowest level operation of the p-code language.
Definition: op.hh:58
CircleRange::pushForwardTrinary
bool pushForwardTrinary(OpCode opc, const CircleRange &in1, const CircleRange &in2, const CircleRange &in3, int4 inSize, int4 outSize, int4 maxStep)
Push this range forward through a trinary operation.
Definition: rangeutil.cc:1367
CircleRange::setStride
void setStride(int4 newStep, uintb rem)
Set a new step on this range.
Definition: rangeutil.cc:705
ValueSetRead::printRaw
void printRaw(ostream &s) const
Write a text description of to the given stream.
Definition: rangeutil.cc:1807
CircleRange::pushForwardBinary
bool pushForwardBinary(OpCode opc, const CircleRange &in1, const CircleRange &in2, int4 inSize, int4 outSize, int4 maxStep)
Push this range forward through a binary operation.
Definition: rangeutil.cc:1165
Varnode
A low-level variable or contiguous set of bytes described by an Address and a size.
Definition: varnode.hh:65
CircleRange::translate2Op
int4 translate2Op(OpCode &opc, uintb &c, int4 &cslot) const
Translate range to a comparison op.
Definition: rangeutil.cc:1410
ValueSet
A range of values attached to a Varnode within a data-flow subsystem.
Definition: rangeutil.hh:111
WidenerNone::doWidening
virtual bool doWidening(const ValueSet &valueSet, CircleRange &range, const CircleRange &newRange)
For an iteration that isn't stabilizing attempt to widen the given ValueSet.
Definition: rangeutil.cc:1882
WidenerFull
Class for doing normal widening.
Definition: rangeutil.hh:234
CircleRange::widen
void widen(const CircleRange &op2, bool leftIsStable)
Widen the unstable bound to match containing range.
Definition: rangeutil.cc:1381
CircleRange::setRange
void setRange(uintb lft, uintb rgt, int4 size, int4 step)
Set directly to a specific range.
Definition: rangeutil.cc:217
ValueSetSolver::establishValueSets
void establishValueSets(const vector< Varnode * > &sinks, const vector< PcodeOp * > &reads, Varnode *stackReg, bool indirectAsCopy)
Build value sets for a data-flow system.
Definition: rangeutil.cc:2402
CircleRange::pullBack
Varnode * pullBack(PcodeOp *op, Varnode **constMarkup, bool usenzmask)
Pull-back this range through given PcodeOp.
Definition: rangeutil.cc:1012
WidenerFull::determineIterationReset
virtual int4 determineIterationReset(const ValueSet &valueSet)
Upon entering a fresh partition, determine how the given ValueSet count should be reset.
Definition: rangeutil.cc:1819
op.hh
The PcodeOp and PcodeOpBank classes.
CircleRange::operator==
bool operator==(const CircleRange &op2) const
Equals operator.
Definition: rangeutil.hh:329
CircleRange
A class for manipulating integer value ranges.
Definition: rangeutil.hh:48
CircleRange::circleUnion
int4 circleUnion(const CircleRange &op2)
Union two ranges.
Definition: rangeutil.cc:358
OpCode
OpCode
The op-code defining a specific p-code operation (PcodeOp)
Definition: opcodes.hh:35
ValueSetRead::compute
void compute(void)
Compute this value set.
Definition: rangeutil.cc:1790
Widener::determineIterationReset
virtual int4 determineIterationReset(const ValueSet &valueSet)=0
Upon entering a fresh partition, determine how the given ValueSet count should be reset.
CircleRange::getMaxInfo
int4 getMaxInfo(void) const
Get maximum information content of range.
Definition: rangeutil.cc:278
CircleRange::pushForwardUnary
bool pushForwardUnary(OpCode opc, const CircleRange &in1, int4 inSize, int4 outSize)
Push-forward thru given unary operator.
Definition: rangeutil.cc:1083
CircleRange::intersect
int4 intersect(const CircleRange &op2)
Intersect this with another range.
Definition: rangeutil.cc:547
WidenerFull::checkFreeze
virtual bool checkFreeze(const ValueSet &valueSet)
Check if the given value set has been frozen for the remainder of the iteration process.
Definition: rangeutil.cc:1827
WidenerNone
Class for freezing value sets at a specific iteration (to accelerate convergence)
Definition: rangeutil.hh:252
ValueSet::printRaw
void printRaw(ostream &s) const
Write a text description of to the given stream.
Definition: rangeutil.cc:1742
CircleRange::printRaw
void printRaw(ostream &s) const
Write a text representation of this to stream.
Definition: rangeutil.cc:1456
ValueSetSolver
Class that determines a ValueSet for each Varnode in a data-flow system.
Definition: rangeutil.hh:272
Generated by   doxygen 1.8.17