C++ bounded::integer library
Dominikus Dittes Scherkl via Digitalmars-d
digitalmars-d at puremagic.com
Tue May 20 12:58:23 PDT 2014
On Tuesday, 20 May 2014 at 13:03:59 UTC, Nordlöw wrote:
> You have a typo: @save instead of @safe
Oops. This happens all the time :-/
>
> You should also guard the use of asm to x86 architectures only
> with version.
Uh?
I thought the D assembler should be generic? So if the target
platform provides some similar mnemonic, I could use the same?
But ok. It's just the do-it-yourself overflow protection is so
awfully slow (especially for multiplication).
I have also a protection for exponentiation, and that works
without asm.
On the other side it requires some helper functions:
/// returns the absolute value of x in the fitting unsigned type
/// (doesn't fail for T.min)
Unsigned!T abs(T)(T x) pure @safe @nogc if(isIntegral!T)
{
return (x < 0) ? -x : x;
}
/// returns the number of the highest set bit +1 in the given
value
/// or 0 if no bit is set
ubyte bitlen(ubyte c) pure @safe @nogc
{
return (c>15) ? (c>63) ? (c>127) ? 8 : 7
: (c>31) ? 6 : 5
: (c>3) ? (c>7) ? 4 : 3
: (c>1) ? 2 : c;
// of course lookup table would be better but I'm to lazy to
create one
}
/// calculate the maximal power of x that would fit in an ucent
/// for smaller types simply shift down the result
/// (e.g. divide by 4 to calc the maxpower that would fit in an
uint)
ubyte maxpow(ulong x) pure @safe @nogc
{
assert(x>1); // no useful maxpower exists for 0 and 1
static immutable ubyte[10] mp = [ 127, 80, 63, 55, 49, 45, 43,
40, 38, 37 ];
return (x<139) ? ((x<31) ? ((x<20) ? ((x<16) ? ((x<12) ?
mp[x-2] : 47-x)
: ((x<18) ? 31 :
30))
: ((x<24) ? ((x<22) ? 29 :
28)
: ((x<27) ? 27 :
26)))
: ((x<57) ? ((x<41) ? ((x<35) ? 25 :
24)
: ((x<48) ? 23 :
22))
: ((x<85) ? ((x<69) ? 21 :
20)
: ((x<107) ? 19 :
18))))
: ((x<7132) ? ((x<566) ? ((x<256) ? ((x<185) ? 17 :
16)
: ((x<371) ? 15 :
14))
: ((x<1626) ? ((x<921) ? 13 :
12)
: ((x<3184) ? 11 :
10)))
: ((x<2642246) ? ((x<65536) ? ((x<19113) ? 9 :
8)
: ((x<319558) ? 7 :
6))
: ((x<4294967296) ? ((x<50859009) ? 5 :
4)
: ((x<6981463658332) ? 3 :
2))));
}
/// full exponentiation without overflow
/// return T.max(for unsigned) or T.min (for signed) if overflow
would occur.
T savePow(T)(T base, ubyte exp) pure @safe @nogc if(isIntegral!T)
{
static if(isUnsigned!T)
{
if(!exp) return 1; // x^^0 is always 1
if(exp == 1 || base < 2) return base; // x^^1 = x, so do
nothing
static if(T.sizeof > ulong.sizeof)
{
if(base > ulong.max) return T.max;
}
if(exp > (maxpow(base)>>(5-bitlen(T.sizeof)))) return T.max;
return base ^^ exp;
}
else
{
auto r = savePow(abs!T(base), exp);
if(r > T.max) return T.min;
return ((base < 0) && (exp&1)) ? -cast(T)r : cast(T)r;
}
}
More information about the Digitalmars-d
mailing list