diff options
19 files changed, 2646 insertions, 72 deletions
diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalysisException.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalysisException.java new file mode 100644 index 00000000..673557eb --- /dev/null +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalysisException.java @@ -0,0 +1,48 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.dexlib2.analysis; + +import org.jf.util.ExceptionWithContext; + +public class AnalysisException extends ExceptionWithContext { + public AnalysisException(Throwable cause) { + super(cause); + } + + public AnalysisException(Throwable cause, String message, Object... formatArgs) { + super(cause, message, formatArgs); + } + + public AnalysisException(String message, Object... formatArgs) { + super(message, formatArgs); + } +} diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalyzedInstruction.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalyzedInstruction.java index 0533e569..3eac1012 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalyzedInstruction.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/AnalyzedInstruction.java @@ -36,6 +36,7 @@ import org.jf.dexlib2.iface.reference.MethodReference; import org.jf.dexlib2.iface.reference.Reference; import org.jf.util.ExceptionWithContext; +import javax.annotation.Nonnull; import java.util.*; public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { @@ -75,13 +76,6 @@ public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { */ protected final Instruction originalInstruction; - /** - * An analyzed instruction's "deadness" is set during analysis (i.e. MethodAnalyzer.analyzer()). A dead instruction - * is one that the analyzer never reaches. This occurs either with natural "dead code" - code that simply has no - * code path that can ever reach it, or code that follows an odexed instruction that can't be deodexed. - */ - protected boolean dead = false; - public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) { this.instruction = instruction; this.originalInstruction = instruction; @@ -141,10 +135,6 @@ public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { return originalInstruction; } - public boolean isDead() { - return dead; - } - /** * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction * that can be the first successfully executed instruction in the method. The first instruction is always a @@ -319,10 +309,12 @@ public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { return postRegisterMap.length; } + @Nonnull public RegisterType getPostInstructionRegisterType(int registerNumber) { return postRegisterMap[registerNumber]; } + @Nonnull public RegisterType getPreInstructionRegisterType(int registerNumber) { return preRegisterMap[registerNumber]; } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ArrayProto.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ArrayProto.java index fa9b5c36..6172a5c9 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ArrayProto.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ArrayProto.java @@ -32,6 +32,8 @@ package org.jf.dexlib2.analysis; import com.google.common.base.Strings; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; import org.jf.dexlib2.util.TypeUtils; import org.jf.util.ExceptionWithContext; @@ -53,6 +55,10 @@ public class ArrayProto implements TypeProto { } } + if (i == 0) { + throw new ExceptionWithContext("Invalid array type: %s", type); + } + dimensions = i; elementType = type.substring(i); } @@ -60,9 +66,25 @@ public class ArrayProto implements TypeProto { @Override public String toString() { return getType(); } @Nonnull @Override public ClassPath getClassPath() { return classPath; } @Nonnull @Override public String getType() { return makeArrayType(elementType, dimensions); } - @Nonnull public String getElementType() { return elementType; } + public int getDimensions() { return dimensions; } @Override public boolean isInterface() { return false; } + /** + * @return The base element type of this array. E.g. This would return Ljava/lang/String; for [[Ljava/lang/String; + */ + @Nonnull public String getElementType() { return elementType; } + + /** + * @return The immediate element type of this array. E.g. This would return [Ljava/lang/String; for + * [[Ljava/lang/String; + */ + @Nonnull public String getImmediateElementType() { + if (dimensions > 1) { + return makeArrayType(elementType, dimensions-1); + } + return elementType; + } + @Override public boolean implementsInterface(@Nonnull String iface) { return iface.equals("Ljava/lang/Cloneable;") || iface.equals("Ljava/io/Serializable;"); } @@ -124,4 +146,17 @@ public class ArrayProto implements TypeProto { private static String makeArrayType(@Nonnull String elementType, int dimensions) { return BRACKETS.substring(0, dimensions) + elementType; } + + + @Override + @Nullable + public FieldReference getFieldByOffset(int fieldOffset) { + return classPath.getClass("Ljava/lang/Array;").getFieldByOffset(fieldOffset); + } + + @Override + @Nullable + public MethodReference getMethodByVtableIndex(int vtableIndex) { + return classPath.getClass("Ljava/lang/Array;").getMethodByVtableIndex(vtableIndex); + } } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassPath.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassPath.java index fbd150c4..aca2edd5 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassPath.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassPath.java @@ -62,29 +62,49 @@ public class ClassPath { unknownClass = new UnknownClassProto(this); loadedClasses.put(unknownClass.getType(), unknownClass); + + loadPrimitiveType("Z"); + loadPrimitiveType("B"); + loadPrimitiveType("S"); + loadPrimitiveType("C"); + loadPrimitiveType("I"); + loadPrimitiveType("J"); + loadPrimitiveType("F"); + loadPrimitiveType("D"); + loadPrimitiveType("L"); + } + + private void loadPrimitiveType(String type) { + loadedClasses.put(type, new PrimitiveProto(this, type)); } private static DexFile getBasicClasses() { + // fallbacks for some special classes that we assume are present return new ImmutableDexFile(ImmutableSet.of( - new ReflectionClassDef(Object.class), + new ReflectionClassDef(Class.class), new ReflectionClassDef(Cloneable.class), - new ReflectionClassDef(Serializable.class))); + new ReflectionClassDef(Object.class), + new ReflectionClassDef(Serializable.class), + new ReflectionClassDef(String.class), + new ReflectionClassDef(Throwable.class))); } @Nonnull - public TypeProto getClass(String type) { - TypeProto typeProto = loadedClasses.get(type); + public TypeProto getClass(CharSequence type) { + String typeString = type.toString(); + TypeProto typeProto = loadedClasses.get(typeString); if (typeProto != null) { return typeProto; } if (type.charAt(0) == '[') { - typeProto = new ArrayProto(this, type); + typeProto = new ArrayProto(this, typeString); } else { - typeProto = new ClassProto(this, type); + typeProto = new ClassProto(this, typeString); } + // All primitive types are preloaded into loadedClasses, so we don't need to check for that here - loadedClasses.put(type, typeProto); + loadedClasses.put(typeString, typeProto); return typeProto; } @@ -102,34 +122,6 @@ public class ClassPath { } @Nonnull - public RegisterType getRegisterTypeForType(@Nonnull String type) { - switch (type.charAt(0)) { - case 'Z': - return RegisterType.getRegisterType(RegisterType.BOOLEAN, null); - case 'B': - return RegisterType.getRegisterType(RegisterType.BYTE, null); - case 'S': - return RegisterType.getRegisterType(RegisterType.SHORT, null); - case 'C': - return RegisterType.getRegisterType(RegisterType.CHAR, null); - case 'I': - return RegisterType.getRegisterType(RegisterType.INTEGER, null); - case 'F': - return RegisterType.getRegisterType(RegisterType.FLOAT, null); - case 'J': - return RegisterType.getRegisterType(RegisterType.LONG_LO, null); - case 'D': - return RegisterType.getRegisterType(RegisterType.DOUBLE_LO, null); - case 'L': - case 'U': - case '[': - return RegisterType.getRegisterType(RegisterType.REFERENCE, getClass(type)); - default: - throw new RuntimeException("Invalid type: " + type); - } - } - - @Nonnull public TypeProto getUnknownClass() { return unknownClass; } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassProto.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassProto.java index 4626587d..fdd48a1a 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassProto.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/ClassProto.java @@ -37,6 +37,9 @@ import com.google.common.collect.Sets; import org.jf.dexlib2.AccessFlags; import org.jf.dexlib2.analysis.util.TypeProtoUtils; import org.jf.dexlib2.iface.ClassDef; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; +import org.jf.util.ExceptionWithContext; import javax.annotation.Nonnull; import javax.annotation.Nullable; @@ -55,6 +58,9 @@ public class ClassProto implements TypeProto { protected boolean interfacesFullyResolved = true; public ClassProto(@Nonnull ClassPath classPath, @Nonnull String type) { + if (type.charAt(0) != 'L') { + throw new ExceptionWithContext("Cannot construct ClassProto for non reference type: %s", type); + } this.classPath = classPath; this.type = type; } @@ -264,4 +270,18 @@ public class ClassProto implements TypeProto { return classPath.getUnknownClass(); } + + @Override + @Nullable + public FieldReference getFieldByOffset(int fieldOffset) { + // TODO: implement this + return null; + } + + @Override + @Nullable + public MethodReference getMethodByVtableIndex(int vtableIndex) { + // TODO: implement this + return null; + } } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/InlineMethodResolver.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/InlineMethodResolver.java index 33e031c8..f11c54ff 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/InlineMethodResolver.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/InlineMethodResolver.java @@ -32,7 +32,6 @@ package org.jf.dexlib2.analysis; import com.google.common.collect.ImmutableList; -import org.jf.dexlib2.AccessFlags; import org.jf.dexlib2.iface.Method; import org.jf.dexlib2.iface.instruction.InlineIndexInstruction; import org.jf.dexlib2.iface.instruction.VariableRegisterInstruction; @@ -40,11 +39,17 @@ import org.jf.dexlib2.immutable.ImmutableMethod; import org.jf.dexlib2.immutable.ImmutableMethodParameter; import org.jf.dexlib2.immutable.util.ParamUtil; -public abstract class InlineMethodResolver { - private static final int STATIC = AccessFlags.STATIC.getValue(); - private static final int VIRTUAL = AccessFlags.PUBLIC.getValue(); - private static final int PRIVATE = AccessFlags.PRIVATE.getValue(); +import javax.annotation.Nonnull; +public abstract class InlineMethodResolver { + // These are the possible values for the accessFlag field on a resolved inline method + // We can't use, e.g. AccessFlags.STATIC.value, because we need them to be a constant in order to use them as cases + // in switch statements + public static final int STATIC = 0x8; // AccessFlags.STATIC.value; + public static final int VIRTUAL = 0x1; // AccessFlags.PRIVATE.value; + public static final int DIRECT = 0x2; // AccessFlags.PRIVATE.value; + + @Nonnull public static InlineMethodResolver createInlineMethodResolver(int odexVersion) { if (odexVersion == 35) { return new InlineMethodResolver_version35(); @@ -58,12 +63,14 @@ public abstract class InlineMethodResolver { protected InlineMethodResolver() { } - private static Method inlineMethod(int accessFlags, String cls, String name, String params, String returnType) { + @Nonnull + private static Method inlineMethod(int accessFlags, @Nonnull String cls, @Nonnull String name, + @Nonnull String params, @Nonnull String returnType) { ImmutableList<ImmutableMethodParameter> paramList = ImmutableList.copyOf(ParamUtil.parseParamString(params)); return new ImmutableMethod(cls, name, paramList, returnType, accessFlags, null, null); } - public abstract Method resolveExecuteInline(AnalyzedInstruction instruction); + @Nonnull public abstract Method resolveExecuteInline(@Nonnull AnalyzedInstruction instruction); private static class InlineMethodResolver_version35 extends InlineMethodResolver { @@ -89,7 +96,8 @@ public abstract class InlineMethodResolver { } @Override - public Method resolveExecuteInline(AnalyzedInstruction analyzedInstruction) { + @Nonnull + public Method resolveExecuteInline(@Nonnull AnalyzedInstruction analyzedInstruction) { InlineIndexInstruction instruction = (InlineIndexInstruction)analyzedInstruction.instruction; int inlineIndex = instruction.getInlineIndex(); @@ -118,7 +126,7 @@ public abstract class InlineMethodResolver { indexOfIIMethod = inlineMethod(VIRTUAL, "Ljava/lang/String;", "indexOf", "II", "I"); //gingerbread - fastIndexOfMethod = inlineMethod(PRIVATE, "Ljava/lang/String;", "fastIndexOf", "II", "I"); + fastIndexOfMethod = inlineMethod(DIRECT, "Ljava/lang/String;", "fastIndexOf", "II", "I"); isEmptyMethod = inlineMethod(VIRTUAL, "Ljava/lang/String;", "isEmpty", "", "Z"); inlineMethods = new Method[] { @@ -159,7 +167,8 @@ public abstract class InlineMethodResolver { } @Override - public Method resolveExecuteInline(AnalyzedInstruction analyzedInstruction) { + @Nonnull + public Method resolveExecuteInline(@Nonnull AnalyzedInstruction analyzedInstruction) { InlineIndexInstruction instruction = (InlineIndexInstruction)analyzedInstruction.instruction; int inlineIndex = instruction.getInlineIndex(); diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/MethodAnalyzer.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/MethodAnalyzer.java new file mode 100644 index 00000000..6e60a306 --- /dev/null +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/MethodAnalyzer.java @@ -0,0 +1,1671 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.dexlib2.analysis; + +import com.google.common.collect.ImmutableList; +import org.jf.dexlib2.Opcode; +import org.jf.dexlib2.iface.*; +import org.jf.dexlib2.iface.instruction.*; +import org.jf.dexlib2.iface.instruction.formats.*; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; +import org.jf.dexlib2.iface.reference.Reference; +import org.jf.dexlib2.iface.reference.TypeReference; +import org.jf.dexlib2.immutable.instruction.*; +import org.jf.dexlib2.util.MethodUtil; +import org.jf.dexlib2.util.ReferenceUtil; +import org.jf.dexlib2.util.TypeUtils; +import org.jf.util.BitSetUtils; +import org.jf.util.ExceptionWithContext; +import org.jf.util.SparseArray; + +import javax.annotation.Nonnull; +import javax.annotation.Nullable; +import java.util.BitSet; +import java.util.List; + +/** + * The MethodAnalyzer performs several functions. It "analyzes" the instructions and infers the register types + * for each register, it can deodex odexed instructions, and it can verify the bytecode. The analysis and verification + * are done in two separate passes, because the analysis has to process instructions multiple times in some cases, and + * there's no need to perform the verification multiple times, so we wait until the method is fully analyzed and then + * verify it. + * + * Before calling the analyze() method, you must have initialized the ClassPath by calling + * ClassPath.InitializeClassPath + */ +public class MethodAnalyzer { + @Nonnull private final Method method; + @Nonnull private final MethodImplementation methodImpl; + + @Nonnull private final ClassPath classPath; + @Nullable private final InlineMethodResolver inlineResolver; + + // This contains all the AnalyzedInstruction instances, keyed by the code unit address of the instruction + @Nonnull private final SparseArray<AnalyzedInstruction> analyzedInstructions = + new SparseArray<AnalyzedInstruction>(0); + + // Which instructions have been analyzed, keyed by instruction index + @Nonnull private final BitSet analyzedState; + + @Nullable private AnalysisException analysisException = null; + + //This is a dummy instruction that occurs immediately before the first real instruction. We can initialize the + //register types for this instruction to the parameter types, in order to have them propagate to all of its + //successors, e.g. the first real instruction, the first instructions in any exception handlers covering the first + //instruction, etc. + private final AnalyzedInstruction startOfMethod; + + public MethodAnalyzer(@Nonnull ClassPath classPath, @Nonnull Method method, + @Nullable InlineMethodResolver inlineResolver) { + this.classPath = classPath; + this.inlineResolver = inlineResolver; + + this.method = method; + + MethodImplementation methodImpl = method.getImplementation(); + if (methodImpl == null) { + throw new IllegalArgumentException("The method has no implementation"); + } + + this.methodImpl = methodImpl; + + //override AnalyzedInstruction and provide custom implementations of some of the methods, so that we don't + //have to handle the case this special case of instruction being null, in the main class + startOfMethod = new AnalyzedInstruction(null, -1, methodImpl.getRegisterCount()) { + public boolean setsRegister() { + return false; + } + + @Override + public boolean setsWideRegister() { + return false; + } + + @Override + public boolean setsRegister(int registerNumber) { + return false; + } + + @Override + public int getDestinationRegister() { + assert false; + return -1; + } + }; + + buildInstructionList(); + + analyzedState = new BitSet(analyzedInstructions.size()); + analyze(); + } + + private void analyze() { + Method method = this.method; + MethodImplementation methodImpl = this.methodImpl; + + int totalRegisters = methodImpl.getRegisterCount(); + int parameterRegisters = MethodUtil.getParameterRegisterCount(method); + + int nonParameterRegisters = totalRegisters - parameterRegisters; + + //if this isn't a static method, determine which register is the "this" register and set the type to the + //current class + if (!MethodUtil.isStatic(method)) { + nonParameterRegisters--; + int thisRegister = totalRegisters - parameterRegisters - 1; + + //if this is a constructor, then set the "this" register to an uninitialized reference of the current class + if (MethodUtil.isConstructor(method)) { + setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister, + RegisterType.getRegisterType(RegisterType.UNINIT, + classPath.getClass(method.getDefiningClass()))); + } else { + setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister, + RegisterType.getRegisterType(RegisterType.REFERENCE, + classPath.getClass(method.getDefiningClass()))); + } + } + + List<? extends MethodParameter> parameters = method.getParameters(); + if (parameters != null) { + RegisterType[] parameterTypes = getParameterTypes(parameters); + for (int i=0; i<parameterTypes.length; i++) { + RegisterType registerType = parameterTypes[i]; + int registerNum = (totalRegisters - parameterRegisters) + i; + setPostRegisterTypeAndPropagateChanges(startOfMethod, registerNum, registerType); + } + } + + RegisterType uninit = RegisterType.getRegisterType(RegisterType.UNINIT, null); + for (int i=0; i<nonParameterRegisters; i++) { + setPostRegisterTypeAndPropagateChanges(startOfMethod, i, uninit); + } + + BitSet instructionsToAnalyze = new BitSet(analyzedInstructions.size()); + + //make sure all of the "first instructions" are marked for processing + for (AnalyzedInstruction successor: startOfMethod.successors) { + instructionsToAnalyze.set(successor.instructionIndex); + } + + BitSet undeodexedInstructions = new BitSet(analyzedInstructions.size()); + + do { + boolean didSomething = false; + + while (!instructionsToAnalyze.isEmpty()) { + for(int i=instructionsToAnalyze.nextSetBit(0); i>=0; i=instructionsToAnalyze.nextSetBit(i+1)) { + instructionsToAnalyze.clear(i); + if (analyzedState.get(i)) { + continue; + } + AnalyzedInstruction instructionToAnalyze = analyzedInstructions.valueAt(i); + try { + if (instructionToAnalyze.originalInstruction.getOpcode().odexOnly()) { + //if we had deodexed an odex instruction in a previous pass, we might have more specific + //register information now, so let's restore the original odexed instruction and + //re-deodex it + instructionToAnalyze.restoreOdexedInstruction(); + } + + if (!analyzeInstruction(instructionToAnalyze)) { + undeodexedInstructions.set(i); + continue; + } else { + didSomething = true; + undeodexedInstructions.clear(i); + } + } catch (AnalysisException ex) { + this.analysisException = ex; + int codeAddress = getInstructionAddress(instructionToAnalyze); + ex.addContext(String.format("opcode: %s", instructionToAnalyze.instruction.getOpcode().name)); + ex.addContext(String.format("code address: %d", codeAddress)); + ex.addContext(String.format("method: %s", ReferenceUtil.getReferenceString(method))); + break; + } + + analyzedState.set(instructionToAnalyze.getInstructionIndex()); + + for (AnalyzedInstruction successor: instructionToAnalyze.successors) { + instructionsToAnalyze.set(successor.getInstructionIndex()); + } + } + if (analysisException != null) { + break; + } + } + + if (!didSomething) { + break; + } + + if (!undeodexedInstructions.isEmpty()) { + for (int i=undeodexedInstructions.nextSetBit(0); i>=0; i=undeodexedInstructions.nextSetBit(i+1)) { + instructionsToAnalyze.set(i); + } + } + } while (true); + + //Now, go through and fix up any unresolvable odex instructions. These are usually odex instructions + //that operate on a null register, and thus always throw an NPE. They can also be any sort of odex instruction + //that occurs after an unresolvable odex instruction. We deodex if possible, or replace with an + //UnresolvableOdexInstruction + for (int i=0; i< analyzedInstructions.size(); i++) { + AnalyzedInstruction analyzedInstruction = analyzedInstructions.valueAt(i); + + Instruction instruction = analyzedInstruction.getInstruction(); + + if (instruction.getOpcode().odexOnly()) { + int objectRegisterNumber; + switch (instruction.getOpcode().format) { + case Format10x: + analyzeReturnVoidBarrier(analyzedInstruction, false); + continue; + case Format21c: + case Format22c: + analyzePutGetVolatile(analyzedInstruction, false); + continue; + case Format35c: + analyzeInvokeDirectEmpty(analyzedInstruction, false); + continue; + case Format3rc: + analyzeInvokeObjectInitRange(analyzedInstruction, false); + continue; + case Format22cs: + objectRegisterNumber = ((Instruction22cs)instruction).getRegisterB(); + break; + case Format35mi: + case Format35ms: + objectRegisterNumber = ((FiveRegisterInstruction)instruction).getRegisterD(); + break; + case Format3rmi: + case Format3rms: + objectRegisterNumber = ((RegisterRangeInstruction)instruction).getStartRegister(); + break; + default: + continue; + } + + analyzedInstruction.setDeodexedInstruction( + new UnresolvedOdexInstruction(instruction, objectRegisterNumber)); + } + } + } + + private RegisterType[] getParameterTypes(@Nonnull List<? extends MethodParameter> parameters) { + RegisterType[] registerTypes = new RegisterType[parameters.size()]; + + int registerNum = 0; + for (MethodParameter parameter: parameters) { + if (TypeUtils.isWideType(parameter)) { + registerTypes[registerNum++] = RegisterType.getWideRegisterType(parameter, true); + registerTypes[registerNum++] = RegisterType.getWideRegisterType(parameter, false); + } else { + registerTypes[registerNum++] = RegisterType.getRegisterType(classPath, parameter); + } + } + + return registerTypes; + } + + public int getInstructionAddress(@Nonnull AnalyzedInstruction instruction) { + return analyzedInstructions.keyAt(instruction.instructionIndex); + } + + private void setDestinationRegisterTypeAndPropagateChanges(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType registerType) { + setPostRegisterTypeAndPropagateChanges(analyzedInstruction, analyzedInstruction.getDestinationRegister(), + registerType); + } + + private void setPostRegisterTypeAndPropagateChanges(@Nonnull AnalyzedInstruction analyzedInstruction, + int registerNumber, @Nonnull RegisterType registerType) { + + BitSet changedInstructions = new BitSet(analyzedInstructions.size()); + + if (!analyzedInstruction.setPostRegisterType(registerNumber, registerType)) { + return; + } + + propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions); + + //Using a for loop inside the while loop optimizes for the common case of the successors of an instruction + //occurring after the instruction. Any successors that occur prior to the instruction will be picked up on + //the next iteration of the while loop. + //This could also be done recursively, but in large methods it would likely cause very deep recursion, + //which requires the user to specify a larger stack size. This isn't really a problem, but it is slightly + //annoying. + while (!changedInstructions.isEmpty()) { + for (int instructionIndex=changedInstructions.nextSetBit(0); + instructionIndex>=0; + instructionIndex=changedInstructions.nextSetBit(instructionIndex+1)) { + + changedInstructions.clear(instructionIndex); + + propagateRegisterToSuccessors(analyzedInstructions.valueAt(instructionIndex), registerNumber, + changedInstructions); + } + } + + if (registerType.category == RegisterType.LONG_LO) { + checkWidePair(registerNumber, analyzedInstruction); + setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.LONG_HI_TYPE); + } else if (registerType.category == RegisterType.DOUBLE_LO) { + checkWidePair(registerNumber, analyzedInstruction); + setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.DOUBLE_HI_TYPE); + } + } + + private void propagateRegisterToSuccessors(@Nonnull AnalyzedInstruction instruction, int registerNumber, + @Nonnull BitSet changedInstructions) { + RegisterType postRegisterType = instruction.getPostInstructionRegisterType(registerNumber); + for (AnalyzedInstruction successor: instruction.successors) { + if (successor.mergeRegister(registerNumber, postRegisterType, analyzedState)) { + changedInstructions.set(successor.instructionIndex); + } + } + } + + private void buildInstructionList() { + int registerCount = methodImpl.getRegisterCount(); + + ImmutableList<Instruction> instructions = ImmutableList.copyOf(methodImpl.getInstructions()); + + analyzedInstructions.ensureCapacity(instructions.size()); + + //first, create all the instructions and populate the instructionAddresses array + int currentCodeAddress = 0; + for (int i=0; i<instructions.size(); i++) { + Instruction instruction = instructions.get(i); + analyzedInstructions.append(currentCodeAddress, new AnalyzedInstruction(instruction, i, registerCount)); + assert analyzedInstructions.indexOfKey(currentCodeAddress) == i; + currentCodeAddress += instruction.getCodeUnits(); + } + + //next, populate the exceptionHandlers array. The array item for each instruction that can throw an exception + //and is covered by a try block should be set to a list of the first instructions of each exception handler + //for the try block covering the instruction + List<? extends TryBlock> tries = methodImpl.getTryBlocks(); + int triesIndex = 0; + TryBlock currentTry = null; + AnalyzedInstruction[] currentExceptionHandlers = null; + AnalyzedInstruction[][] exceptionHandlers = new AnalyzedInstruction[instructions.size()][]; + + if (tries != null) { + for (int i=0; i< analyzedInstructions.size(); i++) { + AnalyzedInstruction instruction = analyzedInstructions.valueAt(i); + Opcode instructionOpcode = instruction.instruction.getOpcode(); + currentCodeAddress = getInstructionAddress(instruction); + + //check if we have gone past the end of the current try + if (currentTry != null) { + if (currentTry.getStartCodeAddress() + currentTry.getCodeUnitCount() <= currentCodeAddress) { + currentTry = null; + triesIndex++; + } + } + + //check if the next try is applicable yet + if (currentTry == null && triesIndex < tries.size()) { + TryBlock tryBlock = tries.get(triesIndex); + if (tryBlock.getStartCodeAddress() <= currentCodeAddress) { + assert(tryBlock.getStartCodeAddress() + tryBlock.getCodeUnitCount() > currentCodeAddress); + + currentTry = tryBlock; + + currentExceptionHandlers = buildExceptionHandlerArray(tryBlock); + } + } + + //if we're inside a try block, and the instruction can throw an exception, then add the exception handlers + //for the current instruction + if (currentTry != null && instructionOpcode.canThrow()) { + exceptionHandlers[i] = currentExceptionHandlers; + } + } + } + + //finally, populate the successors and predecessors for each instruction. We start at the fake "StartOfMethod" + //instruction and follow the execution path. Any unreachable code won't have any predecessors or successors, + //and no reachable code will have an unreachable predessor or successor + assert analyzedInstructions.size() > 0; + BitSet instructionsToProcess = new BitSet(instructions.size()); + + addPredecessorSuccessor(startOfMethod, analyzedInstructions.valueAt(0), exceptionHandlers, instructionsToProcess); + while (!instructionsToProcess.isEmpty()) { + int currentInstructionIndex = instructionsToProcess.nextSetBit(0); + instructionsToProcess.clear(currentInstructionIndex); + + AnalyzedInstruction instruction = analyzedInstructions.valueAt(currentInstructionIndex); + Opcode instructionOpcode = instruction.instruction.getOpcode(); + int instructionCodeAddress = getInstructionAddress(instruction); + + if (instruction.instruction.getOpcode().canContinue()) { + if (currentInstructionIndex == analyzedInstructions.size() - 1) { + throw new AnalysisException("Execution can continue past the last instruction"); + } + + AnalyzedInstruction nextInstruction = analyzedInstructions.valueAt(currentInstructionIndex+1); + addPredecessorSuccessor(instruction, nextInstruction, exceptionHandlers, instructionsToProcess); + } + + if (instruction.instruction instanceof OffsetInstruction) { + OffsetInstruction offsetInstruction = (OffsetInstruction)instruction.instruction; + + if (instructionOpcode == Opcode.PACKED_SWITCH || instructionOpcode == Opcode.SPARSE_SWITCH) { + SwitchPayload switchPayload = (SwitchPayload)analyzedInstructions.get(instructionCodeAddress + + offsetInstruction.getCodeOffset()).instruction; + for (SwitchElement switchElement: switchPayload.getSwitchElements()) { + AnalyzedInstruction targetInstruction = analyzedInstructions.get(instructionCodeAddress + + switchElement.getOffset()); + + addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers, + instructionsToProcess); + } + } else { + int targetAddressOffset = offsetInstruction.getCodeOffset(); + AnalyzedInstruction targetInstruction = analyzedInstructions.get(instructionCodeAddress + + targetAddressOffset); + addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers, instructionsToProcess); + } + } + } + } + + private void addPredecessorSuccessor(@Nonnull AnalyzedInstruction predecessor, + @Nonnull AnalyzedInstruction successor, + @Nonnull AnalyzedInstruction[][] exceptionHandlers, + @Nonnull BitSet instructionsToProcess) { + addPredecessorSuccessor(predecessor, successor, exceptionHandlers, instructionsToProcess, false); + } + + private void addPredecessorSuccessor(@Nonnull AnalyzedInstruction predecessor, + @Nonnull AnalyzedInstruction successor, + @Nonnull AnalyzedInstruction[][] exceptionHandlers, + @Nonnull BitSet instructionsToProcess, boolean allowMoveException) { + + if (!allowMoveException && successor.instruction.getOpcode() == Opcode.MOVE_EXCEPTION) { + throw new AnalysisException("Execution can pass from the " + predecessor.instruction.getOpcode().name + + " instruction at code address 0x" + Integer.toHexString(getInstructionAddress(predecessor)) + + " to the move-exception instruction at address 0x" + + Integer.toHexString(getInstructionAddress(successor))); + } + + if (!successor.addPredecessor(predecessor)) { + return; + } + + predecessor.addSuccessor(successor); + instructionsToProcess.set(successor.getInstructionIndex()); + + + //if the successor can throw an instruction, then we need to add the exception handlers as additional + //successors to the predecessor (and then apply this same logic recursively if needed) + //Technically, we should handle the monitor-exit instruction as a special case. The exception is actually + //thrown *after* the instruction executes, instead of "before" the instruction executes, lke for any other + //instruction. But since it doesn't modify any registers, we can treat it like any other instruction. + AnalyzedInstruction[] exceptionHandlersForSuccessor = exceptionHandlers[successor.instructionIndex]; + if (exceptionHandlersForSuccessor != null) { + //the item for this instruction in exceptionHandlersForSuccessor should only be set if this instruction + //can throw an exception + assert successor.instruction.getOpcode().canThrow(); + + for (AnalyzedInstruction exceptionHandler: exceptionHandlersForSuccessor) { + addPredecessorSuccessor(predecessor, exceptionHandler, exceptionHandlers, instructionsToProcess, true); + } + } + } + + @Nonnull + private AnalyzedInstruction[] buildExceptionHandlerArray(@Nonnull TryBlock tryBlock) { + List<? extends ExceptionHandler> exceptionHandlers = tryBlock.getExceptionHandlers(); + + AnalyzedInstruction[] handlerInstructions = new AnalyzedInstruction[exceptionHandlers.size()]; + for (int i=0; i<exceptionHandlers.size(); i++) { + handlerInstructions[i] = analyzedInstructions.get(exceptionHandlers.get(i).getHandlerCodeAddress()); + } + + return handlerInstructions; + } + + /** + * @return false if analyzedInstruction is an odex instruction that couldn't be deodexed, due to its + * object register being null + */ + private boolean analyzeInstruction(@Nonnull AnalyzedInstruction analyzedInstruction) { + Instruction instruction = analyzedInstruction.instruction; + + switch (instruction.getOpcode()) { + case NOP: + return true; + case MOVE: + case MOVE_FROM16: + case MOVE_16: + case MOVE_WIDE: + case MOVE_WIDE_FROM16: + case MOVE_WIDE_16: + case MOVE_OBJECT: + case MOVE_OBJECT_FROM16: + case MOVE_OBJECT_16: + analyzeMove(analyzedInstruction); + return true; + case MOVE_RESULT: + case MOVE_RESULT_WIDE: + case MOVE_RESULT_OBJECT: + analyzeMoveResult(analyzedInstruction); + return true; + case MOVE_EXCEPTION: + analyzeMoveException(analyzedInstruction); + return true; + case RETURN_VOID: + case RETURN: + case RETURN_WIDE: + case RETURN_OBJECT: + return true; + case RETURN_VOID_BARRIER: + analyzeReturnVoidBarrier(analyzedInstruction); + return true; + case CONST_4: + case CONST_16: + case CONST: + case CONST_HIGH16: + analyzeConst(analyzedInstruction); + return true; + case CONST_WIDE_16: + case CONST_WIDE_32: + case CONST_WIDE: + case CONST_WIDE_HIGH16: + analyzeWideConst(analyzedInstruction); + return true; + case CONST_STRING: + case CONST_STRING_JUMBO: + analyzeConstString(analyzedInstruction); + return true; + case CONST_CLASS: + analyzeConstClass(analyzedInstruction); + return true; + case MONITOR_ENTER: + case MONITOR_EXIT: + return true; + case CHECK_CAST: + analyzeCheckCast(analyzedInstruction); + return true; + case INSTANCE_OF: + analyzeInstanceOf(analyzedInstruction); + return true; + case ARRAY_LENGTH: + analyzeArrayLength(analyzedInstruction); + return true; + case NEW_INSTANCE: + analyzeNewInstance(analyzedInstruction); + return true; + case NEW_ARRAY: + analyzeNewArray(analyzedInstruction); + return true; + case FILLED_NEW_ARRAY: + case FILLED_NEW_ARRAY_RANGE: + return true; + case FILL_ARRAY_DATA: + return true; + case THROW: + case GOTO: + case GOTO_16: + case GOTO_32: + return true; + case PACKED_SWITCH: + case SPARSE_SWITCH: + return true; + case CMPL_FLOAT: + case CMPG_FLOAT: + case CMPL_DOUBLE: + case CMPG_DOUBLE: + case CMP_LONG: + analyzeFloatWideCmp(analyzedInstruction); + return true; + case IF_EQ: + case IF_NE: + case IF_LT: + case IF_GE: + case IF_GT: + case IF_LE: + case IF_EQZ: + case IF_NEZ: + case IF_LTZ: + case IF_GEZ: + case IF_GTZ: + case IF_LEZ: + return true; + case AGET: + analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case AGET_BOOLEAN: + analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.BOOLEAN_TYPE); + return true; + case AGET_BYTE: + analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.BYTE_TYPE); + return true; + case AGET_CHAR: + analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.CHAR_TYPE); + return true; + case AGET_SHORT: + analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.SHORT_TYPE); + return true; + case AGET_WIDE: + analyzeAgetWide(analyzedInstruction); + return true; + case AGET_OBJECT: + analyzeAgetObject(analyzedInstruction); + return true; + case APUT: + case APUT_BOOLEAN: + case APUT_BYTE: + case APUT_CHAR: + case APUT_SHORT: + case APUT_WIDE: + case APUT_OBJECT: + return true; + case IGET: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case IGET_BOOLEAN: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BOOLEAN_TYPE); + return true; + case IGET_BYTE: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BYTE_TYPE); + return true; + case IGET_CHAR: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.CHAR_TYPE); + return true; + case IGET_SHORT: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.SHORT_TYPE); + return true; + case IGET_WIDE: + case IGET_OBJECT: + analyzeIgetSgetWideObject(analyzedInstruction); + return true; + case IPUT: + case IPUT_BOOLEAN: + case IPUT_BYTE: + case IPUT_CHAR: + case IPUT_SHORT: + case IPUT_WIDE: + case IPUT_OBJECT: + return true; + case SGET: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case SGET_BOOLEAN: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BOOLEAN_TYPE); + return true; + case SGET_BYTE: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BYTE_TYPE); + return true; + case SGET_CHAR: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.CHAR_TYPE); + return true; + case SGET_SHORT: + analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.SHORT_TYPE); + return true; + case SGET_WIDE: + case SGET_OBJECT: + analyzeIgetSgetWideObject(analyzedInstruction); + return true; + case SPUT: + case SPUT_BOOLEAN: + case SPUT_BYTE: + case SPUT_CHAR: + case SPUT_SHORT: + case SPUT_WIDE: + case SPUT_OBJECT: + return true; + case INVOKE_VIRTUAL: + case INVOKE_SUPER: + return true; + case INVOKE_DIRECT: + analyzeInvokeDirect(analyzedInstruction); + return true; + case INVOKE_STATIC: + case INVOKE_INTERFACE: + case INVOKE_VIRTUAL_RANGE: + case INVOKE_SUPER_RANGE: + return true; + case INVOKE_DIRECT_RANGE: + analyzeInvokeDirectRange(analyzedInstruction); + return true; + case INVOKE_STATIC_RANGE: + case INVOKE_INTERFACE_RANGE: + return true; + case NEG_INT: + case NOT_INT: + analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case NEG_LONG: + case NOT_LONG: + analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE); + return true; + case NEG_FLOAT: + analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE); + return true; + case NEG_DOUBLE: + analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE); + return true; + case INT_TO_LONG: + analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE); + return true; + case INT_TO_FLOAT: + analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE); + return true; + case INT_TO_DOUBLE: + analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE); + return true; + case LONG_TO_INT: + case DOUBLE_TO_INT: + analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case LONG_TO_FLOAT: + case DOUBLE_TO_FLOAT: + analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE); + return true; + case LONG_TO_DOUBLE: + analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE); + return true; + case FLOAT_TO_INT: + analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE); + return true; + case FLOAT_TO_LONG: + analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE); + return true; + case FLOAT_TO_DOUBLE: + analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE); + return true; + case DOUBLE_TO_LONG: + analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE); + return true; + case INT_TO_BYTE: + analyzeUnaryOp(analyzedInstruction, RegisterType.BYTE_TYPE); + return true; + case INT_TO_CHAR: + analyzeUnaryOp(analyzedInstruction, RegisterType.CHAR_TYPE); + return true; + case INT_TO_SHORT: + analyzeUnaryOp(analyzedInstruction, RegisterType.SHORT_TYPE); + return true; + case ADD_INT: + case SUB_INT: + case MUL_INT: + case DIV_INT: + case REM_INT: + case SHL_INT: + case SHR_INT: + case USHR_INT: + analyzeBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false); + return true; + case AND_INT: + case OR_INT: + case XOR_INT: + analyzeBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true); + return true; + case ADD_LONG: + case SUB_LONG: + case MUL_LONG: + case DIV_LONG: + case REM_LONG: + case AND_LONG: + case OR_LONG: + case XOR_LONG: + case SHL_LONG: + case SHR_LONG: + case USHR_LONG: + analyzeBinaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE, false); + return true; + case ADD_FLOAT: + case SUB_FLOAT: + case MUL_FLOAT: + case DIV_FLOAT: + case REM_FLOAT: + analyzeBinaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE, false); + return true; + case ADD_DOUBLE: + case SUB_DOUBLE: + case MUL_DOUBLE: + case DIV_DOUBLE: + case REM_DOUBLE: + analyzeBinaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE, false); + return true; + case ADD_INT_2ADDR: + case SUB_INT_2ADDR: + case MUL_INT_2ADDR: + case DIV_INT_2ADDR: + case REM_INT_2ADDR: + case SHL_INT_2ADDR: + case SHR_INT_2ADDR: + case USHR_INT_2ADDR: + analyzeBinary2AddrOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false); + return true; + case AND_INT_2ADDR: + case OR_INT_2ADDR: + case XOR_INT_2ADDR: + analyzeBinary2AddrOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true); + return true; + case ADD_LONG_2ADDR: + case SUB_LONG_2ADDR: + case MUL_LONG_2ADDR: + case DIV_LONG_2ADDR: + case REM_LONG_2ADDR: + case AND_LONG_2ADDR: + case OR_LONG_2ADDR: + case XOR_LONG_2ADDR: + case SHL_LONG_2ADDR: + case SHR_LONG_2ADDR: + case USHR_LONG_2ADDR: + analyzeBinary2AddrOp(analyzedInstruction, RegisterType.LONG_LO_TYPE, false); + return true; + case ADD_FLOAT_2ADDR: + case SUB_FLOAT_2ADDR: + case MUL_FLOAT_2ADDR: + case DIV_FLOAT_2ADDR: + case REM_FLOAT_2ADDR: + analyzeBinary2AddrOp(analyzedInstruction, RegisterType.FLOAT_TYPE, false); + return true; + case ADD_DOUBLE_2ADDR: + case SUB_DOUBLE_2ADDR: + case MUL_DOUBLE_2ADDR: + case DIV_DOUBLE_2ADDR: + case REM_DOUBLE_2ADDR: + analyzeBinary2AddrOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE, false); + return true; + case ADD_INT_LIT16: + case RSUB_INT: + case MUL_INT_LIT16: + case DIV_INT_LIT16: + case REM_INT_LIT16: + analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false); + return true; + case AND_INT_LIT16: + case OR_INT_LIT16: + case XOR_INT_LIT16: + analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true); + return true; + case ADD_INT_LIT8: + case RSUB_INT_LIT8: + case MUL_INT_LIT8: + case DIV_INT_LIT8: + case REM_INT_LIT8: + case SHL_INT_LIT8: + analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false); + return true; + case AND_INT_LIT8: + case OR_INT_LIT8: + case XOR_INT_LIT8: + analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true); + return true; + case SHR_INT_LIT8: + analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, true), + false); + return true; + case USHR_INT_LIT8: + analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, false), + false); + return true; + + /*odexed instructions*/ + case IGET_VOLATILE: + case IPUT_VOLATILE: + case SGET_VOLATILE: + case SPUT_VOLATILE: + case IGET_OBJECT_VOLATILE: + case IGET_WIDE_VOLATILE: + case IPUT_WIDE_VOLATILE: + case SGET_WIDE_VOLATILE: + case SPUT_WIDE_VOLATILE: + analyzePutGetVolatile(analyzedInstruction); + return true; + case THROW_VERIFICATION_ERROR: + return true; + case EXECUTE_INLINE: + analyzeExecuteInline(analyzedInstruction); + return true; + case EXECUTE_INLINE_RANGE: + analyzeExecuteInlineRange(analyzedInstruction); + return true; + case INVOKE_DIRECT_EMPTY: + analyzeInvokeDirectEmpty(analyzedInstruction); + return true; + case INVOKE_OBJECT_INIT_RANGE: + analyzeInvokeObjectInitRange(analyzedInstruction); + return true; + case IGET_QUICK: + case IGET_WIDE_QUICK: + case IGET_OBJECT_QUICK: + case IPUT_QUICK: + case IPUT_WIDE_QUICK: + case IPUT_OBJECT_QUICK: + return analyzeIputIgetQuick(analyzedInstruction); + case INVOKE_VIRTUAL_QUICK: + return analyzeInvokeVirtualQuick(analyzedInstruction, false, false); + case INVOKE_SUPER_QUICK: + return analyzeInvokeVirtualQuick(analyzedInstruction, true, false); + case INVOKE_VIRTUAL_QUICK_RANGE: + return analyzeInvokeVirtualQuick(analyzedInstruction, false, true); + case INVOKE_SUPER_QUICK_RANGE: + return analyzeInvokeVirtualQuick(analyzedInstruction, true, true); + case IPUT_OBJECT_VOLATILE: + case SGET_OBJECT_VOLATILE: + case SPUT_OBJECT_VOLATILE: + analyzePutGetVolatile(analyzedInstruction); + return true; + default: + assert false; + return true; + } + } + + private static final BitSet Primitive32BitCategories = BitSetUtils.bitSetOfIndexes( + RegisterType.NULL, + RegisterType.ONE, + RegisterType.BOOLEAN, + RegisterType.BYTE, + RegisterType.POS_BYTE, + RegisterType.SHORT, + RegisterType.POS_SHORT, + RegisterType.CHAR, + RegisterType.INTEGER, + RegisterType.FLOAT); + + private static final BitSet WideLowCategories = BitSetUtils.bitSetOfIndexes( + RegisterType.LONG_LO, + RegisterType.DOUBLE_LO); + + private static final BitSet WideHighCategories = BitSetUtils.bitSetOfIndexes( + RegisterType.LONG_HI, + RegisterType.DOUBLE_HI); + + private static final BitSet ReferenceOrUninitCategories = BitSetUtils.bitSetOfIndexes( + RegisterType.NULL, + RegisterType.UNINIT_REF, + RegisterType.UNINIT_THIS, + RegisterType.REFERENCE); + + private static final BitSet BooleanCategories = BitSetUtils.bitSetOfIndexes( + RegisterType.NULL, + RegisterType.ONE, + RegisterType.BOOLEAN); + + private void analyzeMove(@Nonnull AnalyzedInstruction analyzedInstruction) { + TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction; + + RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType); + } + + private void analyzeMoveResult(@Nonnull AnalyzedInstruction analyzedInstruction) { + AnalyzedInstruction previousInstruction = analyzedInstructions.valueAt(analyzedInstruction.instructionIndex-1); + if (!previousInstruction.instruction.getOpcode().setsResult()) { + throw new AnalysisException(analyzedInstruction.instruction.getOpcode().name + " must occur after an " + + "invoke-*/fill-new-array instruction"); + } + + RegisterType resultRegisterType; + ReferenceInstruction invokeInstruction = (ReferenceInstruction)previousInstruction.instruction; + Reference reference = invokeInstruction.getReference(); + + if (reference instanceof MethodReference) { + resultRegisterType = RegisterType.getRegisterType(classPath, ((MethodReference)reference).getReturnType()); + } else { + resultRegisterType = RegisterType.getRegisterType(classPath, (TypeReference)reference); + } + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, resultRegisterType); + } + + private void analyzeMoveException(@Nonnull AnalyzedInstruction analyzedInstruction) { + int instructionAddress = getInstructionAddress(analyzedInstruction); + + RegisterType exceptionType = RegisterType.UNKNOWN_TYPE; + + for (TryBlock tryBlock: methodImpl.getTryBlocks()) { + for (ExceptionHandler handler: tryBlock.getExceptionHandlers()) { + + if (handler.getHandlerCodeAddress() == instructionAddress) { + String type = handler.getExceptionType(); + if (type == null) { + exceptionType = RegisterType.getRegisterType(RegisterType.REFERENCE, + classPath.getClass("Ljava/lang/Throwable;")); + } else { + exceptionType = RegisterType.getRegisterType(RegisterType.REFERENCE, classPath.getClass(type)) + .merge(exceptionType); + } + } + } + } + + if (exceptionType == null) { + throw new AnalysisException("move-exception must be the first instruction in an exception handler block"); + } + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType); + } + + private void analyzeReturnVoidBarrier(AnalyzedInstruction analyzedInstruction) { + analyzeReturnVoidBarrier(analyzedInstruction, true); + } + + private void analyzeReturnVoidBarrier(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) { + Instruction10x deodexedInstruction = new ImmutableInstruction10x(Opcode.RETURN_VOID); + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + + if (analyzeResult) { + analyzeInstruction(analyzedInstruction); + } + } + + private void analyzeConst(@Nonnull AnalyzedInstruction analyzedInstruction) { + NarrowLiteralInstruction instruction = (NarrowLiteralInstruction)analyzedInstruction.instruction; + + //we assume that the literal value is a valid value for the given instruction type, because it's impossible + //to store an invalid literal with the instruction. so we don't need to check the type of the literal + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, + RegisterType.getRegisterTypeForLiteral(instruction.getNarrowLiteral())); + } + + private void analyzeWideConst(@Nonnull AnalyzedInstruction analyzedInstruction) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE); + } + + private void analyzeConstString(@Nonnull AnalyzedInstruction analyzedInstruction) { + TypeProto stringClass = classPath.getClass("Ljava/lang/String;"); + RegisterType stringType = RegisterType.getRegisterType(RegisterType.REFERENCE, stringClass); + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType); + } + + private void analyzeConstClass(@Nonnull AnalyzedInstruction analyzedInstruction) { + TypeProto classClass = classPath.getClass("Ljava/lang/Class;"); + RegisterType classType = RegisterType.getRegisterType(RegisterType.REFERENCE, classClass); + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, classType); + } + + private void analyzeCheckCast(@Nonnull AnalyzedInstruction analyzedInstruction) { + ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction; + TypeReference reference = (TypeReference)instruction.getReference(); + RegisterType castRegisterType = RegisterType.getRegisterType(classPath, reference); + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, castRegisterType); + } + + private void analyzeInstanceOf(@Nonnull AnalyzedInstruction analyzedInstruction) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.BOOLEAN_TYPE); + } + + private void analyzeArrayLength(@Nonnull AnalyzedInstruction analyzedInstruction) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.INTEGER_TYPE); + } + + private void analyzeNewInstance(@Nonnull AnalyzedInstruction analyzedInstruction) { + ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction; + + int register = ((OneRegisterInstruction)analyzedInstruction.instruction).getRegisterA(); + RegisterType destRegisterType = analyzedInstruction.getPostInstructionRegisterType(register); + if (destRegisterType.category != RegisterType.UNKNOWN) { + //the post-instruction destination register will only be set if we have already analyzed this instruction + //at least once. If this is the case, then the uninit reference has already been propagated to all + //successors and nothing else needs to be done. + assert destRegisterType.category == RegisterType.UNINIT_REF; + return; + } + + TypeReference typeReference = (TypeReference)instruction.getReference(); + + RegisterType classType = RegisterType.getRegisterType(classPath, typeReference); + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, + RegisterType.getRegisterType(RegisterType.UNINIT_REF, classType.type)); + } + + private void analyzeNewArray(@Nonnull AnalyzedInstruction analyzedInstruction) { + ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction; + + TypeReference type = (TypeReference)instruction.getReference(); + if (type.getType().charAt(0) != '[') { + throw new AnalysisException("new-array used with non-array type"); + } + + RegisterType arrayType = RegisterType.getRegisterType(classPath, type); + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType); + } + + private void analyzeFloatWideCmp(@Nonnull AnalyzedInstruction analyzedInstruction) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.BYTE_TYPE); + } + + private void analyze32BitPrimitiveAget(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType registerType) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, registerType); + } + + private void analyzeAgetWide(@Nonnull AnalyzedInstruction analyzedInstruction) { + ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction; + + RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + if (arrayRegisterType.category != RegisterType.NULL) { + if (arrayRegisterType.category != RegisterType.REFERENCE || + !(arrayRegisterType.type instanceof ArrayProto)) { + throw new AnalysisException("aget-wide used with non-array register: %s", arrayRegisterType.toString()); + } + ArrayProto arrayProto = (ArrayProto)arrayRegisterType.type; + + if (arrayProto.dimensions != 1) { + throw new AnalysisException("aget-wide used with multi-dimensional array: %s", + arrayRegisterType.toString()); + } + + char arrayBaseType = arrayProto.getElementType().charAt(0); + if (arrayBaseType == 'J') { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE); + } else if (arrayBaseType == 'D') { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE); + } else { + throw new AnalysisException("aget-wide used with narrow array: %s", arrayRegisterType); + } + } else { + // If the array register is null, we can assume that the destination register was meant to be a wide type. + // This is the same behavior as dalvik's verifier + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE); + } + } + + private void analyzeAgetObject(@Nonnull AnalyzedInstruction analyzedInstruction) { + ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction; + + RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + if (arrayRegisterType.category != RegisterType.NULL) { + if (arrayRegisterType.category != RegisterType.REFERENCE || + !(arrayRegisterType.type instanceof ArrayProto)) { + throw new AnalysisException("aget-object used with non-array register: %s", + arrayRegisterType.toString()); + } + + ArrayProto arrayProto = (ArrayProto)arrayRegisterType.type; + + String elementType = arrayProto.getImmediateElementType(); + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, + RegisterType.getRegisterType(RegisterType.REFERENCE, classPath.getClass(elementType))); + } else { + // If the array register is null, we can assume that the destination register was meant to be a reference + // type, so we set the destination to NULL. This is the same behavior as dalvik's verifier + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.NULL_TYPE); + } + } + + private void analyze32BitPrimitiveIgetSget(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType registerType) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, registerType); + } + + private void analyzeIgetSgetWideObject(@Nonnull AnalyzedInstruction analyzedInstruction) { + ReferenceInstruction referenceInstruction = (ReferenceInstruction)analyzedInstruction.instruction; + + FieldReference fieldReference = (FieldReference)referenceInstruction.getReference(); + + RegisterType fieldType = RegisterType.getRegisterType(classPath, fieldReference.getType()); + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType); + } + + private void analyzeInvokeDirect(@Nonnull AnalyzedInstruction analyzedInstruction) { + FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction; + analyzeInvokeDirectCommon(analyzedInstruction, instruction.getRegisterC()); + } + + private void analyzeInvokeDirectRange(@Nonnull AnalyzedInstruction analyzedInstruction) { + RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction; + analyzeInvokeDirectCommon(analyzedInstruction, instruction.getStartRegister()); + } + + private void analyzeInvokeDirectCommon(@Nonnull AnalyzedInstruction analyzedInstruction, int objectRegister) { + //the only time that an invoke instruction changes a register type is when using invoke-direct on a + //constructor (<init>) method, which changes the uninitialized reference (and any register that the same + //uninit reference has been copied to) to an initialized reference + + ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction; + + MethodReference methodReference = (MethodReference)instruction.getReference(); + + if (!methodReference.getName().equals("<init>")) { + return; + } + + RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister); + + if (objectRegisterType.category != RegisterType.UNINIT_REF && + objectRegisterType.category != RegisterType.UNINIT_THIS) { + return; + } + + setPostRegisterTypeAndPropagateChanges(analyzedInstruction, objectRegister, + RegisterType.getRegisterType(RegisterType.REFERENCE, objectRegisterType.type)); + + for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) { + RegisterType postInstructionRegisterType = analyzedInstruction.postRegisterMap[i]; + if (postInstructionRegisterType.category == RegisterType.UNKNOWN) { + RegisterType preInstructionRegisterType = + analyzedInstruction.getPreInstructionRegisterType(i); + + if (preInstructionRegisterType.category == RegisterType.UNINIT_REF || + preInstructionRegisterType.category == RegisterType.UNINIT_THIS) { + RegisterType registerType; + if (preInstructionRegisterType == objectRegisterType) { + registerType = analyzedInstruction.postRegisterMap[objectRegister]; + } else { + registerType = preInstructionRegisterType; + } + + setPostRegisterTypeAndPropagateChanges(analyzedInstruction, i, registerType); + } + } + } + } + + private void analyzeUnaryOp(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType destRegisterType) { + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType); + } + + private void analyzeBinaryOp(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType destRegisterType, boolean checkForBoolean) { + if (checkForBoolean) { + ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction; + + RegisterType source1RegisterType = + analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + RegisterType source2RegisterType = + analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC()); + + if (BooleanCategories.get(source1RegisterType.category) && + BooleanCategories.get(source2RegisterType.category)) { + destRegisterType = RegisterType.BOOLEAN_TYPE; + } + } + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType); + } + + private void analyzeBinary2AddrOp(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType destRegisterType, boolean checkForBoolean) { + if (checkForBoolean) { + TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction; + + RegisterType source1RegisterType = + analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA()); + RegisterType source2RegisterType = + analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + + if (BooleanCategories.get(source1RegisterType.category) && + BooleanCategories.get(source2RegisterType.category)) { + destRegisterType = RegisterType.BOOLEAN_TYPE; + } + } + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType); + } + + private void analyzeLiteralBinaryOp(@Nonnull AnalyzedInstruction analyzedInstruction, + @Nonnull RegisterType destRegisterType, boolean checkForBoolean) { + if (checkForBoolean) { + TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction; + + RegisterType sourceRegisterType = + analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB()); + + if (BooleanCategories.get(sourceRegisterType.category)) { + int literal = ((NarrowLiteralInstruction)analyzedInstruction.instruction).getNarrowLiteral(); + if (literal == 0 || literal == 1) { + destRegisterType = RegisterType.BOOLEAN_TYPE; + } + } + } + + setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType); + } + + private RegisterType getDestTypeForLiteralShiftRight(@Nonnull AnalyzedInstruction analyzedInstruction, boolean signedShift) { + TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction; + + RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), + Primitive32BitCategories); + long literalShift = ((NarrowLiteralInstruction)analyzedInstruction.instruction).getNarrowLiteral(); + + if (literalShift == 0) { + return sourceRegisterType; + } + + RegisterType destRegisterType; + if (!signedShift) { + destRegisterType = RegisterType.INTEGER_TYPE; + } else { + destRegisterType = sourceRegisterType; + } + + literalShift = literalShift & 0x1f; + + switch (sourceRegisterType.category) { + case RegisterType.INTEGER: + case RegisterType.FLOAT: + if (!signedShift) { + if (literalShift > 24) { + return RegisterType.POS_BYTE_TYPE; + } + if (literalShift >= 16) { + return RegisterType.CHAR_TYPE; + } + } else { + if (literalShift >= 24) { + return RegisterType.BYTE_TYPE; + } + if (literalShift >= 16) { + return RegisterType.SHORT_TYPE; + } + } + break; + case RegisterType.SHORT: + if (signedShift && literalShift >= 8) { + return RegisterType.BYTE_TYPE; + } + break; + case RegisterType.POS_SHORT: + if (literalShift >= 8) { + return RegisterType.POS_BYTE_TYPE; + } + break; + case RegisterType.CHAR: + if (literalShift > 8) { + return RegisterType.POS_BYTE_TYPE; + } + break; + case RegisterType.BYTE: + break; + case RegisterType.POS_BYTE: + return RegisterType.POS_BYTE_TYPE; + case RegisterType.NULL: + case RegisterType.ONE: + case RegisterType.BOOLEAN: + return RegisterType.NULL_TYPE; + default: + assert false; + } + + return destRegisterType; + } + + + private void analyzeExecuteInline(@Nonnull AnalyzedInstruction analyzedInstruction) { + if (inlineResolver == null) { + throw new AnalysisException("Cannot analyze an odexed instruction unless we are deodexing"); + } + + Instruction35mi instruction = (Instruction35mi)analyzedInstruction.instruction; + Method resolvedMethod = inlineResolver.resolveExecuteInline(analyzedInstruction); + + Opcode deodexedOpcode; + switch (resolvedMethod.getAccessFlags()) { + case InlineMethodResolver.DIRECT: + deodexedOpcode = Opcode.INVOKE_DIRECT; + break; + case InlineMethodResolver.STATIC: + deodexedOpcode = Opcode.INVOKE_STATIC; + break; + case InlineMethodResolver.VIRTUAL: + deodexedOpcode = Opcode.INVOKE_VIRTUAL; + break; + default: + throw new ExceptionWithContext("Unexpected access flags on resolved inline method: %d, %s", + resolvedMethod.getAccessFlags(), ReferenceUtil.getReferenceString(resolvedMethod)); + } + + Instruction35c deodexedInstruction = new ImmutableInstruction35c(deodexedOpcode, instruction.getRegisterCount(), + instruction.getRegisterC(), instruction.getRegisterD(), instruction.getRegisterE(), + instruction.getRegisterF(), instruction.getRegisterG(), resolvedMethod); + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + analyzeInstruction(analyzedInstruction); + } + + private void analyzeExecuteInlineRange(@Nonnull AnalyzedInstruction analyzedInstruction) { + if (inlineResolver == null) { + throw new AnalysisException("Cannot analyze an odexed instruction unless we are deodexing"); + } + + Instruction3rmi instruction = (Instruction3rmi)analyzedInstruction.instruction; + Method resolvedMethod = inlineResolver.resolveExecuteInline(analyzedInstruction); + + Opcode deodexedOpcode = null; + switch (resolvedMethod.getAccessFlags()) { + case InlineMethodResolver.DIRECT: + deodexedOpcode = Opcode.INVOKE_DIRECT_RANGE; + break; + case InlineMethodResolver.STATIC: + deodexedOpcode = Opcode.INVOKE_STATIC_RANGE; + break; + case InlineMethodResolver.VIRTUAL: + deodexedOpcode = Opcode.INVOKE_VIRTUAL_RANGE; + break; + default: + assert false; + } + + Instruction3rc deodexedInstruction = new ImmutableInstruction3rc(deodexedOpcode, instruction.getRegisterCount(), + instruction.getStartRegister(), resolvedMethod); + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + analyzeInstruction(analyzedInstruction); + } + + private void analyzeInvokeDirectEmpty(@Nonnull AnalyzedInstruction analyzedInstruction) { + analyzeInvokeDirectEmpty(analyzedInstruction, true); + } + + private void analyzeInvokeDirectEmpty(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) { + Instruction35c instruction = (Instruction35c)analyzedInstruction.instruction; + + Instruction35c deodexedInstruction = new ImmutableInstruction35c(Opcode.INVOKE_DIRECT, + instruction.getRegisterCount(), instruction.getRegisterC(), instruction.getRegisterD(), + instruction.getRegisterE(), instruction.getRegisterF(), instruction.getRegisterG(), + instruction.getReference()); + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + + if (analyzeResult) { + analyzeInstruction(analyzedInstruction); + } + } + + private void analyzeInvokeObjectInitRange(@Nonnull AnalyzedInstruction analyzedInstruction) { + analyzeInvokeObjectInitRange(analyzedInstruction, true); + } + + private void analyzeInvokeObjectInitRange(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) { + Instruction3rc instruction = (Instruction3rc)analyzedInstruction.instruction; + + Instruction3rc deodexedInstruction = new ImmutableInstruction3rc(Opcode.INVOKE_DIRECT_RANGE, + instruction.getRegisterCount(), instruction.getStartRegister(), instruction.getReference()); + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + + if (analyzeResult) { + analyzeInstruction(analyzedInstruction); + } + } + + private boolean analyzeIputIgetQuick(@Nonnull AnalyzedInstruction analyzedInstruction) { + Instruction22cs instruction = (Instruction22cs)analyzedInstruction.instruction; + + int fieldOffset = instruction.getFieldOffset(); + RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), + ReferenceOrUninitCategories); + + if (objectRegisterType.category == RegisterType.NULL) { + return false; + } + + TypeProto registerTypeProto = objectRegisterType.type; + assert registerTypeProto != null; + + TypeProto classTypeProto = classPath.getClass(registerTypeProto.getType()); + FieldReference field = classTypeProto.getFieldByOffset(fieldOffset); + + if (field == null) { + throw new AnalysisException("Could not resolve the field in class %s at offset %d", + objectRegisterType.type.getType(), fieldOffset); + } + + String fieldType = field.getType(); + + Opcode opcode = OdexedFieldInstructionMapper.getAndCheckDeodexedOpcodeForOdexedOpcode(fieldType, + instruction.getOpcode()); + + Instruction22c deodexedInstruction = new ImmutableInstruction22c(opcode, (byte)instruction.getRegisterA(), + (byte)instruction.getRegisterB(), field); + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + + analyzeInstruction(analyzedInstruction); + + return true; + } + + private boolean analyzeInvokeVirtualQuick(@Nonnull AnalyzedInstruction analyzedInstruction, boolean isSuper, + boolean isRange) { + int methodIndex; + int objectRegister; + + if (isRange) { + Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction; + methodIndex = instruction.getVtableIndex(); + objectRegister = instruction.getStartRegister(); + } else { + Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction; + methodIndex = instruction.getVtableIndex(); + objectRegister = instruction.getRegisterD(); + } + + RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, objectRegister, + ReferenceOrUninitCategories); + TypeProto objectRegisterTypeProto = objectRegisterType.type; + assert objectRegisterTypeProto != null; + + if (objectRegisterType.category == RegisterType.NULL) { + return false; + } + + MethodReference resolvedMethod; + if (isSuper) { + // invoke-super is only used for the same class that we're currently in + TypeProto typeProto = classPath.getClass(method.getDefiningClass()); + TypeProto superType; + + String superclassType = typeProto.getSuperclass(); + if (superclassType != null) { + superType = classPath.getClass(superclassType); + } else { + // This is either java.lang.Object, or an UnknownClassProto + superType = typeProto; + } + + resolvedMethod = superType.getMethodByVtableIndex(methodIndex); + } else{ + resolvedMethod = objectRegisterTypeProto.getMethodByVtableIndex(methodIndex); + } + + if (resolvedMethod == null) { + throw new AnalysisException("Could not resolve the method in class %s at index %d", + objectRegisterType.type.getType(), methodIndex); + } + + Instruction deodexedInstruction; + if (isRange) { + Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction; + Opcode opcode; + if (isSuper) { + opcode = Opcode.INVOKE_SUPER_RANGE; + } else { + opcode = Opcode.INVOKE_VIRTUAL_RANGE; + } + + deodexedInstruction = new ImmutableInstruction3rc(opcode, instruction.getRegisterCount(), + instruction.getStartRegister(), resolvedMethod); + } else { + Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction; + Opcode opcode; + if (isSuper) { + opcode = Opcode.INVOKE_SUPER; + } else { + opcode = Opcode.INVOKE_VIRTUAL; + } + + deodexedInstruction = new ImmutableInstruction35c(opcode, instruction.getRegisterCount(), + instruction.getRegisterC(), instruction.getRegisterD(), instruction.getRegisterE(), + instruction.getRegisterF(), instruction.getRegisterG(), resolvedMethod); + } + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + analyzeInstruction(analyzedInstruction); + + return true; + } + + private boolean analyzePutGetVolatile(@Nonnull AnalyzedInstruction analyzedInstruction) { + return analyzePutGetVolatile(analyzedInstruction, true); + } + + private boolean analyzePutGetVolatile(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) { + FieldReference field = (FieldReference)((ReferenceInstruction)analyzedInstruction.instruction).getReference(); + String fieldType = field.getType(); + + Opcode originalOpcode = analyzedInstruction.instruction.getOpcode(); + + Opcode opcode = OdexedFieldInstructionMapper.getAndCheckDeodexedOpcodeForOdexedOpcode(fieldType, + originalOpcode); + + Instruction deodexedInstruction; + + if (originalOpcode.isOdexedStaticVolatile()) { + OneRegisterInstruction instruction = (OneRegisterInstruction)analyzedInstruction.instruction; + deodexedInstruction = new ImmutableInstruction21c(opcode, instruction.getRegisterA(), field); + } else { + TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction; + + deodexedInstruction = new ImmutableInstruction22c(opcode, instruction.getRegisterA(), + instruction.getRegisterB(), field); + } + + analyzedInstruction.setDeodexedInstruction(deodexedInstruction); + + if (analyzeResult) { + analyzeInstruction(analyzedInstruction); + } + return true; + } + + @Nonnull + private static RegisterType getAndCheckSourceRegister(@Nonnull AnalyzedInstruction analyzedInstruction, + int registerNumber, BitSet validCategories) { + assert registerNumber >= 0 && registerNumber < analyzedInstruction.postRegisterMap.length; + + RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(registerNumber); + + checkRegister(registerType, registerNumber, validCategories); + + if (validCategories == WideLowCategories) { + checkRegister(registerType, registerNumber, WideLowCategories); + checkWidePair(registerNumber, analyzedInstruction); + + RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(registerNumber + 1); + checkRegister(secondRegisterType, registerNumber+1, WideHighCategories); + } + + return registerType; + } + + private static void checkRegister(RegisterType registerType, int registerNumber, BitSet validCategories) { + if (!validCategories.get(registerType.category)) { + throw new AnalysisException(String.format("Invalid register type %s for register v%d.", + registerType.toString(), registerNumber)); + } + } + + private static void checkWidePair(int registerNumber, AnalyzedInstruction analyzedInstruction) { + if (registerNumber + 1 >= analyzedInstruction.postRegisterMap.length) { + throw new AnalysisException(String.format("v%d cannot be used as the first register in a wide register" + + "pair because it is the last register.", registerNumber)); + } + } +}
\ No newline at end of file diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/OdexedFieldInstructionMapper.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/OdexedFieldInstructionMapper.java new file mode 100644 index 00000000..49136c35 --- /dev/null +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/OdexedFieldInstructionMapper.java @@ -0,0 +1,241 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.dexlib2.analysis; + +import org.jf.dexlib2.Opcode; + +import javax.annotation.Nonnull; + +public class OdexedFieldInstructionMapper { + private static Opcode[][][][] opcodeMap = new Opcode[][][][] { + //get opcodes + new Opcode[][][] { + //iget quick + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.IGET_QUICK, + /*B*/ Opcode.IGET_QUICK, + /*S*/ Opcode.IGET_QUICK, + /*C*/ Opcode.IGET_QUICK, + /*I,F*/ Opcode.IGET_QUICK, + /*J,D*/ Opcode.IGET_WIDE_QUICK, + /*L,[*/ Opcode.IGET_OBJECT_QUICK + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.IGET_BOOLEAN, + /*B*/ Opcode.IGET_BYTE, + /*S*/ Opcode.IGET_SHORT, + /*C*/ Opcode.IGET_CHAR, + /*I,F*/ Opcode.IGET, + /*J,D*/ Opcode.IGET_WIDE, + /*L,[*/ Opcode.IGET_OBJECT + } + }, + //iget volatile + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.IGET_VOLATILE, + /*B*/ Opcode.IGET_VOLATILE, + /*S*/ Opcode.IGET_VOLATILE, + /*C*/ Opcode.IGET_VOLATILE, + /*I,F*/ Opcode.IGET_VOLATILE, + /*J,D*/ Opcode.IGET_WIDE_VOLATILE, + /*L,[*/ Opcode.IGET_OBJECT_VOLATILE + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.IGET_BOOLEAN, + /*B*/ Opcode.IGET_BYTE, + /*S*/ Opcode.IGET_SHORT, + /*C*/ Opcode.IGET_CHAR, + /*I,F*/ Opcode.IGET, + /*J,D*/ Opcode.IGET_WIDE, + /*L,[*/ Opcode.IGET_OBJECT + } + }, + //sget volatile + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.SGET_VOLATILE, + /*B*/ Opcode.SGET_VOLATILE, + /*S*/ Opcode.SGET_VOLATILE, + /*C*/ Opcode.SGET_VOLATILE, + /*I,F*/ Opcode.SGET_VOLATILE, + /*J,D*/ Opcode.SGET_WIDE_VOLATILE, + /*L,[*/ Opcode.SGET_OBJECT_VOLATILE + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.SGET_BOOLEAN, + /*B*/ Opcode.SGET_BYTE, + /*S*/ Opcode.SGET_SHORT, + /*C*/ Opcode.SGET_CHAR, + /*I,F*/ Opcode.SGET, + /*J,D*/ Opcode.SGET_WIDE, + /*L,[*/ Opcode.SGET_OBJECT + } + } + }, + //put opcodes + new Opcode[][][] { + //iput quick + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.IPUT_QUICK, + /*B*/ Opcode.IPUT_QUICK, + /*S*/ Opcode.IPUT_QUICK, + /*C*/ Opcode.IPUT_QUICK, + /*I,F*/ Opcode.IPUT_QUICK, + /*J,D*/ Opcode.IPUT_WIDE_QUICK, + /*L,[*/ Opcode.IPUT_OBJECT_QUICK + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.IPUT_BOOLEAN, + /*B*/ Opcode.IPUT_BYTE, + /*S*/ Opcode.IPUT_SHORT, + /*C*/ Opcode.IPUT_CHAR, + /*I,F*/ Opcode.IPUT, + /*J,D*/ Opcode.IPUT_WIDE, + /*L,[*/ Opcode.IPUT_OBJECT + } + }, + //iput volatile + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.IPUT_VOLATILE, + /*B*/ Opcode.IPUT_VOLATILE, + /*S*/ Opcode.IPUT_VOLATILE, + /*C*/ Opcode.IPUT_VOLATILE, + /*I,F*/ Opcode.IPUT_VOLATILE, + /*J,D*/ Opcode.IPUT_WIDE_VOLATILE, + /*L,[*/ Opcode.IPUT_OBJECT_VOLATILE + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.IPUT_BOOLEAN, + /*B*/ Opcode.IPUT_BYTE, + /*S*/ Opcode.IPUT_SHORT, + /*C*/ Opcode.IPUT_CHAR, + /*I,F*/ Opcode.IPUT, + /*J,D*/ Opcode.IPUT_WIDE, + /*L,[*/ Opcode.IPUT_OBJECT + } + }, + //sput volatile + new Opcode[][] { + //odexed + new Opcode[] { + /*Z*/ Opcode.SPUT_VOLATILE, + /*B*/ Opcode.SPUT_VOLATILE, + /*S*/ Opcode.SPUT_VOLATILE, + /*C*/ Opcode.SPUT_VOLATILE, + /*I,F*/ Opcode.SPUT_VOLATILE, + /*J,D*/ Opcode.SPUT_WIDE_VOLATILE, + /*L,[*/ Opcode.SPUT_OBJECT_VOLATILE + }, + //deodexed + new Opcode[] { + /*Z*/ Opcode.SPUT_BOOLEAN, + /*B*/ Opcode.SPUT_BYTE, + /*S*/ Opcode.SPUT_SHORT, + /*C*/ Opcode.SPUT_CHAR, + /*I,F*/ Opcode.SPUT, + /*J,D*/ Opcode.SPUT_WIDE, + /*L,[*/ Opcode.SPUT_OBJECT + } + } + } + }; + + private static int getTypeIndex(char type) { + switch (type) { + case 'Z': + return 0; + case 'B': + return 1; + case 'S': + return 2; + case 'C': + return 3; + case 'I': + case 'F': + return 4; + case 'J': + case 'D': + return 5; + case 'L': + case '[': + return 6; + default: + } + throw new RuntimeException(String.format("Unknown type %s: ", type)); + } + + private static int getOpcodeSubtype(@Nonnull Opcode opcode) { + if (opcode.isOdexedInstanceQuick()) { + return 0; + } else if (opcode.isOdexedInstanceVolatile()) { + return 1; + } else if (opcode.isOdexedStaticVolatile()) { + return 2; + } + throw new RuntimeException(String.format("Not an odexed field access opcode: %s", opcode.name)); + } + + @Nonnull + static Opcode getAndCheckDeodexedOpcodeForOdexedOpcode(@Nonnull String fieldType, @Nonnull Opcode odexedOpcode) { + int opcodeType = odexedOpcode.setsRegister()?0:1; + int opcodeSubType = getOpcodeSubtype(odexedOpcode); + int typeIndex = getTypeIndex(fieldType.charAt(0)); + + Opcode correctOdexedOpcode, deodexedOpcode; + + correctOdexedOpcode = opcodeMap[opcodeType][opcodeSubType][0][typeIndex]; + deodexedOpcode = opcodeMap[opcodeType][opcodeSubType][1][typeIndex]; + + if (correctOdexedOpcode != odexedOpcode) { + throw new AnalysisException(String.format("Incorrect field type \"%s\" for %s", fieldType, + odexedOpcode.name)); + } + + return deodexedOpcode; + } +} + + diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/PrimitiveProto.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/PrimitiveProto.java index c0b17270..06ab8e17 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/PrimitiveProto.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/PrimitiveProto.java @@ -31,6 +31,8 @@ package org.jf.dexlib2.analysis; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; import org.jf.util.ExceptionWithContext; import javax.annotation.Nonnull; @@ -54,4 +56,16 @@ public class PrimitiveProto implements TypeProto { @Nonnull @Override public TypeProto getCommonSuperclass(@Nonnull TypeProto other) { throw new ExceptionWithContext("Cannot call getCommonSuperclass on PrimitiveProto"); } + + @Override + @Nullable + public FieldReference getFieldByOffset(int fieldOffset) { + return null; + } + + @Override + @Nullable + public MethodReference getMethodByVtableIndex(int vtableIndex) { + return null; + } } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/RegisterType.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/RegisterType.java index df3d03e1..f21ebbf2 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/RegisterType.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/RegisterType.java @@ -185,7 +185,7 @@ public class RegisterType { public static final RegisterType CONFLICTED_TYPE = new RegisterType(CONFLICTED, null); @Nonnull - public static RegisterType getWideRegisterTypeForType(@Nonnull String type, boolean firstRegister) { + public static RegisterType getWideRegisterType(@Nonnull CharSequence type, boolean firstRegister) { switch (type.charAt(0)) { case 'J': if (firstRegister) { @@ -204,34 +204,63 @@ public class RegisterType { } } - public static RegisterType getRegisterTypeForLiteral(long literalValue) { + @Nonnull + public static RegisterType getRegisterType(@Nonnull ClassPath classPath, @Nonnull CharSequence type) { + switch (type.charAt(0)) { + case 'Z': + return BOOLEAN_TYPE; + case 'B': + return BYTE_TYPE; + case 'S': + return SHORT_TYPE; + case 'C': + return CHAR_TYPE; + case 'I': + return INTEGER_TYPE; + case 'F': + return FLOAT_TYPE; + case 'J': + return LONG_LO_TYPE; + case 'D': + return DOUBLE_LO_TYPE; + case 'L': + case '[': + return getRegisterType(REFERENCE, classPath.getClass(type)); + default: + throw new ExceptionWithContext("Invalid type: " + type); + } + } + + @Nonnull + public static RegisterType getRegisterTypeForLiteral(int literalValue) { if (literalValue < -32768) { - return getRegisterType(INTEGER, null); + return INTEGER_TYPE; } if (literalValue < -128) { - return getRegisterType(SHORT, null); + return SHORT_TYPE; } if (literalValue < 0) { - return getRegisterType(BYTE, null); + return BYTE_TYPE; } if (literalValue == 0) { - return getRegisterType(NULL, null); + return NULL_TYPE; } if (literalValue == 1) { - return getRegisterType(ONE, null); + return ONE_TYPE; } if (literalValue < 128) { - return getRegisterType(POS_BYTE, null); + return POS_BYTE_TYPE; } if (literalValue < 32768) { - return getRegisterType(POS_SHORT, null); + return POS_SHORT_TYPE; } if (literalValue < 65536) { - return getRegisterType(CHAR, null); + return CHAR_TYPE; } - return getRegisterType(INTEGER, null); + return INTEGER_TYPE; } + @Nonnull public RegisterType merge(@Nonnull RegisterType other) { if (other == this) { return this; @@ -263,6 +292,10 @@ public class RegisterType { return RegisterType.getRegisterType(mergedCategory, mergedType); } + // TODO: consider making TypeProto extend/implement RegisterType? + // TODO: add a getReferenceRegisterType convenience method + + @Nonnull public static RegisterType getRegisterType(byte category, @Nullable TypeProto typeProto) { switch (category) { case UNKNOWN: diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/TypeProto.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/TypeProto.java index 3e3bb9a5..f6db2399 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/TypeProto.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/TypeProto.java @@ -31,6 +31,9 @@ package org.jf.dexlib2.analysis; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; + import javax.annotation.Nonnull; import javax.annotation.Nullable; @@ -41,4 +44,6 @@ public interface TypeProto { boolean implementsInterface(@Nonnull String iface); @Nullable String getSuperclass(); @Nonnull TypeProto getCommonSuperclass(@Nonnull TypeProto other); + @Nullable FieldReference getFieldByOffset(int fieldOffset); + @Nullable MethodReference getMethodByVtableIndex(int vtableIndex); } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnknownClassProto.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnknownClassProto.java index c6e91802..38256fbe 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnknownClassProto.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnknownClassProto.java @@ -31,6 +31,9 @@ package org.jf.dexlib2.analysis; +import org.jf.dexlib2.iface.reference.FieldReference; +import org.jf.dexlib2.iface.reference.MethodReference; + import javax.annotation.Nonnull; import javax.annotation.Nullable; @@ -63,4 +66,16 @@ public class UnknownClassProto implements TypeProto { // use the otherwise used U prefix for an unknown/unresolvable class return "Ujava/lang/Object;"; } + + @Override + @Nullable + public FieldReference getFieldByOffset(int fieldOffset) { + return classPath.getClass("Ljava/lang/Object;").getFieldByOffset(fieldOffset); + } + + @Override + @Nullable + public MethodReference getMethodByVtableIndex(int vtableIndex) { + return classPath.getClass("Ljava/lang/Object;").getMethodByVtableIndex(vtableIndex); + } } diff --git a/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnresolvedOdexInstruction.java b/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnresolvedOdexInstruction.java new file mode 100644 index 00000000..2df9b858 --- /dev/null +++ b/dexlib2/src/main/java/org/jf/dexlib2/analysis/UnresolvedOdexInstruction.java @@ -0,0 +1,64 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.dexlib2.analysis; + +import org.jf.dexlib2.Format; +import org.jf.dexlib2.Opcode; +import org.jf.dexlib2.iface.instruction.Instruction; + +/** + * This represents a "fixed" odexed instruction, where the object register is always null and so the correct type + * can't be determined. Typically, these are replaced by an equivalent instruction that would have the same + * effect (namely, an NPE) + */ +public class UnresolvedOdexInstruction implements Instruction { + public final Instruction originalInstruction; + //the register number that holds the (null) reference type that the instruction operates on + public final int objectRegisterNum; + + public UnresolvedOdexInstruction(Instruction originalInstruction, int objectRegisterNumber) { + this.originalInstruction = originalInstruction; + this.objectRegisterNum = objectRegisterNumber; + } + + public Format getFormat() { + return Format.UnresolvedOdexInstruction; + } + + @Override public Opcode getOpcode() { + return originalInstruction.getOpcode(); + } + + @Override public int getCodeUnits() { + return originalInstruction.getCodeUnits(); + } +} diff --git a/dexlib2/src/main/java/org/jf/dexlib2/iface/TryBlock.java b/dexlib2/src/main/java/org/jf/dexlib2/iface/TryBlock.java index 7979e88f..7d25f66b 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/iface/TryBlock.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/iface/TryBlock.java @@ -62,7 +62,7 @@ public interface TryBlock { * A list of the exception handlers associated with this try block. * * The exception handlers in the returned list will all have a unique type, including at most 1 with no type, which - * is the catch-all handler. Catch-all handler is always the last item in the list. + * is the catch-all handler. If present, the catch-all handler is always the last item in the list. * * @return A list of ExceptionHandler objects */ diff --git a/dexlib2/src/main/java/org/jf/dexlib2/immutable/util/ParamUtil.java b/dexlib2/src/main/java/org/jf/dexlib2/immutable/util/ParamUtil.java index c843375a..9886e1a7 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/immutable/util/ParamUtil.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/immutable/util/ParamUtil.java @@ -33,10 +33,11 @@ package org.jf.dexlib2.immutable.util; import org.jf.dexlib2.immutable.ImmutableMethodParameter; +import javax.annotation.Nonnull; import java.util.Iterator; public class ParamUtil { - private static int findTypeEnd(String str, int index) { + private static int findTypeEnd(@Nonnull String str, int index) { char c = str.charAt(index); switch (c) { case 'Z': @@ -60,7 +61,8 @@ public class ParamUtil { } } - public static Iterable<ImmutableMethodParameter> parseParamString(final String params) { + @Nonnull + public static Iterable<ImmutableMethodParameter> parseParamString(@Nonnull final String params) { return new Iterable<ImmutableMethodParameter>() { @Override public Iterator<ImmutableMethodParameter> iterator() { return new Iterator<ImmutableMethodParameter>() { diff --git a/dexlib2/src/main/java/org/jf/dexlib2/util/MethodUtil.java b/dexlib2/src/main/java/org/jf/dexlib2/util/MethodUtil.java index cc77c06c..09c39d2b 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/util/MethodUtil.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/util/MethodUtil.java @@ -49,6 +49,14 @@ public final class MethodUtil { return AccessFlags.STATIC.isSet(method.getAccessFlags()); } + public static boolean isConstructor(@Nonnull MethodReference methodReference) { + return methodReference.getName().equals("<init>"); + } + + public static int getParameterRegisterCount(@Nonnull Method method) { + return getParameterRegisterCount(method, MethodUtil.isStatic(method)); + } + public static int getParameterRegisterCount(@Nonnull MethodReference methodRef, boolean isStatic) { int regCount = 0; for (CharSequence paramType: methodRef.getParameterTypes()) { diff --git a/dexlib2/src/main/java/org/jf/dexlib2/util/TypeUtils.java b/dexlib2/src/main/java/org/jf/dexlib2/util/TypeUtils.java index 2f77228f..02890b87 100644 --- a/dexlib2/src/main/java/org/jf/dexlib2/util/TypeUtils.java +++ b/dexlib2/src/main/java/org/jf/dexlib2/util/TypeUtils.java @@ -31,12 +31,20 @@ package org.jf.dexlib2.util; +import org.jf.dexlib2.iface.reference.TypeReference; + +import javax.annotation.Nonnull; + public final class TypeUtils { - public static boolean isWideType(String type) { + public static boolean isWideType(@Nonnull String type) { char c = type.charAt(0); return c == 'J' || c == 'D'; } + public static boolean isWideType(@Nonnull TypeReference type) { + return isWideType(type.getType()); + } + public static boolean isPrimitiveType(String type) { return type.length() == 1; } diff --git a/util/src/main/java/org/jf/util/BitSetUtils.java b/util/src/main/java/org/jf/util/BitSetUtils.java new file mode 100644 index 00000000..777a857a --- /dev/null +++ b/util/src/main/java/org/jf/util/BitSetUtils.java @@ -0,0 +1,44 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.util; + +import java.util.BitSet; + +public class BitSetUtils { + public static BitSet bitSetOfIndexes(int... indexes) { + BitSet bitSet = new BitSet(); + for (int index: indexes) { + bitSet.set(index); + } + return bitSet; + } +} diff --git a/util/src/main/java/org/jf/util/SparseArray.java b/util/src/main/java/org/jf/util/SparseArray.java new file mode 100644 index 00000000..474e21c7 --- /dev/null +++ b/util/src/main/java/org/jf/util/SparseArray.java @@ -0,0 +1,373 @@ +/* + * Copyright 2013, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.jf.util; + +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +/** + * SparseArrays map integers to Objects. Unlike a normal array of Objects, + * there can be gaps in the indices. It is intended to be more efficient + * than using a HashMap to map Integers to Objects. + */ +public class SparseArray<E> { + private static final Object DELETED = new Object(); + private boolean mGarbage = false; + + /** + * Creates a new SparseArray containing no mappings. + */ + public SparseArray() { + this(10); + } + + /** + * Creates a new SparseArray containing no mappings that will not + * require any additional memory allocation to store the specified + * number of mappings. + */ + public SparseArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new Object[initialCapacity]; + mSize = 0; + } + + /** + * Gets the Object mapped from the specified key, or <code>null</code> + * if no such mapping has been made. + */ + public E get(int key) { + return get(key, null); + } + + /** + * Gets the Object mapped from the specified key, or the specified Object + * if no such mapping has been made. + */ + public E get(int key, E valueIfKeyNotFound) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i < 0 || mValues[i] == DELETED) { + return valueIfKeyNotFound; + } else { + return (E) mValues[i]; + } + } + + /** + * Removes the mapping from the specified key, if there was any. + */ + public void delete(int key) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i >= 0) { + if (mValues[i] != DELETED) { + mValues[i] = DELETED; + mGarbage = true; + } + } + } + + /** + * Alias for {@link #delete(int)}. + */ + public void remove(int key) { + delete(key); + } + + private void gc() { + // Log.e("SparseArray", "gc start with " + mSize); + + int n = mSize; + int o = 0; + int[] keys = mKeys; + Object[] values = mValues; + + for (int i = 0; i < n; i++) { + Object val = values[i]; + + if (val != DELETED) { + if (i != o) { + keys[o] = keys[i]; + values[o] = val; + } + + o++; + } + } + + mGarbage = false; + mSize = o; + + // Log.e("SparseArray", "gc end with " + mSize); + } + + /** + * Adds a mapping from the specified key to the specified value, + * replacing the previous mapping from the specified key if there + * was one. + */ + public void put(int key, E value) { + int i = binarySearch(mKeys, 0, mSize, key); + + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + + if (i < mSize && mValues[i] == DELETED) { + mKeys[i] = key; + mValues[i] = value; + return; + } + + if (mGarbage && mSize >= mKeys.length) { + gc(); + + // Search again because indices may have changed. + i = ~binarySearch(mKeys, 0, mSize, key); + } + + if (mSize >= mKeys.length) { + int n = Math.max(mSize + 1, mKeys.length * 2); + + int[] nkeys = new int[n]; + Object[] nvalues = new Object[n]; + + // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); + System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); + System.arraycopy(mValues, 0, nvalues, 0, mValues.length); + + mKeys = nkeys; + mValues = nvalues; + } + + if (mSize - i != 0) { + // Log.e("SparseArray", "move " + (mSize - i)); + System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); + System.arraycopy(mValues, i, mValues, i + 1, mSize - i); + } + + mKeys[i] = key; + mValues[i] = value; + mSize++; + } + } + + /** + * Returns the number of key-value mappings that this SparseArray + * currently stores. + */ + public int size() { + if (mGarbage) { + gc(); + } + + return mSize; + } + + /** + * Given an index in the range <code>0...size()-1</code>, returns + * the key from the <code>index</code>th key-value mapping that this + * SparseArray stores. + */ + public int keyAt(int index) { + if (mGarbage) { + gc(); + } + + return mKeys[index]; + } + + /** + * Given an index in the range <code>0...size()-1</code>, returns + * the value from the <code>index</code>th key-value mapping that this + * SparseArray stores. + */ + public E valueAt(int index) { + if (mGarbage) { + gc(); + } + + return (E) mValues[index]; + } + + /** + * Given an index in the range <code>0...size()-1</code>, sets a new + * value for the <code>index</code>th key-value mapping that this + * SparseArray stores. + */ + public void setValueAt(int index, E value) { + if (mGarbage) { + gc(); + } + + mValues[index] = value; + } + + /** + * Returns the index for which {@link #keyAt} would return the + * specified key, or a negative number if the specified + * key is not mapped. + */ + public int indexOfKey(int key) { + if (mGarbage) { + gc(); + } + + return binarySearch(mKeys, 0, mSize, key); + } + + /** + * Returns an index for which {@link #valueAt} would return the + * specified key, or a negative number if no keys map to the + * specified value. + * Beware that this is a linear search, unlike lookups by key, + * and that multiple keys can map to the same value and this will + * find only one of them. + */ + public int indexOfValue(E value) { + if (mGarbage) { + gc(); + } + + for (int i = 0; i < mSize; i++) + if (mValues[i] == value) + return i; + + return -1; + } + + /** + * Removes all key-value mappings from this SparseArray. + */ + public void clear() { + int n = mSize; + Object[] values = mValues; + + for (int i = 0; i < n; i++) { + values[i] = null; + } + + mSize = 0; + mGarbage = false; + } + + /** + * Puts a key/value pair into the array, optimizing for the case where + * the key is greater than all existing keys in the array. + */ + public void append(int key, E value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + + if (mGarbage && mSize >= mKeys.length) { + gc(); + } + + int pos = mSize; + if (pos >= mKeys.length) { + int n = Math.max(pos + 1, mKeys.length * 2); + + int[] nkeys = new int[n]; + Object[] nvalues = new Object[n]; + + // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); + System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); + System.arraycopy(mValues, 0, nvalues, 0, mValues.length); + + mKeys = nkeys; + mValues = nvalues; + } + + mKeys[pos] = key; + mValues[pos] = value; + mSize = pos + 1; + } + + /** + * Increases the size of the underlying storage if needed, to ensure that it can + * hold the specified number of items without having to allocate additional memory + * @param capacity the number of items + */ + public void ensureCapacity(int capacity) { + if (mGarbage && mSize >= mKeys.length) { + gc(); + } + + if (mKeys.length < capacity) { + int[] nkeys = new int[capacity]; + Object[] nvalues = new Object[capacity]; + + System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); + System.arraycopy(mValues, 0, nvalues, 0, mValues.length); + + mKeys = nkeys; + mValues = nvalues; + } + } + + private static int binarySearch(int[] a, int start, int len, int key) { + int high = start + len, low = start - 1, guess; + + while (high - low > 1) { + guess = (high + low) / 2; + + if (a[guess] < key) + low = guess; + else + high = guess; + } + + if (high == start + len) + return ~(start + len); + else if (a[high] == key) + return high; + else + return ~high; + } + + /** + * @return a read-only list of the values in this SparseArray which are in ascending order, based on their + * associated key + */ + public List<E> getValues() { + return Collections.unmodifiableList(Arrays.asList((E[])mValues)); + } + + private int[] mKeys; + private Object[] mValues; + private int mSize; +} |