dx/src/com/android/dx/merge/DexMerger.java

   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
  17 package com.android.dx.merge;
  18
  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;
  31 import java.io.File;
  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;
  38 import java.util.Set;
  39
  40 /**
  41  * Combine two dex files into one.
  42  */
  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;
  48
  49     private final DexBuffer dexOut = new DexBuffer();
  50
  51     private final DexBuffer.Section headerOut;
  52
  53     /** All IDs and definitions sections */
  54     private final DexBuffer.Section idsDefsOut;
  55
  56     private final DexBuffer.Section mapListOut;
  57
  58     private final DexBuffer.Section typeListOut;
  59
  60     private final DexBuffer.Section classDataOut;
  61
  62     private final DexBuffer.Section codeOut;
  63
  64     private final DexBuffer.Section stringDataOut;
  65
  66     private final DexBuffer.Section debugInfoOut;
  67
  68     private final DexBuffer.Section encodedArrayOut;
  69
  70     /** annotations directory on a type */
  71     private final DexBuffer.Section annotationsDirectoryOut;
  72
  73     /** sets of annotations on a member, parameter or type */
  74     private final DexBuffer.Section annotationSetOut;
  75
  76     /** parameter lists */
  77     private final DexBuffer.Section annotationSetRefListOut;
  78
  79     /** individual annotations, each containing zero or more fields */
  80     private final DexBuffer.Section annotationOut;
  81
  82     private final TableOfContents contentsOut;
  83
  84     private final IndexMap aIndexMap;
  85     private final IndexMap bIndexMap;
  86     private final InstructionTransformer aInstructionTransformer;
  87     private final InstructionTransformer bInstructionTransformer;
  88
  89     /** minimum number of wasted bytes before it's worthwhile to compact the result */
  90     private int compactWasteThreshold = 1024 * 1024; // 1MiB
  91
  92     public DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy)
  93             throws IOException {
  94         this(dexA, dexB, collisionPolicy, new WriterSizes(dexA, dexB));
  95     }
  96
  97     private DexMerger(DexBuffer dexA, DexBuffer dexB, CollisionPolicy collisionPolicy,
  98             WriterSizes writerSizes) throws IOException {
  99         this.dexA = dexA;
 100         this.dexB = dexB;
 101         this.collisionPolicy = collisionPolicy;
 102         this.writerSizes = writerSizes;
 103
 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);
 110
 111         headerOut = dexOut.appendSection(writerSizes.header, "header");
 112         idsDefsOut = dexOut.appendSection(writerSizes.idsDefs, "ids defs");
 113
 114         contentsOut = dexOut.getTableOfContents();
 115         contentsOut.dataOff = dexOut.getLength();
 116
 117         contentsOut.mapList.off = dexOut.getLength();
 118         contentsOut.mapList.size = 1;
 119         mapListOut = dexOut.appendSection(writerSizes.mapList, "map list");
 120
 121         contentsOut.typeLists.off = dexOut.getLength();
 122         typeListOut = dexOut.appendSection(writerSizes.typeList, "type list");
 123
 124         contentsOut.annotationSetRefLists.off = dexOut.getLength();
 125         annotationSetRefListOut = dexOut.appendSection(
 126                 writerSizes.annotationsSetRefList, "annotation set ref list");
 127
 128         contentsOut.annotationSets.off = dexOut.getLength();
 129         annotationSetOut = dexOut.appendSection(writerSizes.annotationsSet, "annotation sets");
 130
 131         contentsOut.classDatas.off = dexOut.getLength();
 132         classDataOut = dexOut.appendSection(writerSizes.classData, "class data");
 133
 134         contentsOut.codes.off = dexOut.getLength();
 135         codeOut = dexOut.appendSection(writerSizes.code, "code");
 136
 137         contentsOut.stringDatas.off = dexOut.getLength();
 138         stringDataOut = dexOut.appendSection(writerSizes.stringData, "string data");
 139
 140         contentsOut.debugInfos.off = dexOut.getLength();
 141         debugInfoOut = dexOut.appendSection(writerSizes.debugInfo, "debug info");
 142
 143         contentsOut.annotations.off = dexOut.getLength();
 144         annotationOut = dexOut.appendSection(writerSizes.annotation, "annotation");
 145
 146         contentsOut.encodedArrays.off = dexOut.getLength();
 147         encodedArrayOut = dexOut.appendSection(writerSizes.encodedArray, "encoded array");
 148
 149         contentsOut.annotationsDirectories.off = dexOut.getLength();
 150         annotationsDirectoryOut = dexOut.appendSection(
 151                 writerSizes.annotationsDirectory, "annotations directory");
 152
 153         dexOut.noMoreSections();
 154         contentsOut.dataSize = dexOut.getLength() - contentsOut.dataOff;
 155     }
 156
 157     public void setCompactWasteThreshold(int compactWasteThreshold) {
 158         this.compactWasteThreshold = compactWasteThreshold;
 159     }
 160
 161     private DexBuffer mergeDexBuffers() throws IOException {
 162         mergeStringIds();
 163         mergeTypeIds();
 164         mergeTypeLists();
 165         mergeProtoIds();
 166         mergeFieldIds();
 167         mergeMethodIds();
 168         mergeAnnotations();
 169         unionAnnotationSetsAndDirectories();
 170         mergeClassDefs();
 171
 172         // write the header
 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);
 179
 180         // generate and write the hashes
 181         new DexHasher().writeHashes(dexOut);
 182
 183         return dexOut;
 184     }
 185
 186     public DexBuffer merge() throws IOException {
 187         long start = System.nanoTime();
 188         DexBuffer result = mergeDexBuffers();
 189
 190         /*
 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.
 194          */
 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);
 205         }
 206
 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);
 217
 218         return result;
 219     }
 220
 221     /**
 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.
 224      */
 225     abstract class IdMerger<T extends Comparable<T>> {
 226         private final DexBuffer.Section out;
 227
 228         protected IdMerger(DexBuffer.Section out) {
 229             this.out = out;
 230         }
 231
 232         /**
 233          * Merges already-sorted sections, reading only two values into memory
 234          * at a time.
 235          */
 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();
 240
 241             DexBuffer.Section inA = aSection.exists() ? dexA.open(aSection.off) : null;
 242             DexBuffer.Section inB = bSection.exists() ? dexB.open(bSection.off) : null;
 243             int aOffset = -1;
 244             int bOffset = -1;
 245             int aIndex = 0;
 246             int bIndex = 0;
 247             int outCount = 0;
 248             T a = null;
 249             T b = null;
 250
 251             while (true) {
 252                 if (a == null && aIndex < aSection.size) {
 253                     aOffset = inA.getPosition();
 254                     a = read(inA, aIndexMap, aIndex);
 255                 }
 256                 if (b == null && bIndex < bSection.size) {
 257                     bOffset = inB.getPosition();
 258                     b = read(inB, bIndexMap, bIndex);
 259                 }
 260
 261                 // Write the smaller of a and b. If they're equal, write only once
 262                 boolean advanceA;
 263                 boolean advanceB;
 264                 if (a != null && b != null) {
 265                     int compare = a.compareTo(b);
 266                     advanceA = compare <= 0;
 267                     advanceB = compare >= 0;
 268                 } else {
 269                     advanceA = (a != null);
 270                     advanceB = (b != null);
 271                 }
 272
 273                 T toWrite = null;
 274                 if (advanceA) {
 275                     toWrite = a;
 276                     updateIndex(aOffset, aIndexMap, aIndex++, outCount);
 277                     a = null;
 278                     aOffset = -1;
 279                 }
 280                 if (advanceB) {
 281                     toWrite = b;
 282                     updateIndex(bOffset, bIndexMap, bIndex++, outCount);
 283                     b = null;
 284                     bOffset = -1;
 285                 }
 286                 if (toWrite == null) {
 287                     break; // advanceA == false && advanceB == false
 288                 }
 289                 write(toWrite);
 290                 outCount++;
 291             }
 292
 293             getSection(contentsOut).size = outCount;
 294         }
 295
 296         /**
 297          * Merges unsorted sections by reading them completely into memory and
 298          * sorting in memory.
 299          */
 300         public final void mergeUnsorted() {
 301             getSection(contentsOut).off = out.getPosition();
 302
 303             List<UnsortedValue> all = new ArrayList<UnsortedValue>();
 304             all.addAll(readUnsortedValues(dexA, aIndexMap));
 305             all.addAll(readUnsortedValues(dexB, bIndexMap));
 306             Collections.sort(all);
 307
 308             int outCount = 0;
 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);
 312
 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);
 316                 }
 317
 318                 write(e1.value);
 319                 outCount++;
 320             }
 321
 322             getSection(contentsOut).size = outCount;
 323         }
 324
 325         private List<UnsortedValue> readUnsortedValues(DexBuffer source, IndexMap indexMap) {
 326             TableOfContents.Section section = getSection(source.getTableOfContents());
 327             if (!section.exists()) {
 328                 return Collections.emptyList();
 329             }
 330
 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));
 337             }
 338             return result;
 339         }
 340
 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);
 345
 346         class UnsortedValue implements Comparable<UnsortedValue> {
 347             final DexBuffer source;
 348             final IndexMap indexMap;
 349             final T value;
 350             final int index;
 351             final int offset;
 352
 353             UnsortedValue(DexBuffer source, IndexMap indexMap, T value, int index, int offset) {
 354                 this.source = source;
 355                 this.indexMap = indexMap;
 356                 this.value = value;
 357                 this.index = index;
 358                 this.offset = offset;
 359             }
 360
 361             public int compareTo(UnsortedValue unsortedValue) {
 362                 return value.compareTo(unsortedValue.value);
 363             }
 364         }
 365     }
 366
 367     private IndexMap getIndexMap(DexBuffer dexBuffer) {
 368         if (dexBuffer == dexA) {
 369             return aIndexMap;
 370         } else if (dexBuffer == dexB) {
 371             return bIndexMap;
 372         } else {
 373             throw new IllegalArgumentException();
 374         }
 375     }
 376
 377     private void mergeStringIds() {
 378         new IdMerger<String>(idsDefsOut) {
 379             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 380                 return tableOfContents.stringIds;
 381             }
 382
 383             @Override String read(DexBuffer.Section in, IndexMap indexMap, int index) {
 384                 return in.readString();
 385             }
 386
 387             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 388                 indexMap.stringIds[oldIndex] = newIndex;
 389             }
 390
 391             @Override void write(String value) {
 392                 contentsOut.stringDatas.size++;
 393                 idsDefsOut.writeInt(stringDataOut.getPosition());
 394                 stringDataOut.writeStringData(value);
 395             }
 396         }.mergeSorted();
 397     }
 398
 399     private void mergeTypeIds() {
 400         new IdMerger<Integer>(idsDefsOut) {
 401             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 402                 return tableOfContents.typeIds;
 403             }
 404
 405             @Override Integer read(DexBuffer.Section in, IndexMap indexMap, int index) {
 406                 int stringIndex = in.readInt();
 407                 return indexMap.adjustString(stringIndex);
 408             }
 409
 410             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 411                 indexMap.typeIds[oldIndex] = (short) newIndex;
 412             }
 413
 414             @Override void write(Integer value) {
 415                 idsDefsOut.writeInt(value);
 416             }
 417         }.mergeSorted();
 418     }
 419
 420     private void mergeTypeLists() {
 421         new IdMerger<TypeList>(typeListOut) {
 422             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 423                 return tableOfContents.typeLists;
 424             }
 425
 426             @Override TypeList read(DexBuffer.Section in, IndexMap indexMap, int index) {
 427                 return indexMap.adjustTypeList(in.readTypeList());
 428             }
 429
 430             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 431                 indexMap.putTypeListOffset(offset, typeListOut.getPosition());
 432             }
 433
 434             @Override void write(TypeList value) {
 435                 typeListOut.writeTypeList(value);
 436             }
 437         }.mergeUnsorted();
 438     }
 439
 440     private void mergeProtoIds() {
 441         new IdMerger<ProtoId>(idsDefsOut) {
 442             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 443                 return tableOfContents.protoIds;
 444             }
 445
 446             @Override ProtoId read(DexBuffer.Section in, IndexMap indexMap, int index) {
 447                 return indexMap.adjust(in.readProtoId());
 448             }
 449
 450             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 451                 indexMap.protoIds[oldIndex] = (short) newIndex;
 452             }
 453
 454             @Override void write(ProtoId value) {
 455                 value.writeTo(idsDefsOut);
 456             }
 457         }.mergeSorted();
 458     }
 459
 460     private void mergeFieldIds() {
 461         new IdMerger<FieldId>(idsDefsOut) {
 462             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 463                 return tableOfContents.fieldIds;
 464             }
 465
 466             @Override FieldId read(DexBuffer.Section in, IndexMap indexMap, int index) {
 467                 return indexMap.adjust(in.readFieldId());
 468             }
 469
 470             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 471                 indexMap.fieldIds[oldIndex] = (short) newIndex;
 472             }
 473
 474             @Override void write(FieldId value) {
 475                 value.writeTo(idsDefsOut);
 476             }
 477         }.mergeSorted();
 478     }
 479
 480     private void mergeMethodIds() {
 481         new IdMerger<MethodId>(idsDefsOut) {
 482             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 483                 return tableOfContents.methodIds;
 484             }
 485
 486             @Override MethodId read(DexBuffer.Section in, IndexMap indexMap, int index) {
 487                 return indexMap.adjust(in.readMethodId());
 488             }
 489
 490             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 491                 indexMap.methodIds[oldIndex] = (short) newIndex;
 492             }
 493
 494             @Override void write(MethodId methodId) {
 495                 methodId.writeTo(idsDefsOut);
 496             }
 497         }.mergeSorted();
 498     }
 499
 500     private void mergeAnnotations() {
 501         new IdMerger<Annotation>(annotationOut) {
 502             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
 503                 return tableOfContents.annotations;
 504             }
 505
 506             @Override Annotation read(DexBuffer.Section in, IndexMap indexMap, int index) {
 507                 return indexMap.adjust(in.readAnnotation());
 508             }
 509
 510             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
 511                 indexMap.putAnnotationOffset(offset, annotationOut.getPosition());
 512             }
 513
 514             @Override void write(Annotation value) {
 515                 value.writeTo(annotationOut);
 516             }
 517         }.mergeUnsorted();
 518     }
 519
 520     private void mergeClassDefs() {
 521         SortableType[] types = getSortedTypes();
 522         contentsOut.classDefs.off = idsDefsOut.getPosition();
 523         contentsOut.classDefs.size = types.length;
 524
 525         for (SortableType type : types) {
 526             DexBuffer in = type.getBuffer();
 527             IndexMap indexMap = (in == dexA) ? aIndexMap : bIndexMap;
 528             transformClassDef(in, type.getClassDef(), indexMap);
 529         }
 530     }
 531
 532     /**
 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.
 535      */
 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);
 541
 542         /*
 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
 546          * is 11 types deep.
 547          */
 548         while (true) {
 549             boolean allDone = true;
 550             for (SortableType sortableType : sortableTypes) {
 551                 if (sortableType != null && !sortableType.isDepthAssigned()) {
 552                     allDone &= sortableType.tryAssignDepth(sortableTypes);
 553                 }
 554             }
 555             if (allDone) {
 556                 break;
 557             }
 558         }
 559
 560         // Now that all types have depth information, the result can be sorted
 561         Arrays.sort(sortableTypes, SortableType.NULLS_LAST_ORDER);
 562
 563         // Strip nulls from the end
 564         int firstNull = Arrays.asList(sortableTypes).indexOf(null);
 565         return firstNull != -1
 566                 ? Arrays.copyOfRange(sortableTypes, 0, firstNull)
 567                 : sortableTypes;
 568     }
 569
 570     /**
 571      * Reads just enough data on each class so that we can sort it and then find
 572      * it later.
 573      */
 574     private void readSortableTypes(SortableType[] sortableTypes, DexBuffer buffer,
 575             IndexMap indexMap) {
 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()));
 584             }
 585         }
 586     }
 587
 588     /**
 589      * Copy annotation sets from each input to the output.
 590      *
 591      * TODO: this may write multiple copies of the same annotation set.
 592      * We should shrink the output by merging rather than unioning
 593      */
 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);
 601     }
 602
 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);
 609             }
 610         }
 611     }
 612
 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);
 619             }
 620         }
 621     }
 622
 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);
 629             }
 630         }
 631     }
 632
 633     /**
 634      * Reads a class_def_item beginning at {@code in} and writes the index and
 635      * data.
 636      */
 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());
 643
 644         int sourceFileIndex = indexMap.adjustString(classDef.getSourceFileIndex());
 645         idsDefsOut.writeInt(sourceFileIndex);
 646
 647         int annotationsOff = classDef.getAnnotationsOffset();
 648         idsDefsOut.writeInt(indexMap.adjustAnnotationDirectory(annotationsOff));
 649
 650         int classDataOff = classDef.getClassDataOffset();
 651         if (classDataOff == 0) {
 652             idsDefsOut.writeInt(0);
 653         } else {
 654             idsDefsOut.writeInt(classDataOut.getPosition());
 655             ClassData classData = in.readClassData(classDef);
 656             transformClassData(in, classData, indexMap);
 657         }
 658
 659         int staticValuesOff = classDef.getStaticValuesOffset();
 660         idsDefsOut.writeInt(indexMap.adjustStaticValues(staticValuesOff));
 661     }
 662
 663     /**
 664      * Transform all annotations on a class.
 665      */
 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());
 672
 673         int classAnnotationsOffset = indexMap.adjustAnnotationSet(directoryIn.readInt());
 674         annotationsDirectoryOut.writeInt(classAnnotationsOffset);
 675
 676         int fieldsSize = directoryIn.readInt();
 677         annotationsDirectoryOut.writeInt(fieldsSize);
 678
 679         int methodsSize = directoryIn.readInt();
 680         annotationsDirectoryOut.writeInt(methodsSize);
 681
 682         int parameterListSize = directoryIn.readInt();
 683         annotationsDirectoryOut.writeInt(parameterListSize);
 684
 685         for (int i = 0; i < fieldsSize; i++) {
 686             // field index
 687             annotationsDirectoryOut.writeInt(indexMap.adjustField(directoryIn.readInt()));
 688
 689             // annotations offset
 690             annotationsDirectoryOut.writeInt(indexMap.adjustAnnotationSet(directoryIn.readInt()));
 691         }
 692
 693         for (int i = 0; i < methodsSize; i++) {
 694             // method index
 695             annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt()));
 696
 697             // annotation set offset
 698             annotationsDirectoryOut.writeInt(
 699                     indexMap.adjustAnnotationSet(directoryIn.readInt()));
 700         }
 701
 702         for (int i = 0; i < parameterListSize; i++) {
 703             contentsOut.annotationSetRefLists.size++;
 704             annotationSetRefListOut.assertFourByteAligned();
 705
 706             // method index
 707             annotationsDirectoryOut.writeInt(indexMap.adjustMethod(directoryIn.readInt()));
 708
 709             // annotations offset
 710             annotationsDirectoryOut.writeInt(annotationSetRefListOut.getPosition());
 711             DexBuffer.Section refListIn = in.open(directoryIn.readInt());
 712
 713             // parameters
 714             int parameterCount = refListIn.readInt();
 715             annotationSetRefListOut.writeInt(parameterCount);
 716             for (int p = 0; p < parameterCount; p++) {
 717                 annotationSetRefListOut.writeInt(indexMap.adjustAnnotationSet(refListIn.readInt()));
 718             }
 719         }
 720     }
 721
 722     /**
 723      * Transform all annotations on a single type, member or parameter.
 724      */
 725     private void transformAnnotationSet(IndexMap indexMap, DexBuffer.Section setIn) {
 726         contentsOut.annotationSets.size++;
 727         annotationSetOut.assertFourByteAligned();
 728         indexMap.putAnnotationSetOffset(setIn.getPosition(), annotationSetOut.getPosition());
 729
 730         int size = setIn.readInt();
 731         annotationSetOut.writeInt(size);
 732
 733         for (int j = 0; j < size; j++) {
 734             annotationSetOut.writeInt(indexMap.adjustAnnotation(setIn.readInt()));
 735         }
 736     }
 737
 738     private void transformClassData(DexBuffer in, ClassData classData, IndexMap indexMap) {
 739         contentsOut.classDatas.size++;
 740
 741         ClassData.Field[] staticFields = classData.getStaticFields();
 742         ClassData.Field[] instanceFields = classData.getInstanceFields();
 743         ClassData.Method[] directMethods = classData.getDirectMethods();
 744         ClassData.Method[] virtualMethods = classData.getVirtualMethods();
 745
 746         classDataOut.writeUleb128(staticFields.length);
 747         classDataOut.writeUleb128(instanceFields.length);
 748         classDataOut.writeUleb128(directMethods.length);
 749         classDataOut.writeUleb128(virtualMethods.length);
 750
 751         transformFields(indexMap, staticFields);
 752         transformFields(indexMap, instanceFields);
 753         transformMethods(in, indexMap, directMethods);
 754         transformMethods(in, indexMap, virtualMethods);
 755     }
 756
 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());
 764         }
 765     }
 766
 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;
 773
 774             classDataOut.writeUleb128(method.getAccessFlags());
 775
 776             if (method.getCodeOffset() == 0) {
 777                 classDataOut.writeUleb128(0);
 778             } else {
 779                 codeOut.alignToFourBytes();
 780                 classDataOut.writeUleb128(codeOut.getPosition());
 781                 transformCode(in, in.readCode(method), indexMap);
 782             }
 783         }
 784     }
 785
 786     private void transformCode(DexBuffer in, Code code, IndexMap indexMap) {
 787         contentsOut.codes.size++;
 788         codeOut.assertFourByteAligned();
 789
 790         codeOut.writeUnsignedShort(code.getRegistersSize());
 791         codeOut.writeUnsignedShort(code.getInsSize());
 792         codeOut.writeUnsignedShort(code.getOutsSize());
 793
 794         Code.Try[] tries = code.getTries();
 795         codeOut.writeUnsignedShort(tries.length);
 796
 797         int debugInfoOffset = code.getDebugInfoOffset();
 798         if (debugInfoOffset != 0) {
 799             codeOut.writeInt(debugInfoOut.getPosition());
 800             transformDebugInfoItem(in.open(debugInfoOffset), indexMap);
 801         } else {
 802             codeOut.writeInt(0);
 803         }
 804
 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);
 812
 813         if (tries.length > 0) {
 814             if (newInstructions.length % 2 == 1) {
 815                 codeOut.writeShort((short) 0); // padding
 816             }
 817             for (Code.Try tryItem : tries) {
 818                 codeOut.writeInt(tryItem.getStartAddress());
 819                 codeOut.writeUnsignedShort(tryItem.getInstructionCount());
 820                 codeOut.writeUnsignedShort(tryItem.getHandlerOffset());
 821             }
 822             Code.CatchHandler[] catchHandlers = code.getCatchHandlers();
 823             codeOut.writeUleb128(catchHandlers.length);
 824             for (Code.CatchHandler catchHandler : catchHandlers) {
 825                 transformEncodedCatchHandler(catchHandler, indexMap);
 826             }
 827         }
 828     }
 829
 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;
 840
 841     private void transformDebugInfoItem(DexBuffer.Section in, IndexMap indexMap) {
 842         int lineStart = in.readUleb128();
 843         debugInfoOut.writeUleb128(lineStart);
 844
 845         int parametersSize = in.readUleb128();
 846         debugInfoOut.writeUleb128(parametersSize);
 847
 848         for (int p = 0; p < parametersSize; p++) {
 849             int parameterName = in.readUleb128p1();
 850             debugInfoOut.writeUleb128p1(indexMap.adjustString(parameterName));
 851         }
 852
 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.
 859
 860         while (true) {
 861             int opcode = in.readByte();
 862             debugInfoOut.writeByte(opcode);
 863
 864             switch (opcode) {
 865             case DBG_END_SEQUENCE:
 866                 return;
 867
 868             case DBG_ADVANCE_PC:
 869                 addrDiff = in.readUleb128();
 870                 debugInfoOut.writeUleb128(addrDiff);
 871                 break;
 872
 873             case DBG_ADVANCE_LINE:
 874                 lineDiff = in.readSleb128();
 875                 debugInfoOut.writeSleb128(lineDiff);
 876                 break;
 877
 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));
 889                 }
 890                 break;
 891
 892             case DBG_END_LOCAL:
 893             case DBG_RESTART_LOCAL:
 894                 registerNum = in.readUleb128();
 895                 debugInfoOut.writeUleb128(registerNum);
 896                 break;
 897
 898             case DBG_SET_FILE:
 899                 nameIndex = in.readUleb128p1();
 900                 debugInfoOut.writeUleb128p1(indexMap.adjustString(nameIndex));
 901                 break;
 902
 903             case DBG_SET_PROLOGUE_END:
 904             case DBG_SET_EPILOGUE_BEGIN:
 905             default:
 906                 break;
 907             }
 908         }
 909     }
 910
 911     private void transformEncodedCatchHandler(Code.CatchHandler catchHandler, IndexMap indexMap) {
 912         int catchAllAddress = catchHandler.getCatchAllAddress();
 913         int[] typeIndexes = catchHandler.getTypeIndexes();
 914         int[] addresses = catchHandler.getAddresses();
 915
 916         if (catchAllAddress != -1) {
 917             codeOut.writeSleb128(-typeIndexes.length);
 918         } else {
 919             codeOut.writeSleb128(typeIndexes.length);
 920         }
 921
 922         for (int i = 0; i < typeIndexes.length; i++) {
 923             codeOut.writeUleb128(indexMap.adjustType(typeIndexes[i]));
 924             codeOut.writeUleb128(addresses[i]);
 925         }
 926
 927         if (catchAllAddress != -1) {
 928             codeOut.writeUleb128(catchAllAddress);
 929         }
 930     }
 931
 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);
 936     }
 937
 938     /**
 939      * Byte counts for the sections written when creating a dex. Target sizes
 940      * are defined in one of two ways:
 941      * <ul>
 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.
 947      * </ul>
 948      */
 949     private static class WriterSizes {
 950         private int header = SizeOf.HEADER_ITEM;
 951         private int idsDefs;
 952         private int mapList;
 953         private int typeList;
 954         private int classData;
 955         private int code;
 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;
 963
 964         /**
 965          * Compute sizes for merging a and b.
 966          */
 967         public WriterSizes(DexBuffer a, DexBuffer b) {
 968             plus(a.getTableOfContents(), false);
 969             plus(b.getTableOfContents(), false);
 970         }
 971
 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();
 986         }
 987
 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;
1001
1002             if (exact) {
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;
1008             } else {
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;
1019             }
1020
1021             typeList = DexBuffer.fourByteAlign(typeList);
1022             code = DexBuffer.fourByteAlign(code);
1023         }
1024
1025         public int size() {
1026             return header + idsDefs + mapList + typeList + classData + code + stringData + debugInfo
1027                     + encodedArray + annotationsDirectory + annotationsSet + annotationsSetRefList
1028                     + annotation;
1029         }
1030     }
1031
1032     public static void main(String[] args) throws IOException {
1033         if (args.length != 3) {
1034             printUsage();
1035             return;
1036         }
1037
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]));
1042     }
1043
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.");
1048     }
1049 }