/*
* 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));
}
}
|
