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.dexgen.dex.code;
18
19import com.android.dexgen.rop.code.RegisterSpecList;
20import com.android.dexgen.rop.code.SourcePosition;
21import com.android.dexgen.util.AnnotatedOutput;
22import com.android.dexgen.util.Hex;
23import com.android.dexgen.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