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

Structure for sorting out pointer expression trees. More...

#include <ruleaction.hh>

Public Member Functions

 AddTreeState (Funcdata &d, PcodeOp *op, int4 slot)
 Construct given root of ADD tree and pointer.
 
bool apply (void)
 Attempt to transform the pointer expression. More...
 
bool initAlternateForm (void)
 Prepare analysis if there is an alternate form of the base pointer. More...
 

Private Member Functions

uint4 findArrayHint (void) const
 Look for evidence of an array in a sub-component. More...
 
bool hasMatchingSubType (int8 off, uint4 arrayHint, int8 *newoff) const
 Given an offset into the base data-type and array hints find sub-component being referenced. More...
 
bool checkMultTerm (Varnode *vn, PcodeOp *op, uint8 treeCoeff)
 Accumulate details of INT_MULT term and continue traversal if appropriate. More...
 
bool checkTerm (Varnode *vn, uint8 treeCoeff)
 Accumulate details of given term and continue tree traversal. More...
 
bool spanAddTree (PcodeOp *op, uint8 treeCoeff)
 Walk the given sub-tree accumulating details. More...
 
void calcSubtype (void)
 Calculate final sub-type offset. More...
 
VarnodebuildMultiples (void)
 Build part of tree that is multiple of base size. More...
 
VarnodebuildExtra (void)
 Build part of tree not accounted for by multiples or offset. More...
 
bool buildDegenerate (void)
 Transform ADD into degenerate PTRADD. More...
 
void buildTree (void)
 Build the transformed ADD tree. More...
 
void clear (void)
 Reset for a new ADD tree traversal.
 

Private Attributes

Funcdatadata
 The function containing the expression.
 
PcodeOpbaseOp
 Base of the ADD tree.
 
Varnodeptr
 The pointer varnode.
 
const TypePointerct
 The pointer data-type.
 
const DatatypebaseType
 The base data-type being pointed at.
 
const TypePointerRelpRelType
 A copy of ct, if it is a relative pointer.
 
int4 ptrsize
 Size of the pointer.
 
int4 size
 Size of data-type being pointed to (in address units) or 0 for open ended pointer.
 
int4 baseSlot
 Slot of the ADD tree base that is holding the pointer.
 
uint8 ptrmask
 Mask for modulo calculations in ptr space.
 
uint8 offset
 Number of bytes we dig into the base data-type.
 
uint8 correct
 Number of bytes being double counted.
 
vector< Varnode * > multiple
 Varnodes which are multiples of size.
 
vector< intb > coeff
 Associated constant multiple.
 
vector< Varnode * > nonmult
 Varnodes which are not multiples.
 
PcodeOpdistributeOp
 A CPUI_INT_MULT op that needs to be distributed.
 
uint8 multsum
 Sum of multiple constants.
 
uint8 nonmultsum
 Sum of non-multiple constants.
 
bool preventDistribution
 Do not distribute "multiply by constant" operation.
 
bool isDistributeUsed
 Are terms produced by distributing used.
 
bool isSubtype
 Is there a sub-type (using CPUI_PTRSUB)
 
bool valid
 Set to true if the whole expression can be transformed.
 
bool isDegenerate
 Set to true if pointer to unitsize or smaller.
 

Detailed Description

Structure for sorting out pointer expression trees.

Given a base pointer of known data-type and an additive expression involving the pointer, group the terms of the expression into:

The multiple terms are rewritten using a CPUI_PTRADD. The constant offset is rewritten using a CPUI_PTRSUB. Other terms are added back in. Analysis may cause multiplication (CPUI_INT_MULT) by a constant to be distributed to its CPUI_INT_ADD input.

Member Function Documentation

◆ apply()

bool ghidra::AddTreeState::apply ( void  )

◆ buildDegenerate()

bool ghidra::AddTreeState::buildDegenerate ( void  )
private

Transform ADD into degenerate PTRADD.

The base data-type being pointed to is unit sized (or smaller). Everything is a multiple, so an ADD is always converted into a PTRADD.

Returns
true if the degenerate transform was applied

References baseOp, baseType, ghidra::CPUI_PTRADD, ct, data, ghidra::PcodeOp::getIn(), ghidra::Datatype::getMetatype(), ghidra::PcodeOp::getOut(), ghidra::Datatype::getSize(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::getTypeDefFacing(), ghidra::TypePointer::getWordSize(), ghidra::Funcdata::newConstant(), ghidra::Funcdata::opSetAllInput(), ghidra::Funcdata::opSetOpcode(), ptr, and ghidra::TYPE_PTR.

Referenced by apply().

◆ buildExtra()

Varnode * ghidra::AddTreeState::buildExtra ( void  )
private

Build part of tree not accounted for by multiples or offset.

Create a subtree summing all the elements that aren't multiples of the base data-type size. Correct for any double counting of non-multiple constants. Return the final Varnode holding the sum or null if there are no terms.

Returns
the final Varnode or null

References baseOp, correct, ghidra::CPUI_INT_ADD, data, ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::Varnode::isConstant(), ghidra::Funcdata::newConstant(), ghidra::Funcdata::newOpBefore(), nonmult, offset, ptrmask, and ptrsize.

Referenced by buildTree().

◆ buildMultiples()

Varnode * ghidra::AddTreeState::buildMultiples ( void  )
private

Build part of tree that is multiple of base size.

Construct part of the tree that sums to a multiple of the base data-type size. This value will be added to the base pointer as a CPUI_PTRADD. The final Varnode produced by the sum is returned. If there are no multiples, null is returned.

Returns
the output Varnode of the multiple tree or null

References baseOp, coeff, ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_MULT, data, ghidra::PcodeOp::getOut(), multiple, multsum, ghidra::Funcdata::newConstant(), ghidra::Funcdata::newOpBefore(), ptrmask, ptrsize, and size.

Referenced by buildTree().

◆ buildTree()

void ghidra::AddTreeState::buildTree ( void  )
private

Build the transformed ADD tree.

The original ADD tree has been successfully split into multiple and non-multiple pieces. Rewrite the tree as a pointer expression, putting any multiple pieces into a PTRADD operation, creating a PTRSUB if a sub data-type offset has been calculated, and preserving and remaining terms.

References baseOp, baseSlot, buildExtra(), buildMultiples(), ghidra::CPUI_INT_ADD, ghidra::CPUI_PTRADD, ghidra::CPUI_PTRSUB, ct, data, ghidra::PcodeOp::getAddr(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getType(), ghidra::Funcdata::inheritResolution(), isSubtype, ghidra::Datatype::needsResolution(), ghidra::Funcdata::newConstant(), ghidra::Funcdata::newOpBefore(), offset, ghidra::Funcdata::opDestroy(), ghidra::Funcdata::opSetOutput(), pRelType, ptr, ptrmask, ptrsize, ghidra::PcodeOp::setStopTypePropagation(), size, and ghidra::Funcdata::warning().

Referenced by apply().

◆ calcSubtype()

void ghidra::AddTreeState::calcSubtype ( void  )
private

◆ checkMultTerm()

bool ghidra::AddTreeState::checkMultTerm ( Varnode vn,
PcodeOp op,
uint8  treeCoeff 
)
private

Accumulate details of INT_MULT term and continue traversal if appropriate.

Examine a CPUI_INT_MULT element in the middle of the add tree. Determine if we treat the output simply as a leaf, or if the multiply needs to be distributed to an additive subtree. If the Varnode is a leaf of the tree, return true if it is considered a multiple of the base data-type size. If the Varnode is the root of another additive sub-tree, return true if no sub-node is a multiple.

Parameters
vnis the output Varnode of the operation
opis the CPUI_INT_MULT operation
treeCoeffis constant multiple being applied to the node
Returns
true if there are no multiples of the base data-type size discovered

References ghidra::PcodeOp::code(), coeff, ghidra::CPUI_INT_ADD, distributeOp, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), isDistributeUsed, ghidra::Varnode::isFree(), ghidra::Varnode::isWritten(), multiple, preventDistribution, ptrmask, size, spanAddTree(), and valid.

Referenced by checkTerm().

◆ checkTerm()

bool ghidra::AddTreeState::checkTerm ( Varnode vn,
uint8  treeCoeff 
)
private

Accumulate details of given term and continue tree traversal.

If the given Varnode is a constant or multiplicative term, update totals. If the Varnode is additive, traverse its sub-terms.

Parameters
vnis the given Varnode term
treeCoeffis a constant multiple applied to the entire sub-tree
Returns
true if the sub-tree rooted at the given Varnode contains no multiples

References baseType, checkMultTerm(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INT_ADD, ghidra::CPUI_INT_MULT, ghidra::Varnode::getDef(), ghidra::Datatype::getMetatype(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), isDistributeUsed, ghidra::Varnode::isFree(), ghidra::Varnode::isWritten(), multsum, nonmultsum, ptr, ptrmask, size, spanAddTree(), ghidra::TYPE_ARRAY, ghidra::TYPE_STRUCT, and valid.

Referenced by spanAddTree().

◆ findArrayHint()

uint4 ghidra::AddTreeState::findArrayHint ( void  ) const
private

Look for evidence of an array in a sub-component.

Even if the current base data-type is not an array, the pointer expression may incorporate an array access for a sub component. This manifests as a non-constant non-multiple terms in the tree. If this term is itself defined by a CPUI_INT_MULT with a constant, the constant indicates a likely element size. Return a non-zero value, the likely element size, if there is evidence of a non-constant non-multiple term. Return zero otherwise.

Returns
a non-zero value indicating likely element size, or zero

References ghidra::PcodeOp::code(), ghidra::CPUI_INT_MULT, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), ghidra::Varnode::isWritten(), and nonmult.

Referenced by calcSubtype().

◆ hasMatchingSubType()

bool ghidra::AddTreeState::hasMatchingSubType ( int8  off,
uint4  arrayHint,
int8 *  newoff 
) const
private

Given an offset into the base data-type and array hints find sub-component being referenced.

An explicit offset should target a specific sub data-type, but array indexing may confuse things. This method passes back the offset of the best matching component, searching among components that are nearby the given offset, preferring a matching array element size and a component start that is nearer to the offset.

Parameters
offis the given offset into the data-type
arrayHintif non-zero indicates array access, where the value is the element size
newoffis used to pass back the actual offset of the selected component
Returns
true if a good component match was found

References baseType, ghidra::AddrSpace::byteToAddressInt(), ct, ghidra::Datatype::getSize(), ghidra::Datatype::getSubType(), ghidra::TypePointer::getWordSize(), ghidra::Datatype::nearestArrayedComponentBackward(), and ghidra::Datatype::nearestArrayedComponentForward().

Referenced by calcSubtype().

◆ initAlternateForm()

bool ghidra::AddTreeState::initAlternateForm ( void  )

Prepare analysis if there is an alternate form of the base pointer.

For some forms of pointer (TypePointerRel), the pointer can be interpreted as having two versions of the data-type being pointed to. This method initializes analysis for the second version, assuming analysis of the first version has failed.

Returns
true if there is a second version that can still be analyzed

References ghidra::AddrSpace::addressToByteInt(), and ghidra::AddrSpace::byteToAddressInt().

Referenced by ghidra::RulePtrArith::applyOp().

◆ spanAddTree()

bool ghidra::AddTreeState::spanAddTree ( PcodeOp op,
uint8  treeCoeff 
)
private

Walk the given sub-tree accumulating details.

Recursively walk the sub-tree from the given root. Terms that are a multiple of the base data-type size are accumulated either in the the sum of constant multiples or the container of non-constant multiples. Terms that are a non-multiple are accumulated either in the sum of constant non-multiples or the container of non-constant non-multiples. The constant non-multiples are counted twice, once in the sum, and once in the container. This routine returns true if no node of the sub-tree is considered a multiple of the base data-type size (or false if any node is considered a multiple).

Parameters
opis the root of the sub-expression to traverse
treeCoeffis a constant multiple applied to the entire additive tree
Returns
true if the given sub-tree contains no multiple nodes

References checkTerm(), ghidra::PcodeOp::getIn(), multiple, multsum, nonmult, nonmultsum, pRelType, size, and valid.

Referenced by apply(), checkMultTerm(), and checkTerm().


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