| /* |
| * Copyright (C) 2007 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.dx.dex.code; |
| |
| import com.android.dx.io.Opcodes; |
| import com.android.dx.rop.code.RegisterSpecList; |
| import com.android.dx.rop.code.SourcePosition; |
| import com.android.dx.util.AnnotatedOutput; |
| import com.android.dx.util.Hex; |
| import com.android.dx.util.IntList; |
| |
| /** |
| * Pseudo-instruction which holds switch data. The switch data is |
| * a map of values to target addresses, and this class writes the data |
| * in either a "packed" or "sparse" form. |
| */ |
| public final class SwitchData extends VariableSizeInsn { |
| /** |
| * {@code non-null;} address representing the instruction that uses this |
| * instance |
| */ |
| private final CodeAddress user; |
| |
| /** {@code non-null;} sorted list of switch cases (keys) */ |
| private final IntList cases; |
| |
| /** |
| * {@code non-null;} corresponding list of code addresses; the branch |
| * target for each case |
| */ |
| private final CodeAddress[] targets; |
| |
| /** whether the output table will be packed (vs. sparse) */ |
| private final boolean packed; |
| |
| /** |
| * Constructs an instance. The output address of this instance is initially |
| * unknown ({@code -1}). |
| * |
| * @param position {@code non-null;} source position |
| * @param user {@code non-null;} address representing the instruction that |
| * uses this instance |
| * @param cases {@code non-null;} sorted list of switch cases (keys) |
| * @param targets {@code non-null;} corresponding list of code addresses; the |
| * branch target for each case |
| */ |
| public SwitchData(SourcePosition position, CodeAddress user, |
| IntList cases, CodeAddress[] targets) { |
| super(position, RegisterSpecList.EMPTY); |
| |
| if (user == null) { |
| throw new NullPointerException("user == null"); |
| } |
| |
| if (cases == null) { |
| throw new NullPointerException("cases == null"); |
| } |
| |
| if (targets == null) { |
| throw new NullPointerException("targets == null"); |
| } |
| |
| int sz = cases.size(); |
| |
| if (sz != targets.length) { |
| throw new IllegalArgumentException("cases / targets mismatch"); |
| } |
| |
| if (sz > 65535) { |
| throw new IllegalArgumentException("too many cases"); |
| } |
| |
| this.user = user; |
| this.cases = cases; |
| this.targets = targets; |
| this.packed = shouldPack(cases); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public int codeSize() { |
| return packed ? (int) packedCodeSize(cases) : |
| (int) sparseCodeSize(cases); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void writeTo(AnnotatedOutput out) { |
| int baseAddress = user.getAddress(); |
| int defaultTarget = Dops.PACKED_SWITCH.getFormat().codeSize(); |
| int sz = targets.length; |
| |
| if (packed) { |
| int firstCase = (sz == 0) ? 0 : cases.get(0); |
| int lastCase = (sz == 0) ? 0 : cases.get(sz - 1); |
| int outSz = lastCase - firstCase + 1; |
| |
| out.writeShort(Opcodes.PACKED_SWITCH_PAYLOAD); |
| out.writeShort(outSz); |
| out.writeInt(firstCase); |
| |
| int caseAt = 0; |
| for (int i = 0; i < outSz; i++) { |
| int outCase = firstCase + i; |
| int oneCase = cases.get(caseAt); |
| int relTarget; |
| |
| if (oneCase > outCase) { |
| relTarget = defaultTarget; |
| } else { |
| relTarget = targets[caseAt].getAddress() - baseAddress; |
| caseAt++; |
| } |
| |
| out.writeInt(relTarget); |
| } |
| } else { |
| out.writeShort(Opcodes.SPARSE_SWITCH_PAYLOAD); |
| out.writeShort(sz); |
| |
| for (int i = 0; i < sz; i++) { |
| out.writeInt(cases.get(i)); |
| } |
| |
| for (int i = 0; i < sz; i++) { |
| int relTarget = targets[i].getAddress() - baseAddress; |
| out.writeInt(relTarget); |
| } |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public DalvInsn withRegisters(RegisterSpecList registers) { |
| return new SwitchData(getPosition(), user, cases, targets); |
| } |
| |
| /** |
| * Returns whether or not this instance's data will be output as packed. |
| * |
| * @return {@code true} iff the data is to be packed |
| */ |
| public boolean isPacked() { |
| return packed; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected String argString() { |
| StringBuffer sb = new StringBuffer(100); |
| |
| int sz = targets.length; |
| for (int i = 0; i < sz; i++) { |
| sb.append("\n "); |
| sb.append(cases.get(i)); |
| sb.append(": "); |
| sb.append(targets[i]); |
| } |
| |
| return sb.toString(); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| protected String listingString0(boolean noteIndices) { |
| int baseAddress = user.getAddress(); |
| StringBuffer sb = new StringBuffer(100); |
| int sz = targets.length; |
| |
| sb.append(packed ? "packed" : "sparse"); |
| sb.append("-switch-payload // for switch @ "); |
| sb.append(Hex.u2(baseAddress)); |
| |
| for (int i = 0; i < sz; i++) { |
| int absTarget = targets[i].getAddress(); |
| int relTarget = absTarget - baseAddress; |
| sb.append("\n "); |
| sb.append(cases.get(i)); |
| sb.append(": "); |
| sb.append(Hex.u4(absTarget)); |
| sb.append(" // "); |
| sb.append(Hex.s4(relTarget)); |
| } |
| |
| return sb.toString(); |
| } |
| |
| /** |
| * Gets the size of a packed table for the given cases, in 16-bit code |
| * units. |
| * |
| * @param cases {@code non-null;} sorted list of cases |
| * @return {@code >= -1;} the packed table size or {@code -1} if the |
| * cases couldn't possibly be represented as a packed table |
| */ |
| private static long packedCodeSize(IntList cases) { |
| int sz = cases.size(); |
| long low = cases.get(0); |
| long high = cases.get(sz - 1); |
| long result = ((high - low + 1)) * 2 + 4; |
| |
| return (result <= 0x7fffffff) ? result : -1; |
| } |
| |
| /** |
| * Gets the size of a sparse table for the given cases, in 16-bit code |
| * units. |
| * |
| * @param cases {@code non-null;} sorted list of cases |
| * @return {@code > 0;} the sparse table size |
| */ |
| private static long sparseCodeSize(IntList cases) { |
| int sz = cases.size(); |
| |
| return (sz * 4L) + 2; |
| } |
| |
| /** |
| * Determines whether the given list of cases warrant being packed. |
| * |
| * @param cases {@code non-null;} sorted list of cases |
| * @return {@code true} iff the table encoding the cases |
| * should be packed |
| */ |
| private static boolean shouldPack(IntList cases) { |
| int sz = cases.size(); |
| |
| if (sz < 2) { |
| return true; |
| } |
| |
| long packedSize = packedCodeSize(cases); |
| long sparseSize = sparseCodeSize(cases); |
| |
| /* |
| * We pick the packed representation if it is possible and |
| * would be as small or smaller than 5/4 of the sparse |
| * representation. That is, we accept some size overhead on |
| * the packed representation, since that format is faster to |
| * execute at runtime. |
| */ |
| return (packedSize >= 0) && (packedSize <= ((sparseSize * 5) / 4)); |
| } |
| } |