1 /* 2 * bitmask user library implementation. 3 * 4 * Copyright (c) 2004-2006 Silicon Graphics, Inc. All rights reserved. 5 * 6 * Paul Jackson <pj (at) sgi.com> 7 */ 8 9 /* 10 * This program is free software; you can redistribute it and/or modify 11 * it under the terms of the GNU Lesser General Public License as published by 12 * the Free Software Foundation; either version 2.1 of the License, or 13 * (at your option) any later version. 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 Lesser General Public License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 23 */ 24 25 #include <stdio.h> 26 #include <string.h> 27 #include <stdlib.h> 28 #include <stdint.h> 29 30 #include "bitmask.h" 31 #include "tst_minmax.h" 32 33 struct bitmask { 34 unsigned int size; 35 unsigned long *maskp; 36 }; 37 38 /* How many bits in an unsigned long */ 39 #define bitsperlong (8 * sizeof(unsigned long)) 40 41 /* howmany(a,b) : how many elements of size b needed to hold all of a */ 42 #define howmany(x,y) (((x)+((y)-1))/(y)) 43 44 /* How many longs in mask of n bits */ 45 #define longsperbits(n) howmany(n, bitsperlong) 46 47 /* 48 * The routines _getbit() and _setbit() are the only 49 * routines that actually understand the layout of bmp->maskp[]. 50 * 51 * On little endian architectures, this could simply be an array of 52 * bytes. But the kernel layout of bitmasks _is_ visible to userspace 53 * via the sched_(set/get)affinity calls in Linux 2.6, and on big 54 * endian architectures, it is painfully obvious that this is an 55 * array of unsigned longs. 56 */ 57 58 /* Return the value (0 or 1) of bit n in bitmask bmp */ 59 static unsigned int _getbit(const struct bitmask *bmp, unsigned int n) 60 { 61 if (n < bmp->size) 62 return (bmp->maskp[n / bitsperlong] >> (n % bitsperlong)) & 1; 63 else 64 return 0; 65 } 66 67 /* Set bit n in bitmask bmp to value v (0 or 1) */ 68 static void _setbit(struct bitmask *bmp, unsigned int n, unsigned int v) 69 { 70 if (n < bmp->size) { 71 if (v) 72 bmp->maskp[n / bitsperlong] |= 1UL << (n % bitsperlong); 73 else 74 bmp->maskp[n / bitsperlong] &= 75 ~(1UL << (n % bitsperlong)); 76 } 77 } 78 79 /* 80 * Allocate and free `struct bitmask *` 81 */ 82 83 /* Allocate a new `struct bitmask` with a size of n bits */ 84 struct bitmask *bitmask_alloc(unsigned int n) 85 { 86 struct bitmask *bmp; 87 88 bmp = malloc(sizeof(*bmp)); 89 if (bmp == 0) 90 return 0; 91 bmp->size = n; 92 bmp->maskp = calloc(longsperbits(n), sizeof(unsigned long)); 93 if (bmp->maskp == 0) { 94 free(bmp); 95 return 0; 96 } 97 return bmp; 98 } 99 100 /* Free `struct bitmask` */ 101 void bitmask_free(struct bitmask *bmp) 102 { 103 if (bmp == 0) 104 return; 105 free(bmp->maskp); 106 bmp->maskp = (unsigned long *)0xdeadcdef; /* double free tripwire */ 107 free(bmp); 108 } 109 110 /* 111 * Display and parse ascii string representations. 112 */ 113 114 #define HEXCHUNKSZ 32 /* hex binary format shows 32 bits per chunk */ 115 #define HEXCHARSZ 8 /* hex ascii format has up to 8 chars per chunk */ 116 117 /* 118 * Write hex word representation of bmp to buf, 32 bits per 119 * comma-separated, zero-filled hex word. Do not write more 120 * than buflen chars to buf. 121 * 122 * Return number of chars that would have been written 123 * if buf were large enough. 124 */ 125 126 int bitmask_displayhex(char *buf, int buflen, const struct bitmask *bmp) 127 { 128 int chunk; 129 int cnt = 0; 130 const char *sep = ""; 131 132 if (buflen < 1) 133 return 0; 134 buf[0] = 0; 135 136 for (chunk = howmany(bmp->size, HEXCHUNKSZ) - 1; chunk >= 0; chunk--) { 137 uint32_t val = 0; 138 int bit; 139 140 for (bit = HEXCHUNKSZ - 1; bit >= 0; bit--) 141 val = val << 1 | _getbit(bmp, chunk * HEXCHUNKSZ + bit); 142 cnt += snprintf(buf + cnt, MAX(buflen - cnt, 0), "%s%0*x", 143 sep, HEXCHARSZ, val); 144 sep = ","; 145 } 146 return cnt; 147 } 148 149 /* 150 * emit(buf, buflen, rbot, rtop, len) 151 * 152 * Helper routine for bitmask_displaylist(). Write decimal number 153 * or range to buf+len, suppressing output past buf+buflen, with optional 154 * comma-prefix. Return len of what would be written to buf, if it 155 * all fit. 156 */ 157 158 static inline int emit(char *buf, int buflen, int rbot, int rtop, int len) 159 { 160 if (len > 0) 161 len += snprintf(buf + len, MAX(buflen - len, 0), ","); 162 if (rbot == rtop) 163 len += snprintf(buf + len, MAX(buflen - len, 0), "%d", rbot); 164 else 165 len += 166 snprintf(buf + len, MAX(buflen - len, 0), "%d-%d", rbot, 167 rtop); 168 return len; 169 } 170 171 /* 172 * Write decimal list representation of bmp to buf. 173 * 174 * Output format is a comma-separated list of decimal numbers and 175 * ranges. Consecutively set bits are shown as two hyphen-separated 176 * decimal numbers, the smallest and largest bit numbers set in 177 * the range. Output format is compatible with the format 178 * accepted as input by bitmap_parselist(). 179 * 180 * The return value is the number of characters which would be 181 * generated for the given input, excluding the trailing '\0', as 182 * per ISO C99. 183 */ 184 185 int bitmask_displaylist(char *buf, int buflen, const struct bitmask *bmp) 186 { 187 int len = 0; 188 /* current bit is 'cur', most recently seen range is [rbot, rtop] */ 189 unsigned int cur, rbot, rtop; 190 191 if (buflen > 0) 192 *buf = 0; 193 rbot = cur = bitmask_first(bmp); 194 while (cur < bmp->size) { 195 rtop = cur; 196 cur = bitmask_next(bmp, cur + 1); 197 if (cur >= bmp->size || cur > rtop + 1) { 198 len = emit(buf, buflen, rbot, rtop, len); 199 rbot = cur; 200 } 201 } 202 return len; 203 } 204 205 static const char *nexttoken(const char *q, int sep) 206 { 207 if (q) 208 q = strchr(q, sep); 209 if (q) 210 q++; 211 return q; 212 } 213 214 /* 215 * Parse hex word representation in buf to bmp. 216 * 217 * Returns -1 on error, leaving unspecified results in bmp. 218 */ 219 220 int bitmask_parsehex(const char *buf, struct bitmask *bmp) 221 { 222 const char *p, *q; 223 int nchunks = 0, chunk; 224 unsigned int size = 0; 225 226 bitmask_clearall(bmp); 227 size = longsperbits(bmp->size) * 8 * sizeof(unsigned long); 228 229 q = buf; 230 while (p = q, q = nexttoken(q, ','), p) 231 nchunks++; 232 233 chunk = nchunks - 1; 234 q = buf; 235 while (p = q, q = nexttoken(q, ','), p) { 236 uint32_t val; 237 int bit; 238 char *endptr; 239 int nchars_read, nchars_unread; 240 241 val = strtoul(p, &endptr, 16); 242 243 /* We should have consumed 1 to 8 (HEXCHARSZ) chars */ 244 nchars_read = endptr - p; 245 if (nchars_read < 1 || nchars_read > HEXCHARSZ) 246 goto err; 247 248 /* We should have consumed up to next comma */ 249 nchars_unread = q - endptr; 250 if (q != NULL && nchars_unread != 1) 251 goto err; 252 253 for (bit = HEXCHUNKSZ - 1; bit >= 0; bit--) { 254 unsigned int n = chunk * HEXCHUNKSZ + bit; 255 if (n >= size) 256 goto err; 257 _setbit(bmp, n, (val >> bit) & 1); 258 } 259 chunk--; 260 } 261 return 0; 262 err: 263 bitmask_clearall(bmp); 264 return -1; 265 } 266 267 /* 268 * When parsing bitmask lists, only allow numbers, separated by one 269 * of the allowed next characters. 270 * 271 * The parameter 'sret' is the return from a sscanf "%u%c". It is 272 * -1 if the sscanf input string was empty. It is 0 if the first 273 * character in the sscanf input string was not a decimal number. 274 * It is 1 if the unsigned number matching the "%u" was the end of the 275 * input string. It is 2 if one or more additional characters followed 276 * the matched unsigned number. If it is 2, then 'nextc' is the first 277 * character following the number. The parameter 'ok_next_chars' 278 * is the nul-terminated list of allowed next characters. 279 * 280 * The mask term just scanned was ok if and only if either the numbers 281 * matching the %u were all of the input or if the next character in 282 * the input past the numbers was one of the allowed next characters. 283 */ 284 static int scan_was_ok(int sret, char nextc, const char *ok_next_chars) 285 { 286 return sret == 1 || (sret == 2 && strchr(ok_next_chars, nextc) != NULL); 287 } 288 289 /* 290 * Parses a comma-separated list of numbers and ranges of numbers, 291 * with optional ':%u' strides modifying ranges, into provided bitmask. 292 * Some examples of input lists and their equivalent simple list: 293 * Input Equivalent to 294 * 0-3 0,1,2,3 295 * 0-7:2 0,2,4,6 296 * 1,3,5-7 1,3,5,6,7 297 * 0-3:2,8-15:4 0,2,8,12 298 */ 299 int bitmask_parselist(const char *buf, struct bitmask *bmp) 300 { 301 const char *p, *q; 302 303 bitmask_clearall(bmp); 304 305 q = buf; 306 while (p = q, q = nexttoken(q, ','), p) { 307 unsigned int a; /* begin of range */ 308 unsigned int b; /* end of range */ 309 unsigned int s; /* stride */ 310 const char *c1, *c2; /* next tokens after '-' or ',' */ 311 char nextc; /* char after sscanf %u match */ 312 int sret; /* sscanf return (number of matches) */ 313 314 sret = sscanf(p, "%u%c", &a, &nextc); 315 if (!scan_was_ok(sret, nextc, ",-")) 316 goto err; 317 b = a; 318 s = 1; 319 c1 = nexttoken(p, '-'); 320 c2 = nexttoken(p, ','); 321 if (c1 != NULL && (c2 == NULL || c1 < c2)) { 322 sret = sscanf(c1, "%u%c", &b, &nextc); 323 if (!scan_was_ok(sret, nextc, ",:")) 324 goto err; 325 c1 = nexttoken(c1, ':'); 326 if (c1 != NULL && (c2 == NULL || c1 < c2)) { 327 sret = sscanf(c1, "%u%c", &s, &nextc); 328 if (!scan_was_ok(sret, nextc, ",")) 329 goto err; 330 } 331 } 332 if (!(a <= b)) 333 goto err; 334 if (b >= bmp->size) 335 goto err; 336 while (a <= b) { 337 _setbit(bmp, a, 1); 338 a += s; 339 } 340 } 341 return 0; 342 err: 343 bitmask_clearall(bmp); 344 return -1; 345 } 346 347 /* 348 * Basic assignment operations 349 */ 350 351 /* Copy bmp2 to bmp1 */ 352 struct bitmask *bitmask_copy(struct bitmask *bmp1, const struct bitmask *bmp2) 353 { 354 unsigned int i; 355 for (i = 0; i < bmp1->size; i++) 356 _setbit(bmp1, i, _getbit(bmp2, i)); 357 return bmp1; 358 } 359 360 /* Set all bits in bitmask: bmp = ~0 */ 361 struct bitmask *bitmask_setall(struct bitmask *bmp) 362 { 363 unsigned int i; 364 for (i = 0; i < bmp->size; i++) 365 _setbit(bmp, i, 1); 366 return bmp; 367 } 368 369 /* Clear all bits in bitmask: bmp = 0 */ 370 struct bitmask *bitmask_clearall(struct bitmask *bmp) 371 { 372 unsigned int i; 373 for (i = 0; i < bmp->size; i++) 374 _setbit(bmp, i, 0); 375 return bmp; 376 } 377 378 /* 379 * Interface to kernel sched_setaffinity system call 380 */ 381 382 /* Length in bytes of mask - use as second argument to sched_setaffinity */ 383 unsigned int bitmask_nbytes(struct bitmask *bmp) 384 { 385 return longsperbits(bmp->size) * sizeof(unsigned long); 386 } 387 388 /* Direct pointer to bit mask - use as third argument to sched_setaffinty */ 389 unsigned long *bitmask_mask(struct bitmask *bmp) 390 { 391 return bmp->maskp; 392 } 393 394 /* 395 * Unary numeric queries 396 */ 397 398 /* Size in bits of entire bitmask */ 399 unsigned int bitmask_nbits(const struct bitmask *bmp) 400 { 401 return bmp->size; 402 } 403 404 /* Hamming Weight: number of set bits */ 405 unsigned int bitmask_weight(const struct bitmask *bmp) 406 { 407 unsigned int i; 408 unsigned int w = 0; 409 for (i = 0; i < bmp->size; i++) 410 if (_getbit(bmp, i)) 411 w++; 412 return w; 413 } 414 415 /* 416 * Unary Boolean queries 417 */ 418 419 /* True if specified bit i is set */ 420 int bitmask_isbitset(const struct bitmask *bmp, unsigned int i) 421 { 422 return _getbit(bmp, i); 423 } 424 425 /* True if specified bit i is clear */ 426 int bitmask_isbitclear(const struct bitmask *bmp, unsigned int i) 427 { 428 return !_getbit(bmp, i); 429 } 430 431 /* True if all bits are set */ 432 int bitmask_isallset(const struct bitmask *bmp) 433 { 434 unsigned int i; 435 for (i = 0; i < bmp->size; i++) 436 if (!_getbit(bmp, i)) 437 return 0; 438 return 1; 439 } 440 441 /* True if all bits are clear */ 442 int bitmask_isallclear(const struct bitmask *bmp) 443 { 444 unsigned int i; 445 for (i = 0; i < bmp->size; i++) 446 if (_getbit(bmp, i)) 447 return 0; 448 return 1; 449 } 450 451 /* 452 * Single bit operations 453 */ 454 455 /* Set a single bit i in bitmask */ 456 struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i) 457 { 458 _setbit(bmp, i, 1); 459 return bmp; 460 } 461 462 /* Clear a single bit i in bitmask */ 463 struct bitmask *bitmask_clearbit(struct bitmask *bmp, unsigned int i) 464 { 465 _setbit(bmp, i, 0); 466 return bmp; 467 } 468 469 /* 470 * Binary Boolean operations: bmp1 op? bmp2 471 */ 472 473 /* True if two bitmasks are equal */ 474 int bitmask_equal(const struct bitmask *bmp1, const struct bitmask *bmp2) 475 { 476 unsigned int i; 477 for (i = 0; i < bmp1->size || i < bmp2->size; i++) 478 if (_getbit(bmp1, i) != _getbit(bmp2, i)) 479 return 0; 480 return 1; 481 } 482 483 /* True if first bitmask is subset of second */ 484 int bitmask_subset(const struct bitmask *bmp1, const struct bitmask *bmp2) 485 { 486 unsigned int i; 487 for (i = 0; i < bmp1->size; i++) 488 if (_getbit(bmp1, i) > _getbit(bmp2, i)) 489 return 0; 490 return 1; 491 } 492 493 /* True if two bitmasks don't overlap */ 494 int bitmask_disjoint(const struct bitmask *bmp1, const struct bitmask *bmp2) 495 { 496 unsigned int i; 497 for (i = 0; i < bmp1->size; i++) 498 if (_getbit(bmp1, i) & _getbit(bmp2, i)) 499 return 0; 500 return 1; 501 } 502 503 /* True if two bitmasks do overlap */ 504 int bitmask_intersects(const struct bitmask *bmp1, const struct bitmask *bmp2) 505 { 506 unsigned int i; 507 for (i = 0; i < bmp1->size; i++) 508 if (_getbit(bmp1, i) & _getbit(bmp2, i)) 509 return 1; 510 return 0; 511 } 512 513 /* 514 * Range operations 515 */ 516 517 /* Set bits of bitmask in specified range [i, j) */ 518 struct bitmask *bitmask_setrange(struct bitmask *bmp, 519 unsigned int i, unsigned int j) 520 { 521 unsigned int n; 522 for (n = i; n < j; n++) 523 _setbit(bmp, n, 1); 524 return bmp; 525 } 526 527 /* Clear bits of bitmask in specified range */ 528 struct bitmask *bitmask_clearrange(struct bitmask *bmp, 529 unsigned int i, unsigned int j) 530 { 531 unsigned int n; 532 for (n = i; n < j; n++) 533 _setbit(bmp, n, 0); 534 return bmp; 535 } 536 537 /* Clear all but specified range */ 538 struct bitmask *bitmask_keeprange(struct bitmask *bmp, 539 unsigned int i, unsigned int j) 540 { 541 bitmask_clearrange(bmp, 0, i); 542 bitmask_clearrange(bmp, j, bmp->size); 543 return bmp; 544 } 545 546 /* 547 * Unary operations: bmp1 = op(struct bitmask *bmp2) 548 */ 549 550 /* Complement: bmp1 = ~bmp2 */ 551 struct bitmask *bitmask_complement(struct bitmask *bmp1, 552 const struct bitmask *bmp2) 553 { 554 unsigned int i; 555 for (i = 0; i < bmp1->size; i++) 556 _setbit(bmp1, i, !_getbit(bmp2, i)); 557 return bmp1; 558 } 559 560 /* Right shift: bmp1 = bmp2 >> n */ 561 struct bitmask *bitmask_shiftright(struct bitmask *bmp1, 562 const struct bitmask *bmp2, unsigned int n) 563 { 564 unsigned int i; 565 for (i = 0; i < bmp1->size; i++) 566 _setbit(bmp1, i, _getbit(bmp2, i + n)); 567 return bmp1; 568 } 569 570 /* Left shift: bmp1 = bmp2 << n */ 571 struct bitmask *bitmask_shiftleft(struct bitmask *bmp1, 572 const struct bitmask *bmp2, unsigned int n) 573 { 574 int i; 575 for (i = bmp1->size - 1; i >= 0; i--) 576 _setbit(bmp1, i, _getbit(bmp2, i - n)); 577 return bmp1; 578 } 579 580 /* 581 * Binary operations: bmp1 = bmp2 op bmp3 582 */ 583 584 /* Logical `and` of two bitmasks: bmp1 = bmp2 & bmp3 */ 585 struct bitmask *bitmask_and(struct bitmask *bmp1, const struct bitmask *bmp2, 586 const struct bitmask *bmp3) 587 { 588 unsigned int i; 589 for (i = 0; i < bmp1->size; i++) 590 _setbit(bmp1, i, _getbit(bmp2, i) & _getbit(bmp3, i)); 591 return bmp1; 592 } 593 594 /* Logical `andnot` of two bitmasks: bmp1 = bmp2 & ~bmp3 */ 595 struct bitmask *bitmask_andnot(struct bitmask *bmp1, const struct bitmask *bmp2, 596 const struct bitmask *bmp3) 597 { 598 unsigned int i; 599 for (i = 0; i < bmp1->size; i++) 600 _setbit(bmp1, i, _getbit(bmp2, i) & ~_getbit(bmp3, i)); 601 return bmp1; 602 } 603 604 /* Logical `or` of two bitmasks: bmp1 = bmp2 | bmp3 */ 605 struct bitmask *bitmask_or(struct bitmask *bmp1, const struct bitmask *bmp2, 606 const struct bitmask *bmp3) 607 { 608 unsigned int i; 609 for (i = 0; i < bmp1->size; i++) 610 _setbit(bmp1, i, _getbit(bmp2, i) | _getbit(bmp3, i)); 611 return bmp1; 612 } 613 614 /* Logical `eor` of two bitmasks: bmp1 = bmp2 ^ bmp3 */ 615 struct bitmask *bitmask_eor(struct bitmask *bmp1, const struct bitmask *bmp2, 616 const struct bitmask *bmp3) 617 { 618 unsigned int i; 619 for (i = 0; i < bmp1->size; i++) 620 _setbit(bmp1, i, _getbit(bmp2, i) ^ _getbit(bmp3, i)); 621 return bmp1; 622 } 623 624 /* 625 * Iteration operators 626 */ 627 628 /* Number of lowest set bit (min) */ 629 unsigned int bitmask_first(const struct bitmask *bmp) 630 { 631 return bitmask_next(bmp, 0); 632 } 633 634 /* Number of next set bit at or above given bit i */ 635 unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i) 636 { 637 unsigned int n; 638 for (n = i; n < bmp->size; n++) 639 if (_getbit(bmp, n)) 640 break; 641 return n; 642 } 643 644 /* Absolute position of nth set bit */ 645 unsigned int bitmask_rel_to_abs_pos(const struct bitmask *bmp, unsigned int n) 646 { 647 unsigned int i; 648 for (i = 0; i < bmp->size; i++) 649 if (_getbit(bmp, i)) 650 if (n-- == 0) 651 break; 652 return i; 653 } 654 655 /* Relative position amongst set bits of bit n */ 656 unsigned int bitmask_abs_to_rel_pos(const struct bitmask *bmp, unsigned int n) 657 { 658 unsigned int i; 659 unsigned int w = 0; 660 661 if (!_getbit(bmp, n)) 662 return bmp->size; 663 /* Add in number bits set before bit n */ 664 for (i = 0; i < n; i++) 665 if (_getbit(bmp, i)) 666 w++; 667 return w; 668 } 669 670 /* Number of highest set bit (max) */ 671 unsigned int bitmask_last(const struct bitmask *bmp) 672 { 673 unsigned int i; 674 unsigned int m = bmp->size; 675 for (i = 0; i < bmp->size; i++) 676 if (_getbit(bmp, i)) 677 m = i; 678 return m; 679 } 680
