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.

Detailed Description

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

Generate ranges based on a pcode condition:
- x < 2 => left=0 right=2 mask=sizeof(x)
- 5 >= x => left=5 right=0 mask=sizeof(x)
Intersect and union ranges, if the result is another range
Pull-back a range through a transformation operation
Iterate

val = range.getMin();
do {
} while(range.getNext(val));

Constructor & Destructor Documentation

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.

Parameters

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 calc_mask(), isempty, left, mask, right, and step.

CircleRange::CircleRange ( bool val )

Construct a boolean range.

The range contains only a single integer, 0 or 1, depending on the boolean parameter.

Parameters

val	is the boolean parameter

References isempty, left, mask, right, and step.

CircleRange::CircleRange	(	uintb	val,
		int4	size
	)

Construct range with single value.

A size specifies the number of bytes (*8 to get number of bits) in the mask. The stride is assumed to be 1.

Parameters

val	is is the single value
size	is the size of the mask in bytes

References calc_mask(), isempty, left, mask, right, and step.

Member Function Documentation

int4 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.

Parameters

op2	is the range to union with

Returns: the result code

References encodeRangeOverlaps(), isempty, isSingle(), left, mask, right, and step.

Referenced by RuleRangeMeld::applyOp(), getNext(), and ValueSet::iterate().

void CircleRange::complement ( void )

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 CircleRange::contains ( const CircleRange & op2 ) const

Check containment of another range in this.

Parameters

op2	is the specific range to test for containment.

Returns: true if this contains the interval op2

References encodeRangeOverlaps(), isempty, isSingle(), left, right, and step.

Referenced by convertToBoolean(), WidenerFull::doWidening(), getMaxInfo(), and getNext().

bool CircleRange::contains ( uintb val ) const

Check containment of a specific integer.

Check if a specific integer is a member of this range.

Parameters

val	is the specific integer

Returns: true if it is contained in this

References isempty, left, right, and step.

bool CircleRange::convertToBoolean ( void )

private

Convert this to boolean.

If the original range contained

0 and 1 => the new range is [0,2)
0 only => the new range is [0,1)
1 only => the new range is [1,2)
neither 0 or 1 => the new range is empty

Returns: true if the range contains both 0 and 1

References contains(), isempty, left, mask, right, and step.

Referenced by pullBackBinary(), and pullBackUnary().

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

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

a = (l r op2.l op2.r)
b = (l op2.l r op2.r)
c = (l op2.l op2.r r)
d = (op2.l l r op2.r)
e = (op2.l l op2.r r)
f = (op2.l op2.r l r)
g = (l op2.r op2.l r)

Given 2 ranges, this method calculates the category code for the overlap.

Parameters

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

Returns: the character code of the normalized overlap category

References arrange.

Referenced by circleUnion(), contains(), intersect(), and minimalContainer().

int4 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.

Returns: the maximum information

References contains(), count_leading_zeros(), left, mask, and right.

Referenced by getStep(), and pushForwardBinary().

uintb CircleRange::getSize ( void ) const

Get the size of this range.

Returns: the number of integers contained in this range

References isempty, left, mask, right, and step.

Referenced by JumpBasic::calcRange(), LoadGuard::establishRange(), LoadGuard::finalizeRange(), JumpBasic::findSmallestNormal(), and getMask().

int4 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

Parameters

op2	is the second range

Returns: the intersection code

References encodeRangeOverlaps(), isempty, left, mask, newDomain(), newStride(), right, and step.

Referenced by RuleRangeMeld::applyOp(), JumpBasic::calcRange(), getNext(), ValueSet::iterate(), pullBack(), and pullBackUnary().

int4 CircleRange::invert ( void )

Convert to complementary range.

Convert range to its complement. The step is automatically converted to 1 first.

Returns: the original step size

References complement(), and step.

Referenced by WidenerFull::doWidening(), ValueSetSolver::generateFalseEquation(), and getNext().

bool 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.

Parameters

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

Returns: true if the container is everything (full)

References encodeRangeOverlaps(), getMin(), isSingle(), leastsigbit_set(), left, mask, mostsigbit_set(), normalize(), right, and step.

Referenced by getNext(), and ValueSet::iterate().

bool CircleRange::newDomain	(	uintb	newMask,
		int4	newStep,
		uintb &	myleft,
		uintb &	myright
	)

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.

Parameters

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

Returns: true if the truncated domain is empty

Referenced by intersect().

bool CircleRange::newStride	(	uintb	mask,
		int4	step,
		int4	oldStep,
		uint4	rem,
		uintb &	myleft,
		uintb &	myright
	)

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.

Parameters

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

Returns: true if result is empty

References mask.

Referenced by intersect().

void CircleRange::normalize ( void )

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().

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

inline

Equals operator.

Parameters

op2	is the range to compare this to

Returns: true if the two ranges are equal

References isempty, left, mask, right, and step.

Referenced by getStep().

void CircleRange::printRaw ( ostream & s ) const

Write a text representation of this to stream.

Parameters

s	is the stream to write to

References isempty, left, mask, ValueSet::MAX_STEP, right, and step.

Referenced by getNext(), ValueSet::isRightStable(), and ValueSetRead::isRightStable().

Varnode * CircleRange::pullBack	(	PcodeOp *	op,
		Varnode **	constMarkup,
		bool	usenzmask
	)

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.

Parameters

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

Returns: the input Varnode or NULL

