decompiler  1.0.0
Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
ghidra::CircleRange Class Reference

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

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

Constructor & Destructor Documentation

◆ CircleRange() [1/3]

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.

Parameters
lftis the left boundary of the range
rgtis the right boundary of the range
sizeis the domain size in bytes (1,2,4,8,..)
stpis the desired step (1,2,4,8,..)

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

◆ CircleRange() [2/3]

ghidra::CircleRange::CircleRange ( bool  val)

Construct a boolean range.

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

Parameters
valis the boolean parameter

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

◆ CircleRange() [3/3]

ghidra::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
valis is the single value
sizeis the size of the mask in bytes

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

Member Function Documentation

◆ circleUnion()

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.

Parameters
op2is the range to union with
Returns
the result code

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

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

◆ complement()

void ghidra::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().

◆ contains() [1/2]

bool ghidra::CircleRange::contains ( const CircleRange op2) const

Check containment of another range in this.

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

◆ contains() [2/2]

bool ghidra::CircleRange::contains ( uintb  val) const

Check containment of a specific integer.

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

Parameters
valis the specific integer
Returns
true if it is contained in this

References isempty, left, right, and step.

◆ convertToBoolean()

bool ghidra::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().

◆ encodeRangeOverlaps()

char ghidra::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
op1leftis left boundary of the first range
op1rightis the right boundary of the first range
op2leftis the left boundary of the second range
op2rightis 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().

◆ getMaxInfo()

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.

Returns
the maximum information

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

Referenced by getStep(), and pushForwardBinary().

◆ getSize()

uintb ghidra::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 ghidra::JumpBasic::calcRange(), ghidra::LoadGuard::establishRange(), ghidra::LoadGuard::finalizeRange(), ghidra::JumpBasic::findSmallestNormal(), and getMask().

◆ intersect()

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

Parameters
op2is the second range
Returns
the intersection code

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

◆ invert()

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

◆ minimalContainer()

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.

Parameters
op2is the other given range to combine with this
maxStepis 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(), left, mask, normalize(), right, and step.

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

◆ newDomain()

bool ghidra::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
newMaskis the mask for the new domain
newStepis the step associated with the range
myleftis a reference to the left edge of the range to fit
myrightis a reference to the right edge of the range to fit
Returns
true if the truncated domain is empty

Referenced by intersect().

◆ newStride()

bool ghidra::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
maskis the domain mask
stepis the new stride
oldStepis the original step (always smaller)
remis the given remainder to match
myleftis a reference to the left boundary of the specified range
myrightis a reference to the right boundary of the specified range
Returns
true if result is empty

References mask.

Referenced by intersect().

◆ normalize()

void ghidra::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().

◆ operator==()

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

Equals operator.

Parameters
op2is the range to compare this to
Returns
true if the two ranges are equal

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

Referenced by getStep().

◆ printRaw()

void ghidra::CircleRange::printRaw ( ostream &  s) const

Write a text representation of this to stream.

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

◆ pullBack()

Varnode * ghidra::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
opis the given PcodeOp
constMarkupis the reference for passing back the constant relevant to the pull-back
usenzmaskspecifies whether to use the NZMASK
Returns
the input Varnode or NULL

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

◆ pullBackBinary()

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

Pull-back this thru binary operator.

Parameters
opcis the OpCode to pull the range back through
valis the constant value of the other input parameter (if present)
slotis the slot of the input variable whose range gets produced
inSizeis the storage size in bytes of the resulting input
outSizeis the storage size in bytes of the range to pull-back
Returns
true if a valid range is formed in the 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().

◆ pullBackUnary()

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

Pull-back this through the given unary operator.

Parameters
opcis the OpCode to pull the range back through
inSizeis the storage size in bytes of the resulting input
outSizeis the storage size in bytes of the range to pull-back
Returns
true if a valid range is formed in the 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().

◆ pushForwardBinary()

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.

Parameters
opcis the given p-code operator
in1is the first given input range
in2is the second given input range
inSizeis the storage space in bytes for the input
outSizeis the storage space in bytes for the output
maxStepis the maximum to allow step to grow via multiplication
Returns
true if the result is known and forms a range

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

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

Parameters
opcis the given p-code operator
in1is the first given input range
in2is the second given input range
in3is the third given input range
inSizeis the storage space in bytes for the input
outSizeis the storage space in bytes for the output
maxStepis the maximum to allow step to grow via multiplication
Returns
true if the result is known and forms a range

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

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

◆ pushForwardUnary()

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.

Parameters
opcis the given p-code operator
in1is the given input range
inSizeis the storage space in bytes for the input
outSizeis the storage space in bytes for the output
Returns
true if the result is known and forms a range

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

◆ setFull()

void ghidra::CircleRange::setFull ( int4  size)

Set a completely full range.

Make a range of values that holds everything.

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

◆ setNZMask()

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.

Parameters
nzmaskis the putative mask
sizeis a maximum size (in bytes) for the mask
Returns
true if the mask is valid

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

Referenced by getNext(), and pullBack().

◆ setRange() [1/2]

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

Set directly to a specific range.

Parameters
lftis the left boundary of the range
rgtis the right boundary of the range
sizeis the size of the range domain in bytes
stpis the step/stride of the range

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

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

◆ setRange() [2/2]

void ghidra::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
valis is the single value
sizeis the size of the mask in bytes

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

◆ setStride()

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.

Parameters
newStepis the new step amount
remis the desired phase (remainder of the values modulo the step)

References isempty, left, right, and step.

Referenced by getNext().

◆ translate2Op()

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:

  • 0 on success
  • 1 if all inputs must return true
  • 2 if this is not possible
  • 3 if no inputs must return true
    Parameters
    opcwill contain the OpCode for the comparison PcodeOp
    cwill contain the constant input to the op
    cslotwill indicate the slot holding the constant
    Returns
    the success code

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

◆ widen()

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.

Parameters
op2is the given containing range
leftIsStableis true if we want to match right boundaries

References left, mask, normalize(), right, and step.

Referenced by ghidra::WidenerFull::doWidening(), and getNext().


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