VirtualBox

source: vbox/trunk/src/VBox/Runtime/testcase/tstRTBitOperations.cpp@ 48935

Last change on this file since 48935 was 48935, checked in by vboxsync, 11 years ago

Runtime: Whitespace and svn:keyword cleanups by scm.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 15.0 KB
Line 
1/* $Id: tstRTBitOperations.cpp 48935 2013-10-07 21:19:37Z vboxsync $ */
2/** @file
3 * IPRT Testcase - Inlined Bit Operations.
4 */
5
6/*
7 * Copyright (C) 2006-2011 Oracle Corporation
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
27/*******************************************************************************
28* Header Files *
29*******************************************************************************/
30#include <iprt/asm.h>
31
32#include <iprt/initterm.h>
33#include <iprt/stream.h>
34#include <iprt/string.h>
35#include <iprt/test.h>
36
37
38/*
39 * Test 2 - ID allocation using a bitmap.
40 */
41
42#define NIL_TEST2_ID 0
43#define TEST2_ID_LAST ((RT_BIT_32(28) - 1) >> 8)
44
45struct TestMap2
46{
47 uint32_t idNil;
48 uint32_t idLast;
49 uint32_t idChunkPrev;
50 uint32_t bmChunkId[(TEST2_ID_LAST + 1 + 31) / 32];
51};
52
53static uint32_t test2AllocId(struct TestMap2 *p2)
54{
55 /*
56 * Scan sequentially from the last one + 1.
57 */
58 int32_t idChunk = ++p2->idChunkPrev;
59 if ( (uint32_t)idChunk < TEST2_ID_LAST
60 && idChunk > NIL_TEST2_ID)
61 {
62 idChunk = ASMBitNextClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1, idChunk);
63 if (idChunk > NIL_TEST2_ID)
64 {
65 if (ASMAtomicBitTestAndSet(&p2->bmChunkId[0], idChunk))
66 {
67 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
68 return NIL_TEST2_ID;
69 }
70 return p2->idChunkPrev = idChunk;
71 }
72 }
73
74 /*
75 * Ok, scan from the start.
76 */
77 idChunk = ASMBitFirstClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1);
78 if (idChunk <= NIL_TEST2_ID)
79 {
80 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
81 return NIL_TEST2_ID;
82 }
83 if (ASMAtomicBitTestAndSet(&p2->bmChunkId[0], idChunk))
84 {
85 RTTestFailed(NIL_RTTEST, "line %d: idChunk=%#x", __LINE__, idChunk);
86 return NIL_TEST2_ID;
87 }
88
89 return p2->idChunkPrev = idChunk;
90}
91
92
93static void test2(RTTEST hTest)
94{
95 struct TestMap2 *p2 = (struct TestMap2 *)RTTestGuardedAllocTail(hTest, sizeof(TestMap2));
96 p2->idNil = NIL_TEST2_ID;
97 p2->idLast = TEST2_ID_LAST;
98
99 /* Some simple tests first. */
100 RT_ZERO(p2->bmChunkId);
101 RTTEST_CHECK(hTest, ASMBitFirstSet(&p2->bmChunkId[0], TEST2_ID_LAST + 1) == -1);
102 for (uint32_t iBit = 0; iBit <= TEST2_ID_LAST; iBit++)
103 RTTEST_CHECK(hTest, !ASMBitTest(&p2->bmChunkId[0], iBit));
104
105 memset(&p2->bmChunkId[0], 0xff, sizeof(p2->bmChunkId));
106 RTTEST_CHECK(hTest, ASMBitFirstClear(&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 /* The real test. */
111 p2->idChunkPrev = 0;
112 RT_ZERO(p2->bmChunkId);
113 ASMBitSet(p2->bmChunkId, NIL_TEST2_ID);
114 uint32_t cLeft = TEST2_ID_LAST;
115 while (cLeft-- > 0)
116 test2AllocId(p2);
117
118 RTTEST_CHECK(hTest, ASMBitFirstClear(&p2->bmChunkId[0], TEST2_ID_LAST + 1) == -1);
119}
120
121
122int main()
123{
124 /*
125 * Init the runtime and stuff.
126 */
127 RTTEST hTest;
128 int rc = RTTestInitAndCreate("tstRTBitOperations", &hTest);
129 if (rc)
130 return rc;
131 RTTestBanner(hTest);
132
133 int i;
134 int j;
135 int k;
136
137 /*
138 * Tests
139 */
140 struct TestMap
141 {
142 uint32_t au32[4];
143 };
144#if 0
145 struct TestMap sTest;
146 struct TestMap *p = &sTest;
147#else
148 struct TestMap *p = (struct TestMap *)RTTestGuardedAllocTail(hTest, sizeof(*p));
149#endif
150#define DUMP() RTTestPrintf(hTest, RTTESTLVL_INFO, "au32={%08x,%08x,%08x,%08x}", p->au32[0], p->au32[1], p->au32[2], p->au32[3])
151#define CHECK(expr) do { if (!(expr)) { RTTestFailed(hTest, "line %d: %s", __LINE__, #expr); DUMP(); } CHECK_GUARD(s); } while (0)
152#define CHECK_BIT(expr, b1) do { if (!(expr)) { RTTestFailed(hTest, "line %d, b1=%d: %s", __LINE__, b1, #expr); } CHECK_GUARD(s); } while (0)
153#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)
154#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)
155
156#define GUARD_MAP(p) do { } while (0)
157#define CHECK_GUARD(p) do { } while (0)
158#define MAP_CLEAR(p) do { RT_ZERO(*(p)); GUARD_MAP(p); } while (0)
159#define MAP_SET(p) do { memset(p, 0xff, sizeof(*(p))); GUARD_MAP(p); } while (0)
160
161 /* self check. */
162 MAP_CLEAR(p);
163 CHECK_GUARD(p);
164
165 /* set */
166 MAP_CLEAR(p);
167 ASMBitSet(&p->au32[0], 0);
168 ASMBitSet(&p->au32[0], 31);
169 ASMBitSet(&p->au32[0], 65);
170 CHECK(p->au32[0] == 0x80000001U);
171 CHECK(p->au32[2] == 0x00000002U);
172 CHECK(ASMBitTestAndSet(&p->au32[0], 0) && p->au32[0] == 0x80000001U);
173 CHECK(!ASMBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x80010001U);
174 CHECK(ASMBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x80010001U);
175 CHECK(!ASMBitTestAndSet(&p->au32[0], 80) && p->au32[2] == 0x00010002U);
176
177 MAP_CLEAR(p);
178 ASMAtomicBitSet(&p->au32[0], 0);
179 ASMAtomicBitSet(&p->au32[0], 30);
180 ASMAtomicBitSet(&p->au32[0], 64);
181 CHECK(p->au32[0] == 0x40000001U);
182 CHECK(p->au32[2] == 0x00000001U);
183 CHECK(ASMAtomicBitTestAndSet(&p->au32[0], 0) && p->au32[0] == 0x40000001U);
184 CHECK(!ASMAtomicBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x40010001U);
185 CHECK(ASMAtomicBitTestAndSet(&p->au32[0], 16) && p->au32[0] == 0x40010001U);
186 CHECK(!ASMAtomicBitTestAndSet(&p->au32[0], 80) && p->au32[2] == 0x00010001U);
187
188 /* clear */
189 MAP_SET(p);
190 ASMBitClear(&p->au32[0], 0);
191 ASMBitClear(&p->au32[0], 31);
192 ASMBitClear(&p->au32[0], 65);
193 CHECK(p->au32[0] == ~0x80000001U);
194 CHECK(p->au32[2] == ~0x00000002U);
195 CHECK(!ASMBitTestAndClear(&p->au32[0], 0) && p->au32[0] == ~0x80000001U);
196 CHECK(ASMBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
197 CHECK(!ASMBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
198 CHECK(ASMBitTestAndClear(&p->au32[0], 80) && p->au32[2] == ~0x00010002U);
199
200 MAP_SET(p);
201 ASMAtomicBitClear(&p->au32[0], 0);
202 ASMAtomicBitClear(&p->au32[0], 30);
203 ASMAtomicBitClear(&p->au32[0], 64);
204 CHECK(p->au32[0] == ~0x40000001U);
205 CHECK(p->au32[2] == ~0x00000001U);
206 CHECK(!ASMAtomicBitTestAndClear(&p->au32[0], 0) && p->au32[0] == ~0x40000001U);
207 CHECK(ASMAtomicBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
208 CHECK(!ASMAtomicBitTestAndClear(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
209 CHECK(ASMAtomicBitTestAndClear(&p->au32[0], 80) && p->au32[2] == ~0x00010001U);
210
211 /* toggle */
212 MAP_SET(p);
213 ASMBitToggle(&p->au32[0], 0);
214 ASMBitToggle(&p->au32[0], 31);
215 ASMBitToggle(&p->au32[0], 65);
216 ASMBitToggle(&p->au32[0], 47);
217 ASMBitToggle(&p->au32[0], 47);
218 CHECK(p->au32[0] == ~0x80000001U);
219 CHECK(p->au32[2] == ~0x00000002U);
220 CHECK(!ASMBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x80000000U);
221 CHECK(ASMBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x80000001U);
222 CHECK(ASMBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x80010001U);
223 CHECK(!ASMBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x80000001U);
224 CHECK(ASMBitTestAndToggle(&p->au32[0], 80) && p->au32[2] == ~0x00010002U);
225
226 MAP_SET(p);
227 ASMAtomicBitToggle(&p->au32[0], 0);
228 ASMAtomicBitToggle(&p->au32[0], 30);
229 ASMAtomicBitToggle(&p->au32[0], 64);
230 ASMAtomicBitToggle(&p->au32[0], 47);
231 ASMAtomicBitToggle(&p->au32[0], 47);
232 CHECK(p->au32[0] == ~0x40000001U);
233 CHECK(p->au32[2] == ~0x00000001U);
234 CHECK(!ASMAtomicBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x40000000U);
235 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 0) && p->au32[0] == ~0x40000001U);
236 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x40010001U);
237 CHECK(!ASMAtomicBitTestAndToggle(&p->au32[0], 16) && p->au32[0] == ~0x40000001U);
238 CHECK(ASMAtomicBitTestAndToggle(&p->au32[0], 80) && p->au32[2] == ~0x00010001U);
239
240 /* test bit. */
241 for (i = 0; i < 128; i++)
242 {
243 MAP_SET(p);
244 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
245 ASMBitToggle(&p->au32[0], i);
246 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
247 CHECK_BIT(!ASMBitTestAndToggle(&p->au32[0], i), i);
248 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
249 CHECK_BIT(ASMBitTestAndToggle(&p->au32[0], i), i);
250 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
251
252 MAP_SET(p);
253 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
254 ASMAtomicBitToggle(&p->au32[0], i);
255 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
256 CHECK_BIT(!ASMAtomicBitTestAndToggle(&p->au32[0], i), i);
257 CHECK_BIT(ASMBitTest(&p->au32[0], i), i);
258 CHECK_BIT(ASMAtomicBitTestAndToggle(&p->au32[0], i), i);
259 CHECK_BIT(!ASMBitTest(&p->au32[0], i), i);
260 }
261
262 /* bit searching */
263 MAP_SET(p);
264 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == -1);
265 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
266
267 ASMBitClear(&p->au32[0], 1);
268 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 1);
269 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
270
271 MAP_SET(p);
272 ASMBitClear(&p->au32[0], 95);
273 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 95);
274 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
275
276 MAP_SET(p);
277 ASMBitClear(&p->au32[0], 127);
278 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 127);
279 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 0);
280 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 0) == 1);
281 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 1) == 2);
282 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 2) == 3);
283
284
285 MAP_SET(p);
286 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 0) == -1);
287 ASMBitClear(&p->au32[0], 32);
288 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 32) == -1);
289 ASMBitClear(&p->au32[0], 88);
290 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 57) == 88);
291
292 MAP_SET(p);
293 ASMBitClear(&p->au32[0], 31);
294 ASMBitClear(&p->au32[0], 57);
295 ASMBitClear(&p->au32[0], 88);
296 ASMBitClear(&p->au32[0], 101);
297 ASMBitClear(&p->au32[0], 126);
298 ASMBitClear(&p->au32[0], 127);
299 CHECK(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == 31);
300 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 31) == 57);
301 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 57) == 88);
302 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 88) == 101);
303 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 101) == 126);
304 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 126) == 127);
305 CHECK(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, 127) == -1);
306
307 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 29) == 30);
308 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 30) == 32);
309
310 MAP_CLEAR(p);
311 for (i = 1; i < 128; i++)
312 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, i - 1) == i, i);
313 for (i = 0; i < 128; i++)
314 {
315 MAP_SET(p);
316 ASMBitClear(&p->au32[0], i);
317 CHECK_BIT(ASMBitFirstClear(&p->au32[0], sizeof(p->au32) * 8) == i, i);
318 for (j = 0; j < i; j++)
319 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, j) == i, i);
320 for (j = i; j < 128; j++)
321 CHECK_BIT(ASMBitNextClear(&p->au32[0], sizeof(p->au32) * 8, j) == -1, i);
322 }
323
324 /* clear range. */
325 MAP_SET(p);
326 ASMBitClearRange(&p->au32, 0, 128);
327 CHECK(!p->au32[0] && !p->au32[1] && !p->au32[2] && !p->au32[3]);
328 for (i = 0; i < 128; i++)
329 {
330 for (j = i + 1; j <= 128; j++)
331 {
332 MAP_SET(p);
333 ASMBitClearRange(&p->au32, i, j);
334 for (k = 0; k < i; k++)
335 CHECK_BIT3(ASMBitTest(&p->au32[0], k), i, j, k);
336 for (k = i; k < j; k++)
337 CHECK_BIT3(!ASMBitTest(&p->au32[0], k), i, j, k);
338 for (k = j; k < 128; k++)
339 CHECK_BIT3(ASMBitTest(&p->au32[0], k), i, j, k);
340 }
341 }
342
343 /* searching for set bits. */
344 MAP_CLEAR(p);
345 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == -1);
346
347 ASMBitSet(&p->au32[0], 65);
348 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 65);
349 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 65) == -1);
350 for (i = 0; i < 65; i++)
351 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 65);
352 for (i = 65; i < 128; i++)
353 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == -1);
354
355 ASMBitSet(&p->au32[0], 17);
356 CHECK(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == 17);
357 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, 17) == 65);
358 for (i = 0; i < 16; i++)
359 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 17);
360 for (i = 17; i < 65; i++)
361 CHECK(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i) == 65);
362
363 MAP_SET(p);
364 for (i = 1; i < 128; i++)
365 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, i - 1) == i, i);
366 for (i = 0; i < 128; i++)
367 {
368 MAP_CLEAR(p);
369 ASMBitSet(&p->au32[0], i);
370 CHECK_BIT(ASMBitFirstSet(&p->au32[0], sizeof(p->au32) * 8) == i, i);
371 for (j = 0; j < i; j++)
372 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, j) == i, i);
373 for (j = i; j < 128; j++)
374 CHECK_BIT(ASMBitNextSet(&p->au32[0], sizeof(p->au32) * 8, j) == -1, i);
375 }
376
377
378 CHECK(ASMBitLastSetU32(0) == 0);
379 CHECK(ASMBitLastSetU32(1) == 1);
380 CHECK(ASMBitLastSetU32(0x80000000) == 32);
381 CHECK(ASMBitLastSetU32(0xffffffff) == 32);
382 CHECK(ASMBitLastSetU32(RT_BIT(23) | RT_BIT(11)) == 24);
383 for (i = 0; i < 32; i++)
384 CHECK(ASMBitLastSetU32(1 << i) == (unsigned)i + 1);
385
386 CHECK(ASMBitFirstSetU32(0) == 0);
387 CHECK(ASMBitFirstSetU32(1) == 1);
388 CHECK(ASMBitFirstSetU32(0x80000000) == 32);
389 CHECK(ASMBitFirstSetU32(0xffffffff) == 1);
390 CHECK(ASMBitFirstSetU32(RT_BIT(23) | RT_BIT(11)) == 12);
391 for (i = 0; i < 32; i++)
392 CHECK(ASMBitFirstSetU32(1 << i) == (unsigned)i + 1);
393
394 /*
395 * Special tests.
396 */
397 test2(hTest);
398
399 /*
400 * Summary
401 */
402 return RTTestSummaryAndDestroy(hTest);
403}
404
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