tools/dexfuzz/src/dexfuzz/program/CodeTranslator.java - platform/art - Git at Google

 /*
  * Copyright (C) 2014 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package dexfuzz.program;

 import dexfuzz.Log;
 import dexfuzz.rawdex.CodeItem;
 import dexfuzz.rawdex.EncodedCatchHandler;
 import dexfuzz.rawdex.EncodedTypeAddrPair;
 import dexfuzz.rawdex.Instruction;
 import dexfuzz.rawdex.Opcode;
 import dexfuzz.rawdex.TryItem;
 import dexfuzz.rawdex.formats.ContainsTarget;
 import dexfuzz.rawdex.formats.RawInsnHelper;

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;

 /**
  * Translates from a CodeItem (the raw list of Instructions) to MutatableCode
  * (graph of Instructions, using MInsns and subclasses) and vice-versa.
  */
 public class CodeTranslator {

   /**
    * Given a raw DEX file's CodeItem, produce a MutatableCode object, that CodeMutators
    * are designed to operate on.
    * @param codeItemIdx Used to make sure the correct CodeItem is updated later after mutation.
    * @return A new MutatableCode object, which contains all relevant information
    *         obtained from the CodeItem.
    */
   public MutatableCode codeItemToMutatableCode(Program program, CodeItem codeItem,
       int codeItemIdx, int mutatableCodeIdx) {
     Log.debug("Translating CodeItem " + codeItemIdx
         + " (" + codeItem.meta.methodName + ") to MutatableCode");

     MutatableCode mutatableCode = new MutatableCode(program);

     codeItem.registerMutatableCode(mutatableCode);

     mutatableCode.name = codeItem.meta.methodName;
     mutatableCode.shorty = codeItem.meta.shorty;
     mutatableCode.isStatic = codeItem.meta.isStatic;

     mutatableCode.codeItemIdx = codeItemIdx;

     mutatableCode.mutatableCodeIdx = mutatableCodeIdx;

     mutatableCode.registersSize = codeItem.registersSize;
     mutatableCode.insSize = codeItem.insSize;
     mutatableCode.outsSize = codeItem.outsSize;
     mutatableCode.triesSize = codeItem.triesSize;

     // Temporary map from bytecode offset -> instruction.
     Map<Integer,MInsn> insnLocationMap = new HashMap<Integer,MInsn>();

     List<Instruction> inputInsns = codeItem.insns;

     // Create the MInsns.
     int loc = 0;
     for (Instruction insn : inputInsns) {
       MInsn mInsn = null;

       if (isInstructionSwitch(insn)) {
         mInsn = new MSwitchInsn();
       } else if (isInstructionBranch(insn)) {
         mInsn = new MBranchInsn();
       } else if (isInstructionFillArrayData(insn)) {
         mInsn = new MInsnWithData();
       } else {
         mInsn = new MInsn();
       }

       mInsn.insn = insn;

       // Populate the temporary map.
       insnLocationMap.put(loc, mInsn);

       // Populate the proper list of mutatable instructions.
       mutatableCode.addInstructionToEnd(mInsn);

       // Calculate the offsets for each instruction.
       mInsn.location = loc;
       mInsn.locationUpdated = false;

       loc += mInsn.insn.getSize();
     }

     // Now make branch/switch instructions point at the right target instructions.
     for (MInsn mInsn : mutatableCode.getInstructions()) {
       if (mInsn instanceof MSwitchInsn) {
         readSwitchInstruction((MSwitchInsn) mInsn, insnLocationMap);
       } else if (mInsn instanceof MInsnWithData) {
         ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
         int targetLoc = mInsn.location + (int) containsTarget.getTarget(mInsn.insn);
         ((MInsnWithData)mInsn).dataTarget = insnLocationMap.get(targetLoc);
         if (((MInsnWithData)mInsn).dataTarget == null) {
           Log.errorAndQuit("Bad offset calculation in data-target insn");
         }
       } else if (mInsn instanceof MBranchInsn) {
         ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
         int targetLoc = mInsn.location + (int) containsTarget.getTarget(mInsn.insn);
         ((MBranchInsn)mInsn).target = insnLocationMap.get(targetLoc);
         if (((MBranchInsn)mInsn).target == null) {
           Log.errorAndQuit("Bad offset calculation in branch insn");
         }
       }
     }

     // Now create try blocks.
     if (mutatableCode.triesSize > 0) {
       readTryBlocks(codeItem, mutatableCode, insnLocationMap);
     }

     return mutatableCode;
   }

   /**
    * Given a MutatableCode item that may have been mutated, update the original CodeItem
    * correctly, to allow valid DEX to be written back to the output file.
    */
   public void mutatableCodeToCodeItem(CodeItem codeItem, MutatableCode mutatableCode) {
     Log.debug("Translating MutatableCode " + mutatableCode.name
         + " to CodeItem " + mutatableCode.codeItemIdx);

     // We must first align any data instructions at the end of the code
     // before we recalculate any offsets.
     // This also updates their sizes...
     alignDataInstructions(mutatableCode);

     // Validate that the tracked locations for instructions are valid.
     // Also mark locations as no longer being updated.
     int loc = 0;
     for (MInsn mInsn : mutatableCode.getInstructions()) {
       if (mInsn.insn.justRaw) {
         // All just_raw instructions need alignment!
         if ((loc % 2) != 0) {
           loc++;
         }
       }
       if (mInsn.location != loc) {
         Log.errorAndQuit(String.format("%s does not have expected location 0x%x",
             mInsn, loc));
       }
       mInsn.locationUpdated = false;
       loc += mInsn.insn.getSize();
     }

     // This new list will be attached to the CodeItem at the end...
     List<Instruction> outputInsns = new LinkedList<Instruction>();

     // Go through our new list of MInsns, adding them to the new
     // list of instructions that will be attached to the CodeItem.
     // Also recalculate offsets for branches.
     for (MInsn mInsn : mutatableCode.getInstructions()) {
       if (mInsn instanceof MSwitchInsn) {
         updateSwitchInstruction((MSwitchInsn)mInsn, mutatableCode);
       } else if (mInsn instanceof MInsnWithData) {
         MInsn target = ((MInsnWithData) mInsn).dataTarget;
         int dataOffset = target.location - mInsn.location;
         ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
         containsTarget.setTarget(mInsn.insn, dataOffset);
       } else if (mInsn instanceof MBranchInsn) {
         MInsn target = ((MBranchInsn) mInsn).target;
         int branchOffset = target.location - mInsn.location;
         ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
         containsTarget.setTarget(mInsn.insn, branchOffset);
       }
       outputInsns.add(mInsn.insn);
     }

     // Calculate the new insns_size.
     int newInsnsSize = 0;
     for (Instruction insn : outputInsns) {
       newInsnsSize += insn.getSize();
     }

     if (mutatableCode.triesSize > 0) {
       updateTryBlocks(codeItem, mutatableCode);
     }

     codeItem.insnsSize = newInsnsSize;
     codeItem.insns = outputInsns;
     codeItem.registersSize = mutatableCode.registersSize;
     codeItem.insSize = mutatableCode.insSize;
     codeItem.outsSize = mutatableCode.outsSize;
     codeItem.triesSize = mutatableCode.triesSize;
   }

   /**
    * The TryItem specifies an offset into the EncodedCatchHandlerList for a given CodeItem,
    * but we only have an array of the EncodedCatchHandlers that the List contains.
    * This function produces a map that offers a way to find out the index into our array,
    * from the try handler's offset.
    */
   private Map<Short,Integer> createTryHandlerOffsetToIndexMap(CodeItem codeItem) {
     // Create a sorted set of offsets.
     List<Short> uniqueOffsets = new ArrayList<Short>();
     for (TryItem tryItem : codeItem.tries) {
       int index = 0;
       while (true) {
         if ((index == uniqueOffsets.size())
             || (uniqueOffsets.get(index) > tryItem.handlerOff)) {
           // First condition means we're at the end of the set (or we're inserting
           //   into an empty set)
           // Second condition means that the offset belongs here
           // ...so insert it here, pushing the element currently in this position to the
           //    right, if it exists
           uniqueOffsets.add(index, tryItem.handlerOff);
           break;
         } else if (uniqueOffsets.get(index) == tryItem.handlerOff) {
           // We've already seen it, and we're making a set, not a list.
           break;
         } else {
           // Keep searching.
           index++;
         }
       }
     }
     // Now we have an (implicit) index -> offset mapping!

     // Now create the reverse mapping.
     Map<Short,Integer> offsetIndexMap = new HashMap<Short,Integer>();
     for (int i = 0; i < uniqueOffsets.size(); i++) {
       offsetIndexMap.put(uniqueOffsets.get(i), i);
     }

     return offsetIndexMap;
   }

   private void readTryBlocks(CodeItem codeItem, MutatableCode mutatableCode,
       Map<Integer,MInsn> insnLocationMap) {
     mutatableCode.mutatableTries = new LinkedList<MTryBlock>();

     Map<Short,Integer> offsetIndexMap = createTryHandlerOffsetToIndexMap(codeItem);

     // Read each TryItem into a MutatableTryBlock.
     for (TryItem tryItem : codeItem.tries) {
       MTryBlock mTryBlock = new MTryBlock();

       // Get the MInsns that form the start and end of the try block.
       int startLocation = tryItem.startAddr;
       mTryBlock.startInsn = insnLocationMap.get(startLocation);
       int endLocation = tryItem.startAddr + tryItem.insnCount;
       mTryBlock.endInsn = insnLocationMap.get(endLocation);

       // Sanity checks.
       if (mTryBlock.startInsn == null) {
         Log.errorAndQuit(String.format(
             "Couldn't find a mutatable insn at start offset 0x%x",
             startLocation));
       }
       if (mTryBlock.endInsn == null) {
         Log.errorAndQuit(String.format(
             "Couldn't find a mutatable insn at end offset 0x%x",
             endLocation));
       }

       // Get the EncodedCatchHandler.
       int handlerIdx = offsetIndexMap.get(tryItem.handlerOff);
       EncodedCatchHandler encodedCatchHandler = codeItem.handlers.list[handlerIdx];

       // Do we have a catch all? If so, associate the MInsn that's there.
       if (encodedCatchHandler.size <= 0) {
         mTryBlock.catchAllHandler =
             insnLocationMap.get(encodedCatchHandler.catchAllAddr);
         // Sanity check.
         if (mTryBlock.catchAllHandler == null) {
           Log.errorAndQuit(
               String.format("Couldn't find a mutatable insn at catch-all offset 0x%x",
                   encodedCatchHandler.catchAllAddr));
         }
       }
       // Do we have explicitly-typed handlers? This will remain empty if not.
       mTryBlock.handlers = new LinkedList<MInsn>();

       // Associate all the explicitly-typed handlers.
       for (int i = 0; i < Math.abs(encodedCatchHandler.size); i++) {
         EncodedTypeAddrPair handler = encodedCatchHandler.handlers[i];
         MInsn handlerInsn = insnLocationMap.get(handler.addr);
         // Sanity check.
         if (handlerInsn == null) {
           Log.errorAndQuit(String.format(
               "Couldn't find a mutatable instruction at handler offset 0x%x",
               handler.addr));
         }
         mTryBlock.handlers.add(handlerInsn);
       }

       // Now finally add the new MutatableTryBlock into this MutatableCode's list!
       mutatableCode.mutatableTries.add(mTryBlock);
     }
   }

   private void updateTryBlocks(CodeItem codeItem, MutatableCode mutatableCode) {

     // TODO: Support ability to add extra try blocks/handlers?

     for (MTryBlock mTryBlock : mutatableCode.mutatableTries) {
       if (mTryBlock.startInsn.location > mTryBlock.endInsn.location) {
         // Mutation has put this try block's end insn before its start insn. Fix this.
         MInsn tempInsn = mTryBlock.startInsn;
         mTryBlock.startInsn = mTryBlock.endInsn;
         mTryBlock.endInsn = tempInsn;
       }
     }

     // First, manipulate the try blocks if they overlap.
     for (int i = 0; i < mutatableCode.mutatableTries.size() - 1; i++) {
       MTryBlock first = mutatableCode.mutatableTries.get(i);
       MTryBlock second = mutatableCode.mutatableTries.get(i + 1);

       // Do they overlap?
       if (first.endInsn.location > second.startInsn.location) {

         Log.debug("Found overlap in TryBlocks, moving 2nd TryBlock...");
         Log.debug("1st TryBlock goes from " + first.startInsn + " to "  + first.endInsn);
         Log.debug("2nd TryBlock goes from " + second.startInsn + " to "  + second.endInsn);

         // Find the first instruction that comes after that does not overlap
         // with the first try block.
         MInsn newInsn = second.startInsn;
         int ptr = mutatableCode.getInstructionIndex(newInsn);
         while (first.endInsn.location > newInsn.location) {
           ptr++;
           newInsn = mutatableCode.getInstructionAt(ptr);
         }
         second.startInsn = newInsn;

         Log.debug("Now 2nd TryBlock goes from " + second.startInsn + " to "  + second.endInsn);
       }
     }

     Map<Short,Integer> offsetIndexMap = createTryHandlerOffsetToIndexMap(codeItem);

     int tryItemIdx = 0;
     for (MTryBlock mTryBlock : mutatableCode.mutatableTries) {
       TryItem tryItem = codeItem.tries[tryItemIdx];

       tryItem.startAddr = mTryBlock.startInsn.location;
       tryItem.insnCount =
           (short) (mTryBlock.endInsn.location - mTryBlock.startInsn.location);

       // Get the EncodedCatchHandler.
       EncodedCatchHandler encodedCatchHandler =
           codeItem.handlers.list[offsetIndexMap.get(tryItem.handlerOff)];

       if (encodedCatchHandler.size <= 0) {
         encodedCatchHandler.catchAllAddr = mTryBlock.catchAllHandler.location;
       }
       for (int i = 0; i < Math.abs(encodedCatchHandler.size); i++) {
         MInsn handlerInsn = mTryBlock.handlers.get(i);
         EncodedTypeAddrPair handler = encodedCatchHandler.handlers[i];
         handler.addr = handlerInsn.location;
       }
       tryItemIdx++;
     }
   }

   /**
    * Given a switch instruction, find the associated data's raw[] form, and update
    * the targets of the switch instruction to point to the correct instructions.
    */
   private void readSwitchInstruction(MSwitchInsn switchInsn,
       Map<Integer,MInsn> insnLocationMap) {
     // Find the data.
     ContainsTarget containsTarget = (ContainsTarget) switchInsn.insn.info.format;
     int dataLocation = switchInsn.location + (int) containsTarget.getTarget(switchInsn.insn);
     switchInsn.dataTarget = insnLocationMap.get(dataLocation);
     if (switchInsn.dataTarget == null) {
       Log.errorAndQuit("Bad offset calculation for data target in switch insn");
     }

     // Now read the data.
     Instruction dataInsn = switchInsn.dataTarget.insn;

     int rawPtr = 2;

     int targetsSize = (int) RawInsnHelper.getUnsignedShortFromTwoBytes(dataInsn.rawBytes, rawPtr);
     rawPtr += 2;

     int[] keys = new int[targetsSize];
     int[] targets = new int[targetsSize];

     if (dataInsn.rawType == 1) {
       switchInsn.packed = true;
       // Dealing with a packed-switch.
       // Read the first key.
       keys[0] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes, rawPtr);
       rawPtr += 4;
       // Calculate the rest of the keys.
       for (int i = 1; i < targetsSize; i++) {
         keys[i] = keys[i - 1] + 1;
       }
     } else if (dataInsn.rawType == 2) {
       // Dealing with a sparse-switch.
       // Read all of the keys.
       for (int i = 0; i < targetsSize; i++) {
         keys[i] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes,
             rawPtr);
         rawPtr += 4;
       }
     }

     // Now read the targets.
     for (int i = 0; i < targetsSize; i++) {
       targets[i] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes,
           rawPtr);
       rawPtr += 4;
     }

     // Store the keys.
     switchInsn.keys = keys;

     // Convert our targets[] offsets into pointers to MInsns.
     for (int target : targets) {
       int targetLocation = switchInsn.location + target;
       MInsn targetInsn = insnLocationMap.get(targetLocation);
       switchInsn.targets.add(targetInsn);
       if (targetInsn == null) {
         Log.errorAndQuit("Bad offset calculation for target in switch insn");
       }
     }
   }

   /**
    * Given a mutatable switch instruction, which may have had some of its branch
    * targets moved, update all the target offsets in the raw[] form of the instruction.
    */
   private void updateSwitchInstruction(MSwitchInsn switchInsn, MutatableCode mutatableCode) {
     // Update the offset to the data instruction
     MInsn dataTarget = switchInsn.dataTarget;
     int dataOffset = dataTarget.location - switchInsn.location;
     ContainsTarget containsTarget = (ContainsTarget) switchInsn.insn.info.format;
     containsTarget.setTarget(switchInsn.insn, dataOffset);

     int targetsSize = switchInsn.targets.size();

     int[] keys = switchInsn.keys;
     int[] targets = new int[targetsSize];

     // Calculate the new offsets.
     int targetIdx = 0;
     for (MInsn target : switchInsn.targets) {
       targets[targetIdx] = target.location - switchInsn.location;
       targetIdx++;
     }

     // Now write the data back to the raw bytes.
     Instruction dataInsn = switchInsn.dataTarget.insn;

     int rawPtr = 2;

     // Write out the size.
     RawInsnHelper.writeUnsignedShortToTwoBytes(dataInsn.rawBytes, rawPtr, targetsSize);
     rawPtr += 2;

     // Write out the keys.
     if (switchInsn.packed) {
       // Only write out one key - the first.
       RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, keys[0]);
       rawPtr += 4;
     } else {
       // Write out all the keys.
       for (int i = 0; i < targetsSize; i++) {
         RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, keys[i]);
         rawPtr += 4;
       }
     }

     // Write out all the targets.
     for (int i = 0; i < targetsSize; i++) {
       RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, targets[i]);
       rawPtr += 4;
     }
   }

   /**
    * After mutation, data instructions may no longer be 4-byte aligned.
    * If this is the case, insert nops to align them all.
    * This makes a number of assumptions about data currently:
    * - data is always at the end of method insns
    * - all data instructions are stored contiguously
    */
   private void alignDataInstructions(MutatableCode mutatableCode) {
     // Find all the switch data instructions.
     List<MInsn> dataInsns = new ArrayList<MInsn>();

     // Update raw sizes of the data instructions as well.
     for (MInsn mInsn : mutatableCode.getInstructions()) {
       if (mInsn instanceof MSwitchInsn) {
         // Update the raw size of the instruction.
         MSwitchInsn switchInsn = (MSwitchInsn) mInsn;
         int targetsSize = switchInsn.targets.size();
         Instruction dataInsn = switchInsn.dataTarget.insn;
         if (switchInsn.packed) {
           dataInsn.rawSize = (targetsSize * 2) + 4;
         } else {
           dataInsn.rawSize = (targetsSize * 4) + 2;
         }
         dataInsns.add(switchInsn.dataTarget);
       } else if (mInsn instanceof MInsnWithData) {
         MInsnWithData insnWithData =
             (MInsnWithData) mInsn;
         dataInsns.add(insnWithData.dataTarget);
       }
     }

     // Only need to align switch data instructions if there are any!
     if (!dataInsns.isEmpty()) {

       Log.debug("Found data instructions, checking alignment...");

       // Sort data_insns by location.
       Collections.sort(dataInsns, new Comparator<MInsn>() {
         @Override
         public int compare(MInsn first, MInsn second) {
           if (first.location < second.location) {
             return -1;
           } else if (first.location > second.location) {
             return 1;
           }
           return 0;
         }
       });

       boolean performedAlignment = false;

       // Go through all the data insns, and insert an alignment nop if they're unaligned.
       for (MInsn dataInsn : dataInsns) {
         if (dataInsn.location % 2 != 0) {
           Log.debug("Aligning data instruction with a nop.");
           int alignmentNopIdx = mutatableCode.getInstructionIndex(dataInsn);
           MInsn nop = new MInsn();
           nop.insn = new Instruction();
           nop.insn.info = Instruction.getOpcodeInfo(Opcode.NOP);
           mutatableCode.insertInstructionAt(nop, alignmentNopIdx);
           performedAlignment = true;
         }
       }

       if (!performedAlignment) {
         Log.debug("Alignment okay.");
       }
     }
   }

   /**
    * Determine if a particular instruction is a branch instruction, based on opcode.
    */
   private boolean isInstructionBranch(Instruction insn) {
     Opcode opcode = insn.info.opcode;
     if (Opcode.isBetween(opcode, Opcode.IF_EQ, Opcode.IF_LEZ)
         || Opcode.isBetween(opcode, Opcode.GOTO, Opcode.GOTO_32)) {
       return true;
     }
     return false;
   }

   /**
    * Determine if a particular instruction is a switch instruction, based on opcode.
    */
   private boolean isInstructionSwitch(Instruction insn) {
     Opcode opcode = insn.info.opcode;
     if (Opcode.isBetween(opcode, Opcode.PACKED_SWITCH, Opcode.SPARSE_SWITCH)) {
       return true;
     }
     return false;
   }

   private boolean isInstructionFillArrayData(Instruction insn) {
     return (insn.info.opcode == Opcode.FILL_ARRAY_DATA);
   }
 }
	/*
	* Copyright (C) 2014 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package dexfuzz.program;

	import dexfuzz.Log;
	import dexfuzz.rawdex.CodeItem;
	import dexfuzz.rawdex.EncodedCatchHandler;
	import dexfuzz.rawdex.EncodedTypeAddrPair;
	import dexfuzz.rawdex.Instruction;
	import dexfuzz.rawdex.Opcode;
	import dexfuzz.rawdex.TryItem;
	import dexfuzz.rawdex.formats.ContainsTarget;
	import dexfuzz.rawdex.formats.RawInsnHelper;

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;

	/**
	* Translates from a CodeItem (the raw list of Instructions) to MutatableCode
	* (graph of Instructions, using MInsns and subclasses) and vice-versa.
	*/
	public class CodeTranslator {

	/**
	* Given a raw DEX file's CodeItem, produce a MutatableCode object, that CodeMutators
	* are designed to operate on.
	* @param codeItemIdx Used to make sure the correct CodeItem is updated later after mutation.
	* @return A new MutatableCode object, which contains all relevant information
	* obtained from the CodeItem.
	*/
	public MutatableCode codeItemToMutatableCode(Program program, CodeItem codeItem,
	int codeItemIdx, int mutatableCodeIdx) {
	Log.debug("Translating CodeItem " + codeItemIdx
	+ " (" + codeItem.meta.methodName + ") to MutatableCode");

	MutatableCode mutatableCode = new MutatableCode(program);

	codeItem.registerMutatableCode(mutatableCode);

	mutatableCode.name = codeItem.meta.methodName;
	mutatableCode.shorty = codeItem.meta.shorty;
	mutatableCode.isStatic = codeItem.meta.isStatic;

	mutatableCode.codeItemIdx = codeItemIdx;

	mutatableCode.mutatableCodeIdx = mutatableCodeIdx;

	mutatableCode.registersSize = codeItem.registersSize;
	mutatableCode.insSize = codeItem.insSize;
	mutatableCode.outsSize = codeItem.outsSize;
	mutatableCode.triesSize = codeItem.triesSize;

	// Temporary map from bytecode offset -> instruction.
	Map<Integer,MInsn> insnLocationMap = new HashMap<Integer,MInsn>();

	List<Instruction> inputInsns = codeItem.insns;

	// Create the MInsns.
	int loc = 0;
	for (Instruction insn : inputInsns) {
	MInsn mInsn = null;

	if (isInstructionSwitch(insn)) {
	mInsn = new MSwitchInsn();
	} else if (isInstructionBranch(insn)) {
	mInsn = new MBranchInsn();
	} else if (isInstructionFillArrayData(insn)) {
	mInsn = new MInsnWithData();
	} else {
	mInsn = new MInsn();
	}

	mInsn.insn = insn;

	// Populate the temporary map.
	insnLocationMap.put(loc, mInsn);

	// Populate the proper list of mutatable instructions.
	mutatableCode.addInstructionToEnd(mInsn);

	// Calculate the offsets for each instruction.
	mInsn.location = loc;
	mInsn.locationUpdated = false;

	loc += mInsn.insn.getSize();
	}

	// Now make branch/switch instructions point at the right target instructions.
	for (MInsn mInsn : mutatableCode.getInstructions()) {
	if (mInsn instanceof MSwitchInsn) {
	readSwitchInstruction((MSwitchInsn) mInsn, insnLocationMap);
	} else if (mInsn instanceof MInsnWithData) {
	ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
	int targetLoc = mInsn.location + (int) containsTarget.getTarget(mInsn.insn);
	((MInsnWithData)mInsn).dataTarget = insnLocationMap.get(targetLoc);
	if (((MInsnWithData)mInsn).dataTarget == null) {
	Log.errorAndQuit("Bad offset calculation in data-target insn");
	}
	} else if (mInsn instanceof MBranchInsn) {
	ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
	int targetLoc = mInsn.location + (int) containsTarget.getTarget(mInsn.insn);
	((MBranchInsn)mInsn).target = insnLocationMap.get(targetLoc);
	if (((MBranchInsn)mInsn).target == null) {
	Log.errorAndQuit("Bad offset calculation in branch insn");
	}
	}
	}

	// Now create try blocks.
	if (mutatableCode.triesSize > 0) {
	readTryBlocks(codeItem, mutatableCode, insnLocationMap);
	}

	return mutatableCode;
	}

	/**
	* Given a MutatableCode item that may have been mutated, update the original CodeItem
	* correctly, to allow valid DEX to be written back to the output file.
	*/
	public void mutatableCodeToCodeItem(CodeItem codeItem, MutatableCode mutatableCode) {
	Log.debug("Translating MutatableCode " + mutatableCode.name
	+ " to CodeItem " + mutatableCode.codeItemIdx);

	// We must first align any data instructions at the end of the code
	// before we recalculate any offsets.
	// This also updates their sizes...
	alignDataInstructions(mutatableCode);

	// Validate that the tracked locations for instructions are valid.
	// Also mark locations as no longer being updated.
	int loc = 0;
	for (MInsn mInsn : mutatableCode.getInstructions()) {
	if (mInsn.insn.justRaw) {
	// All just_raw instructions need alignment!
	if ((loc % 2) != 0) {
	loc++;
	}
	}
	if (mInsn.location != loc) {
	Log.errorAndQuit(String.format("%s does not have expected location 0x%x",
	mInsn, loc));
	}
	mInsn.locationUpdated = false;
	loc += mInsn.insn.getSize();
	}

	// This new list will be attached to the CodeItem at the end...
	List<Instruction> outputInsns = new LinkedList<Instruction>();

	// Go through our new list of MInsns, adding them to the new
	// list of instructions that will be attached to the CodeItem.
	// Also recalculate offsets for branches.
	for (MInsn mInsn : mutatableCode.getInstructions()) {
	if (mInsn instanceof MSwitchInsn) {
	updateSwitchInstruction((MSwitchInsn)mInsn, mutatableCode);
	} else if (mInsn instanceof MInsnWithData) {
	MInsn target = ((MInsnWithData) mInsn).dataTarget;
	int dataOffset = target.location - mInsn.location;
	ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
	containsTarget.setTarget(mInsn.insn, dataOffset);
	} else if (mInsn instanceof MBranchInsn) {
	MInsn target = ((MBranchInsn) mInsn).target;
	int branchOffset = target.location - mInsn.location;
	ContainsTarget containsTarget = (ContainsTarget) mInsn.insn.info.format;
	containsTarget.setTarget(mInsn.insn, branchOffset);
	}
	outputInsns.add(mInsn.insn);
	}

	// Calculate the new insns_size.
	int newInsnsSize = 0;
	for (Instruction insn : outputInsns) {
	newInsnsSize += insn.getSize();
	}

	if (mutatableCode.triesSize > 0) {
	updateTryBlocks(codeItem, mutatableCode);
	}

	codeItem.insnsSize = newInsnsSize;
	codeItem.insns = outputInsns;
	codeItem.registersSize = mutatableCode.registersSize;
	codeItem.insSize = mutatableCode.insSize;
	codeItem.outsSize = mutatableCode.outsSize;
	codeItem.triesSize = mutatableCode.triesSize;
	}

	/**
	* The TryItem specifies an offset into the EncodedCatchHandlerList for a given CodeItem,
	* but we only have an array of the EncodedCatchHandlers that the List contains.
	* This function produces a map that offers a way to find out the index into our array,
	* from the try handler's offset.
	*/
	private Map<Short,Integer> createTryHandlerOffsetToIndexMap(CodeItem codeItem) {
	// Create a sorted set of offsets.
	List<Short> uniqueOffsets = new ArrayList<Short>();
	for (TryItem tryItem : codeItem.tries) {
	int index = 0;
	while (true) {
	if ((index == uniqueOffsets.size())
	\|\| (uniqueOffsets.get(index) > tryItem.handlerOff)) {
	// First condition means we're at the end of the set (or we're inserting
	// into an empty set)
	// Second condition means that the offset belongs here
	// ...so insert it here, pushing the element currently in this position to the
	// right, if it exists
	uniqueOffsets.add(index, tryItem.handlerOff);
	break;
	} else if (uniqueOffsets.get(index) == tryItem.handlerOff) {
	// We've already seen it, and we're making a set, not a list.
	break;
	} else {
	// Keep searching.
	index++;
	}
	}
	}
	// Now we have an (implicit) index -> offset mapping!

	// Now create the reverse mapping.
	Map<Short,Integer> offsetIndexMap = new HashMap<Short,Integer>();
	for (int i = 0; i < uniqueOffsets.size(); i++) {
	offsetIndexMap.put(uniqueOffsets.get(i), i);
	}

	return offsetIndexMap;
	}

	private void readTryBlocks(CodeItem codeItem, MutatableCode mutatableCode,
	Map<Integer,MInsn> insnLocationMap) {
	mutatableCode.mutatableTries = new LinkedList<MTryBlock>();

	Map<Short,Integer> offsetIndexMap = createTryHandlerOffsetToIndexMap(codeItem);

	// Read each TryItem into a MutatableTryBlock.
	for (TryItem tryItem : codeItem.tries) {
	MTryBlock mTryBlock = new MTryBlock();

	// Get the MInsns that form the start and end of the try block.
	int startLocation = tryItem.startAddr;
	mTryBlock.startInsn = insnLocationMap.get(startLocation);
	int endLocation = tryItem.startAddr + tryItem.insnCount;
	mTryBlock.endInsn = insnLocationMap.get(endLocation);

	// Sanity checks.
	if (mTryBlock.startInsn == null) {
	Log.errorAndQuit(String.format(
	"Couldn't find a mutatable insn at start offset 0x%x",
	startLocation));
	}
	if (mTryBlock.endInsn == null) {
	Log.errorAndQuit(String.format(
	"Couldn't find a mutatable insn at end offset 0x%x",
	endLocation));
	}

	// Get the EncodedCatchHandler.
	int handlerIdx = offsetIndexMap.get(tryItem.handlerOff);
	EncodedCatchHandler encodedCatchHandler = codeItem.handlers.list[handlerIdx];

	// Do we have a catch all? If so, associate the MInsn that's there.
	if (encodedCatchHandler.size <= 0) {
	mTryBlock.catchAllHandler =
	insnLocationMap.get(encodedCatchHandler.catchAllAddr);
	// Sanity check.
	if (mTryBlock.catchAllHandler == null) {
	Log.errorAndQuit(
	String.format("Couldn't find a mutatable insn at catch-all offset 0x%x",
	encodedCatchHandler.catchAllAddr));
	}
	}
	// Do we have explicitly-typed handlers? This will remain empty if not.
	mTryBlock.handlers = new LinkedList<MInsn>();

	// Associate all the explicitly-typed handlers.
	for (int i = 0; i < Math.abs(encodedCatchHandler.size); i++) {
	EncodedTypeAddrPair handler = encodedCatchHandler.handlers[i];
	MInsn handlerInsn = insnLocationMap.get(handler.addr);
	// Sanity check.
	if (handlerInsn == null) {
	Log.errorAndQuit(String.format(
	"Couldn't find a mutatable instruction at handler offset 0x%x",
	handler.addr));
	}
	mTryBlock.handlers.add(handlerInsn);
	}

	// Now finally add the new MutatableTryBlock into this MutatableCode's list!
	mutatableCode.mutatableTries.add(mTryBlock);
	}
	}

	private void updateTryBlocks(CodeItem codeItem, MutatableCode mutatableCode) {

	// TODO: Support ability to add extra try blocks/handlers?

	for (MTryBlock mTryBlock : mutatableCode.mutatableTries) {
	if (mTryBlock.startInsn.location > mTryBlock.endInsn.location) {
	// Mutation has put this try block's end insn before its start insn. Fix this.
	MInsn tempInsn = mTryBlock.startInsn;
	mTryBlock.startInsn = mTryBlock.endInsn;
	mTryBlock.endInsn = tempInsn;
	}
	}

	// First, manipulate the try blocks if they overlap.
	for (int i = 0; i < mutatableCode.mutatableTries.size() - 1; i++) {
	MTryBlock first = mutatableCode.mutatableTries.get(i);
	MTryBlock second = mutatableCode.mutatableTries.get(i + 1);

	// Do they overlap?
	if (first.endInsn.location > second.startInsn.location) {

	Log.debug("Found overlap in TryBlocks, moving 2nd TryBlock...");
	Log.debug("1st TryBlock goes from " + first.startInsn + " to " + first.endInsn);
	Log.debug("2nd TryBlock goes from " + second.startInsn + " to " + second.endInsn);

	// Find the first instruction that comes after that does not overlap
	// with the first try block.
	MInsn newInsn = second.startInsn;
	int ptr = mutatableCode.getInstructionIndex(newInsn);
	while (first.endInsn.location > newInsn.location) {
	ptr++;
	newInsn = mutatableCode.getInstructionAt(ptr);
	}
	second.startInsn = newInsn;

	Log.debug("Now 2nd TryBlock goes from " + second.startInsn + " to " + second.endInsn);
	}
	}

	Map<Short,Integer> offsetIndexMap = createTryHandlerOffsetToIndexMap(codeItem);

	int tryItemIdx = 0;
	for (MTryBlock mTryBlock : mutatableCode.mutatableTries) {
	TryItem tryItem = codeItem.tries[tryItemIdx];

	tryItem.startAddr = mTryBlock.startInsn.location;
	tryItem.insnCount =
	(short) (mTryBlock.endInsn.location - mTryBlock.startInsn.location);

	// Get the EncodedCatchHandler.
	EncodedCatchHandler encodedCatchHandler =
	codeItem.handlers.list[offsetIndexMap.get(tryItem.handlerOff)];

	if (encodedCatchHandler.size <= 0) {
	encodedCatchHandler.catchAllAddr = mTryBlock.catchAllHandler.location;
	}
	for (int i = 0; i < Math.abs(encodedCatchHandler.size); i++) {
	MInsn handlerInsn = mTryBlock.handlers.get(i);
	EncodedTypeAddrPair handler = encodedCatchHandler.handlers[i];
	handler.addr = handlerInsn.location;
	}
	tryItemIdx++;
	}
	}

	/**
	* Given a switch instruction, find the associated data's raw[] form, and update
	* the targets of the switch instruction to point to the correct instructions.
	*/
	private void readSwitchInstruction(MSwitchInsn switchInsn,
	Map<Integer,MInsn> insnLocationMap) {
	// Find the data.
	ContainsTarget containsTarget = (ContainsTarget) switchInsn.insn.info.format;
	int dataLocation = switchInsn.location + (int) containsTarget.getTarget(switchInsn.insn);
	switchInsn.dataTarget = insnLocationMap.get(dataLocation);
	if (switchInsn.dataTarget == null) {
	Log.errorAndQuit("Bad offset calculation for data target in switch insn");
	}

	// Now read the data.
	Instruction dataInsn = switchInsn.dataTarget.insn;

	int rawPtr = 2;

	int targetsSize = (int) RawInsnHelper.getUnsignedShortFromTwoBytes(dataInsn.rawBytes, rawPtr);
	rawPtr += 2;

	int[] keys = new int[targetsSize];
	int[] targets = new int[targetsSize];

	if (dataInsn.rawType == 1) {
	switchInsn.packed = true;
	// Dealing with a packed-switch.
	// Read the first key.
	keys[0] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes, rawPtr);
	rawPtr += 4;
	// Calculate the rest of the keys.
	for (int i = 1; i < targetsSize; i++) {
	keys[i] = keys[i - 1] + 1;
	}
	} else if (dataInsn.rawType == 2) {
	// Dealing with a sparse-switch.
	// Read all of the keys.
	for (int i = 0; i < targetsSize; i++) {
	keys[i] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes,
	rawPtr);
	rawPtr += 4;
	}
	}

	// Now read the targets.
	for (int i = 0; i < targetsSize; i++) {
	targets[i] = (int) RawInsnHelper.getUnsignedIntFromFourBytes(dataInsn.rawBytes,
	rawPtr);
	rawPtr += 4;
	}

	// Store the keys.
	switchInsn.keys = keys;

	// Convert our targets[] offsets into pointers to MInsns.
	for (int target : targets) {
	int targetLocation = switchInsn.location + target;
	MInsn targetInsn = insnLocationMap.get(targetLocation);
	switchInsn.targets.add(targetInsn);
	if (targetInsn == null) {
	Log.errorAndQuit("Bad offset calculation for target in switch insn");
	}
	}
	}

	/**
	* Given a mutatable switch instruction, which may have had some of its branch
	* targets moved, update all the target offsets in the raw[] form of the instruction.
	*/
	private void updateSwitchInstruction(MSwitchInsn switchInsn, MutatableCode mutatableCode) {
	// Update the offset to the data instruction
	MInsn dataTarget = switchInsn.dataTarget;
	int dataOffset = dataTarget.location - switchInsn.location;
	ContainsTarget containsTarget = (ContainsTarget) switchInsn.insn.info.format;
	containsTarget.setTarget(switchInsn.insn, dataOffset);

	int targetsSize = switchInsn.targets.size();

	int[] keys = switchInsn.keys;
	int[] targets = new int[targetsSize];

	// Calculate the new offsets.
	int targetIdx = 0;
	for (MInsn target : switchInsn.targets) {
	targets[targetIdx] = target.location - switchInsn.location;
	targetIdx++;
	}

	// Now write the data back to the raw bytes.
	Instruction dataInsn = switchInsn.dataTarget.insn;

	int rawPtr = 2;

	// Write out the size.
	RawInsnHelper.writeUnsignedShortToTwoBytes(dataInsn.rawBytes, rawPtr, targetsSize);
	rawPtr += 2;

	// Write out the keys.
	if (switchInsn.packed) {
	// Only write out one key - the first.
	RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, keys[0]);
	rawPtr += 4;
	} else {
	// Write out all the keys.
	for (int i = 0; i < targetsSize; i++) {
	RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, keys[i]);
	rawPtr += 4;
	}
	}

	// Write out all the targets.
	for (int i = 0; i < targetsSize; i++) {
	RawInsnHelper.writeUnsignedIntToFourBytes(dataInsn.rawBytes, rawPtr, targets[i]);
	rawPtr += 4;
	}
	}

	/**
	* After mutation, data instructions may no longer be 4-byte aligned.
	* If this is the case, insert nops to align them all.
	* This makes a number of assumptions about data currently:
	* - data is always at the end of method insns
	* - all data instructions are stored contiguously
	*/
	private void alignDataInstructions(MutatableCode mutatableCode) {
	// Find all the switch data instructions.
	List<MInsn> dataInsns = new ArrayList<MInsn>();

	// Update raw sizes of the data instructions as well.
	for (MInsn mInsn : mutatableCode.getInstructions()) {
	if (mInsn instanceof MSwitchInsn) {
	// Update the raw size of the instruction.
	MSwitchInsn switchInsn = (MSwitchInsn) mInsn;
	int targetsSize = switchInsn.targets.size();
	Instruction dataInsn = switchInsn.dataTarget.insn;
	if (switchInsn.packed) {
	dataInsn.rawSize = (targetsSize * 2) + 4;
	} else {
	dataInsn.rawSize = (targetsSize * 4) + 2;
	}
	dataInsns.add(switchInsn.dataTarget);
	} else if (mInsn instanceof MInsnWithData) {
	MInsnWithData insnWithData =
	(MInsnWithData) mInsn;
	dataInsns.add(insnWithData.dataTarget);
	}
	}

	// Only need to align switch data instructions if there are any!
	if (!dataInsns.isEmpty()) {

	Log.debug("Found data instructions, checking alignment...");

	// Sort data_insns by location.
	Collections.sort(dataInsns, new Comparator<MInsn>() {
	@Override
	public int compare(MInsn first, MInsn second) {
	if (first.location < second.location) {
	return -1;
	} else if (first.location > second.location) {
	return 1;
	}
	return 0;
	}
	});

	boolean performedAlignment = false;

	// Go through all the data insns, and insert an alignment nop if they're unaligned.
	for (MInsn dataInsn : dataInsns) {
	if (dataInsn.location % 2 != 0) {
	Log.debug("Aligning data instruction with a nop.");
	int alignmentNopIdx = mutatableCode.getInstructionIndex(dataInsn);
	MInsn nop = new MInsn();
	nop.insn = new Instruction();
	nop.insn.info = Instruction.getOpcodeInfo(Opcode.NOP);
	mutatableCode.insertInstructionAt(nop, alignmentNopIdx);
	performedAlignment = true;
	}
	}

	if (!performedAlignment) {
	Log.debug("Alignment okay.");
	}
	}
	}

	/**
	* Determine if a particular instruction is a branch instruction, based on opcode.
	*/
	private boolean isInstructionBranch(Instruction insn) {
	Opcode opcode = insn.info.opcode;
	if (Opcode.isBetween(opcode, Opcode.IF_EQ, Opcode.IF_LEZ)
	\|\| Opcode.isBetween(opcode, Opcode.GOTO, Opcode.GOTO_32)) {
	return true;
	}
	return false;
	}

	/**
	* Determine if a particular instruction is a switch instruction, based on opcode.
	*/
	private boolean isInstructionSwitch(Instruction insn) {
	Opcode opcode = insn.info.opcode;
	if (Opcode.isBetween(opcode, Opcode.PACKED_SWITCH, Opcode.SPARSE_SWITCH)) {
	return true;
	}
	return false;
	}

	private boolean isInstructionFillArrayData(Instruction insn) {
	return (insn.info.opcode == Opcode.FILL_ARRAY_DATA);
	}
	}