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

      • RecursiveDescentSolver

        public RecursiveDescentSolver()

    • 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