2 * Copyright (C) 2011 The Android Open Source Project
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package com.android.dx.merge;
19 import com.android.dx.dex.SizeOf;
20 import com.android.dx.dex.TableOfContents;
21 import com.android.dx.io.Annotation;
22 import com.android.dx.io.ClassData;
23 import com.android.dx.io.ClassDef;
24 import com.android.dx.io.Code;
25 import com.android.dx.io.DexBuffer;
26 import com.android.dx.io.DexHasher;
27 import com.android.dx.io.FieldId;
28 import com.android.dx.io.MethodId;
29 import com.android.dx.io.ProtoId;
30 import com.android.dx.util.DexException;
32 import java.io.IOException;
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Collections;
36 import java.util.HashSet;
37 import java.util.List;
41 * Combine two dex files into one.
43 public final class DexMerger {
44 private final DexBuffer dexA;
45 private final DexBuffer dexB;
46 private final CollisionPolicy collisionPolicy;
47 private final WriterSizes writerSizes;
49 private final DexBuffer dexOut = new DexBuffer();
51 private final DexBuffer.Section headerOut;
53 /** All IDs and definitions sections */
54 private final DexBuffer.Section idsDefsOut;
56 private final DexBuffer.Section mapListOut;
58 private final DexBuffer.Section typeListOut;
60 private final DexBuffer.Section classDataOut;
62 private final DexBuffer.Section codeOut;
64 private final DexBuffer.Section stringDataOut;
66 private final DexBuffer.Section debugInfoOut;
68 private final DexBuffer.Section encodedArrayOut;
70 /** annotations directory on a type */
71 private final DexBuffer.Section annotationsDirectoryOut;
73 /** sets of annotations on a member, parameter or type */
74 private final DexBuffer.Section annotationSetOut;
76 /** parameter lists */
77 private final DexBuffer.Section annotationSetRefListOut;
79 /** individual annotations, each containing zero or more fields */
80 private final DexBuffer.Section annotationOut;
82 private final TableOfContents contentsOut;
84 private final IndexMap aIndexMap;
85 private final IndexMap bIndexMap;
86 private final InstructionTransformer aInstructionTransformer;
87 private final InstructionTransformer bInstructionTransformer;
89 /** minimum number of wasted bytes before it's worthwhile to compact the result */
90 private int compactWasteThreshold = 1024 * 1024; // 1MiB
92 public DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy)
94 this(dexA, dexB, collisionPolicy, new WriterSizes(dexA, dexB));
97 private DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy,
98 WriterSizes writerSizes) throws IOException {
101 this.collisionPolicy = collisionPolicy;
102 this.writerSizes = writerSizes;
104 TableOfContents aContents = dexA.getTableOfContents();
105 TableOfContents bContents = dexB.getTableOfContents();
106 aIndexMap = new IndexMap(dexOut, aContents);
107 bIndexMap = new IndexMap(dexOut, bContents);
108 aInstructionTransformer = new InstructionTransformer(aIndexMap);
109 bInstructionTransformer = new InstructionTransformer(bIndexMap);
111 headerOut = dexOut.appendSection(writerSizes.header, "header");
112 idsDefsOut = dexOut.appendSection(writerSizes.idsDefs, "ids defs");
114 contentsOut = dexOut.getTableOfContents();
115 contentsOut.dataOff = dexOut.getLength();
117 contentsOut.mapList.off = dexOut.getLength();
118 contentsOut.mapList.size = 1;
119 mapListOut = dexOut.appendSection(writerSizes.mapList, "map list");
121 contentsOut.typeLists.off = dexOut.getLength();
122 typeListOut = dexOut.appendSection(writerSizes.typeList, "type list");
124 contentsOut.annotationSetRefLists.off = dexOut.getLength();
125 annotationSetRefListOut = dexOut.appendSection(
126 writerSizes.annotationsSetRefList, "annotation set ref list");
128 contentsOut.annotationSets.off = dexOut.getLength();
129 annotationSetOut = dexOut.appendSection(writerSizes.annotationsSet, "annotation sets");
131 contentsOut.classDatas.off = dexOut.getLength();
132 classDataOut = dexOut.appendSection(writerSizes.classData, "class data");
134 contentsOut.codes.off = dexOut.getLength();
135 codeOut = dexOut.appendSection(writerSizes.code, "code");
137 contentsOut.stringDatas.off = dexOut.getLength();
138 stringDataOut = dexOut.appendSection(writerSizes.stringData, "string data");
140 contentsOut.debugInfos.off = dexOut.getLength();
141 debugInfoOut = dexOut.appendSection(writerSizes.debugInfo, "debug info");
143 contentsOut.annotations.off = dexOut.getLength();
144 annotationOut = dexOut.appendSection(writerSizes.annotation, "annotation");
146 contentsOut.encodedArrays.off = dexOut.getLength();
147 encodedArrayOut = dexOut.appendSection(writerSizes.encodedArray, "encoded array");
149 contentsOut.annotationsDirectories.off = dexOut.getLength();
150 annotationsDirectoryOut = dexOut.appendSection(
151 writerSizes.annotationsDirectory, "annotations directory");
153 dexOut.noMoreSections();
154 contentsOut.dataSize = dexOut.getLength() - contentsOut.dataOff;
157 public void setCompactWasteThreshold(int compactWasteThreshold) {
158 this.compactWasteThreshold = compactWasteThreshold;
161 private DexBuffer mergeDexBuffers() throws IOException {
169 unionAnnotationSetsAndDirectories();
173 contentsOut.header.off = 0;
174 contentsOut.header.size = 1;
175 contentsOut.fileSize = dexOut.getLength();
176 contentsOut.computeSizesFromOffsets();
177 contentsOut.writeHeader(headerOut);
178 contentsOut.writeMap(mapListOut);
180 // generate and write the hashes
181 new DexHasher().writeHashes(dexOut);
186 public DexBuffer merge() throws IOException {
187 long start = System.nanoTime();
188 DexBuffer result = mergeDexBuffers();
191 * We use pessimistic sizes when merging dex files. If those sizes
192 * result in too many bytes wasted, compact the result. To compact,
193 * simply merge the result with itself.
195 WriterSizes compactedSizes = new WriterSizes(this);
196 int wastedByteCount = writerSizes.size() - compactedSizes.size();
197 if (wastedByteCount > + compactWasteThreshold) {
198 DexMerger compacter = new DexMerger(
199 dexOut, new DexBuffer(), CollisionPolicy.FAIL, compactedSizes);
200 result = compacter.mergeDexBuffers();
201 System.out.printf("Result compacted from %.1fKiB to %.1fKiB to save %.1fKiB%n",
202 dexOut.getLength() / 1024f,
203 result.getLength() / 1024f,
204 wastedByteCount / 1024f);
207 long elapsed = System.nanoTime() - start;
208 System.out.printf("Merged dex A (%d defs/%.1fKiB) with dex B "
209 + "(%d defs/%.1fKiB). Result is %d defs/%.1fKiB. Took %.1fs%n",
210 dexA.getTableOfContents().classDefs.size,
211 dexA.getLength() / 1024f,
212 dexB.getTableOfContents().classDefs.size,
213 dexB.getLength() / 1024f,
214 result.getTableOfContents().classDefs.size,
215 result.getLength() / 1024f,
216 elapsed / 1000000000f);
222 * Reads an IDs section of two dex files and writes an IDs section of a
223 * merged dex file. Populates maps from old to new indices in the process.
225 abstract class IdMerger<T extends Comparable<T>> {
226 private final DexBuffer.Section out;
228 protected IdMerger(DexBuffer.Section out) {
233 * Merges already-sorted sections, reading only two values into memory
236 public final void mergeSorted() {
237 TableOfContents.Section aSection = getSection(dexA.getTableOfContents());
238 TableOfContents.Section bSection = getSection(dexB.getTableOfContents());
239 getSection(contentsOut).off = out.getPosition();
241 DexBuffer.Section inA = aSection.exists() ? dexA.open(aSection.off) : null;
242 DexBuffer.Section inB = bSection.exists() ? dexB.open(bSection.off) : null;
252 if (a == null && aIndex < aSection.size) {
253 aOffset = inA.getPosition();
254 a = read(inA, aIndexMap, aIndex);
256 if (b == null && bIndex < bSection.size) {
257 bOffset = inB.getPosition();
258 b = read(inB, bIndexMap, bIndex);
261 // Write the smaller of a and b. If they're equal, write only once
264 if (a != null && b != null) {
265 int compare = a.compareTo(b);
266 advanceA = compare <= 0;
267 advanceB = compare >= 0;
269 advanceA = (a != null);
270 advanceB = (b != null);
276 updateIndex(aOffset, aIndexMap, aIndex++, outCount);
282 updateIndex(bOffset, bIndexMap, bIndex++, outCount);
286 if (toWrite == null) {
287 break; // advanceA == false && advanceB == false
293 getSection(contentsOut).size = outCount;
297 * Merges unsorted sections by reading them completely into memory and
300 public final void mergeUnsorted() {
301 getSection(contentsOut).off = out.getPosition();
303 List<UnsortedValue> all = new ArrayList<UnsortedValue>();
304 all.addAll(readUnsortedValues(dexA, aIndexMap));
305 all.addAll(readUnsortedValues(dexB, bIndexMap));
306 Collections.sort(all);
309 for (int i = 0; i < all.size(); ) {
310 UnsortedValue e1 = all.get(i++);
311 updateIndex(e1.offset, getIndexMap(e1.source), e1.index, outCount - 1);
313 while (i < all.size() && e1.compareTo(all.get(i)) == 0) {
314 UnsortedValue e2 = all.get(i++);
315 updateIndex(e2.offset, getIndexMap(e2.source), e2.index, outCount - 1);
322 getSection(contentsOut).size = outCount;
325 private List<UnsortedValue> readUnsortedValues(DexBuffer source, IndexMap indexMap) {
326 TableOfContents.Section section = getSection(source.getTableOfContents());
327 if (!section.exists()) {
328 return Collections.emptyList();
331 List<UnsortedValue> result = new ArrayList<UnsortedValue>();
332 DexBuffer.Section in = source.open(section.off);
333 for (int i = 0; i < section.size; i++) {
334 int offset = in.getPosition();
335 T value = read(in, indexMap, 0);
336 result.add(new UnsortedValue(source, indexMap, value, i, offset));
341 abstract TableOfContents.Section getSection(TableOfContents tableOfContents);
342 abstract T read(DexBuffer.Section in, IndexMap indexMap, int index);
343 abstract void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex);
344 abstract void write(T value);
346 class UnsortedValue implements Comparable<UnsortedValue> {
347 final DexBuffer source;
348 final IndexMap indexMap;
353 UnsortedValue(DexBuffer source, IndexMap indexMap, T value, int index, int offset) {
354 this.source = source;
355 this.indexMap = indexMap;
358 this.offset = offset;
361 public int compareTo(UnsortedValue unsortedValue) {
362 return value.compareTo(unsortedValue.value);
367 private IndexMap getIndexMap(DexBuffer dexBuffer) {
368 if (dexBuffer == dexA) {
370 } else if (dexBuffer == dexB) {
373 throw new IllegalArgumentException();
377 private void mergeStringIds() {
378 new IdMerger<String>(idsDefsOut) {
379 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
380 return tableOfContents.stringIds;
383 @Override String read(DexBuffer.Section in, IndexMap indexMap, int index) {
384 return in.readString();
387 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
388 indexMap.stringIds[oldIndex] = newIndex;
391 @Override void write(String value) {
392 contentsOut.stringDatas.size++;
393 idsDefsOut.writeInt(stringDataOut.getPosition());
394 stringDataOut.writeStringData(value);
399 private void mergeTypeIds() {
400 new IdMerger<Integer>(idsDefsOut) {
401 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
402 return tableOfContents.typeIds;
405 @Override Integer read(DexBuffer.Section in, IndexMap indexMap, int index) {
406 int stringIndex = in.readInt();
407 return indexMap.adjustString(stringIndex);
410 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
411 indexMap.typeIds[oldIndex] = (short) newIndex;
414 @Override void write(Integer value) {
415 idsDefsOut.writeInt(value);
420 private void mergeTypeLists() {
421 new IdMerger<TypeList>(typeListOut) {
422 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
423 return tableOfContents.typeLists;
426 @Override TypeList read(DexBuffer.Section in, IndexMap indexMap, int index) {
427 return indexMap.adjustTypeList(in.readTypeList());
430 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
431 indexMap.putTypeListOffset(offset, typeListOut.getPosition());
434 @Override void write(TypeList value) {
435 typeListOut.writeTypeList(value);
440 private void mergeProtoIds() {
441 new IdMerger<ProtoId>(idsDefsOut) {
442 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
443 return tableOfContents.protoIds;
446 @Override ProtoId read(DexBuffer.Section in, IndexMap indexMap, int index) {
447 return indexMap.adjust(in.readProtoId());
450 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
451 indexMap.protoIds[oldIndex] = (short) newIndex;
454 @Override void write(ProtoId value) {
455 value.writeTo(idsDefsOut);
460 private void mergeFieldIds() {
461 new IdMerger<FieldId>(idsDefsOut) {
462 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
463 return tableOfContents.fieldIds;
466 @Override FieldId read(DexBuffer.Section in, IndexMap indexMap, int index) {
467 return indexMap.adjust(in.readFieldId());
470 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
471 indexMap.fieldIds[oldIndex] = (short) newIndex;
474 @Override void write(FieldId value) {
475 value.writeTo(idsDefsOut);
480 private void mergeMethodIds() {
481 new IdMerger<MethodId>(idsDefsOut) {
482 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
483 return tableOfContents.methodIds;
486 @Override MethodId read(DexBuffer.Section in, IndexMap indexMap, int index) {
487 return indexMap.adjust(in.readMethodId());
490 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
491 indexMap.methodIds[oldIndex] = (short) newIndex;
494 @Override void write(MethodId methodId) {
495 methodId.writeTo(idsDefsOut);
500 private void mergeAnnotations() {
501 new IdMerger<Annotation>(annotationOut) {
502 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
503 return tableOfContents.annotations;
506 @Override Annotation read(DexBuffer.Section in, IndexMap indexMap, int index) {
507 return indexMap.adjust(in.readAnnotation());
510 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
511 indexMap.putAnnotationOffset(offset, annotationOut.getPosition());
514 @Override void write(Annotation value) {
515 value.writeTo(annotationOut);
520 private void mergeClassDefs() {
521 SortableType[] types = getSortedTypes();
522 contentsOut.classDefs.off = idsDefsOut.getPosition();
523 contentsOut.classDefs.size = types.length;
525 for (SortableType type : types) {
526 DexBuffer in = type.getBuffer();
527 IndexMap indexMap = (in == dexA) ? aIndexMap : bIndexMap;
528 transformClassDef(in, type.getClassDef(), indexMap);
533 * Returns the union of classes from both files, sorted in order such that
534 * a class is always preceded by its supertype and implemented interfaces.
536 private SortableType[] getSortedTypes() {
537 // size is pessimistic; doesn't include arrays
538 SortableType[] sortableTypes = new SortableType[contentsOut.typeIds.size];
539 readSortableTypes(sortableTypes, dexA, aIndexMap);
540 readSortableTypes(sortableTypes, dexB, bIndexMap);
543 * Populate the depths of each sortable type. This makes D iterations
544 * through all N types, where 'D' is the depth of the deepest type. For
545 * example, the deepest class in libcore is Xalan's KeyIterator, which
549 boolean allDone = true;
550 for (SortableType sortableType : sortableTypes) {
551 if (sortableType != null && !sortableType.isDepthAssigned()) {
552 allDone &= sortableType.tryAssignDepth(sortableTypes);
560 // Now that all types have depth information, the result can be sorted
561 Arrays.sort(sortableTypes, SortableType.NULLS_LAST_ORDER);
563 // Strip nulls from the end
564 int firstNull = Arrays.asList(sortableTypes).indexOf(null);
565 return firstNull != -1
566 ? Arrays.copyOfRange(sortableTypes, 0, firstNull)
571 * Reads just enough data on each class so that we can sort it and then find
574 private void readSortableTypes(SortableType[] sortableTypes, DexBuffer buffer,
576 for (ClassDef classDef : buffer.classDefs()) {
577 SortableType sortableType = indexMap.adjust(new SortableType(buffer, classDef));
578 int t = sortableType.getTypeIndex();
579 if (sortableTypes[t] == null) {
580 sortableTypes[t] = sortableType;
581 } else if (collisionPolicy != CollisionPolicy.KEEP_FIRST) {
582 throw new DexException("Multiple dex files define "
583 + buffer.typeNames().get(classDef.getTypeIndex()));
589 * Copy annotation sets from each input to the output.
591 * TODO: this may write multiple copies of the same annotation set.
592 * We should shrink the output by merging rather than unioning
594 private void unionAnnotationSetsAndDirectories() {
595 transformAnnotationSets(dexA, aIndexMap);
596 transformAnnotationSets(dexB, bIndexMap);
597 transformAnnotationDirectories(dexA, aIndexMap);
598 transformAnnotationDirectories(dexB, bIndexMap);
599 transformStaticValues(dexA, aIndexMap);
600 transformStaticValues(dexB, bIndexMap);
603 private void transformAnnotationSets(DexBuffer in, IndexMap indexMap) {
604 TableOfContents.Section section = in.getTableOfContents().annotationSets;
605 if (section.exists()) {
606 DexBuffer.Section setIn = in.open(section.off);
607 for (int i = 0; i < section.size; i++) {
608 transformAnnotationSet(indexMap, setIn);
613 private void transformAnnotationDirectories(DexBuffer in, IndexMap indexMap) {
614 TableOfContents.Section section = in.getTableOfContents().annotationsDirectories;
615 if (section.exists()) {
616 DexBuffer.Section directoryIn = in.open(section.off);
617 for (int i = 0; i < section.size; i++) {
618 transformAnnotationDirectory(in, directoryIn, indexMap);
623 private void transformStaticValues(DexBuffer in, IndexMap indexMap) {
624 TableOfContents.Section section = in.getTableOfContents().encodedArrays;
625 if (section.exists()) {
626 DexBuffer.Section staticValuesIn = in.open(section.off);
627 for (int i = 0; i < section.size; i++) {
628 transformStaticValues(staticValuesIn, indexMap);
634 * Reads a class_def_item beginning at {@code in} and writes the index and
637 private void transformClassDef(DexBuffer in, ClassDef classDef, IndexMap indexMap) {
638 idsDefsOut.assertFourByteAligned();
639 idsDefsOut.writeInt(classDef.getTypeIndex());
640 idsDefsOut.writeInt(classDef.getAccessFlags());
641 idsDefsOut.writeInt(classDef.getSupertypeIndex());
642 idsDefsOut.writeInt(classDef.getInterfacesOffset());
644 int sourceFileIndex = indexMap.adjustString(classDef.getSourceFileIndex());
645 idsDefsOut.writeInt(sourceFileIndex);
647 int annotationsOff = classDef.getAnnotationsOffset();
648 idsDefsOut.writeInt(indexMap.adjustAnnotationDirectory(annotationsOff));
650 int classDataOff = classDef.getClassDataOffset();
651 if (classDataOff == 0) {
652 idsDefsOut.writeInt(0);
654 idsDefsOut.writeInt(classDataOut.getPosition());
655 ClassData classData = in.readClassData(classDef);
656 transformClassData(in, classData, indexMap);
659 int staticValuesOff = classDef.getStaticValuesOffset();
660 idsDefsOut.writeInt(indexMap.adjustStaticValues(staticValuesOff));
664 * Transform all annotations on a class.
666 private void transformAnnotationDirectory(
667 DexBuffer in, DexBuffer.Section directoryIn, IndexMap indexMap) {
668 contentsOut.annotationsDirectories.size++;
669 annotationsDirectoryOut.assertFourByteAligned();
670 indexMap.putAnnotationDirectoryOffset(
671 directoryIn.getPosition(), annotationsDirectoryOut.getPosition());
673 int classAnnotationsOffset = indexMap.adjustAnnotationSet(directoryIn.readInt());
674 annotationsDirectoryOut.writeInt(classAnnotationsOffset);
676 int fieldsSize = directoryIn.readInt();
677 annotationsDirectoryOut.writeInt(fieldsSize);
679 int methodsSize = directoryIn.readInt();
680 annotationsDirectoryOut.writeInt(methodsSize);
682 int parameterListSize = directoryIn.readInt();
683 annotationsDirectoryOut.writeInt(parameterListSize);
685 for (int i = 0; i < fieldsSize; i++) {
687 annotationsDirectoryOut.writeInt(indexMap.adjustField(directoryIn.readInt()));
689 // annotations offset
690 annotationsDirectoryOut.writeInt(indexMap.adjustAnnotationSet(directoryIn.readInt()));
693 for (int i = 0; i < methodsSize; i++) {
695 annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt()));
697 // annotation set offset
698 annotationsDirectoryOut.writeInt(
699 indexMap.adjustAnnotationSet(directoryIn.readInt()));
702 for (int i = 0; i < parameterListSize; i++) {
703 contentsOut.annotationSetRefLists.size++;
704 annotationSetRefListOut.assertFourByteAligned();
707 annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt()));
709 // annotations offset
710 annotationsDirectoryOut.writeInt(annotationSetRefListOut.getPosition());
711 DexBuffer.Section refListIn = in.open(directoryIn.readInt());
714 int parameterCount = refListIn.readInt();
715 annotationSetRefListOut.writeInt(parameterCount);
716 for (int p = 0; p < parameterCount; p++) {
717 annotationSetRefListOut.writeInt(indexMap.adjustAnnotationSet(refListIn.readInt()));
723 * Transform all annotations on a single type, member or parameter.
725 private void transformAnnotationSet(IndexMap indexMap, DexBuffer.Section setIn) {
726 contentsOut.annotationSets.size++;
727 annotationSetOut.assertFourByteAligned();
728 indexMap.putAnnotationSetOffset(setIn.getPosition(), annotationSetOut.getPosition());
730 int size = setIn.readInt();
731 annotationSetOut.writeInt(size);
733 for (int j = 0; j < size; j++) {
734 annotationSetOut.writeInt(indexMap.adjustAnnotation(setIn.readInt()));
738 private void transformClassData(DexBuffer in, ClassData classData, IndexMap indexMap) {
739 contentsOut.classDatas.size++;
741 ClassData.Field[] staticFields = classData.getStaticFields();
742 ClassData.Field[] instanceFields = classData.getInstanceFields();
743 ClassData.Method[] directMethods = classData.getDirectMethods();
744 ClassData.Method[] virtualMethods = classData.getVirtualMethods();
746 classDataOut.writeUleb128(staticFields.length);
747 classDataOut.writeUleb128(instanceFields.length);
748 classDataOut.writeUleb128(directMethods.length);
749 classDataOut.writeUleb128(virtualMethods.length);
751 transformFields(indexMap, staticFields);
752 transformFields(indexMap, instanceFields);
753 transformMethods(in, indexMap, directMethods);
754 transformMethods(in, indexMap, virtualMethods);
757 private void transformFields(IndexMap indexMap, ClassData.Field[] fields) {
758 int lastOutFieldIndex = 0;
759 for (ClassData.Field field : fields) {
760 int outFieldIndex = indexMap.adjustField(field.getFieldIndex());
761 classDataOut.writeUleb128(outFieldIndex - lastOutFieldIndex);
762 lastOutFieldIndex = outFieldIndex;
763 classDataOut.writeUleb128(field.getAccessFlags());
767 private void transformMethods(DexBuffer in, IndexMap indexMap, ClassData.Method[] methods) {
768 int lastOutMethodIndex = 0;
769 for (ClassData.Method method : methods) {
770 int outMethodIndex = indexMap.adjustMethod(method.getMethodIndex());
771 classDataOut.writeUleb128(outMethodIndex - lastOutMethodIndex);
772 lastOutMethodIndex = outMethodIndex;
774 classDataOut.writeUleb128(method.getAccessFlags());
776 if (method.getCodeOffset() == 0) {
777 classDataOut.writeUleb128(0);
779 codeOut.alignToFourBytes();
780 classDataOut.writeUleb128(codeOut.getPosition());
781 transformCode(in, in.readCode(method), indexMap);
786 private void transformCode(DexBuffer in, Code code, IndexMap indexMap) {
787 contentsOut.codes.size++;
788 codeOut.assertFourByteAligned();
790 codeOut.writeUnsignedShort(code.getRegistersSize());
791 codeOut.writeUnsignedShort(code.getInsSize());
792 codeOut.writeUnsignedShort(code.getOutsSize());
794 Code.Try[] tries = code.getTries();
795 codeOut.writeUnsignedShort(tries.length);
797 int debugInfoOffset = code.getDebugInfoOffset();
798 if (debugInfoOffset != 0) {
799 codeOut.writeInt(debugInfoOut.getPosition());
800 transformDebugInfoItem(in.open(debugInfoOffset), indexMap);
805 short[] instructions = code.getInstructions();
806 InstructionTransformer transformer = (in == dexA)
807 ? aInstructionTransformer
808 : bInstructionTransformer;
809 short[] newInstructions = transformer.transform(instructions);
810 codeOut.writeInt(newInstructions.length);
811 codeOut.write(newInstructions);
813 if (tries.length > 0) {
814 if (newInstructions.length % 2 == 1) {
815 codeOut.writeShort((short) 0); // padding
817 for (Code.Try tryItem : tries) {
818 codeOut.writeInt(tryItem.getStartAddress());
819 codeOut.writeUnsignedShort(tryItem.getInstructionCount());
820 codeOut.writeUnsignedShort(tryItem.getHandlerOffset());
822 Code.CatchHandler[] catchHandlers = code.getCatchHandlers();
823 codeOut.writeUleb128(catchHandlers.length);
824 for (Code.CatchHandler catchHandler : catchHandlers) {
825 transformEncodedCatchHandler(catchHandler, indexMap);
830 private static final byte DBG_END_SEQUENCE = 0x00;
831 private static final byte DBG_ADVANCE_PC = 0x01;
832 private static final byte DBG_ADVANCE_LINE = 0x02;
833 private static final byte DBG_START_LOCAL = 0x03;
834 private static final byte DBG_START_LOCAL_EXTENDED = 0x04;
835 private static final byte DBG_END_LOCAL = 0x05;
836 private static final byte DBG_RESTART_LOCAL = 0x06;
837 private static final byte DBG_SET_PROLOGUE_END = 0x07;
838 private static final byte DBG_SET_EPILOGUE_BEGIN = 0x08;
839 private static final byte DBG_SET_FILE = 0x09;
841 private void transformDebugInfoItem(DexBuffer.Section in, IndexMap indexMap) {
842 int lineStart = in.readUleb128();
843 debugInfoOut.writeUleb128(lineStart);
845 int parametersSize = in.readUleb128();
846 debugInfoOut.writeUleb128(parametersSize);
848 for (int p = 0; p < parametersSize; p++) {
849 int parameterName = in.readUleb128p1();
850 debugInfoOut.writeUleb128p1(indexMap.adjustString(parameterName));
853 int addrDiff; // uleb128 address delta.
854 int lineDiff; // sleb128 line delta.
855 int registerNum; // uleb128 register number.
856 int nameIndex; // uleb128p1 string index. Needs indexMap adjustment.
857 int typeIndex; // uleb128p1 type index. Needs indexMap adjustment.
858 int sigIndex; // uleb128p1 string index. Needs indexMap adjustment.
861 int opcode = in.readByte();
862 debugInfoOut.writeByte(opcode);
865 case DBG_END_SEQUENCE:
869 addrDiff = in.readUleb128();
870 debugInfoOut.writeUleb128(addrDiff);
873 case DBG_ADVANCE_LINE:
874 lineDiff = in.readSleb128();
875 debugInfoOut.writeSleb128(lineDiff);
878 case DBG_START_LOCAL:
879 case DBG_START_LOCAL_EXTENDED:
880 registerNum = in.readUleb128();
881 debugInfoOut.writeUleb128(registerNum);
882 nameIndex = in.readUleb128p1();
883 debugInfoOut.writeUleb128p1(indexMap.adjustString(nameIndex));
884 typeIndex = in.readUleb128p1();
885 debugInfoOut.writeUleb128p1(indexMap.adjustType(typeIndex));
886 if (opcode == DBG_START_LOCAL_EXTENDED) {
887 sigIndex = in.readUleb128p1();
888 debugInfoOut.writeUleb128p1(indexMap.adjustString(sigIndex));
893 case DBG_RESTART_LOCAL:
894 registerNum = in.readUleb128();
895 debugInfoOut.writeUleb128(registerNum);
899 nameIndex = in.readUleb128p1();
900 debugInfoOut.writeUleb128p1(indexMap.adjustString(nameIndex));
903 case DBG_SET_PROLOGUE_END:
904 case DBG_SET_EPILOGUE_BEGIN:
911 private void transformEncodedCatchHandler(Code.CatchHandler catchHandler, IndexMap indexMap) {
912 int catchAllAddress = catchHandler.getCatchAllAddress();
913 int[] typeIndexes = catchHandler.getTypeIndexes();
914 int[] addresses = catchHandler.getAddresses();
916 if (catchAllAddress != -1) {
917 codeOut.writeSleb128(-typeIndexes.length);
919 codeOut.writeSleb128(typeIndexes.length);
922 for (int i = 0; i < typeIndexes.length; i++) {
923 codeOut.writeUleb128(indexMap.adjustType(typeIndexes[i]));
924 codeOut.writeUleb128(addresses[i]);
927 if (catchAllAddress != -1) {
928 codeOut.writeUleb128(catchAllAddress);
932 private void transformStaticValues(DexBuffer.Section in, IndexMap indexMap) {
933 contentsOut.encodedArrays.size++;
934 indexMap.putStaticValuesOffset(in.getPosition(), encodedArrayOut.getPosition());
935 indexMap.adjustEncodedArray(in.readEncodedArray()).writeTo(encodedArrayOut);
939 * Byte counts for the sections written when creating a dex. Target sizes
940 * are defined in one of two ways:
942 * <li>By pessimistically guessing how large the union of dex files will be.
943 * We're pessimistic because we can't predict the amount of duplication
944 * between dex files, nor can we predict the length of ULEB-encoded
945 * offsets or indices.
946 * <li>By exactly measuring an existing dex.
949 private static class WriterSizes {
950 private int header = SizeOf.HEADER_ITEM;
953 private int typeList;
954 private int classData;
956 private int stringData;
957 private int debugInfo;
958 private int encodedArray;
959 private int annotationsDirectory;
960 private int annotationsSet;
961 private int annotationsSetRefList;
962 private int annotation;
965 * Compute sizes for merging a and b.
967 public WriterSizes(DexBuffer a, DexBuffer b) {
968 plus(a.getTableOfContents(), false);
969 plus(b.getTableOfContents(), false);
972 public WriterSizes(DexMerger dexMerger) {
973 header = dexMerger.headerOut.used();
974 idsDefs = dexMerger.idsDefsOut.used();
975 mapList = dexMerger.mapListOut.used();
976 typeList = dexMerger.typeListOut.used();
977 classData = dexMerger.classDataOut.used();
978 code = dexMerger.codeOut.used();
979 stringData = dexMerger.stringDataOut.used();
980 debugInfo = dexMerger.debugInfoOut.used();
981 encodedArray = dexMerger.encodedArrayOut.used();
982 annotationsDirectory = dexMerger.annotationsDirectoryOut.used();
983 annotationsSet = dexMerger.annotationSetOut.used();
984 annotationsSetRefList = dexMerger.annotationSetRefListOut.used();
985 annotation = dexMerger.annotationOut.used();
988 public void plus(TableOfContents contents, boolean exact) {
989 idsDefs += contents.stringIds.size * SizeOf.STRING_ID_ITEM
990 + contents.typeIds.size * SizeOf.TYPE_ID_ITEM
991 + contents.protoIds.size * SizeOf.PROTO_ID_ITEM
992 + contents.fieldIds.size * SizeOf.MEMBER_ID_ITEM
993 + contents.methodIds.size * SizeOf.MEMBER_ID_ITEM
994 + contents.classDefs.size * SizeOf.CLASS_DEF_ITEM;
995 mapList = SizeOf.UINT + (contents.sections.length * SizeOf.MAP_ITEM);
996 typeList += contents.typeLists.byteCount;
997 stringData += contents.stringDatas.byteCount;
998 annotationsDirectory += contents.annotationsDirectories.byteCount;
999 annotationsSet += contents.annotationSets.byteCount;
1000 annotationsSetRefList += contents.annotationSetRefLists.byteCount;
1003 code += contents.codes.byteCount;
1004 classData += contents.classDatas.byteCount;
1005 encodedArray += contents.encodedArrays.byteCount;
1006 annotation += contents.annotations.byteCount;
1007 debugInfo += contents.debugInfos.byteCount;
1009 // at most 1/4 of the bytes in a code section are uleb/sleb
1010 code += (int) Math.ceil(contents.codes.byteCount * 1.25);
1011 // at most 1/3 of the bytes in a class data section are uleb/sleb
1012 classData += (int) Math.ceil(contents.classDatas.byteCount * 1.34);
1013 // all of the bytes in an encoding arrays section may be uleb/sleb
1014 encodedArray += contents.encodedArrays.byteCount * 2;
1015 // at most 1/3 of the bytes in an encoding arrays section are uleb/sleb
1016 annotation += (int) Math.ceil(contents.annotations.byteCount * 1.34);
1017 // all of the bytes in a debug info section may be uleb/sleb
1018 debugInfo += contents.debugInfos.byteCount * 2;
1021 typeList = DexBuffer.fourByteAlign(typeList);
1022 code = DexBuffer.fourByteAlign(code);
1026 return header + idsDefs + mapList + typeList + classData + code + stringData + debugInfo
1027 + encodedArray + annotationsDirectory + annotationsSet + annotationsSetRefList
1032 public static void main(String[] args) throws IOException {
1033 if (args.length != 3) {
1038 DexBuffer dexA = new DexBuffer(new File(args[1]));
1039 DexBuffer dexB = new DexBuffer(new File(args[2]));
1040 DexBuffer merged = new DexMerger(dexA, dexB, CollisionPolicy.KEEP_FIRST).merge();
1041 merged.writeTo(new File(args[0]));
1044 private static void printUsage() {
1045 System.out.println("Usage: DexMerger <out.dex> <a.dex> <b.dex>");
1046 System.out.println();
1047 System.out.println("If both a and b define the same classes, a's copy will be used.");