VirtualBox

source: vbox/trunk/src/VBox/Runtime/testcase/tstBitOperations.cpp@ 19711

Last change on this file since 19711 was 18569, checked in by vboxsync, 16 years ago

RTTest: sub tests, more typical reporting of those.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 15.3 KB
Line 
1/* $Id: tstBitOperations.cpp 18569 2009-03-31 13:07:20Z vboxsync $ */
2/** @file
3 * IPRT Testcase - Inlined Bit Operations.
4 */
5
6/*
7 * Copyright (C) 2006-2007 Sun Microsystems, Inc.
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 *
26 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27 * Clara, CA 95054 USA or visit http://www.sun.com if you need
28 * additional information or have any questions.
29 */
30
31
32/*******************************************************************************
33* Header Files *
34*******************************************************************************/
35#include <iprt/asm.h>
36#include <iprt/test.h>
37#include <iprt/stream.h>
38#include <iprt/string.h>
39#include <iprt/test.h>
40#include <iprt/initterm.h>
41
42
43/*
44 * Test 2 - ID allocation using a bitmap.
45 */
46
47#define NIL_TEST2_ID 0
48#define TEST2_ID_LAST ((RT_BIT_32(28) - 1) >> 8)
49
50struct TestMap2
51{
52 uint32_t idNil;
53 uint32_t idLast;
54 uint32_t idChunkPrev;
55 uint32_t bmChunkId[(TEST2_ID_LAST + 1 + 31) / 32];
56};
57
58static uint32_t test2AllocId(struct TestMap2 *p2)
59{
60 /*
61 * Scan sequentially from the last one + 1.
62 */
63 int32_t idChunk = ++p2->idChunkPrev;
64 if ( (uint32_t)idChunk < TEST2_ID_LAST
65 && idChunk > NIL_TEST2_ID)
66 {
67 idChunk = ASMBitNextClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1, idChunk);
68 if (idChunk > NIL_TEST2_ID)
69 {
70 if (ASMAtomicBitTestAndSet(&p2->bmChunkId[0], idChunk))
71 {
72 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
73 return NIL_TEST2_ID;
74 }
75 return p2->idChunkPrev = idChunk;
76 }
77 }
78
79 /*
80 * Ok, scan from the start.
81 */
82 idChunk = ASMBitFirstClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1);
83 if (idChunk <= NIL_TEST2_ID)
84 {
85 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
86 return NIL_TEST2_ID;
87 }
88 if (ASMAtomicBitTestAndSet(&p2->bmChunkId[0], idChunk))
89 {
90 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
91 return NIL_TEST2_ID;
92 }
93
94 return p2->idChunkPrev = idChunk;
95}
96
97
98static void test2(RTTEST hTest)
99{
100 struct TestMap2 *p2 = (struct TestMap2 *)RTTestGuardedAllocTail(hTest, sizeof(TestMap2));
101 p2->idNil = NIL_TEST2_ID;
102 p2->idLast = TEST2_ID_LAST;
103
104 /* Some simple tests first. */
105 RT_ZERO(p2->bmChunkId);
106 RTTEST_CHECK(hTest, ASMBitFirstSet(&p2->bmChunkId[0], TEST2_ID_LAST + 1) == -1);
107 for (uint32_t iBit = 0; iBit <= TEST2_ID_LAST; iBit++)
108 RTTEST_CHECK(hTest, !ASMBitTest(&p2->bmChunkId[0], iBit));
109
110 memset(&p2->bmChunkId[0], 0xff, sizeof(p2->bmChunkId));
111 RTTEST_CHECK(hTest, ASMBitFirstClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1) == -1);
112 for (uint32_t iBit = 0; iBit <= TEST2_ID_LAST; iBit++)
113 RTTEST_CHECK(hTest, ASMBitTest(&p2->bmChunkId[0], iBit));
114
115 /* The real test. */
116 p2->idChunkPrev = 0;
117 RT_ZERO(p2->bmChunkId);
118 ASMBitSet(p2->bmChunkId, NIL_TEST2_ID);
119 uint32_t cLeft = TEST2_ID_LAST;
120 while (cLeft-- > 0)
121 test2AllocId(p2);
122
123 RTTEST_CHECK(hTest, ASMBitFirstClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1) == -1);
124}
125
126
127int main()
128{
129 /*
130 * Init the runtime and stuff.
131 */
132 RTTEST hTest;
133 if ( RT_FAILURE(RTR3Init())
134 || RT_FAILURE(RTTestCreate("tstBitOperations", &hTest)))
135 {
136 RTPrintf("tstBitOperation: fatal initialization error\n");
137 return 1;
138 }
139 RTTestBanner(hTest);
140
141 int rcRet = 0;
142 int i;
143 int j;
144 int k;
145
146 /*
147 * Tests
148 */
149 struct TestMap
150 {
151 uint32_t au32[4];
152 };
153#if 0
154 struct TestMap sTest;
155 struct TestMap *p = &sTest;
156#else
157 struct TestMap *p = (struct TestMap *)RTTestGuardedAllocTail(hTest, sizeof(*p));
158#endif
159#define DUMP() RTTestPrintf(hTest, RTTESTLVL_INFO, "au32={%08x,%08x,%08x,%08x}", p->au32[0], p->au32[1], p->au32[2], p->au32[3])
160#define CHECK(expr) do { if (!(expr)) { RTTestFailed(hTest, "line %d: %s", __LINE__, #expr); DUMP(); } CHECK_GUARD(s); } while (0)
161#define CHECK_BIT(expr, b1) do { if (!(expr)) { RTTestFailed(hTest, "line %d, b1=%d: %s", __LINE__, b1, #expr); } CHECK_GUARD(s); } while (0)
162#define CHECK_BIT2(expr, b1, b2) do { if (!(expr)) { RTTestFailed(hTest, "line %d, b1=%d b2=%d: %s", __LINE__, b1, b2, #expr); } CHECK_GUARD(s); } while (0)
163#define CHECK_BIT3(expr, b1, b2, b3) do { if (!(expr)) { RTTestFailed(hTest, "line %d, b1=%d b2=%d b3=%d: %s", __LINE__, b1, b2, b3, #expr); } CHECK_GUARD(s); } while (0)
164
165#define GUARD_MAP(p) do { } while (0)
166#define CHECK_GUARD(p) do { } while (0)
167#define MAP_CLEAR(p) do { RT_ZERO(*(p)); GUARD_MAP(p); } while (0)
168#define MAP_SET(p) do { memset(p, 0xff, sizeof(*(p))); GUARD_MAP(p); } while (0)
169
170 /* self check. */
171 MAP_CLEAR(p);
172 CHECK_GUARD(p);
173
174 /* set */
175 MAP_CLEAR(p);
176 ASMBitSet(&p->au32[0], 0);
177 ASMBitSet(&p->au32[0], 31);
178 ASMBitSet(&p->au32[0], 65);
179 CHECK(p->au32[0] == 0x80000001U);
180 CHECK(p->au32[2] == 0x00000002U);
181 CHECK(ASMBitTestAndSet(&p->au32[0], 0) && p->au32[0] == 0x80000001U);
182 CHECK(!ASMBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x80010001U);
183 CHECK(ASMBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x80010001U);
184 CHECK(!ASMBitTestAndSet(&p->au32[0], 80) && p->au32[2] == 0x00010002U);
185
186 MAP_CLEAR(p);
187 ASMAtomicBitSet(&p->au32[0], 0);
188 ASMAtomicBitSet(&p->au32[0], 30);
189 ASMAtomicBitSet(&p->au32[0], 64);
190 CHECK(p->au32[0] == 0x40000001U);
191 CHECK(p->au32[2] == 0x00000001U);
192 CHECK(ASMAtomicBitTestAndSet(&p->au32[0], 0) && p->au32[0] == 0x40000001U);
193 CHECK(!ASMAtomicBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x40010001U);
194 CHECK(ASMAtomicBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x40010001U);
195 CHECK(!ASMAtomicBitTestAndSet(&p->au32[0], 80) && p->au32[2] == 0x00010001U);
196
197 /* clear */
198 MAP_SET(p);
199 ASMBitClear(&p->au32[0], 0);
200 ASMBitClear(&p->au32[0], 31);
201 ASMBitClear(&p->au32[0], 65);
202 CHECK(p->au32[0] == ~0x80000001U);
203 CHECK(p->au32[2] == ~0x00000002U);
204 CHECK(!ASMBitTestAndClear(&p->au32[0], 0) && p->au32[0] == ~0x80000001U);
205 CHECK(ASMBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
206 CHECK(!ASMBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
207 CHECK(ASMBitTestAndClear(&p->au32[0], 80) && p->au32[2] == ~0x00010002U);
208
209 MAP_SET(p);
210 ASMAtomicBitClear(&p->au32[0], 0);
211 ASMAtomicBitClear(&p->au32[0], 30);
212 ASMAtomicBitClear(&p->au32[0], 64);
213 CHECK(p->au32[0] == ~0x40000001U);
214 CHECK(p->au32[2] == ~0x00000001U);
215 CHECK(!ASMAtomicBitTestAndClear(&p->au32[0], 0) && p->au32[0] == ~0x40000001U);
216 CHECK(ASMAtomicBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
217 CHECK(!ASMAtomicBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
218 CHECK(ASMAtomicBitTestAndClear(&p->au32[0], 80) && p->au32[2] == ~0x00010001U);
219
220 /* toggle */
221 MAP_SET(p);
222 ASMBitToggle(&p->au32[0], 0);
223 ASMBitToggle(&p->au32[0], 31);
224 ASMBitToggle(&p->au32[0], 65);
225 ASMBitToggle(&p->au32[0], 47);
226 ASMBitToggle(&p->au32[0], 47);
227 CHECK(p->au32[0] == ~0x80000001U);
228 CHECK(p->au32[2] == ~0x00000002U);
229 CHECK(!ASMBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x80000000U);
230 CHECK(ASMBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x80000001U);
231 CHECK(ASMBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
232 CHECK(!ASMBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x80000001U);
233 CHECK(ASMBitTestAndToggle(&p->au32[0], 80) && p->au32[2] == ~0x00010002U);
234
235 MAP_SET(p);
236 ASMAtomicBitToggle(&p->au32[0], 0);
237 ASMAtomicBitToggle(&p->au32[0], 30);
238 ASMAtomicBitToggle(&p->au32[0], 64);
239 ASMAtomicBitToggle(&p->au32[0], 47);
240 ASMAtomicBitToggle(&p->au32[0], 47);
241 CHECK(p->au32[0] == ~0x40000001U);
242 CHECK(p->au32[2] == ~0x00000001U);
243 CHECK(!ASMAtomicBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x40000000U);
244 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x40000001U);
245 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
246 CHECK(!ASMAtomicBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x40000001U);
247 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 80) && p->au32[2] == ~0x00010001U);
248
249 /* test bit. */
250 for (i = 0; i < 128; i++)
251 {
252 MAP_SET(p);
253 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
254 ASMBitToggle(&p->au32[0], i);
255 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
256 CHECK_BIT(!ASMBitTestAndToggle(&p->au32[0], i), i);
257 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
258 CHECK_BIT(ASMBitTestAndToggle(&p->au32[0], i), i);
259 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
260
261 MAP_SET(p);
262 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
263 ASMAtomicBitToggle(&p->au32[0], i);
264 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
265 CHECK_BIT(!ASMAtomicBitTestAndToggle(&p->au32[0], i), i);
266 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
267 CHECK_BIT(ASMAtomicBitTestAndToggle(&p->au32[0], i), i);
268 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
269 }
270
271 /* bit searching */
272 MAP_SET(p);
273 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == -1);
274 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
275
276 ASMBitClear(&p->au32[0], 1);
277 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 1);
278 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
279
280 MAP_SET(p);
281 ASMBitClear(&p->au32[0], 95);
282 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 95);
283 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
284
285 MAP_SET(p);
286 ASMBitClear(&p->au32[0], 127);
287 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 127);
288 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
289 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 0) == 1);
290 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 1) == 2);
291 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 2) == 3);
292
293
294 MAP_SET(p);
295 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 0) == -1);
296 ASMBitClear(&p->au32[0], 32);
297 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 32) == -1);
298 ASMBitClear(&p->au32[0], 88);
299 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 57) == 88);
300
301 MAP_SET(p);
302 ASMBitClear(&p->au32[0], 31);
303 ASMBitClear(&p->au32[0], 57);
304 ASMBitClear(&p->au32[0], 88);
305 ASMBitClear(&p->au32[0], 101);
306 ASMBitClear(&p->au32[0], 126);
307 ASMBitClear(&p->au32[0], 127);
308 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 31);
309 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 31) == 57);
310 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 57) == 88);
311 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 88) == 101);
312 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 101) == 126);
313 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 126) == 127);
314 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 127) == -1);
315
316 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 29) == 30);
317 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 30) == 32);
318
319 MAP_CLEAR(p);
320 for (i = 1; i < 128; i++)
321 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, i - 1) == i, i);
322 for (i = 0; i < 128; i++)
323 {
324 MAP_SET(p);
325 ASMBitClear(&p->au32[0], i);
326 CHECK_BIT(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == i, i);
327 for (j = 0; j < i; j++)
328 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, j) == i, i);
329 for (j = i; j < 128; j++)
330 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, j) == -1, i);
331 }
332
333 /* clear range. */
334 MAP_SET(p);
335 ASMBitClearRange(&p->au32, 0, 128);
336 CHECK(!p->au32[0] && !p->au32[1] && !p->au32[2] && !p->au32[3]);
337 for (i = 0; i < 128; i++)
338 {
339 for (j = i + 1; j <= 128; j++)
340 {
341 MAP_SET(p);
342 ASMBitClearRange(&p->au32, i, j);
343 for (k = 0; k < i; k++)
344 CHECK_BIT3(ASMBitTest(&p->au32[0], k), i, j, k);
345 for (k = i; k < j; k++)
346 CHECK_BIT3(!ASMBitTest(&p->au32[0], k), i, j, k);
347 for (k = j; k < 128; k++)
348 CHECK_BIT3(ASMBitTest(&p->au32[0], k), i, j, k);
349 }
350 }
351
352 /* searching for set bits. */
353 MAP_CLEAR(p);
354 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == -1);
355
356 ASMBitSet(&p->au32[0], 65);
357 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 65);
358 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 65) == -1);
359 for (i = 0; i < 65; i++)
360 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 65);
361 for (i = 65; i < 128; i++)
362 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == -1);
363
364 ASMBitSet(&p->au32[0], 17);
365 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 17);
366 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 17) == 65);
367 for (i = 0; i < 16; i++)
368 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 17);
369 for (i = 17; i < 65; i++)
370 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 65);
371
372 MAP_SET(p);
373 for (i = 1; i < 128; i++)
374 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i - 1) == i, i);
375 for (i = 0; i < 128; i++)
376 {
377 MAP_CLEAR(p);
378 ASMBitSet(&p->au32[0], i);
379 CHECK_BIT(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == i, i);
380 for (j = 0; j < i; j++)
381 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, j) == i, i);
382 for (j = i; j < 128; j++)
383 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, j) == -1, i);
384 }
385
386
387 CHECK(ASMBitLastSetU32(0) == 0);
388 CHECK(ASMBitLastSetU32(1) == 1);
389 CHECK(ASMBitLastSetU32(0x80000000) == 32);
390 CHECK(ASMBitLastSetU32(0xffffffff) == 32);
391 CHECK(ASMBitLastSetU32(RT_BIT(23) | RT_BIT(11)) == 24);
392 for (i = 0; i < 32; i++)
393 CHECK(ASMBitLastSetU32(1 << i) == (unsigned)i + 1);
394
395 CHECK(ASMBitFirstSetU32(0) == 0);
396 CHECK(ASMBitFirstSetU32(1) == 1);
397 CHECK(ASMBitFirstSetU32(0x80000000) == 32);
398 CHECK(ASMBitFirstSetU32(0xffffffff) == 1);
399 CHECK(ASMBitFirstSetU32(RT_BIT(23) | RT_BIT(11)) == 12);
400 for (i = 0; i < 32; i++)
401 CHECK(ASMBitFirstSetU32(1 << i) == (unsigned)i + 1);
402
403 /*
404 * Special tests.
405 */
406 test2(hTest);
407
408 /*
409 * Summary
410 */
411 return RTTestSummaryAndDestroy(hTest);
412}
413
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette