A hash utility to uniquely identify a temporary Varnode in data-flow. More...

#include <dynamic.hh>

Public Member Functions
void	clear (void)
	Called for each additional hash (after the first)

void	calcHash (const Varnode *root, uint4 method)
	Calculate the hash for given Varnode and method. More...

void	calcHash (const PcodeOp *op, int4 slot, uint4 method)
	Calculate hash for given PcodeOp, slot, and method.

void	uniqueHash (const Varnode root, Funcdata fd)
	Select a unique hash for the given Varnode. More...

void	uniqueHash (const PcodeOp op, int4 slot, Funcdata fd)
	Select unique hash for given PcodeOp and slot. More...

Varnode *	findVarnode (const Funcdata *fd, const Address &addr, uint8 h)
	Given an address and hash, find the unique matching Varnode. More...

PcodeOp *	findOp (const Funcdata *fd, const Address &addr, uint8 h)
	Given an address and hash, find the unique matching PcodeOp. More...

uint8	getHash (void) const
	Get the (current) hash.

const Address &	getAddress (void) const
	Get the (current) address.

Static Public Member Functions
static void	gatherFirstLevelVars (vector< Varnode > &varlist, const Funcdata fd, const Address &addr, uint8 h)
	Get the Varnodes immediately attached to PcodeOps at the given address. More...

static void	gatherOpsAtAddress (vector< PcodeOp > &opList, const Funcdata fd, const Address &addr)
	Place all PcodeOps at the given address in the provided container. More...

static int4	getSlotFromHash (uint8 h)
	Retrieve the encoded slot from a hash. More...

static uint4	getMethodFromHash (uint8 h)
	Retrieve the encoded method from a hash. More...

static uint4	getOpCodeFromHash (uint8 h)
	Retrieve the encoded op-code from a hash. More...

static uint4	getPositionFromHash (uint8 h)
	Retrieve the encoded position from a hash. More...

static uint4	getTotalFromHash (uint8 h)
	Retrieve the encoded collision total from a hash. More...

static bool	getIsNotAttached (uint8 h)
	Retrieve the attachment boolean from a hash. More...

static void	clearTotalPosition (uint8 &h)
	Clear the collision total and position fields within a hash. More...

static uint4	getComparable (uint8 h)
	Get only the formal hash for comparing.

Static Public Attributes
static const uint4	transtable []
	Translation of op-codes to hash values.

Private Member Functions
void	buildVnUp (const Varnode *vn)
	Add in the edge between the given Varnode and its defining PcodeOp. More...

void	buildVnDown (const Varnode *vn)
	Add in edges between the given Varnode and any PcodeOp that reads it. More...

void	buildOpUp (const PcodeOp *op)
	Move input Varnodes for the given PcodeOp into staging. More...

void	buildOpDown (const PcodeOp *op)
	Move the output Varnode for the given PcodeOp into staging. More...

void	gatherUnmarkedVn (void)
	Move staged Varnodes into the sub-graph and mark them.

void	gatherUnmarkedOp (void)
	Mark any new PcodeOps in the sub-graph.

void	pieceTogetherHash (const Varnode *root, uint4 method)
	Clean-up and piece together formal hash value. More...

Static Private Member Functions
static void	moveOffSkip (const PcodeOp *&op, int4 &slot)
	Convert given PcodeOp to a non-skip op by following data-flow. More...

static void	dedupVarnodes (vector< Varnode *> &varlist)
	Remove any duplicate Varnodes in given list. More...

Private Attributes
uint4	vnproc
	Number of Varnodes processed in the markvn list so far.

uint4	opproc
	Number of PcodeOps processed in the markop list so far.

uint4	opedgeproc
	Number of edges processed in the opedge list.

vector< const PcodeOp * >	markop
	List of PcodeOps in the sub-graph being hashed.

vector< const Varnode * >	markvn
	List of Varnodes is the sub-graph being hashed.

vector< const Varnode * >	vnedge
	A staging area for Varnodes before formally adding to the sub-graph.

vector< ToOpEdge >	opedge
	The edges in the sub-graph.

Address	addrresult
	Address most closely associated with variable.

uint8	hash
	The calculated hash value.

Detailed Description

A hash utility to uniquely identify a temporary Varnode in data-flow.

