future.bitop source code

1 /**
2 Compatibility shim to allow code written against the latest `core.bitop`
3 module to compile with older versions of D.
4 
5 Copyright: Copyright Thomas Stuart Bockman 2015
6 License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
7 Authors: Thomas Stuart Bockman
8 **/
9 module future.bitop;
10 public import core.bitop;
11 
12 static if (__VERSION__ < 2071)
13 {
14 @safe: pure: nothrow: @nogc:
15 
16     private union Split64
17     {
18         ulong u64;
19         struct
20         {
21             version(LittleEndian)
22             {
23                 uint lo;
24                 uint hi;
25             }
26             else
27             {
28                 uint hi;
29                 uint lo;
30             }
31         }
32     }
33     private auto split64(ulong x)
34     {
35         if (__ctfe)
36         {
37             Split64 ret = void;
38             ret.lo = cast(uint)x;
39             ret.hi = cast(uint)(x >>> 32);
40             return ret;
41         }
42         else
43             return Split64(x);
44     }
45 
46     int bsf(size_t v)
47     {
48         return core.bitop.bsf(v);
49     }
50     static if (size_t.sizeof == uint.sizeof)
51     {
52         int bsf(ulong v) pure
53         {
54             const sv = split64(v);
55             return (sv.lo == 0)?
56                 bsf(sv.hi) + 32 :
57                 bsf(sv.lo);
58         }
59     }
60     else
61         static assert(size_t.sizeof == ulong.sizeof);
62 
63     int bsr(size_t v)
64     {
65         return core.bitop.bsr(v);
66     }
67     static if (size_t.sizeof == uint.sizeof)
68     {
69         int bsr(ulong v)
70         {
71             const sv = split64(v);
72             return (sv.hi == 0)?
73                 bsr(sv.lo) :
74                 bsr(sv.hi) + 32;
75         }
76     } else
77         static assert(size_t.sizeof == ulong.sizeof);
78 
79     int popcnt(uint x)
80     {
81         // Select the fastest method depending on the compiler and CPU architecture
82         version(LDC)
83         {
84             return _popcnt(x);
85         }
86         else
87         {
88             version(DigitalMars)
89             {
90                 static if (is(typeof(_popcnt(uint.max))))
91                 {
92                     import core.cpuid;
93                     if (!__ctfe && hasPopcnt)
94                         return _popcnt(x);
95                 }
96             }
97 
98             return soft_popcnt!uint(x);
99         }
100     }
101     int popcnt(ulong x)
102     {
103         // Select the fastest method depending on the compiler and CPU architecture
104         version(LDC)
105             return _popcnt(x);
106         else
107         {
108             import core.cpuid;
109 
110             static if (size_t.sizeof == uint.sizeof)
111             {
112                 const sx = split64(x);
113                 version(DigitalMars)
114                 {
115                     static if (is(typeof(_popcnt(uint.max))))
116                     {
117                         if (!__ctfe && hasPopcnt)
118                             return _popcnt(sx.lo) + _popcnt(sx.hi);
119                     }
120                 }
121 
122                 return soft_popcnt!uint(sx.lo) + soft_popcnt!uint(sx.hi);
123             }
124             else static if (size_t.sizeof == ulong.sizeof)
125             {
126                 version(DigitalMars)
127                 {
128                     static if (is(typeof(_popcnt(ulong.max))))
129                     {
130                         if (!__ctfe && hasPopcnt)
131                             return _popcnt(x);
132                     }
133                 }
134 
135                 return soft_popcnt!ulong(x);
136             } else
137                 static assert(false);
138         }
139     }
140 
141     private int soft_popcnt(N)(N x) pure
142         if (is(N == uint) || is(N == ulong))
143     {
144         // Avoid branches, and the potential for cache misses which
145         // could be incurred with a table lookup.
146 
147         // We need to mask alternate bits to prevent the
148         // sum from overflowing.
149         // add neighbouring bits. Each bit is 0 or 1.
150         enum mask1 = cast(N) 0x5555_5555_5555_5555L;
151         x = x - ((x>>1) & mask1);
152         // now each two bits of x is a number 00,01 or 10.
153         // now add neighbouring pairs
154         enum mask2a = cast(N) 0xCCCC_CCCC_CCCC_CCCCL;
155         enum mask2b = cast(N) 0x3333_3333_3333_3333L;
156         x = ((x & mask2a)>>2) + (x & mask2b);
157         // now each nibble holds 0000-0100. Adding them won't
158         // overflow any more, so we don't need to mask any more
159 
160         enum mask4 = cast(N) 0x0F0F_0F0F_0F0F_0F0FL;
161         x = (x + (x >> 4)) & mask4;
162 
163         enum shiftbits = is(N == uint)? 24 : 56;
164         enum maskMul = cast(N) 0x0101_0101_0101_0101L;
165         x = (x * maskMul) >> shiftbits;
166 
167         return cast(int) x;
168     }
169 }