1 // Written in the D programming language. 2 3 /** 4 Bit-level manipulation facilities. 5 6 $(SCRIPT inhibitQuickIndex = 1;) 7 $(DIVC quickindex, 8 $(BOOKTABLE, 9 $(TR $(TH Category) $(TH Functions)) 10 $(TR $(TD Bit constructs) $(TD 11 $(LREF BitArray) 12 $(LREF bitfields) 13 $(LREF bitsSet) 14 )) 15 $(TR $(TD Endianness conversion) $(TD 16 $(LREF bigEndianToNative) 17 $(LREF littleEndianToNative) 18 $(LREF nativeToBigEndian) 19 $(LREF nativeToLittleEndian) 20 $(LREF swapEndian) 21 )) 22 $(TR $(TD Integral ranges) $(TD 23 $(LREF append) 24 $(LREF peek) 25 $(LREF read) 26 $(LREF write) 27 )) 28 $(TR $(TD Floating-Point manipulation) $(TD 29 $(LREF DoubleRep) 30 $(LREF FloatRep) 31 )) 32 $(TR $(TD Tagging) $(TD 33 $(LREF taggedClassRef) 34 $(LREF taggedPointer) 35 )) 36 )) 37 38 Copyright: Copyright The D Language Foundation 2007 - 2011. 39 License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0). 40 Authors: $(HTTP digitalmars.com, Walter Bright), 41 $(HTTP erdani.org, Andrei Alexandrescu), 42 $(HTTP jmdavisprog.com, Jonathan M Davis), 43 Alex Rønne Petersen, 44 Damian Ziemba, 45 Amaury SECHET 46 Source: $(PHOBOSSRC std/bitmanip.d) 47 */ 48 /* 49 Copyright The D Language Foundation 2007 - 2012. 50 Distributed under the Boost Software License, Version 1.0. 51 (See accompanying file LICENSE_1_0.txt or copy at 52 http://www.boost.org/LICENSE_1_0.txt) 53 */ 54 module std.bitmanip; 55 56 import std.range.primitives; 57 public import std.system : Endian; 58 import std.traits; 59 60 private string myToString(ulong n) pure @safe 61 { 62 import core.internal..string : UnsignedStringBuf, unsignedToTempString; 63 UnsignedStringBuf buf; 64 auto s = unsignedToTempString(n, buf); 65 // pure allows implicit cast to string 66 return s ~ (n > uint.max ? "UL" : "U"); 67 } 68 69 @safe pure unittest 70 { 71 assert(myToString(5) == "5U"); 72 assert(myToString(uint.max) == "4294967295U"); 73 assert(myToString(uint.max + 1UL) == "4294967296UL"); 74 } 75 76 77 private template createAccessors( 78 string store, T, string name, size_t len, size_t offset) 79 { 80 static if (!name.length) 81 { 82 // No need to create any accessor 83 enum result = ""; 84 } 85 else static if (len == 0) 86 { 87 // Fields of length 0 are always zero 88 enum result = "enum "~T.stringof~" "~name~" = 0;\n"; 89 } 90 else 91 { 92 enum ulong 93 maskAllElse = ((~0uL) >> (64 - len)) << offset, 94 signBitCheck = 1uL << (len - 1); 95 96 static if (T.min < 0) 97 { 98 enum long minVal = -(1uL << (len - 1)); 99 enum ulong maxVal = (1uL << (len - 1)) - 1; 100 alias UT = Unsigned!(T); 101 enum UT extendSign = cast(UT)~((~0uL) >> (64 - len)); 102 } 103 else 104 { 105 enum ulong minVal = 0; 106 enum ulong maxVal = (~0uL) >> (64 - len); 107 enum extendSign = 0; 108 } 109 110 static if (is(T == bool)) 111 { 112 static assert(len == 1, "`" ~ name ~ 113 "` definition problem: type `bool` is only allowed for single-bit fields"); 114 enum result = 115 // getter 116 "@property bool " ~ name ~ "() @safe pure nothrow @nogc const { return " 117 ~"("~store~" & "~myToString(maskAllElse)~") != 0;}\n" 118 // setter 119 ~"@property void " ~ name ~ "(bool v) @safe pure nothrow @nogc { " 120 ~"if (v) "~store~" |= "~myToString(maskAllElse)~";" 121 ~"else "~store~" &= cast(typeof("~store~"))(-1-cast(typeof("~store~"))"~myToString(maskAllElse)~");}\n"; 122 } 123 else 124 { 125 // getter 126 enum result = "@property "~T.stringof~" "~name~"() @safe pure nothrow @nogc const { auto result = " 127 ~"("~store~" & " 128 ~ myToString(maskAllElse) ~ ") >>" 129 ~ myToString(offset) ~ ";" 130 ~ (T.min < 0 131 ? "if (result >= " ~ myToString(signBitCheck) 132 ~ ") result |= " ~ myToString(extendSign) ~ ";" 133 : "") 134 ~ " return cast("~T.stringof~") result;}\n" 135 // setter 136 ~"@property void "~name~"("~T.stringof~" v) @safe pure nothrow @nogc { " 137 ~"assert(v >= "~name~`_min, "Value is smaller than the minimum value of bitfield '`~name~`'"); ` 138 ~"assert(v <= "~name~`_max, "Value is greater than the maximum value of bitfield '`~name~`'"); ` 139 ~store~" = cast(typeof("~store~"))" 140 ~" (("~store~" & (-1-cast(typeof("~store~"))"~myToString(maskAllElse)~"))" 141 ~" | ((cast(typeof("~store~")) v << "~myToString(offset)~")" 142 ~" & "~myToString(maskAllElse)~"));}\n" 143 // constants 144 ~"enum "~T.stringof~" "~name~"_min = cast("~T.stringof~")" 145 ~myToString(minVal)~"; " 146 ~" enum "~T.stringof~" "~name~"_max = cast("~T.stringof~")" 147 ~myToString(maxVal)~"; "; 148 } 149 } 150 } 151 152 private template createStoreName(Ts...) 153 { 154 static if (Ts.length < 2) 155 enum createStoreName = ""; 156 else 157 enum createStoreName = "_" ~ Ts[1] ~ createStoreName!(Ts[3 .. $]); 158 } 159 160 private template createStorageAndFields(Ts...) 161 { 162 enum Name = createStoreName!Ts; 163 enum Size = sizeOfBitField!Ts; 164 static if (Size == ubyte.sizeof * 8) 165 alias StoreType = ubyte; 166 else static if (Size == ushort.sizeof * 8) 167 alias StoreType = ushort; 168 else static if (Size == uint.sizeof * 8) 169 alias StoreType = uint; 170 else static if (Size == ulong.sizeof * 8) 171 alias StoreType = ulong; 172 else 173 { 174 static assert(false, "Field widths must sum to 8, 16, 32, or 64"); 175 alias StoreType = ulong; // just to avoid another error msg 176 } 177 enum result 178 = "private " ~ StoreType.stringof ~ " " ~ Name ~ ";" 179 ~ createFields!(Name, 0, Ts).result; 180 } 181 182 private template createFields(string store, size_t offset, Ts...) 183 { 184 static if (Ts.length > 0) 185 enum result 186 = createAccessors!(store, Ts[0], Ts[1], Ts[2], offset).result 187 ~ createFields!(store, offset + Ts[2], Ts[3 .. $]).result; 188 else 189 enum result = ""; 190 } 191 192 private ulong getBitsForAlign(ulong a) 193 { 194 ulong bits = 0; 195 while ((a & 0x01) == 0) 196 { 197 bits++; 198 a >>= 1; 199 } 200 201 assert(a == 1, "alignment is not a power of 2"); 202 return bits; 203 } 204 205 private template createReferenceAccessor(string store, T, ulong bits, string name) 206 { 207 enum storage = "private void* " ~ store ~ "_ptr;\n"; 208 enum storage_accessor = "@property ref size_t " ~ store ~ "() return @trusted pure nothrow @nogc const { " 209 ~ "return *cast(size_t*) &" ~ store ~ "_ptr;}\n" 210 ~ "@property void " ~ store ~ "(size_t v) @trusted pure nothrow @nogc { " 211 ~ "" ~ store ~ "_ptr = cast(void*) v;}\n"; 212 213 enum mask = (1UL << bits) - 1; 214 // getter 215 enum ref_accessor = "@property "~T.stringof~" "~name~"() @trusted pure nothrow @nogc const { auto result = " 216 ~ "("~store~" & "~myToString(~mask)~"); " 217 ~ "return cast("~T.stringof~") cast(void*) result;}\n" 218 // setter 219 ~"@property void "~name~"("~T.stringof~" v) @trusted pure nothrow @nogc { " 220 ~"assert(((cast(typeof("~store~")) cast(void*) v) & "~myToString(mask) 221 ~`) == 0, "Value not properly aligned for '`~name~`'"); ` 222 ~store~" = cast(typeof("~store~"))" 223 ~" (("~store~" & (cast(typeof("~store~")) "~myToString(mask)~"))" 224 ~" | ((cast(typeof("~store~")) cast(void*) v) & (cast(typeof("~store~")) "~myToString(~mask)~")));}\n"; 225 226 enum result = storage ~ storage_accessor ~ ref_accessor; 227 } 228 229 private template sizeOfBitField(T...) 230 { 231 static if (T.length < 2) 232 enum sizeOfBitField = 0; 233 else 234 enum sizeOfBitField = T[2] + sizeOfBitField!(T[3 .. $]); 235 } 236 237 private template createTaggedReference(T, ulong a, string name, Ts...) 238 { 239 static assert( 240 sizeOfBitField!Ts <= getBitsForAlign(a), 241 "Fields must fit in the bits know to be zero because of alignment." 242 ); 243 enum StoreName = createStoreName!(T, name, 0, Ts); 244 enum result 245 = createReferenceAccessor!(StoreName, T, sizeOfBitField!Ts, name).result 246 ~ createFields!(StoreName, 0, Ts, size_t, "", T.sizeof * 8 - sizeOfBitField!Ts).result; 247 } 248 249 /** 250 Allows creating bit fields inside $(D_PARAM struct)s and $(D_PARAM 251 class)es. 252 253 The type of a bit field can be any integral type or enumerated 254 type. The most efficient type to store in bitfields is $(D_PARAM 255 bool), followed by unsigned types, followed by signed types. 256 257 See_Also: $(REF BitFlags, std,typecons) 258 */ 259 260 template bitfields(T...) 261 { 262 enum { bitfields = createStorageAndFields!T.result } 263 } 264 265 /** 266 Create a bitfield pack of eight bits, which fit in 267 one $(D_PARAM ubyte). The bitfields are allocated starting from the 268 least significant bit, i.e. x occupies the two least significant bits 269 of the bitfields storage. 270 */ 271 @safe unittest 272 { 273 struct A 274 { 275 int a; 276 mixin(bitfields!( 277 uint, "x", 2, 278 int, "y", 3, 279 uint, "z", 2, 280 bool, "flag", 1)); 281 } 282 283 A obj; 284 obj.x = 2; 285 obj.z = obj.x; 286 287 assert(obj.x == 2); 288 assert(obj.y == 0); 289 assert(obj.z == 2); 290 assert(obj.flag == false); 291 } 292 293 /** 294 The sum of all bit lengths in one $(D_PARAM bitfield) instantiation 295 must be exactly 8, 16, 32, or 64. If padding is needed, just allocate 296 one bitfield with an empty name. 297 */ 298 @safe unittest 299 { 300 struct A 301 { 302 mixin(bitfields!( 303 bool, "flag1", 1, 304 bool, "flag2", 1, 305 uint, "", 6)); 306 } 307 308 A a; 309 assert(a.flag1 == 0); 310 a.flag1 = 1; 311 assert(a.flag1 == 1); 312 a.flag1 = 0; 313 assert(a.flag1 == 0); 314 } 315 316 /// enums can be used too 317 @safe unittest 318 { 319 enum ABC { A, B, C } 320 struct EnumTest 321 { 322 mixin(bitfields!( 323 ABC, "x", 2, 324 bool, "y", 1, 325 ubyte, "z", 5)); 326 } 327 } 328 329 /** 330 This string mixin generator allows one to create tagged pointers inside $(D_PARAM struct)s and $(D_PARAM class)es. 331 332 A tagged pointer uses the bits known to be zero in a normal pointer or class reference to store extra information. 333 For example, a pointer to an integer must be 4-byte aligned, so there are 2 bits that are always known to be zero. 334 One can store a 2-bit integer there. 335 336 The example above creates a tagged pointer in the struct A. The pointer is of type 337 `uint*` as specified by the first argument, and is named x, as specified by the second 338 argument. 339 340 Following arguments works the same way as `bitfield`'s. The bitfield must fit into the 341 bits known to be zero because of the pointer alignment. 342 */ 343 344 template taggedPointer(T : T*, string name, Ts...) { 345 enum taggedPointer = createTaggedReference!(T*, T.alignof, name, Ts).result; 346 } 347 348 /// 349 @safe unittest 350 { 351 struct A 352 { 353 int a; 354 mixin(taggedPointer!( 355 uint*, "x", 356 bool, "b1", 1, 357 bool, "b2", 1)); 358 } 359 A obj; 360 obj.x = new uint; 361 obj.b1 = true; 362 obj.b2 = false; 363 } 364 365 /** 366 This string mixin generator allows one to create tagged class reference inside $(D_PARAM struct)s and $(D_PARAM class)es. 367 368 A tagged class reference uses the bits known to be zero in a normal class reference to store extra information. 369 For example, a pointer to an integer must be 4-byte aligned, so there are 2 bits that are always known to be zero. 370 One can store a 2-bit integer there. 371 372 The example above creates a tagged reference to an Object in the struct A. This expects the same parameters 373 as `taggedPointer`, except the first argument which must be a class type instead of a pointer type. 374 */ 375 376 template taggedClassRef(T, string name, Ts...) 377 if (is(T == class)) 378 { 379 enum taggedClassRef = createTaggedReference!(T, 8, name, Ts).result; 380 } 381 382 /// 383 @safe unittest 384 { 385 struct A 386 { 387 int a; 388 mixin(taggedClassRef!( 389 Object, "o", 390 uint, "i", 2)); 391 } 392 A obj; 393 obj.o = new Object(); 394 obj.i = 3; 395 } 396 397 @safe pure nothrow @nogc 398 unittest 399 { 400 // Degenerate bitfields tests mixed with range tests 401 // https://issues.dlang.org/show_bug.cgi?id=8474 402 // https://issues.dlang.org/show_bug.cgi?id=11160 403 struct Test1 404 { 405 mixin(bitfields!(uint, "a", 32, 406 uint, "b", 4, 407 uint, "c", 4, 408 uint, "d", 8, 409 uint, "e", 16,)); 410 411 static assert(Test1.b_min == 0); 412 static assert(Test1.b_max == 15); 413 } 414 415 struct Test2 416 { 417 mixin(bitfields!(bool, "a", 0, 418 ulong, "b", 64)); 419 420 static assert(Test2.b_min == ulong.min); 421 static assert(Test2.b_max == ulong.max); 422 } 423 424 struct Test1b 425 { 426 mixin(bitfields!(bool, "a", 0, 427 int, "b", 8)); 428 } 429 430 struct Test2b 431 { 432 mixin(bitfields!(int, "a", 32, 433 int, "b", 4, 434 int, "c", 4, 435 int, "d", 8, 436 int, "e", 16,)); 437 438 static assert(Test2b.b_min == -8); 439 static assert(Test2b.b_max == 7); 440 } 441 442 struct Test3b 443 { 444 mixin(bitfields!(bool, "a", 0, 445 long, "b", 64)); 446 447 static assert(Test3b.b_min == long.min); 448 static assert(Test3b.b_max == long.max); 449 } 450 451 struct Test4b 452 { 453 mixin(bitfields!(long, "a", 32, 454 int, "b", 32)); 455 } 456 457 // Sign extension tests 458 Test2b t2b; 459 Test4b t4b; 460 t2b.b = -5; assert(t2b.b == -5); 461 t2b.d = -5; assert(t2b.d == -5); 462 t2b.e = -5; assert(t2b.e == -5); 463 t4b.a = -5; assert(t4b.a == -5L); 464 } 465 466 @system unittest 467 { 468 struct Test5 469 { 470 mixin(taggedPointer!( 471 int*, "a", 472 uint, "b", 2)); 473 } 474 475 Test5 t5; 476 t5.a = null; 477 t5.b = 3; 478 assert(t5.a is null); 479 assert(t5.b == 3); 480 481 int myint = 42; 482 t5.a = &myint; 483 assert(t5.a is &myint); 484 assert(t5.b == 3); 485 486 struct Test6 487 { 488 mixin(taggedClassRef!( 489 Object, "o", 490 bool, "b", 1)); 491 } 492 493 Test6 t6; 494 t6.o = null; 495 t6.b = false; 496 assert(t6.o is null); 497 assert(t6.b == false); 498 499 auto o = new Object(); 500 t6.o = o; 501 t6.b = true; 502 assert(t6.o is o); 503 assert(t6.b == true); 504 } 505 506 @safe unittest 507 { 508 static assert(!__traits(compiles, 509 taggedPointer!( 510 int*, "a", 511 uint, "b", 3))); 512 513 static assert(!__traits(compiles, 514 taggedClassRef!( 515 Object, "a", 516 uint, "b", 4))); 517 518 struct S { 519 mixin(taggedClassRef!( 520 Object, "a", 521 bool, "b", 1)); 522 } 523 524 const S s; 525 void bar(S s) {} 526 527 static assert(!__traits(compiles, bar(s))); 528 } 529 530 // https://issues.dlang.org/show_bug.cgi?id=6686 531 @safe unittest 532 { 533 union S { 534 ulong bits = ulong.max; 535 mixin (bitfields!( 536 ulong, "back", 31, 537 ulong, "front", 33) 538 ); 539 } 540 S num; 541 542 num.bits = ulong.max; 543 num.back = 1; 544 assert(num.bits == 0xFFFF_FFFF_8000_0001uL); 545 } 546 547 // https://issues.dlang.org/show_bug.cgi?id=5942 548 @safe unittest 549 { 550 struct S 551 { 552 mixin(bitfields!( 553 int, "a" , 32, 554 int, "b" , 32 555 )); 556 } 557 558 S data; 559 data.b = 42; 560 data.a = 1; 561 assert(data.b == 42); 562 } 563 564 @safe unittest 565 { 566 struct Test 567 { 568 mixin(bitfields!(bool, "a", 1, 569 uint, "b", 3, 570 short, "c", 4)); 571 } 572 573 @safe void test() pure nothrow 574 { 575 Test t; 576 577 t.a = true; 578 t.b = 5; 579 t.c = 2; 580 581 assert(t.a); 582 assert(t.b == 5); 583 assert(t.c == 2); 584 } 585 586 test(); 587 } 588 589 @safe unittest 590 { 591 { 592 static struct Integrals { 593 bool checkExpectations(bool eb, int ei, short es) { return b == eb && i == ei && s == es; } 594 595 mixin(bitfields!( 596 bool, "b", 1, 597 uint, "i", 3, 598 short, "s", 4)); 599 } 600 Integrals i; 601 assert(i.checkExpectations(false, 0, 0)); 602 i.b = true; 603 assert(i.checkExpectations(true, 0, 0)); 604 i.i = 7; 605 assert(i.checkExpectations(true, 7, 0)); 606 i.s = -8; 607 assert(i.checkExpectations(true, 7, -8)); 608 i.s = 7; 609 assert(i.checkExpectations(true, 7, 7)); 610 } 611 612 //https://issues.dlang.org/show_bug.cgi?id=8876 613 { 614 struct MoreIntegrals { 615 bool checkExpectations(uint eu, ushort es, uint ei) { return u == eu && s == es && i == ei; } 616 617 mixin(bitfields!( 618 uint, "u", 24, 619 short, "s", 16, 620 int, "i", 24)); 621 } 622 623 MoreIntegrals i; 624 assert(i.checkExpectations(0, 0, 0)); 625 i.s = 20; 626 assert(i.checkExpectations(0, 20, 0)); 627 i.i = 72; 628 assert(i.checkExpectations(0, 20, 72)); 629 i.u = 8; 630 assert(i.checkExpectations(8, 20, 72)); 631 i.s = 7; 632 assert(i.checkExpectations(8, 7, 72)); 633 } 634 635 enum A { True, False } 636 enum B { One, Two, Three, Four } 637 static struct Enums { 638 bool checkExpectations(A ea, B eb) { return a == ea && b == eb; } 639 640 mixin(bitfields!( 641 A, "a", 1, 642 B, "b", 2, 643 uint, "", 5)); 644 } 645 Enums e; 646 assert(e.checkExpectations(A.True, B.One)); 647 e.a = A.False; 648 assert(e.checkExpectations(A.False, B.One)); 649 e.b = B.Three; 650 assert(e.checkExpectations(A.False, B.Three)); 651 652 static struct SingleMember { 653 bool checkExpectations(bool eb) { return b == eb; } 654 655 mixin(bitfields!( 656 bool, "b", 1, 657 uint, "", 7)); 658 } 659 SingleMember f; 660 assert(f.checkExpectations(false)); 661 f.b = true; 662 assert(f.checkExpectations(true)); 663 } 664 665 // https://issues.dlang.org/show_bug.cgi?id=12477 666 @system unittest 667 { 668 import core.exception : AssertError; 669 import std.algorithm.searching : canFind; 670 import std.bitmanip : bitfields; 671 672 static struct S 673 { 674 mixin(bitfields!( 675 uint, "a", 6, 676 int, "b", 2)); 677 } 678 679 S s; 680 681 try { s.a = uint.max; assert(0); } 682 catch (AssertError ae) 683 { assert(ae.msg.canFind("Value is greater than the maximum value of bitfield 'a'"), ae.msg); } 684 685 try { s.b = int.min; assert(0); } 686 catch (AssertError ae) 687 { assert(ae.msg.canFind("Value is smaller than the minimum value of bitfield 'b'"), ae.msg); } 688 } 689 690 /** 691 Allows manipulating the fraction, exponent, and sign parts of a 692 $(D_PARAM float) separately. The definition is: 693 694 ---- 695 struct FloatRep 696 { 697 union 698 { 699 float value; 700 mixin(bitfields!( 701 uint, "fraction", 23, 702 ubyte, "exponent", 8, 703 bool, "sign", 1)); 704 } 705 enum uint bias = 127, fractionBits = 23, exponentBits = 8, signBits = 1; 706 } 707 ---- 708 */ 709 struct FloatRep 710 { 711 union 712 { 713 float value; 714 mixin(bitfields!( 715 uint, "fraction", 23, 716 ubyte, "exponent", 8, 717 bool, "sign", 1)); 718 } 719 enum uint bias = 127, fractionBits = 23, exponentBits = 8, signBits = 1; 720 } 721 722 /// 723 @safe unittest 724 { 725 FloatRep rep = {value: 0}; 726 assert(rep.fraction == 0); 727 assert(rep.exponent == 0); 728 assert(!rep.sign); 729 730 rep.value = 42; 731 assert(rep.fraction == 2621440); 732 assert(rep.exponent == 132); 733 assert(!rep.sign); 734 735 rep.value = 10; 736 assert(rep.fraction == 2097152); 737 assert(rep.exponent == 130); 738 } 739 740 /// 741 @safe unittest 742 { 743 FloatRep rep = {value: 1}; 744 assert(rep.fraction == 0); 745 assert(rep.exponent == 127); 746 assert(!rep.sign); 747 748 rep.exponent = 126; 749 assert(rep.value == 0.5); 750 751 rep.exponent = 130; 752 assert(rep.value == 8); 753 } 754 755 /// 756 @safe unittest 757 { 758 FloatRep rep = {value: 1}; 759 rep.value = -0.5; 760 assert(rep.fraction == 0); 761 assert(rep.exponent == 126); 762 assert(rep.sign); 763 764 rep.value = -1. / 3; 765 assert(rep.fraction == 2796203); 766 assert(rep.exponent == 125); 767 assert(rep.sign); 768 } 769 770 /** 771 Allows manipulating the fraction, exponent, and sign parts of a 772 $(D_PARAM double) separately. The definition is: 773 774 ---- 775 struct DoubleRep 776 { 777 union 778 { 779 double value; 780 mixin(bitfields!( 781 ulong, "fraction", 52, 782 ushort, "exponent", 11, 783 bool, "sign", 1)); 784 } 785 enum uint bias = 1023, signBits = 1, fractionBits = 52, exponentBits = 11; 786 } 787 ---- 788 */ 789 790 struct DoubleRep 791 { 792 union 793 { 794 double value; 795 mixin(bitfields!( 796 ulong, "fraction", 52, 797 ushort, "exponent", 11, 798 bool, "sign", 1)); 799 } 800 enum uint bias = 1023, signBits = 1, fractionBits = 52, exponentBits = 11; 801 } 802 803 /// 804 @safe unittest 805 { 806 DoubleRep rep = {value: 0}; 807 assert(rep.fraction == 0); 808 assert(rep.exponent == 0); 809 assert(!rep.sign); 810 811 rep.value = 42; 812 assert(rep.fraction == 1407374883553280); 813 assert(rep.exponent == 1028); 814 assert(!rep.sign); 815 816 rep.value = 10; 817 assert(rep.fraction == 1125899906842624); 818 assert(rep.exponent == 1026); 819 } 820 821 /// 822 @safe unittest 823 { 824 DoubleRep rep = {value: 1}; 825 assert(rep.fraction == 0); 826 assert(rep.exponent == 1023); 827 assert(!rep.sign); 828 829 rep.exponent = 1022; 830 assert(rep.value == 0.5); 831 832 rep.exponent = 1026; 833 assert(rep.value == 8); 834 } 835 836 /// 837 @safe unittest 838 { 839 DoubleRep rep = {value: 1}; 840 rep.value = -0.5; 841 assert(rep.fraction == 0); 842 assert(rep.exponent == 1022); 843 assert(rep.sign); 844 845 rep.value = -1. / 3; 846 assert(rep.fraction == 1501199875790165); 847 assert(rep.exponent == 1021); 848 assert(rep.sign); 849 } 850 851 /// Reading 852 @safe unittest 853 { 854 DoubleRep x; 855 x.value = 1.0; 856 assert(x.fraction == 0 && x.exponent == 1023 && !x.sign); 857 x.value = -0.5; 858 assert(x.fraction == 0 && x.exponent == 1022 && x.sign); 859 x.value = 0.5; 860 assert(x.fraction == 0 && x.exponent == 1022 && !x.sign); 861 } 862 863 /// Writing 864 @safe unittest 865 { 866 DoubleRep x; 867 x.fraction = 1125899906842624; 868 x.exponent = 1025; 869 x.sign = true; 870 assert(x.value == -5.0); 871 } 872 873 // https://issues.dlang.org/show_bug.cgi?id=15305 874 @safe unittest 875 { 876 struct S { 877 mixin(bitfields!( 878 bool, "alice", 1, 879 ulong, "bob", 63, 880 )); 881 } 882 883 S s; 884 s.bob = long.max - 1; 885 s.alice = false; 886 assert(s.bob == long.max - 1); 887 } 888 889 /** 890 A dynamic array of bits. Each bit in a `BitArray` can be manipulated individually 891 or by the standard bitwise operators `&`, `|`, `^`, `~`, `>>`, `<<` and also by 892 other effective member functions; most of them work relative to the `BitArray`'s 893 dimension (see $(LREF dim)), instead of its $(LREF length). 894 */ 895 struct BitArray 896 { 897 private: 898 899 import core.bitop : btc, bts, btr, bsf, bt; 900 import std.format : FormatSpec; 901 902 size_t _len; 903 size_t* _ptr; 904 enum bitsPerSizeT = size_t.sizeof * 8; 905 906 @property size_t fullWords() const @nogc pure nothrow 907 { 908 return _len / bitsPerSizeT; 909 } 910 // Number of bits after the last full word 911 @property size_t endBits() const @nogc pure nothrow 912 { 913 return _len % bitsPerSizeT; 914 } 915 // Bit mask to extract the bits after the last full word 916 @property size_t endMask() const @nogc pure nothrow 917 { 918 return (size_t(1) << endBits) - 1; 919 } 920 static size_t lenToDim(size_t len) @nogc pure nothrow @safe 921 { 922 return (len + (bitsPerSizeT-1)) / bitsPerSizeT; 923 } 924 925 public: 926 /** 927 Creates a `BitArray` from a `bool` array, such that `bool` values read 928 from left to right correspond to subsequent bits in the `BitArray`. 929 930 Params: ba = Source array of `bool` values. 931 */ 932 this(in bool[] ba) nothrow pure 933 { 934 length = ba.length; 935 foreach (i, b; ba) 936 { 937 this[i] = b; 938 } 939 } 940 941 /// 942 @system unittest 943 { 944 import std.algorithm.comparison : equal; 945 946 bool[] input = [true, false, false, true, true]; 947 auto a = BitArray(input); 948 assert(a.length == 5); 949 assert(a.bitsSet.equal([0, 3, 4])); 950 951 // This also works because an implicit cast to bool[] occurs for this array. 952 auto b = BitArray([0, 0, 1]); 953 assert(b.length == 3); 954 assert(b.bitsSet.equal([2])); 955 } 956 957 /// 958 @system unittest 959 { 960 import std.algorithm.comparison : equal; 961 import std.array : array; 962 import std.range : iota, repeat; 963 964 BitArray a = true.repeat(70).array; 965 assert(a.length == 70); 966 assert(a.bitsSet.equal(iota(0, 70))); 967 } 968 969 /** 970 Creates a `BitArray` from the raw contents of the source array. The 971 source array is not copied but simply acts as the underlying array 972 of bits, which stores data as `size_t` units. 973 974 That means a particular care should be taken when passing an array 975 of a type different than `size_t`, firstly because its length should 976 be a multiple of `size_t.sizeof`, and secondly because how the bits 977 are mapped: 978 --- 979 size_t[] source = [1, 2, 3, 3424234, 724398, 230947, 389492]; 980 enum sbits = size_t.sizeof * 8; 981 auto ba = BitArray(source, source.length * sbits); 982 foreach (n; 0 .. source.length * sbits) 983 { 984 auto nth_bit = cast(bool) (source[n / sbits] & (1L << (n % sbits))); 985 assert(ba[n] == nth_bit); 986 } 987 --- 988 The least significant bit in any `size_t` unit is the starting bit of this 989 unit, and the most significant bit is the last bit of this unit. Therefore, 990 passing e.g. an array of `int`s may result in a different `BitArray` 991 depending on the processor's endianness. 992 993 This constructor is the inverse of $(LREF opCast). 994 995 Params: 996 v = Source array. `v.length` must be a multple of `size_t.sizeof`. 997 numbits = Number of bits to be mapped from the source array, i.e. 998 length of the created `BitArray`. 999 */ 1000 this(void[] v, size_t numbits) @nogc nothrow pure 1001 in 1002 { 1003 assert(numbits <= v.length * 8, 1004 "numbits must be less than or equal to v.length * 8"); 1005 assert(v.length % size_t.sizeof == 0, 1006 "v.length must be a multiple of the size of size_t"); 1007 } 1008 do 1009 { 1010 _ptr = cast(size_t*) v.ptr; 1011 _len = numbits; 1012 } 1013 1014 /// 1015 @system unittest 1016 { 1017 import std.algorithm.comparison : equal; 1018 1019 auto a = BitArray([1, 0, 0, 1, 1]); 1020 1021 // Inverse of the cast. 1022 auto v = cast(void[]) a; 1023 auto b = BitArray(v, a.length); 1024 1025 assert(b.length == 5); 1026 assert(b.bitsSet.equal([0, 3, 4])); 1027 1028 // a and b share the underlying data. 1029 a[0] = 0; 1030 assert(b[0] == 0); 1031 assert(a == b); 1032 } 1033 1034 /// 1035 @system unittest 1036 { 1037 import std.algorithm.comparison : equal; 1038 1039 size_t[] source = [0b1100, 0b0011]; 1040 enum sbits = size_t.sizeof * 8; 1041 auto ba = BitArray(source, source.length * sbits); 1042 // The least significant bit in each unit is this unit's starting bit. 1043 assert(ba.bitsSet.equal([2, 3, sbits, sbits + 1])); 1044 } 1045 1046 /// 1047 @system unittest 1048 { 1049 // Example from the doc for this constructor. 1050 static immutable size_t[] sourceData = [1, 0b101, 3, 3424234, 724398, 230947, 389492]; 1051 size_t[] source = sourceData.dup; 1052 enum sbits = size_t.sizeof * 8; 1053 auto ba = BitArray(source, source.length * sbits); 1054 foreach (n; 0 .. source.length * sbits) 1055 { 1056 auto nth_bit = cast(bool) (source[n / sbits] & (1L << (n % sbits))); 1057 assert(ba[n] == nth_bit); 1058 } 1059 1060 // Example of mapping only part of the array. 1061 import std.algorithm.comparison : equal; 1062 1063 auto bc = BitArray(source, sbits + 1); 1064 assert(bc.bitsSet.equal([0, sbits])); 1065 // Source array has not been modified. 1066 assert(source == sourceData); 1067 } 1068 1069 // Deliberately undocumented: raw initialization of bit array. 1070 this(size_t len, size_t* ptr) @nogc nothrow pure 1071 { 1072 _len = len; 1073 _ptr = ptr; 1074 } 1075 1076 /** 1077 Returns: Dimension i.e. the number of native words backing this `BitArray`. 1078 1079 Technically, this is the length of the underlying array storing bits, which 1080 is equal to `ceil(length / (size_t.sizeof * 8))`, as bits are packed into 1081 `size_t` units. 1082 */ 1083 @property size_t dim() const @nogc nothrow pure @safe 1084 { 1085 return lenToDim(_len); 1086 } 1087 1088 /** 1089 Returns: Number of bits in the `BitArray`. 1090 */ 1091 @property size_t length() const @nogc nothrow pure @safe 1092 { 1093 return _len; 1094 } 1095 1096 /********************************************** 1097 * Sets the amount of bits in the `BitArray`. 1098 * $(RED Warning: increasing length may overwrite bits in 1099 * the final word of the current underlying data regardless 1100 * of whether it is shared between BitArray objects. i.e. D 1101 * dynamic array extension semantics are not followed.) 1102 */ 1103 @property size_t length(size_t newlen) pure nothrow @system 1104 { 1105 if (newlen != _len) 1106 { 1107 size_t olddim = dim; 1108 immutable newdim = lenToDim(newlen); 1109 1110 if (newdim != olddim) 1111 { 1112 // Create a fake array so we can use D's realloc machinery 1113 auto b = _ptr[0 .. olddim]; 1114 b.length = newdim; // realloc 1115 _ptr = b.ptr; 1116 } 1117 1118 auto oldlen = _len; 1119 _len = newlen; 1120 if (oldlen < newlen) 1121 { 1122 auto end = ((oldlen / bitsPerSizeT) + 1) * bitsPerSizeT; 1123 if (end > newlen) 1124 end = newlen; 1125 this[oldlen .. end] = 0; 1126 } 1127 } 1128 return _len; 1129 } 1130 1131 // https://issues.dlang.org/show_bug.cgi?id=20240 1132 @system unittest 1133 { 1134 BitArray ba; 1135 1136 ba.length = 1; 1137 ba[0] = 1; 1138 ba.length = 0; 1139 ba.length = 1; 1140 assert(ba[0] == 0); // OK 1141 1142 ba.length = 2; 1143 ba[1] = 1; 1144 ba.length = 1; 1145 ba.length = 2; 1146 assert(ba[1] == 0); // Fail 1147 } 1148 1149 /********************************************** 1150 * Gets the `i`'th bit in the `BitArray`. 1151 */ 1152 bool opIndex(size_t i) const @nogc pure nothrow 1153 in 1154 { 1155 assert(i < _len, "i must be less than the length"); 1156 } 1157 do 1158 { 1159 return cast(bool) bt(_ptr, i); 1160 } 1161 1162 /// 1163 @system unittest 1164 { 1165 static void fun(const BitArray arr) 1166 { 1167 auto x = arr[0]; 1168 assert(x == 1); 1169 } 1170 BitArray a; 1171 a.length = 3; 1172 a[0] = 1; 1173 fun(a); 1174 } 1175 1176 /********************************************** 1177 * Sets the `i`'th bit in the `BitArray`. 1178 */ 1179 bool opIndexAssign(bool b, size_t i) @nogc pure nothrow 1180 in 1181 { 1182 assert(i < _len, "i must be less than the length"); 1183 } 1184 do 1185 { 1186 if (b) 1187 bts(_ptr, i); 1188 else 1189 btr(_ptr, i); 1190 return b; 1191 } 1192 1193 /** 1194 Sets all the values in the `BitArray` to the 1195 value specified by `val`. 1196 */ 1197 void opSliceAssign(bool val) @nogc pure nothrow 1198 { 1199 _ptr[0 .. fullWords] = val ? ~size_t(0) : 0; 1200 if (endBits) 1201 { 1202 if (val) 1203 _ptr[fullWords] |= endMask; 1204 else 1205 _ptr[fullWords] &= ~endMask; 1206 } 1207 } 1208 1209 /// 1210 @system pure nothrow unittest 1211 { 1212 import std.algorithm.comparison : equal; 1213 1214 auto b = BitArray([1, 0, 1, 0, 1, 1]); 1215 1216 b[] = true; 1217 // all bits are set 1218 assert(b.bitsSet.equal([0, 1, 2, 3, 4, 5])); 1219 1220 b[] = false; 1221 // none of the bits are set 1222 assert(b.bitsSet.empty); 1223 } 1224 1225 /** 1226 Sets the bits of a slice of `BitArray` starting 1227 at index `start` and ends at index ($D end - 1) 1228 with the values specified by `val`. 1229 */ 1230 void opSliceAssign(bool val, size_t start, size_t end) @nogc pure nothrow 1231 in 1232 { 1233 assert(start <= end, "start must be less or equal to end"); 1234 assert(end <= length, "end must be less or equal to the length"); 1235 } 1236 do 1237 { 1238 size_t startBlock = start / bitsPerSizeT; 1239 size_t endBlock = end / bitsPerSizeT; 1240 size_t startOffset = start % bitsPerSizeT; 1241 size_t endOffset = end % bitsPerSizeT; 1242 1243 if (startBlock == endBlock) 1244 { 1245 size_t startBlockMask = ~((size_t(1) << startOffset) - 1); 1246 size_t endBlockMask = (size_t(1) << endOffset) - 1; 1247 size_t joinMask = startBlockMask & endBlockMask; 1248 if (val) 1249 _ptr[startBlock] |= joinMask; 1250 else 1251 _ptr[startBlock] &= ~joinMask; 1252 return; 1253 } 1254 1255 if (startOffset != 0) 1256 { 1257 size_t startBlockMask = ~((size_t(1) << startOffset) - 1); 1258 if (val) 1259 _ptr[startBlock] |= startBlockMask; 1260 else 1261 _ptr[startBlock] &= ~startBlockMask; 1262 ++startBlock; 1263 } 1264 if (endOffset != 0) 1265 { 1266 size_t endBlockMask = (size_t(1) << endOffset) - 1; 1267 if (val) 1268 _ptr[endBlock] |= endBlockMask; 1269 else 1270 _ptr[endBlock] &= ~endBlockMask; 1271 } 1272 _ptr[startBlock .. endBlock] = size_t(0) - size_t(val); 1273 } 1274 1275 /// 1276 @system pure nothrow unittest 1277 { 1278 import std.algorithm.comparison : equal; 1279 import std.range : iota; 1280 import std.stdio; 1281 1282 auto b = BitArray([1, 0, 0, 0, 1, 1, 0]); 1283 b[1 .. 3] = true; 1284 assert(b.bitsSet.equal([0, 1, 2, 4, 5])); 1285 1286 bool[72] bitArray; 1287 auto b1 = BitArray(bitArray); 1288 b1[63 .. 67] = true; 1289 assert(b1.bitsSet.equal([63, 64, 65, 66])); 1290 b1[63 .. 67] = false; 1291 assert(b1.bitsSet.empty); 1292 b1[0 .. 64] = true; 1293 assert(b1.bitsSet.equal(iota(0, 64))); 1294 b1[0 .. 64] = false; 1295 assert(b1.bitsSet.empty); 1296 1297 bool[256] bitArray2; 1298 auto b2 = BitArray(bitArray2); 1299 b2[3 .. 245] = true; 1300 assert(b2.bitsSet.equal(iota(3, 245))); 1301 b2[3 .. 245] = false; 1302 assert(b2.bitsSet.empty); 1303 } 1304 1305 /** 1306 Flips all the bits in the `BitArray` 1307 */ 1308 void flip() @nogc pure nothrow 1309 { 1310 foreach (i; 0 .. fullWords) 1311 _ptr[i] = ~_ptr[i]; 1312 1313 if (endBits) 1314 _ptr[fullWords] = (~_ptr[fullWords]) & endMask; 1315 } 1316 1317 /// 1318 @system pure nothrow unittest 1319 { 1320 import std.algorithm.comparison : equal; 1321 import std.range : iota; 1322 1323 // positions 0, 2, 4 are set 1324 auto b = BitArray([1, 0, 1, 0, 1, 0]); 1325 b.flip(); 1326 // after flipping, positions 1, 3, 5 are set 1327 assert(b.bitsSet.equal([1, 3, 5])); 1328 1329 bool[270] bits; 1330 auto b1 = BitArray(bits); 1331 b1.flip(); 1332 assert(b1.bitsSet.equal(iota(0, 270))); 1333 } 1334 1335 /** 1336 Flips a single bit, specified by `pos` 1337 */ 1338 void flip(size_t i) @nogc pure nothrow 1339 { 1340 bt(_ptr, i) ? btr(_ptr, i) : bts(_ptr, i); 1341 } 1342 1343 /// 1344 @system pure nothrow unittest 1345 { 1346 auto ax = BitArray([1, 0, 0, 1]); 1347 ax.flip(0); 1348 assert(ax[0] == 0); 1349 1350 bool[200] y; 1351 y[90 .. 130] = true; 1352 auto ay = BitArray(y); 1353 ay.flip(100); 1354 assert(ay[100] == 0); 1355 } 1356 1357 /********************************************** 1358 * Counts all the set bits in the `BitArray` 1359 */ 1360 size_t count() const @nogc pure nothrow 1361 { 1362 if (_ptr) 1363 { 1364 size_t bitCount; 1365 foreach (i; 0 .. fullWords) 1366 bitCount += countBitsSet(_ptr[i]); 1367 bitCount += countBitsSet(_ptr[fullWords] & endMask); 1368 return bitCount; 1369 } 1370 else 1371 { 1372 return 0; 1373 } 1374 } 1375 1376 /// 1377 @system pure nothrow unittest 1378 { 1379 auto a = BitArray([0, 1, 1, 0, 0, 1, 1]); 1380 assert(a.count == 4); 1381 1382 BitArray b; 1383 assert(b.count == 0); 1384 1385 bool[200] boolArray; 1386 boolArray[45 .. 130] = true; 1387 auto c = BitArray(boolArray); 1388 assert(c.count == 85); 1389 } 1390 1391 /********************************************** 1392 * Duplicates the `BitArray` and its contents. 1393 */ 1394 @property BitArray dup() const pure nothrow 1395 { 1396 BitArray ba; 1397 1398 auto b = _ptr[0 .. dim].dup; 1399 ba._len = _len; 1400 ba._ptr = b.ptr; 1401 return ba; 1402 } 1403 1404 /// 1405 @system unittest 1406 { 1407 BitArray a; 1408 BitArray b; 1409 1410 a.length = 3; 1411 a[0] = 1; a[1] = 0; a[2] = 1; 1412 b = a.dup; 1413 assert(b.length == 3); 1414 foreach (i; 0 .. 3) 1415 assert(b[i] == (((i ^ 1) & 1) ? true : false)); 1416 } 1417 1418 /********************************************** 1419 * Support for `foreach` loops for `BitArray`. 1420 */ 1421 int opApply(scope int delegate(ref bool) dg) 1422 { 1423 int result; 1424 1425 foreach (i; 0 .. _len) 1426 { 1427 bool b = opIndex(i); 1428 result = dg(b); 1429 this[i] = b; 1430 if (result) 1431 break; 1432 } 1433 return result; 1434 } 1435 1436 /** ditto */ 1437 int opApply(scope int delegate(bool) dg) const 1438 { 1439 int result; 1440 1441 foreach (i; 0 .. _len) 1442 { 1443 immutable b = opIndex(i); 1444 result = dg(b); 1445 if (result) 1446 break; 1447 } 1448 return result; 1449 } 1450 1451 /** ditto */ 1452 int opApply(scope int delegate(size_t, ref bool) dg) 1453 { 1454 int result; 1455 1456 foreach (i; 0 .. _len) 1457 { 1458 bool b = opIndex(i); 1459 result = dg(i, b); 1460 this[i] = b; 1461 if (result) 1462 break; 1463 } 1464 return result; 1465 } 1466 1467 /** ditto */ 1468 int opApply(scope int delegate(size_t, bool) dg) const 1469 { 1470 int result; 1471 1472 foreach (i; 0 .. _len) 1473 { 1474 immutable b = opIndex(i); 1475 result = dg(i, b); 1476 if (result) 1477 break; 1478 } 1479 return result; 1480 } 1481 1482 /// 1483 @system unittest 1484 { 1485 bool[] ba = [1,0,1]; 1486 1487 auto a = BitArray(ba); 1488 1489 int i; 1490 foreach (b;a) 1491 { 1492 switch (i) 1493 { 1494 case 0: assert(b == true); break; 1495 case 1: assert(b == false); break; 1496 case 2: assert(b == true); break; 1497 default: assert(0); 1498 } 1499 i++; 1500 } 1501 1502 foreach (j,b;a) 1503 { 1504 switch (j) 1505 { 1506 case 0: assert(b == true); break; 1507 case 1: assert(b == false); break; 1508 case 2: assert(b == true); break; 1509 default: assert(0); 1510 } 1511 } 1512 } 1513 1514 1515 /********************************************** 1516 * Reverses the bits of the `BitArray`. 1517 */ 1518 @property BitArray reverse() @nogc pure nothrow 1519 out (result) 1520 { 1521 assert(result == this, "the result must be equal to this"); 1522 } 1523 do 1524 { 1525 if (_len >= 2) 1526 { 1527 bool t; 1528 size_t lo, hi; 1529 1530 lo = 0; 1531 hi = _len - 1; 1532 for (; lo < hi; lo++, hi--) 1533 { 1534 t = this[lo]; 1535 this[lo] = this[hi]; 1536 this[hi] = t; 1537 } 1538 } 1539 return this; 1540 } 1541 1542 /// 1543 @system unittest 1544 { 1545 BitArray b; 1546 bool[5] data = [1,0,1,1,0]; 1547 1548 b = BitArray(data); 1549 b.reverse; 1550 foreach (i; 0 .. data.length) 1551 assert(b[i] == data[4 - i]); 1552 } 1553 1554 1555 /********************************************** 1556 * Sorts the `BitArray`'s elements. 1557 */ 1558 @property BitArray sort() @nogc pure nothrow 1559 out (result) 1560 { 1561 assert(result == this, "the result must be equal to this"); 1562 } 1563 do 1564 { 1565 if (_len >= 2) 1566 { 1567 size_t lo, hi; 1568 1569 lo = 0; 1570 hi = _len - 1; 1571 while (1) 1572 { 1573 while (1) 1574 { 1575 if (lo >= hi) 1576 goto Ldone; 1577 if (this[lo] == true) 1578 break; 1579 lo++; 1580 } 1581 1582 while (1) 1583 { 1584 if (lo >= hi) 1585 goto Ldone; 1586 if (this[hi] == false) 1587 break; 1588 hi--; 1589 } 1590 1591 this[lo] = false; 1592 this[hi] = true; 1593 1594 lo++; 1595 hi--; 1596 } 1597 } 1598 Ldone: 1599 return this; 1600 } 1601 1602 /// 1603 @system unittest 1604 { 1605 size_t x = 0b1100011000; 1606 auto ba = BitArray(10, &x); 1607 ba.sort; 1608 foreach (i; 0 .. 6) 1609 assert(ba[i] == false); 1610 foreach (i; 6 .. 10) 1611 assert(ba[i] == true); 1612 } 1613 1614 1615 /*************************************** 1616 * Support for operators == and != for `BitArray`. 1617 */ 1618 bool opEquals(const ref BitArray a2) const @nogc pure nothrow 1619 { 1620 if (this.length != a2.length) 1621 return false; 1622 auto p1 = this._ptr; 1623 auto p2 = a2._ptr; 1624 1625 if (p1[0 .. fullWords] != p2[0 .. fullWords]) 1626 return false; 1627 1628 if (!endBits) 1629 return true; 1630 1631 auto i = fullWords; 1632 return (p1[i] & endMask) == (p2[i] & endMask); 1633 } 1634 1635 /// 1636 @system unittest 1637 { 1638 bool[] ba = [1,0,1,0,1]; 1639 bool[] bb = [1,0,1]; 1640 bool[] bc = [1,0,1,0,1,0,1]; 1641 bool[] bd = [1,0,1,1,1]; 1642 bool[] be = [1,0,1,0,1]; 1643 bool[] bf = [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; 1644 bool[] bg = [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]; 1645 1646 auto a = BitArray(ba); 1647 auto b = BitArray(bb); 1648 auto c = BitArray(bc); 1649 auto d = BitArray(bd); 1650 auto e = BitArray(be); 1651 auto f = BitArray(bf); 1652 auto g = BitArray(bg); 1653 1654 assert(a != b); 1655 assert(a != c); 1656 assert(a != d); 1657 assert(a == e); 1658 assert(f != g); 1659 } 1660 1661 /*************************************** 1662 * Supports comparison operators for `BitArray`. 1663 */ 1664 int opCmp(BitArray a2) const @nogc pure nothrow 1665 { 1666 const lesser = this.length < a2.length ? &this : &a2; 1667 immutable fullWords = lesser.fullWords; 1668 immutable endBits = lesser.endBits; 1669 auto p1 = this._ptr; 1670 auto p2 = a2._ptr; 1671 1672 foreach (i; 0 .. fullWords) 1673 { 1674 if (p1[i] != p2[i]) 1675 { 1676 return p1[i] & (size_t(1) << bsf(p1[i] ^ p2[i])) ? 1 : -1; 1677 } 1678 } 1679 1680 if (endBits) 1681 { 1682 immutable i = fullWords; 1683 immutable diff = p1[i] ^ p2[i]; 1684 if (diff) 1685 { 1686 immutable index = bsf(diff); 1687 if (index < endBits) 1688 { 1689 return p1[i] & (size_t(1) << index) ? 1 : -1; 1690 } 1691 } 1692 } 1693 1694 // Standard: 1695 // A bool value can be implicitly converted to any integral type, 1696 // with false becoming 0 and true becoming 1 1697 return (this.length > a2.length) - (this.length < a2.length); 1698 } 1699 1700 /// 1701 @system unittest 1702 { 1703 bool[] ba = [1,0,1,0,1]; 1704 bool[] bb = [1,0,1]; 1705 bool[] bc = [1,0,1,0,1,0,1]; 1706 bool[] bd = [1,0,1,1,1]; 1707 bool[] be = [1,0,1,0,1]; 1708 bool[] bf = [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]; 1709 bool[] bg = [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]; 1710 1711 auto a = BitArray(ba); 1712 auto b = BitArray(bb); 1713 auto c = BitArray(bc); 1714 auto d = BitArray(bd); 1715 auto e = BitArray(be); 1716 auto f = BitArray(bf); 1717 auto g = BitArray(bg); 1718 1719 assert(a > b); 1720 assert(a >= b); 1721 assert(a < c); 1722 assert(a <= c); 1723 assert(a < d); 1724 assert(a <= d); 1725 assert(a == e); 1726 assert(a <= e); 1727 assert(a >= e); 1728 assert(f < g); 1729 assert(g <= g); 1730 } 1731 1732 @system unittest 1733 { 1734 bool[] v; 1735 foreach (i; 1 .. 256) 1736 { 1737 v.length = i; 1738 v[] = false; 1739 auto x = BitArray(v); 1740 v[i-1] = true; 1741 auto y = BitArray(v); 1742 assert(x < y); 1743 assert(x <= y); 1744 } 1745 1746 BitArray a1, a2; 1747 1748 for (size_t len = 4; len <= 256; len <<= 1) 1749 { 1750 a1.length = a2.length = len; 1751 a1[len-2] = a2[len-1] = true; 1752 assert(a1 > a2); 1753 a1[len-2] = a2[len-1] = false; 1754 } 1755 1756 foreach (j; 1 .. a1.length) 1757 { 1758 a1[j-1] = a2[j] = true; 1759 assert(a1 > a2); 1760 a1[j-1] = a2[j] = false; 1761 } 1762 } 1763 1764 /*************************************** 1765 * Support for hashing for `BitArray`. 1766 */ 1767 size_t toHash() const @nogc pure nothrow 1768 { 1769 size_t hash = 3557; 1770 auto fullBytes = _len / 8; 1771 foreach (i; 0 .. fullBytes) 1772 { 1773 hash *= 3559; 1774 hash += (cast(byte*) this._ptr)[i]; 1775 } 1776 foreach (i; 8*fullBytes .. _len) 1777 { 1778 hash *= 3571; 1779 hash += this[i]; 1780 } 1781 return hash; 1782 } 1783 1784 /*************************************** 1785 * Convert to `void[]`. 1786 */ 1787 inout(void)[] opCast(T : const void[])() inout @nogc pure nothrow 1788 { 1789 return cast(inout void[]) _ptr[0 .. dim]; 1790 } 1791 1792 /*************************************** 1793 * Convert to `size_t[]`. 1794 */ 1795 inout(size_t)[] opCast(T : const size_t[])() inout @nogc pure nothrow 1796 { 1797 return _ptr[0 .. dim]; 1798 } 1799 1800 /// 1801 @system unittest 1802 { 1803 import std.array : array; 1804 import std.range : repeat, take; 1805 1806 // bit array with 300 elements 1807 auto a = BitArray(true.repeat.take(300).array); 1808 size_t[] v = cast(size_t[]) a; 1809 const blockSize = size_t.sizeof * 8; 1810 assert(v.length == (a.length + blockSize - 1) / blockSize); 1811 } 1812 1813 // https://issues.dlang.org/show_bug.cgi?id=20606 1814 @system unittest 1815 { 1816 import std.meta : AliasSeq; 1817 1818 static foreach (alias T; AliasSeq!(void, size_t)) 1819 {{ 1820 BitArray m; 1821 T[] ma = cast(T[]) m; 1822 1823 const BitArray c; 1824 const(T)[] ca = cast(const T[]) c; 1825 1826 immutable BitArray i; 1827 immutable(T)[] ia = cast(immutable T[]) i; 1828 1829 // Cross-mutability 1830 ca = cast(const T[]) m; 1831 ca = cast(const T[]) i; 1832 1833 // Invalid cast don't compile 1834 static assert(!is(typeof(cast(T[]) c))); 1835 static assert(!is(typeof(cast(T[]) i))); 1836 static assert(!is(typeof(cast(immutable T[]) m))); 1837 static assert(!is(typeof(cast(immutable T[]) c))); 1838 }} 1839 } 1840 1841 /*************************************** 1842 * Support for unary operator ~ for `BitArray`. 1843 */ 1844 BitArray opUnary(string op)() const pure nothrow 1845 if (op == "~") 1846 { 1847 auto dim = this.dim; 1848 1849 BitArray result; 1850 result.length = _len; 1851 1852 result._ptr[0 .. dim] = ~this._ptr[0 .. dim]; 1853 1854 // Avoid putting garbage in extra bits 1855 // Remove once we zero on length extension 1856 if (endBits) 1857 result._ptr[dim - 1] &= endMask; 1858 1859 return result; 1860 } 1861 1862 /// 1863 @system unittest 1864 { 1865 bool[] ba = [1,0,1,0,1]; 1866 1867 auto a = BitArray(ba); 1868 BitArray b = ~a; 1869 1870 assert(b[0] == 0); 1871 assert(b[1] == 1); 1872 assert(b[2] == 0); 1873 assert(b[3] == 1); 1874 assert(b[4] == 0); 1875 } 1876 1877 1878 /*************************************** 1879 * Support for binary bitwise operators for `BitArray`. 1880 */ 1881 BitArray opBinary(string op)(const BitArray e2) const pure nothrow 1882 if (op == "-" || op == "&" || op == "|" || op == "^") 1883 in 1884 { 1885 assert(e2.length == _len, "e2 must have the same length as this"); 1886 } 1887 do 1888 { 1889 auto dim = this.dim; 1890 1891 BitArray result; 1892 result.length = _len; 1893 1894 static if (op == "-") 1895 result._ptr[0 .. dim] = this._ptr[0 .. dim] & ~e2._ptr[0 .. dim]; 1896 else 1897 mixin("result._ptr[0 .. dim] = this._ptr[0 .. dim]"~op~" e2._ptr[0 .. dim];"); 1898 1899 // Avoid putting garbage in extra bits 1900 // Remove once we zero on length extension 1901 if (endBits) 1902 result._ptr[dim - 1] &= endMask; 1903 1904 return result; 1905 } 1906 1907 /// 1908 @system unittest 1909 { 1910 static bool[] ba = [1,0,1,0,1]; 1911 static bool[] bb = [1,0,1,1,0]; 1912 1913 auto a = BitArray(ba); 1914 auto b = BitArray(bb); 1915 1916 BitArray c = a & b; 1917 1918 assert(c[0] == 1); 1919 assert(c[1] == 0); 1920 assert(c[2] == 1); 1921 assert(c[3] == 0); 1922 assert(c[4] == 0); 1923 } 1924 1925 /// 1926 @system unittest 1927 { 1928 bool[] ba = [1,0,1,0,1]; 1929 bool[] bb = [1,0,1,1,0]; 1930 1931 auto a = BitArray(ba); 1932 auto b = BitArray(bb); 1933 1934 BitArray c = a | b; 1935 1936 assert(c[0] == 1); 1937 assert(c[1] == 0); 1938 assert(c[2] == 1); 1939 assert(c[3] == 1); 1940 assert(c[4] == 1); 1941 } 1942 1943 /// 1944 @system unittest 1945 { 1946 bool[] ba = [1,0,1,0,1]; 1947 bool[] bb = [1,0,1,1,0]; 1948 1949 auto a = BitArray(ba); 1950 auto b = BitArray(bb); 1951 1952 BitArray c = a ^ b; 1953 1954 assert(c[0] == 0); 1955 assert(c[1] == 0); 1956 assert(c[2] == 0); 1957 assert(c[3] == 1); 1958 assert(c[4] == 1); 1959 } 1960 1961 /// 1962 @system unittest 1963 { 1964 bool[] ba = [1,0,1,0,1]; 1965 bool[] bb = [1,0,1,1,0]; 1966 1967 auto a = BitArray(ba); 1968 auto b = BitArray(bb); 1969 1970 BitArray c = a - b; 1971 1972 assert(c[0] == 0); 1973 assert(c[1] == 0); 1974 assert(c[2] == 0); 1975 assert(c[3] == 0); 1976 assert(c[4] == 1); 1977 } 1978 1979 1980 /*************************************** 1981 * Support for operator op= for `BitArray`. 1982 */ 1983 BitArray opOpAssign(string op)(const BitArray e2) @nogc pure nothrow 1984 if (op == "-" || op == "&" || op == "|" || op == "^") 1985 in 1986 { 1987 assert(e2.length == _len, "e2 must have the same length as this"); 1988 } 1989 do 1990 { 1991 foreach (i; 0 .. fullWords) 1992 { 1993 static if (op == "-") 1994 _ptr[i] &= ~e2._ptr[i]; 1995 else 1996 mixin("_ptr[i] "~op~"= e2._ptr[i];"); 1997 } 1998 if (!endBits) 1999 return this; 2000 2001 size_t i = fullWords; 2002 size_t endWord = _ptr[i]; 2003 static if (op == "-") 2004 endWord &= ~e2._ptr[i]; 2005 else 2006 mixin("endWord "~op~"= e2._ptr[i];"); 2007 _ptr[i] = (_ptr[i] & ~endMask) | (endWord & endMask); 2008 2009 return this; 2010 } 2011 2012 /// 2013 @system unittest 2014 { 2015 bool[] ba = [1,0,1,0,1,1,0,1,0,1]; 2016 bool[] bb = [1,0,1,1,0]; 2017 auto a = BitArray(ba); 2018 auto b = BitArray(bb); 2019 BitArray c = a; 2020 c.length = 5; 2021 c &= b; 2022 assert(a[5] == 1); 2023 assert(a[6] == 0); 2024 assert(a[7] == 1); 2025 assert(a[8] == 0); 2026 assert(a[9] == 1); 2027 } 2028 2029 /// 2030 @system unittest 2031 { 2032 bool[] ba = [1,0,1,0,1]; 2033 bool[] bb = [1,0,1,1,0]; 2034 2035 auto a = BitArray(ba); 2036 auto b = BitArray(bb); 2037 2038 a &= b; 2039 assert(a[0] == 1); 2040 assert(a[1] == 0); 2041 assert(a[2] == 1); 2042 assert(a[3] == 0); 2043 assert(a[4] == 0); 2044 } 2045 2046 /// 2047 @system unittest 2048 { 2049 bool[] ba = [1,0,1,0,1]; 2050 bool[] bb = [1,0,1,1,0]; 2051 2052 auto a = BitArray(ba); 2053 auto b = BitArray(bb); 2054 2055 a |= b; 2056 assert(a[0] == 1); 2057 assert(a[1] == 0); 2058 assert(a[2] == 1); 2059 assert(a[3] == 1); 2060 assert(a[4] == 1); 2061 } 2062 2063 /// 2064 @system unittest 2065 { 2066 bool[] ba = [1,0,1,0,1]; 2067 bool[] bb = [1,0,1,1,0]; 2068 2069 auto a = BitArray(ba); 2070 auto b = BitArray(bb); 2071 2072 a ^= b; 2073 assert(a[0] == 0); 2074 assert(a[1] == 0); 2075 assert(a[2] == 0); 2076 assert(a[3] == 1); 2077 assert(a[4] == 1); 2078 } 2079 2080 /// 2081 @system unittest 2082 { 2083 bool[] ba = [1,0,1,0,1]; 2084 bool[] bb = [1,0,1,1,0]; 2085 2086 auto a = BitArray(ba); 2087 auto b = BitArray(bb); 2088 2089 a -= b; 2090 assert(a[0] == 0); 2091 assert(a[1] == 0); 2092 assert(a[2] == 0); 2093 assert(a[3] == 0); 2094 assert(a[4] == 1); 2095 } 2096 2097 /*************************************** 2098 * Support for operator ~= for `BitArray`. 2099 * $(RED Warning: This will overwrite a bit in the final word 2100 * of the current underlying data regardless of whether it is 2101 * shared between BitArray objects. i.e. D dynamic array 2102 * concatenation semantics are not followed) 2103 */ 2104 BitArray opOpAssign(string op)(bool b) pure nothrow 2105 if (op == "~") 2106 { 2107 length = _len + 1; 2108 this[_len - 1] = b; 2109 return this; 2110 } 2111 2112 /// 2113 @system unittest 2114 { 2115 bool[] ba = [1,0,1,0,1]; 2116 2117 auto a = BitArray(ba); 2118 BitArray b; 2119 2120 b = (a ~= true); 2121 assert(a[0] == 1); 2122 assert(a[1] == 0); 2123 assert(a[2] == 1); 2124 assert(a[3] == 0); 2125 assert(a[4] == 1); 2126 assert(a[5] == 1); 2127 2128 assert(b == a); 2129 } 2130 2131 /*************************************** 2132 * ditto 2133 */ 2134 BitArray opOpAssign(string op)(BitArray b) pure nothrow 2135 if (op == "~") 2136 { 2137 auto istart = _len; 2138 length = _len + b.length; 2139 for (auto i = istart; i < _len; i++) 2140 this[i] = b[i - istart]; 2141 return this; 2142 } 2143 2144 /// 2145 @system unittest 2146 { 2147 bool[] ba = [1,0]; 2148 bool[] bb = [0,1,0]; 2149 2150 auto a = BitArray(ba); 2151 auto b = BitArray(bb); 2152 BitArray c; 2153 2154 c = (a ~= b); 2155 assert(a.length == 5); 2156 assert(a[0] == 1); 2157 assert(a[1] == 0); 2158 assert(a[2] == 0); 2159 assert(a[3] == 1); 2160 assert(a[4] == 0); 2161 2162 assert(c == a); 2163 } 2164 2165 /*************************************** 2166 * Support for binary operator ~ for `BitArray`. 2167 */ 2168 BitArray opBinary(string op)(bool b) const pure nothrow 2169 if (op == "~") 2170 { 2171 BitArray r; 2172 2173 r = this.dup; 2174 r.length = _len + 1; 2175 r[_len] = b; 2176 return r; 2177 } 2178 2179 /** ditto */ 2180 BitArray opBinaryRight(string op)(bool b) const pure nothrow 2181 if (op == "~") 2182 { 2183 BitArray r; 2184 2185 r.length = _len + 1; 2186 r[0] = b; 2187 foreach (i; 0 .. _len) 2188 r[1 + i] = this[i]; 2189 return r; 2190 } 2191 2192 /** ditto */ 2193 BitArray opBinary(string op)(BitArray b) const pure nothrow 2194 if (op == "~") 2195 { 2196 BitArray r; 2197 2198 r = this.dup; 2199 r ~= b; 2200 return r; 2201 } 2202 2203 /// 2204 @system unittest 2205 { 2206 bool[] ba = [1,0]; 2207 bool[] bb = [0,1,0]; 2208 2209 auto a = BitArray(ba); 2210 auto b = BitArray(bb); 2211 BitArray c; 2212 2213 c = (a ~ b); 2214 assert(c.length == 5); 2215 assert(c[0] == 1); 2216 assert(c[1] == 0); 2217 assert(c[2] == 0); 2218 assert(c[3] == 1); 2219 assert(c[4] == 0); 2220 2221 c = (a ~ true); 2222 assert(c.length == 3); 2223 assert(c[0] == 1); 2224 assert(c[1] == 0); 2225 assert(c[2] == 1); 2226 2227 c = (false ~ a); 2228 assert(c.length == 3); 2229 assert(c[0] == 0); 2230 assert(c[1] == 1); 2231 assert(c[2] == 0); 2232 } 2233 2234 // Rolls double word (upper, lower) to the right by n bits and returns the 2235 // lower word of the result. 2236 private static size_t rollRight()(size_t upper, size_t lower, size_t nbits) 2237 pure @safe nothrow @nogc 2238 in 2239 { 2240 assert(nbits < bitsPerSizeT, "nbits must be less than bitsPerSizeT"); 2241 } 2242 do 2243 { 2244 if (nbits == 0) 2245 return lower; 2246 return (upper << (bitsPerSizeT - nbits)) | (lower >> nbits); 2247 } 2248 2249 @safe unittest 2250 { 2251 static if (size_t.sizeof == 8) 2252 { 2253 size_t x = 0x12345678_90ABCDEF; 2254 size_t y = 0xFEDBCA09_87654321; 2255 2256 assert(rollRight(x, y, 32) == 0x90ABCDEF_FEDBCA09); 2257 assert(rollRight(y, x, 4) == 0x11234567_890ABCDE); 2258 } 2259 else static if (size_t.sizeof == 4) 2260 { 2261 size_t x = 0x12345678; 2262 size_t y = 0x90ABCDEF; 2263 2264 assert(rollRight(x, y, 16) == 0x567890AB); 2265 assert(rollRight(y, x, 4) == 0xF1234567); 2266 } 2267 else 2268 static assert(0, "Unsupported size_t width"); 2269 } 2270 2271 // Rolls double word (upper, lower) to the left by n bits and returns the 2272 // upper word of the result. 2273 private static size_t rollLeft()(size_t upper, size_t lower, size_t nbits) 2274 pure @safe nothrow @nogc 2275 in 2276 { 2277 assert(nbits < bitsPerSizeT, "nbits must be less than bitsPerSizeT"); 2278 } 2279 do 2280 { 2281 if (nbits == 0) 2282 return upper; 2283 return (upper << nbits) | (lower >> (bitsPerSizeT - nbits)); 2284 } 2285 2286 @safe unittest 2287 { 2288 static if (size_t.sizeof == 8) 2289 { 2290 size_t x = 0x12345678_90ABCDEF; 2291 size_t y = 0xFEDBCA09_87654321; 2292 2293 assert(rollLeft(x, y, 32) == 0x90ABCDEF_FEDBCA09); 2294 assert(rollLeft(y, x, 4) == 0xEDBCA098_76543211); 2295 } 2296 else static if (size_t.sizeof == 4) 2297 { 2298 size_t x = 0x12345678; 2299 size_t y = 0x90ABCDEF; 2300 2301 assert(rollLeft(x, y, 16) == 0x567890AB); 2302 assert(rollLeft(y, x, 4) == 0x0ABCDEF1); 2303 } 2304 } 2305 2306 /** 2307 * Operator `<<=` support. 2308 * 2309 * Shifts all the bits in the array to the left by the given number of 2310 * bits. The leftmost bits are dropped, and 0's are appended to the end 2311 * to fill up the vacant bits. 2312 * 2313 * $(RED Warning: unused bits in the final word up to the next word 2314 * boundary may be overwritten by this operation. It does not attempt to 2315 * preserve bits past the end of the array.) 2316 */ 2317 void opOpAssign(string op)(size_t nbits) @nogc pure nothrow 2318 if (op == "<<") 2319 { 2320 size_t wordsToShift = nbits / bitsPerSizeT; 2321 size_t bitsToShift = nbits % bitsPerSizeT; 2322 2323 if (wordsToShift < dim) 2324 { 2325 foreach_reverse (i; 1 .. dim - wordsToShift) 2326 { 2327 _ptr[i + wordsToShift] = rollLeft(_ptr[i], _ptr[i-1], 2328 bitsToShift); 2329 } 2330 _ptr[wordsToShift] = rollLeft(_ptr[0], 0, bitsToShift); 2331 } 2332 2333 import std.algorithm.comparison : min; 2334 foreach (i; 0 .. min(wordsToShift, dim)) 2335 { 2336 _ptr[i] = 0; 2337 } 2338 } 2339 2340 /** 2341 * Operator `>>=` support. 2342 * 2343 * Shifts all the bits in the array to the right by the given number of 2344 * bits. The rightmost bits are dropped, and 0's are inserted at the back 2345 * to fill up the vacant bits. 2346 * 2347 * $(RED Warning: unused bits in the final word up to the next word 2348 * boundary may be overwritten by this operation. It does not attempt to 2349 * preserve bits past the end of the array.) 2350 */ 2351 void opOpAssign(string op)(size_t nbits) @nogc pure nothrow 2352 if (op == ">>") 2353 { 2354 size_t wordsToShift = nbits / bitsPerSizeT; 2355 size_t bitsToShift = nbits % bitsPerSizeT; 2356 2357 if (wordsToShift + 1 < dim) 2358 { 2359 foreach (i; 0 .. dim - wordsToShift - 1) 2360 { 2361 _ptr[i] = rollRight(_ptr[i + wordsToShift + 1], 2362 _ptr[i + wordsToShift], bitsToShift); 2363 } 2364 } 2365 2366 // The last word needs some care, as it must shift in 0's from past the 2367 // end of the array. 2368 if (wordsToShift < dim) 2369 { 2370 if (bitsToShift == 0) 2371 _ptr[dim - wordsToShift - 1] = _ptr[dim - 1]; 2372 else 2373 { 2374 // Special case: if endBits == 0, then also endMask == 0. 2375 size_t lastWord = (endBits ? (_ptr[fullWords] & endMask) : _ptr[fullWords - 1]); 2376 _ptr[dim - wordsToShift - 1] = rollRight(0, lastWord, bitsToShift); 2377 } 2378 } 2379 2380 import std.algorithm.comparison : min; 2381 foreach (i; 0 .. min(wordsToShift, dim)) 2382 { 2383 _ptr[dim - i - 1] = 0; 2384 } 2385 } 2386 2387 // https://issues.dlang.org/show_bug.cgi?id=17467 2388 @system unittest 2389 { 2390 import std.algorithm.comparison : equal; 2391 import std.range : iota; 2392 2393 bool[] buf = new bool[64*3]; 2394 buf[0 .. 64] = true; 2395 BitArray b = BitArray(buf); 2396 assert(equal(b.bitsSet, iota(0, 64))); 2397 b <<= 64; 2398 assert(equal(b.bitsSet, iota(64, 128))); 2399 2400 buf = new bool[64*3]; 2401 buf[64*2 .. 64*3] = true; 2402 b = BitArray(buf); 2403 assert(equal(b.bitsSet, iota(64*2, 64*3))); 2404 b >>= 64; 2405 assert(equal(b.bitsSet, iota(64, 128))); 2406 } 2407 2408 // https://issues.dlang.org/show_bug.cgi?id=18134 2409 // shifting right when length is a multiple of 8 * size_t.sizeof. 2410 @system unittest 2411 { 2412 import std.algorithm.comparison : equal; 2413 import std.array : array; 2414 import std.range : repeat, iota; 2415 2416 immutable r = size_t.sizeof * 8; 2417 2418 BitArray a = true.repeat(r / 2).array; 2419 a >>= 0; 2420 assert(a.bitsSet.equal(iota(0, r / 2))); 2421 a >>= 1; 2422 assert(a.bitsSet.equal(iota(0, r / 2 - 1))); 2423 2424 BitArray b = true.repeat(r).array; 2425 b >>= 0; 2426 assert(b.bitsSet.equal(iota(0, r))); 2427 b >>= 1; 2428 assert(b.bitsSet.equal(iota(0, r - 1))); 2429 2430 BitArray c = true.repeat(2 * r).array; 2431 c >>= 0; 2432 assert(c.bitsSet.equal(iota(0, 2 * r))); 2433 c >>= 10; 2434 assert(c.bitsSet.equal(iota(0, 2 * r - 10))); 2435 } 2436 2437 /// 2438 @system unittest 2439 { 2440 import std.format : format; 2441 2442 auto b = BitArray([1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1]); 2443 2444 b <<= 1; 2445 assert(format("%b", b) == "01100_10101101"); 2446 2447 b >>= 1; 2448 assert(format("%b", b) == "11001_01011010"); 2449 2450 b <<= 4; 2451 assert(format("%b", b) == "00001_10010101"); 2452 2453 b >>= 5; 2454 assert(format("%b", b) == "10010_10100000"); 2455 2456 b <<= 13; 2457 assert(format("%b", b) == "00000_00000000"); 2458 2459 b = BitArray([1, 0, 1, 1, 0, 1, 1, 1]); 2460 b >>= 8; 2461 assert(format("%b", b) == "00000000"); 2462 2463 } 2464 2465 // Test multi-word case 2466 @system unittest 2467 { 2468 import std.format : format; 2469 2470 // This has to be long enough to occupy more than one size_t. On 64-bit 2471 // machines, this would be at least 64 bits. 2472 auto b = BitArray([ 2473 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2474 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 2475 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 2476 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2477 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 2478 ]); 2479 b <<= 8; 2480 assert(format("%b", b) == 2481 "00000000_10000000_"~ 2482 "11000000_11100000_"~ 2483 "11110000_11111000_"~ 2484 "11111100_11111110_"~ 2485 "11111111_10101010"); 2486 2487 // Test right shift of more than one size_t's worth of bits 2488 b <<= 68; 2489 assert(format("%b", b) == 2490 "00000000_00000000_"~ 2491 "00000000_00000000_"~ 2492 "00000000_00000000_"~ 2493 "00000000_00000000_"~ 2494 "00000000_00001000"); 2495 2496 b = BitArray([ 2497 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2498 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 2499 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 2500 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2501 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 2502 ]); 2503 b >>= 8; 2504 assert(format("%b", b) == 2505 "11000000_11100000_"~ 2506 "11110000_11111000_"~ 2507 "11111100_11111110_"~ 2508 "11111111_10101010_"~ 2509 "01010101_00000000"); 2510 2511 // Test left shift of more than 1 size_t's worth of bits 2512 b >>= 68; 2513 assert(format("%b", b) == 2514 "01010000_00000000_"~ 2515 "00000000_00000000_"~ 2516 "00000000_00000000_"~ 2517 "00000000_00000000_"~ 2518 "00000000_00000000"); 2519 } 2520 2521 /*************************************** 2522 * Return a string representation of this BitArray. 2523 * 2524 * Two format specifiers are supported: 2525 * $(LI $(B %s) which prints the bits as an array, and) 2526 * $(LI $(B %b) which prints the bits as 8-bit byte packets) 2527 * separated with an underscore. 2528 * 2529 * Params: 2530 * sink = A `char` accepting 2531 * $(REF_ALTTEXT output range, isOutputRange, std, range, primitives). 2532 * fmt = A $(REF FormatSpec, std,format) which controls how the data 2533 * is displayed. 2534 */ 2535 void toString(W)(ref W sink, scope const ref FormatSpec!char fmt) const 2536 if (isOutputRange!(W, char)) 2537 { 2538 const spec = fmt.spec; 2539 switch (spec) 2540 { 2541 case 'b': 2542 return formatBitString(sink); 2543 case 's': 2544 return formatBitArray(sink); 2545 default: 2546 throw new Exception("Unknown format specifier: %" ~ spec); 2547 } 2548 } 2549 2550 /// 2551 @system pure unittest 2552 { 2553 import std.format : format; 2554 2555 auto b = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 2556 2557 auto s1 = format("%s", b); 2558 assert(s1 == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 2559 2560 auto s2 = format("%b", b); 2561 assert(s2 == "00001111_00001111"); 2562 } 2563 2564 /*************************************** 2565 * Return a lazy range of the indices of set bits. 2566 */ 2567 @property auto bitsSet() const nothrow 2568 { 2569 import std.algorithm.iteration : filter, map, joiner; 2570 import std.range : iota, chain; 2571 2572 return chain( 2573 iota(fullWords) 2574 .filter!(i => _ptr[i])() 2575 .map!(i => BitsSet!size_t(_ptr[i], i * bitsPerSizeT))() 2576 .joiner(), 2577 iota(fullWords * bitsPerSizeT, _len) 2578 .filter!(i => this[i])() 2579 ); 2580 } 2581 2582 /// 2583 @system unittest 2584 { 2585 import std.algorithm.comparison : equal; 2586 2587 auto b1 = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 2588 assert(b1.bitsSet.equal([4, 5, 6, 7, 12, 13, 14, 15])); 2589 2590 BitArray b2; 2591 b2.length = 1000; 2592 b2[333] = true; 2593 b2[666] = true; 2594 b2[999] = true; 2595 assert(b2.bitsSet.equal([333, 666, 999])); 2596 } 2597 2598 @system unittest 2599 { 2600 import std.algorithm.comparison : equal; 2601 import std.range : iota; 2602 2603 BitArray b; 2604 enum wordBits = size_t.sizeof * 8; 2605 b = BitArray([size_t.max], 0); 2606 assert(b.bitsSet.empty); 2607 b = BitArray([size_t.max], 1); 2608 assert(b.bitsSet.equal([0])); 2609 b = BitArray([size_t.max], wordBits); 2610 assert(b.bitsSet.equal(iota(wordBits))); 2611 b = BitArray([size_t.max, size_t.max], wordBits); 2612 assert(b.bitsSet.equal(iota(wordBits))); 2613 b = BitArray([size_t.max, size_t.max], wordBits + 1); 2614 assert(b.bitsSet.equal(iota(wordBits + 1))); 2615 b = BitArray([size_t.max, size_t.max], wordBits * 2); 2616 assert(b.bitsSet.equal(iota(wordBits * 2))); 2617 } 2618 2619 // https://issues.dlang.org/show_bug.cgi?id=20241 2620 @system unittest 2621 { 2622 BitArray ba; 2623 ba.length = 2; 2624 ba[1] = 1; 2625 ba.length = 1; 2626 assert(ba.bitsSet.empty); 2627 } 2628 2629 private void formatBitString(Writer)(auto ref Writer sink) const 2630 { 2631 if (!length) 2632 return; 2633 2634 auto leftover = _len % 8; 2635 foreach (idx; 0 .. leftover) 2636 { 2637 put(sink, cast(char)(this[idx] + '0')); 2638 } 2639 2640 if (leftover && _len > 8) 2641 put(sink, "_"); 2642 2643 size_t count; 2644 foreach (idx; leftover .. _len) 2645 { 2646 put(sink, cast(char)(this[idx] + '0')); 2647 if (++count == 8 && idx != _len - 1) 2648 { 2649 put(sink, "_"); 2650 count = 0; 2651 } 2652 } 2653 } 2654 2655 private void formatBitArray(Writer)(auto ref Writer sink) const 2656 { 2657 put(sink, "["); 2658 foreach (idx; 0 .. _len) 2659 { 2660 put(sink, cast(char)(this[idx] + '0')); 2661 if (idx + 1 < _len) 2662 put(sink, ", "); 2663 } 2664 put(sink, "]"); 2665 } 2666 2667 // https://issues.dlang.org/show_bug.cgi?id=20639 2668 // Separate @nogc test because public tests use array literals 2669 // (and workarounds needlessly uglify those examples) 2670 @system @nogc unittest 2671 { 2672 size_t[2] buffer; 2673 BitArray b = BitArray(buffer[], buffer.sizeof * 8); 2674 2675 b[] = true; 2676 b[0 .. 1] = true; 2677 b.flip(); 2678 b.flip(1); 2679 cast(void) b.count(); 2680 } 2681 } 2682 2683 /// Slicing & bitsSet 2684 @system unittest 2685 { 2686 import std.algorithm.comparison : equal; 2687 import std.range : iota; 2688 2689 bool[] buf = new bool[64 * 3]; 2690 buf[0 .. 64] = true; 2691 BitArray b = BitArray(buf); 2692 assert(b.bitsSet.equal(iota(0, 64))); 2693 b <<= 64; 2694 assert(b.bitsSet.equal(iota(64, 128))); 2695 } 2696 2697 /// Concatenation and appending 2698 @system unittest 2699 { 2700 import std.algorithm.comparison : equal; 2701 2702 auto b = BitArray([1, 0]); 2703 b ~= true; 2704 assert(b[2] == 1); 2705 b ~= BitArray([0, 1]); 2706 auto c = BitArray([1, 0, 1, 0, 1]); 2707 assert(b == c); 2708 assert(b.bitsSet.equal([0, 2, 4])); 2709 } 2710 2711 /// Bit flipping 2712 @system unittest 2713 { 2714 import std.algorithm.comparison : equal; 2715 2716 auto b = BitArray([1, 1, 0, 1]); 2717 b &= BitArray([0, 1, 1, 0]); 2718 assert(b.bitsSet.equal([1])); 2719 b.flip; 2720 assert(b.bitsSet.equal([0, 2, 3])); 2721 } 2722 2723 /// String format of bitarrays 2724 @system unittest 2725 { 2726 import std.format : format; 2727 auto b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 2728 assert(format("%b", b) == "1_00001111_00001111"); 2729 } 2730 2731 /// 2732 @system unittest 2733 { 2734 import std.format : format; 2735 2736 BitArray b; 2737 2738 b = BitArray([]); 2739 assert(format("%s", b) == "[]"); 2740 assert(format("%b", b) is null); 2741 2742 b = BitArray([1]); 2743 assert(format("%s", b) == "[1]"); 2744 assert(format("%b", b) == "1"); 2745 2746 b = BitArray([0, 0, 0, 0]); 2747 assert(format("%b", b) == "0000"); 2748 2749 b = BitArray([0, 0, 0, 0, 1, 1, 1, 1]); 2750 assert(format("%s", b) == "[0, 0, 0, 0, 1, 1, 1, 1]"); 2751 assert(format("%b", b) == "00001111"); 2752 2753 b = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 2754 assert(format("%s", b) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 2755 assert(format("%b", b) == "00001111_00001111"); 2756 2757 b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1]); 2758 assert(format("%b", b) == "1_00001111"); 2759 2760 b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 2761 assert(format("%b", b) == "1_00001111_00001111"); 2762 } 2763 2764 /++ 2765 Swaps the endianness of the given integral value or character. 2766 +/ 2767 T swapEndian(T)(const T val) @safe pure nothrow @nogc 2768 if (isIntegral!T || isSomeChar!T || isBoolean!T) 2769 { 2770 import core.bitop : bswap, byteswap; 2771 static if (val.sizeof == 1) 2772 return val; 2773 else static if (T.sizeof == 2) 2774 return cast(T) byteswap(cast(ushort) val); 2775 else static if (T.sizeof == 4) 2776 return cast(T) bswap(cast(uint) val); 2777 else static if (T.sizeof == 8) 2778 return cast(T) bswap(cast(ulong) val); 2779 else 2780 static assert(0, T.stringof ~ " unsupported by swapEndian."); 2781 } 2782 2783 /// 2784 @safe unittest 2785 { 2786 assert(42.swapEndian == 704643072); 2787 assert(42.swapEndian.swapEndian == 42); // reflexive 2788 assert(1.swapEndian == 16777216); 2789 2790 assert(true.swapEndian == true); 2791 assert(byte(10).swapEndian == 10); 2792 assert(char(10).swapEndian == 10); 2793 2794 assert(ushort(10).swapEndian == 2560); 2795 assert(long(10).swapEndian == 720575940379279360); 2796 assert(ulong(10).swapEndian == 720575940379279360); 2797 } 2798 2799 @safe unittest 2800 { 2801 import std.meta; 2802 import std.stdio; 2803 static foreach (T; AliasSeq!(bool, byte, ubyte, short, ushort, int, uint, long, ulong, char, wchar, dchar)) 2804 {{ 2805 scope(failure) writeln("Failed type: ", T.stringof); 2806 T val; 2807 const T cval; 2808 immutable T ival; 2809 2810 assert(swapEndian(swapEndian(val)) == val); 2811 assert(swapEndian(swapEndian(cval)) == cval); 2812 assert(swapEndian(swapEndian(ival)) == ival); 2813 assert(swapEndian(swapEndian(T.min)) == T.min); 2814 assert(swapEndian(swapEndian(T.max)) == T.max); 2815 2816 // Check CTFE compiles. 2817 static assert(swapEndian(swapEndian(T(1))) is T(1)); 2818 2819 foreach (i; 2 .. 10) 2820 { 2821 immutable T maxI = cast(T)(T.max / i); 2822 immutable T minI = cast(T)(T.min / i); 2823 2824 assert(swapEndian(swapEndian(maxI)) == maxI); 2825 2826 static if (isSigned!T) 2827 assert(swapEndian(swapEndian(minI)) == minI); 2828 } 2829 2830 static if (isSigned!T) 2831 assert(swapEndian(swapEndian(cast(T) 0)) == 0); 2832 2833 // used to trigger https://issues.dlang.org/show_bug.cgi?id=6354 2834 static if (T.sizeof > 1 && isUnsigned!T) 2835 { 2836 T left = 0xffU; 2837 left <<= (T.sizeof - 1) * 8; 2838 T right = 0xffU; 2839 2840 for (size_t i = 1; i < T.sizeof; ++i) 2841 { 2842 assert(swapEndian(left) == right); 2843 assert(swapEndian(right) == left); 2844 left >>= 8; 2845 right <<= 8; 2846 } 2847 } 2848 }} 2849 } 2850 2851 2852 private union EndianSwapper(T) 2853 if (canSwapEndianness!T) 2854 { 2855 Unqual!T value; 2856 ubyte[T.sizeof] array; 2857 2858 static if (is(FloatingPointTypeOf!(Unqual!T) == float)) 2859 uint intValue; 2860 else static if (is(FloatingPointTypeOf!(Unqual!T) == double)) 2861 ulong intValue; 2862 2863 } 2864 2865 // Can't use EndianSwapper union during CTFE. 2866 private auto ctfeRead(T)(const ubyte[T.sizeof] array) 2867 if (__traits(isIntegral, T)) 2868 { 2869 Unqual!T result; 2870 version (LittleEndian) 2871 foreach_reverse (b; array) 2872 result = cast(Unqual!T) ((result << 8) | b); 2873 else 2874 foreach (b; array) 2875 result = cast(Unqual!T) ((result << 8) | b); 2876 return cast(T) result; 2877 } 2878 2879 // Can't use EndianSwapper union during CTFE. 2880 private auto ctfeBytes(T)(const T value) 2881 if (__traits(isIntegral, T)) 2882 { 2883 ubyte[T.sizeof] result; 2884 Unqual!T tmp = value; 2885 version (LittleEndian) 2886 { 2887 foreach (i; 0 .. T.sizeof) 2888 { 2889 result[i] = cast(ubyte) tmp; 2890 tmp = cast(Unqual!T) (tmp >>> 8); 2891 } 2892 } 2893 else 2894 { 2895 foreach_reverse (i; 0 .. T.sizeof) 2896 { 2897 result[i] = cast(ubyte) tmp; 2898 tmp = cast(Unqual!T) (tmp >>> 8); 2899 } 2900 } 2901 return result; 2902 } 2903 2904 /++ 2905 Converts the given value from the native endianness to big endian and 2906 returns it as a `ubyte[n]` where `n` is the size of the given type. 2907 2908 Returning a `ubyte[n]` helps prevent accidentally using a swapped value 2909 as a regular one (and in the case of floating point values, it's necessary, 2910 because the FPU will mess up any swapped floating point values. So, you 2911 can't actually have swapped floating point values as floating point values). 2912 2913 `real` is not supported, because its size is implementation-dependent 2914 and therefore could vary from machine to machine (which could make it 2915 unusable if you tried to transfer it to another machine). 2916 +/ 2917 auto nativeToBigEndian(T)(const T val) @safe pure nothrow @nogc 2918 if (canSwapEndianness!T) 2919 { 2920 version (LittleEndian) 2921 return nativeToEndianImpl!true(val); 2922 else 2923 return nativeToEndianImpl!false(val); 2924 } 2925 2926 /// 2927 @safe unittest 2928 { 2929 int i = 12345; 2930 ubyte[4] swappedI = nativeToBigEndian(i); 2931 assert(i == bigEndianToNative!int(swappedI)); 2932 2933 float f = 123.45f; 2934 ubyte[4] swappedF = nativeToBigEndian(f); 2935 assert(f == bigEndianToNative!float(swappedF)); 2936 2937 const float cf = 123.45f; 2938 ubyte[4] swappedCF = nativeToBigEndian(cf); 2939 assert(cf == bigEndianToNative!float(swappedCF)); 2940 2941 double d = 123.45; 2942 ubyte[8] swappedD = nativeToBigEndian(d); 2943 assert(d == bigEndianToNative!double(swappedD)); 2944 2945 const double cd = 123.45; 2946 ubyte[8] swappedCD = nativeToBigEndian(cd); 2947 assert(cd == bigEndianToNative!double(swappedCD)); 2948 } 2949 2950 private auto nativeToEndianImpl(bool swap, T)(const T val) @safe pure nothrow @nogc 2951 if (__traits(isIntegral, T)) 2952 { 2953 if (!__ctfe) 2954 { 2955 static if (swap) 2956 return EndianSwapper!T(swapEndian(val)).array; 2957 else 2958 return EndianSwapper!T(val).array; 2959 } 2960 else 2961 { 2962 // Can't use EndianSwapper in CTFE. 2963 static if (swap) 2964 return ctfeBytes(swapEndian(val)); 2965 else 2966 return ctfeBytes(val); 2967 } 2968 } 2969 2970 @safe unittest 2971 { 2972 import std.meta; 2973 import std.stdio; 2974 static foreach (T; AliasSeq!(bool, byte, ubyte, short, ushort, int, uint, long, ulong, 2975 char, wchar, dchar 2976 /* The trouble here is with floats and doubles being compared against nan 2977 * using a bit compare. There are two kinds of nans, quiet and signaling. 2978 * When a nan passes through the x87, it converts signaling to quiet. 2979 * When a nan passes through the XMM, it does not convert signaling to quiet. 2980 * float.init is a signaling nan. 2981 * The binary API sometimes passes the data through the XMM, sometimes through 2982 * the x87, meaning these will fail the 'is' bit compare under some circumstances. 2983 * I cannot think of a fix for this that makes consistent sense. 2984 */ 2985 /*,float, double*/)) 2986 {{ 2987 scope(failure) writeln("Failed type: ", T.stringof); 2988 T val; 2989 const T cval; 2990 immutable T ival; 2991 2992 //is instead of == because of NaN for floating point values. 2993 assert(bigEndianToNative!T(nativeToBigEndian(val)) is val); 2994 assert(bigEndianToNative!T(nativeToBigEndian(cval)) is cval); 2995 assert(bigEndianToNative!T(nativeToBigEndian(ival)) is ival); 2996 assert(bigEndianToNative!T(nativeToBigEndian(T.min)) == T.min); 2997 assert(bigEndianToNative!T(nativeToBigEndian(T.max)) == T.max); 2998 2999 //Check CTFE compiles. 3000 static assert(bigEndianToNative!T(nativeToBigEndian(T(1))) is T(1)); 3001 3002 static if (isSigned!T) 3003 assert(bigEndianToNative!T(nativeToBigEndian(cast(T) 0)) == 0); 3004 3005 static if (!is(T == bool)) 3006 { 3007 foreach (i; [2, 4, 6, 7, 9, 11]) 3008 { 3009 immutable T maxI = cast(T)(T.max / i); 3010 immutable T minI = cast(T)(T.min / i); 3011 3012 assert(bigEndianToNative!T(nativeToBigEndian(maxI)) == maxI); 3013 3014 static if (T.sizeof > 1) 3015 assert(nativeToBigEndian(maxI) != nativeToLittleEndian(maxI)); 3016 else 3017 assert(nativeToBigEndian(maxI) == nativeToLittleEndian(maxI)); 3018 3019 static if (isSigned!T) 3020 { 3021 assert(bigEndianToNative!T(nativeToBigEndian(minI)) == minI); 3022 3023 static if (T.sizeof > 1) 3024 assert(nativeToBigEndian(minI) != nativeToLittleEndian(minI)); 3025 else 3026 assert(nativeToBigEndian(minI) == nativeToLittleEndian(minI)); 3027 } 3028 } 3029 } 3030 3031 static if (isUnsigned!T || T.sizeof == 1 || is(T == wchar)) 3032 assert(nativeToBigEndian(T.max) == nativeToLittleEndian(T.max)); 3033 else 3034 assert(nativeToBigEndian(T.max) != nativeToLittleEndian(T.max)); 3035 3036 static if (isUnsigned!T || T.sizeof == 1 || isSomeChar!T) 3037 assert(nativeToBigEndian(T.min) == nativeToLittleEndian(T.min)); 3038 else 3039 assert(nativeToBigEndian(T.min) != nativeToLittleEndian(T.min)); 3040 }} 3041 } 3042 3043 3044 /++ 3045 Converts the given value from big endian to the native endianness and 3046 returns it. The value is given as a `ubyte[n]` where `n` is the size 3047 of the target type. You must give the target type as a template argument, 3048 because there are multiple types with the same size and so the type of the 3049 argument is not enough to determine the return type. 3050 3051 Taking a `ubyte[n]` helps prevent accidentally using a swapped value 3052 as a regular one (and in the case of floating point values, it's necessary, 3053 because the FPU will mess up any swapped floating point values. So, you 3054 can't actually have swapped floating point values as floating point values). 3055 +/ 3056 T bigEndianToNative(T, size_t n)(ubyte[n] val) @safe pure nothrow @nogc 3057 if (canSwapEndianness!T && n == T.sizeof) 3058 { 3059 version (LittleEndian) 3060 return endianToNativeImpl!(true, T, n)(val); 3061 else 3062 return endianToNativeImpl!(false, T, n)(val); 3063 } 3064 3065 /// 3066 @safe unittest 3067 { 3068 ushort i = 12345; 3069 ubyte[2] swappedI = nativeToBigEndian(i); 3070 assert(i == bigEndianToNative!ushort(swappedI)); 3071 3072 dchar c = 'D'; 3073 ubyte[4] swappedC = nativeToBigEndian(c); 3074 assert(c == bigEndianToNative!dchar(swappedC)); 3075 } 3076 3077 /++ 3078 Converts the given value from the native endianness to little endian and 3079 returns it as a `ubyte[n]` where `n` is the size of the given type. 3080 3081 Returning a `ubyte[n]` helps prevent accidentally using a swapped value 3082 as a regular one (and in the case of floating point values, it's necessary, 3083 because the FPU will mess up any swapped floating point values. So, you 3084 can't actually have swapped floating point values as floating point values). 3085 +/ 3086 auto nativeToLittleEndian(T)(const T val) @safe pure nothrow @nogc 3087 if (canSwapEndianness!T) 3088 { 3089 version (BigEndian) 3090 return nativeToEndianImpl!true(val); 3091 else 3092 return nativeToEndianImpl!false(val); 3093 } 3094 3095 /// 3096 @safe unittest 3097 { 3098 int i = 12345; 3099 ubyte[4] swappedI = nativeToLittleEndian(i); 3100 assert(i == littleEndianToNative!int(swappedI)); 3101 3102 double d = 123.45; 3103 ubyte[8] swappedD = nativeToLittleEndian(d); 3104 assert(d == littleEndianToNative!double(swappedD)); 3105 } 3106 3107 @safe unittest 3108 { 3109 import std.meta; 3110 import std.stdio; 3111 static foreach (T; AliasSeq!(bool, byte, ubyte, short, ushort, int, uint, long, ulong, 3112 char, wchar, dchar/*, 3113 float, double*/)) 3114 {{ 3115 scope(failure) writeln("Failed type: ", T.stringof); 3116 T val; 3117 const T cval; 3118 immutable T ival; 3119 3120 //is instead of == because of NaN for floating point values. 3121 assert(littleEndianToNative!T(nativeToLittleEndian(val)) is val); 3122 assert(littleEndianToNative!T(nativeToLittleEndian(cval)) is cval); 3123 assert(littleEndianToNative!T(nativeToLittleEndian(ival)) is ival); 3124 assert(littleEndianToNative!T(nativeToLittleEndian(T.min)) == T.min); 3125 assert(littleEndianToNative!T(nativeToLittleEndian(T.max)) == T.max); 3126 3127 //Check CTFE compiles. 3128 static assert(littleEndianToNative!T(nativeToLittleEndian(T(1))) is T(1)); 3129 3130 static if (isSigned!T) 3131 assert(littleEndianToNative!T(nativeToLittleEndian(cast(T) 0)) == 0); 3132 3133 static if (!is(T == bool)) 3134 { 3135 foreach (i; 2 .. 10) 3136 { 3137 immutable T maxI = cast(T)(T.max / i); 3138 immutable T minI = cast(T)(T.min / i); 3139 3140 assert(littleEndianToNative!T(nativeToLittleEndian(maxI)) == maxI); 3141 3142 static if (isSigned!T) 3143 assert(littleEndianToNative!T(nativeToLittleEndian(minI)) == minI); 3144 } 3145 } 3146 }} 3147 } 3148 3149 3150 /++ 3151 Converts the given value from little endian to the native endianness and 3152 returns it. The value is given as a `ubyte[n]` where `n` is the size 3153 of the target type. You must give the target type as a template argument, 3154 because there are multiple types with the same size and so the type of the 3155 argument is not enough to determine the return type. 3156 3157 Taking a `ubyte[n]` helps prevent accidentally using a swapped value 3158 as a regular one (and in the case of floating point values, it's necessary, 3159 because the FPU will mess up any swapped floating point values. So, you 3160 can't actually have swapped floating point values as floating point values). 3161 3162 `real` is not supported, because its size is implementation-dependent 3163 and therefore could vary from machine to machine (which could make it 3164 unusable if you tried to transfer it to another machine). 3165 +/ 3166 T littleEndianToNative(T, size_t n)(ubyte[n] val) @safe pure nothrow @nogc 3167 if (canSwapEndianness!T && n == T.sizeof) 3168 { 3169 version (BigEndian) 3170 return endianToNativeImpl!(true, T, n)(val); 3171 else 3172 return endianToNativeImpl!(false, T, n)(val); 3173 } 3174 3175 /// 3176 @safe unittest 3177 { 3178 ushort i = 12345; 3179 ubyte[2] swappedI = nativeToLittleEndian(i); 3180 assert(i == littleEndianToNative!ushort(swappedI)); 3181 3182 dchar c = 'D'; 3183 ubyte[4] swappedC = nativeToLittleEndian(c); 3184 assert(c == littleEndianToNative!dchar(swappedC)); 3185 } 3186 3187 private T endianToNativeImpl(bool swap, T, size_t n)(ubyte[n] val) @nogc nothrow pure @safe 3188 if (__traits(isIntegral, T) && n == T.sizeof) 3189 { 3190 if (!__ctfe) 3191 { 3192 EndianSwapper!T es = { array: val }; 3193 static if (swap) 3194 return swapEndian(es.value); 3195 else 3196 return es.value; 3197 } 3198 else 3199 { 3200 static if (swap) 3201 return swapEndian(ctfeRead!T(val)); 3202 else 3203 return ctfeRead!T(val); 3204 } 3205 } 3206 3207 private auto nativeToEndianImpl(bool swap, T)(const T val) @trusted pure nothrow @nogc 3208 if (isFloatOrDouble!T) 3209 { 3210 if (!__ctfe) 3211 { 3212 EndianSwapper!T es = EndianSwapper!T(val); 3213 static if (swap) 3214 es.intValue = swapEndian(es.intValue); 3215 return es.array; 3216 } 3217 else 3218 { 3219 static if (T.sizeof == 4) 3220 uint intValue = *cast(const uint*) &val; 3221 else static if (T.sizeof == 8) 3222 ulong intValue = *cast(const ulong*) & val; 3223 static if (swap) 3224 intValue = swapEndian(intValue); 3225 return ctfeBytes(intValue); 3226 } 3227 } 3228 3229 private auto endianToNativeImpl(bool swap, T, size_t n)(ubyte[n] val) @trusted pure nothrow @nogc 3230 if (isFloatOrDouble!T && n == T.sizeof) 3231 { 3232 if (!__ctfe) 3233 { 3234 EndianSwapper!T es = { array: val }; 3235 static if (swap) 3236 es.intValue = swapEndian(es.intValue); 3237 return es.value; 3238 } 3239 else 3240 { 3241 static if (n == 4) 3242 uint x = ctfeRead!uint(val); 3243 else static if (n == 8) 3244 ulong x = ctfeRead!ulong(val); 3245 static if (swap) 3246 x = swapEndian(x); 3247 return *cast(T*) &x; 3248 } 3249 } 3250 3251 private template isFloatOrDouble(T) 3252 { 3253 enum isFloatOrDouble = isFloatingPoint!T && 3254 !is(immutable FloatingPointTypeOf!T == immutable real); 3255 } 3256 3257 @safe unittest 3258 { 3259 import std.meta; 3260 static foreach (T; AliasSeq!(float, double)) 3261 { 3262 static assert(isFloatOrDouble!(T)); 3263 static assert(isFloatOrDouble!(const T)); 3264 static assert(isFloatOrDouble!(immutable T)); 3265 static assert(isFloatOrDouble!(shared T)); 3266 static assert(isFloatOrDouble!(shared(const T))); 3267 static assert(isFloatOrDouble!(shared(immutable T))); 3268 } 3269 3270 static assert(!isFloatOrDouble!(real)); 3271 static assert(!isFloatOrDouble!(const real)); 3272 static assert(!isFloatOrDouble!(immutable real)); 3273 static assert(!isFloatOrDouble!(shared real)); 3274 static assert(!isFloatOrDouble!(shared(const real))); 3275 static assert(!isFloatOrDouble!(shared(immutable real))); 3276 } 3277 3278 private template canSwapEndianness(T) 3279 { 3280 enum canSwapEndianness = isIntegral!T || 3281 isSomeChar!T || 3282 isBoolean!T || 3283 isFloatOrDouble!T; 3284 } 3285 3286 @safe unittest 3287 { 3288 import std.meta; 3289 static foreach (T; AliasSeq!(bool, ubyte, byte, ushort, short, uint, int, ulong, 3290 long, char, wchar, dchar, float, double)) 3291 { 3292 static assert(canSwapEndianness!(T)); 3293 static assert(canSwapEndianness!(const T)); 3294 static assert(canSwapEndianness!(immutable T)); 3295 static assert(canSwapEndianness!(shared(T))); 3296 static assert(canSwapEndianness!(shared(const T))); 3297 static assert(canSwapEndianness!(shared(immutable T))); 3298 } 3299 3300 //! 3301 static foreach (T; AliasSeq!(real, string, wstring, dstring)) 3302 { 3303 static assert(!canSwapEndianness!(T)); 3304 static assert(!canSwapEndianness!(const T)); 3305 static assert(!canSwapEndianness!(immutable T)); 3306 static assert(!canSwapEndianness!(shared(T))); 3307 static assert(!canSwapEndianness!(shared(const T))); 3308 static assert(!canSwapEndianness!(shared(immutable T))); 3309 } 3310 } 3311 3312 /++ 3313 Takes a range of `ubyte`s and converts the first `T.sizeof` bytes to 3314 `T`. The value returned is converted from the given endianness to the 3315 native endianness. The range is not consumed. 3316 3317 Params: 3318 T = The integral type to convert the first `T.sizeof` bytes to. 3319 endianness = The endianness that the bytes are assumed to be in. 3320 range = The range to read from. 3321 index = The index to start reading from (instead of starting at the 3322 front). If index is a pointer, then it is updated to the index 3323 after the bytes read. The overloads with index are only 3324 available if `hasSlicing!R` is `true`. 3325 +/ 3326 3327 T peek(T, Endian endianness = Endian.bigEndian, R)(R range) 3328 if (canSwapEndianness!T && 3329 isForwardRange!R && 3330 is(ElementType!R : const ubyte)) 3331 { 3332 static if (hasSlicing!R) 3333 const ubyte[T.sizeof] bytes = range[0 .. T.sizeof]; 3334 else 3335 { 3336 ubyte[T.sizeof] bytes; 3337 //Make sure that range is not consumed, even if it's a class. 3338 range = range.save; 3339 3340 foreach (ref e; bytes) 3341 { 3342 e = range.front; 3343 range.popFront(); 3344 } 3345 } 3346 3347 static if (endianness == Endian.bigEndian) 3348 return bigEndianToNative!T(bytes); 3349 else 3350 return littleEndianToNative!T(bytes); 3351 } 3352 3353 /++ Ditto +/ 3354 T peek(T, Endian endianness = Endian.bigEndian, R)(R range, size_t index) 3355 if (canSwapEndianness!T && 3356 isForwardRange!R && 3357 hasSlicing!R && 3358 is(ElementType!R : const ubyte)) 3359 { 3360 return peek!(T, endianness)(range, &index); 3361 } 3362 3363 /++ Ditto +/ 3364 T peek(T, Endian endianness = Endian.bigEndian, R)(R range, size_t* index) 3365 if (canSwapEndianness!T && 3366 isForwardRange!R && 3367 hasSlicing!R && 3368 is(ElementType!R : const ubyte)) 3369 { 3370 assert(index, "index must not point to null"); 3371 3372 immutable begin = *index; 3373 immutable end = begin + T.sizeof; 3374 const ubyte[T.sizeof] bytes = range[begin .. end]; 3375 *index = end; 3376 3377 static if (endianness == Endian.bigEndian) 3378 return bigEndianToNative!T(bytes); 3379 else 3380 return littleEndianToNative!T(bytes); 3381 } 3382 3383 /// 3384 @system unittest 3385 { 3386 ubyte[] buffer = [1, 5, 22, 9, 44, 255, 8]; 3387 assert(buffer.peek!uint() == 17110537); 3388 assert(buffer.peek!ushort() == 261); 3389 assert(buffer.peek!ubyte() == 1); 3390 3391 assert(buffer.peek!uint(2) == 369700095); 3392 assert(buffer.peek!ushort(2) == 5641); 3393 assert(buffer.peek!ubyte(2) == 22); 3394 3395 size_t index = 0; 3396 assert(buffer.peek!ushort(&index) == 261); 3397 assert(index == 2); 3398 3399 assert(buffer.peek!uint(&index) == 369700095); 3400 assert(index == 6); 3401 3402 assert(buffer.peek!ubyte(&index) == 8); 3403 assert(index == 7); 3404 } 3405 3406 /// 3407 @safe unittest 3408 { 3409 import std.algorithm.iteration : filter; 3410 ubyte[] buffer = [1, 5, 22, 9, 44, 255, 7]; 3411 auto range = filter!"true"(buffer); 3412 assert(range.peek!uint() == 17110537); 3413 assert(range.peek!ushort() == 261); 3414 assert(range.peek!ubyte() == 1); 3415 } 3416 3417 @system unittest 3418 { 3419 { 3420 //bool 3421 ubyte[] buffer = [0, 1]; 3422 assert(buffer.peek!bool() == false); 3423 assert(buffer.peek!bool(1) == true); 3424 3425 size_t index = 0; 3426 assert(buffer.peek!bool(&index) == false); 3427 assert(index == 1); 3428 3429 assert(buffer.peek!bool(&index) == true); 3430 assert(index == 2); 3431 } 3432 3433 { 3434 //char (8bit) 3435 ubyte[] buffer = [97, 98, 99, 100]; 3436 assert(buffer.peek!char() == 'a'); 3437 assert(buffer.peek!char(1) == 'b'); 3438 3439 size_t index = 0; 3440 assert(buffer.peek!char(&index) == 'a'); 3441 assert(index == 1); 3442 3443 assert(buffer.peek!char(&index) == 'b'); 3444 assert(index == 2); 3445 } 3446 3447 { 3448 //wchar (16bit - 2x ubyte) 3449 ubyte[] buffer = [1, 5, 32, 29, 1, 7]; 3450 assert(buffer.peek!wchar() == 'ą'); 3451 assert(buffer.peek!wchar(2) == '”'); 3452 assert(buffer.peek!wchar(4) == 'ć'); 3453 3454 size_t index = 0; 3455 assert(buffer.peek!wchar(&index) == 'ą'); 3456 assert(index == 2); 3457 3458 assert(buffer.peek!wchar(&index) == '”'); 3459 assert(index == 4); 3460 3461 assert(buffer.peek!wchar(&index) == 'ć'); 3462 assert(index == 6); 3463 } 3464 3465 { 3466 //dchar (32bit - 4x ubyte) 3467 ubyte[] buffer = [0, 0, 1, 5, 0, 0, 32, 29, 0, 0, 1, 7]; 3468 assert(buffer.peek!dchar() == 'ą'); 3469 assert(buffer.peek!dchar(4) == '”'); 3470 assert(buffer.peek!dchar(8) == 'ć'); 3471 3472 size_t index = 0; 3473 assert(buffer.peek!dchar(&index) == 'ą'); 3474 assert(index == 4); 3475 3476 assert(buffer.peek!dchar(&index) == '”'); 3477 assert(index == 8); 3478 3479 assert(buffer.peek!dchar(&index) == 'ć'); 3480 assert(index == 12); 3481 } 3482 3483 { 3484 //float (32bit - 4x ubyte) 3485 ubyte[] buffer = [66, 0, 0, 0, 65, 200, 0, 0]; 3486 assert(buffer.peek!float()== 32.0); 3487 assert(buffer.peek!float(4) == 25.0f); 3488 3489 size_t index = 0; 3490 assert(buffer.peek!float(&index) == 32.0f); 3491 assert(index == 4); 3492 3493 assert(buffer.peek!float(&index) == 25.0f); 3494 assert(index == 8); 3495 } 3496 3497 { 3498 //double (64bit - 8x ubyte) 3499 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3500 assert(buffer.peek!double() == 32.0); 3501 assert(buffer.peek!double(8) == 25.0); 3502 3503 size_t index = 0; 3504 assert(buffer.peek!double(&index) == 32.0); 3505 assert(index == 8); 3506 3507 assert(buffer.peek!double(&index) == 25.0); 3508 assert(index == 16); 3509 } 3510 3511 { 3512 //enum 3513 ubyte[] buffer = [0, 0, 0, 10, 0, 0, 0, 20, 0, 0, 0, 30]; 3514 3515 enum Foo 3516 { 3517 one = 10, 3518 two = 20, 3519 three = 30 3520 } 3521 3522 assert(buffer.peek!Foo() == Foo.one); 3523 assert(buffer.peek!Foo(0) == Foo.one); 3524 assert(buffer.peek!Foo(4) == Foo.two); 3525 assert(buffer.peek!Foo(8) == Foo.three); 3526 3527 size_t index = 0; 3528 assert(buffer.peek!Foo(&index) == Foo.one); 3529 assert(index == 4); 3530 3531 assert(buffer.peek!Foo(&index) == Foo.two); 3532 assert(index == 8); 3533 3534 assert(buffer.peek!Foo(&index) == Foo.three); 3535 assert(index == 12); 3536 } 3537 3538 { 3539 //enum - bool 3540 ubyte[] buffer = [0, 1]; 3541 3542 enum Bool: bool 3543 { 3544 bfalse = false, 3545 btrue = true, 3546 } 3547 3548 assert(buffer.peek!Bool() == Bool.bfalse); 3549 assert(buffer.peek!Bool(0) == Bool.bfalse); 3550 assert(buffer.peek!Bool(1) == Bool.btrue); 3551 3552 size_t index = 0; 3553 assert(buffer.peek!Bool(&index) == Bool.bfalse); 3554 assert(index == 1); 3555 3556 assert(buffer.peek!Bool(&index) == Bool.btrue); 3557 assert(index == 2); 3558 } 3559 3560 { 3561 //enum - float 3562 ubyte[] buffer = [66, 0, 0, 0, 65, 200, 0, 0]; 3563 3564 enum Float: float 3565 { 3566 one = 32.0f, 3567 two = 25.0f 3568 } 3569 3570 assert(buffer.peek!Float() == Float.one); 3571 assert(buffer.peek!Float(0) == Float.one); 3572 assert(buffer.peek!Float(4) == Float.two); 3573 3574 size_t index = 0; 3575 assert(buffer.peek!Float(&index) == Float.one); 3576 assert(index == 4); 3577 3578 assert(buffer.peek!Float(&index) == Float.two); 3579 assert(index == 8); 3580 } 3581 3582 { 3583 //enum - double 3584 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3585 3586 enum Double: double 3587 { 3588 one = 32.0, 3589 two = 25.0 3590 } 3591 3592 assert(buffer.peek!Double() == Double.one); 3593 assert(buffer.peek!Double(0) == Double.one); 3594 assert(buffer.peek!Double(8) == Double.two); 3595 3596 size_t index = 0; 3597 assert(buffer.peek!Double(&index) == Double.one); 3598 assert(index == 8); 3599 3600 assert(buffer.peek!Double(&index) == Double.two); 3601 assert(index == 16); 3602 } 3603 3604 { 3605 //enum - real 3606 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3607 3608 enum Real: real 3609 { 3610 one = 32.0, 3611 two = 25.0 3612 } 3613 3614 static assert(!__traits(compiles, buffer.peek!Real())); 3615 } 3616 } 3617 3618 /++ 3619 Takes a range of `ubyte`s and converts the first `T.sizeof` bytes to 3620 `T`. The value returned is converted from the given endianness to the 3621 native endianness. The `T.sizeof` bytes which are read are consumed from 3622 the range. 3623 3624 Params: 3625 T = The integral type to convert the first `T.sizeof` bytes to. 3626 endianness = The endianness that the bytes are assumed to be in. 3627 range = The range to read from. 3628 +/ 3629 T read(T, Endian endianness = Endian.bigEndian, R)(ref R range) 3630 if (canSwapEndianness!T && isInputRange!R && is(ElementType!R : const ubyte)) 3631 { 3632 static if (hasSlicing!R && is(typeof(R.init[0 .. 0]) : const(ubyte)[])) 3633 { 3634 const ubyte[T.sizeof] bytes = range[0 .. T.sizeof]; 3635 range.popFrontN(T.sizeof); 3636 } 3637 else 3638 { 3639 ubyte[T.sizeof] bytes; 3640 3641 foreach (ref e; bytes) 3642 { 3643 e = range.front; 3644 range.popFront(); 3645 } 3646 } 3647 3648 static if (endianness == Endian.bigEndian) 3649 return bigEndianToNative!T(bytes); 3650 else 3651 return littleEndianToNative!T(bytes); 3652 } 3653 3654 /// 3655 @safe unittest 3656 { 3657 import std.range.primitives : empty; 3658 ubyte[] buffer = [1, 5, 22, 9, 44, 255, 8]; 3659 assert(buffer.length == 7); 3660 3661 assert(buffer.read!ushort() == 261); 3662 assert(buffer.length == 5); 3663 3664 assert(buffer.read!uint() == 369700095); 3665 assert(buffer.length == 1); 3666 3667 assert(buffer.read!ubyte() == 8); 3668 assert(buffer.empty); 3669 } 3670 3671 @safe unittest 3672 { 3673 { 3674 //bool 3675 ubyte[] buffer = [0, 1]; 3676 assert(buffer.length == 2); 3677 3678 assert(buffer.read!bool() == false); 3679 assert(buffer.length == 1); 3680 3681 assert(buffer.read!bool() == true); 3682 assert(buffer.empty); 3683 } 3684 3685 { 3686 //char (8bit) 3687 ubyte[] buffer = [97, 98, 99]; 3688 assert(buffer.length == 3); 3689 3690 assert(buffer.read!char() == 'a'); 3691 assert(buffer.length == 2); 3692 3693 assert(buffer.read!char() == 'b'); 3694 assert(buffer.length == 1); 3695 3696 assert(buffer.read!char() == 'c'); 3697 assert(buffer.empty); 3698 } 3699 3700 { 3701 //wchar (16bit - 2x ubyte) 3702 ubyte[] buffer = [1, 5, 32, 29, 1, 7]; 3703 assert(buffer.length == 6); 3704 3705 assert(buffer.read!wchar() == 'ą'); 3706 assert(buffer.length == 4); 3707 3708 assert(buffer.read!wchar() == '”'); 3709 assert(buffer.length == 2); 3710 3711 assert(buffer.read!wchar() == 'ć'); 3712 assert(buffer.empty); 3713 } 3714 3715 { 3716 //dchar (32bit - 4x ubyte) 3717 ubyte[] buffer = [0, 0, 1, 5, 0, 0, 32, 29, 0, 0, 1, 7]; 3718 assert(buffer.length == 12); 3719 3720 assert(buffer.read!dchar() == 'ą'); 3721 assert(buffer.length == 8); 3722 3723 assert(buffer.read!dchar() == '”'); 3724 assert(buffer.length == 4); 3725 3726 assert(buffer.read!dchar() == 'ć'); 3727 assert(buffer.empty); 3728 } 3729 3730 { 3731 //float (32bit - 4x ubyte) 3732 ubyte[] buffer = [66, 0, 0, 0, 65, 200, 0, 0]; 3733 assert(buffer.length == 8); 3734 3735 assert(buffer.read!float()== 32.0); 3736 assert(buffer.length == 4); 3737 3738 assert(buffer.read!float() == 25.0f); 3739 assert(buffer.empty); 3740 } 3741 3742 { 3743 //double (64bit - 8x ubyte) 3744 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3745 assert(buffer.length == 16); 3746 3747 assert(buffer.read!double() == 32.0); 3748 assert(buffer.length == 8); 3749 3750 assert(buffer.read!double() == 25.0); 3751 assert(buffer.empty); 3752 } 3753 3754 { 3755 //enum - uint 3756 ubyte[] buffer = [0, 0, 0, 10, 0, 0, 0, 20, 0, 0, 0, 30]; 3757 assert(buffer.length == 12); 3758 3759 enum Foo 3760 { 3761 one = 10, 3762 two = 20, 3763 three = 30 3764 } 3765 3766 assert(buffer.read!Foo() == Foo.one); 3767 assert(buffer.length == 8); 3768 3769 assert(buffer.read!Foo() == Foo.two); 3770 assert(buffer.length == 4); 3771 3772 assert(buffer.read!Foo() == Foo.three); 3773 assert(buffer.empty); 3774 } 3775 3776 { 3777 //enum - bool 3778 ubyte[] buffer = [0, 1]; 3779 assert(buffer.length == 2); 3780 3781 enum Bool: bool 3782 { 3783 bfalse = false, 3784 btrue = true, 3785 } 3786 3787 assert(buffer.read!Bool() == Bool.bfalse); 3788 assert(buffer.length == 1); 3789 3790 assert(buffer.read!Bool() == Bool.btrue); 3791 assert(buffer.empty); 3792 } 3793 3794 { 3795 //enum - float 3796 ubyte[] buffer = [66, 0, 0, 0, 65, 200, 0, 0]; 3797 assert(buffer.length == 8); 3798 3799 enum Float: float 3800 { 3801 one = 32.0f, 3802 two = 25.0f 3803 } 3804 3805 assert(buffer.read!Float() == Float.one); 3806 assert(buffer.length == 4); 3807 3808 assert(buffer.read!Float() == Float.two); 3809 assert(buffer.empty); 3810 } 3811 3812 { 3813 //enum - double 3814 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3815 assert(buffer.length == 16); 3816 3817 enum Double: double 3818 { 3819 one = 32.0, 3820 two = 25.0 3821 } 3822 3823 assert(buffer.read!Double() == Double.one); 3824 assert(buffer.length == 8); 3825 3826 assert(buffer.read!Double() == Double.two); 3827 assert(buffer.empty); 3828 } 3829 3830 { 3831 //enum - real 3832 ubyte[] buffer = [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]; 3833 3834 enum Real: real 3835 { 3836 one = 32.0, 3837 two = 25.0 3838 } 3839 3840 static assert(!__traits(compiles, buffer.read!Real())); 3841 } 3842 } 3843 3844 // https://issues.dlang.org/show_bug.cgi?id=17247 3845 @safe unittest 3846 { 3847 struct UbyteRange 3848 { 3849 ubyte[] impl; 3850 @property bool empty() { return impl.empty; } 3851 @property ubyte front() { return impl.front; } 3852 void popFront() { impl.popFront(); } 3853 @property UbyteRange save() { return this; } 3854 3855 // N.B. support slicing but do not return ubyte[] slices. 3856 UbyteRange opSlice(size_t start, size_t end) 3857 { 3858 return UbyteRange(impl[start .. end]); 3859 } 3860 @property size_t length() { return impl.length; } 3861 size_t opDollar() { return impl.length; } 3862 } 3863 static assert(hasSlicing!UbyteRange); 3864 3865 auto r = UbyteRange([0x01, 0x00, 0x00, 0x00]); 3866 int x = r.read!(int, Endian.littleEndian)(); 3867 assert(x == 1); 3868 } 3869 3870 3871 /++ 3872 Takes an integral value, converts it to the given endianness, and writes it 3873 to the given range of `ubyte`s as a sequence of `T.sizeof` `ubyte`s 3874 starting at index. `hasSlicing!R` must be `true`. 3875 3876 Params: 3877 T = The integral type to convert the first `T.sizeof` bytes to. 3878 endianness = The endianness to _write the bytes in. 3879 range = The range to _write to. 3880 value = The value to _write. 3881 index = The index to start writing to. If index is a pointer, then it 3882 is updated to the index after the bytes read. 3883 +/ 3884 void write(T, Endian endianness = Endian.bigEndian, R)(R range, const T value, size_t index) 3885 if (canSwapEndianness!T && 3886 isForwardRange!R && 3887 hasSlicing!R && 3888 is(ElementType!R : ubyte)) 3889 { 3890 write!(T, endianness)(range, value, &index); 3891 } 3892 3893 /++ Ditto +/ 3894 void write(T, Endian endianness = Endian.bigEndian, R)(R range, const T value, size_t* index) 3895 if (canSwapEndianness!T && 3896 isForwardRange!R && 3897 hasSlicing!R && 3898 is(ElementType!R : ubyte)) 3899 { 3900 assert(index, "index must not point to null"); 3901 3902 static if (endianness == Endian.bigEndian) 3903 immutable bytes = nativeToBigEndian!T(value); 3904 else 3905 immutable bytes = nativeToLittleEndian!T(value); 3906 3907 immutable begin = *index; 3908 immutable end = begin + T.sizeof; 3909 *index = end; 3910 range[begin .. end] = bytes[0 .. T.sizeof]; 3911 } 3912 3913 /// 3914 @system unittest 3915 { 3916 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0]; 3917 buffer.write!uint(29110231u, 0); 3918 assert(buffer == [1, 188, 47, 215, 0, 0, 0, 0]); 3919 3920 buffer.write!ushort(927, 0); 3921 assert(buffer == [3, 159, 47, 215, 0, 0, 0, 0]); 3922 3923 buffer.write!ubyte(42, 0); 3924 assert(buffer == [42, 159, 47, 215, 0, 0, 0, 0]); 3925 } 3926 3927 /// 3928 @system unittest 3929 { 3930 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0, 0]; 3931 buffer.write!uint(142700095u, 2); 3932 assert(buffer == [0, 0, 8, 129, 110, 63, 0, 0, 0]); 3933 3934 buffer.write!ushort(19839, 2); 3935 assert(buffer == [0, 0, 77, 127, 110, 63, 0, 0, 0]); 3936 3937 buffer.write!ubyte(132, 2); 3938 assert(buffer == [0, 0, 132, 127, 110, 63, 0, 0, 0]); 3939 } 3940 3941 /// 3942 @system unittest 3943 { 3944 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0]; 3945 size_t index = 0; 3946 buffer.write!ushort(261, &index); 3947 assert(buffer == [1, 5, 0, 0, 0, 0, 0, 0]); 3948 assert(index == 2); 3949 3950 buffer.write!uint(369700095u, &index); 3951 assert(buffer == [1, 5, 22, 9, 44, 255, 0, 0]); 3952 assert(index == 6); 3953 3954 buffer.write!ubyte(8, &index); 3955 assert(buffer == [1, 5, 22, 9, 44, 255, 8, 0]); 3956 assert(index == 7); 3957 } 3958 3959 /// bool 3960 @system unittest 3961 { 3962 ubyte[] buffer = [0, 0]; 3963 buffer.write!bool(false, 0); 3964 assert(buffer == [0, 0]); 3965 3966 buffer.write!bool(true, 0); 3967 assert(buffer == [1, 0]); 3968 3969 buffer.write!bool(true, 1); 3970 assert(buffer == [1, 1]); 3971 3972 buffer.write!bool(false, 1); 3973 assert(buffer == [1, 0]); 3974 3975 size_t index = 0; 3976 buffer.write!bool(false, &index); 3977 assert(buffer == [0, 0]); 3978 assert(index == 1); 3979 3980 buffer.write!bool(true, &index); 3981 assert(buffer == [0, 1]); 3982 assert(index == 2); 3983 } 3984 3985 /// char(8-bit) 3986 @system unittest 3987 { 3988 ubyte[] buffer = [0, 0, 0]; 3989 3990 buffer.write!char('a', 0); 3991 assert(buffer == [97, 0, 0]); 3992 3993 buffer.write!char('b', 1); 3994 assert(buffer == [97, 98, 0]); 3995 3996 size_t index = 0; 3997 buffer.write!char('a', &index); 3998 assert(buffer == [97, 98, 0]); 3999 assert(index == 1); 4000 4001 buffer.write!char('b', &index); 4002 assert(buffer == [97, 98, 0]); 4003 assert(index == 2); 4004 4005 buffer.write!char('c', &index); 4006 assert(buffer == [97, 98, 99]); 4007 assert(index == 3); 4008 } 4009 4010 /// wchar (16bit - 2x ubyte) 4011 @system unittest 4012 { 4013 ubyte[] buffer = [0, 0, 0, 0]; 4014 4015 buffer.write!wchar('ą', 0); 4016 assert(buffer == [1, 5, 0, 0]); 4017 4018 buffer.write!wchar('”', 2); 4019 assert(buffer == [1, 5, 32, 29]); 4020 4021 size_t index = 0; 4022 buffer.write!wchar('ć', &index); 4023 assert(buffer == [1, 7, 32, 29]); 4024 assert(index == 2); 4025 4026 buffer.write!wchar('ą', &index); 4027 assert(buffer == [1, 7, 1, 5]); 4028 assert(index == 4); 4029 } 4030 4031 /// dchar (32bit - 4x ubyte) 4032 @system unittest 4033 { 4034 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0]; 4035 4036 buffer.write!dchar('ą', 0); 4037 assert(buffer == [0, 0, 1, 5, 0, 0, 0, 0]); 4038 4039 buffer.write!dchar('”', 4); 4040 assert(buffer == [0, 0, 1, 5, 0, 0, 32, 29]); 4041 4042 size_t index = 0; 4043 buffer.write!dchar('ć', &index); 4044 assert(buffer == [0, 0, 1, 7, 0, 0, 32, 29]); 4045 assert(index == 4); 4046 4047 buffer.write!dchar('ą', &index); 4048 assert(buffer == [0, 0, 1, 7, 0, 0, 1, 5]); 4049 assert(index == 8); 4050 } 4051 4052 /// float (32bit - 4x ubyte) 4053 @system unittest 4054 { 4055 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0]; 4056 4057 buffer.write!float(32.0f, 0); 4058 assert(buffer == [66, 0, 0, 0, 0, 0, 0, 0]); 4059 4060 buffer.write!float(25.0f, 4); 4061 assert(buffer == [66, 0, 0, 0, 65, 200, 0, 0]); 4062 4063 size_t index = 0; 4064 buffer.write!float(25.0f, &index); 4065 assert(buffer == [65, 200, 0, 0, 65, 200, 0, 0]); 4066 assert(index == 4); 4067 4068 buffer.write!float(32.0f, &index); 4069 assert(buffer == [65, 200, 0, 0, 66, 0, 0, 0]); 4070 assert(index == 8); 4071 } 4072 4073 /// double (64bit - 8x ubyte) 4074 @system unittest 4075 { 4076 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 4077 4078 buffer.write!double(32.0, 0); 4079 assert(buffer == [64, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); 4080 4081 buffer.write!double(25.0, 8); 4082 assert(buffer == [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]); 4083 4084 size_t index = 0; 4085 buffer.write!double(25.0, &index); 4086 assert(buffer == [64, 57, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]); 4087 assert(index == 8); 4088 4089 buffer.write!double(32.0, &index); 4090 assert(buffer == [64, 57, 0, 0, 0, 0, 0, 0, 64, 64, 0, 0, 0, 0, 0, 0]); 4091 assert(index == 16); 4092 } 4093 4094 /// enum 4095 @system unittest 4096 { 4097 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 4098 4099 enum Foo 4100 { 4101 one = 10, 4102 two = 20, 4103 three = 30 4104 } 4105 4106 buffer.write!Foo(Foo.one, 0); 4107 assert(buffer == [0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0]); 4108 4109 buffer.write!Foo(Foo.two, 4); 4110 assert(buffer == [0, 0, 0, 10, 0, 0, 0, 20, 0, 0, 0, 0]); 4111 4112 buffer.write!Foo(Foo.three, 8); 4113 assert(buffer == [0, 0, 0, 10, 0, 0, 0, 20, 0, 0, 0, 30]); 4114 4115 size_t index = 0; 4116 buffer.write!Foo(Foo.three, &index); 4117 assert(buffer == [0, 0, 0, 30, 0, 0, 0, 20, 0, 0, 0, 30]); 4118 assert(index == 4); 4119 4120 buffer.write!Foo(Foo.one, &index); 4121 assert(buffer == [0, 0, 0, 30, 0, 0, 0, 10, 0, 0, 0, 30]); 4122 assert(index == 8); 4123 4124 buffer.write!Foo(Foo.two, &index); 4125 assert(buffer == [0, 0, 0, 30, 0, 0, 0, 10, 0, 0, 0, 20]); 4126 assert(index == 12); 4127 } 4128 4129 // enum - bool 4130 @system unittest 4131 { 4132 ubyte[] buffer = [0, 0]; 4133 4134 enum Bool: bool 4135 { 4136 bfalse = false, 4137 btrue = true, 4138 } 4139 4140 buffer.write!Bool(Bool.btrue, 0); 4141 assert(buffer == [1, 0]); 4142 4143 buffer.write!Bool(Bool.btrue, 1); 4144 assert(buffer == [1, 1]); 4145 4146 size_t index = 0; 4147 buffer.write!Bool(Bool.bfalse, &index); 4148 assert(buffer == [0, 1]); 4149 assert(index == 1); 4150 4151 buffer.write!Bool(Bool.bfalse, &index); 4152 assert(buffer == [0, 0]); 4153 assert(index == 2); 4154 } 4155 4156 /// enum - float 4157 @system unittest 4158 { 4159 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0]; 4160 4161 enum Float: float 4162 { 4163 one = 32.0f, 4164 two = 25.0f 4165 } 4166 4167 buffer.write!Float(Float.one, 0); 4168 assert(buffer == [66, 0, 0, 0, 0, 0, 0, 0]); 4169 4170 buffer.write!Float(Float.two, 4); 4171 assert(buffer == [66, 0, 0, 0, 65, 200, 0, 0]); 4172 4173 size_t index = 0; 4174 buffer.write!Float(Float.two, &index); 4175 assert(buffer == [65, 200, 0, 0, 65, 200, 0, 0]); 4176 assert(index == 4); 4177 4178 buffer.write!Float(Float.one, &index); 4179 assert(buffer == [65, 200, 0, 0, 66, 0, 0, 0]); 4180 assert(index == 8); 4181 } 4182 4183 /// enum - double 4184 @system unittest 4185 { 4186 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 4187 4188 enum Double: double 4189 { 4190 one = 32.0, 4191 two = 25.0 4192 } 4193 4194 buffer.write!Double(Double.one, 0); 4195 assert(buffer == [64, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); 4196 4197 buffer.write!Double(Double.two, 8); 4198 assert(buffer == [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]); 4199 4200 size_t index = 0; 4201 buffer.write!Double(Double.two, &index); 4202 assert(buffer == [64, 57, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]); 4203 assert(index == 8); 4204 4205 buffer.write!Double(Double.one, &index); 4206 assert(buffer == [64, 57, 0, 0, 0, 0, 0, 0, 64, 64, 0, 0, 0, 0, 0, 0]); 4207 assert(index == 16); 4208 } 4209 4210 /// enum - real 4211 @system unittest 4212 { 4213 ubyte[] buffer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 4214 4215 enum Real: real 4216 { 4217 one = 32.0, 4218 two = 25.0 4219 } 4220 4221 static assert(!__traits(compiles, buffer.write!Real(Real.one))); 4222 } 4223 4224 4225 /++ 4226 Takes an integral value, converts it to the given endianness, and appends 4227 it to the given range of `ubyte`s (using `put`) as a sequence of 4228 `T.sizeof` `ubyte`s starting at index. `hasSlicing!R` must be 4229 `true`. 4230 4231 Params: 4232 T = The integral type to convert the first `T.sizeof` bytes to. 4233 endianness = The endianness to write the bytes in. 4234 range = The range to _append to. 4235 value = The value to _append. 4236 +/ 4237 void append(T, Endian endianness = Endian.bigEndian, R)(R range, const T value) 4238 if (canSwapEndianness!T && isOutputRange!(R, ubyte)) 4239 { 4240 static if (endianness == Endian.bigEndian) 4241 immutable bytes = nativeToBigEndian!T(value); 4242 else 4243 immutable bytes = nativeToLittleEndian!T(value); 4244 4245 put(range, bytes[]); 4246 } 4247 4248 /// 4249 @safe unittest 4250 { 4251 import std.array; 4252 auto buffer = appender!(const ubyte[])(); 4253 buffer.append!ushort(261); 4254 assert(buffer.data == [1, 5]); 4255 4256 buffer.append!uint(369700095u); 4257 assert(buffer.data == [1, 5, 22, 9, 44, 255]); 4258 4259 buffer.append!ubyte(8); 4260 assert(buffer.data == [1, 5, 22, 9, 44, 255, 8]); 4261 } 4262 4263 /// bool 4264 @safe unittest 4265 { 4266 import std.array : appender; 4267 auto buffer = appender!(const ubyte[])(); 4268 4269 buffer.append!bool(true); 4270 assert(buffer.data == [1]); 4271 4272 buffer.append!bool(false); 4273 assert(buffer.data == [1, 0]); 4274 } 4275 4276 /// char wchar dchar 4277 @safe unittest 4278 { 4279 import std.array : appender; 4280 auto buffer = appender!(const ubyte[])(); 4281 4282 buffer.append!char('a'); 4283 assert(buffer.data == [97]); 4284 4285 buffer.append!char('b'); 4286 assert(buffer.data == [97, 98]); 4287 4288 buffer.append!wchar('ą'); 4289 assert(buffer.data == [97, 98, 1, 5]); 4290 4291 buffer.append!dchar('ą'); 4292 assert(buffer.data == [97, 98, 1, 5, 0, 0, 1, 5]); 4293 } 4294 4295 /// float double 4296 @safe unittest 4297 { 4298 import std.array : appender; 4299 auto buffer = appender!(const ubyte[])(); 4300 4301 buffer.append!float(32.0f); 4302 assert(buffer.data == [66, 0, 0, 0]); 4303 4304 buffer.append!double(32.0); 4305 assert(buffer.data == [66, 0, 0, 0, 64, 64, 0, 0, 0, 0, 0, 0]); 4306 } 4307 4308 /// enum 4309 @safe unittest 4310 { 4311 import std.array : appender; 4312 auto buffer = appender!(const ubyte[])(); 4313 4314 enum Foo 4315 { 4316 one = 10, 4317 two = 20, 4318 three = 30 4319 } 4320 4321 buffer.append!Foo(Foo.one); 4322 assert(buffer.data == [0, 0, 0, 10]); 4323 4324 buffer.append!Foo(Foo.two); 4325 assert(buffer.data == [0, 0, 0, 10, 0, 0, 0, 20]); 4326 4327 buffer.append!Foo(Foo.three); 4328 assert(buffer.data == [0, 0, 0, 10, 0, 0, 0, 20, 0, 0, 0, 30]); 4329 } 4330 4331 /// enum - bool 4332 @safe unittest 4333 { 4334 import std.array : appender; 4335 auto buffer = appender!(const ubyte[])(); 4336 4337 enum Bool: bool 4338 { 4339 bfalse = false, 4340 btrue = true, 4341 } 4342 4343 buffer.append!Bool(Bool.btrue); 4344 assert(buffer.data == [1]); 4345 4346 buffer.append!Bool(Bool.bfalse); 4347 assert(buffer.data == [1, 0]); 4348 4349 buffer.append!Bool(Bool.btrue); 4350 assert(buffer.data == [1, 0, 1]); 4351 } 4352 4353 /// enum - float 4354 @safe unittest 4355 { 4356 import std.array : appender; 4357 auto buffer = appender!(const ubyte[])(); 4358 4359 enum Float: float 4360 { 4361 one = 32.0f, 4362 two = 25.0f 4363 } 4364 4365 buffer.append!Float(Float.one); 4366 assert(buffer.data == [66, 0, 0, 0]); 4367 4368 buffer.append!Float(Float.two); 4369 assert(buffer.data == [66, 0, 0, 0, 65, 200, 0, 0]); 4370 } 4371 4372 /// enum - double 4373 @safe unittest 4374 { 4375 import std.array : appender; 4376 auto buffer = appender!(const ubyte[])(); 4377 4378 enum Double: double 4379 { 4380 one = 32.0, 4381 two = 25.0 4382 } 4383 4384 buffer.append!Double(Double.one); 4385 assert(buffer.data == [64, 64, 0, 0, 0, 0, 0, 0]); 4386 4387 buffer.append!Double(Double.two); 4388 assert(buffer.data == [64, 64, 0, 0, 0, 0, 0, 0, 64, 57, 0, 0, 0, 0, 0, 0]); 4389 } 4390 4391 /// enum - real 4392 @safe unittest 4393 { 4394 import std.array : appender; 4395 auto buffer = appender!(const ubyte[])(); 4396 4397 enum Real: real 4398 { 4399 one = 32.0, 4400 two = 25.0 4401 } 4402 4403 static assert(!__traits(compiles, buffer.append!Real(Real.one))); 4404 } 4405 4406 @system unittest 4407 { 4408 import std.array; 4409 import std.format : format; 4410 import std.meta : AliasSeq; 4411 static foreach (endianness; [Endian.bigEndian, Endian.littleEndian]) 4412 {{ 4413 auto toWrite = appender!(ubyte[])(); 4414 alias Types = AliasSeq!(uint, int, long, ulong, short, ubyte, ushort, byte, uint); 4415 ulong[] values = [42, -11, long.max, 1098911981329L, 16, 255, 19012, 2, 17]; 4416 assert(Types.length == values.length); 4417 4418 size_t index = 0; 4419 size_t length = 0; 4420 static foreach (T; Types) 4421 { 4422 toWrite.append!(T, endianness)(cast(T) values[index++]); 4423 length += T.sizeof; 4424 } 4425 4426 auto toRead = toWrite.data; 4427 assert(toRead.length == length); 4428 4429 index = 0; 4430 static foreach (T; Types) 4431 { 4432 assert(toRead.peek!(T, endianness)() == values[index], format("Failed Index: %s", index)); 4433 assert(toRead.peek!(T, endianness)(0) == values[index], format("Failed Index: %s", index)); 4434 assert(toRead.length == length, 4435 format("Failed Index [%s], Actual Length: %s", index, toRead.length)); 4436 assert(toRead.read!(T, endianness)() == values[index], format("Failed Index: %s", index)); 4437 length -= T.sizeof; 4438 assert(toRead.length == length, 4439 format("Failed Index [%s], Actual Length: %s", index, toRead.length)); 4440 ++index; 4441 } 4442 assert(toRead.empty); 4443 }} 4444 } 4445 4446 /** 4447 Counts the number of set bits in the binary representation of `value`. 4448 For signed integers, the sign bit is included in the count. 4449 */ 4450 private uint countBitsSet(T)(const T value) @nogc pure nothrow 4451 if (isIntegral!T) 4452 { 4453 static if (T.sizeof == 8) 4454 { 4455 import core.bitop : popcnt; 4456 const c = popcnt(cast(ulong) value); 4457 } 4458 else static if (T.sizeof == 4) 4459 { 4460 import core.bitop : popcnt; 4461 const c = popcnt(cast(uint) value); 4462 } 4463 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 4464 else static if (T.sizeof == 2) 4465 { 4466 uint c = value - ((value >> 1) & 0x5555); 4467 c = ((c >> 2) & 0x3333) + (c & 0X3333); 4468 c = ((c >> 4) + c) & 0x0F0F; 4469 c = ((c >> 8) + c) & 0x00FF; 4470 } 4471 else static if (T.sizeof == 1) 4472 { 4473 uint c = value - ((value >> 1) & 0x55); 4474 c = ((c >> 2) & 0x33) + (c & 0X33); 4475 c = ((c >> 4) + c) & 0x0F; 4476 } 4477 else 4478 { 4479 static assert(false, "countBitsSet only supports 1, 2, 4, or 8 byte sized integers."); 4480 } 4481 return cast(uint) c; 4482 } 4483 4484 @safe unittest 4485 { 4486 assert(countBitsSet(1) == 1); 4487 assert(countBitsSet(0) == 0); 4488 assert(countBitsSet(int.min) == 1); 4489 assert(countBitsSet(uint.max) == 32); 4490 } 4491 4492 @safe unittest 4493 { 4494 import std.meta; 4495 static foreach (T; AliasSeq!(byte, ubyte, short, ushort, int, uint, long, ulong)) 4496 { 4497 assert(countBitsSet(cast(T) 0) == 0); 4498 assert(countBitsSet(cast(T) 1) == 1); 4499 assert(countBitsSet(cast(T) 2) == 1); 4500 assert(countBitsSet(cast(T) 3) == 2); 4501 assert(countBitsSet(cast(T) 4) == 1); 4502 assert(countBitsSet(cast(T) 5) == 2); 4503 assert(countBitsSet(cast(T) 127) == 7); 4504 static if (isSigned!T) 4505 { 4506 assert(countBitsSet(cast(T)-1) == 8 * T.sizeof); 4507 assert(countBitsSet(T.min) == 1); 4508 } 4509 else 4510 { 4511 assert(countBitsSet(T.max) == 8 * T.sizeof); 4512 } 4513 // Check CTFE compiles. 4514 static assert(countBitsSet(cast(T) 1) == 1); 4515 } 4516 assert(countBitsSet(1_000_000) == 7); 4517 foreach (i; 0 .. 63) 4518 assert(countBitsSet(1UL << i) == 1); 4519 } 4520 4521 private struct BitsSet(T) 4522 { 4523 static assert(T.sizeof <= 8, "bitsSet assumes T is no more than 64-bit."); 4524 4525 @nogc pure nothrow: 4526 4527 this(T value, size_t startIndex = 0) 4528 { 4529 _value = value; 4530 // Further calculation is only valid and needed when the range is non-empty. 4531 if (!_value) 4532 return; 4533 4534 import core.bitop : bsf; 4535 immutable trailingZerosCount = bsf(value); 4536 _value >>>= trailingZerosCount; 4537 _index = startIndex + trailingZerosCount; 4538 } 4539 4540 @property size_t front() 4541 { 4542 return _index; 4543 } 4544 4545 @property bool empty() const 4546 { 4547 return !_value; 4548 } 4549 4550 void popFront() 4551 { 4552 assert(_value, "Cannot call popFront on empty range."); 4553 4554 _value >>>= 1; 4555 // Further calculation is only valid and needed when the range is non-empty. 4556 if (!_value) 4557 return; 4558 4559 import core.bitop : bsf; 4560 immutable trailingZerosCount = bsf(_value); 4561 _value >>>= trailingZerosCount; 4562 _index += trailingZerosCount + 1; 4563 } 4564 4565 @property auto save() 4566 { 4567 return this; 4568 } 4569 4570 @property size_t length() 4571 { 4572 return countBitsSet(_value); 4573 } 4574 4575 private T _value; 4576 private size_t _index; 4577 } 4578 4579 /** 4580 Range that iterates the indices of the set bits in `value`. 4581 Index 0 corresponds to the least significant bit. 4582 For signed integers, the highest index corresponds to the sign bit. 4583 */ 4584 auto bitsSet(T)(const T value) @nogc pure nothrow 4585 if (isIntegral!T) 4586 { 4587 return BitsSet!T(value); 4588 } 4589 4590 /// 4591 @safe unittest 4592 { 4593 import std.algorithm.comparison : equal; 4594 import std.range : iota; 4595 4596 assert(bitsSet(1).equal([0])); 4597 assert(bitsSet(5).equal([0, 2])); 4598 assert(bitsSet(-1).equal(iota(32))); 4599 assert(bitsSet(int.min).equal([31])); 4600 } 4601 4602 @safe unittest 4603 { 4604 import std.algorithm.comparison : equal; 4605 import std.range : iota; 4606 4607 import std.meta; 4608 static foreach (T; AliasSeq!(byte, ubyte, short, ushort, int, uint, long, ulong)) 4609 { 4610 assert(bitsSet(cast(T) 0).empty); 4611 assert(bitsSet(cast(T) 1).equal([0])); 4612 assert(bitsSet(cast(T) 2).equal([1])); 4613 assert(bitsSet(cast(T) 3).equal([0, 1])); 4614 assert(bitsSet(cast(T) 4).equal([2])); 4615 assert(bitsSet(cast(T) 5).equal([0, 2])); 4616 assert(bitsSet(cast(T) 127).equal(iota(7))); 4617 static if (isSigned!T) 4618 { 4619 assert(bitsSet(cast(T)-1).equal(iota(8 * T.sizeof))); 4620 assert(bitsSet(T.min).equal([8 * T.sizeof - 1])); 4621 } 4622 else 4623 { 4624 assert(bitsSet(T.max).equal(iota(8 * T.sizeof))); 4625 } 4626 } 4627 assert(bitsSet(1_000_000).equal([6, 9, 14, 16, 17, 18, 19])); 4628 foreach (i; 0 .. 63) 4629 assert(bitsSet(1UL << i).equal([i])); 4630 }