References calc_mask(), PcodeOp::code(), CPUI_SUBPIECE, PcodeOp::getIn(), Varnode::getNZMask(), Varnode::getOffset(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getSymbolEntry(), intersect(), Varnode::isConstant(), mask, mostsigbit_set(), PcodeOp::numInput(), pullBackBinary(), pullBackUnary(), and setNZMask().

Referenced by JumpBasic::analyzeGuards(), RuleRangeMeld::applyOp(), ValueSetSolver::constraintsFromPath(), and getNext().

bool CircleRange::pullBackBinary	(	OpCode	opc,
		uintb	val,
		int4	slot,
		int4	inSize,
		int4	outSize
	)

Pull-back this thru binary operator.

Parameters

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

Returns: true if a valid range is formed in the pull-back

References calc_mask(), complement(), convertToBoolean(), CPUI_INT_ADD, CPUI_INT_CARRY, CPUI_INT_EQUAL, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_NOTEQUAL, CPUI_INT_RIGHT, CPUI_INT_SLESS, CPUI_INT_SLESSEQUAL, CPUI_INT_SRIGHT, CPUI_INT_SUB, isempty, left, mask, right, and step.

Referenced by ValueSetSolver::generateRelativeConstraint(), getNext(), and pullBack().

bool CircleRange::pullBackUnary	(	OpCode	opc,
		int4	inSize,
		int4	outSize
	)

Pull-back this through the given unary operator.

Parameters

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

Returns: true if a valid range is formed in the pull-back

References calc_mask(), convertToBoolean(), CPUI_BOOL_NEGATE, CPUI_COPY, CPUI_INT_2COMP, CPUI_INT_SEXT, CPUI_INT_ZEXT, intersect(), isempty, isEmpty(), left, mask, right, sign_extend(), and step.

Referenced by getNext(), and pullBack().

bool 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.

Parameters

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

Returns: true if the result is known and forms a range

References calc_mask(), count_leading_zeros(), CPUI_BOOL_AND, CPUI_BOOL_OR, CPUI_BOOL_XOR, CPUI_FLOAT_EQUAL, CPUI_FLOAT_LESS, CPUI_FLOAT_LESSEQUAL, CPUI_FLOAT_NOTEQUAL, CPUI_INT_ADD, CPUI_INT_CARRY, CPUI_INT_EQUAL, CPUI_INT_LEFT, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_MULT, CPUI_INT_NOTEQUAL, CPUI_INT_RIGHT, CPUI_INT_SBORROW, CPUI_INT_SCARRY, CPUI_INT_SLESS, CPUI_INT_SLESSEQUAL, CPUI_INT_SRIGHT, CPUI_PTRSUB, CPUI_SUBPIECE, getMaxInfo(), getMin(), isempty, isSingle(), left, mask, normalize(), right, sign_extend(), and step.

Referenced by getNext(), ValueSet::iterate(), and pushForwardTrinary().

bool 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.

Parameters

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

Returns: true if the result is known and forms a range

References CPUI_INT_ADD, CPUI_INT_MULT, CPUI_PTRADD, and pushForwardBinary().

Referenced by getNext(), and ValueSet::iterate().

bool 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.

Parameters

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

Returns: true if the result is known and forms a range

References calc_mask(), CPUI_BOOL_NEGATE, CPUI_CAST, CPUI_COPY, CPUI_FLOAT_NAN, CPUI_INT_2COMP, CPUI_INT_NEGATE, CPUI_INT_SEXT, CPUI_INT_ZEXT, isempty, left, mask, normalize(), right, sign_extend(), and step.

Referenced by getNext(), and ValueSet::iterate().

void CircleRange::setFull ( int4 size )

Set a completely full range.

Make a range of values that holds everything.

Parameters

size	is the size (in bytes) of the range

References calc_mask(), isempty, left, mask, right, and step.

Referenced by CircleRange(), ValueSet::iterate(), and ValueSet::setFull().

bool 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.

Parameters

nzmask	is the putative mask
size	is a maximum size (in bytes) for the mask

Returns: true if the mask is valid

References bit_transitions(), calc_mask(), isempty, leastsigbit_set(), left, mask, right, and step.

Referenced by getNext(), and pullBack().

void CircleRange::setRange	(	uintb	lft,
		uintb	rgt,
		int4	size,
		int4	stp
	)

Set directly to a specific range.

Parameters

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 calc_mask(), isempty, left, mask, right, and step.

Referenced by CircleRange(), and JumpBasic::findSmallestNormal().

void CircleRange::setRange	(	uintb	val,
		int4	size
	)

Set range with a single value.

A size specifies the number of bytes (*8 to get number of bits) in the mask. The stride is assumed to be 1.

Parameters

val	is is the single value
size	is the size of the mask in bytes

References calc_mask(), isempty, left, mask, right, and step.

void 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.

Parameters

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 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:

0 on success
1 if all inputs must return true
2 if this is not possible
3 if no inputs must return true
Parameters

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

Returns
the success code

References CPUI_INT_EQUAL, CPUI_INT_LESS, CPUI_INT_NOTEQUAL, CPUI_INT_SLESS, isempty, left, mask, right, and step.

Referenced by RuleRangeMeld::applyOp(), and getNext().

void 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.

Parameters

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 WidenerFull::doWidening(), and getNext().

The documentation for this class was generated from the following files:

rangeutil.hh
rangeutil.cc

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

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation