1 module tagion.utils.BitMask; 2 3 enum WORD_SIZE = size_t(size_t.sizeof * 8); 4 5 size_t bitsize(const size_t[] mask) pure nothrow @nogc @safe { 6 return mask.length * WORD_SIZE; 7 } 8 9 size_t wordindex(const size_t i) pure nothrow @nogc @safe { 10 return i / WORD_SIZE; 11 } 12 13 size_t word_bitindex(const size_t i) pure nothrow @nogc @safe { 14 return i % WORD_SIZE; 15 } 16 17 @safe 18 struct BitMask { 19 import std.algorithm; 20 import std.format; 21 import std.range; 22 import std.traits; 23 24 enum absolute_mask = 0x1000; 25 private size_t[] mask; 26 27 void opAssign(const BitMask rhs) pure nothrow { 28 mask = rhs.mask.dup; 29 } 30 31 /++ 32 This set the mask as bit stream with LSB first 33 +/ 34 this(T)(T bitstring) if (isSomeString!T) { 35 auto bitrange = bitstring.filter!((c) => (c == '0' || c == '1')).enumerate; 36 foreach (i, c; bitrange) { 37 if (c == '1') { 38 this[i] = true; 39 } 40 } 41 } 42 43 this(R)(scope R range) pure nothrow if ((isInputRange!R) && is(ElementType!R : bool)) { 44 this(range.enumerate 45 .filter!(b => b.value) 46 .map!(b => b.index)); 47 } 48 49 this(R)(scope R range) pure nothrow if ((isInputRange!R) && isIntegral!(ElementType!R) && !is(ElementType!R : bool)) { 50 range.each!((n) => this[n] = true); 51 } 52 53 BitMask dup() const pure nothrow { 54 BitMask result; 55 result.mask = mask.dup; 56 return result; 57 } 58 59 void clear() pure nothrow { 60 mask[] = 0; 61 } 62 63 @nogc 64 bool opEquals(const BitMask rhs) const pure nothrow { 65 import std.algorithm; 66 67 if (mask == rhs.mask) { 68 return true; 69 } 70 const min_length = min(mask.length, rhs.mask.length); 71 if (mask[0 .. min_length] == rhs.mask[0 .. min_length]) { 72 return mask.all!(q{a==0}) && rhs.mask.all!(q{a==0}); 73 74 } 75 return false; 76 } 77 78 unittest { 79 BitMask bits_a, bits_b; 80 assert(bits_a == bits_b); 81 bits_b.mask.length = 1; 82 assert(bits_a == bits_b); 83 bits_a[17] = true; 84 assert(bits_a != bits_b); 85 bits_b[17] = true; 86 assert(bits_a == bits_b); 87 bits_b[100] = true; 88 assert(bits_a != bits_b); 89 bits_a[100] = true; 90 assert(bits_a == bits_b); 91 BitMask all_null_bits; 92 all_null_bits.mask.length = 3; // long sequency of bits of value 93 assert(all_null_bits == BitMask.init); 94 assert(BitMask.init == all_null_bits); 95 } 96 97 Range opSlice() const pure nothrow { 98 return Range(mask); 99 } 100 101 unittest { 102 BitMask bits; 103 assert(bits[].empty); 104 bits[17] = true; 105 assert(equal(bits[], [17])); 106 bits[0] = true; 107 assert(equal(bits[], [0, 17])); 108 enum first_bit_in_the_next_word = 8 * size_t.sizeof; 109 enum last_bit_in_a_word = first_bit_in_the_next_word - 1; 110 bits[last_bit_in_a_word] = true; 111 assert(equal(bits[], [0, 17, last_bit_in_a_word])); 112 bits[first_bit_in_the_next_word] = true; 113 assert(equal(bits[], [0, 17, last_bit_in_a_word, first_bit_in_the_next_word])); 114 } 115 116 @nogc 117 struct Range { 118 private { 119 const(size_t[]) mask; 120 size_t index; 121 size_t bit_pos; 122 } 123 124 private this( 125 const(size_t[]) mask, 126 size_t index, 127 size_t bit_pos) pure nothrow { 128 this.mask = mask; 129 this.index = index; 130 this.bit_pos = bit_pos; 131 } 132 133 this(const size_t[] mask) pure nothrow { 134 this.mask = mask; 135 if (mask.length && (mask[0] & 0x1) is 0) { 136 popFront; 137 } 138 } 139 140 static size_t pos(size_t BIT_SIZE = WORD_SIZE)(const size_t x, const size_t index = 0) pure nothrow { 141 static if (BIT_SIZE is 1) { 142 return (x) ? index : WORD_SIZE; 143 } 144 else { 145 enum HALF_SIZE = BIT_SIZE >> 1; 146 enum MASK = (size_t(1) << HALF_SIZE) - size_t(1); 147 if (x & MASK) { 148 return pos!HALF_SIZE(x & MASK, index); 149 } 150 else { 151 return pos!HALF_SIZE(x >> HALF_SIZE, index + HALF_SIZE); 152 } 153 } 154 } 155 156 static unittest { 157 assert(pos(0b1) is 0); 158 assert(pos(0b10) is 1); 159 assert(pos(0b1000_0000_0000) is 11); 160 assert(pos(0) is WORD_SIZE); 161 enum small_pos = (WORD_SIZE >> 1) + 5; 162 enum larger_pos = small_pos + 7; 163 enum small_val = size_t(1) << small_pos; 164 enum larger_val = size_t(1) << larger_pos; 165 assert(pos(small_val | larger_val) is small_pos); 166 } 167 168 pure nothrow { 169 const { 170 size_t rest() { 171 return (bit_pos < WORD_SIZE - 1) ? ( 172 mask[index] & ~((size_t(1) << (bit_pos + 1)) - 1)) : 0; 173 } 174 175 bool empty() { 176 return index >= mask.length; 177 } 178 179 size_t front() { 180 return index * WORD_SIZE + bit_pos; 181 } 182 } 183 void popFront() { 184 if (!empty) { 185 bit_pos = pos(rest); 186 if (bit_pos >= WORD_SIZE) { 187 bit_pos = 0; 188 index++; 189 if (index < mask.length && ((mask[index] & 0x1) is 0)) { 190 popFront; 191 } 192 } 193 } 194 } 195 196 Range save() { 197 return Range(mask, index, bit_pos); 198 } 199 } 200 } 201 202 bool opIndex(size_t i) const pure nothrow @nogc 203 in { 204 assert(i < absolute_mask); 205 } 206 do { 207 if (i < mask.bitsize) { 208 return (mask[i.wordindex] & (size_t(1) << i.word_bitindex)) != 0; 209 } 210 return false; 211 } 212 213 bool opIndexAssign(const bool b, const size_t i) pure nothrow 214 in { 215 assert(i < absolute_mask); 216 } 217 do { 218 if (i >= mask.bitsize) { 219 mask.length = i.wordindex + 1; 220 } 221 if (b) { 222 mask[i.wordindex] |= size_t(1) << i.word_bitindex; 223 } 224 else { 225 mask[i.wordindex] &= ~(size_t(1) << i.word_bitindex); 226 } 227 return b; 228 } 229 230 unittest { 231 BitMask bits; 232 assert(!bits[100]); 233 bits[100] = true; 234 assert(bits[100]); 235 bits[100] = false; 236 assert(!bits[100]); 237 } 238 239 BitMask opUnary(string op)() const pure nothrow 240 if (op == "~") { 241 BitMask result; 242 result.mask = new size_t[mask.length]; 243 result.mask[] = ~mask[]; 244 return result; 245 } 246 247 @trusted 248 unittest { 249 BitMask bits; 250 assert(~bits == BitMask.init); 251 bits.mask.length = 1; 252 const all_bits = BitMask('1'.repeat(8 * size_t.sizeof).array); 253 assert(~bits == all_bits); 254 BitMask expected = all_bits.dup; 255 expected[7] = false; 256 assert(~bits != expected); 257 bits[7] = true; 258 assert(~bits == expected); 259 260 } 261 262 BitMask opBinary(string op)(scope const BitMask rhs) const pure nothrow 263 if (op == "-" || op == "&" || op == "|" || op == "^") { 264 import std.algorithm.comparison : max, min; 265 266 BitMask result; 267 result.mask = mask.dup; 268 result.opOpAssign!op(rhs); 269 return result; 270 } 271 272 version (unittest) { 273 import std.array; 274 import std.stdio; 275 import tagion.basic.Debug; 276 277 /// Result table 278 /// 279 } 280 281 unittest { // opBinary and opOpAssign 282 283 BitMask bits_a, bits_b; 284 enum op_list = ["|", "&", "^", "-"]; 285 //enum righ 286 static struct Expected { 287 BitMask Y, A, B; /// y = a OP b 288 } 289 290 const left_one_right_none = [ 291 "|": Expected(BitMask("010101"), BitMask("010101"), BitMask.init), 292 "&": Expected(BitMask("000000"), BitMask("010101"), BitMask.init), 293 "^": Expected(BitMask("010101"), BitMask("010101"), BitMask.init), 294 "-": Expected(BitMask("010101"), BitMask("010101"), BitMask.init), 295 ]; 296 const left_one_right_one = [ 297 "|": Expected(BitMask("010111001"), BitMask("010101001"), BitMask("0101110")), 298 "&": Expected(BitMask("010001"), BitMask("010101"), BitMask("0100010")), 299 "^": Expected(BitMask("00110001"), BitMask("000101"), BitMask("00100101")), 300 "-": Expected(BitMask("0000101"), BitMask("000010111"), BitMask("01010101111")), 301 ]; 302 303 const left_more_right_more = [ 304 "|": Expected(BitMask([1, 57, 100]), BitMask([57]), BitMask([100, 1])), 305 "&": Expected(BitMask([57, 101]), BitMask([1, 57, 101, 65]), BitMask([101, 57, 22])), 306 "^": Expected(BitMask([1, 2, 57, 100]), BitMask([2, 57, 100, 65]), BitMask([1, 65])), 307 "-": Expected(BitMask([2, 100]), BitMask([2, 57, 100, 65]), BitMask([67, 57, 65])), 308 ]; 309 310 static foreach (OP; op_list) { 311 assert(bits_a.opBinary!OP(bits_b) == BitMask.init); 312 { 313 foreach (test; only(left_one_right_none, left_one_right_one, left_more_right_more)) { 314 const expected = test[OP]; 315 with (expected) { 316 const result = A.opBinary!OP(B); 317 assert(result == Y, 318 __format("%.16s == %.16s %s %.16s result %.16s", Y, A, OP, B, result)); 319 } 320 with (expected) { 321 auto result = A.dup; 322 result.opOpAssign!OP(B); 323 324 assert(result == Y, 325 __format("%.16s == (%.16s %s= %.16s) result %.16s", Y, A, OP, B, result)); 326 327 } 328 329 } 330 } 331 } 332 } 333 334 BitMask opOpAssign(string op)(scope const BitMask rhs) pure nothrow 335 if (op == "-" || op == "&" || op == "|" || op == "^") { 336 if (mask.length > rhs.mask.length) { 337 switch (op) { 338 case "&": 339 mask[rhs.mask.length .. $] = 0; 340 break; 341 default: 342 } 343 } 344 else if (mask.length < rhs.mask.length) { 345 mask.length = rhs.mask.length; 346 } 347 348 static if (op == "-") { 349 mask[0 .. rhs.mask.length] &= ~rhs.mask[0 .. rhs.mask.length]; 350 } 351 else { 352 enum code = format(q{mask[0..rhs.mask.length] %s= rhs.mask[0..rhs.mask.length];}, op); 353 mixin(code); 354 } 355 return this; 356 } 357 358 BitMask opBinary(string op, Index)(const Index index) const pure nothrow 359 if ((op == "-" || op == "+") && isIntegral!Index) { 360 BitMask result = dup; 361 result[index] = (op == "+"); 362 return result; 363 } 364 365 unittest { 366 BitMask bits; 367 assert(bits + 17 == BitMask([17])); 368 bits = BitMask([42, 17]); 369 assert(bits + 100 == BitMask([17, 100, 42])); 370 assert(bits - 17 == BitMask([42])); 371 } 372 373 void chunk(size_t bit_len) pure nothrow { 374 const new_size = bit_len.wordindex + 1; 375 if (new_size < mask.length) { 376 mask.length = new_size; 377 } 378 const chunk_mask = ((size_t(1) << (bit_len.word_bitindex)) - 1); 379 mask[$ - 1] &= chunk_mask; 380 } 381 382 unittest { 383 BitMask bits = BitMask([17, 42, 99, 101]); 384 bits.chunk(100); 385 assert(equal(bits[], [17, 42, 99])); 386 bits.chunk(99); 387 assert(equal(bits[], [17, 42])); 388 } 389 390 size_t count() const pure nothrow @nogc { 391 import core.bitop : popcnt; 392 393 return mask.map!(m => m.popcnt).sum; 394 } 395 396 unittest { 397 BitMask bits; 398 assert(bits.count == 0); 399 bits[17] = true; 400 assert(bits.count == 1); 401 bits = ~bits; 402 assert(bits.count == WORD_SIZE - 1); 403 bits[WORD_SIZE * 3 / 2] = true; 404 assert(bits.count == WORD_SIZE); 405 bits[WORD_SIZE / 2] = false; 406 bits = ~bits; 407 assert(bits.count == WORD_SIZE + 1); 408 } 409 410 void toString(scope void delegate(scope const(char)[]) @safe sink, 411 const FormatSpec!char fmt) const { 412 enum separator = '_'; 413 import std.stdio; 414 415 @nogc @safe struct BitRange { 416 size_t index; 417 const size_t width; 418 const(size_t[]) mask; 419 this(const BitMask bitmask, const size_t width) { 420 mask = bitmask.mask; 421 this.width = (width is 0) ? mask.bitsize : width; 422 } 423 424 pure nothrow { 425 char front() const { 426 const word_index = index.wordindex; 427 if (word_index < mask.length) { 428 return (mask[word_index] & (size_t(1) << (index.word_bitindex))) ? '1' : '0'; 429 } 430 return '0'; 431 } 432 433 bool empty() const { 434 return index >= width; 435 } 436 437 void popFront() { 438 index++; 439 } 440 } 441 } 442 443 switch (fmt.spec) { 444 case 's': 445 auto bit_range = BitRange(this, fmt.width); 446 scope char[] str; 447 auto max_size = bit_range.width + (bit_range.width) / fmt.precision + 1; 448 str.length = max_size; 449 size_t index; 450 size_t sep_count; 451 while (!bit_range.empty) { 452 str[index++] = bit_range.front; 453 bit_range.popFront; 454 if (fmt.precision !is 0 && !bit_range.empty) { 455 sep_count++; 456 if ((sep_count % fmt.precision) is 0) { 457 str[index++] = separator; 458 } 459 } 460 } 461 sink(str[0 .. index]); 462 break; 463 default: 464 assert(0, "Unknown format specifier: %" ~ fmt.spec); 465 } 466 } 467 468 @trusted 469 unittest { 470 { 471 auto bits = BitMask("0101_1"); 472 assert(format("%16.8s", bits) == "01011000_00000000"); 473 assert(format("%16.4s", bits) == "0101_1000_0000_0000"); 474 assert(format("%7.3s", bits) == "010_110_0"); 475 } 476 477 { 478 BitMask bits; 479 bits[64] = true; 480 assert(format("%.16s", bits) == 481 "0000000000000000_0000000000000000_0000000000000000_0000000000000000_1000000000000000_0000000000000000_0000000000000000_0000000000000000"); 482 bits[17] = true; 483 bits[78] = true; 484 bits[64] = false; 485 assert(format("%.16s", bits) == 486 "0000000000000000_0100000000000000_0000000000000000_0000000000000000_0000000000000010_0000000000000000_0000000000000000_0000000000000000"); 487 } 488 489 { 490 const a = BitMask("1000_1100_1100"); 491 const b = BitMask("0010_1001_0101"); 492 { // bit or 493 const y = a | b; 494 assert(format("%16.4s", y) == "1010_1101_1101_0000"); 495 assert(y.count is 8); 496 } 497 498 { // bit and 499 const y = a & b; 500 assert(format("%16.4s", y) == "0000_1000_0100_0000"); 501 assert(y.count is 2); 502 } 503 504 { // bit xor 505 const y = a ^ b; 506 assert(format("%16.4s", y) == "1010_0101_1001_0000"); 507 assert(y.count is 6); 508 } 509 510 { // bit and not 511 const y = a - b; 512 assert(format("%16.4s", y) == "1000_0100_1000_0000"); 513 assert(y.count is 3); 514 } 515 516 version (BITMASK) { 517 BitMask null_mask; 518 const y = a - null_mask; 519 assert(y == a); 520 } 521 522 { 523 auto y = a.dup; 524 y |= b; 525 assert(format("%16.4s", y) == "1010_1101_1101_0000"); 526 assert(y.count is 8); 527 528 } 529 530 { // bit and 531 auto y = a.dup; 532 y &= b; 533 assert(format("%16.4s", y) == "0000_1000_0100_0000"); 534 assert(y.count is 2); 535 536 } 537 538 { // bit xor 539 auto y = a.dup; 540 y ^= b; 541 assert(format("%16.4s", y) == "1010_0101_1001_0000"); 542 assert(y.count is 6); 543 } 544 545 { // bit and not 546 auto y = a.dup; 547 y -= b; 548 assert(format("%16.4s", y) == "1000_0100_1000_0000"); 549 assert(y.count is 3); 550 } 551 552 { // Not and chunk 553 auto y = ~a; 554 assert(format("%32.4s", y) == "0111_0011_0011_1111_1111_1111_1111_1111"); 555 y.chunk(16); 556 assert(format("%32.4s", y) == "0111_0011_0011_1111_0000_0000_0000_0000"); 557 assert(y.count is 11); 558 } 559 } 560 561 } 562 563 unittest { 564 import std.algorithm : equal; 565 import std.algorithm.iteration : fold, uniq; 566 import std.algorithm.sorting : merge, sort; 567 import std.stdio; 568 569 { // Bit assign 570 BitMask a; 571 assert(!a[42]); 572 assert(!a[17]); 573 assert(!a[0]); 574 a[42] = true; 575 assert(a[42]); 576 assert(!a[17]); 577 assert(!a[0]); 578 a[0] = true; 579 assert(a[42]); 580 assert(!a[17]); 581 assert(a[0]); 582 a[17] = true; 583 assert(a[42]); 584 assert(a[17]); 585 assert(a[0]); 586 587 } 588 589 { // Range 590 const bit_list = [17, 52, 53, 54, 75, 28, 101]; 591 { // Empty Range 592 BitMask a; 593 assert(a[].empty); 594 size_t[] a_empty; 595 assert(equal(a[], a_empty)); 596 } 597 598 { // First element 599 BitMask a; 600 a[0] = true; 601 auto range = a[]; 602 assert(range.front is 0); 603 assert(!range.empty); 604 range.popFront; 605 assert(range.empty); 606 assert(equal(a[], [0])); 607 } 608 609 { // One element 610 BitMask a; 611 a[2] = true; 612 assert(equal(a[], [2])); 613 } 614 615 { // One element at the end of a word 616 BitMask a; 617 a[63] = true; 618 assert(equal(a[], [63])); 619 } 620 621 { // One element at the begin of the next word 622 BitMask a; 623 a[64] = true; 624 assert(equal(a[], [64])); 625 } 626 627 { // elements at the end and begin of a word 628 BitMask a; 629 a[63] = true; 630 a[64] = true; 631 assert(equal(a[], [63, 64])); 632 } 633 634 { // Simple range test 635 auto a = BitMask(bit_list); 636 assert(equal(a[], bit_list.dup.sort)); 637 } 638 } 639 640 void and_filter(ref BitMask result, Range a, Range b) @safe { 641 if (a.front < b.front) { 642 a.popFront; 643 } 644 else if (a.front > b.front) { 645 b.popFront; 646 } 647 else { 648 if (a.empty) { 649 return; 650 } 651 result[b.front] = true; 652 a.popFront; 653 b.popFront; 654 } 655 and_filter(result, a, b); 656 } 657 658 void xor_filter(ref BitMask result, Range a, Range b) @safe { 659 if (a.front < b.front) { 660 result[a.front] = true; 661 a.popFront; 662 } 663 else if (a.front > b.front) { 664 result[b.front] = true; 665 b.popFront; 666 } 667 else { 668 if (a.empty) { 669 return; 670 } 671 //result[b.front]=true; 672 a.popFront; 673 b.popFront; 674 } 675 and_filter(result, a, b); 676 } 677 678 { // Check BitMask with mask.length > 1 679 const a_list = [17, 52, 53, 54, 75, 28, 101]; 680 const a = BitMask(a_list); 681 const b_list = [17, 52, 54, 76, 28, 101, 102, 103]; 682 const b = BitMask(b_list); 683 684 { // Or 685 const y = a | b; 686 auto y_list = (a_list ~ b_list).dup.sort.uniq; //uniq;//.dup.sort; 687 assert(equal(y[], y_list)); 688 assert(y.count is 10); 689 } 690 691 { // And 692 const y = a & b; 693 BitMask result; 694 and_filter(result, a[], b[]); 695 assert(result == y); 696 assert(y.count is 5); 697 } 698 699 { // Xor 700 const y = a ^ b; 701 const result = ~a & b | a & ~b; 702 assert(result == y); 703 assert(y.count is 5); 704 } 705 706 { // and not 707 const y = a - b; 708 const result = a & ~b; 709 assert(result == y); 710 assert(y.count is 2); 711 } 712 713 { // Empty Or= 714 BitMask y; 715 y |= a; 716 assert(y == a); 717 assert(a.count is y.count); 718 } 719 720 { // Or 721 auto y = a.dup; 722 y |= b; 723 auto y_list = (a_list ~ b_list).dup.sort.uniq; 724 assert(equal(y[], y_list)); 725 assert(y.count is 10); 726 } 727 728 { // And 729 auto y = a.dup; 730 y &= b; 731 BitMask result; 732 and_filter(result, a[], b[]); 733 assert(result == y); 734 assert(y.count is 5); 735 } 736 737 { // Xor 738 auto y = a.dup; 739 y ^= b; 740 //const y= a ^ b; 741 const result = ~a & b | a & ~b; 742 assert(result == y); 743 assert(y.count is 5); 744 } 745 746 { // and not 747 auto y = a.dup; 748 y -= b; 749 750 //const y= a - b; 751 const result = a & ~b; 752 assert(result == y); 753 assert(y.count is 2); 754 } 755 } 756 757 { // Duplicate on assign 758 BitMask z; 759 auto y = z; 760 z[3] = true; 761 assert(equal(z[], [3])); 762 assert(y[].empty); 763 y = z; 764 z[5] = true; 765 assert(equal(z[], [3, 5])); 766 assert(equal(y[], [3])); 767 } 768 769 } 770 }