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