diff options
Diffstat (limited to 'src/proguard/classfile/util/InstructionSequenceMatcher.java')
| -rw-r--r-- | src/proguard/classfile/util/InstructionSequenceMatcher.java | 634 |
1 files changed, 634 insertions, 0 deletions
diff --git a/src/proguard/classfile/util/InstructionSequenceMatcher.java b/src/proguard/classfile/util/InstructionSequenceMatcher.java new file mode 100644 index 0000000..8a689d5 --- /dev/null +++ b/src/proguard/classfile/util/InstructionSequenceMatcher.java @@ -0,0 +1,634 @@ +/* + * ProGuard -- shrinking, optimization, obfuscation, and preverification + * of Java bytecode. + * + * Copyright (c) 2002-2009 Eric Lafortune (eric@graphics.cornell.edu) + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ +package proguard.classfile.util; + +import proguard.classfile.*; +import proguard.classfile.attribute.CodeAttribute; +import proguard.classfile.constant.*; +import proguard.classfile.constant.visitor.ConstantVisitor; +import proguard.classfile.instruction.*; +import proguard.classfile.instruction.visitor.InstructionVisitor; + +/** + * This InstructionVisitor checks whether a given pattern instruction sequence + * occurs in the instructions that are visited. The arguments of the + * instruction sequence can be wildcards that are matched. + * + * @author Eric Lafortune + */ +public class InstructionSequenceMatcher +extends SimplifiedVisitor +implements InstructionVisitor, + ConstantVisitor +{ + /* + private static boolean DEBUG = false; + public static boolean DEBUG_MORE = false; + /*/ + private static final boolean DEBUG = false; + private static final boolean DEBUG_MORE = false; + //*/ + + public static final int X = 0x40000000; + public static final int Y = 0x40000001; + public static final int Z = 0x40000002; + + public static final int A = 0x40000003; + public static final int B = 0x40000004; + public static final int C = 0x40000005; + public static final int D = 0x40000006; + + + private final Constant[] patternConstants; + private final Instruction[] patternInstructions; + + private boolean matching; + private boolean matchingAnyWildCards; + private int patternInstructionIndex; + private final int[] matchedInstructionOffsets; + private int matchedArgumentFlags; + private final int[] matchedArguments = new int[7]; + private long matchedConstantFlags; + private final int[] matchedConstantIndices; + + // Fields acting as a parameter and a return value for visitor methods. + private Constant patternConstant; + private boolean matchingConstant; + + + /** + * Creates a new InstructionSequenceMatcher. + * @param patternConstants any constants referenced by the pattern + * instruction. + * @param patternInstructions the pattern instruction sequence. + */ + public InstructionSequenceMatcher(Constant[] patternConstants, + Instruction[] patternInstructions) + { + this.patternConstants = patternConstants; + this.patternInstructions = patternInstructions; + + matchedInstructionOffsets = new int[patternInstructions.length]; + matchedConstantIndices = new int[patternConstants.length]; + } + + + /** + * Starts matching from the first instruction again next time. + */ + public void reset() + { + patternInstructionIndex = 0; + matchedArgumentFlags = 0; + matchedConstantFlags = 0L; + } + + + public boolean isMatching() + { + return matching; + } + + + public boolean isMatchingAnyWildcards() + { + return matchingAnyWildCards; + } + + + public int instructionCount() + { + return patternInstructions.length; + } + + + public int matchedInstructionOffset(int index) + { + return matchedInstructionOffsets[index]; + } + + + public int matchedArgument(int argument) + { + int argumentIndex = argument - X; + return argumentIndex < 0 ? + argument : + matchedArguments[argumentIndex]; + } + + + public int[] matchedArguments(int[] arguments) + { + int[] matchedArguments = new int[arguments.length]; + + for (int index = 0; index < arguments.length; index++) + { + matchedArguments[index] = matchedArgument(arguments[index]); + } + + return matchedArguments; + } + + + public int matchedConstantIndex(int constantIndex) + { + int argumentIndex = constantIndex - X; + return argumentIndex < 0 ? + matchedConstantIndices[constantIndex] : + matchedArguments[argumentIndex]; + } + + + public int matchedBranchOffset(int offset, int branchOffset) + { + int argumentIndex = branchOffset - X; + return argumentIndex < 0 ? + branchOffset : + matchedArguments[argumentIndex] - offset; + } + + + public int[] matchedJumpOffsets(int offset, int[] jumpOffsets) + { + int[] matchedJumpOffsets = new int[jumpOffsets.length]; + + for (int index = 0; index < jumpOffsets.length; index++) + { + matchedJumpOffsets[index] = matchedBranchOffset(offset, + jumpOffsets[index]); + } + + return matchedJumpOffsets; + } + + + // Implementations for InstructionVisitor. + + public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the sequence. + boolean condition = + matchingOpcodes(simpleInstruction, patternInstruction) && + matchingArguments(simpleInstruction.constant, + ((SimpleInstruction)patternInstruction).constant); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + simpleInstruction); + } + + + public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the sequence. + boolean condition = + matchingOpcodes(variableInstruction, patternInstruction) && + matchingArguments(variableInstruction.variableIndex, + ((VariableInstruction)patternInstruction).variableIndex) && + matchingArguments(variableInstruction.constant, + ((VariableInstruction)patternInstruction).constant); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + variableInstruction); + } + + + public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the sequence. + boolean condition = + matchingOpcodes(constantInstruction, patternInstruction) && + matchingConstantIndices(clazz, + constantInstruction.constantIndex, + ((ConstantInstruction)patternInstruction).constantIndex) && + matchingArguments(constantInstruction.constant, + ((ConstantInstruction)patternInstruction).constant); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + constantInstruction); + } + + + public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the from + // sequence. + boolean condition = + matchingOpcodes(branchInstruction, patternInstruction) && + matchingBranchOffsets(offset, + branchInstruction.branchOffset, + ((BranchInstruction)patternInstruction).branchOffset); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + branchInstruction); + } + + + public void visitTableSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, TableSwitchInstruction tableSwitchInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the sequence. + boolean condition = + matchingOpcodes(tableSwitchInstruction, patternInstruction) && + matchingBranchOffsets(offset, + tableSwitchInstruction.defaultOffset, + ((TableSwitchInstruction)patternInstruction).defaultOffset) && + matchingArguments(tableSwitchInstruction.lowCase, + ((TableSwitchInstruction)patternInstruction).lowCase) && + matchingArguments(tableSwitchInstruction.highCase, + ((TableSwitchInstruction)patternInstruction).highCase) && + matchingJumpOffsets(offset, + tableSwitchInstruction.jumpOffsets, + ((TableSwitchInstruction)patternInstruction).jumpOffsets); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + tableSwitchInstruction); + } + + + public void visitLookUpSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, LookUpSwitchInstruction lookUpSwitchInstruction) + { + Instruction patternInstruction = patternInstructions[patternInstructionIndex]; + + // Check if the instruction matches the next instruction in the sequence. + boolean condition = + matchingOpcodes(lookUpSwitchInstruction, patternInstruction) && + matchingBranchOffsets(offset, + lookUpSwitchInstruction.defaultOffset, + ((LookUpSwitchInstruction)patternInstruction).defaultOffset) && + matchingArguments(lookUpSwitchInstruction.cases, + ((LookUpSwitchInstruction)patternInstruction).cases) && + matchingJumpOffsets(offset, + lookUpSwitchInstruction.jumpOffsets, + ((LookUpSwitchInstruction)patternInstruction).jumpOffsets); + + // Check if the instruction sequence is matching now. + checkMatch(condition, + clazz, + method, + codeAttribute, + offset, + lookUpSwitchInstruction); + } + + + // Implementations for ConstantVisitor. + + public void visitIntegerConstant(Clazz clazz, IntegerConstant integerConstant) + { + IntegerConstant integerPatternConstant = (IntegerConstant)patternConstant; + + // Compare the integer values. + matchingConstant = integerConstant.getValue() == + integerPatternConstant.getValue(); + } + + + public void visitLongConstant(Clazz clazz, LongConstant longConstant) + { + LongConstant longPatternConstant = (LongConstant)patternConstant; + + // Compare the long values. + matchingConstant = longConstant.getValue() == + longPatternConstant.getValue(); + } + + + public void visitFloatConstant(Clazz clazz, FloatConstant floatConstant) + { + FloatConstant floatPatternConstant = (FloatConstant)patternConstant; + + // Compare the float values. + matchingConstant = floatConstant.getValue() == + floatPatternConstant.getValue(); + } + + + public void visitDoubleConstant(Clazz clazz, DoubleConstant doubleConstant) + { + DoubleConstant doublePatternConstant = (DoubleConstant)patternConstant; + + // Compare the double values. + matchingConstant = doubleConstant.getValue() == + doublePatternConstant.getValue(); + } + + + public void visitStringConstant(Clazz clazz, StringConstant stringConstant) + { + StringConstant stringPatternConstant = (StringConstant)patternConstant; + + // Check the UTF-8 constant. + matchingConstant = + matchingConstantIndices(clazz, + stringConstant.u2stringIndex, + stringPatternConstant.u2stringIndex); + } + + + public void visitUtf8Constant(Clazz clazz, Utf8Constant utf8Constant) + { + Utf8Constant utf8PatternConstant = (Utf8Constant)patternConstant; + + // Compare the actual strings. + matchingConstant = utf8Constant.getString().equals( + utf8PatternConstant.getString()); + } + + + public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant) + { + RefConstant refPatternConstant = (RefConstant)patternConstant; + + // Check the class and the name and type. + matchingConstant = + matchingConstantIndices(clazz, + refConstant.getClassIndex(), + refPatternConstant.getClassIndex()) && + matchingConstantIndices(clazz, + refConstant.getNameAndTypeIndex(), + refPatternConstant.getNameAndTypeIndex()); + } + + + public void visitClassConstant(Clazz clazz, ClassConstant classConstant) + { + ClassConstant classPatternConstant = (ClassConstant)patternConstant; + + // Check the class name. + matchingConstant = + matchingConstantIndices(clazz, + classConstant.u2nameIndex, + classPatternConstant.u2nameIndex); + } + + + public void visitNameAndTypeConstant(Clazz clazz, NameAndTypeConstant nameAndTypeConstant) + { + NameAndTypeConstant typePatternConstant = (NameAndTypeConstant)patternConstant; + + // Check the name and the descriptor. + matchingConstant = + matchingConstantIndices(clazz, + nameAndTypeConstant.u2nameIndex, + typePatternConstant.u2nameIndex) && + matchingConstantIndices(clazz, + nameAndTypeConstant.u2descriptorIndex, + typePatternConstant.u2descriptorIndex); + } + + + // Small utility methods. + + private boolean matchingOpcodes(Instruction instruction1, + Instruction instruction2) + { + // Check the opcode. + return instruction1.opcode == instruction2.opcode || + instruction1.canonicalOpcode() == instruction2.opcode; + } + + + private boolean matchingArguments(int argument1, + int argument2) + { + int argumentIndex = argument2 - X; + if (argumentIndex < 0) + { + // Check the literal argument. + return argument1 == argument2; + } + else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) + { + // Store a wildcard argument. + matchedArguments[argumentIndex] = argument1; + matchedArgumentFlags |= 1 << argumentIndex; + + return true; + } + else + { + // Check the previously stored wildcard argument. + return matchedArguments[argumentIndex] == argument1; + } + } + + + private boolean matchingArguments(int[] arguments1, + int[] arguments2) + { + if (arguments1.length != arguments2.length) + { + return false; + } + + for (int index = 0; index < arguments1.length; index++) + { + if (!matchingArguments(arguments1[index], arguments2[index])) + { + return false; + } + } + + return true; + } + + + private boolean matchingConstantIndices(Clazz clazz, + int constantIndex1, + int constantIndex2) + { + if (constantIndex2 >= X) + { + // Check the constant index. + return matchingArguments(constantIndex1, constantIndex2); + } + else if ((matchedConstantFlags & (1L << constantIndex2)) == 0) + { + // Check the actual constant. + matchingConstant = false; + patternConstant = patternConstants[constantIndex2]; + + if (clazz.getTag(constantIndex1) == patternConstant.getTag()) + { + clazz.constantPoolEntryAccept(constantIndex1, this); + + if (matchingConstant) + { + // Store the constant index. + matchedConstantIndices[constantIndex2] = constantIndex1; + matchedConstantFlags |= 1L << constantIndex2; + } + } + + return matchingConstant; + } + else + { + // Check a previously stored constant index. + return matchedConstantIndices[constantIndex2] == constantIndex1; + } + } + + + private boolean matchingBranchOffsets(int offset, + int branchOffset1, + int branchOffset2) + { + int argumentIndex = branchOffset2 - X; + if (argumentIndex < 0) + { + // Check the literal argument. + return branchOffset1 == branchOffset2; + } + else if ((matchedArgumentFlags & (1 << argumentIndex)) == 0) + { + // Store a wildcard argument. + matchedArguments[argumentIndex] = offset + branchOffset1; + matchedArgumentFlags |= 1 << argumentIndex; + + return true; + } + else + { + // Check the previously stored wildcard argument. + return matchedArguments[argumentIndex] == offset + branchOffset1; + } + } + + + private boolean matchingJumpOffsets(int offset, + int[] jumpOffsets1, + int[] jumpOffsets2) + { + if (jumpOffsets1.length != jumpOffsets2.length) + { + return false; + } + + for (int index = 0; index < jumpOffsets1.length; index++) + { + if (!matchingBranchOffsets(offset, + jumpOffsets1[index], + jumpOffsets2[index])) + { + return false; + } + } + + return true; + } + + + private void checkMatch(boolean condition, + Clazz clazz, + Method method, + CodeAttribute codeAttribute, + int offset, + Instruction instruction) + { + if (DEBUG_MORE) + { + System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]: "+patternInstructions[patternInstructionIndex].toString(patternInstructionIndex)+(condition?"\t== ":"\t ")+instruction.toString(offset)); + } + + // Did the instruction match? + if (condition) + { + // Remember the offset of the matching instruction. + matchedInstructionOffsets[patternInstructionIndex] = offset; + + // Try to match the next instruction next time. + patternInstructionIndex++; + + // Did we match all instructions in the sequence? + matching = patternInstructionIndex == patternInstructions.length; + + // Did we match any wildcards along the way? + matchingAnyWildCards = matchedArgumentFlags != 0; + + if (matching) + { + if (DEBUG) + { + System.out.println("InstructionSequenceMatcher: ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]"); + for (int index = 0; index < patternInstructionIndex; index++) + { + System.out.println(" "+InstructionFactory.create(codeAttribute.code, matchedInstructionOffsets[index]).toString(matchedInstructionOffsets[index])); + } + } + + // Start matching from the first instruction again next time. + reset(); + } + } + else + { + // The instruction didn't match. + matching = false; + + // Is this a failed second instruction? + boolean retry = patternInstructionIndex == 1; + + // Start matching from the first instruction next time. + reset(); + + // Retry a failed second instruction as a first instruction. + if (retry) + { + instruction.accept(clazz, method, codeAttribute, offset, this); + } + } + } +} |