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 }