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.util;
18
19/**
20 * Utilities for treating {@code int[]}s as bit sets.
21 */
22public final class Bits {
23    /**
24     * This class is uninstantiable.
25     */
26    private Bits() {
27        // This space intentionally left blank.
28    }
29
30    /**
31     * Constructs a bit set to contain bits up to the given index (exclusive).
32     *
33     * @param max {@code >= 0;} the maximum bit index (exclusive)
34     * @return {@code non-null;} an appropriately-constructed instance
35     */
36    public static int[] makeBitSet(int max) {
37        int size = (max + 0x1f) >> 5;
38        return new int[size];
39    }
40
41    /**
42     * Gets the maximum index (exclusive) for the given bit set.
43     *
44     * @param bits {@code non-null;} bit set in question
45     * @return {@code >= 0;} the maximum index (exclusive) that may be set
46     */
47    public static int getMax(int[] bits) {
48        return bits.length * 0x20;
49    }
50
51    /**
52     * Gets the value of the bit at the given index.
53     *
54     * @param bits {@code non-null;} bit set to operate on
55     * @param idx {@code >= 0, < getMax(set);} which bit
56     * @return the value of the indicated bit
57     */
58    public static boolean get(int[] bits, int idx) {
59        int arrayIdx = idx >> 5;
60        int bit = 1 << (idx & 0x1f);
61        return (bits[arrayIdx] & bit) != 0;
62    }
63
64    /**
65     * Sets the given bit to the given value.
66     *
67     * @param bits {@code non-null;} bit set to operate on
68     * @param idx {@code >= 0, < getMax(set);} which bit
69     * @param value the new value for the bit
70     */
71    public static void set(int[] bits, int idx, boolean value) {
72        int arrayIdx = idx >> 5;
73        int bit = 1 << (idx & 0x1f);
74
75        if (value) {
76            bits[arrayIdx] |= bit;
77        } else {
78            bits[arrayIdx] &= ~bit;
79        }
80    }
81
82    /**
83     * Sets the given bit to {@code true}.
84     *
85     * @param bits {@code non-null;} bit set to operate on
86     * @param idx {@code >= 0, < getMax(set);} which bit
87     */
88    public static void set(int[] bits, int idx) {
89        int arrayIdx = idx >> 5;
90        int bit = 1 << (idx & 0x1f);
91        bits[arrayIdx] |= bit;
92    }
93
94    /**
95     * Sets the given bit to {@code false}.
96     *
97     * @param bits {@code non-null;} bit set to operate on
98     * @param idx {@code >= 0, < getMax(set);} which bit
99     */
100    public static void clear(int[] bits, int idx) {
101        int arrayIdx = idx >> 5;
102        int bit = 1 << (idx & 0x1f);
103        bits[arrayIdx] &= ~bit;
104    }
105
106    /**
107     * Returns whether or not the given bit set is empty, that is, whether
108     * no bit is set to {@code true}.
109     *
110     * @param bits {@code non-null;} bit set to operate on
111     * @return {@code true} iff all bits are {@code false}
112     */
113    public static boolean isEmpty(int[] bits) {
114        int len = bits.length;
115
116        for (int i = 0; i < len; i++) {
117            if (bits[i] != 0) {
118                return false;
119            }
120        }
121
122        return true;
123    }
124
125    /**
126     * Gets the number of bits set to {@code true} in the given bit set.
127     *
128     * @param bits {@code non-null;} bit set to operate on
129     * @return {@code >= 0;} the bit count (aka population count) of the set
130     */
131    public static int bitCount(int[] bits) {
132        int len = bits.length;
133        int count = 0;
134
135        for (int i = 0; i < len; i++) {
136            count += Integer.bitCount(bits[i]);
137        }
138
139        return count;
140    }
141
142    /**
143     * Returns whether any bits are set to {@code true} in the
144     * specified range.
145     *
146     * @param bits {@code non-null;} bit set to operate on
147     * @param start {@code >= 0;} index of the first bit in the range (inclusive)
148     * @param end {@code >= 0;} index of the last bit in the range (exclusive)
149     * @return {@code true} if any bit is set to {@code true} in
150     * the indicated range
151     */
152    public static boolean anyInRange(int[] bits, int start, int end) {
153        int idx = findFirst(bits, start);
154        return (idx >= 0) && (idx < end);
155    }
156
157    /**
158     * Finds the lowest-order bit set at or after the given index in the
159     * given bit set.
160     *
161     * @param bits {@code non-null;} bit set to operate on
162     * @param idx {@code >= 0;} minimum index to return
163     * @return {@code >= -1;} lowest-order bit set at or after {@code idx},
164     * or {@code -1} if there is no appropriate bit index to return
165     */
166    public static int findFirst(int[] bits, int idx) {
167        int len = bits.length;
168        int minBit = idx & 0x1f;
169
170        for (int arrayIdx = idx >> 5; arrayIdx < len; arrayIdx++) {
171            int word = bits[arrayIdx];
172            if (word != 0) {
173                int bitIdx = findFirst(word, minBit);
174                if (bitIdx >= 0) {
175                    return (arrayIdx << 5) + bitIdx;
176                }
177            }
178            minBit = 0;
179        }
180
181        return -1;
182    }
183
184    /**
185     * Finds the lowest-order bit set at or after the given index in the
186     * given {@code int}.
187     *
188     * @param value the value in question
189     * @param idx 0..31 the minimum bit index to return
190     * @return {@code >= -1;} lowest-order bit set at or after {@code idx},
191     * or {@code -1} if there is no appropriate bit index to return
192     */
193    public static int findFirst(int value, int idx) {
194        value &= ~((1 << idx) - 1); // Mask off too-low bits.
195        int result = Integer.numberOfTrailingZeros(value);
196        return (result == 32) ? -1 : result;
197    }
198
199    /**
200     * Ors bit array {@code b} into bit array {@code a}.
201     * {@code a.length} must be greater than or equal to
202     * {@code b.length}.
203     *
204     * @param a {@code non-null;} int array to be ored with other argument. This
205     * argument is modified.
206     * @param b {@code non-null;} int array to be ored into {@code a}. This
207     * argument is not modified.
208     */
209    public static void or(int[] a, int[] b) {
210        for (int i = 0; i < b.length; i++) {
211            a[i] |= b[i];
212        }
213    }
214
215    public static String toHuman(int[] bits) {
216        StringBuilder sb = new StringBuilder();
217
218        boolean needsComma = false;
219
220        sb.append('{');
221
222        int bitsLength = 32 * bits.length;
223        for (int i = 0; i < bitsLength; i++) {
224            if (Bits.get(bits, i)) {
225                if (needsComma) {
226                    sb.append(',');
227                }
228                needsComma = true;
229                sb.append(i);
230            }
231        }
232        sb.append('}');
233
234        return sb.toString();
235    }
236}
237