A class for manipulating integer value ranges. More...

#include <rangeutil.hh>

Public Member Functions
	CircleRange (void)
	Construct an empty range.

	CircleRange (uintb mn, uintb mx, uintb m)
	Construct given specific boundaries. More...

	CircleRange (bool val)
	Construct a boolean range. More...

	CircleRange (uintb val, int4 size)
	Construct range with single value. More...

bool	isEmpty (void) const
	Return true if this range is empty.

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

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

void	setStride (int4 newshift)
	Set a new stride on this range. More...

Varnode *	pullBack (PcodeOp op, Varnode *constMarkup, bool usenzmask)
	Pull-back this range through given PcodeOp. More...

int4	translate2Op (OpCode &opc, uintb &c, int4 &cslot) const
	Translate range to a comparison op. More...

Private Member Functions
void	calcStepShift (void)
	Calculate explicit step and skip from mask.

void	complement (void)
	Set this to the complement of itself. More...

void	convertToBoolean (void)
	Convert this to boolean. More...

Static Private Member Functions
static bool	newStride (uintb newmask, uintb &myleft, uintb &myright)
	Recalculate range based on new size and stride. 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.

int4	shift
	Number of bits in step. Equal to log2(step)

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() [1/3]

CircleRange::CircleRange	(	uintb	mn,
		uintb	mx,
		uintb	m
	)

Construct given specific boundaries.

Give specific left/right boundaries and a mask.

Parameters

mn	is the left boundary of the range
mx	is the right boundary of the range
m	is the mask encoding a size and stride

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

◆ CircleRange() [2/3]

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, shift, and step.

◆ CircleRange() [3/3]

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, shift, and step.

Member Function Documentation

◆ circleUnion()

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, left, mask, right, shift, and step.

Referenced by RuleRangeMeld::applyOp().

◆ complement()

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

◆ contains() [1/2]

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 true contains the interval op2

References encodeRangeOverlaps(), isempty, left, right, and shift.

Referenced by convertToBoolean().

◆ contains() [2/2]

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, mask, and right.

◆ convertToBoolean()

void CircleRange::convertToBoolean ( void )

private

Convert this to boolean.

If the original range contained

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

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

Referenced by pullBack().

◆ encodeRangeOverlaps()

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(), and intersect().

◆ getSize()

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, shift, and step.

◆ intersect()

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, newStride(), right, shift, and step.

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

◆ newStride()

bool CircleRange::newStride	(	uintb	newmask,
		uintb &	myleft,
		uintb &	myright
	)

staticprivate

Recalculate range based on new size and stride.

Given a range mask, restrict a left/right specified range to a new size and stride. This assumes the specified range is not empty.

Parameters

newmask	is the mask encoding the new size and stride
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

Referenced by intersect().

◆ pullBack()

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(), complement(), convertToBoolean(), CPUI_BOOL_NEGATE, CPUI_COPY, CPUI_INT_2COMP, CPUI_INT_ADD, CPUI_INT_CARRY, CPUI_INT_EQUAL, CPUI_INT_LESS, CPUI_INT_LESSEQUAL, CPUI_INT_NOTEQUAL, CPUI_INT_RIGHT, CPUI_INT_SEXT, CPUI_INT_SLESS, CPUI_INT_SLESSEQUAL, CPUI_INT_SRIGHT, CPUI_INT_SUB, CPUI_INT_ZEXT, CPUI_SUBPIECE, PcodeOp::getIn(), Varnode::getNZMask(), Varnode::getOffset(), PcodeOp::getOut(), Varnode::getSize(), Varnode::getSymbolEntry(), intersect(), Varnode::isConstant(), isempty, left, mask, mostsigbit_set(), PcodeOp::numInput(), right, setNZMask(), shift, sign_extend(), and step.

Referenced by RuleRangeMeld::applyOp().

◆ setNZMask()

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, shift, and step.

Referenced by pullBack().

◆ setStride()

void CircleRange::setStride ( int4 newshift )

Set a new stride on this range.

The new stride is specified by giving the number of bits of shift (log2(stride))

Parameters

newshift is the number of bits of shift

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

◆ translate2Op()

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

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

◆ CircleRange() [1/3]

◆ CircleRange() [2/3]

◆ CircleRange() [3/3]

Member Function Documentation

◆ circleUnion()

◆ complement()

◆ contains() [1/2]

◆ contains() [2/2]

◆ convertToBoolean()

◆ encodeRangeOverlaps()

◆ getSize()

◆ intersect()

◆ newStride()

◆ pullBack()

◆ setNZMask()

◆ setStride()

◆ translate2Op()