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.util;
18 
19 import junit.framework.TestCase;
20 
21 public final class BitsTest extends TestCase {
test_makeBitSet()22     public void test_makeBitSet() {
23         assertEquals(label(0), 0, Bits.makeBitSet(0).length);
24 
25         for (int i = 1; i <= 32; i++) {
26             assertEquals(label(i), 1, Bits.makeBitSet(i).length);
27         }
28 
29         for (int i = 33; i <= 64; i++) {
30             assertEquals(label(i), 2, Bits.makeBitSet(i).length);
31         }
32 
33         for (int i = 65; i < 4000; i += 101) {
34             int expect = i >> 5;
35             if ((expect * 32) < i) {
36                 expect++;
37             }
38             assertEquals(label(i), expect, Bits.makeBitSet(i).length);
39         }
40     }
41 
test_getMax()42     public void test_getMax() {
43         for (int i = 0; i < 4000; i += 59) {
44             int expect = i >> 5;
45             if ((expect * 32) < i) {
46                 expect++;
47             }
48             assertEquals(label(i), expect * 32,
49                          Bits.getMax(new int[expect]));
50         }
51     }
52 
test1_get()53     public void test1_get() {
54         int[] bits = Bits.makeBitSet(100);
55 
56         for (int i = 0; i < 100; i++) {
57             assertFalse(label(i), Bits.get(bits, i));
58         }
59     }
60 
test2_get()61     public void test2_get() {
62         int[] bits = Bits.makeBitSet(100);
63         for (int i = 0; i < bits.length; i++) {
64             bits[i] = -1;
65         }
66 
67         for (int i = 0; i < 100; i++) {
68             assertTrue(label(i), Bits.get(bits, i));
69         }
70     }
71 
test3_get()72     public void test3_get() {
73         int[] bits = Bits.makeBitSet(100);
74 
75         for (int i = 0; i < 100; i++) {
76             Bits.set(bits, i, (i % 5) == 0);
77         }
78 
79         for (int i = 0; i < 100; i++) {
80             boolean expect = (i % 5) == 0;
81             assertTrue(label(i), Bits.get(bits, i) == expect);
82         }
83     }
84 
test1_set1()85     public void test1_set1() {
86         int[] bits = Bits.makeBitSet(50);
87         bits[1] = -1;
88 
89         Bits.set(bits, 0, true);
90         Bits.set(bits, 3, true);
91         Bits.set(bits, 6, true);
92         Bits.set(bits, 3, false);
93         Bits.set(bits, 35, false);
94         Bits.set(bits, 38, false);
95         Bits.set(bits, 42, false);
96         Bits.set(bits, 38, true);
97 
98         assertEquals(label(1), 0x41, bits[0]);
99         assertEquals(label(2), 0xfffffbf7, bits[1]);
100     }
101 
test2_set1()102     public void test2_set1() {
103         int[] bits = Bits.makeBitSet(100);
104 
105         for (int i = 0; i < 100; i++) {
106             if ((i % 3) == 0) {
107                 Bits.set(bits, i, true);
108             }
109         }
110 
111         for (int i = 0; i < 100; i++) {
112             if ((i % 5) == 0) {
113                 Bits.set(bits, i, false);
114             }
115         }
116 
117         for (int i = 0; i < 100; i++) {
118             if ((i % 7) == 0) {
119                 Bits.set(bits, i, true);
120             }
121         }
122 
123         for (int i = 0; i < 100; i++) {
124             boolean expect = ((i % 7) == 0) ||
125                 (((i % 3) == 0) && ((i % 5) != 0));
126             assertTrue(label(i), Bits.get(bits, i) == expect);
127         }
128     }
129 
test_set2()130     public void test_set2() {
131         int[] bits = Bits.makeBitSet(100);
132 
133         for (int i = 0; i < 100; i++) {
134             if ((i % 11) == 0) {
135                 Bits.set(bits, i);
136             }
137         }
138 
139         for (int i = 0; i < 100; i++) {
140             boolean expect = (i % 11) == 0;
141             assertTrue(label(i), Bits.get(bits, i) == expect);
142         }
143     }
144 
test_clear()145     public void test_clear() {
146         int[] bits = Bits.makeBitSet(100);
147         for (int i = 0; i < bits.length; i++) {
148             bits[i] = -1;
149         }
150 
151         for (int i = 0; i < 100; i++) {
152             if ((i % 5) == 0) {
153                 Bits.clear(bits, i);
154             }
155         }
156 
157         for (int i = 0; i < 100; i++) {
158             boolean expect = (i % 5) != 0;
159             assertTrue(label(i), Bits.get(bits, i) == expect);
160         }
161     }
162 
test1_isEmpty()163     public void test1_isEmpty() {
164         for (int i = 0; i < 10; i++) {
165             assertTrue(label(i), Bits.isEmpty(new int[i]));
166         }
167     }
168 
test2_isEmpty()169     public void test2_isEmpty() {
170         for (int i = 1; i < 1000; i += 11) {
171             int[] bits = Bits.makeBitSet(i);
172             for (int j = i % 11; j >= 0; j--) {
173                 int x = i - 1 - (j * 13);
174                 if (x >= 0) {
175                     Bits.set(bits, x);
176                 }
177             }
178             assertFalse(label(i), Bits.isEmpty(bits));
179         }
180     }
181 
test1_bitCount()182     public void test1_bitCount() {
183         for (int i = 0; i < 10; i++) {
184             assertEquals(label(i), 0, Bits.bitCount(new int[i]));
185         }
186     }
187 
test2_bitCount()188     public void test2_bitCount() {
189         for (int i = 1; i < 1000; i += 13) {
190             int[] bits = Bits.makeBitSet(i);
191             int count = 0;
192             for (int j = 0; j < i; j += 20) {
193                 Bits.set(bits, j);
194                 count++;
195             }
196             for (int j = 7; j < i; j += 11) {
197                 if (!Bits.get(bits, j)) {
198                     Bits.set(bits, j);
199                     count++;
200                 }
201             }
202             for (int j = 3; j < i; j += 17) {
203                 if (!Bits.get(bits, j)) {
204                     Bits.set(bits, j);
205                     count++;
206                 }
207             }
208             assertEquals(label(i), count, Bits.bitCount(bits));
209         }
210     }
211 
test1_anyInRange()212     public void test1_anyInRange() {
213         int[] bits = new int[100];
214 
215         for (int i = 0; i < 100; i += 11) {
216             assertFalse(label(i), Bits.anyInRange(bits, 0, i));
217         }
218     }
219 
test2_anyInRange()220     public void test2_anyInRange() {
221         int[] bits = new int[100];
222 
223         for (int i = 0; i < 100; i += 11) {
224             assertFalse(label(i), Bits.anyInRange(bits, i, 100));
225         }
226     }
227 
test3_anyInRange()228     public void test3_anyInRange() {
229         int[] bits = new int[100];
230 
231         for (int i = 0; i < 50; i += 7) {
232             assertFalse(label(i), Bits.anyInRange(bits, i, 100 - i));
233         }
234     }
235 
test4_anyInRange()236     public void test4_anyInRange() {
237         int[] bits = new int[100];
238         for (int i = 0; i < bits.length; i++) {
239             bits[i] = -1;
240         }
241 
242         for (int i = 1; i < 100; i += 11) {
243             assertTrue(label(i), Bits.anyInRange(bits, 0, i));
244         }
245     }
246 
test5_anyInRange()247     public void test5_anyInRange() {
248         int[] bits = new int[100];
249         for (int i = 0; i < bits.length; i++) {
250             bits[i] = -1;
251         }
252 
253         for (int i = 1; i < 100; i += 11) {
254             assertTrue(label(i), Bits.anyInRange(bits, i, 100));
255         }
256     }
257 
test6_anyInRange()258     public void test6_anyInRange() {
259         int[] bits = new int[100];
260         for (int i = 0; i < bits.length; i++) {
261             bits[i] = -1;
262         }
263 
264         for (int i = 0; i < 50; i += 7) {
265             assertTrue(label(i), Bits.anyInRange(bits, i, 100 - i));
266         }
267     }
268 
test1_findFirst1()269     public void test1_findFirst1() {
270         int[] bits = new int[100];
271 
272         for (int i = 0; i < 100; i++) {
273             assertEquals(label(i), -1, Bits.findFirst(bits, i));
274         }
275     }
276 
test2_findFirst1()277     public void test2_findFirst1() {
278         int[] bits = new int[100];
279         for (int i = 0; i < bits.length; i++) {
280             bits[i] = -1;
281         }
282 
283         for (int i = 0; i < 100; i++) {
284             assertEquals(label(i), i, Bits.findFirst(bits, i));
285         }
286     }
287 
test3_findFirst1()288     public void test3_findFirst1() {
289         int[] bits = new int[100];
290 
291         for (int i = 25; i < 80; i++) {
292             for (int j = 0; j < bits.length; j++) {
293                 bits[j] = 0;
294             }
295 
296             Bits.set(bits, i - 5);
297             Bits.set(bits, i + 5);
298             Bits.set(bits, i + 10);
299             Bits.set(bits, i + 20);
300             assertEquals(label(i), i + 5, Bits.findFirst(bits, i));
301         }
302     }
303 
test1_findFirst2()304     public void test1_findFirst2() {
305         for (int i = 0; i < 32; i++) {
306             assertEquals(label(i), -1, Bits.findFirst(0, i));
307         }
308     }
309 
test2_findFirst2()310     public void test2_findFirst2() {
311         for (int i = 0; i < 32; i++) {
312             assertEquals(label(i), i, Bits.findFirst(-1, i));
313         }
314     }
315 
test3_findFirst2()316     public void test3_findFirst2() {
317         for (int i = 0; i < 32; i++) {
318             assertEquals(label(i), -1, Bits.findFirst((1 << i) >>> 1, i));
319         }
320     }
321 
test4_findFirst2()322     public void test4_findFirst2() {
323         for (int i = 0; i < 32; i++) {
324             assertEquals(label(i), i, Bits.findFirst(1 << i, i));
325         }
326     }
327 
test5_findFirst2()328     public void test5_findFirst2() {
329         for (int i = 0; i < 31; i++) {
330             assertEquals(label(i), i + 1, Bits.findFirst(1 << (i + 1), i));
331         }
332     }
333 
test6_findFirst2()334     public void test6_findFirst2() {
335         for (int i = 0; i < 32; i++) {
336             int value = (1 << i);
337             value |= (value >>> 1);
338             assertEquals(label(i), i, Bits.findFirst(value, i));
339         }
340     }
341 
label(int n)342     private static String label(int n) {
343         return "(" + n + ")";
344     }
345 }
346