Package ghidra.app.plugin.assembler.sleigh.expr

Class RecursiveDescentSolver

java.lang.Object
ghidra.app.plugin.assembler.sleigh.expr.RecursiveDescentSolver
public class RecursiveDescentSolver extends Object
This singleton class seeks solutions to PatternExpressions

It is rather naive. It does not perform algebraic transformations. Instead, 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. There are some common cases where it is forced to solve expressions involving multiple variables. Those cases are addressed in the derivatives of AbstractBinaryExpressionSolver where the situation can be detected. One common example is field concatenation using the (A << 4) | B pattern.

TODO: Perhaps this whole mechanism ought to just be factored directly into PatternExpression.

  • Field Details

  • Constructor Details

    • RecursiveDescentSolver

      public RecursiveDescentSolver()

  • Method Details

    • getSolver

      public static RecursiveDescentSolver getSolver()
      Obtain an instance of the naive solver
      Returns:
      the singleton instance

    • register

      protected <T extends PatternExpression> void register(Class<T> tcls, AbstractExpressionSolver<T> s)
      Register a solver for a particular subclass of PatternExpression
      Parameters:
      tcls - the subclass the solver can handle
      s - the solver for the subclass

    • getRegistered

      protected <T extends PatternExpression> AbstractExpressionSolver<T> getRegistered(Class<?> tcls)
      Retrieve the registered solver for a given subclass of PatternExpression
      Parameters:
      tcls - the subclass to solve
      Returns:
      the registered solver

    • solve

      protected AssemblyResolution solve(AbstractAssemblyResolutionFactory<?,?> factory, PatternExpression exp, MaskedLong goal, Map<String,Long> vals, AssemblyResolvedPatterns cur, Set<SolverHint> hints, String description) throws NeedsBackfillException
      Solve a given expression, passing hints
      Parameters:
      exp - the expression to solve
      goal - the desired output (modulo a mask) of the expression
      vals - any defined symbols (usually inst_start, and inst_next)
      hints - describes techniques applied by calling solvers
      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

    • solve

      public AssemblyResolution solve(AbstractAssemblyResolutionFactory<?,?> factory, PatternExpression exp, MaskedLong goal, Map<String,Long> vals, AssemblyResolvedPatterns cur, String description) throws NeedsBackfillException
      Solve a given expression, given a masked-value goal

      From a simplified perspective, we need only the expression and the desired value to solve it. Generally speaking, the expression may only contain a single field, and the encoded result specifies the bits of the solved field. It must be absorbed into the overall assembly pattern.

      More realistically, these expressions may depend on quite a bit of extra information. For example, PC-relative encodings (i.e., those involving inst_start or inst_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 a NeedsBackfillException. The symbols, when known, are provided to the solver via the vals parameter.

      Parameters:
      exp - the expression to solve
      goal - the desired output (modulo a mask) of the expression
      vals - any defined symbols (usually inst_start, and inst_next)
      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, Map<String,Long> vals, AssemblyResolvedPatterns cur) throws NeedsBackfillException
      Attempt to fold a given expression (or sub-expression) into a single constant.
      Parameters:
      exp - the (sub-)expression to fold
      vals - any defined symbols (usually inst_start, and inst_next)
      Returns:
      the masked solution
      Throws:
      NeedsBackfillException - it may be folded, but a required symbol is missing

    • getInstructionLength

      public int getInstructionLength(PatternExpression exp)
      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 field
      Returns:
      the anticipated length, in bytes, of the instruction encoding

    • valueForResolution

      public MaskedLong valueForResolution(PatternExpression exp, Map<String,Long> vals, AssemblyResolvedPatterns rc)
      Compute the value of an expression given a (possibly-intermediate) resolution
      Parameters:
      exp - the expression to evaluate
      vals - values of defined symbols
      rc - the resolution on which to evaluate it
      Returns:
      the result