Class RecursiveDescentSolver
- java.lang.Object
-
- ghidra.app.plugin.assembler.sleigh.expr.RecursiveDescentSolver
-
public class RecursiveDescentSolver extends java.lang.Object
This singleton class seeks solutions toPatternExpression
s It is called naive, because it does not perform algebraic transformations. Rather, it attempts to fold constants, assuming there is a single variable in the expression, modifying the goal as it descends toward that variable. If it finds a variable, i.e., token or context field, it encodes the solution, positioned in the field. If the expression is constant, it checks that the goal agrees. If not, an error is returned. TODO This whole mechanism ought to just be factored directly intoPatternExpression
.
-
-
Field Summary
Fields Modifier and Type Field Description protected static DbgTimer
dbg
protected java.util.Map<java.lang.Class<?>,AbstractExpressionSolver<?>>
registry
-
Constructor Summary
Constructors Constructor Description RecursiveDescentSolver()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
getInstructionLength(PatternExpression exp, java.util.Map<java.lang.Integer,java.lang.Object> res)
Determine the length of the instruction part of the encoded solution to the given expression This is used to keep operands in their appropriate position when backfilling becomes applicable.protected <T extends PatternExpression>
AbstractExpressionSolver<T>getRegistered(java.lang.Class<?> tcls)
Retrieve the registered solver for a given subclass ofPatternExpression
static RecursiveDescentSolver
getSolver()
Obtain an instance of the naive solverprotected <T extends PatternExpression>
MaskedLonggetValue(T exp, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur)
Attempt to fold a given expression (or sub-expression) into a single constant.protected <T extends PatternExpression>
voidregister(java.lang.Class<T> tcls, AbstractExpressionSolver<T> s)
Register a solver for a particular subclass ofPatternExpression
AssemblyResolution
solve(PatternExpression exp, MaskedLong goal, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur, java.lang.String description)
Solve a given expression, assuming it outputs a given masked value From a simplified perspective, we need only the expression and the desired value to solve it.protected AssemblyResolution
solve(PatternExpression exp, MaskedLong goal, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur, java.util.Set<SolverHint> hints, java.lang.String description)
Solve a given expression, passing hintsMaskedLong
valueForResolution(PatternExpression exp, AssemblyResolvedConstructor rc)
Compute the value of an expression given a (possibly-intermediate) resolution
-
-
-
Field Detail
-
dbg
protected static final DbgTimer dbg
-
registry
protected java.util.Map<java.lang.Class<?>,AbstractExpressionSolver<?>> registry
-
-
Method Detail
-
getSolver
public static RecursiveDescentSolver getSolver()
Obtain an instance of the naive solver- Returns:
- the singleton instance
-
register
protected <T extends PatternExpression> void register(java.lang.Class<T> tcls, AbstractExpressionSolver<T> s)
Register a solver for a particular subclass ofPatternExpression
- Parameters:
tcls
- the subclass the solver can handles
- the solver for the subclass
-
getRegistered
protected <T extends PatternExpression> AbstractExpressionSolver<T> getRegistered(java.lang.Class<?> tcls)
Retrieve the registered solver for a given subclass ofPatternExpression
- Parameters:
tcls
- the subclass to solve- Returns:
- the registered solver
-
solve
protected AssemblyResolution solve(PatternExpression exp, MaskedLong goal, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur, java.util.Set<SolverHint> hints, java.lang.String description) throws NeedsBackfillException
Solve a given expression, passing hints- Parameters:
exp
- the expression to solvegoal
- the desired output (modulo a mask) of the expressionvals
- any defined symbols (usuallyinst_start
, andinst_next
)res
- resolved subconstructors, by operand index (see method details)hints
- describes techniques applied by calling solversdescription
- a description to attached to the encoded solution- Returns:
- the encoded solution
- Throws:
NeedsBackfillException
- a solution may exist, but a required symbol is missing
-
solve
public AssemblyResolution solve(PatternExpression exp, MaskedLong goal, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur, java.lang.String description) throws NeedsBackfillException
Solve a given expression, assuming it outputs a given masked value From a simplified perspective, we need only the expression and the desired value to solve it. Generally speaking, the expression may have only contain a single variable, and the encoded result represents that single variable. It must be absorbed into the overall instruction and/or context encoding. More realistically, however, these expressions may depend on quite a bit of extra information. For example, PC-relative encodings (i.e., those involvinginst_start
orinst_next
, need to know the starting address of the resulting instruction.inst_start
must be provided to the solver by the assembler.inst_next
cannot be known until the instruction length is known. Thus, expressions using it always result in aNeedsBackfillException
. The symbols, when known, are provided to the solver via thevals
parameter. Expressions involvingOperandValueSolver
s are a little more complicated, because they specify an offset that affects its encoding in the instruction. To compute this offset, the lengths of other surrounding operands must be known. Thus, when solving a context change for a given constructor, its resolved subconstructors must be provided to the solver via theres
parameter.- Parameters:
exp
- the expression to solvegoal
- the desired output (modulo a mask) of the expressionvals
- any defined symbols (usuallyinst_start
, andinst_next
)res
- resolved subconstructors, by operand index (see method details)description
- a description to attached to the encoded solution- Returns:
- the encoded solution
- Throws:
NeedsBackfillException
- a solution may exist, but a required symbol is missing
-
getValue
protected <T extends PatternExpression> MaskedLong getValue(T exp, java.util.Map<java.lang.String,java.lang.Long> vals, java.util.Map<java.lang.Integer,java.lang.Object> res, AssemblyResolvedConstructor cur) throws NeedsBackfillException
Attempt to fold a given expression (or sub-expression) into a single constant.- Parameters:
exp
- the (sub-)expression to foldvals
- any defined symbols (usuallyinst_start
, andinst_next
)res
- resolved subconstructors, by operand index (seesolve(PatternExpression, MaskedLong, Map, Map, AssemblyResolvedConstructor, String)
)- Returns:
- the masked solution
- Throws:
NeedsBackfillException
- it may be folded, but a required symbol is missing
-
getInstructionLength
public int getInstructionLength(PatternExpression exp, java.util.Map<java.lang.Integer,java.lang.Object> res)
Determine the length of the instruction part of the encoded solution to the given expression This is used to keep operands in their appropriate position when backfilling becomes applicable. Normally, the instruction length is taken from the encoding of a solution, but if the solution cannot be determined yet, the instruction length must still be obtained. The length can be determined by finding token fields in the expression.- Parameters:
exp
- the expression, presumably containing a token fieldres
- resolved subconstructors, by operand index (seesolve(PatternExpression, MaskedLong, Map, Map, AssemblyResolvedConstructor, String)
)- Returns:
- the anticipated length, in bytes, of the instruction encoding
-
valueForResolution
public MaskedLong valueForResolution(PatternExpression exp, AssemblyResolvedConstructor rc)
Compute the value of an expression given a (possibly-intermediate) resolution- Parameters:
exp
- the expression to evaluaterc
- the resolution on which to evalute it- Returns:
- the result
-
-