decompiler
1.0.0
|
A class for manipulating integer value ranges. More...
#include <rangeutil.hh>
Public Member Functions | |
CircleRange (void) | |
Construct an empty range. | |
CircleRange (uintb lft, uintb rgt, int4 size, int4 stp) | |
Construct given specific boundaries. More... | |
CircleRange (bool val) | |
Construct a boolean range. More... | |
CircleRange (uintb val, int4 size) | |
Construct range with single value. More... | |
void | setRange (uintb lft, uintb rgt, int4 size, int4 step) |
Set directly to a specific range. More... | |
void | setRange (uintb val, int4 size) |
Set range with a single value. More... | |
void | setFull (int4 size) |
Set a completely full range. More... | |
bool | isEmpty (void) const |
Return true if this range is empty. | |
bool | isFull (void) const |
Return true if this contains all possible values. | |
bool | isSingle (void) const |
Return true if this contains single value. | |
uintb | getMin (void) const |
Get the left boundary of the range. | |
uintb | getMax (void) const |
Get the right-most integer contained in the range. | |
uintb | getEnd (void) const |
Get the right boundary of the range. | |
uintb | getMask (void) const |
Get the mask. | |
uintb | getSize (void) const |
Get the size of this range. More... | |
int4 | getStep (void) const |
Get the step for this range. | |
int4 | getMaxInfo (void) const |
Get maximum information content of range. More... | |
bool | operator== (const CircleRange &op2) const |
Equals operator. More... | |
bool | getNext (uintb &val) const |
Advance an integer within the range. | |
bool | contains (const CircleRange &op2) const |
Check containment of another range in this. More... | |
bool | contains (uintb val) const |
Check containment of a specific integer. More... | |
int4 | intersect (const CircleRange &op2) |
Intersect this with another range. More... | |
bool | setNZMask (uintb nzmask, int4 size) |
Set the range based on a putative mask. More... | |
int4 | circleUnion (const CircleRange &op2) |
Union two ranges. More... | |
bool | minimalContainer (const CircleRange &op2, int4 maxStep) |
Construct minimal range that contains both this and another range. More... | |
int4 | invert (void) |
Convert to complementary range. More... | |
void | setStride (int4 newStep, uintb rem) |
Set a new step on this range. More... | |
bool | pullBackUnary (OpCode opc, int4 inSize, int4 outSize) |
Pull-back this through the given unary operator. More... | |
bool | pullBackBinary (OpCode opc, uintb val, int4 slot, int4 inSize, int4 outSize) |
Pull-back this thru binary operator. More... | |
Varnode * | pullBack (PcodeOp *op, Varnode **constMarkup, bool usenzmask) |
Pull-back this range through given PcodeOp. More... | |
bool | pushForwardUnary (OpCode opc, const CircleRange &in1, int4 inSize, int4 outSize) |
Push-forward thru given unary operator. More... | |
bool | pushForwardBinary (OpCode opc, const CircleRange &in1, const CircleRange &in2, int4 inSize, int4 outSize, int4 maxStep) |
Push this range forward through a binary operation. More... | |
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. More... | |
void | widen (const CircleRange &op2, bool leftIsStable) |
Widen the unstable bound to match containing range. More... | |
int4 | translate2Op (OpCode &opc, uintb &c, int4 &cslot) const |
Translate range to a comparison op. More... | |
void | printRaw (ostream &s) const |
Write a text representation of this to stream. More... | |
Private Member Functions | |
void | normalize (void) |
Normalize the representation of full sets. More... | |
void | complement (void) |
Set this to the complement of itself. More... | |
bool | convertToBoolean (void) |
Convert this to boolean. More... | |
Static Private Member Functions | |
static bool | newStride (uintb mask, int4 step, int4 oldStep, uint4 rem, uintb &myleft, uintb &myright) |
Recalculate range based on new stride. More... | |
static bool | newDomain (uintb newMask, int4 newStep, uintb &myleft, uintb &myright) |
Make this range fit in a new domain. More... | |
static char | encodeRangeOverlaps (uintb op1left, uintb op1right, uintb op2left, uintb op2right) |
Calculate overlap code. More... | |
Private Attributes | |
uintb | left |
Left boundary of the open range [left,right) | |
uintb | right |
Right boundary of the open range [left,right) | |
uintb | mask |
Bit mask defining the size (modulus) and stop of the range. | |
bool | isempty |
true if set is empty | |
int4 | step |
Explicit step size. | |
Static Private Attributes | |
static const char | arrange [] = "gcgbegdagggggggeggggcgbggggggggcdfgggggggegdggggbgggfggggcgbegda" |
Map from raw overlaps to normalized overlap code. | |
A class for manipulating integer value ranges.
The idea is to have a representation of common sets of values that a varnode might take on in analysis so that the representation can be manipulated symbolically to some extent. The representation is a circular range (determined by a half-open interval [left,right)), over the integers mod 2^n, where mask = 2^n-1. The range can support a step, if some of the least significant bits of the mask are set to zero.
The class then can
ghidra::CircleRange::CircleRange | ( | uintb | lft, |
uintb | rgt, | ||
int4 | size, | ||
int4 | stp | ||
) |
Construct given specific boundaries.
Give specific left/right boundaries and step information. The first element in the set is given left boundary. The sequence then proceeds by the given step up to (but not including) the given right boundary. Care should be taken to make sure the remainders of the left and right boundaries modulo the step are equal.
lft | is the left boundary of the range |
rgt | is the right boundary of the range |
size | is the domain size in bytes (1,2,4,8,..) |
stp | is the desired step (1,2,4,8,..) |
References ghidra::calc_mask(), isempty, left, mask, right, and step.
ghidra::CircleRange::CircleRange | ( | bool | val | ) |
ghidra::CircleRange::CircleRange | ( | uintb | val, |
int4 | size | ||
) |
int4 ghidra::CircleRange::circleUnion | ( | const CircleRange & | op2 | ) |
Union two ranges.
Set this to the union of this and op2 as a single interval. Return 0 if the result is valid. Return 2 if the union is two pieces. If result is not zero, this is not modified.
op2 | is the range to union with |
References encodeRangeOverlaps(), isempty, isSingle(), left, mask, right, and step.
Referenced by ghidra::RuleRangeMeld::applyOp(), getNext(), and ghidra::ValueSet::iterate().
|
private |
Set this to the complement of itself.
This method only works if step is 1.
References isempty, left, and right.
Referenced by invert(), and pullBackBinary().
bool ghidra::CircleRange::contains | ( | const CircleRange & | op2 | ) | const |
Check containment of another range in this.
op2 | is the specific range to test for containment. |
References encodeRangeOverlaps(), isempty, isSingle(), left, right, and step.
Referenced by convertToBoolean(), ghidra::WidenerFull::doWidening(), getMaxInfo(), and getNext().
bool ghidra::CircleRange::contains | ( | uintb | val | ) | const |
|
private |
Convert this to boolean.
If the original range contained
References contains(), isempty, left, mask, right, and step.
Referenced by pullBackBinary(), and pullBackUnary().
|
inlinestaticprivate |
Calculate overlap code.
If two ranges are labeled [l , r) and [op2.l, op2.r), the overlap of the ranges can be characterized by listing the four boundary values in order, as the circle is traversed in a clock-wise direction. This characterization can be further normalized by starting the list at op2.l, unless op2.l is contained in the range [l, r). In which case, the list should start with l. You get the following 6 categories
Given 2 ranges, this method calculates the category code for the overlap.
op1left | is left boundary of the first range |
op1right | is the right boundary of the first range |
op2left | is the left boundary of the second range |
op2right | is the right boundary of the second range |
References arrange.
Referenced by circleUnion(), contains(), intersect(), and minimalContainer().
int4 ghidra::CircleRange::getMaxInfo | ( | void | ) | const |
Get maximum information content of range.
In this context, the information content of a value is the index (+1) of the most significant non-zero bit (of the absolute value). This routine returns the maximum information across all values in the range.
References contains(), left, mask, and right.
Referenced by getStep(), and pushForwardBinary().
uintb ghidra::CircleRange::getSize | ( | void | ) | const |
Get the size of this range.
References isempty, left, mask, right, and step.
Referenced by ghidra::JumpBasic::calcRange(), ghidra::LoadGuard::establishRange(), ghidra::LoadGuard::finalizeRange(), ghidra::JumpBasic::findSmallestNormal(), and getMask().
int4 ghidra::CircleRange::intersect | ( | const CircleRange & | op2 | ) |
Intersect this with another range.
Set this to the intersection of this and op2 as a single interval if possible. Return 0 if the result is valid Return 2 if the intersection is two pieces If result is not zero, this is not modified
op2 | is the second range |
References encodeRangeOverlaps(), isempty, left, mask, newDomain(), newStride(), right, and step.
Referenced by ghidra::RuleRangeMeld::applyOp(), ghidra::JumpBasic::calcRange(), getNext(), ghidra::ValueSet::iterate(), pullBack(), and pullBackUnary().
int4 ghidra::CircleRange::invert | ( | void | ) |
Convert to complementary range.
Convert range to its complement. The step is automatically converted to 1 first.
References complement(), and step.
Referenced by ghidra::WidenerFull::doWidening(), ghidra::ValueSetSolver::generateFalseEquation(), and getNext().
bool ghidra::CircleRange::minimalContainer | ( | const CircleRange & | op2, |
int4 | maxStep | ||
) |
Construct minimal range that contains both this and another range.
Turn this into a range that contains both the original range and the other given range. The resulting range may contain values that were in neither of the original ranges (not a strict union). But the number of added values will be minimal. This method will create a range with step if the input ranges hold single values and the distance between them is a power of 2 and less or equal than a given bound.
op2 | is the other given range to combine with this |
maxStep | is the step bound that can be induced for a container with two singles |
References encodeRangeOverlaps(), getMin(), isSingle(), left, mask, normalize(), right, and step.
Referenced by getNext(), and ghidra::ValueSet::iterate().
|
staticprivate |
Make this range fit in a new domain.
Truncate any part of the range outside of the new domain. If the original range is completely outside of the new domain, return true (empty). Step information is preserved.
newMask | is the mask for the new domain |
newStep | is the step associated with the range |
myleft | is a reference to the left edge of the range to fit |
myright | is a reference to the right edge of the range to fit |
Referenced by intersect().
|
staticprivate |
Recalculate range based on new stride.
Restrict a left/right specified range to a new stride, given the step and remainder it needs to match. This assumes the specified range is not empty.
mask | is the domain mask |
step | is the new stride |
oldStep | is the original step (always smaller) |
rem | is the given remainder to match |
myleft | is a reference to the left boundary of the specified range |
myright | is a reference to the right boundary of the specified range |
References mask.
Referenced by intersect().
|
private |
Normalize the representation of full sets.
All the instantiations where left == right represent the same set. We normalize the representation so we can compare sets easily.
References left, right, and step.
Referenced by minimalContainer(), pushForwardBinary(), pushForwardUnary(), and widen().
|
inline |
void ghidra::CircleRange::printRaw | ( | ostream & | s | ) | const |
Write a text representation of this to stream.
s | is the stream to write to |
References isempty, left, mask, ghidra::ValueSet::MAX_STEP, right, and step.
Referenced by getNext(), ghidra::ValueSet::isRightStable(), and ghidra::ValueSetRead::isRightStable().
Pull-back this range through given PcodeOp.
The pull-back is performed through a given p-code op and set this to the resulting range (if possible). If there is a single unknown input, and the set of values for this input that cause the output of op to fall into this form a range, then set this to the range (the "pullBack") and return the unknown varnode. Return null otherwise.
We may know something about the input varnode in the form of its NZMASK, which can further restrict the range we return. If usenzmask is true, and NZMASK forms a range, intersect this with the result.
If there is Symbol markup on any constant passed into the op, pass that information back.
op | is the given PcodeOp |
constMarkup | is the reference for passing back the constant relevant to the pull-back |
usenzmask | specifies whether to use the NZMASK |
References ghidra::calc_mask(), ghidra::PcodeOp::code(), ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getIn(), ghidra::Varnode::getNZMask(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Varnode::getSymbolEntry(), intersect(), ghidra::Varnode::isConstant(), mask, ghidra::PcodeOp::numInput(), pullBackBinary(), pullBackUnary(), and setNZMask().
Referenced by ghidra::JumpBasic::analyzeGuards(), ghidra::RuleRangeMeld::applyOp(), ghidra::JumpBasic::checkUnrolledGuard(), ghidra::ValueSetSolver::constraintsFromPath(), and getNext().
bool ghidra::CircleRange::pullBackBinary | ( | OpCode | opc, |
uintb | val, | ||
int4 | slot, | ||
int4 | inSize, | ||
int4 | outSize | ||
) |
Pull-back this thru binary operator.
opc | is the OpCode to pull the range back through |
val | is the constant value of the other input parameter (if present) |
slot | is the slot of the input variable whose range gets produced |
inSize | is the storage size in bytes of the resulting input |
outSize | is the storage size in bytes of the range to pull-back |
References ghidra::calc_mask(), complement(), convertToBoolean(), ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_CARRY, ghidra::CPUI_INT_EQUAL, ghidra::CPUI_INT_LESS, ghidra::CPUI_INT_LESSEQUAL, ghidra::CPUI_INT_NOTEQUAL, ghidra::CPUI_INT_RIGHT, ghidra::CPUI_INT_SLESS, ghidra::CPUI_INT_SLESSEQUAL, ghidra::CPUI_INT_SRIGHT, ghidra::CPUI_INT_SUB, isempty, left, mask, right, and step.
Referenced by ghidra::ValueSetSolver::generateRelativeConstraint(), getNext(), and pullBack().
bool ghidra::CircleRange::pullBackUnary | ( | OpCode | opc, |
int4 | inSize, | ||
int4 | outSize | ||
) |
Pull-back this through the given unary operator.
opc | is the OpCode to pull the range back through |
inSize | is the storage size in bytes of the resulting input |
outSize | is the storage size in bytes of the range to pull-back |
References ghidra::calc_mask(), convertToBoolean(), ghidra::CPUI_BOOL_NEGATE, ghidra::CPUI_COPY, ghidra::CPUI_INT_2COMP, ghidra::CPUI_INT_NEGATE, ghidra::CPUI_INT_SEXT, ghidra::CPUI_INT_ZEXT, intersect(), isempty, isEmpty(), left, mask, right, and step.
Referenced by getNext(), and pullBack().
bool ghidra::CircleRange::pushForwardBinary | ( | OpCode | opc, |
const CircleRange & | in1, | ||
const CircleRange & | in2, | ||
int4 | inSize, | ||
int4 | outSize, | ||
int4 | maxStep | ||
) |
Push this range forward through a binary operation.
Push all values in the given ranges through a binary p-code operator. If the output set of values forms a range, then set this to the range and return true.
opc | is the given p-code operator |
in1 | is the first given input range |
in2 | is the second given input range |
inSize | is the storage space in bytes for the input |
outSize | is the storage space in bytes for the output |
maxStep | is the maximum to allow step to grow via multiplication |
References ghidra::calc_mask(), ghidra::CPUI_BOOL_AND, ghidra::CPUI_BOOL_OR, ghidra::CPUI_BOOL_XOR, ghidra::CPUI_FLOAT_EQUAL, ghidra::CPUI_FLOAT_LESS, ghidra::CPUI_FLOAT_LESSEQUAL, ghidra::CPUI_FLOAT_NOTEQUAL, ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_CARRY, ghidra::CPUI_INT_EQUAL, ghidra::CPUI_INT_LEFT, ghidra::CPUI_INT_LESS, ghidra::CPUI_INT_LESSEQUAL, ghidra::CPUI_INT_MULT, ghidra::CPUI_INT_NOTEQUAL, ghidra::CPUI_INT_RIGHT, ghidra::CPUI_INT_SBORROW, ghidra::CPUI_INT_SCARRY, ghidra::CPUI_INT_SLESS, ghidra::CPUI_INT_SLESSEQUAL, ghidra::CPUI_INT_SRIGHT, ghidra::CPUI_PTRSUB, ghidra::CPUI_SUBPIECE, getMaxInfo(), getMin(), isempty, isSingle(), left, mask, normalize(), right, and step.
Referenced by getNext(), ghidra::ValueSet::iterate(), and pushForwardTrinary().
bool ghidra::CircleRange::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.
Push all values in the given ranges through a trinary p-code operator (currenly only CPUI_PTRADD). If the output set of values forms a range, then set this to the range and return true.
opc | is the given p-code operator |
in1 | is the first given input range |
in2 | is the second given input range |
in3 | is the third given input range |
inSize | is the storage space in bytes for the input |
outSize | is the storage space in bytes for the output |
maxStep | is the maximum to allow step to grow via multiplication |
References ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_MULT, ghidra::CPUI_PTRADD, and pushForwardBinary().
Referenced by getNext(), and ghidra::ValueSet::iterate().
bool ghidra::CircleRange::pushForwardUnary | ( | OpCode | opc, |
const CircleRange & | in1, | ||
int4 | inSize, | ||
int4 | outSize | ||
) |
Push-forward thru given unary operator.
Push all values in the given range through a p-code operator. If the output set of values forms a range, then set this to the range and return true.
opc | is the given p-code operator |
in1 | is the given input range |
inSize | is the storage space in bytes for the input |
outSize | is the storage space in bytes for the output |
References ghidra::calc_mask(), ghidra::CPUI_BOOL_NEGATE, ghidra::CPUI_CAST, ghidra::CPUI_COPY, ghidra::CPUI_FLOAT_NAN, ghidra::CPUI_INT_2COMP, ghidra::CPUI_INT_NEGATE, ghidra::CPUI_INT_SEXT, ghidra::CPUI_INT_ZEXT, isempty, left, mask, normalize(), right, and step.
Referenced by getNext(), and ghidra::ValueSet::iterate().
void ghidra::CircleRange::setFull | ( | int4 | size | ) |
Set a completely full range.
Make a range of values that holds everything.
size | is the size (in bytes) of the range |
References ghidra::calc_mask(), isempty, left, mask, right, and step.
Referenced by CircleRange(), ghidra::ValueSet::iterate(), and ghidra::ValueSet::setFull().
bool ghidra::CircleRange::setNZMask | ( | uintb | nzmask, |
int4 | size | ||
) |
Set the range based on a putative mask.
Try to create a range given a value that is not necessarily a valid mask. If the mask is valid, range is set to all possible values that whose non-zero bits are contained in the mask. If the mask is invalid, this range is not modified.
nzmask | is the putative mask |
size | is a maximum size (in bytes) for the mask |
References ghidra::calc_mask(), isempty, left, mask, right, and step.
Referenced by getNext(), and pullBack().
void ghidra::CircleRange::setRange | ( | uintb | lft, |
uintb | rgt, | ||
int4 | size, | ||
int4 | stp | ||
) |
Set directly to a specific range.
lft | is the left boundary of the range |
rgt | is the right boundary of the range |
size | is the size of the range domain in bytes |
stp | is the step/stride of the range |
References ghidra::calc_mask(), isempty, left, mask, right, and step.
Referenced by CircleRange(), and ghidra::JumpBasic::findSmallestNormal().
void ghidra::CircleRange::setRange | ( | uintb | val, |
int4 | size | ||
) |
void ghidra::CircleRange::setStride | ( | int4 | newStep, |
uintb | rem | ||
) |
Set a new step on this range.
This method changes the step for this range, i.e. elements are removed. The boundaries of the range do not change except for the remainder modulo the new step.
newStep | is the new step amount |
rem | is the desired phase (remainder of the values modulo the step) |
References isempty, left, right, and step.
Referenced by getNext().
int4 ghidra::CircleRange::translate2Op | ( | OpCode & | opc, |
uintb & | c, | ||
int4 & | cslot | ||
) | const |
Translate range to a comparison op.
Recover parameters for a comparison PcodeOp, that returns true for input values exactly in this range. Return:
opc | will contain the OpCode for the comparison PcodeOp |
c | will contain the constant input to the op |
cslot | will indicate the slot holding the constant |
References ghidra::CPUI_INT_EQUAL, ghidra::CPUI_INT_LESS, ghidra::CPUI_INT_NOTEQUAL, ghidra::CPUI_INT_SLESS, isempty, left, mask, right, and step.
Referenced by ghidra::RuleRangeMeld::applyOp(), and getNext().
void ghidra::CircleRange::widen | ( | const CircleRange & | op2, |
bool | leftIsStable | ||
) |
Widen the unstable bound to match containing range.
Widen this range so at least one of the boundaries matches with the given range, which must contain this.
op2 | is the given containing range |
leftIsStable | is true if we want to match right boundaries |
References left, mask, normalize(), right, and step.
Referenced by ghidra::WidenerFull::doWidening(), and getNext().