1 /*
2 Copyright (c) 2004, 2011, Oracle and/or its affiliates. All rights reserved.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25 #include <Bitmask.hpp>
26 #include <NdbOut.hpp>
27
28 void
getFieldImpl(const Uint32 src[],unsigned shiftL,unsigned len,Uint32 dst[])29 BitmaskImpl::getFieldImpl(const Uint32 src[],
30 unsigned shiftL, unsigned len, Uint32 dst[])
31 {
32 /* Copy whole words of src to dst, shifting src left
33 * by shiftL. Undefined bits of the last written dst word
34 * should be zeroed.
35 */
36 assert(shiftL < 32);
37
38 unsigned shiftR = 32 - shiftL;
39 unsigned undefined = shiftL ? ~0 : 0;
40
41 /* Merge first word with previously set bits if there's a shift */
42 * dst = shiftL ? * dst : 0;
43
44 /* Treat the zero-shift case separately to avoid
45 * trampling or reading past the end of src
46 */
47 if (shiftL == 0)
48 {
49 while(len >= 32)
50 {
51 * dst++ = * src++;
52 len -=32;
53 }
54
55 if (len != 0)
56 {
57 /* Last word has some bits set */
58 Uint32 mask= ((1 << len) -1); // 0000111
59 * dst = (* src) & mask;
60 }
61 }
62 else // shiftL !=0, need to build each word from two words shifted
63 {
64 while(len >= 32)
65 {
66 * dst++ |= (* src) << shiftL;
67 * dst = ((* src++) >> shiftR) & undefined;
68 len -= 32;
69 }
70
71 /* Have space for shiftR more bits in the current dst word
72 * is that enough?
73 */
74 if(len <= shiftR)
75 {
76 /* Fit the remaining bits in the current dst word */
77 * dst |= ((* src) & ((1 << len) - 1)) << shiftL;
78 }
79 else
80 {
81 /* Need to write to two dst words */
82 * dst++ |= ((* src) << shiftL);
83 * dst = ((* src) >> shiftR) & ((1 << (len - shiftR)) - 1) & undefined;
84 }
85 }
86 }
87
88 void
setFieldImpl(Uint32 dst[],unsigned shiftL,unsigned len,const Uint32 src[])89 BitmaskImpl::setFieldImpl(Uint32 dst[],
90 unsigned shiftL, unsigned len, const Uint32 src[])
91 {
92 /**
93 *
94 * abcd ef00
95 * 00ab cdef
96 */
97 assert(shiftL < 32);
98 unsigned shiftR = 32 - shiftL;
99 unsigned undefined = shiftL ? ~0 : 0;
100 while(len >= 32)
101 {
102 * dst = (* src++) >> shiftL;
103 * dst++ |= ((* src) << shiftR) & undefined;
104 len -= 32;
105 }
106
107 /* Copy last bits */
108 Uint32 mask = ((1 << len) -1);
109 * dst = (* dst & ~mask);
110 if(len <= shiftR)
111 {
112 /* Remaining bits fit in current word */
113 * dst |= ((* src++) >> shiftL) & mask;
114 }
115 else
116 {
117 /* Remaining bits update 2 words */
118 * dst |= ((* src++) >> shiftL);
119 * dst |= ((* src) & ((1 << (len - shiftR)) - 1)) << shiftR ;
120 }
121 }
122
123 /* Bitmask testcase code moved from here to
124 * storage/ndb/test/ndbapi/testBitfield.cpp
125 * to get coverage from automated testing
126 */
127
128 template struct BitmaskPOD<1>;
129 template struct BitmaskPOD<2>; // NdbNodeBitmask
130 template struct BitmaskPOD<8>; // NodeBitmask
131 template struct BitmaskPOD<16>;
132
133 #ifdef TEST_BITMASK
134 #include <util/NdbTap.hpp>
135 #include <util/BaseString.hpp>
136
137 #include "parse_mask.hpp"
138
TAPTEST(Bitmask)139 TAPTEST(Bitmask)
140 {
141 unsigned i, found;
142 Bitmask<8> b;
143 OK(b.isclear());
144
145 unsigned MAX_BITS = 32 * b.Size;
146 for (i = 0; i < MAX_BITS; i++)
147 {
148 if (i > 60)
149 continue;
150 switch(i)
151 {
152 case 2:case 3:case 5:case 7:case 11:case 13:case 17:case 19:case 23:
153 case 29:case 31:case 37:case 41:case 43:
154 break;
155 default:;
156 b.set(i);
157 }
158 }
159 for (found = i = 0; i < MAX_BITS; i++)
160 found+=(int)b.get(i);
161 OK(found == b.count());
162 OK(found == 47);
163 printf("getText: %s\n", BaseString::getText(b).c_str());
164 OK(BaseString::getText(b) ==
165 "0000000000000000000000000000000000000000000000001ffff5df5f75d753");
166 printf("getPrettyText: %s\n", BaseString::getPrettyText(b).c_str());
167 OK(BaseString::getPrettyText(b) ==
168 "0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, "
169 "27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 47, "
170 "48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59 and 60");
171 printf("getPrettyTextShort: %s\n",
172 BaseString::getPrettyTextShort(b).c_str());
173 OK(BaseString::getPrettyTextShort(b) ==
174 "0,1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,"
175 "33,34,35,36,38,39,40,42,44,45,46,47,48,49,50,51,52,53,54,55,"
176 "56,57,58,59,60");
177
178 // bitNOT Tests
179 Bitmask<8> c = b;
180 OK(c.equal(b));
181 c.bitNOT();
182 printf("getPrettyTextShort(c 1): %s\n",
183 BaseString::getPrettyTextShort(c).c_str());
184 OK(!c.equal(b));
185 c.bitNOT();
186 OK(c.count() == b.count());
187 OK(c.equal(b));
188 printf("getPrettyTextShort(c 2): %s\n",
189 BaseString::getPrettyTextShort(c).c_str());
190
191 Bitmask<1> d;
192 d.set(1);
193 d.set(3);
194 d.set(4);
195 printf("getPrettyTextShort(d 1): %s\n",
196 BaseString::getPrettyTextShort(d).c_str());
197 OK(d.count() == 3);
198 {
199 Uint8 tmp[32];
200 Uint32 len = d.toArray(tmp, sizeof(tmp));
201 printf("toArray(): ");
202 for (Uint32 i = 0; i < len; i++)
203 printf("%u ", (Uint32)tmp[i]);
204 printf("\n");
205 OK(len == 3);
206 OK(tmp[0] == 1);
207 OK(tmp[1] == 3);
208 OK(tmp[2] == 4);
209 }
210 d.bitNOT();
211 printf("getPrettyTextShort(d 2): %s\n",
212 BaseString::getPrettyTextShort(d).c_str());
213 OK(d.get(2));
214 OK(!d.get(4));
215 OK(d.count() != 3);
216 d.bitNOT();
217 OK(d.count() == 3);
218 printf("getPrettyTextShort(d 3): %s\n",
219 BaseString::getPrettyTextShort(d).c_str());
220
221 /*
222 parse_mask
223 */
224 Bitmask<8> mask;
225 OK(parse_mask("1,2,5-7,255", mask) == 6);
226
227 {
228 Uint8 tmp[8 * 32];
229 Uint32 len = mask.toArray(tmp, sizeof(tmp));
230 printf("toArray(): ");
231 for (Uint32 i = 0; i < len; i++)
232 printf("%u ", (Uint32)tmp[i]);
233 printf("\n");
234 OK(len == 6);
235 OK(tmp[0] == 1);
236 OK(tmp[1] == 2);
237 OK(tmp[2] == 5);
238 OK(tmp[3] == 6);
239 OK(tmp[4] == 7);
240 OK(tmp[5] == 255);
241 }
242
243 // Check all specified bits set
244 OK(mask.get(1));
245 OK(mask.get(2));
246 OK(mask.get(5));
247 OK(mask.get(6));
248 OK(mask.get(7));
249 OK(mask.get(255));
250
251 // Check some random bits not set
252 OK(!mask.get(0));
253 OK(!mask.get(4));
254 OK(!mask.get(3));
255 OK(!mask.get(8));
256 OK(!mask.get(22));
257 OK(!mask.get(254));
258
259 // Parse at the limit
260 OK(parse_mask("254", mask) == 1);
261 OK(parse_mask("255", mask) == 1);
262
263 // Parse invalid spec(s)
264 OK(parse_mask("xx", mask) == -1);
265 OK(parse_mask("5-", mask) == -1);
266 OK(parse_mask("-5", mask) == -1);
267 OK(parse_mask("1,-5", mask) == -1);
268
269 // Parse too large spec
270 OK(parse_mask("256", mask) == -2);
271 OK(parse_mask("1-255,256", mask) == -2);
272
273
274 return 1; // OK
275 }
276
277 #endif
278
279 #ifdef BENCH_BITMASK
280
281 #include <math.h>
282 #include <portlib/NdbTick.h>
283
284 typedef Uint32 (* FUNC)(Uint32 n);
285
286 static
287 Uint32
fast(Uint32 n)288 fast(Uint32 n)
289 {
290 return BitmaskImpl::count_bits(n) +
291 BitmaskImpl::count_bits(n*n);
292 }
293
294 static
295 Uint32
slow(Uint32 n)296 slow(Uint32 n)
297 {
298 double d = 1 + n;
299 double l = log(d);
300 double s = sqrt(d);
301 double r = d * l * s;
302 double t = r > 0 ? r : r < 0 ? -r : 1;
303 double u = log(t);
304 double v = sqrt(t);
305 double w = log(d + s + t + v);
306 double x = sqrt(d + s + t + v);
307 return (Uint32)(d * l * s * r * t * u * v * w * x);
308 }
309
310 struct Result
311 {
ResultResult312 Result() { sum = 0; elapsed = 0; }
313 Uint32 sum;
314 Uint64 elapsed;
315 };
316
317 inline
318 void
test_empty(Result & res,Uint32 len,unsigned iter,FUNC func)319 test_empty(Result& res, Uint32 len, unsigned iter, FUNC func)
320 {
321 Uint32 sum = 0;
322 Uint64 start = NdbTick_CurrentMillisecond();
323 for (Uint32 j = 0; j<iter; j++)
324 {
325 for (Uint32 k = 0; k<len; k++)
326 sum += (* func)(k);
327 }
328 Uint64 stop = NdbTick_CurrentMillisecond();
329 res.sum += sum;
330 res.elapsed += (stop - start);
331 }
332
333 template<unsigned sz>
334 inline
335 void
test_find(Result & res,const Bitmask<sz> & mask,unsigned iter,FUNC func)336 test_find(Result& res, const Bitmask<sz> & mask, unsigned iter, FUNC func)
337 {
338 Uint32 sum = 0;
339 Uint64 start = NdbTick_CurrentMillisecond();
340 for (Uint32 j = 0; j<iter; j++)
341 {
342 for (Uint32 n = mask.find(0); n != mask.NotFound;
343 n = mask.find(n + 1))
344 {
345 sum += (* func)(n);
346 }
347 }
348 Uint64 stop = NdbTick_CurrentMillisecond();
349 res.sum += sum;
350 res.elapsed += (stop - start);
351 }
352
353 template<unsigned sz>
354 inline
355 void
test_find_fast(Result & res,const Bitmask<sz> & mask,unsigned iter,FUNC func)356 test_find_fast(Result& res, const Bitmask<sz> & mask, unsigned iter, FUNC func)
357 {
358 Uint32 sum = 0;
359 Uint64 start = NdbTick_CurrentMillisecond();
360 for (Uint32 j = 0; j<iter; j++)
361 {
362
363 for (Uint32 n = BitmaskImpl::find_first(sz, mask.rep.data);
364 n != mask.NotFound;
365 n = BitmaskImpl::find_next(sz, mask.rep.data, n + 1))
366 {
367 sum += (* func)(n);
368 }
369 }
370 Uint64 stop = NdbTick_CurrentMillisecond();
371 res.sum += sum;
372 res.elapsed += (stop - start);
373 }
374
375 template<unsigned sz>
376 inline
377 void
test_toArray(Result & res,const Bitmask<sz> & mask,unsigned iter,FUNC func)378 test_toArray(Result& res, const Bitmask<sz> & mask, unsigned iter, FUNC func)
379 {
380 Uint32 sum = 0;
381 Uint64 start = NdbTick_CurrentMillisecond();
382 for (Uint32 j = 0; j<iter; j++)
383 {
384 Uint8 tmp[256];
385 Uint32 cnt = mask.toArray(tmp, sizeof(tmp));
386 for (Uint32 n = 0; n<cnt; n++)
387 sum += (* func)(tmp[n]);
388 }
389 Uint64 stop = NdbTick_CurrentMillisecond();
390 res.sum += sum;
391 res.elapsed += (stop - start);
392 }
393
394 static
395 Uint64
sub0(Uint64 hi,Uint64 lo)396 sub0(Uint64 hi, Uint64 lo)
397 {
398 if (hi > lo)
399 return hi - lo;
400 return 0;
401 }
402
403 static
404 Uint64
x_min(Uint64 a,Uint64 b,Uint64 c)405 x_min(Uint64 a, Uint64 b, Uint64 c)
406 {
407 if (a < b && a < c)
408 return a;
409 if (b < a && b < c)
410 return b;
411 return c;
412 }
413
414 static
415 void
do_test(Uint32 len,FUNC func,const char * name,const char * dist)416 do_test(Uint32 len, FUNC func, const char * name, const char * dist)
417 {
418 Uint32 iter = 10000;
419 if (func == slow)
420 iter = 3000;
421
422 Result res_find, res_fast, res_toArray, res_empty;
423 for (Uint32 i = 0; i < (10000 / len); i++)
424 {
425 Bitmask<8> tmp;
426 if (strcmp(dist, "ran") == 0)
427 {
428 for (Uint32 i = 0; i<len; i++)
429 {
430 Uint32 b = rand() % (32 * tmp.Size);
431 while (tmp.get(b))
432 {
433 b = rand() % (32 * tmp.Size);
434 }
435 tmp.set(b);
436 }
437 }
438 else if (strcmp(dist, "low") == 0)
439 {
440 for (Uint32 i = 0; i<len; i++)
441 {
442 tmp.set(i);
443 }
444 }
445 test_find(res_find, tmp, iter, func);
446 test_find_fast(res_fast, tmp, iter, func);
447 test_toArray(res_toArray, tmp, iter, func);
448 test_empty(res_empty, len, iter, func);
449 }
450
451 res_find.elapsed = sub0(res_find.elapsed, res_empty.elapsed);
452 res_toArray.elapsed = sub0(res_toArray.elapsed, res_empty.elapsed);
453 res_fast.elapsed = sub0(res_fast.elapsed, res_empty.elapsed);
454 Uint64 m = x_min(res_find.elapsed, res_toArray.elapsed, res_fast.elapsed);
455 if (m == 0)
456 m = 1;
457
458 Uint64 div = iter * (10000 / len);
459 printf("empty(%s,%s, %u) : %llu ns/iter (elapsed: %llums)\n",
460 dist, name, len,
461 (1000000 * res_empty.elapsed / div / len),
462 res_empty.elapsed);
463 printf("find(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n",
464 dist, name, len,
465 (1000000 * res_find.elapsed / div),
466 Uint32((100 * res_find.elapsed) / m),
467 res_find.sum);
468 printf("fast(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n",
469 dist, name, len,
470 (1000000 * res_fast.elapsed / div),
471 Uint32((100 * res_fast.elapsed) / m),
472 res_fast.sum);
473 printf("toArray(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n",
474 dist, name, len,
475 (1000000 * res_toArray.elapsed / div),
476 Uint32((100 * res_toArray.elapsed) / m),
477 res_toArray.sum);
478 printf("\n");
479 }
480
481 int
main(void)482 main(void)
483 {
484 int pos;
485 const int len[] = { 1, 10, 50, 100, 250, 0 };
486
487 pos = 0;
488 while (len[pos] != 0)
489 {
490 Uint32 l = len[pos++];
491 do_test(l, slow, "slow", "ran");
492 }
493
494 pos = 0;
495 while (len[pos] != 0)
496 {
497 Uint32 l = len[pos++];
498 do_test(l, slow, "slow", "low");
499 }
500
501 pos = 0;
502 while (len[pos] != 0)
503 {
504 Uint32 l = len[pos++];
505 do_test(l, fast, "fast", "ran");
506 }
507 pos = 0;
508 while (len[pos] != 0)
509 {
510 Uint32 l = len[pos++];
511 do_test(l, fast, "fast", "low");
512 }
513
514 return 0;
515 }
516
517 #endif
518