Most Varnodes can be identified within the data-flow graph by their storage address and the address of the PcodeOp that defines them. For temporary registers, this does not work because the storage address is ephemeral. This class allows Varnodes like temporary registers (and constants) to be robustly identified by hashing details of the local data-flow.

This class, when presented a Varnode via calcHash(), calculates a hash (getHash()) and an address (getAddress()) of the PcodeOp most closely associated with the Varnode, either the defining op or the op directly reading the Varnode. There are actually four hash variants that can be calculated, labeled 0, 1, 2, or 3, which incrementally hash in a larger portion of data-flow. The method uniqueHash() selects the simplest variant that causes the hash to be unique for the Varnode, among all the Varnodes that share the same address.

The variant index is encoded in the hash, so the hash and the address are enough information to uniquely identify the Varnode. This is what is stored in the symbol table for a dynamic Symbol.

Member Function Documentation

◆ buildOpDown()

void ghidra::DynamicHash::buildOpDown ( const PcodeOp * op )

private

Move the output Varnode for the given PcodeOp into staging.

Parameters

op	is the given PcodeOp thats already in the sub-graph

References ghidra::PcodeOp::getOut().

◆ buildOpUp()

void ghidra::DynamicHash::buildOpUp ( const PcodeOp * op )

private

Move input Varnodes for the given PcodeOp into staging.

Parameters

op	is the given PcodeOp thats already in the sub-graph

References ghidra::PcodeOp::getIn(), and ghidra::PcodeOp::numInput().

◆ buildVnDown()

void ghidra::DynamicHash::buildVnDown ( const Varnode * vn )

private

Add in edges between the given Varnode and any PcodeOp that reads it.

When building edges, certain p-code ops (CAST) are effectively ignored so that we get the same hash whether or not these ops are present.

Parameters

