DexMerger.java revision 519975591eba13ae7ac4e494a0dfb88a34ca191b
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 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 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 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. 15 */ 16 17package com.android.dx.merge; 18 19import com.android.dx.dex.SizeOf; 20import com.android.dx.dex.TableOfContents; 21import com.android.dx.io.Annotation; 22import com.android.dx.io.ClassData; 23import com.android.dx.io.ClassDef; 24import com.android.dx.io.Code; 25import com.android.dx.io.DexBuffer; 26import com.android.dx.io.DexHasher; 27import com.android.dx.io.FieldId; 28import com.android.dx.io.MethodId; 29import com.android.dx.io.ProtoId; 30import com.android.dx.util.DexException; 31import java.io.File; 32import java.io.IOException; 33import java.util.ArrayList; 34import java.util.Arrays; 35import java.util.Collections; 36import java.util.List; 37 38/** 39 * Combine two dex files into one. 40 */ 41public final class DexMerger { 42 private final DexBuffer dexA; 43 private final DexBuffer dexB; 44 private final CollisionPolicy collisionPolicy; 45 private final WriterSizes writerSizes; 46 47 private final DexBuffer dexOut = new DexBuffer(); 48 49 private final DexBuffer.Section headerOut; 50 51 /** All IDs and definitions sections */ 52 private final DexBuffer.Section idsDefsOut; 53 54 private final DexBuffer.Section mapListOut; 55 56 private final DexBuffer.Section typeListOut; 57 58 private final DexBuffer.Section classDataOut; 59 60 private final DexBuffer.Section codeOut; 61 62 private final DexBuffer.Section stringDataOut; 63 64 private final DexBuffer.Section debugInfoOut; 65 66 private final DexBuffer.Section encodedArrayOut; 67 68 /** annotations directory on a type */ 69 private final DexBuffer.Section annotationsDirectoryOut; 70 71 /** sets of annotations on a member, parameter or type */ 72 private final DexBuffer.Section annotationSetOut; 73 74 /** parameter lists */ 75 private final DexBuffer.Section annotationSetRefListOut; 76 77 /** individual annotations, each containing zero or more fields */ 78 private final DexBuffer.Section annotationOut; 79 80 private final TableOfContents contentsOut; 81 82 private final IndexMap aIndexMap; 83 private final IndexMap bIndexMap; 84 private final InstructionTransformer aInstructionTransformer; 85 private final InstructionTransformer bInstructionTransformer; 86 87 /** minimum number of wasted bytes before it's worthwhile to compact the result */ 88 private int compactWasteThreshold = 1024 * 1024; // 1MiB 89 90 public DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy) 91 throws IOException { 92 this(dexA, dexB, collisionPolicy, new WriterSizes(dexA, dexB)); 93 } 94 95 private DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy, 96 WriterSizes writerSizes) throws IOException { 97 this.dexA = dexA; 98 this.dexB = dexB; 99 this.collisionPolicy = collisionPolicy; 100 this.writerSizes = writerSizes; 101 102 TableOfContents aContents = dexA.getTableOfContents(); 103 TableOfContents bContents = dexB.getTableOfContents(); 104 aIndexMap = new IndexMap(dexOut, aContents); 105 bIndexMap = new IndexMap(dexOut, bContents); 106 aInstructionTransformer = new InstructionTransformer(aIndexMap); 107 bInstructionTransformer = new InstructionTransformer(bIndexMap); 108 109 headerOut = dexOut.appendSection(writerSizes.header, "header"); 110 idsDefsOut = dexOut.appendSection(writerSizes.idsDefs, "ids defs"); 111 112 contentsOut = dexOut.getTableOfContents(); 113 contentsOut.dataOff = dexOut.getLength(); 114 115 contentsOut.mapList.off = dexOut.getLength(); 116 contentsOut.mapList.size = 1; 117 mapListOut = dexOut.appendSection(writerSizes.mapList, "map list"); 118 119 contentsOut.typeLists.off = dexOut.getLength(); 120 typeListOut = dexOut.appendSection(writerSizes.typeList, "type list"); 121 122 contentsOut.annotationSetRefLists.off = dexOut.getLength(); 123 annotationSetRefListOut = dexOut.appendSection( 124 writerSizes.annotationsSetRefList, "annotation set ref list"); 125 126 contentsOut.annotationSets.off = dexOut.getLength(); 127 annotationSetOut = dexOut.appendSection(writerSizes.annotationsSet, "annotation sets"); 128 129 contentsOut.classDatas.off = dexOut.getLength(); 130 classDataOut = dexOut.appendSection(writerSizes.classData, "class data"); 131 132 contentsOut.codes.off = dexOut.getLength(); 133 codeOut = dexOut.appendSection(writerSizes.code, "code"); 134 135 contentsOut.stringDatas.off = dexOut.getLength(); 136 stringDataOut = dexOut.appendSection(writerSizes.stringData, "string data"); 137 138 contentsOut.debugInfos.off = dexOut.getLength(); 139 debugInfoOut = dexOut.appendSection(writerSizes.debugInfo, "debug info"); 140 141 contentsOut.annotations.off = dexOut.getLength(); 142 annotationOut = dexOut.appendSection(writerSizes.annotation, "annotation"); 143 144 contentsOut.encodedArrays.off = dexOut.getLength(); 145 encodedArrayOut = dexOut.appendSection(writerSizes.encodedArray, "encoded array"); 146 147 contentsOut.annotationsDirectories.off = dexOut.getLength(); 148 annotationsDirectoryOut = dexOut.appendSection( 149 writerSizes.annotationsDirectory, "annotations directory"); 150 151 dexOut.noMoreSections(); 152 contentsOut.dataSize = dexOut.getLength() - contentsOut.dataOff; 153 } 154 155 public void setCompactWasteThreshold(int compactWasteThreshold) { 156 this.compactWasteThreshold = compactWasteThreshold; 157 } 158 159 private DexBuffer mergeDexBuffers() throws IOException { 160 mergeStringIds(); 161 mergeTypeIds(); 162 mergeTypeLists(); 163 mergeProtoIds(); 164 mergeFieldIds(); 165 mergeMethodIds(); 166 mergeAnnotations(); 167 unionAnnotationSetsAndDirectories(); 168 mergeClassDefs(); 169 170 // write the header 171 contentsOut.header.off = 0; 172 contentsOut.header.size = 1; 173 contentsOut.fileSize = dexOut.getLength(); 174 contentsOut.computeSizesFromOffsets(); 175 contentsOut.writeHeader(headerOut); 176 contentsOut.writeMap(mapListOut); 177 178 // generate and write the hashes 179 new DexHasher().writeHashes(dexOut); 180 181 return dexOut; 182 } 183 184 public DexBuffer merge() throws IOException { 185 long start = System.nanoTime(); 186 DexBuffer result = mergeDexBuffers(); 187 188 /* 189 * We use pessimistic sizes when merging dex files. If those sizes 190 * result in too many bytes wasted, compact the result. To compact, 191 * simply merge the result with itself. 192 */ 193 WriterSizes compactedSizes = new WriterSizes(this); 194 int wastedByteCount = writerSizes.size() - compactedSizes.size(); 195 if (wastedByteCount > + compactWasteThreshold) { 196 DexMerger compacter = new DexMerger( 197 dexOut, new DexBuffer(), CollisionPolicy.FAIL, compactedSizes); 198 result = compacter.mergeDexBuffers(); 199 System.out.printf("Result compacted from %.1fKiB to %.1fKiB to save %.1fKiB%n", 200 dexOut.getLength() / 1024f, 201 result.getLength() / 1024f, 202 wastedByteCount / 1024f); 203 } 204 205 long elapsed = System.nanoTime() - start; 206 System.out.printf("Merged dex A (%d defs/%.1fKiB) with dex B " 207 + "(%d defs/%.1fKiB). Result is %d defs/%.1fKiB. Took %.1fs%n", 208 dexA.getTableOfContents().classDefs.size, 209 dexA.getLength() / 1024f, 210 dexB.getTableOfContents().classDefs.size, 211 dexB.getLength() / 1024f, 212 result.getTableOfContents().classDefs.size, 213 result.getLength() / 1024f, 214 elapsed / 1000000000f); 215 216 return result; 217 } 218 219 /** 220 * Reads an IDs section of two dex files and writes an IDs section of a 221 * merged dex file. Populates maps from old to new indices in the process. 222 */ 223 abstract class IdMerger<T extends Comparable<T>> { 224 private final DexBuffer.Section out; 225 226 protected IdMerger(DexBuffer.Section out) { 227 this.out = out; 228 } 229 230 /** 231 * Merges already-sorted sections, reading only two values into memory 232 * at a time. 233 */ 234 public final void mergeSorted() { 235 TableOfContents.Section aSection = getSection(dexA.getTableOfContents()); 236 TableOfContents.Section bSection = getSection(dexB.getTableOfContents()); 237 getSection(contentsOut).off = out.getPosition(); 238 239 DexBuffer.Section inA = aSection.exists() ? dexA.open(aSection.off) : null; 240 DexBuffer.Section inB = bSection.exists() ? dexB.open(bSection.off) : null; 241 int aOffset = -1; 242 int bOffset = -1; 243 int aIndex = 0; 244 int bIndex = 0; 245 int outCount = 0; 246 T a = null; 247 T b = null; 248 249 while (true) { 250 if (a == null && aIndex < aSection.size) { 251 aOffset = inA.getPosition(); 252 a = read(inA, aIndexMap, aIndex); 253 } 254 if (b == null && bIndex < bSection.size) { 255 bOffset = inB.getPosition(); 256 b = read(inB, bIndexMap, bIndex); 257 } 258 259 // Write the smaller of a and b. If they're equal, write only once 260 boolean advanceA; 261 boolean advanceB; 262 if (a != null && b != null) { 263 int compare = a.compareTo(b); 264 advanceA = compare <= 0; 265 advanceB = compare >= 0; 266 } else { 267 advanceA = (a != null); 268 advanceB = (b != null); 269 } 270 271 T toWrite = null; 272 if (advanceA) { 273 toWrite = a; 274 updateIndex(aOffset, aIndexMap, aIndex++, outCount); 275 a = null; 276 aOffset = -1; 277 } 278 if (advanceB) { 279 toWrite = b; 280 updateIndex(bOffset, bIndexMap, bIndex++, outCount); 281 b = null; 282 bOffset = -1; 283 } 284 if (toWrite == null) { 285 break; // advanceA == false && advanceB == false 286 } 287 write(toWrite); 288 outCount++; 289 } 290 291 getSection(contentsOut).size = outCount; 292 } 293 294 /** 295 * Merges unsorted sections by reading them completely into memory and 296 * sorting in memory. 297 */ 298 public final void mergeUnsorted() { 299 getSection(contentsOut).off = out.getPosition(); 300 301 List<UnsortedValue> all = new ArrayList<UnsortedValue>(); 302 all.addAll(readUnsortedValues(dexA, aIndexMap)); 303 all.addAll(readUnsortedValues(dexB, bIndexMap)); 304 Collections.sort(all); 305 306 int outCount = 0; 307 for (int i = 0; i < all.size(); ) { 308 UnsortedValue e1 = all.get(i++); 309 updateIndex(e1.offset, getIndexMap(e1.source), e1.index, outCount - 1); 310 311 while (i < all.size() && e1.compareTo(all.get(i)) == 0) { 312 UnsortedValue e2 = all.get(i++); 313 updateIndex(e2.offset, getIndexMap(e2.source), e2.index, outCount - 1); 314 } 315 316 write(e1.value); 317 outCount++; 318 } 319 320 getSection(contentsOut).size = outCount; 321 } 322 323 private List<UnsortedValue> readUnsortedValues(DexBuffer source, IndexMap indexMap) { 324 TableOfContents.Section section = getSection(source.getTableOfContents()); 325 if (!section.exists()) { 326 return Collections.emptyList(); 327 } 328 329 List<UnsortedValue> result = new ArrayList<UnsortedValue>(); 330 DexBuffer.Section in = source.open(section.off); 331 for (int i = 0; i < section.size; i++) { 332 int offset = in.getPosition(); 333 T value = read(in, indexMap, 0); 334 result.add(new UnsortedValue(source, indexMap, value, i, offset)); 335 } 336 return result; 337 } 338 339 abstract TableOfContents.Section getSection(TableOfContents tableOfContents); 340 abstract T read(DexBuffer.Section in, IndexMap indexMap, int index); 341 abstract void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex); 342 abstract void write(T value); 343 344 class UnsortedValue implements Comparable<UnsortedValue> { 345 final DexBuffer source; 346 final IndexMap indexMap; 347 final T value; 348 final int index; 349 final int offset; 350 351 UnsortedValue(DexBuffer source, IndexMap indexMap, T value, int index, int offset) { 352 this.source = source; 353 this.indexMap = indexMap; 354 this.value = value; 355 this.index = index; 356 this.offset = offset; 357 } 358 359 public int compareTo(UnsortedValue unsortedValue) { 360 return value.compareTo(unsortedValue.value); 361 } 362 } 363 } 364 365 private IndexMap getIndexMap(DexBuffer dexBuffer) { 366 if (dexBuffer == dexA) { 367 return aIndexMap; 368 } else if (dexBuffer == dexB) { 369 return bIndexMap; 370 } else { 371 throw new IllegalArgumentException(); 372 } 373 } 374 375 private void mergeStringIds() { 376 new IdMerger<String>(idsDefsOut) { 377 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 378 return tableOfContents.stringIds; 379 } 380 381 @Override String read(DexBuffer.Section in, IndexMap indexMap, int index) { 382 return in.readString(); 383 } 384 385 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 386 indexMap.stringIds[oldIndex] = newIndex; 387 } 388 389 @Override void write(String value) { 390 contentsOut.stringDatas.size++; 391 idsDefsOut.writeInt(stringDataOut.getPosition()); 392 stringDataOut.writeStringData(value); 393 } 394 }.mergeSorted(); 395 } 396 397 private void mergeTypeIds() { 398 new IdMerger<Integer>(idsDefsOut) { 399 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 400 return tableOfContents.typeIds; 401 } 402 403 @Override Integer read(DexBuffer.Section in, IndexMap indexMap, int index) { 404 int stringIndex = in.readInt(); 405 return indexMap.adjustString(stringIndex); 406 } 407 408 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 409 if (newIndex < 0 || newIndex > 0xffff) { 410 throw new IllegalArgumentException("type ID not in [0, 0xffff]: " + newIndex); 411 } 412 indexMap.typeIds[oldIndex] = (short) newIndex; 413 } 414 415 @Override void write(Integer value) { 416 idsDefsOut.writeInt(value); 417 } 418 }.mergeSorted(); 419 } 420 421 private void mergeTypeLists() { 422 new IdMerger<TypeList>(typeListOut) { 423 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 424 return tableOfContents.typeLists; 425 } 426 427 @Override TypeList read(DexBuffer.Section in, IndexMap indexMap, int index) { 428 return indexMap.adjustTypeList(in.readTypeList()); 429 } 430 431 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 432 indexMap.putTypeListOffset(offset, typeListOut.getPosition()); 433 } 434 435 @Override void write(TypeList value) { 436 typeListOut.writeTypeList(value); 437 } 438 }.mergeUnsorted(); 439 } 440 441 private void mergeProtoIds() { 442 new IdMerger<ProtoId>(idsDefsOut) { 443 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 444 return tableOfContents.protoIds; 445 } 446 447 @Override ProtoId read(DexBuffer.Section in, IndexMap indexMap, int index) { 448 return indexMap.adjust(in.readProtoId()); 449 } 450 451 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 452 if (newIndex < 0 || newIndex > 0xffff) { 453 throw new IllegalArgumentException("proto ID not in [0, 0xffff]: " + newIndex); 454 } 455 indexMap.protoIds[oldIndex] = (short) newIndex; 456 } 457 458 @Override void write(ProtoId value) { 459 value.writeTo(idsDefsOut); 460 } 461 }.mergeSorted(); 462 } 463 464 private void mergeFieldIds() { 465 new IdMerger<FieldId>(idsDefsOut) { 466 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 467 return tableOfContents.fieldIds; 468 } 469 470 @Override FieldId read(DexBuffer.Section in, IndexMap indexMap, int index) { 471 return indexMap.adjust(in.readFieldId()); 472 } 473 474 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 475 if (newIndex < 0 || newIndex > 0xffff) { 476 throw new IllegalArgumentException("field ID not in [0, 0xffff]: " + newIndex); 477 } 478 indexMap.fieldIds[oldIndex] = (short) newIndex; 479 } 480 481 @Override void write(FieldId value) { 482 value.writeTo(idsDefsOut); 483 } 484 }.mergeSorted(); 485 } 486 487 private void mergeMethodIds() { 488 new IdMerger<MethodId>(idsDefsOut) { 489 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 490 return tableOfContents.methodIds; 491 } 492 493 @Override MethodId read(DexBuffer.Section in, IndexMap indexMap, int index) { 494 return indexMap.adjust(in.readMethodId()); 495 } 496 497 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 498 if (newIndex < 0 || newIndex > 0xffff) { 499 throw new IllegalArgumentException("method ID not in [0, 0xffff]: " + newIndex); 500 } 501 indexMap.methodIds[oldIndex] = (short) newIndex; 502 } 503 504 @Override void write(MethodId methodId) { 505 methodId.writeTo(idsDefsOut); 506 } 507 }.mergeSorted(); 508 } 509 510 private void mergeAnnotations() { 511 new IdMerger<Annotation>(annotationOut) { 512 @Override TableOfContents.Section getSection(TableOfContents tableOfContents) { 513 return tableOfContents.annotations; 514 } 515 516 @Override Annotation read(DexBuffer.Section in, IndexMap indexMap, int index) { 517 return indexMap.adjust(in.readAnnotation()); 518 } 519 520 @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) { 521 indexMap.putAnnotationOffset(offset, annotationOut.getPosition()); 522 } 523 524 @Override void write(Annotation value) { 525 value.writeTo(annotationOut); 526 } 527 }.mergeUnsorted(); 528 } 529 530 private void mergeClassDefs() { 531 SortableType[] types = getSortedTypes(); 532 contentsOut.classDefs.off = idsDefsOut.getPosition(); 533 contentsOut.classDefs.size = types.length; 534 535 for (SortableType type : types) { 536 DexBuffer in = type.getBuffer(); 537 IndexMap indexMap = (in == dexA) ? aIndexMap : bIndexMap; 538 transformClassDef(in, type.getClassDef(), indexMap); 539 } 540 } 541 542 /** 543 * Returns the union of classes from both files, sorted in order such that 544 * a class is always preceded by its supertype and implemented interfaces. 545 */ 546 private SortableType[] getSortedTypes() { 547 // size is pessimistic; doesn't include arrays 548 SortableType[] sortableTypes = new SortableType[contentsOut.typeIds.size]; 549 readSortableTypes(sortableTypes, dexA, aIndexMap); 550 readSortableTypes(sortableTypes, dexB, bIndexMap); 551 552 /* 553 * Populate the depths of each sortable type. This makes D iterations 554 * through all N types, where 'D' is the depth of the deepest type. For 555 * example, the deepest class in libcore is Xalan's KeyIterator, which 556 * is 11 types deep. 557 */ 558 while (true) { 559 boolean allDone = true; 560 for (SortableType sortableType : sortableTypes) { 561 if (sortableType != null && !sortableType.isDepthAssigned()) { 562 allDone &= sortableType.tryAssignDepth(sortableTypes); 563 } 564 } 565 if (allDone) { 566 break; 567 } 568 } 569 570 // Now that all types have depth information, the result can be sorted 571 Arrays.sort(sortableTypes, SortableType.NULLS_LAST_ORDER); 572 573 // Strip nulls from the end 574 int firstNull = Arrays.asList(sortableTypes).indexOf(null); 575 return firstNull != -1 576 ? Arrays.copyOfRange(sortableTypes, 0, firstNull) 577 : sortableTypes; 578 } 579 580 /** 581 * Reads just enough data on each class so that we can sort it and then find 582 * it later. 583 */ 584 private void readSortableTypes(SortableType[] sortableTypes, DexBuffer buffer, 585 IndexMap indexMap) { 586 for (ClassDef classDef : buffer.classDefs()) { 587 SortableType sortableType = indexMap.adjust(new SortableType(buffer, classDef)); 588 int t = sortableType.getTypeIndex(); 589 if (sortableTypes[t] == null) { 590 sortableTypes[t] = sortableType; 591 } else if (collisionPolicy != CollisionPolicy.KEEP_FIRST) { 592 throw new DexException("Multiple dex files define " 593 + buffer.typeNames().get(classDef.getTypeIndex())); 594 } 595 } 596 } 597 598 /** 599 * Copy annotation sets from each input to the output. 600 * 601 * TODO: this may write multiple copies of the same annotation set. 602 * We should shrink the output by merging rather than unioning 603 */ 604 private void unionAnnotationSetsAndDirectories() { 605 transformAnnotationSets(dexA, aIndexMap); 606 transformAnnotationSets(dexB, bIndexMap); 607 transformAnnotationDirectories(dexA, aIndexMap); 608 transformAnnotationDirectories(dexB, bIndexMap); 609 transformStaticValues(dexA, aIndexMap); 610 transformStaticValues(dexB, bIndexMap); 611 } 612 613 private void transformAnnotationSets(DexBuffer in, IndexMap indexMap) { 614 TableOfContents.Section section = in.getTableOfContents().annotationSets; 615 if (section.exists()) { 616 DexBuffer.Section setIn = in.open(section.off); 617 for (int i = 0; i < section.size; i++) { 618 transformAnnotationSet(indexMap, setIn); 619 } 620 } 621 } 622 623 private void transformAnnotationDirectories(DexBuffer in, IndexMap indexMap) { 624 TableOfContents.Section section = in.getTableOfContents().annotationsDirectories; 625 if (section.exists()) { 626 DexBuffer.Section directoryIn = in.open(section.off); 627 for (int i = 0; i < section.size; i++) { 628 transformAnnotationDirectory(in, directoryIn, indexMap); 629 } 630 } 631 } 632 633 private void transformStaticValues(DexBuffer in, IndexMap indexMap) { 634 TableOfContents.Section section = in.getTableOfContents().encodedArrays; 635 if (section.exists()) { 636 DexBuffer.Section staticValuesIn = in.open(section.off); 637 for (int i = 0; i < section.size; i++) { 638 transformStaticValues(staticValuesIn, indexMap); 639 } 640 } 641 } 642 643 /** 644 * Reads a class_def_item beginning at {@code in} and writes the index and 645 * data. 646 */ 647 private void transformClassDef(DexBuffer in, ClassDef classDef, IndexMap indexMap) { 648 idsDefsOut.assertFourByteAligned(); 649 idsDefsOut.writeInt(classDef.getTypeIndex()); 650 idsDefsOut.writeInt(classDef.getAccessFlags()); 651 idsDefsOut.writeInt(classDef.getSupertypeIndex()); 652 idsDefsOut.writeInt(classDef.getInterfacesOffset()); 653 654 int sourceFileIndex = indexMap.adjustString(classDef.getSourceFileIndex()); 655 idsDefsOut.writeInt(sourceFileIndex); 656 657 int annotationsOff = classDef.getAnnotationsOffset(); 658 idsDefsOut.writeInt(indexMap.adjustAnnotationDirectory(annotationsOff)); 659 660 int classDataOff = classDef.getClassDataOffset(); 661 if (classDataOff == 0) { 662 idsDefsOut.writeInt(0); 663 } else { 664 idsDefsOut.writeInt(classDataOut.getPosition()); 665 ClassData classData = in.readClassData(classDef); 666 transformClassData(in, classData, indexMap); 667 } 668 669 int staticValuesOff = classDef.getStaticValuesOffset(); 670 idsDefsOut.writeInt(indexMap.adjustStaticValues(staticValuesOff)); 671 } 672 673 /** 674 * Transform all annotations on a class. 675 */ 676 private void transformAnnotationDirectory( 677 DexBuffer in, DexBuffer.Section directoryIn, IndexMap indexMap) { 678 contentsOut.annotationsDirectories.size++; 679 annotationsDirectoryOut.assertFourByteAligned(); 680 indexMap.putAnnotationDirectoryOffset( 681 directoryIn.getPosition(), annotationsDirectoryOut.getPosition()); 682 683 int classAnnotationsOffset = indexMap.adjustAnnotationSet(directoryIn.readInt()); 684 annotationsDirectoryOut.writeInt(classAnnotationsOffset); 685 686 int fieldsSize = directoryIn.readInt(); 687 annotationsDirectoryOut.writeInt(fieldsSize); 688 689 int methodsSize = directoryIn.readInt(); 690 annotationsDirectoryOut.writeInt(methodsSize); 691 692 int parameterListSize = directoryIn.readInt(); 693 annotationsDirectoryOut.writeInt(parameterListSize); 694 695 for (int i = 0; i < fieldsSize; i++) { 696 // field index 697 annotationsDirectoryOut.writeInt(indexMap.adjustField(directoryIn.readInt())); 698 699 // annotations offset 700 annotationsDirectoryOut.writeInt(indexMap.adjustAnnotationSet(directoryIn.readInt())); 701 } 702 703 for (int i = 0; i < methodsSize; i++) { 704 // method index 705 annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt())); 706 707 // annotation set offset 708 annotationsDirectoryOut.writeInt( 709 indexMap.adjustAnnotationSet(directoryIn.readInt())); 710 } 711 712 for (int i = 0; i < parameterListSize; i++) { 713 contentsOut.annotationSetRefLists.size++; 714 annotationSetRefListOut.assertFourByteAligned(); 715 716 // method index 717 annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt())); 718 719 // annotations offset 720 annotationsDirectoryOut.writeInt(annotationSetRefListOut.getPosition()); 721 DexBuffer.Section refListIn = in.open(directoryIn.readInt()); 722 723 // parameters 724 int parameterCount = refListIn.readInt(); 725 annotationSetRefListOut.writeInt(parameterCount); 726 for (int p = 0; p < parameterCount; p++) { 727 annotationSetRefListOut.writeInt(indexMap.adjustAnnotationSet(refListIn.readInt())); 728 } 729 } 730 } 731 732 /** 733 * Transform all annotations on a single type, member or parameter. 734 */ 735 private void transformAnnotationSet(IndexMap indexMap, DexBuffer.Section setIn) { 736 contentsOut.annotationSets.size++; 737 annotationSetOut.assertFourByteAligned(); 738 indexMap.putAnnotationSetOffset(setIn.getPosition(), annotationSetOut.getPosition()); 739 740 int size = setIn.readInt(); 741 annotationSetOut.writeInt(size); 742 743 for (int j = 0; j < size; j++) { 744 annotationSetOut.writeInt(indexMap.adjustAnnotation(setIn.readInt())); 745 } 746 } 747 748 private void transformClassData(DexBuffer in, ClassData classData, IndexMap indexMap) { 749 contentsOut.classDatas.size++; 750 751 ClassData.Field[] staticFields = classData.getStaticFields(); 752 ClassData.Field[] instanceFields = classData.getInstanceFields(); 753 ClassData.Method[] directMethods = classData.getDirectMethods(); 754 ClassData.Method[] virtualMethods = classData.getVirtualMethods(); 755 756 classDataOut.writeUleb128(staticFields.length); 757 classDataOut.writeUleb128(instanceFields.length); 758 classDataOut.writeUleb128(directMethods.length); 759 classDataOut.writeUleb128(virtualMethods.length); 760 761 transformFields(indexMap, staticFields); 762 transformFields(indexMap, instanceFields); 763 transformMethods(in, indexMap, directMethods); 764 transformMethods(in, indexMap, virtualMethods); 765 } 766 767 private void transformFields(IndexMap indexMap, ClassData.Field[] fields) { 768 int lastOutFieldIndex = 0; 769 for (ClassData.Field field : fields) { 770 int outFieldIndex = indexMap.adjustField(field.getFieldIndex()); 771 classDataOut.writeUleb128(outFieldIndex - lastOutFieldIndex); 772 lastOutFieldIndex = outFieldIndex; 773 classDataOut.writeUleb128(field.getAccessFlags()); 774 } 775 } 776 777 private void transformMethods(DexBuffer in, IndexMap indexMap, ClassData.Method[] methods) { 778 int lastOutMethodIndex = 0; 779 for (ClassData.Method method : methods) { 780 int outMethodIndex = indexMap.adjustMethod(method.getMethodIndex()); 781 classDataOut.writeUleb128(outMethodIndex - lastOutMethodIndex); 782 lastOutMethodIndex = outMethodIndex; 783 784 classDataOut.writeUleb128(method.getAccessFlags()); 785 786 if (method.getCodeOffset() == 0) { 787 classDataOut.writeUleb128(0); 788 } else { 789 codeOut.alignToFourBytes(); 790 classDataOut.writeUleb128(codeOut.getPosition()); 791 transformCode(in, in.readCode(method), indexMap); 792 } 793 } 794 } 795 796 private void transformCode(DexBuffer in, Code code, IndexMap indexMap) { 797 contentsOut.codes.size++; 798 codeOut.assertFourByteAligned(); 799 800 codeOut.writeUnsignedShort(code.getRegistersSize()); 801 codeOut.writeUnsignedShort(code.getInsSize()); 802 codeOut.writeUnsignedShort(code.getOutsSize()); 803 804 Code.Try[] tries = code.getTries(); 805 Code.CatchHandler[] catchHandlers = code.getCatchHandlers(); 806 codeOut.writeUnsignedShort(tries.length); 807 808 int debugInfoOffset = code.getDebugInfoOffset(); 809 if (debugInfoOffset != 0) { 810 codeOut.writeInt(debugInfoOut.getPosition()); 811 transformDebugInfoItem(in.open(debugInfoOffset), indexMap); 812 } else { 813 codeOut.writeInt(0); 814 } 815 816 short[] instructions = code.getInstructions(); 817 InstructionTransformer transformer = (in == dexA) 818 ? aInstructionTransformer 819 : bInstructionTransformer; 820 short[] newInstructions = transformer.transform(instructions); 821 codeOut.writeInt(newInstructions.length); 822 codeOut.write(newInstructions); 823 824 if (tries.length > 0) { 825 if (newInstructions.length % 2 == 1) { 826 codeOut.writeShort((short) 0); // padding 827 } 828 829 /* 830 * We can't write the tries until we've written the catch handlers. 831 * Unfortunately they're in the opposite order in the dex file so we 832 * need to transform them out-of-order. 833 */ 834 DexBuffer.Section triesSection = dexOut.open(codeOut.getPosition()); 835 codeOut.skip(tries.length * SizeOf.TRY_ITEM); 836 int[] offsets = transformCatchHandlers(indexMap, catchHandlers); 837 transformTries(triesSection, tries, offsets); 838 } 839 } 840 841 /** 842 * Writes the catch handlers to {@code codeOut} and returns their indices. 843 */ 844 private int[] transformCatchHandlers(IndexMap indexMap, Code.CatchHandler[] catchHandlers) { 845 int baseOffset = codeOut.getPosition(); 846 codeOut.writeUleb128(catchHandlers.length); 847 int[] offsets = new int[catchHandlers.length]; 848 for (int i = 0; i < catchHandlers.length; i++) { 849 offsets[i] = codeOut.getPosition() - baseOffset; 850 transformEncodedCatchHandler(catchHandlers[i], indexMap); 851 } 852 return offsets; 853 } 854 855 private void transformTries(DexBuffer.Section out, Code.Try[] tries, 856 int[] catchHandlerOffsets) { 857 for (Code.Try tryItem : tries) { 858 out.writeInt(tryItem.getStartAddress()); 859 out.writeUnsignedShort(tryItem.getInstructionCount()); 860 out.writeUnsignedShort(catchHandlerOffsets[tryItem.getCatchHandlerIndex()]); 861 } 862 } 863 864 private static final byte DBG_END_SEQUENCE = 0x00; 865 private static final byte DBG_ADVANCE_PC = 0x01; 866 private static final byte DBG_ADVANCE_LINE = 0x02; 867 private static final byte DBG_START_LOCAL = 0x03; 868 private static final byte DBG_START_LOCAL_EXTENDED = 0x04; 869 private static final byte DBG_END_LOCAL = 0x05; 870 private static final byte DBG_RESTART_LOCAL = 0x06; 871 private static final byte DBG_SET_PROLOGUE_END = 0x07; 872 private static final byte DBG_SET_EPILOGUE_BEGIN = 0x08; 873 private static final byte DBG_SET_FILE = 0x09; 874 875 private void transformDebugInfoItem(DexBuffer.Section in, IndexMap indexMap) { 876 contentsOut.debugInfos.size++; 877 int lineStart = in.readUleb128(); 878 debugInfoOut.writeUleb128(lineStart); 879 880 int parametersSize = in.readUleb128(); 881 debugInfoOut.writeUleb128(parametersSize); 882 883 for (int p = 0; p < parametersSize; p++) { 884 int parameterName = in.readUleb128p1(); 885 debugInfoOut.writeUleb128p1(indexMap.adjustString(parameterName)); 886 } 887 888 int addrDiff; // uleb128 address delta. 889 int lineDiff; // sleb128 line delta. 890 int registerNum; // uleb128 register number. 891 int nameIndex; // uleb128p1 string index. Needs indexMap adjustment. 892 int typeIndex; // uleb128p1 type index. Needs indexMap adjustment. 893 int sigIndex; // uleb128p1 string index. Needs indexMap adjustment. 894 895 while (true) { 896 int opcode = in.readByte(); 897 debugInfoOut.writeByte(opcode); 898 899 switch (opcode) { 900 case DBG_END_SEQUENCE: 901 return; 902 903 case DBG_ADVANCE_PC: 904 addrDiff = in.readUleb128(); 905 debugInfoOut.writeUleb128(addrDiff); 906 break; 907 908 case DBG_ADVANCE_LINE: 909 lineDiff = in.readSleb128(); 910 debugInfoOut.writeSleb128(lineDiff); 911 break; 912 913 case DBG_START_LOCAL: 914 case DBG_START_LOCAL_EXTENDED: 915 registerNum = in.readUleb128(); 916 debugInfoOut.writeUleb128(registerNum); 917 nameIndex = in.readUleb128p1(); 918 debugInfoOut.writeUleb128p1(indexMap.adjustString(nameIndex)); 919 typeIndex = in.readUleb128p1(); 920 debugInfoOut.writeUleb128p1(indexMap.adjustType(typeIndex)); 921 if (opcode == DBG_START_LOCAL_EXTENDED) { 922 sigIndex = in.readUleb128p1(); 923 debugInfoOut.writeUleb128p1(indexMap.adjustString(sigIndex)); 924 } 925 break; 926 927 case DBG_END_LOCAL: 928 case DBG_RESTART_LOCAL: 929 registerNum = in.readUleb128(); 930 debugInfoOut.writeUleb128(registerNum); 931 break; 932 933 case DBG_SET_FILE: 934 nameIndex = in.readUleb128p1(); 935 debugInfoOut.writeUleb128p1(indexMap.adjustString(nameIndex)); 936 break; 937 938 case DBG_SET_PROLOGUE_END: 939 case DBG_SET_EPILOGUE_BEGIN: 940 default: 941 break; 942 } 943 } 944 } 945 946 private void transformEncodedCatchHandler(Code.CatchHandler catchHandler, IndexMap indexMap) { 947 int catchAllAddress = catchHandler.getCatchAllAddress(); 948 int[] typeIndexes = catchHandler.getTypeIndexes(); 949 int[] addresses = catchHandler.getAddresses(); 950 951 if (catchAllAddress != -1) { 952 codeOut.writeSleb128(-typeIndexes.length); 953 } else { 954 codeOut.writeSleb128(typeIndexes.length); 955 } 956 957 for (int i = 0; i < typeIndexes.length; i++) { 958 codeOut.writeUleb128(indexMap.adjustType(typeIndexes[i])); 959 codeOut.writeUleb128(addresses[i]); 960 } 961 962 if (catchAllAddress != -1) { 963 codeOut.writeUleb128(catchAllAddress); 964 } 965 } 966 967 private void transformStaticValues(DexBuffer.Section in, IndexMap indexMap) { 968 contentsOut.encodedArrays.size++; 969 indexMap.putStaticValuesOffset(in.getPosition(), encodedArrayOut.getPosition()); 970 indexMap.adjustEncodedArray(in.readEncodedArray()).writeTo(encodedArrayOut); 971 } 972 973 /** 974 * Byte counts for the sections written when creating a dex. Target sizes 975 * are defined in one of two ways: 976 * <ul> 977 * <li>By pessimistically guessing how large the union of dex files will be. 978 * We're pessimistic because we can't predict the amount of duplication 979 * between dex files, nor can we predict the length of ULEB-encoded 980 * offsets or indices. 981 * <li>By exactly measuring an existing dex. 982 * </ul> 983 */ 984 private static class WriterSizes { 985 private int header = SizeOf.HEADER_ITEM; 986 private int idsDefs; 987 private int mapList; 988 private int typeList; 989 private int classData; 990 private int code; 991 private int stringData; 992 private int debugInfo; 993 private int encodedArray; 994 private int annotationsDirectory; 995 private int annotationsSet; 996 private int annotationsSetRefList; 997 private int annotation; 998 999 /** 1000 * Compute sizes for merging a and b. 1001 */ 1002 public WriterSizes(DexBuffer a, DexBuffer b) { 1003 plus(a.getTableOfContents(), false); 1004 plus(b.getTableOfContents(), false); 1005 } 1006 1007 public WriterSizes(DexMerger dexMerger) { 1008 header = dexMerger.headerOut.used(); 1009 idsDefs = dexMerger.idsDefsOut.used(); 1010 mapList = dexMerger.mapListOut.used(); 1011 typeList = dexMerger.typeListOut.used(); 1012 classData = dexMerger.classDataOut.used(); 1013 code = dexMerger.codeOut.used(); 1014 stringData = dexMerger.stringDataOut.used(); 1015 debugInfo = dexMerger.debugInfoOut.used(); 1016 encodedArray = dexMerger.encodedArrayOut.used(); 1017 annotationsDirectory = dexMerger.annotationsDirectoryOut.used(); 1018 annotationsSet = dexMerger.annotationSetOut.used(); 1019 annotationsSetRefList = dexMerger.annotationSetRefListOut.used(); 1020 annotation = dexMerger.annotationOut.used(); 1021 } 1022 1023 public void plus(TableOfContents contents, boolean exact) { 1024 idsDefs += contents.stringIds.size * SizeOf.STRING_ID_ITEM 1025 + contents.typeIds.size * SizeOf.TYPE_ID_ITEM 1026 + contents.protoIds.size * SizeOf.PROTO_ID_ITEM 1027 + contents.fieldIds.size * SizeOf.MEMBER_ID_ITEM 1028 + contents.methodIds.size * SizeOf.MEMBER_ID_ITEM 1029 + contents.classDefs.size * SizeOf.CLASS_DEF_ITEM; 1030 mapList = SizeOf.UINT + (contents.sections.length * SizeOf.MAP_ITEM); 1031 typeList += contents.typeLists.byteCount; 1032 stringData += contents.stringDatas.byteCount; 1033 annotationsDirectory += contents.annotationsDirectories.byteCount; 1034 annotationsSet += contents.annotationSets.byteCount; 1035 annotationsSetRefList += contents.annotationSetRefLists.byteCount; 1036 1037 if (exact) { 1038 code += contents.codes.byteCount; 1039 classData += contents.classDatas.byteCount; 1040 encodedArray += contents.encodedArrays.byteCount; 1041 annotation += contents.annotations.byteCount; 1042 debugInfo += contents.debugInfos.byteCount; 1043 } else { 1044 // at most 1/4 of the bytes in a code section are uleb/sleb 1045 code += (int) Math.ceil(contents.codes.byteCount * 1.25); 1046 // at most 1/3 of the bytes in a class data section are uleb/sleb 1047 classData += (int) Math.ceil(contents.classDatas.byteCount * 1.34); 1048 // all of the bytes in an encoding arrays section may be uleb/sleb 1049 encodedArray += contents.encodedArrays.byteCount * 2; 1050 // all of the bytes in an annotations section may be uleb/sleb 1051 annotation += (int) Math.ceil(contents.annotations.byteCount * 2); 1052 // all of the bytes in a debug info section may be uleb/sleb 1053 debugInfo += contents.debugInfos.byteCount * 2; 1054 } 1055 1056 typeList = DexBuffer.fourByteAlign(typeList); 1057 code = DexBuffer.fourByteAlign(code); 1058 } 1059 1060 public int size() { 1061 return header + idsDefs + mapList + typeList + classData + code + stringData + debugInfo 1062 + encodedArray + annotationsDirectory + annotationsSet + annotationsSetRefList 1063 + annotation; 1064 } 1065 } 1066 1067 public static void main(String[] args) throws IOException { 1068 if (args.length != 3) { 1069 printUsage(); 1070 return; 1071 } 1072 1073 DexBuffer dexA = new DexBuffer(new File(args[1])); 1074 DexBuffer dexB = new DexBuffer(new File(args[2])); 1075 DexBuffer merged = new DexMerger(dexA, dexB, CollisionPolicy.KEEP_FIRST).merge(); 1076 merged.writeTo(new File(args[0])); 1077 } 1078 1079 private static void printUsage() { 1080 System.out.println("Usage: DexMerger <out.dex> <a.dex> <b.dex>"); 1081 System.out.println(); 1082 System.out.println("If both a and b define the same classes, a's copy will be used."); 1083 } 1084} 1085