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