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])) { return false; }
236 }
237 return true;
238 }();
239 }
240 else static if (is(T == struct) ||
241 is(T == union))
242 {
243 enum isAllZeroBits = ()
244 {
245 static foreach (e; value.tupleof)
246 {
247 if (!isAllZeroBits!(typeof(e), e)) { return false; }
248 }
249 return true;
250 }();
251 }
252 else
253 {
254 enum isAllZeroBits = false;
255 }
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) return b;
309 }
310
311 return b;
312 }();
313 }
314 else static if (is(typeof(value) == struct))
315 {
316 enum isAllOneBits = ()
317 {
318 bool b = true;
319 size_t fieldSizeSum = 0;
320 static foreach (e; value.tupleof)
321 {
322 b &= isAllOneBits!(typeof(e), e);
323 if (b == false) return b;
324 fieldSizeSum += typeof(e).sizeof;
325 }
326 // If fieldSizeSum == T.sizeof then there can be no gaps
327 // between fields.
328 return b && fieldSizeSum == T.sizeof;
329 }();
330 }
331 else
332 {
333 enum isAllOneBits = false;
334 }
335 }
336
337 @nogc nothrow pure @safe unittest
338 {
339 static assert(isAllOneBits!(char, 0xff));
340 static assert(isAllOneBits!(wchar, 0xffff));
341 static assert(isAllOneBits!(byte, cast(byte) 0xff));
342 static assert(isAllOneBits!(int, 0xffff_ffff));
343 static assert(isAllOneBits!(char[4], [0xff, 0xff, 0xff, 0xff]));
344
345 static assert(!isAllOneBits!(bool, true));
346 static assert(!isAllOneBits!(wchar, 0xff));
347 static assert(!isAllOneBits!(Object, Object.init));
348 }
349
350 /+ Can the representation be determined at compile time to consist of nothing
351 but 1 bits? This is reported as $(B false) for structs with padding between
352 their fields because `opEquals` and hashing may rely on those bits being zero.
353
354 See_Also:
355 https://forum.dlang.org/post/hn11oh$1usk$1@digitalmars.com
356 https://github.com/dlang/phobos/pull/6024
357 +/
358 template isInitAllOneBits(T)
359 {
360 static if (__traits(isStaticArray, T) && __traits(compiles, T.init[0]))
361 enum isInitAllOneBits = __traits(compiles, {
362 static assert(isAllOneBits!(typeof(T.init[0]), T.init[0]));
363 });
364 else
365 enum isInitAllOneBits = __traits(compiles, {
366 static assert(isAllOneBits!(T, T.init));
367 });
368 }
369
370 @nogc nothrow pure @safe unittest
371 {
372 static assert(isInitAllOneBits!char);
373 static assert(isInitAllOneBits!wchar);
374 static assert(!isInitAllOneBits!dchar);
375
376 static assert(isInitAllOneBits!(char[4]));
377 static assert(!isInitAllOneBits!(int[4]));
378 static assert(!isInitAllOneBits!Object);
379
380 static struct S1
381 {
382 char a;
383 char b;
384 }
385 static assert(isInitAllOneBits!S1);
386
387 static struct S2
388 {
389 char a = 1;
390 }
391 static assert(!isInitAllOneBits!S2);
392
393 static struct S3
394 {
395 S1 a;
396 char b;
397 }
398 static assert(isInitAllOneBits!S3);
399 static assert(isInitAllOneBits!(S3[2]));
400
401 static struct S4
402 {
403 S1 a;
404 S2 b;
405 }
406 static assert(!isInitAllOneBits!S4);
407
408 static struct Sshort
409 {
410 short r = cast(short)0xffff;
411 }
412 static assert(isInitAllOneBits!Sshort);
413
414 static struct Sint
415 {
416 int r = 0xffff_ffff;
417 }
418 static assert(isInitAllOneBits!Sint);
419
420 static struct Slong
421 {
422 long r = 0xffff_ffff_ffff_ffff;
423 }
424 static assert(isInitAllOneBits!Slong);
425
426 // Verify that when there is padding between fields isInitAllOneBits is false.
427 static struct S10
428 {
429 align(4) char a;
430 align(4) char b;
431 }
432 static assert(!isInitAllOneBits!S10);
433
434 static class C1
435 {
436 char c;
437 }
438 static assert(!isInitAllOneBits!C1);
439 }