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