1 /*++
2 Copyright (c) 2006 Microsoft Corporation
3 
4 Module Name:
5 
6     tst_bitvector.cpp
7 
8 Abstract:
9 
10     Test bitvector module
11 
12 Author:
13 
14     Leonardo de Moura (leonardo) 2006-10-03.
15 
16 Revision History:
17 
18 --*/
19 #include<cstdlib>
20 #include<iostream>
21 #include "util/bit_vector.h"
22 #include "util/vector.h"
23 
tst1()24 static void tst1() {
25     bit_vector     v1;
26     bool_vector v2;
27     unsigned n = rand()%10000;
28     for (unsigned i = 0; i < n; i++) {
29         int op = rand()%6;
30     if (op <= 1) {
31         bool val = (rand()%2) != 0;
32         v1.push_back(val);
33         v2.push_back(val);
34         ENSURE(v1.size() == v2.size());
35     }
36     else if (op <= 3) {
37         ENSURE(v1.size() == v2.size());
38         if (!v1.empty()) {
39         bool val = (rand()%2) != 0;
40         unsigned idx = rand()%v1.size();
41         ENSURE(v1.get(idx) == v2[idx]);
42         v1.set(idx, val);
43         v2[idx] = val;
44         ENSURE(v1.get(idx) == v2[idx]);
45         }
46     }
47     else if (op <= 4) {
48         ENSURE(v1.size() == v2.size());
49         if (!v1.empty()) {
50         unsigned idx = rand()%v1.size();
51         VERIFY(v1.get(idx) == v2[idx]);
52         }
53     }
54     else if (op <= 5) {
55         ENSURE(v1.size() == v2.size());
56         for (unsigned j = 0; j < v1.size(); j++) {
57         ENSURE(v1.get(j) == v2[j]);
58         }
59     }
60     }
61 }
62 
tst2()63 static void tst2() {
64     bit_vector b;
65     b.push_back(true);
66     b.push_back(false);
67     b.push_back(true);
68     b.resize(30);
69     ENSURE(b.get(0) == true);
70     ENSURE(b.get(1) == false);
71     ENSURE(b.get(2) == true);
72     ENSURE(b.get(3) == false);
73     ENSURE(b.get(29) == false);
74 }
75 
tst_shift()76 static void tst_shift() {
77     bit_vector b;
78     b.resize(111);
79     b.set(105);
80     b.set(99);
81     b.set(98);
82     b.set(90);
83     b.set(80);
84     b.set(75);
85     b.set(33);
86     b.set(32);
87     b.set(31);
88     b.set(30);
89     b.set(10);
90     std::cout << "b: " << b << "\n";
91     b.shift_right(16);
92     std::cout << "b: " << b << "\n";
93     b.shift_right(1);
94     std::cout << "b: " << b << "\n";
95     b.shift_right(32);
96     std::cout << "b: " << b << "\n";
97     b.shift_right(42);
98     std::cout << "b: " << b << "\n";
99     b.shift_right(16);
100     std::cout << "b: " << b << "\n";
101     b.shift_right(63);
102     std::cout << "b: " << b << "\n";
103 }
104 
tst_or()105 static void tst_or() {
106     {
107         bit_vector b1;
108         bit_vector b2;
109         b1.resize(5);
110         b2.resize(10);
111         b1.set(4);
112         b2.set(8);
113         b2.set(3);
114         b2.set(2);
115         b2.set(1);
116         std::cout << b1 << "\n";
117         std::cout << b2 << "\n";
118         b1 |= b2;
119         ENSURE(b1.size() == 10);
120         std::cout << b1 << "\n";
121         ENSURE(b1 != b2);
122         ENSURE(b1 != b2);
123         b1.unset(4);
124         ENSURE(b1 == b2);
125         b1.unset(3);
126         ENSURE(b1 != b2);
127     }
128     {
129         bit_vector b1;
130         bit_vector b2;
131         b1.resize(2);
132         b2.resize(5);
133         b1.set(0);
134         b2.set(4);
135         b1 |= b2;
136         ENSURE(b1 != b2);
137         b2.set(0);
138         ENSURE(b1 == b2);
139         std::cout << "-----\n";
140         std::cout << b1 << "\n";
141     }
142     {
143         bit_vector b1;
144         bit_vector b2;
145         b1.resize(10);
146         b2.resize(10);
147         b1.set(5);
148         b2.set(8);
149         b2.set(3);
150         b2.resize(5);
151         b1 |= b2;
152         ENSURE(!b1.get(8));
153         ENSURE(b1.get(5));
154         ENSURE(b1.get(3));
155     }
156     {
157         bit_vector b1;
158         bit_vector b2;
159         b1.resize(123);
160         b2.resize(126);
161         b2.set(124);
162         b1.set(122);
163         b1.set(100);
164         b2.set(100);
165         b1.set(80);
166         b2.set(80);
167         b1.set(4);
168         b2.set(4);
169         ENSURE(b1!=b2);
170         b2.resize(123);
171         ENSURE(b1!=b2);
172         b1.resize(120);
173         b2.resize(120);
174         ENSURE(b1==b2);
175         b1.unset(80);
176         b1.unset(100);
177         ENSURE(b1!=b2);
178         b1 |= b2;
179         ENSURE(b1 == b2);
180     }
181     {
182         bit_vector b1;
183         bit_vector b2;
184         b1.resize(5);
185         b2.resize(10);
186         b2.set(8);
187         b1.set(4);
188         b2.set(1);
189         b1.set(0);
190         b1 |= b2;
191         ENSURE(b1.size() == 10);
192         ENSURE(b1.get(8) && b1.get(4) && b1.get(1) && b1.get(0) && !b1.get(9));
193     }
194     {
195         bit_vector b1;
196         bit_vector b2;
197         b1.resize(32);
198         b2.resize(32);
199         b1.set(1);
200         b1.set(5);
201         b2.set(8);
202         b2.set(0);
203         b1 |= b2;
204         ENSURE(b1.get(1) && b1.get(5) && b1.get(8) && b1.get(0) && !b1.get(11));
205         std::cout << "b1(size32): " << b1 << "\n";
206     }
207 }
208 
tst_and()209 static void tst_and() {
210     {
211         bit_vector b1;
212         bit_vector b2;
213         b1.resize(5);
214         b2.resize(3);
215         b2.set(2);
216         b1.set(2);
217         b1.set(4);
218         std::cout << "------\nb1: " << b1 << "\n";
219         b1 &= b2;
220         std::cout << "------\nb1: " << b1 << "\n";
221         ENSURE(!b1.get(4));
222         ENSURE(b1.get(2));
223     }
224     {
225         bit_vector b1;
226         bit_vector b2;
227         b1.resize(241);
228         b2.resize(128);
229         b1.set(240);
230         b1.set(232);
231         b1.set(127);
232         b1.set(128);
233         b1.set(8);
234         b2.set(127);
235         b2.set(5);
236         b1 &= b2;
237         ENSURE(!b1.get(240) && !b1.get(232) && !b1.get(128) && b1.get(127) && !b1.get(8) && !b1.get(5));
238     }
239 }
240 
tst_crash()241 static void tst_crash() {
242     {
243         bit_vector b;
244         b.push_back(true);
245         b.resize(64);
246         ENSURE(!b.get(63));
247         ENSURE(b.get(0));
248         ENSURE(!b.get(1));
249     }
250     {
251         bit_vector b;
252         b.push_back(false);
253         b.resize(64, true);
254         ENSURE(b.get(63));
255         ENSURE(!b.get(0));
256         ENSURE(b.get(1));
257     }
258 }
259 
tst_bv_reset()260 static void tst_bv_reset() {
261     bit_vector b;
262     bool bit = true;
263     for (unsigned sz = 1; sz < 84; ++sz) {
264         b.reset();
265         b.resize(sz, bit);
266         for (unsigned i = 0; i < sz; ++i) {
267             ENSURE(bit == b.get(i));
268         }
269         for (unsigned sz2 = sz; sz2 < sz+10; ++sz2) {
270             b.resize(sz2, !bit);
271             for (unsigned i = sz; i < sz2; ++i) {
272                 ENSURE(bit != b.get(i));
273             }
274         }
275         bit = !bit;
276     }
277 }
278 
tst_eq()279 static void tst_eq() {
280     bit_vector b1, b2, b3;
281     b1.resize(32);
282     b2.resize(32);
283     b3.resize(32);
284 
285     b1.set(3, true);
286     ENSURE(b1 != b2);
287     ENSURE(!(b1 == b2));
288     ENSURE(b2 == b3);
289 
290     b3.set(3, true);
291     ENSURE(b1 == b3);
292     ENSURE(!(b1 != b3));
293 
294     b2.set(31, true);
295     b3.set(31);
296     b3.unset(3);
297     ENSURE(b2 == b3);
298     ENSURE(!(b2 != b3));
299 }
300 
tst_bit_vector()301 void tst_bit_vector() {
302     tst_crash();
303     tst_shift();
304     tst_or();
305     tst_and();
306     tst_bv_reset();
307     tst_eq();
308     return;
309     tst2();
310     for (unsigned i = 0; i < 20; i++) {
311         std::cerr << i << std::endl;
312     tst1();
313     }
314 }
315