nxt.clz source code

1 /** Count leading zeros.
2  */
3 module nxt.clz;
4 
5 import std.traits : Unqual;
6 
7 /*******************************************************************************
8  *
9  * Count leading zeroes.
10  *
11  * Params:
12  *   u = the unsigned value to scan
13  *
14  * Returns:
15  *   The number of leading zero bits before the first one bit. If `u` is `0`,
16  *   the result is undefined.
17  *
18  **************************************/
19 version (DigitalMars)
20 {
21 	U clz(U)(U u) @safe @nogc pure nothrow
22     if (is(Unqual!U == uint) ||
23         is(Unqual!U == size_t))
24 	{
25 		pragma(inline, true);
26 		enum U max = 8 * U.sizeof - 1;
27 		return max - bsr(u);
28 	}
29 
30 	static if (isX86)
31 	{
32 		uint clz(U)(U u) @safe @nogc pure nothrow
33         if (is(Unqual!U == ulong))
34 		{
35 			pragma(inline, true);
36 			uint hi = u >> 32;
37 			return hi ? 31 - bsr(hi) : 63 - bsr(cast(uint)u);
38 		}
39 	}
40 }
41 else version (GNU)
42 {
43 	import gcc.builtins;
44 	alias clz = __builtin_clz;
45 	static if (isX86)
46 	{
47 		@safe @nogc pure nothrow uint
48 		clz(ulong u)
49 		{
50 			uint hi = u >> 32;
51 			return hi ? __builtin_clz(hi) : 32 + __builtin_clz(cast(uint)u);
52 		}
53 	}
54 	else alias clz = __builtin_clzl;
55 }
56 else version (LDC)
57 {
58 	U clz(U)(U u) @safe @nogc pure nothrow
59     if (is(Unqual!U == uint) || is(Unqual!U == size_t))
60 	{
61 		pragma(inline, true);
62 		import ldc.intrinsics;
63 		return llvm_ctlz(u, false);
64 	}
65 
66 	static if (isX86)
67 	{
68 		uint clz(U)(U u) @safe @nogc pure nothrow
69         if (is(Unqual!U == ulong))
70 		{
71 			pragma(inline, true);
72 			import ldc.intrinsics;
73 			return cast(uint)llvm_ctlz(u, false);
74 		}
75 	}
76 }
77 
78 version (X86_64)
79 {
80 	private enum isAMD64 = true;
81 	private enum isX86   = false;
82 }
83 else version (X86)
84 {
85 	private enum isAMD64 = false;
86 	private enum isX86   = true;
87 }
88 
89 version (X86_64)
90 	private enum hasSSE2 = true;
91 else
92 	private enum hasSSE2 = false;
93 
94 static import core.bitop;
95 
96 alias bsr = core.bitop.bsr;
97 alias bsf = core.bitop.bsf;
98 
99 @safe pure nothrow @nogc unittest
100 {
101 	assert(clz(uint(0x01234567)) == 7);
102 	assert(clz(ulong(0x0123456701234567)) == 7);
103 	assert(clz(ulong(0x0000000001234567)) == 7+32);
104 	assert(bsr(uint(0x01234567)) == 24);
105 	assert(bsr(ulong(0x0123456701234567)) == 24+32);
106 	assert(bsr(ulong(0x0000000001234567)) == 24);
107 	assert(bsf(uint(0x76543210)) == 4);
108 	assert(bsf(ulong(0x7654321076543210)) == 4);
109 	assert(bsf(ulong(0x7654321000000000)) == 4+32);
110 }
111