| // Written in the D programming language. |
| |
| /** |
| Bit-level manipulation facilities. |
| |
| $(SCRIPT inhibitQuickIndex = 1;) |
| $(DIVC quickindex, |
| $(BOOKTABLE, |
| $(TR $(TH Category) $(TH Functions)) |
| $(TR $(TD Bit constructs) $(TD |
| $(LREF BitArray) |
| $(LREF bitfields) |
| $(LREF bitsSet) |
| )) |
| $(TR $(TD Endianness conversion) $(TD |
| $(LREF bigEndianToNative) |
| $(LREF littleEndianToNative) |
| $(LREF nativeToBigEndian) |
| $(LREF nativeToLittleEndian) |
| $(LREF swapEndian) |
| )) |
| $(TR $(TD Integral ranges) $(TD |
| $(LREF append) |
| $(LREF peek) |
| $(LREF read) |
| $(LREF write) |
| )) |
| $(TR $(TD Floating-Point manipulation) $(TD |
| $(LREF DoubleRep) |
| $(LREF FloatRep) |
| )) |
| $(TR $(TD Tagging) $(TD |
| $(LREF taggedClassRef) |
| $(LREF taggedPointer) |
| )) |
| )) |
| |
| Copyright: Copyright The D Language Foundation 2007 - 2011. |
| License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0). |
| Authors: $(HTTP digitalmars.com, Walter Bright), |
| $(HTTP erdani.org, Andrei Alexandrescu), |
| $(HTTP jmdavisprog.com, Jonathan M Davis), |
| Alex Rønne Petersen, |
| Damian Ziemba, |
| Amaury SECHET |
| Source: $(PHOBOSSRC std/bitmanip.d) |
| */ |
| /* |
| Copyright The D Language Foundation 2007 - 2012. |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| */ |
| module std.bitmanip; |
| |
| import std.range.primitives; |
| public import std.system : Endian; |
| import std.traits; |
| |
| private string myToString(ulong n) pure @safe |
| { |
| import core.internal.string : UnsignedStringBuf, unsignedToTempString; |
| UnsignedStringBuf buf; |
| auto s = unsignedToTempString(n, buf); |
| // pure allows implicit cast to string |
| return s ~ (n > uint.max ? "UL" : "U"); |
| } |
| |
| @safe pure unittest |
| { |
| assert(myToString(5) == "5U"); |
| assert(myToString(uint.max) == "4294967295U"); |
| assert(myToString(uint.max + 1UL) == "4294967296UL"); |
| } |
| |
| |
| private template createAccessors( |
| string store, T, string name, size_t len, size_t offset) |
| { |
| static if (!name.length) |
| { |
| // No need to create any accessor |
| enum createAccessors = ""; |
| } |
| else static if (len == 0) |
| { |
| // Fields of length 0 are always zero |
| enum createAccessors = "enum "~T.stringof~" "~name~" = 0;\n"; |
| } |
| else |
| { |
| enum ulong |
| maskAllElse = ((~0uL) >> (64 - len)) << offset, |
| signBitCheck = 1uL << (len - 1); |
| |
| static if (T.min < 0) |
| { |
| enum long minVal = -(1uL << (len - 1)); |
| enum ulong maxVal = (1uL << (len - 1)) - 1; |
| alias UT = Unsigned!(T); |
| enum UT extendSign = cast(UT)~((~0uL) >> (64 - len)); |
| } |
| else |
| { |
| enum ulong minVal = 0; |
| enum ulong maxVal = (~0uL) >> (64 - len); |
| enum extendSign = 0; |
| } |
| |
| static if (is(T == bool)) |
| { |
| enum createAccessors = |
| // getter |
| "@property bool " ~ name ~ "() @safe pure nothrow @nogc const { return " |
| ~"("~store~" & "~myToString(maskAllElse)~") != 0;}\n" |
| // setter |
| ~"@property void " ~ name ~ "(bool v) @safe pure nothrow @nogc { " |
| ~"if (v) "~store~" |= "~myToString(maskAllElse)~";" |
| ~"else "~store~" &= cast(typeof("~store~"))(-1-cast(typeof("~store~"))"~myToString(maskAllElse)~");}\n"; |
| } |
| else |
| { |
| // getter |
| enum createAccessors = "@property "~T.stringof~" "~name~"() @safe pure nothrow @nogc const { auto result = " |
| ~"("~store~" & " |
| ~ myToString(maskAllElse) ~ ") >>" |
| ~ myToString(offset) ~ ";" |
| ~ (T.min < 0 |
| ? "if (result >= " ~ myToString(signBitCheck) |
| ~ ") result |= " ~ myToString(extendSign) ~ ";" |
| : "") |
| ~ " return cast("~T.stringof~") result;}\n" |
| // setter |
| ~"@property void "~name~"("~T.stringof~" v) @safe pure nothrow @nogc { " |
| ~"assert(v >= "~name~`_min, "Value is smaller than the minimum value of bitfield '`~name~`'"); ` |
| ~"assert(v <= "~name~`_max, "Value is greater than the maximum value of bitfield '`~name~`'"); ` |
| ~store~" = cast(typeof("~store~"))" |
| ~" (("~store~" & (-1-cast(typeof("~store~"))"~myToString(maskAllElse)~"))" |
| ~" | ((cast(typeof("~store~")) v << "~myToString(offset)~")" |
| ~" & "~myToString(maskAllElse)~"));}\n" |
| // constants |
| ~"enum "~T.stringof~" "~name~"_min = cast("~T.stringof~")" |
| ~myToString(minVal)~"; " |
| ~" enum "~T.stringof~" "~name~"_max = cast("~T.stringof~")" |
| ~myToString(maxVal)~"; "; |
| } |
| } |
| } |
| |
| private template createStoreName(Ts...) |
| { |
| static if (Ts.length < 2) |
| enum createStoreName = "_bf"; |
| else |
| enum createStoreName = "_" ~ Ts[1] ~ createStoreName!(Ts[3 .. $]); |
| } |
| |
| private template createStorageAndFields(Ts...) |
| { |
| enum Name = createStoreName!Ts; |
| enum Size = sizeOfBitField!Ts; |
| static if (Size == ubyte.sizeof * 8) |
| alias StoreType = ubyte; |
| else static if (Size == ushort.sizeof * 8) |
| alias StoreType = ushort; |
| else static if (Size == uint.sizeof * 8) |
| alias StoreType = uint; |
| else static if (Size == ulong.sizeof * 8) |
| alias StoreType = ulong; |
| else |
| { |
| import std.conv : to; |
| static assert(false, "Field widths must sum to 8, 16, 32, or 64, not " ~ to!string(Size)); |
| alias StoreType = ulong; // just to avoid another error msg |
| } |
| |
| enum createStorageAndFields |
| = "private " ~ StoreType.stringof ~ " " ~ Name ~ ";" |
| ~ createFields!(Name, 0, Ts); |
| } |
| |
| private template createFields(string store, size_t offset, Ts...) |
| { |
| static if (Ts.length > 0) |
| enum createFields |
| = createAccessors!(store, Ts[0], Ts[1], Ts[2], offset) |
| ~ createFields!(store, offset + Ts[2], Ts[3 .. $]); |
| else |
| enum createFields = ""; |
| } |
| |
| private ulong getBitsForAlign(ulong a) |
| { |
| ulong bits = 0; |
| while ((a & 0x01) == 0) |
| { |
| bits++; |
| a >>= 1; |
| } |
| |
| assert(a == 1, "alignment is not a power of 2"); |
| return bits; |
| } |
| |
| private template createReferenceAccessor(string store, T, ulong bits, string name) |
| { |
| enum storage = "private void* " ~ store ~ "_ptr;\n"; |
| enum storage_accessor = "@property ref size_t " ~ store ~ "() return @trusted pure nothrow @nogc const { " |
| ~ "return *cast(size_t*) &" ~ store ~ "_ptr;}\n" |
| ~ "@property void " ~ store ~ "(size_t v) @trusted pure nothrow @nogc { " |
| ~ "" ~ store ~ "_ptr = cast(void*) v;}\n"; |
| |
| enum mask = (1UL << bits) - 1; |
| // getter |
| enum ref_accessor = "@property "~T.stringof~" "~name~"() @trusted pure nothrow @nogc const { auto result = " |
| ~ "("~store~" & "~myToString(~mask)~"); " |
| ~ "return cast("~T.stringof~") cast(void*) result;}\n" |
| // setter |
| ~"@property void "~name~"("~T.stringof~" v) @trusted pure nothrow @nogc { " |
| ~"assert(((cast(typeof("~store~")) cast(void*) v) & "~myToString(mask) |
| ~`) == 0, "Value not properly aligned for '`~name~`'"); ` |
| ~store~" = cast(typeof("~store~"))" |
| ~" (("~store~" & (cast(typeof("~store~")) "~myToString(mask)~"))" |
| ~" | ((cast(typeof("~store~")) cast(void*) v) & (cast(typeof("~store~")) "~myToString(~mask)~")));}\n"; |
| |
| enum createReferenceAccessor = storage ~ storage_accessor ~ ref_accessor; |
| } |
| |
| private template sizeOfBitField(T...) |
| { |
| static if (T.length < 2) |
| enum sizeOfBitField = 0; |
| else |
| enum sizeOfBitField = T[2] + sizeOfBitField!(T[3 .. $]); |
| } |
| |
| private template createTaggedReference(T, ulong a, string name, Ts...) |
| { |
| static assert( |
| sizeOfBitField!Ts <= getBitsForAlign(a), |
| "Fields must fit in the bits know to be zero because of alignment." |
| ); |
| enum StoreName = createStoreName!(T, name, 0, Ts); |
| enum createTaggedReference |
| = createReferenceAccessor!(StoreName, T, sizeOfBitField!Ts, name) |
| ~ createFields!(StoreName, 0, Ts, size_t, "", T.sizeof * 8 - sizeOfBitField!Ts); |
| } |
| |
| /** |
| Allows creating `bitfields` inside `structs`, `classes` and `unions`. |
| |
| A `bitfield` consists of one or more entries with a fixed number of |
| bits reserved for each of the entries. The types of the entries can |
| be `bool`s, integral types or enumerated types, arbitrarily mixed. |
| The most efficient type to store in `bitfields` is `bool`, followed |
| by unsigned types, followed by signed types. |
| |
| Each non-`bool` entry of the `bitfield` will be represented by the |
| number of bits specified by the user. The minimum and the maximum |
| numbers that represent this domain can be queried by using the name |
| of the variable followed by `_min` or `_max`. |
| |
| Limitation: The number of bits in a `bitfield` is limited to 8, 16, |
| 32 or 64. If padding is needed, an entry should be explicitly |
| allocated with an empty name. |
| |
| Implementation_details: `Bitfields` are internally stored in an |
| `ubyte`, `ushort`, `uint` or `ulong` depending on the number of bits |
| used. The bits are filled in the order given by the parameters, |
| starting with the lowest significant bit. The name of the (private) |
| variable used for saving the `bitfield` is created by a prefix `_bf` |
| and concatenating all of the variable names, each preceded by an |
| underscore. |
| |
| Params: T = A list of template parameters divided into chunks of 3 |
| items. Each chunk consists (in this order) of a type, a |
| name and a number. Together they define an entry |
| of the `bitfield`: a variable of the given type and name, |
| which can hold as many bits as the number denotes. |
| |
| Returns: A string that can be used in a `mixin` to add the `bitfield`. |
| |
| See_Also: $(REF BitFlags, std,typecons) |
| */ |
| string bitfields(T...)() |
| { |
| import std.conv : to; |
| |
| static assert(T.length % 3 == 0, |
| "Wrong number of arguments (" ~ to!string(T.length) ~ "): Must be a multiple of 3"); |
| |
| static foreach (i, ARG; T) |
| { |
| static if (i % 3 == 0) |
| static assert(is (typeof({ARG tmp = cast (ARG)0; if (ARG.min < 0) {} }())), |
| "Integral type or `bool` expected, found " ~ ARG.stringof); |
| |
| // would be nice to check for valid variable names too |
| static if (i % 3 == 1) |
| static assert(is (typeof(ARG) : string), |
| "Variable name expected, found " ~ ARG.stringof); |
| |
| static if (i % 3 == 2) |
| { |
| static assert(is (typeof({ulong tmp = ARG;}())), |
| "Integral value expected, found " ~ ARG.stringof); |
| |
| static if (T[i-1] != "") |
| { |
| static assert(!is (T[i-2] : bool) || ARG <= 1, |
| "Type `bool` is only allowed for single-bit fields"); |
| |
| static assert(ARG >= 0 && ARG <= T[i-2].sizeof * 8, |
| "Wrong size of bitfield: " ~ ARG.stringof); |
| } |
| } |
| } |
| |
| return createStorageAndFields!T; |
| } |
| |
| /** |
| Create a `bitfield` pack of eight bits, which fit in |
| one `ubyte`. The `bitfields` are allocated starting from the |
| least significant bit, i.e. `x` occupies the two least significant bits |
| of the `bitfields` storage. |
| */ |
| @safe unittest |
| { |
| struct A |
| { |
| int a; |
| mixin(bitfields!( |
| uint, "x", 2, |
| int, "y", 3, |
| uint, "z", 2, |
| bool, "flag", 1)); |
| } |
| |
| A obj; |
| obj.x = 2; |
| obj.z = obj.x; |
| |
| assert(obj.x == 2); |
| assert(obj.y == 0); |
| assert(obj.z == 2); |
| assert(obj.flag == false); |
| } |
| |
| /** |
| The sum of all bit lengths in one `bitfield` instantiation |
| must be exactly 8, 16, 32, or 64. If padding is needed, just allocate |
| one bitfield with an empty name. |
| */ |
| @safe unittest |
| { |
| struct A |
| { |
| mixin(bitfields!( |
| bool, "flag1", 1, |
| bool, "flag2", 1, |
| uint, "", 6)); |
| } |
| |
| A a; |
| assert(a.flag1 == 0); |
| a.flag1 = 1; |
| assert(a.flag1 == 1); |
| a.flag1 = 0; |
| assert(a.flag1 == 0); |
| } |
| |
| /// enums can be used too |
| @safe unittest |
| { |
| enum ABC { A, B, C } |
| struct EnumTest |
| { |
| mixin(bitfields!( |
| ABC, "x", 2, |
| bool, "y", 1, |
| ubyte, "z", 5)); |
| } |
| } |
| |
| @safe pure nothrow @nogc |
| unittest |
| { |
| // Degenerate bitfields tests mixed with range tests |
| // https://issues.dlang.org/show_bug.cgi?id=8474 |
| // https://issues.dlang.org/show_bug.cgi?id=11160 |
| struct Test1 |
| { |
| mixin(bitfields!(uint, "a", 32, |
| uint, "b", 4, |
| uint, "c", 4, |
| uint, "d", 8, |
| uint, "e", 16,)); |
| |
| static assert(Test1.b_min == 0); |
| static assert(Test1.b_max == 15); |
| } |
| |
| struct Test2 |
| { |
| mixin(bitfields!(bool, "a", 0, |
| ulong, "b", 64)); |
| |
| static assert(Test2.b_min == ulong.min); |
| static assert(Test2.b_max == ulong.max); |
| } |
| |
| struct Test1b |
| { |
| mixin(bitfields!(bool, "a", 0, |
| int, "b", 8)); |
| } |
| |
| struct Test2b |
| { |
| mixin(bitfields!(int, "a", 32, |
| int, "b", 4, |
| int, "c", 4, |
| int, "d", 8, |
| int, "e", 16,)); |
| |
| static assert(Test2b.b_min == -8); |
| static assert(Test2b.b_max == 7); |
| } |
| |
| struct Test3b |
| { |
| mixin(bitfields!(bool, "a", 0, |
| long, "b", 64)); |
| |
| static assert(Test3b.b_min == long.min); |
| static assert(Test3b.b_max == long.max); |
| } |
| |
| struct Test4b |
| { |
| mixin(bitfields!(long, "a", 32, |
| int, "b", 32)); |
| } |
| |
| // Sign extension tests |
| Test2b t2b; |
| Test4b t4b; |
| t2b.b = -5; assert(t2b.b == -5); |
| t2b.d = -5; assert(t2b.d == -5); |
| t2b.e = -5; assert(t2b.e == -5); |
| t4b.a = -5; assert(t4b.a == -5L); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=6686 |
| @safe unittest |
| { |
| union S { |
| ulong bits = ulong.max; |
| mixin (bitfields!( |
| ulong, "back", 31, |
| ulong, "front", 33) |
| ); |
| } |
| S num; |
| |
| num.bits = ulong.max; |
| num.back = 1; |
| assert(num.bits == 0xFFFF_FFFF_8000_0001uL); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=5942 |
| @safe unittest |
| { |
| struct S |
| { |
| mixin(bitfields!( |
| int, "a" , 32, |
| int, "b" , 32 |
| )); |
| } |
| |
| S data; |
| data.b = 42; |
| data.a = 1; |
| assert(data.b == 42); |
| } |
| |
| @safe unittest |
| { |
| struct Test |
| { |
| mixin(bitfields!(bool, "a", 1, |
| uint, "b", 3, |
| short, "c", 4)); |
| } |
| |
| @safe void test() pure nothrow |
| { |
| Test t; |
| |
| t.a = true; |
| t.b = 5; |
| t.c = 2; |
| |
| assert(t.a); |
| assert(t.b == 5); |
| assert(t.c == 2); |
| } |
| |
| test(); |
| } |
| |
| @safe unittest |
| { |
| { |
| static struct Integrals { |
| bool checkExpectations(bool eb, int ei, short es) { return b == eb && i == ei && s == es; } |
| |
| mixin(bitfields!( |
| bool, "b", 1, |
| uint, "i", 3, |
| short, "s", 4)); |
| } |
| Integrals i; |
| assert(i.checkExpectations(false, 0, 0)); |
| i.b = true; |
| assert(i.checkExpectations(true, 0, 0)); |
| i.i = 7; |
| assert(i.checkExpectations(true, 7, 0)); |
| i.s = -8; |
| assert(i.checkExpectations(true, 7, -8)); |
| i.s = 7; |
| assert(i.checkExpectations(true, 7, 7)); |
| } |
| |
| //https://issues.dlang.org/show_bug.cgi?id=8876 |
| { |
| struct MoreIntegrals { |
| bool checkExpectations(uint eu, ushort es, uint ei) { return u == eu && s == es && i == ei; } |
| |
| mixin(bitfields!( |
| uint, "u", 24, |
| short, "s", 16, |
| int, "i", 24)); |
| } |
| |
| MoreIntegrals i; |
| assert(i.checkExpectations(0, 0, 0)); |
| i.s = 20; |
| assert(i.checkExpectations(0, 20, 0)); |
| i.i = 72; |
| assert(i.checkExpectations(0, 20, 72)); |
| i.u = 8; |
| assert(i.checkExpectations(8, 20, 72)); |
| i.s = 7; |
| assert(i.checkExpectations(8, 7, 72)); |
| } |
| |
| enum A { True, False } |
| enum B { One, Two, Three, Four } |
| static struct Enums { |
| bool checkExpectations(A ea, B eb) { return a == ea && b == eb; } |
| |
| mixin(bitfields!( |
| A, "a", 1, |
| B, "b", 2, |
| uint, "", 5)); |
| } |
| Enums e; |
| assert(e.checkExpectations(A.True, B.One)); |
| e.a = A.False; |
| assert(e.checkExpectations(A.False, B.One)); |
| e.b = B.Three; |
| assert(e.checkExpectations(A.False, B.Three)); |
| |
| static struct SingleMember { |
| bool checkExpectations(bool eb) { return b == eb; } |
| |
| mixin(bitfields!( |
| bool, "b", 1, |
| uint, "", 7)); |
| } |
| SingleMember f; |
| assert(f.checkExpectations(false)); |
| f.b = true; |
| assert(f.checkExpectations(true)); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=12477 |
| @system unittest |
| { |
| import core.exception : AssertError; |
| import std.algorithm.searching : canFind; |
| |
| static struct S |
| { |
| mixin(bitfields!( |
| uint, "a", 6, |
| int, "b", 2)); |
| } |
| |
| S s; |
| |
| try { s.a = uint.max; assert(0); } |
| catch (AssertError ae) |
| { assert(ae.msg.canFind("Value is greater than the maximum value of bitfield 'a'"), ae.msg); } |
| |
| try { s.b = int.min; assert(0); } |
| catch (AssertError ae) |
| { assert(ae.msg.canFind("Value is smaller than the minimum value of bitfield 'b'"), ae.msg); } |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=15305 |
| @safe unittest |
| { |
| struct S { |
| mixin(bitfields!( |
| bool, "alice", 1, |
| ulong, "bob", 63, |
| )); |
| } |
| |
| S s; |
| s.bob = long.max - 1; |
| s.alice = false; |
| assert(s.bob == long.max - 1); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=21634 |
| @safe unittest |
| { |
| struct A |
| { |
| mixin(bitfields!(int, "", 1, |
| int, "gshared", 7)); |
| } |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=21725 |
| @safe unittest |
| { |
| struct S |
| { |
| mixin(bitfields!( |
| uint, q{foo}, 4, |
| uint, null, 4, |
| )); |
| } |
| } |
| |
| /** |
| This string mixin generator allows one to create tagged pointers inside $(D_PARAM struct)s and $(D_PARAM class)es. |
| |
| A tagged pointer uses the bits known to be zero in a normal pointer or class reference to store extra information. |
| For example, a pointer to an integer must be 4-byte aligned, so there are 2 bits that are always known to be zero. |
| One can store a 2-bit integer there. |
| |
| The example above creates a tagged pointer in the struct A. The pointer is of type |
| `uint*` as specified by the first argument, and is named x, as specified by the second |
| argument. |
| |
| Following arguments works the same way as `bitfield`'s. The bitfield must fit into the |
| bits known to be zero because of the pointer alignment. |
| */ |
| |
| template taggedPointer(T : T*, string name, Ts...) { |
| enum taggedPointer = createTaggedReference!(T*, T.alignof, name, Ts); |
| } |
| |
| /// |
| @safe unittest |
| { |
| struct A |
| { |
| int a; |
| mixin(taggedPointer!( |
| uint*, "x", |
| bool, "b1", 1, |
| bool, "b2", 1)); |
| } |
| A obj; |
| obj.x = new uint; |
| obj.b1 = true; |
| obj.b2 = false; |
| } |
| |
| @system unittest |
| { |
| struct Test5 |
| { |
| mixin(taggedPointer!( |
| int*, "a", |
| uint, "b", 2)); |
| } |
| |
| Test5 t5; |
| t5.a = null; |
| t5.b = 3; |
| assert(t5.a is null); |
| assert(t5.b == 3); |
| |
| int myint = 42; |
| t5.a = &myint; |
| assert(t5.a is &myint); |
| assert(t5.b == 3); |
| } |
| |
| /** |
| This string mixin generator allows one to create tagged class reference inside $(D_PARAM struct)s and $(D_PARAM class)es. |
| |
| A tagged class reference uses the bits known to be zero in a normal class reference to store extra information. |
| For example, a pointer to an integer must be 4-byte aligned, so there are 2 bits that are always known to be zero. |
| One can store a 2-bit integer there. |
| |
| The example above creates a tagged reference to an Object in the struct A. This expects the same parameters |
| as `taggedPointer`, except the first argument which must be a class type instead of a pointer type. |
| */ |
| |
| template taggedClassRef(T, string name, Ts...) |
| if (is(T == class)) |
| { |
| enum taggedClassRef = createTaggedReference!(T, 8, name, Ts); |
| } |
| |
| /// |
| @safe unittest |
| { |
| struct A |
| { |
| int a; |
| mixin(taggedClassRef!( |
| Object, "o", |
| uint, "i", 2)); |
| } |
| A obj; |
| obj.o = new Object(); |
| obj.i = 3; |
| } |
| |
| @system unittest |
| { |
| struct Test6 |
| { |
| mixin(taggedClassRef!( |
| Object, "o", |
| bool, "b", 1)); |
| } |
| |
| Test6 t6; |
| t6.o = null; |
| t6.b = false; |
| assert(t6.o is null); |
| assert(t6.b == false); |
| |
| auto o = new Object(); |
| t6.o = o; |
| t6.b = true; |
| assert(t6.o is o); |
| assert(t6.b == true); |
| } |
| |
| @safe unittest |
| { |
| static assert(!__traits(compiles, |
| taggedPointer!( |
| int*, "a", |
| uint, "b", 3))); |
| |
| static assert(!__traits(compiles, |
| taggedClassRef!( |
| Object, "a", |
| uint, "b", 4))); |
| |
| struct S { |
| mixin(taggedClassRef!( |
| Object, "a", |
| bool, "b", 1)); |
| } |
| |
| const S s; |
| void bar(S s) {} |
| |
| static assert(!__traits(compiles, bar(s))); |
| } |
| |
| /** |
| Allows manipulating the fraction, exponent, and sign parts of a |
| `float` separately. The definition is: |
| |
| ---- |
| struct FloatRep |
| { |
| union |
| { |
| float value; |
| mixin(bitfields!( |
| uint, "fraction", 23, |
| ubyte, "exponent", 8, |
| bool, "sign", 1)); |
| } |
| enum uint bias = 127, fractionBits = 23, exponentBits = 8, signBits = 1; |
| } |
| ---- |
| */ |
| alias FloatRep = FloatingPointRepresentation!float; |
| |
| /** |
| Allows manipulating the fraction, exponent, and sign parts of a |
| `double` separately. The definition is: |
| |
| ---- |
| struct DoubleRep |
| { |
| union |
| { |
| double value; |
| mixin(bitfields!( |
| ulong, "fraction", 52, |
| ushort, "exponent", 11, |
| bool, "sign", 1)); |
| } |
| enum uint bias = 1023, signBits = 1, fractionBits = 52, exponentBits = 11; |
| } |
| ---- |
| */ |
| alias DoubleRep = FloatingPointRepresentation!double; |
| |
| private struct FloatingPointRepresentation(T) |
| { |
| static if (is(T == float)) |
| { |
| enum uint bias = 127, fractionBits = 23, exponentBits = 8, signBits = 1; |
| alias FractionType = uint; |
| alias ExponentType = ubyte; |
| } |
| else |
| { |
| enum uint bias = 1023, fractionBits = 52, exponentBits = 11, signBits = 1; |
| alias FractionType = ulong; |
| alias ExponentType = ushort; |
| } |
| |
| union |
| { |
| T value; |
| mixin(bitfields!( |
| FractionType, "fraction", fractionBits, |
| ExponentType, "exponent", exponentBits, |
| bool, "sign", signBits)); |
| } |
| } |
| |
| /// |
| @safe unittest |
| { |
| FloatRep rep = {value: 0}; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 0); |
| assert(!rep.sign); |
| |
| rep.value = 42; |
| assert(rep.fraction == 2621440); |
| assert(rep.exponent == 132); |
| assert(!rep.sign); |
| |
| rep.value = 10; |
| assert(rep.fraction == 2097152); |
| assert(rep.exponent == 130); |
| } |
| |
| /// |
| @safe unittest |
| { |
| FloatRep rep = {value: 1}; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 127); |
| assert(!rep.sign); |
| |
| rep.exponent = 126; |
| assert(rep.value == 0.5); |
| |
| rep.exponent = 130; |
| assert(rep.value == 8); |
| } |
| |
| /// |
| @safe unittest |
| { |
| FloatRep rep = {value: 1}; |
| rep.value = -0.5; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 126); |
| assert(rep.sign); |
| |
| rep.value = -1. / 3; |
| assert(rep.fraction == 2796203); |
| assert(rep.exponent == 125); |
| assert(rep.sign); |
| } |
| |
| /// |
| @safe unittest |
| { |
| DoubleRep rep = {value: 0}; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 0); |
| assert(!rep.sign); |
| |
| rep.value = 42; |
| assert(rep.fraction == 1407374883553280); |
| assert(rep.exponent == 1028); |
| assert(!rep.sign); |
| |
| rep.value = 10; |
| assert(rep.fraction == 1125899906842624); |
| assert(rep.exponent == 1026); |
| } |
| |
| /// |
| @safe unittest |
| { |
| DoubleRep rep = {value: 1}; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 1023); |
| assert(!rep.sign); |
| |
| rep.exponent = 1022; |
| assert(rep.value == 0.5); |
| |
| rep.exponent = 1026; |
| assert(rep.value == 8); |
| } |
| |
| /// |
| @safe unittest |
| { |
| DoubleRep rep = {value: 1}; |
| rep.value = -0.5; |
| assert(rep.fraction == 0); |
| assert(rep.exponent == 1022); |
| assert(rep.sign); |
| |
| rep.value = -1. / 3; |
| assert(rep.fraction == 1501199875790165); |
| assert(rep.exponent == 1021); |
| assert(rep.sign); |
| } |
| |
| /// Reading |
| @safe unittest |
| { |
| DoubleRep x; |
| x.value = 1.0; |
| assert(x.fraction == 0 && x.exponent == 1023 && !x.sign); |
| x.value = -0.5; |
| assert(x.fraction == 0 && x.exponent == 1022 && x.sign); |
| x.value = 0.5; |
| assert(x.fraction == 0 && x.exponent == 1022 && !x.sign); |
| } |
| |
| /// Writing |
| @safe unittest |
| { |
| DoubleRep x; |
| x.fraction = 1125899906842624; |
| x.exponent = 1025; |
| x.sign = true; |
| assert(x.value == -5.0); |
| } |
| |
| /** |
| A dynamic array of bits. Each bit in a `BitArray` can be manipulated individually |
| or by the standard bitwise operators `&`, `|`, `^`, `~`, `>>`, `<<` and also by |
| other effective member functions; most of them work relative to the `BitArray`'s |
| dimension (see $(LREF dim)), instead of its $(LREF length). |
| */ |
| struct BitArray |
| { |
| private: |
| |
| import core.bitop : btc, bts, btr, bsf, bt; |
| import std.format.spec : FormatSpec; |
| |
| size_t _len; |
| size_t* _ptr; |
| enum bitsPerSizeT = size_t.sizeof * 8; |
| |
| @property size_t fullWords() const @nogc pure nothrow |
| { |
| return _len / bitsPerSizeT; |
| } |
| // Number of bits after the last full word |
| @property size_t endBits() const @nogc pure nothrow |
| { |
| return _len % bitsPerSizeT; |
| } |
| // Bit mask to extract the bits after the last full word |
| @property size_t endMask() const @nogc pure nothrow |
| { |
| return (size_t(1) << endBits) - 1; |
| } |
| static size_t lenToDim(size_t len) @nogc pure nothrow @safe |
| { |
| return (len + (bitsPerSizeT-1)) / bitsPerSizeT; |
| } |
| |
| public: |
| /** |
| Creates a `BitArray` from a `bool` array, such that `bool` values read |
| from left to right correspond to subsequent bits in the `BitArray`. |
| |
| Params: ba = Source array of `bool` values. |
| */ |
| this(in bool[] ba) nothrow pure |
| { |
| length = ba.length; |
| foreach (i, b; ba) |
| { |
| this[i] = b; |
| } |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| bool[] input = [true, false, false, true, true]; |
| auto a = BitArray(input); |
| assert(a.length == 5); |
| assert(a.bitsSet.equal([0, 3, 4])); |
| |
| // This also works because an implicit cast to bool[] occurs for this array. |
| auto b = BitArray([0, 0, 1]); |
| assert(b.length == 3); |
| assert(b.bitsSet.equal([2])); |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.array : array; |
| import std.range : iota, repeat; |
| |
| BitArray a = true.repeat(70).array; |
| assert(a.length == 70); |
| assert(a.bitsSet.equal(iota(0, 70))); |
| } |
| |
| /** |
| Creates a `BitArray` from the raw contents of the source array. The |
| source array is not copied but simply acts as the underlying array |
| of bits, which stores data as `size_t` units. |
| |
| That means a particular care should be taken when passing an array |
| of a type different than `size_t`, firstly because its length should |
| be a multiple of `size_t.sizeof`, and secondly because how the bits |
| are mapped: |
| --- |
| size_t[] source = [1, 2, 3, 3424234, 724398, 230947, 389492]; |
| enum sbits = size_t.sizeof * 8; |
| auto ba = BitArray(source, source.length * sbits); |
| foreach (n; 0 .. source.length * sbits) |
| { |
| auto nth_bit = cast(bool) (source[n / sbits] & (1L << (n % sbits))); |
| assert(ba[n] == nth_bit); |
| } |
| --- |
| The least significant bit in any `size_t` unit is the starting bit of this |
| unit, and the most significant bit is the last bit of this unit. Therefore, |
| passing e.g. an array of `int`s may result in a different `BitArray` |
| depending on the processor's endianness. |
| |
| This constructor is the inverse of $(LREF opCast). |
| |
| Params: |
| v = Source array. `v.length` must be a multple of `size_t.sizeof`. |
| numbits = Number of bits to be mapped from the source array, i.e. |
| length of the created `BitArray`. |
| */ |
| this(void[] v, size_t numbits) @nogc nothrow pure |
| in |
| { |
| assert(numbits <= v.length * 8, |
| "numbits must be less than or equal to v.length * 8"); |
| assert(v.length % size_t.sizeof == 0, |
| "v.length must be a multiple of the size of size_t"); |
| } |
| do |
| { |
| _ptr = cast(size_t*) v.ptr; |
| _len = numbits; |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| auto a = BitArray([1, 0, 0, 1, 1]); |
| |
| // Inverse of the cast. |
| auto v = cast(void[]) a; |
| auto b = BitArray(v, a.length); |
| |
| assert(b.length == 5); |
| assert(b.bitsSet.equal([0, 3, 4])); |
| |
| // a and b share the underlying data. |
| a[0] = 0; |
| assert(b[0] == 0); |
| assert(a == b); |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| size_t[] source = [0b1100, 0b0011]; |
| enum sbits = size_t.sizeof * 8; |
| auto ba = BitArray(source, source.length * sbits); |
| // The least significant bit in each unit is this unit's starting bit. |
| assert(ba.bitsSet.equal([2, 3, sbits, sbits + 1])); |
| } |
| |
| /// |
| @system unittest |
| { |
| // Example from the doc for this constructor. |
| static immutable size_t[] sourceData = [1, 0b101, 3, 3424234, 724398, 230947, 389492]; |
| size_t[] source = sourceData.dup; |
| enum sbits = size_t.sizeof * 8; |
| auto ba = BitArray(source, source.length * sbits); |
| foreach (n; 0 .. source.length * sbits) |
| { |
| auto nth_bit = cast(bool) (source[n / sbits] & (1L << (n % sbits))); |
| assert(ba[n] == nth_bit); |
| } |
| |
| // Example of mapping only part of the array. |
| import std.algorithm.comparison : equal; |
| |
| auto bc = BitArray(source, sbits + 1); |
| assert(bc.bitsSet.equal([0, sbits])); |
| // Source array has not been modified. |
| assert(source == sourceData); |
| } |
| |
| // Deliberately undocumented: raw initialization of bit array. |
| this(size_t len, size_t* ptr) @nogc nothrow pure |
| { |
| _len = len; |
| _ptr = ptr; |
| } |
| |
| /** |
| Returns: Dimension i.e. the number of native words backing this `BitArray`. |
| |
| Technically, this is the length of the underlying array storing bits, which |
| is equal to `ceil(length / (size_t.sizeof * 8))`, as bits are packed into |
| `size_t` units. |
| */ |
| @property size_t dim() const @nogc nothrow pure @safe |
| { |
| return lenToDim(_len); |
| } |
| |
| /** |
| Returns: Number of bits in the `BitArray`. |
| */ |
| @property size_t length() const @nogc nothrow pure @safe |
| { |
| return _len; |
| } |
| |
| /********************************************** |
| * Sets the amount of bits in the `BitArray`. |
| * $(RED Warning: increasing length may overwrite bits in |
| * the final word of the current underlying data regardless |
| * of whether it is shared between BitArray objects. i.e. D |
| * dynamic array extension semantics are not followed.) |
| */ |
| @property size_t length(size_t newlen) pure nothrow @system |
| { |
| if (newlen != _len) |
| { |
| size_t olddim = dim; |
| immutable newdim = lenToDim(newlen); |
| |
| if (newdim != olddim) |
| { |
| // Create a fake array so we can use D's realloc machinery |
| auto b = _ptr[0 .. olddim]; |
| b.length = newdim; // realloc |
| _ptr = b.ptr; |
| } |
| |
| auto oldlen = _len; |
| _len = newlen; |
| if (oldlen < newlen) |
| { |
| auto end = ((oldlen / bitsPerSizeT) + 1) * bitsPerSizeT; |
| if (end > newlen) |
| end = newlen; |
| this[oldlen .. end] = 0; |
| } |
| } |
| return _len; |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=20240 |
| @system unittest |
| { |
| BitArray ba; |
| |
| ba.length = 1; |
| ba[0] = 1; |
| ba.length = 0; |
| ba.length = 1; |
| assert(ba[0] == 0); // OK |
| |
| ba.length = 2; |
| ba[1] = 1; |
| ba.length = 1; |
| ba.length = 2; |
| assert(ba[1] == 0); // Fail |
| } |
| |
| /********************************************** |
| * Gets the `i`'th bit in the `BitArray`. |
| */ |
| bool opIndex(size_t i) const @nogc pure nothrow |
| in |
| { |
| assert(i < _len, "i must be less than the length"); |
| } |
| do |
| { |
| return cast(bool) bt(_ptr, i); |
| } |
| |
| /// |
| @system unittest |
| { |
| static void fun(const BitArray arr) |
| { |
| auto x = arr[0]; |
| assert(x == 1); |
| } |
| BitArray a; |
| a.length = 3; |
| a[0] = 1; |
| fun(a); |
| } |
| |
| /********************************************** |
| * Sets the `i`'th bit in the `BitArray`. |
| */ |
| bool opIndexAssign(bool b, size_t i) @nogc pure nothrow |
| in |
| { |
| assert(i < _len, "i must be less than the length"); |
| } |
| do |
| { |
| if (b) |
| bts(_ptr, i); |
| else |
| btr(_ptr, i); |
| return b; |
| } |
| |
| /** |
| Sets all the values in the `BitArray` to the |
| value specified by `val`. |
| */ |
| void opSliceAssign(bool val) @nogc pure nothrow |
| { |
| _ptr[0 .. fullWords] = val ? ~size_t(0) : 0; |
| if (endBits) |
| { |
| if (val) |
| _ptr[fullWords] |= endMask; |
| else |
| _ptr[fullWords] &= ~endMask; |
| } |
| } |
| |
| /// |
| @system pure nothrow unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| auto b = BitArray([1, 0, 1, 0, 1, 1]); |
| |
| b[] = true; |
| // all bits are set |
| assert(b.bitsSet.equal([0, 1, 2, 3, 4, 5])); |
| |
| b[] = false; |
| // none of the bits are set |
| assert(b.bitsSet.empty); |
| } |
| |
| /** |
| Sets the bits of a slice of `BitArray` starting |
| at index `start` and ends at index ($D end - 1) |
| with the values specified by `val`. |
| */ |
| void opSliceAssign(bool val, size_t start, size_t end) @nogc pure nothrow |
| in |
| { |
| assert(start <= end, "start must be less or equal to end"); |
| assert(end <= length, "end must be less or equal to the length"); |
| } |
| do |
| { |
| size_t startBlock = start / bitsPerSizeT; |
| size_t endBlock = end / bitsPerSizeT; |
| size_t startOffset = start % bitsPerSizeT; |
| size_t endOffset = end % bitsPerSizeT; |
| |
| if (startBlock == endBlock) |
| { |
| size_t startBlockMask = ~((size_t(1) << startOffset) - 1); |
| size_t endBlockMask = (size_t(1) << endOffset) - 1; |
| size_t joinMask = startBlockMask & endBlockMask; |
| if (val) |
| _ptr[startBlock] |= joinMask; |
| else |
| _ptr[startBlock] &= ~joinMask; |
| return; |
| } |
| |
| if (startOffset != 0) |
| { |
| size_t startBlockMask = ~((size_t(1) << startOffset) - 1); |
| if (val) |
| _ptr[startBlock] |= startBlockMask; |
| else |
| _ptr[startBlock] &= ~startBlockMask; |
| ++startBlock; |
| } |
| if (endOffset != 0) |
| { |
| size_t endBlockMask = (size_t(1) << endOffset) - 1; |
| if (val) |
| _ptr[endBlock] |= endBlockMask; |
| else |
| _ptr[endBlock] &= ~endBlockMask; |
| } |
| _ptr[startBlock .. endBlock] = size_t(0) - size_t(val); |
| } |
| |
| /// |
| @system pure nothrow unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.range : iota; |
| import std.stdio; |
| |
| auto b = BitArray([1, 0, 0, 0, 1, 1, 0]); |
| b[1 .. 3] = true; |
| assert(b.bitsSet.equal([0, 1, 2, 4, 5])); |
| |
| bool[72] bitArray; |
| auto b1 = BitArray(bitArray); |
| b1[63 .. 67] = true; |
| assert(b1.bitsSet.equal([63, 64, 65, 66])); |
| b1[63 .. 67] = false; |
| assert(b1.bitsSet.empty); |
| b1[0 .. 64] = true; |
| assert(b1.bitsSet.equal(iota(0, 64))); |
| b1[0 .. 64] = false; |
| assert(b1.bitsSet.empty); |
| |
| bool[256] bitArray2; |
| auto b2 = BitArray(bitArray2); |
| b2[3 .. 245] = true; |
| assert(b2.bitsSet.equal(iota(3, 245))); |
| b2[3 .. 245] = false; |
| assert(b2.bitsSet.empty); |
| } |
| |
| /** |
| Flips all the bits in the `BitArray` |
| */ |
| void flip() @nogc pure nothrow |
| { |
| foreach (i; 0 .. fullWords) |
| _ptr[i] = ~_ptr[i]; |
| |
| if (endBits) |
| _ptr[fullWords] = (~_ptr[fullWords]) & endMask; |
| } |
| |
| /// |
| @system pure nothrow unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.range : iota; |
| |
| // positions 0, 2, 4 are set |
| auto b = BitArray([1, 0, 1, 0, 1, 0]); |
| b.flip(); |
| // after flipping, positions 1, 3, 5 are set |
| assert(b.bitsSet.equal([1, 3, 5])); |
| |
| bool[270] bits; |
| auto b1 = BitArray(bits); |
| b1.flip(); |
| assert(b1.bitsSet.equal(iota(0, 270))); |
| } |
| |
| /** |
| Flips a single bit, specified by `pos` |
| */ |
| void flip(size_t i) @nogc pure nothrow |
| { |
| bt(_ptr, i) ? btr(_ptr, i) : bts(_ptr, i); |
| } |
| |
| /// |
| @system pure nothrow unittest |
| { |
| auto ax = BitArray([1, 0, 0, 1]); |
| ax.flip(0); |
| assert(ax[0] == 0); |
| |
| bool[200] y; |
| y[90 .. 130] = true; |
| auto ay = BitArray(y); |
| ay.flip(100); |
| assert(ay[100] == 0); |
| } |
| |
| /********************************************** |
| * Counts all the set bits in the `BitArray` |
| */ |
| size_t count() const @nogc pure nothrow |
| { |
| if (_ptr) |
| { |
| size_t bitCount; |
| foreach (i; 0 .. fullWords) |
| bitCount += countBitsSet(_ptr[i]); |
| if (endBits) |
| bitCount += countBitsSet(_ptr[fullWords] & endMask); |
| return bitCount; |
| } |
| else |
| { |
| return 0; |
| } |
| } |
| |
| /// |
| @system pure nothrow unittest |
| { |
| auto a = BitArray([0, 1, 1, 0, 0, 1, 1]); |
| assert(a.count == 4); |
| |
| BitArray b; |
| assert(b.count == 0); |
| |
| bool[200] boolArray; |
| boolArray[45 .. 130] = true; |
| auto c = BitArray(boolArray); |
| assert(c.count == 85); |
| } |
| |
| /********************************************** |
| * Duplicates the `BitArray` and its contents. |
| */ |
| @property BitArray dup() const pure nothrow |
| { |
| BitArray ba; |
| |
| auto b = _ptr[0 .. dim].dup; |
| ba._len = _len; |
| ba._ptr = b.ptr; |
| return ba; |
| } |
| |
| /// |
| @system unittest |
| { |
| BitArray a; |
| BitArray b; |
| |
| a.length = 3; |
| a[0] = 1; a[1] = 0; a[2] = 1; |
| b = a.dup; |
| assert(b.length == 3); |
| foreach (i; 0 .. 3) |
| assert(b[i] == (((i ^ 1) & 1) ? true : false)); |
| } |
| |
| /********************************************** |
| * Support for `foreach` loops for `BitArray`. |
| */ |
| int opApply(scope int delegate(ref bool) dg) |
| { |
| int result; |
| |
| foreach (i; 0 .. _len) |
| { |
| bool b = opIndex(i); |
| result = dg(b); |
| this[i] = b; |
| if (result) |
| break; |
| } |
| return result; |
| } |
| |
| /** ditto */ |
| int opApply(scope int delegate(bool) dg) const |
| { |
| int result; |
| |
| foreach (i; 0 .. _len) |
| { |
| immutable b = opIndex(i); |
| result = dg(b); |
| if (result) |
| break; |
| } |
| return result; |
| } |
| |
| /** ditto */ |
| int opApply(scope int delegate(size_t, ref bool) dg) |
| { |
| int result; |
| |
| foreach (i; 0 .. _len) |
| { |
| bool b = opIndex(i); |
| result = dg(i, b); |
| this[i] = b; |
| if (result) |
| break; |
| } |
| return result; |
| } |
| |
| /** ditto */ |
| int opApply(scope int delegate(size_t, bool) dg) const |
| { |
| int result; |
| |
| foreach (i; 0 .. _len) |
| { |
| immutable b = opIndex(i); |
| result = dg(i, b); |
| if (result) |
| break; |
| } |
| return result; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1]; |
| |
| auto a = BitArray(ba); |
| |
| int i; |
| foreach (b;a) |
| { |
| switch (i) |
| { |
| case 0: assert(b == true); break; |
| case 1: assert(b == false); break; |
| case 2: assert(b == true); break; |
| default: assert(0); |
| } |
| i++; |
| } |
| |
| foreach (j,b;a) |
| { |
| switch (j) |
| { |
| case 0: assert(b == true); break; |
| case 1: assert(b == false); break; |
| case 2: assert(b == true); break; |
| default: assert(0); |
| } |
| } |
| } |
| |
| |
| /********************************************** |
| * Reverses the bits of the `BitArray`. |
| */ |
| @property BitArray reverse() @nogc pure nothrow return |
| out (result) |
| { |
| assert(result == this, "the result must be equal to this"); |
| } |
| do |
| { |
| if (_len >= 2) |
| { |
| bool t; |
| size_t lo, hi; |
| |
| lo = 0; |
| hi = _len - 1; |
| for (; lo < hi; lo++, hi--) |
| { |
| t = this[lo]; |
| this[lo] = this[hi]; |
| this[hi] = t; |
| } |
| } |
| return this; |
| } |
| |
| /// |
| @system unittest |
| { |
| BitArray b; |
| bool[5] data = [1,0,1,1,0]; |
| |
| b = BitArray(data); |
| b.reverse; |
| foreach (i; 0 .. data.length) |
| assert(b[i] == data[4 - i]); |
| } |
| |
| |
| /********************************************** |
| * Sorts the `BitArray`'s elements. |
| */ |
| @property BitArray sort() @nogc pure nothrow return |
| out (result) |
| { |
| assert(result == this, "the result must be equal to this"); |
| } |
| do |
| { |
| if (_len >= 2) |
| { |
| size_t lo, hi; |
| |
| lo = 0; |
| hi = _len - 1; |
| while (1) |
| { |
| while (1) |
| { |
| if (lo >= hi) |
| goto Ldone; |
| if (this[lo] == true) |
| break; |
| lo++; |
| } |
| |
| while (1) |
| { |
| if (lo >= hi) |
| goto Ldone; |
| if (this[hi] == false) |
| break; |
| hi--; |
| } |
| |
| this[lo] = false; |
| this[hi] = true; |
| |
| lo++; |
| hi--; |
| } |
| } |
| Ldone: |
| return this; |
| } |
| |
| /// |
| @system unittest |
| { |
| size_t x = 0b1100011000; |
| auto ba = BitArray(10, &x); |
| ba.sort; |
| foreach (i; 0 .. 6) |
| assert(ba[i] == false); |
| foreach (i; 6 .. 10) |
| assert(ba[i] == true); |
| } |
| |
| |
| /*************************************** |
| * Support for operators == and != for `BitArray`. |
| */ |
| bool opEquals(const ref BitArray a2) const @nogc pure nothrow |
| { |
| if (this.length != a2.length) |
| return false; |
| auto p1 = this._ptr; |
| auto p2 = a2._ptr; |
| |
| if (p1[0 .. fullWords] != p2[0 .. fullWords]) |
| return false; |
| |
| if (!endBits) |
| return true; |
| |
| auto i = fullWords; |
| return (p1[i] & endMask) == (p2[i] & endMask); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1]; |
| bool[] bc = [1,0,1,0,1,0,1]; |
| bool[] bd = [1,0,1,1,1]; |
| bool[] be = [1,0,1,0,1]; |
| 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]; |
| 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]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| auto c = BitArray(bc); |
| auto d = BitArray(bd); |
| auto e = BitArray(be); |
| auto f = BitArray(bf); |
| auto g = BitArray(bg); |
| |
| assert(a != b); |
| assert(a != c); |
| assert(a != d); |
| assert(a == e); |
| assert(f != g); |
| } |
| |
| /*************************************** |
| * Supports comparison operators for `BitArray`. |
| */ |
| int opCmp(BitArray a2) const @nogc pure nothrow |
| { |
| const lesser = this.length < a2.length ? &this : &a2; |
| immutable fullWords = lesser.fullWords; |
| immutable endBits = lesser.endBits; |
| auto p1 = this._ptr; |
| auto p2 = a2._ptr; |
| |
| foreach (i; 0 .. fullWords) |
| { |
| if (p1[i] != p2[i]) |
| { |
| return p1[i] & (size_t(1) << bsf(p1[i] ^ p2[i])) ? 1 : -1; |
| } |
| } |
| |
| if (endBits) |
| { |
| immutable i = fullWords; |
| immutable diff = p1[i] ^ p2[i]; |
| if (diff) |
| { |
| immutable index = bsf(diff); |
| if (index < endBits) |
| { |
| return p1[i] & (size_t(1) << index) ? 1 : -1; |
| } |
| } |
| } |
| |
| // Standard: |
| // A bool value can be implicitly converted to any integral type, |
| // with false becoming 0 and true becoming 1 |
| return (this.length > a2.length) - (this.length < a2.length); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1]; |
| bool[] bc = [1,0,1,0,1,0,1]; |
| bool[] bd = [1,0,1,1,1]; |
| bool[] be = [1,0,1,0,1]; |
| 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]; |
| 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]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| auto c = BitArray(bc); |
| auto d = BitArray(bd); |
| auto e = BitArray(be); |
| auto f = BitArray(bf); |
| auto g = BitArray(bg); |
| |
| assert(a > b); |
| assert(a >= b); |
| assert(a < c); |
| assert(a <= c); |
| assert(a < d); |
| assert(a <= d); |
| assert(a == e); |
| assert(a <= e); |
| assert(a >= e); |
| assert(f < g); |
| assert(g <= g); |
| } |
| |
| @system unittest |
| { |
| bool[] v; |
| foreach (i; 1 .. 256) |
| { |
| v.length = i; |
| v[] = false; |
| auto x = BitArray(v); |
| v[i-1] = true; |
| auto y = BitArray(v); |
| assert(x < y); |
| assert(x <= y); |
| } |
| |
| BitArray a1, a2; |
| |
| for (size_t len = 4; len <= 256; len <<= 1) |
| { |
| a1.length = a2.length = len; |
| a1[len-2] = a2[len-1] = true; |
| assert(a1 > a2); |
| a1[len-2] = a2[len-1] = false; |
| } |
| |
| foreach (j; 1 .. a1.length) |
| { |
| a1[j-1] = a2[j] = true; |
| assert(a1 > a2); |
| a1[j-1] = a2[j] = false; |
| } |
| } |
| |
| /*************************************** |
| * Support for hashing for `BitArray`. |
| */ |
| size_t toHash() const @nogc pure nothrow |
| { |
| size_t hash = 3557; |
| auto fullBytes = _len / 8; |
| foreach (i; 0 .. fullBytes) |
| { |
| hash *= 3559; |
| hash += (cast(byte*) this._ptr)[i]; |
| } |
| foreach (i; 8*fullBytes .. _len) |
| { |
| hash *= 3571; |
| hash += this[i]; |
| } |
| return hash; |
| } |
| |
| /*************************************** |
| * Convert to `void[]`. |
| */ |
| inout(void)[] opCast(T : const void[])() inout @nogc pure nothrow |
| { |
| return cast(inout void[]) _ptr[0 .. dim]; |
| } |
| |
| /*************************************** |
| * Convert to `size_t[]`. |
| */ |
| inout(size_t)[] opCast(T : const size_t[])() inout @nogc pure nothrow |
| { |
| return _ptr[0 .. dim]; |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.array : array; |
| import std.range : repeat, take; |
| |
| // bit array with 300 elements |
| auto a = BitArray(true.repeat.take(300).array); |
| size_t[] v = cast(size_t[]) a; |
| const blockSize = size_t.sizeof * 8; |
| assert(v.length == (a.length + blockSize - 1) / blockSize); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=20606 |
| @system unittest |
| { |
| import std.meta : AliasSeq; |
| |
| static foreach (alias T; AliasSeq!(void, size_t)) |
| {{ |
| BitArray m; |
| T[] ma = cast(T[]) m; |
| |
| const BitArray c; |
| const(T)[] ca = cast(const T[]) c; |
| |
| immutable BitArray i; |
| immutable(T)[] ia = cast(immutable T[]) i; |
| |
| // Cross-mutability |
| ca = cast(const T[]) m; |
| ca = cast(const T[]) i; |
| |
| // Invalid cast don't compile |
| static assert(!is(typeof(cast(T[]) c))); |
| static assert(!is(typeof(cast(T[]) i))); |
| static assert(!is(typeof(cast(immutable T[]) m))); |
| static assert(!is(typeof(cast(immutable T[]) c))); |
| }} |
| } |
| |
| /*************************************** |
| * Support for unary operator ~ for `BitArray`. |
| */ |
| BitArray opUnary(string op)() const pure nothrow |
| if (op == "~") |
| { |
| auto dim = this.dim; |
| |
| BitArray result; |
| result.length = _len; |
| |
| result._ptr[0 .. dim] = ~this._ptr[0 .. dim]; |
| |
| // Avoid putting garbage in extra bits |
| // Remove once we zero on length extension |
| if (endBits) |
| result._ptr[dim - 1] &= endMask; |
| |
| return result; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| |
| auto a = BitArray(ba); |
| BitArray b = ~a; |
| |
| assert(b[0] == 0); |
| assert(b[1] == 1); |
| assert(b[2] == 0); |
| assert(b[3] == 1); |
| assert(b[4] == 0); |
| } |
| |
| |
| /*************************************** |
| * Support for binary bitwise operators for `BitArray`. |
| */ |
| BitArray opBinary(string op)(const BitArray e2) const pure nothrow |
| if (op == "-" || op == "&" || op == "|" || op == "^") |
| in |
| { |
| assert(e2.length == _len, "e2 must have the same length as this"); |
| } |
| do |
| { |
| auto dim = this.dim; |
| |
| BitArray result; |
| result.length = _len; |
| |
| static if (op == "-") |
| result._ptr[0 .. dim] = this._ptr[0 .. dim] & ~e2._ptr[0 .. dim]; |
| else |
| mixin("result._ptr[0 .. dim] = this._ptr[0 .. dim]"~op~" e2._ptr[0 .. dim];"); |
| |
| // Avoid putting garbage in extra bits |
| // Remove once we zero on length extension |
| if (endBits) |
| result._ptr[dim - 1] &= endMask; |
| |
| return result; |
| } |
| |
| /// |
| @system unittest |
| { |
| static bool[] ba = [1,0,1,0,1]; |
| static bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| BitArray c = a & b; |
| |
| assert(c[0] == 1); |
| assert(c[1] == 0); |
| assert(c[2] == 1); |
| assert(c[3] == 0); |
| assert(c[4] == 0); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| BitArray c = a | b; |
| |
| assert(c[0] == 1); |
| assert(c[1] == 0); |
| assert(c[2] == 1); |
| assert(c[3] == 1); |
| assert(c[4] == 1); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| BitArray c = a ^ b; |
| |
| assert(c[0] == 0); |
| assert(c[1] == 0); |
| assert(c[2] == 0); |
| assert(c[3] == 1); |
| assert(c[4] == 1); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| BitArray c = a - b; |
| |
| assert(c[0] == 0); |
| assert(c[1] == 0); |
| assert(c[2] == 0); |
| assert(c[3] == 0); |
| assert(c[4] == 1); |
| } |
| |
| |
| /*************************************** |
| * Support for operator op= for `BitArray`. |
| */ |
| BitArray opOpAssign(string op)(const BitArray e2) @nogc pure nothrow return scope |
| if (op == "-" || op == "&" || op == "|" || op == "^") |
| in |
| { |
| assert(e2.length == _len, "e2 must have the same length as this"); |
| } |
| do |
| { |
| foreach (i; 0 .. fullWords) |
| { |
| static if (op == "-") |
| _ptr[i] &= ~e2._ptr[i]; |
| else |
| mixin("_ptr[i] "~op~"= e2._ptr[i];"); |
| } |
| if (!endBits) |
| return this; |
| |
| size_t i = fullWords; |
| size_t endWord = _ptr[i]; |
| static if (op == "-") |
| endWord &= ~e2._ptr[i]; |
| else |
| mixin("endWord "~op~"= e2._ptr[i];"); |
| _ptr[i] = (_ptr[i] & ~endMask) | (endWord & endMask); |
| |
| return this; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1,1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| BitArray c = a; |
| c.length = 5; |
| c &= b; |
| assert(a[5] == 1); |
| assert(a[6] == 0); |
| assert(a[7] == 1); |
| assert(a[8] == 0); |
| assert(a[9] == 1); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| a &= b; |
| assert(a[0] == 1); |
| assert(a[1] == 0); |
| assert(a[2] == 1); |
| assert(a[3] == 0); |
| assert(a[4] == 0); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| a |= b; |
| assert(a[0] == 1); |
| assert(a[1] == 0); |
| assert(a[2] == 1); |
| assert(a[3] == 1); |
| assert(a[4] == 1); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| a ^= b; |
| assert(a[0] == 0); |
| assert(a[1] == 0); |
| assert(a[2] == 0); |
| assert(a[3] == 1); |
| assert(a[4] == 1); |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| bool[] bb = [1,0,1,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| |
| a -= b; |
| assert(a[0] == 0); |
| assert(a[1] == 0); |
| assert(a[2] == 0); |
| assert(a[3] == 0); |
| assert(a[4] == 1); |
| } |
| |
| /*************************************** |
| * Support for operator ~= for `BitArray`. |
| * $(RED Warning: This will overwrite a bit in the final word |
| * of the current underlying data regardless of whether it is |
| * shared between BitArray objects. i.e. D dynamic array |
| * concatenation semantics are not followed) |
| */ |
| BitArray opOpAssign(string op)(bool b) pure nothrow return scope |
| if (op == "~") |
| { |
| length = _len + 1; |
| this[_len - 1] = b; |
| return this; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0,1,0,1]; |
| |
| auto a = BitArray(ba); |
| BitArray b; |
| |
| b = (a ~= true); |
| assert(a[0] == 1); |
| assert(a[1] == 0); |
| assert(a[2] == 1); |
| assert(a[3] == 0); |
| assert(a[4] == 1); |
| assert(a[5] == 1); |
| |
| assert(b == a); |
| } |
| |
| /*************************************** |
| * ditto |
| */ |
| BitArray opOpAssign(string op)(BitArray b) pure nothrow return scope |
| if (op == "~") |
| { |
| auto istart = _len; |
| length = _len + b.length; |
| for (auto i = istart; i < _len; i++) |
| this[i] = b[i - istart]; |
| return this; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0]; |
| bool[] bb = [0,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| BitArray c; |
| |
| c = (a ~= b); |
| assert(a.length == 5); |
| assert(a[0] == 1); |
| assert(a[1] == 0); |
| assert(a[2] == 0); |
| assert(a[3] == 1); |
| assert(a[4] == 0); |
| |
| assert(c == a); |
| } |
| |
| /*************************************** |
| * Support for binary operator ~ for `BitArray`. |
| */ |
| BitArray opBinary(string op)(bool b) const pure nothrow |
| if (op == "~") |
| { |
| BitArray r; |
| |
| r = this.dup; |
| r.length = _len + 1; |
| r[_len] = b; |
| return r; |
| } |
| |
| /** ditto */ |
| BitArray opBinaryRight(string op)(bool b) const pure nothrow |
| if (op == "~") |
| { |
| BitArray r; |
| |
| r.length = _len + 1; |
| r[0] = b; |
| foreach (i; 0 .. _len) |
| r[1 + i] = this[i]; |
| return r; |
| } |
| |
| /** ditto */ |
| BitArray opBinary(string op)(BitArray b) const pure nothrow |
| if (op == "~") |
| { |
| BitArray r; |
| |
| r = this.dup; |
| r ~= b; |
| return r; |
| } |
| |
| /// |
| @system unittest |
| { |
| bool[] ba = [1,0]; |
| bool[] bb = [0,1,0]; |
| |
| auto a = BitArray(ba); |
| auto b = BitArray(bb); |
| BitArray c; |
| |
| c = (a ~ b); |
| assert(c.length == 5); |
| assert(c[0] == 1); |
| assert(c[1] == 0); |
| assert(c[2] == 0); |
| assert(c[3] == 1); |
| assert(c[4] == 0); |
| |
| c = (a ~ true); |
| assert(c.length == 3); |
| assert(c[0] == 1); |
| assert(c[1] == 0); |
| assert(c[2] == 1); |
| |
| c = (false ~ a); |
| assert(c.length == 3); |
| assert(c[0] == 0); |
| assert(c[1] == 1); |
| assert(c[2] == 0); |
| } |
| |
| // Rolls double word (upper, lower) to the right by n bits and returns the |
| // lower word of the result. |
| private static size_t rollRight()(size_t upper, size_t lower, size_t nbits) |
| pure @safe nothrow @nogc |
| in |
| { |
| assert(nbits < bitsPerSizeT, "nbits must be less than bitsPerSizeT"); |
| } |
| do |
| { |
| if (nbits == 0) |
| return lower; |
| return (upper << (bitsPerSizeT - nbits)) | (lower >> nbits); |
| } |
| |
| @safe unittest |
| { |
| static if (size_t.sizeof == 8) |
| { |
| size_t x = 0x12345678_90ABCDEF; |
| size_t y = 0xFEDBCA09_87654321; |
| |
| assert(rollRight(x, y, 32) == 0x90ABCDEF_FEDBCA09); |
| assert(rollRight(y, x, 4) == 0x11234567_890ABCDE); |
| } |
| else static if (size_t.sizeof == 4) |
| { |
| size_t x = 0x12345678; |
| size_t y = 0x90ABCDEF; |
| |
| assert(rollRight(x, y, 16) == 0x567890AB); |
| assert(rollRight(y, x, 4) == 0xF1234567); |
| } |
| else |
| static assert(0, "Unsupported size_t width"); |
| } |
| |
| // Rolls double word (upper, lower) to the left by n bits and returns the |
| // upper word of the result. |
| private static size_t rollLeft()(size_t upper, size_t lower, size_t nbits) |
| pure @safe nothrow @nogc |
| in |
| { |
| assert(nbits < bitsPerSizeT, "nbits must be less than bitsPerSizeT"); |
| } |
| do |
| { |
| if (nbits == 0) |
| return upper; |
| return (upper << nbits) | (lower >> (bitsPerSizeT - nbits)); |
| } |
| |
| @safe unittest |
| { |
| static if (size_t.sizeof == 8) |
| { |
| size_t x = 0x12345678_90ABCDEF; |
| size_t y = 0xFEDBCA09_87654321; |
| |
| assert(rollLeft(x, y, 32) == 0x90ABCDEF_FEDBCA09); |
| assert(rollLeft(y, x, 4) == 0xEDBCA098_76543211); |
| } |
| else static if (size_t.sizeof == 4) |
| { |
| size_t x = 0x12345678; |
| size_t y = 0x90ABCDEF; |
| |
| assert(rollLeft(x, y, 16) == 0x567890AB); |
| assert(rollLeft(y, x, 4) == 0x0ABCDEF1); |
| } |
| } |
| |
| /** |
| * Operator `<<=` support. |
| * |
| * Shifts all the bits in the array to the left by the given number of |
| * bits. The leftmost bits are dropped, and 0's are appended to the end |
| * to fill up the vacant bits. |
| * |
| * $(RED Warning: unused bits in the final word up to the next word |
| * boundary may be overwritten by this operation. It does not attempt to |
| * preserve bits past the end of the array.) |
| */ |
| void opOpAssign(string op)(size_t nbits) @nogc pure nothrow |
| if (op == "<<") |
| { |
| size_t wordsToShift = nbits / bitsPerSizeT; |
| size_t bitsToShift = nbits % bitsPerSizeT; |
| |
| if (wordsToShift < dim) |
| { |
| foreach_reverse (i; 1 .. dim - wordsToShift) |
| { |
| _ptr[i + wordsToShift] = rollLeft(_ptr[i], _ptr[i-1], |
| bitsToShift); |
| } |
| _ptr[wordsToShift] = rollLeft(_ptr[0], 0, bitsToShift); |
| } |
| |
| import std.algorithm.comparison : min; |
| foreach (i; 0 .. min(wordsToShift, dim)) |
| { |
| _ptr[i] = 0; |
| } |
| } |
| |
| /** |
| * Operator `>>=` support. |
| * |
| * Shifts all the bits in the array to the right by the given number of |
| * bits. The rightmost bits are dropped, and 0's are inserted at the back |
| * to fill up the vacant bits. |
| * |
| * $(RED Warning: unused bits in the final word up to the next word |
| * boundary may be overwritten by this operation. It does not attempt to |
| * preserve bits past the end of the array.) |
| */ |
| void opOpAssign(string op)(size_t nbits) @nogc pure nothrow |
| if (op == ">>") |
| { |
| size_t wordsToShift = nbits / bitsPerSizeT; |
| size_t bitsToShift = nbits % bitsPerSizeT; |
| |
| if (wordsToShift + 1 < dim) |
| { |
| foreach (i; 0 .. dim - wordsToShift - 1) |
| { |
| _ptr[i] = rollRight(_ptr[i + wordsToShift + 1], |
| _ptr[i + wordsToShift], bitsToShift); |
| } |
| } |
| |
| // The last word needs some care, as it must shift in 0's from past the |
| // end of the array. |
| if (wordsToShift < dim) |
| { |
| if (bitsToShift == 0) |
| _ptr[dim - wordsToShift - 1] = _ptr[dim - 1]; |
| else |
| { |
| // Special case: if endBits == 0, then also endMask == 0. |
| size_t lastWord = (endBits ? (_ptr[fullWords] & endMask) : _ptr[fullWords - 1]); |
| _ptr[dim - wordsToShift - 1] = rollRight(0, lastWord, bitsToShift); |
| } |
| } |
| |
| import std.algorithm.comparison : min; |
| foreach (i; 0 .. min(wordsToShift, dim)) |
| { |
| _ptr[dim - i - 1] = 0; |
| } |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=17467 |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.range : iota; |
| |
| bool[] buf = new bool[64*3]; |
| buf[0 .. 64] = true; |
| BitArray b = BitArray(buf); |
| assert(equal(b.bitsSet, iota(0, 64))); |
| b <<= 64; |
| assert(equal(b.bitsSet, iota(64, 128))); |
| |
| buf = new bool[64*3]; |
| buf[64*2 .. 64*3] = true; |
| b = BitArray(buf); |
| assert(equal(b.bitsSet, iota(64*2, 64*3))); |
| b >>= 64; |
| assert(equal(b.bitsSet, iota(64, 128))); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=18134 |
| // shifting right when length is a multiple of 8 * size_t.sizeof. |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.array : array; |
| import std.range : repeat, iota; |
| |
| immutable r = size_t.sizeof * 8; |
| |
| BitArray a = true.repeat(r / 2).array; |
| a >>= 0; |
| assert(a.bitsSet.equal(iota(0, r / 2))); |
| a >>= 1; |
| assert(a.bitsSet.equal(iota(0, r / 2 - 1))); |
| |
| BitArray b = true.repeat(r).array; |
| b >>= 0; |
| assert(b.bitsSet.equal(iota(0, r))); |
| b >>= 1; |
| assert(b.bitsSet.equal(iota(0, r - 1))); |
| |
| BitArray c = true.repeat(2 * r).array; |
| c >>= 0; |
| assert(c.bitsSet.equal(iota(0, 2 * r))); |
| c >>= 10; |
| assert(c.bitsSet.equal(iota(0, 2 * r - 10))); |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.format : format; |
| |
| auto b = BitArray([1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1]); |
| |
| b <<= 1; |
| assert(format("%b", b) == "01100_10101101"); |
| |
| b >>= 1; |
| assert(format("%b", b) == "11001_01011010"); |
| |
| b <<= 4; |
| assert(format("%b", b) == "00001_10010101"); |
| |
| b >>= 5; |
| assert(format("%b", b) == "10010_10100000"); |
| |
| b <<= 13; |
| assert(format("%b", b) == "00000_00000000"); |
| |
| b = BitArray([1, 0, 1, 1, 0, 1, 1, 1]); |
| b >>= 8; |
| assert(format("%b", b) == "00000000"); |
| |
| } |
| |
| // Test multi-word case |
| @system unittest |
| { |
| import std.format : format; |
| |
| // This has to be long enough to occupy more than one size_t. On 64-bit |
| // machines, this would be at least 64 bits. |
| auto b = BitArray([ |
| 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, |
| 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, |
| 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, |
| 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, |
| 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, |
| ]); |
| b <<= 8; |
| assert(format("%b", b) == |
| "00000000_10000000_"~ |
| "11000000_11100000_"~ |
| "11110000_11111000_"~ |
| "11111100_11111110_"~ |
| "11111111_10101010"); |
| |
| // Test right shift of more than one size_t's worth of bits |
| b <<= 68; |
| assert(format("%b", b) == |
| "00000000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00001000"); |
| |
| b = BitArray([ |
| 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, |
| 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, |
| 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, |
| 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, |
| 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, |
| ]); |
| b >>= 8; |
| assert(format("%b", b) == |
| "11000000_11100000_"~ |
| "11110000_11111000_"~ |
| "11111100_11111110_"~ |
| "11111111_10101010_"~ |
| "01010101_00000000"); |
| |
| // Test left shift of more than 1 size_t's worth of bits |
| b >>= 68; |
| assert(format("%b", b) == |
| "01010000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00000000_"~ |
| "00000000_00000000"); |
| } |
| |
| /*************************************** |
| * Return a string representation of this BitArray. |
| * |
| * Two format specifiers are supported: |
| * $(LI $(B %s) which prints the bits as an array, and) |
| * $(LI $(B %b) which prints the bits as 8-bit byte packets) |
| * separated with an underscore. |
| * |
| * Params: |
| * sink = A `char` accepting |
| * $(REF_ALTTEXT output range, isOutputRange, std, range, primitives). |
| * fmt = A $(REF FormatSpec, std,format) which controls how the data |
| * is displayed. |
| */ |
| void toString(W)(ref W sink, scope const ref FormatSpec!char fmt) const |
| if (isOutputRange!(W, char)) |
| { |
| const spec = fmt.spec; |
| switch (spec) |
| { |
| case 'b': |
| return formatBitString(sink); |
| case 's': |
| return formatBitArray(sink); |
| default: |
| throw new Exception("Unknown format specifier: %" ~ spec); |
| } |
| } |
| |
| /// |
| @system pure unittest |
| { |
| import std.format : format; |
| |
| auto b = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| |
| auto s1 = format("%s", b); |
| assert(s1 == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); |
| |
| auto s2 = format("%b", b); |
| assert(s2 == "00001111_00001111"); |
| } |
| |
| /*************************************** |
| * Return a lazy range of the indices of set bits. |
| */ |
| @property auto bitsSet() const nothrow |
| { |
| import std.algorithm.iteration : filter, map, joiner; |
| import std.range : iota, chain; |
| |
| return chain( |
| iota(fullWords) |
| .filter!(i => _ptr[i])() |
| .map!(i => BitsSet!size_t(_ptr[i], i * bitsPerSizeT))() |
| .joiner(), |
| iota(fullWords * bitsPerSizeT, _len) |
| .filter!(i => this[i])() |
| ); |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| auto b1 = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(b1.bitsSet.equal([4, 5, 6, 7, 12, 13, 14, 15])); |
| |
| BitArray b2; |
| b2.length = 1000; |
| b2[333] = true; |
| b2[666] = true; |
| b2[999] = true; |
| assert(b2.bitsSet.equal([333, 666, 999])); |
| } |
| |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.range : iota; |
| |
| BitArray b; |
| enum wordBits = size_t.sizeof * 8; |
| b = BitArray([size_t.max], 0); |
| assert(b.bitsSet.empty); |
| b = BitArray([size_t.max], 1); |
| assert(b.bitsSet.equal([0])); |
| b = BitArray([size_t.max], wordBits); |
| assert(b.bitsSet.equal(iota(wordBits))); |
| b = BitArray([size_t.max, size_t.max], wordBits); |
| assert(b.bitsSet.equal(iota(wordBits))); |
| b = BitArray([size_t.max, size_t.max], wordBits + 1); |
| assert(b.bitsSet.equal(iota(wordBits + 1))); |
| b = BitArray([size_t.max, size_t.max], wordBits * 2); |
| assert(b.bitsSet.equal(iota(wordBits * 2))); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=20241 |
| @system unittest |
| { |
| BitArray ba; |
| ba.length = 2; |
| ba[1] = 1; |
| ba.length = 1; |
| assert(ba.bitsSet.empty); |
| } |
| |
| private void formatBitString(Writer)(auto ref Writer sink) const |
| { |
| if (!length) |
| return; |
| |
| auto leftover = _len % 8; |
| foreach (idx; 0 .. leftover) |
| { |
| put(sink, cast(char)(this[idx] + '0')); |
| } |
| |
| if (leftover && _len > 8) |
| put(sink, "_"); |
| |
| size_t count; |
| foreach (idx; leftover .. _len) |
| { |
| put(sink, cast(char)(this[idx] + '0')); |
| if (++count == 8 && idx != _len - 1) |
| { |
| put(sink, "_"); |
| count = 0; |
| } |
| } |
| } |
| |
| private void formatBitArray(Writer)(auto ref Writer sink) const |
| { |
| put(sink, "["); |
| foreach (idx; 0 .. _len) |
| { |
| put(sink, cast(char)(this[idx] + '0')); |
| if (idx + 1 < _len) |
| put(sink, ", "); |
| } |
| put(sink, "]"); |
| } |
| |
| // https://issues.dlang.org/show_bug.cgi?id=20639 |
| // Separate @nogc test because public tests use array literals |
| // (and workarounds needlessly uglify those examples) |
| @system @nogc unittest |
| { |
| size_t[2] buffer; |
| BitArray b = BitArray(buffer[], buffer.sizeof * 8); |
| |
| b[] = true; |
| b[0 .. 1] = true; |
| b.flip(); |
| b.flip(1); |
| cast(void) b.count(); |
| } |
| } |
| |
| /// Slicing & bitsSet |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| import std.range : iota; |
| |
| bool[] buf = new bool[64 * 3]; |
| buf[0 .. 64] = true; |
| BitArray b = BitArray(buf); |
| assert(b.bitsSet.equal(iota(0, 64))); |
| b <<= 64; |
| assert(b.bitsSet.equal(iota(64, 128))); |
| } |
| |
| /// Concatenation and appending |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| auto b = BitArray([1, 0]); |
| b ~= true; |
| assert(b[2] == 1); |
| b ~= BitArray([0, 1]); |
| auto c = BitArray([1, 0, 1, 0, 1]); |
| assert(b == c); |
| assert(b.bitsSet.equal([0, 2, 4])); |
| } |
| |
| /// Bit flipping |
| @system unittest |
| { |
| import std.algorithm.comparison : equal; |
| |
| auto b = BitArray([1, 1, 0, 1]); |
| b &= BitArray([0, 1, 1, 0]); |
| assert(b.bitsSet.equal([1])); |
| b.flip; |
| assert(b.bitsSet.equal([0, 2, 3])); |
| } |
| |
| /// String format of bitarrays |
| @system unittest |
| { |
| import std.format : format; |
| auto b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(format("%b", b) == "1_00001111_00001111"); |
| } |
| |
| /// |
| @system unittest |
| { |
| import std.format : format; |
| |
| BitArray b; |
| |
| b = BitArray([]); |
| assert(format("%s", b) == "[]"); |
| assert(format("%b", b) is null); |
| |
| b = BitArray([1]); |
| assert(format("%s", b) == "[1]"); |
| assert(format("%b", b) == "1"); |
| |
| b = BitArray([0, 0, 0, 0]); |
| assert(format("%b", b) == "0000"); |
| |
| b = BitArray([0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(format("%s", b) == "[0, 0, 0, 0, 1, 1, 1, 1]"); |
| assert(format("%b", b) == "00001111"); |
| |
| b = BitArray([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(format("%s", b) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); |
| assert(format("%b", b) == "00001111_00001111"); |
| |
| b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(format("%b", b) == "1_00001111"); |
| |
| b = BitArray([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); |
| assert(format("%b", b) == "1_00001111_00001111"); |
| } |
| |
| @system unittest |
| { |
| BitArray a; |
| a.length = 5; |
| foreach (ref bool b; a) |
| { |
| assert(b == 0); |
| b = 1; |
| } |
| foreach (bool b; a) |
| assert(b == 1); |
| } |
| |
| /++ |
|
