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