1 module nxt.bit_traits; 2 3 static if (__VERSION__ >= 2083) 4 { 5 version(LDC) static assert(!__traits(compiles, { enum _ = __traits(isZeroInit, T); }), 6 "Remove checks for __traits(compiles, { enum _ = __traits(isZeroInit, T); }) now that it compiles with LDC"); 7 } 8 9 /** Get number of bits needed to represent the range (0 .. `length`-1). 10 */ 11 template bitsNeeded(size_t length) 12 { 13 // TODO: optimize by removing need for a linear search 14 static if (length <= 2) { enum bitsNeeded = 1; } 15 else static if (length <= 4) { enum bitsNeeded = 2; } 16 else static if (length <= 8) { enum bitsNeeded = 3; } 17 else static if (length <= 16) { enum bitsNeeded = 4; } 18 else static if (length <= 32) { enum bitsNeeded = 5; } 19 else static if (length <= 64) { enum bitsNeeded = 6; } 20 else static if (length <= 128) { enum bitsNeeded = 7; } 21 else static if (length <= 256) { enum bitsNeeded = 8; } 22 else static if (length <= 512) { enum bitsNeeded = 9; } 23 else { static assert(0, `Too large length`); } 24 } 25 26 /** Number of bits required to store a packed instance of `T`. 27 See_Also: http://forum.dlang.org/thread/okonqhnxzqlqtxijxsfg@forum.dlang.org 28 29 TODO: Extend to continuous version; use std.numeric.sumOfLog2s. Ask on 30 StackExchange Computer Science for the correct terminology. 31 32 See: http://dlang.org/phobos/std_numeric.html#.sumOfLog2s 33 34 TODO: merge with `UsageOf` 35 */ 36 template packedBitSizeOf(T) 37 { 38 static if (is(T == enum)) 39 { 40 static assert(T.min != T.max, "enum T must have at least two enumerators"); 41 import core.bitop : bsr; 42 enum range = T.max - T.min; // TODO: use uniqueEnumMembers.length instead? 43 enum packedBitSizeOf = range.bsr + 1; 44 } 45 // TODO 46 // else static if (isAggregate!T) 47 // { 48 // foreach (E; T.tupleof) 49 // { 50 // ....; 51 // } 52 // } 53 else 54 { 55 enum packedBitSizeOf = 8*T.sizeof; 56 } 57 } 58 59 @safe pure nothrow @nogc unittest 60 { 61 static assert(packedBitSizeOf!ubyte == 8); 62 static assert(!__traits(compiles, 63 { 64 enum E1 { x } static assert(packedBitSizeOf!E1 == 1); 65 })); 66 enum E2 { x, y } 67 static assert(packedBitSizeOf!E2 == 1); 68 enum E3 { x, y, z } 69 static assert(packedBitSizeOf!E3 == 2); 70 enum E4 { x, y, z, w } 71 static assert(packedBitSizeOf!E4 == 2); 72 enum E5 { a, b, c, d, e } 73 static assert(packedBitSizeOf!E5 == 3); 74 enum E6 { a, b, c, d, e, f } 75 static assert(packedBitSizeOf!E6 == 3); 76 enum E7 { a, b, c, d, e, f, g } 77 static assert(packedBitSizeOf!E7 == 3); 78 enum E8 { a, b, c, d, e, f, g, h } 79 static assert(packedBitSizeOf!E8 == 3); 80 enum E9 { a, b, c, d, e, f, g, h, i } 81 static assert(packedBitSizeOf!E9 == 4); 82 } 83 84 85 /+ Is the representation of `T.init` known at compile time to consist of nothing 86 + but zero bits? Padding between a struct's fields is not considered. 87 +/ 88 template isInitAllZeroBits(T) 89 { 90 static if (__traits(compiles, { enum _ = __traits(isZeroInit, T); })) 91 { 92 enum isInitAllZeroBits = __traits(isZeroInit, T); 93 // pragma(msg, "TODO: use `enum isInitAllZeroBits = __traits(isZeroInit, T);` here and in `isAllZeroBits` and remove the test of isInitAllZeroBits"); 94 } 95 else static if (T.sizeof == 0) 96 { 97 enum isInitAllZeroBits = true; 98 } 99 else 100 { 101 import std.traits : isStaticArray; 102 static if (isStaticArray!T && __traits(compiles, T.init[0])) 103 { 104 enum isInitAllZeroBits = __traits(compiles, { 105 static assert(isAllZeroBits!(typeof(T.init[0]), T.init[0])); 106 }); 107 } 108 else 109 { 110 enum isInitAllZeroBits = __traits(compiles, { 111 static assert(isAllZeroBits!(T, T.init)); 112 }); 113 } 114 } 115 } 116 117 @nogc nothrow pure @safe unittest 118 { 119 static assert(isInitAllZeroBits!int); 120 static assert(isInitAllZeroBits!(Object)); 121 static assert(isInitAllZeroBits!(void*)); 122 static assert(isInitAllZeroBits!uint); 123 static assert(isInitAllZeroBits!(uint[2])); 124 static assert(isInitAllZeroBits!(string)); 125 static assert(isInitAllZeroBits!(wstring)); 126 static assert(isInitAllZeroBits!(dstring)); 127 128 static assert(!isInitAllZeroBits!float); 129 // static assert(isInitAllZeroBits!(float[0])); 130 static assert(!isInitAllZeroBits!(float[2])); 131 132 static struct S1 133 { 134 int a; 135 } 136 static assert(isInitAllZeroBits!S1); 137 138 static struct S2 139 { 140 int a = 1; 141 } 142 static assert(!isInitAllZeroBits!S2); 143 144 static struct S3 145 { 146 S1 a; 147 int b; 148 } 149 static assert(isInitAllZeroBits!S3); 150 static assert(isInitAllZeroBits!(S3[2])); 151 152 static struct S4 153 { 154 S1 a; 155 S2 b; 156 } 157 static assert(!isInitAllZeroBits!S4); 158 159 static struct S5 160 { 161 real r = 0; 162 } 163 static assert(isInitAllZeroBits!S5); 164 165 static struct S6 166 { 167 168 } 169 static assert(isInitAllZeroBits!S6); 170 171 static struct S7 172 { 173 float[0] a; 174 } 175 // TODO: static assert(isInitAllZeroBits!S7); 176 177 static class C1 178 { 179 int a = 1; 180 } 181 static assert(isInitAllZeroBits!C1); 182 183 // Ensure Tuple can be read. 184 import std.typecons : Tuple; 185 static assert(isInitAllZeroBits!(Tuple!(int, int))); 186 static assert(!isInitAllZeroBits!(Tuple!(float, float))); 187 188 // Ensure private fields of structs from other modules 189 // are taken into account. 190 import std.random : Mt19937; 191 static assert(!isInitAllZeroBits!Mt19937); 192 // Check that it works with const. 193 static assert(isInitAllZeroBits!(const(Mt19937)) == isInitAllZeroBits!Mt19937); 194 static assert(isInitAllZeroBits!(const(S5)) == isInitAllZeroBits!S5); 195 } 196 197 /+ Can the representation be determined at compile time to consist of nothing 198 + but zero bits? Padding between a struct's fields is not considered. 199 +/ 200 template isAllZeroBits(T, T value) 201 { 202 static if ((is(T == class) || is(T == typeof(null))) && // need this special case 203 value is null) // because pointer must be compared with `is` instead of `==` for `SSOString` case below 204 { 205 enum isAllZeroBits = true; 206 } 207 else static if (value == T.init && // NOTE `value is T.init` crashes compiler for `SSOString` 208 __traits(compiles, { enum _ = __traits(isZeroInit, T); })) 209 { 210 enum isAllZeroBits = __traits(isZeroInit, T); 211 } 212 else 213 { 214 // pragma(msg, "T: ", T.stringof, " value:", value); 215 import std.traits : isDynamicArray, isStaticArray; 216 static if (isDynamicArray!(T)) 217 { 218 enum isAllZeroBits = value is null && value.length is 0; 219 } 220 else static if (is(typeof(value is null))) 221 { 222 enum isAllZeroBits = value is null; 223 } 224 else static if (is(typeof(value is 0))) 225 { 226 enum isAllZeroBits = value is 0; 227 } 228 else static if (isStaticArray!(T)) 229 { 230 enum isAllZeroBits = () 231 { 232 // Use index so this works when T.length is 0. 233 static foreach (i; 0 .. T.length) 234 { 235 if (!isAllZeroBits!(typeof(value[i]), value[i])) 236 return false; 237 } 238 return true; 239 }(); 240 } 241 else static if (is(T == struct) || 242 is(T == union)) 243 { 244 enum isAllZeroBits = () 245 { 246 static foreach (e; value.tupleof) 247 { 248 if (!isAllZeroBits!(typeof(e), e)) 249 return false; 250 } 251 return true; 252 }(); 253 } 254 else 255 enum isAllZeroBits = false; 256 } 257 } 258 259 @nogc nothrow pure @safe unittest 260 { 261 static assert(isAllZeroBits!(int, 0)); 262 static assert(!isAllZeroBits!(int, 1)); 263 264 import std.meta : AliasSeq; 265 foreach (Float; AliasSeq!(float, double, real)) 266 { 267 assert(isAllZeroBits!(Float, 0.0)); 268 assert(!isAllZeroBits!(Float, -0.0)); 269 assert(!isAllZeroBits!(Float, Float.nan)); 270 } 271 272 static assert(isAllZeroBits!(void*, null)); 273 static assert(isAllZeroBits!(int*, null)); 274 static assert(isAllZeroBits!(Object, null)); 275 } 276 277 /+ Can the representation be determined at compile time to consist of nothing 278 but 1 bits? This is reported as $(B false) for structs with padding between 279 their fields because `opEquals` and hashing may rely on those bits being zero. 280 281 Note: 282 A bool occupies 8 bits so `isAllOneBits!(bool, true) == false` 283 284 See_Also: 285 https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com 286 https://github.com/dlang/phobos/pull/6024 287 +/ 288 template isAllOneBits(T, T value) 289 { 290 import std.traits : isIntegral, isSomeChar, Unsigned; 291 static if (isIntegral!T || isSomeChar!T) 292 { 293 import core.bitop : popcnt; 294 static if (T.min < T(0)) 295 enum isAllOneBits = popcnt(cast(Unsigned!T) value) == T.sizeof * 8; 296 else 297 enum isAllOneBits = popcnt(value) == T.sizeof * 8; 298 } 299 else static if (__traits(isStaticArray, typeof(value))) 300 { 301 enum isAllOneBits = () 302 { 303 bool b = true; 304 // Use index so this works when T.length is 0. 305 static foreach (i; 0 .. T.length) 306 { 307 b &= isAllOneBits!(typeof(value[i]), value[i]); 308 if (b == false) 309 return b; 310 } 311 312 return b; 313 }(); 314 } 315 else static if (is(typeof(value) == struct)) 316 { 317 enum isAllOneBits = () 318 { 319 bool b = true; 320 size_t fieldSizeSum = 0; 321 alias v = value.tupleof; 322 static foreach (const i, e; v) 323 { 324 b &= isAllOneBits!(typeof(e), v[i]); 325 if (b == false) 326 return b; 327 fieldSizeSum += typeof(e).sizeof; 328 } 329 // If fieldSizeSum == T.sizeof then there can be no gaps 330 // between fields. 331 return b && fieldSizeSum == T.sizeof; 332 }(); 333 } 334 else 335 { 336 enum isAllOneBits = false; 337 } 338 } 339 340 @nogc nothrow pure @safe unittest 341 { 342 static assert(isAllOneBits!(char, 0xff)); 343 static assert(isAllOneBits!(wchar, 0xffff)); 344 static assert(isAllOneBits!(byte, cast(byte) 0xff)); 345 static assert(isAllOneBits!(int, 0xffff_ffff)); 346 static assert(isAllOneBits!(char[4], [0xff, 0xff, 0xff, 0xff])); 347 348 static assert(!isAllOneBits!(bool, true)); 349 static assert(!isAllOneBits!(wchar, 0xff)); 350 static assert(!isAllOneBits!(Object, Object.init)); 351 352 static struct S1 353 { 354 char a; 355 char b; 356 } 357 static assert(isAllOneBits!(S1, S1.init)); 358 } 359 360 /+ Can the representation be determined at compile time to consist of nothing 361 but 1 bits? This is reported as $(B false) for structs with padding between 362 their fields because `opEquals` and hashing may rely on those bits being zero. 363 364 See_Also: 365 https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com 366 https://github.com/dlang/phobos/pull/6024 367 +/ 368 template isInitAllOneBits(T) 369 { 370 static if (__traits(isStaticArray, T) && __traits(compiles, T.init[0])) // TODO: avoid traits compiles here 371 enum isInitAllOneBits = __traits(compiles, { // TODO: avoid traits compiles here 372 static assert(isAllOneBits!(typeof(T.init[0]), T.init[0])); 373 }); 374 else 375 enum isInitAllOneBits = __traits(compiles, { // TODO: avoid traits compiles here 376 static assert(isAllOneBits!(T, T.init)); 377 }); 378 } 379 380 /// 381 @nogc nothrow pure @safe unittest 382 { 383 static assert(isInitAllOneBits!char); 384 static assert(isInitAllOneBits!wchar); 385 static assert(!isInitAllOneBits!dchar); 386 387 static assert(isInitAllOneBits!(char[4])); 388 static assert(!isInitAllOneBits!(int[4])); 389 static assert(!isInitAllOneBits!Object); 390 391 static struct S1 392 { 393 char a; 394 char b; 395 } 396 static assert(isInitAllOneBits!S1); 397 398 static struct S2 399 { 400 char a = 1; 401 } 402 static assert(!isInitAllOneBits!S2); 403 404 static struct S3 405 { 406 S1 a; 407 char b; 408 } 409 static assert(isInitAllOneBits!S3); 410 static assert(isInitAllOneBits!(S3[2])); 411 412 static struct S4 413 { 414 S1 a; 415 S2 b; 416 } 417 static assert(!isInitAllOneBits!S4); 418 419 static struct Sshort 420 { 421 short r = cast(short)0xffff; 422 } 423 static assert(isInitAllOneBits!Sshort); 424 425 static struct Sint 426 { 427 int r = 0xffff_ffff; 428 } 429 static assert(isInitAllOneBits!Sint); 430 431 static struct Slong 432 { 433 long r = 0xffff_ffff_ffff_ffff; 434 } 435 static assert(isInitAllOneBits!Slong); 436 437 // Verify that when there is padding between fields isInitAllOneBits is false. 438 static struct S10 439 { 440 align(4) char a; 441 align(4) char b; 442 } 443 static assert(!isInitAllOneBits!S10); 444 445 static class C1 446 { 447 char c; 448 } 449 static assert(!isInitAllOneBits!C1); 450 }