1/* 2 * Copyright (C) 2007 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.dex.code; 18 19import com.android.dx.rop.code.RegisterSpecList; 20import com.android.dx.rop.code.SourcePosition; 21import com.android.dx.util.AnnotatedOutput; 22import com.android.dx.util.Hex; 23import com.android.dx.util.IntList; 24 25/** 26 * Pseudo-instruction which holds switch data. The switch data is 27 * a map of values to target addresses, and this class writes the data 28 * in either a "packed" or "sparse" form. 29 */ 30public final class SwitchData extends VariableSizeInsn { 31 /** 32 * {@code non-null;} address representing the instruction that uses this 33 * instance 34 */ 35 private final CodeAddress user; 36 37 /** {@code non-null;} sorted list of switch cases (keys) */ 38 private final IntList cases; 39 40 /** 41 * {@code non-null;} corresponding list of code addresses; the branch 42 * target for each case 43 */ 44 private final CodeAddress[] targets; 45 46 /** whether the output table will be packed (vs. sparse) */ 47 private final boolean packed; 48 49 /** 50 * Constructs an instance. The output address of this instance is initially 51 * unknown ({@code -1}). 52 * 53 * @param position {@code non-null;} source position 54 * @param user {@code non-null;} address representing the instruction that 55 * uses this instance 56 * @param cases {@code non-null;} sorted list of switch cases (keys) 57 * @param targets {@code non-null;} corresponding list of code addresses; the 58 * branch target for each case 59 */ 60 public SwitchData(SourcePosition position, CodeAddress user, 61 IntList cases, CodeAddress[] targets) { 62 super(position, RegisterSpecList.EMPTY); 63 64 if (user == null) { 65 throw new NullPointerException("user == null"); 66 } 67 68 if (cases == null) { 69 throw new NullPointerException("cases == null"); 70 } 71 72 if (targets == null) { 73 throw new NullPointerException("targets == null"); 74 } 75 76 int sz = cases.size(); 77 78 if (sz != targets.length) { 79 throw new IllegalArgumentException("cases / targets mismatch"); 80 } 81 82 if (sz > 65535) { 83 throw new IllegalArgumentException("too many cases"); 84 } 85 86 this.user = user; 87 this.cases = cases; 88 this.targets = targets; 89 this.packed = shouldPack(cases); 90 } 91 92 /** {@inheritDoc} */ 93 @Override 94 public int codeSize() { 95 return packed ? (int) packedCodeSize(cases) : 96 (int) sparseCodeSize(cases); 97 } 98 99 /** {@inheritDoc} */ 100 @Override 101 public void writeTo(AnnotatedOutput out) { 102 int baseAddress = user.getAddress(); 103 int defaultTarget = Dops.PACKED_SWITCH.getFormat().codeSize(); 104 int sz = targets.length; 105 106 if (packed) { 107 int firstCase = (sz == 0) ? 0 : cases.get(0); 108 int lastCase = (sz == 0) ? 0 : cases.get(sz - 1); 109 int outSz = lastCase - firstCase + 1; 110 111 out.writeShort(0x100 | DalvOps.NOP); 112 out.writeShort(outSz); 113 out.writeInt(firstCase); 114 115 int caseAt = 0; 116 for (int i = 0; i < outSz; i++) { 117 int outCase = firstCase + i; 118 int oneCase = cases.get(caseAt); 119 int relTarget; 120 121 if (oneCase > outCase) { 122 relTarget = defaultTarget; 123 } else { 124 relTarget = targets[caseAt].getAddress() - baseAddress; 125 caseAt++; 126 } 127 128 out.writeInt(relTarget); 129 } 130 } else { 131 out.writeShort(0x200 | DalvOps.NOP); 132 out.writeShort(sz); 133 134 for (int i = 0; i < sz; i++) { 135 out.writeInt(cases.get(i)); 136 } 137 138 for (int i = 0; i < sz; i++) { 139 int relTarget = targets[i].getAddress() - baseAddress; 140 out.writeInt(relTarget); 141 } 142 } 143 } 144 145 /** {@inheritDoc} */ 146 @Override 147 public DalvInsn withRegisters(RegisterSpecList registers) { 148 return new SwitchData(getPosition(), user, cases, targets); 149 } 150 151 /** 152 * Returns whether or not this instance's data will be output as packed. 153 * 154 * @return {@code true} iff the data is to be packed 155 */ 156 public boolean isPacked() { 157 return packed; 158 } 159 160 /** {@inheritDoc} */ 161 @Override 162 protected String argString() { 163 StringBuffer sb = new StringBuffer(100); 164 165 int sz = targets.length; 166 for (int i = 0; i < sz; i++) { 167 sb.append("\n "); 168 sb.append(cases.get(i)); 169 sb.append(": "); 170 sb.append(targets[i]); 171 } 172 173 return sb.toString(); 174 } 175 176 /** {@inheritDoc} */ 177 @Override 178 protected String listingString0(boolean noteIndices) { 179 int baseAddress = user.getAddress(); 180 StringBuffer sb = new StringBuffer(100); 181 int sz = targets.length; 182 183 sb.append(packed ? "packed" : "sparse"); 184 sb.append("-switch-data // for switch @ "); 185 sb.append(Hex.u2(baseAddress)); 186 187 for (int i = 0; i < sz; i++) { 188 int absTarget = targets[i].getAddress(); 189 int relTarget = absTarget - baseAddress; 190 sb.append("\n "); 191 sb.append(cases.get(i)); 192 sb.append(": "); 193 sb.append(Hex.u4(absTarget)); 194 sb.append(" // "); 195 sb.append(Hex.s4(relTarget)); 196 } 197 198 return sb.toString(); 199 } 200 201 /** 202 * Gets the size of a packed table for the given cases, in 16-bit code 203 * units. 204 * 205 * @param cases {@code non-null;} sorted list of cases 206 * @return {@code >= -1;} the packed table size or {@code -1} if the 207 * cases couldn't possibly be represented as a packed table 208 */ 209 private static long packedCodeSize(IntList cases) { 210 int sz = cases.size(); 211 long low = cases.get(0); 212 long high = cases.get(sz - 1); 213 long result = ((high - low + 1)) * 2 + 4; 214 215 return (result <= 0x7fffffff) ? result : -1; 216 } 217 218 /** 219 * Gets the size of a sparse table for the given cases, in 16-bit code 220 * units. 221 * 222 * @param cases {@code non-null;} sorted list of cases 223 * @return {@code > 0;} the sparse table size 224 */ 225 private static long sparseCodeSize(IntList cases) { 226 int sz = cases.size(); 227 228 return (sz * 4L) + 2; 229 } 230 231 /** 232 * Determines whether the given list of cases warrant being packed. 233 * 234 * @param cases {@code non-null;} sorted list of cases 235 * @return {@code true} iff the table encoding the cases 236 * should be packed 237 */ 238 private static boolean shouldPack(IntList cases) { 239 int sz = cases.size(); 240 241 if (sz < 2) { 242 return true; 243 } 244 245 long packedSize = packedCodeSize(cases); 246 long sparseSize = sparseCodeSize(cases); 247 248 /* 249 * We pick the packed representation if it is possible and 250 * would be as small or smaller than 5/4 of the sparse 251 * representation. That is, we accept some size overhead on 252 * the packed representation, since that format is faster to 253 * execute at runtime. 254 */ 255 return (packedSize >= 0) && (packedSize <= ((sparseSize * 5) / 4)); 256 } 257} 258