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

Class RecursiveDescentSolver

  • public class RecursiveDescentSolver
extends java.lang.Object
    This singleton class seeks solutions to PatternExpressions 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.

Constructor Detail

  • Method Detail

    • getSolver

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

    • 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 solve
      goal - the desired output (modulo a mask) of the expression
      vals - any defined symbols (usually inst_start, and inst_next)
      res - resolved subconstructors, by operand index (see method details)
      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
      SolverException - a solution does not exist

    • 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 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. Expressions involving OperandValues 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 the res 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)
      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
      SolverException - a solution does not exist

    • 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 fold
      vals - any defined symbols (usually inst_start, and inst_next)
      res - resolved subconstructors, by operand index (see #solve(PatternExpression, MaskedLong, Map, Map, 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 field
      res - resolved subconstructors, by operand index (see #solve(PatternExpression, MaskedLong, Map, Map, 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 evaluate
      rc - the resolution on which to evalute it
      Returns:
      the result