vn	is the given Varnode

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::Varnode::endDescend(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::loneDescend(), ghidra::ToOpEdge::op, ghidra::ToOpEdge::slot, and ghidra::ToOpEdge::ToOpEdge().

◆ buildVnUp()

void ghidra::DynamicHash::buildVnUp ( const Varnode * vn )

private

Add in the edge between the given Varnode and its defining PcodeOp.

When building the edge, certain p-code ops (CAST) are effectively ignored so that we get the same hash whether or not these ops are present.

Parameters

vn	is the given Varnode

References ghidra::PcodeOp::code(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::isWritten(), ghidra::ToOpEdge::op, and ghidra::ToOpEdge::ToOpEdge().

◆ calcHash()

void ghidra::DynamicHash::calcHash	(	const Varnode *	root,
		uint4	method
	)

Calculate the hash for given Varnode and method.

A sub-graph is formed extending from the given Varnode as the root. The method specifies how the sub-graph is extended. In particular:

Method 0 is extends to just immediate p-code ops reading or writing root
Method 1 extends to one more level of inputs from method 0.
Method 2 extends to one more level of outputs from method 0.
Method 3 extends to inputs and outputs

The resulting hash and address can be obtained after calling this method through getHash() and getAddress().

Parameters

root	is the given root Varnode
method	is the hashing method to use: 0, 1, 2, 3

◆ clearTotalPosition()

void ghidra::DynamicHash::clearTotalPosition ( uint8 & h )

static

Clear the collision total and position fields within a hash.

The position and total collisions fields are set by the uniqueness and need to be cleared when comparing raw hashes.

Parameters

h	is a reference to the hash to modify

◆ dedupVarnodes()

void ghidra::DynamicHash::dedupVarnodes ( vector< Varnode *> & varlist )

staticprivate

Remove any duplicate Varnodes in given list.

Otherwise preserve the order of the list.

Parameters

varlist is the given list of Varnodes to check

References ghidra::Varnode::isMark(), and ghidra::Varnode::setMark().

◆ findOp()

PcodeOp * ghidra::DynamicHash::findOp	(	const Funcdata *	fd,
		const Address &	addr,
		uint8	h
	)

Given an address and hash, find the unique matching PcodeOp.

The method, slot, number of collisions, and position are pulled out of the hash. Hashes for the method are performed at PcodeOps linked to the given address, and the PcodeOp which matches the hash (and the position) is returned. If the number of collisions for the hash does not match, this method will not return a PcodeOp, even if the position looks valid.

Parameters

fd	is the function containing the data-flow
addr	is the given address
h	is the hash

Returns: the matching PcodeOp or NULL

References ghidra::ToOpEdge::hash(), ghidra::PcodeOp::numInput(), and ghidra::ToOpEdge::slot.

Referenced by ghidra::Funcdata::applyUnionFacet().

◆ findVarnode()

Varnode * ghidra::DynamicHash::findVarnode	(	const Funcdata *	fd,
		const Address &	addr,
		uint8	h
	)

Given an address and hash, find the unique matching Varnode.

The method, number of collisions, and position are pulled out of the hash. Hashes for the method are performed at Varnodes linked to the given address, and the Varnode which matches the hash (and the position) is returned. If the number of collisions for the hash does not match, this method will not return a Varnode, even if the position looks valid.

Parameters

fd	is the function containing the data-flow
addr	is the given address
h	is the hash

Returns: the matching Varnode or NULL

References ghidra::ToOpEdge::hash().

Referenced by ghidra::Funcdata::attemptDynamicMapping(), ghidra::Funcdata::attemptDynamicMappingLate(), ghidra::Funcdata::findLinkedVarnode(), ghidra::Funcdata::findLinkedVarnodes(), ghidra::JumpBasicOverride::recoverModel(), and ghidra::ScopeLocal::recoverNameRecommendationsForSymbols().

◆ gatherFirstLevelVars()

void ghidra::DynamicHash::gatherFirstLevelVars	(	vector< Varnode *> &	varlist,
		const Funcdata *	fd,
		const Address &	addr,
		uint8	h
	)

static

Get the Varnodes immediately attached to PcodeOps at the given address.

Varnodes can be either inputs or outputs to the PcodeOps. The op-code, slot, and attachment boolean encoded in the hash are used to further filter the PcodeOp and Varnode objects. Varnodes are passed back in sequence with a list container.

Parameters

varlist	is the container that will hold the matching Varnodes
fd	is the function holding the data-flow
addr	is the given address
h	is the given hash

References ghidra::Funcdata::beginOp(), ghidra::PcodeOp::code(), ghidra::Funcdata::endOp(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::isDead(), ghidra::Varnode::loneDescend(), ghidra::ToOpEdge::op, and ghidra::ToOpEdge::slot.

◆ gatherOpsAtAddress()

void ghidra::DynamicHash::gatherOpsAtAddress	(	vector< PcodeOp *> &	opList,
		const Funcdata *	fd,
		const Address &	addr
	)

static

Place all PcodeOps at the given address in the provided container.

Parameters

opList	is the container to hold the PcodeOps
fd	is the function
addr	is the given address

References ghidra::Funcdata::beginOp(), ghidra::Funcdata::endOp(), ghidra::PcodeOp::isDead(), and ghidra::ToOpEdge::op.

◆ getIsNotAttached()

bool ghidra::DynamicHash::getIsNotAttached ( uint8 h )

static

Retrieve the attachment boolean from a hash.

The hash encodes whether or not the root was directly attached to its PcodeOp

Parameters

h	is the hash value

Returns: true if the root was not attached

◆ getMethodFromHash()

uint4 ghidra::DynamicHash::getMethodFromHash ( uint8 h )

static

Retrieve the encoded method from a hash.

The hash encodes the method used to produce it.

Parameters

h	is the hash value

Returns: the method: 0, 1, 2, 3

◆ getOpCodeFromHash()

uint4 ghidra::DynamicHash::getOpCodeFromHash ( uint8 h )

static

Retrieve the encoded op-code from a hash.

The hash encodes the op-code of the p-code op attached to the root Varnode

Parameters

h	is the hash value

Returns: the op-code as an integer

◆ getPositionFromHash()

uint4 ghidra::DynamicHash::getPositionFromHash ( uint8 h )

static

Retrieve the encoded position from a hash.

The hash encodes the position of the root Varnode within the list of hash collisions

Parameters

h	is the hash value

Returns: the position of the root

Referenced by ghidra::IfcDuplicateHash::check().

◆ getSlotFromHash()

int4 ghidra::DynamicHash::getSlotFromHash ( uint8 h )

static

Retrieve the encoded slot from a hash.

The hash encodes the input slot the root Varnode was attached to in its PcodeOp.

Parameters

h	is the hash value

Returns: the slot index or -1 if the Varnode was attached as output

Referenced by ghidra::Funcdata::applyUnionFacet().

◆ getTotalFromHash()

uint4 ghidra::DynamicHash::getTotalFromHash ( uint8 h )

static

Retrieve the encoded collision total from a hash.

The hash encodes the total number of collisions for that hash

Parameters

h	is the hash value

Returns: the total number of collisions

Referenced by ghidra::IfcDuplicateHash::check().

◆ moveOffSkip()

void ghidra::DynamicHash::moveOffSkip	(	const PcodeOp *&	op,
		int4 &	slot
	)

staticprivate

Convert given PcodeOp to a non-skip op by following data-flow.

For a DynamicHash on a PcodeOp, the op must not be a CAST or other skipped opcode. Test if the given op is a skip op, and if so follow data-flow indicated by the slot to another PcodeOp until we find one that isn't a skip op. Pass back the new PcodeOp and slot. Pass back null if the data-flow path ends.

Parameters

op	is the given PcodeOp to modify
slot	is the slot to modify

References ghidra::PcodeOp::code(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::isWritten(), and ghidra::Varnode::loneDescend().

◆ pieceTogetherHash()

void ghidra::DynamicHash::pieceTogetherHash	(	const Varnode *	root,
		uint4	method
	)

private

Clean-up and piece together formal hash value.

Assume all the elements of the hash have been calculated. Calculate the internal 32-bit hash based on these elements. Construct the 64-bit hash by piecing together the 32-bit hash together with the core opcode, slot, and method.

Parameters

root	is the Varnode to extract root characteristics from
method	is the method used to compute the hash elements

References ghidra::PcodeOp::code(), ghidra::crc_update(), ghidra::SeqNum::getAddr(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSeqNum(), ghidra::Varnode::getSize(), ghidra::PcodeOp::getSlot(), ghidra::ToOpEdge::hash(), ghidra::Varnode::isConstant(), ghidra::ToOpEdge::op, and ghidra::ToOpEdge::slot.

◆ uniqueHash() [1/2]

void ghidra::DynamicHash::uniqueHash	(	const Varnode *	root,
		Funcdata *	fd
	)

Select a unique hash for the given Varnode.

Collect the set of Varnodes at the same address as the given Varnode. Starting with method 0, increment the method and calculate hashes of the Varnodes until the given Varnode has a unique hash within the set. The resulting hash and address can be obtained after calling this method through getHash() and getAddress().

In the rare situation that the last method still does not yield a unique hash, the hash encodes:

the smallest number of hash collisions
the method that produced the smallest number of hash collisions
the position of the root within the collision list

For most cases, this will still uniquely identify the root Varnode.

Parameters

root	is the given root Varnode
fd	is the function (holding the data-flow graph)

References ghidra::ToOpEdge::hash().

Referenced by ghidra::Funcdata::buildDynamicSymbol(), and ghidra::IfcDuplicateHash::check().

◆ uniqueHash() [2/2]

void ghidra::DynamicHash::uniqueHash	(	const PcodeOp *	op,
		int4	slot,
		Funcdata *	fd
	)

Select unique hash for given PcodeOp and slot.

Different hash methods are cycled through until a hash is found that distinguishes the given op from other PcodeOps at the same address. The final hash encoding and address of the PcodeOp are built for retrieval using getHash() and getAddress().

Parameters

op	is the given PcodeOp
slot	is the particular slot to encode in the hash
fd	is the function containing the given PcodeOp

References ghidra::PcodeOp::getAddr(), ghidra::ToOpEdge::hash(), and ghidra::PcodeOp::numInput().

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

dynamic.hh
dynamic.cc

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ buildOpDown()

◆ buildOpUp()

◆ buildVnDown()

◆ buildVnUp()

◆ calcHash()

◆ clearTotalPosition()

◆ dedupVarnodes()

◆ findOp()

◆ findVarnode()

◆ gatherFirstLevelVars()

◆ gatherOpsAtAddress()

◆ getIsNotAttached()

◆ getMethodFromHash()

◆ getOpCodeFromHash()

◆ getPositionFromHash()

◆ getSlotFromHash()

◆ getTotalFromHash()

◆ moveOffSkip()

◆ pieceTogetherHash()

◆ uniqueHash() [1/2]

◆ uniqueHash() [2/2]