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.io.Opcodes;
20import com.android.dx.rop.code.RegisterSpecList;
21import com.android.dx.rop.code.SourcePosition;
22import com.android.dx.util.AnnotatedOutput;
23import com.android.dx.util.Hex;
24import 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 */
31public 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     */
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
95    public int codeSize() {
96        return packed ? (int) packedCodeSize(cases) :
97            (int) sparseCodeSize(cases);
98    }
99
100    /** {@inheritDoc} */
101    @Override
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
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     */
157    public boolean isPacked() {
158        return packed;
159    }
160
161    /** {@inheritDoc} */
162    @Override
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
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     */
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     */
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     */
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