1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.dex.code; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.io.Opcodes; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegisterSpecList; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.SourcePosition; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.AnnotatedOutput; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Hex; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Pseudo-instruction which holds switch data. The switch data is 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * a map of values to target addresses, and this class writes the data 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * in either a "packed" or "sparse" form. 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class SwitchData extends VariableSizeInsn { 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code non-null;} address representing the instruction that uses this 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * instance 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final CodeAddress user; 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} sorted list of switch cases (keys) */ 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final IntList cases; 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code non-null;} corresponding list of code addresses; the branch 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * target for each case 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final CodeAddress[] targets; 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** whether the output table will be packed (vs. sparse) */ 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final boolean packed; 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. The output address of this instance is initially 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * unknown ({@code -1}). 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param position {@code non-null;} source position 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param user {@code non-null;} address representing the instruction that 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * uses this instance 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cases {@code non-null;} sorted list of switch cases (keys) 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param targets {@code non-null;} corresponding list of code addresses; the 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * branch target for each case 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SwitchData(SourcePosition position, CodeAddress user, 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList cases, CodeAddress[] targets) { 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson super(position, RegisterSpecList.EMPTY); 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (user == null) { 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("user == null"); 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (cases == null) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("cases == null"); 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (targets == null) { 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("targets == null"); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = cases.size(); 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sz != targets.length) { 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("cases / targets mismatch"); 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sz > 65535) { 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("too many cases"); 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.user = user; 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.cases = cases; 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.targets = targets; 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.packed = shouldPack(cases); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int codeSize() { 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return packed ? (int) packedCodeSize(cases) : 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson (int) sparseCodeSize(cases); 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void writeTo(AnnotatedOutput out) { 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int baseAddress = user.getAddress(); 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int defaultTarget = Dops.PACKED_SWITCH.getFormat().codeSize(); 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = targets.length; 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (packed) { 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int firstCase = (sz == 0) ? 0 : cases.get(0); 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int lastCase = (sz == 0) ? 0 : cases.get(sz - 1); 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int outSz = lastCase - firstCase + 1; 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeShort(Opcodes.PACKED_SWITCH_PAYLOAD); 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeShort(outSz); 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeInt(firstCase); 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int caseAt = 0; 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < outSz; i++) { 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int outCase = firstCase + i; 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int oneCase = cases.get(caseAt); 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int relTarget; 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (oneCase > outCase) { 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson relTarget = defaultTarget; 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson relTarget = targets[caseAt].getAddress() - baseAddress; 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson caseAt++; 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeInt(relTarget); 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeShort(Opcodes.SPARSE_SWITCH_PAYLOAD); 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeShort(sz); 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeInt(cases.get(i)); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int relTarget = targets[i].getAddress() - baseAddress; 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeInt(relTarget); 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public DalvInsn withRegisters(RegisterSpecList registers) { 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return new SwitchData(getPosition(), user, cases, targets); 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns whether or not this instance's data will be output as packed. 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} iff the data is to be packed 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean isPacked() { 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return packed; 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected String argString() { 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuffer sb = new StringBuffer(100); 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = targets.length; 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append("\n "); 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(cases.get(i)); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(": "); 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(targets[i]); 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return sb.toString(); 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson protected String listingString0(boolean noteIndices) { 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int baseAddress = user.getAddress(); 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuffer sb = new StringBuffer(100); 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = targets.length; 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(packed ? "packed" : "sparse"); 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append("-switch-payload // for switch @ "); 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(Hex.u2(baseAddress)); 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int absTarget = targets[i].getAddress(); 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int relTarget = absTarget - baseAddress; 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append("\n "); 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(cases.get(i)); 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(": "); 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(Hex.u4(absTarget)); 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(" // "); 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(Hex.s4(relTarget)); 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return sb.toString(); 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the size of a packed table for the given cases, in 16-bit code 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * units. 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cases {@code non-null;} sorted list of cases 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code >= -1;} the packed table size or {@code -1} if the 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * cases couldn't possibly be represented as a packed table 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static long packedCodeSize(IntList cases) { 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = cases.size(); 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson long low = cases.get(0); 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson long high = cases.get(sz - 1); 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson long result = ((high - low + 1)) * 2 + 4; 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (result <= 0x7fffffff) ? result : -1; 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the size of a sparse table for the given cases, in 16-bit code 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * units. 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cases {@code non-null;} sorted list of cases 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code > 0;} the sparse table size 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static long sparseCodeSize(IntList cases) { 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = cases.size(); 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (sz * 4L) + 2; 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Determines whether the given list of cases warrant being packed. 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param cases {@code non-null;} sorted list of cases 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} iff the table encoding the cases 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * should be packed 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean shouldPack(IntList cases) { 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = cases.size(); 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sz < 2) { 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson long packedSize = packedCodeSize(cases); 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson long sparseSize = sparseCodeSize(cases); 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We pick the packed representation if it is possible and 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * would be as small or smaller than 5/4 of the sparse 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * representation. That is, we accept some size overhead on 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the packed representation, since that format is faster to 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * execute at runtime. 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (packedSize >= 0) && (packedSize <= ((sparseSize * 5) / 4)); 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 259