Skip to content

Instantly share code, notes, and snippets.

@JackStouffer
Created July 28, 2016 16:08
Show Gist options
  • Save JackStouffer/af53d497532a864f56a5b53cb35cd438 to your computer and use it in GitHub Desktop.
Save JackStouffer/af53d497532a864f56a5b53cb35cd438 to your computer and use it in GitHub Desktop.
import std.stdio;
import std.datetime;
import std.conv;
import std.traits;
import std.utf;
import std.range;
import std.algorithm;
Target parse2(Target, Source)(ref Source p)
if (isInputRange!Source && isSomeChar!(ElementType!Source) && !is(Source == enum) &&
isFloatingPoint!Target && !is(Target == enum))
{
import std.ascii : isDigit, isAlpha, toLower, toUpper, isHexDigit;
import std.exception : enforce;
import core.stdc.math : HUGE_VAL;
static immutable real[14] negtab =
[ 1e-4096L,1e-2048L,1e-1024L,1e-512L,1e-256L,1e-128L,1e-64L,1e-32L,
1e-16L,1e-8L,1e-4L,1e-2L,1e-1L,1.0L ];
static immutable real[13] postab =
[ 1e+4096L,1e+2048L,1e+1024L,1e+512L,1e+256L,1e+128L,1e+64L,1e+32L,
1e+16L,1e+8L,1e+4L,1e+2L,1e+1L ];
ConvException bailOut()(string msg = null, string fn = __FILE__, size_t ln = __LINE__)
{
if (msg == null)
msg = "Floating point conversion error";
return new ConvException(text(msg, " for input \"", p, "\"."), fn, ln);
}
// special cases for auto-decoding.
// Can't use std.utf.byCodeUnit because it copies
// the range instead of modifying in place
static auto customFront(ref Source r)
{
static if (isAutodecodableString!Source)
return r[0];
else
return r.front;
}
static void customPopFront(ref Source r)
{
static if (isAutodecodableString!Source)
r = r[1 .. $];
else
r.popFront;
}
enforce(!p.empty, bailOut());
bool sign = false;
switch (customFront(p))
{
case '-':
sign = true;
customPopFront(p);
enforce(!p.empty, bailOut());
if (toLower(customFront(p)) == 'i')
goto case 'i';
enforce(!p.empty, bailOut());
break;
case '+':
customPopFront(p);
enforce(!p.empty, bailOut());
break;
case 'i': case 'I':
customPopFront(p);
enforce(!p.empty, bailOut());
if (toLower(customFront(p)) == 'n')
{
customPopFront(p);
enforce(!p.empty, bailOut());
if (toLower(customFront(p)) == 'f')
{
// 'inf'
customPopFront(p);
return sign ? -Target.infinity : Target.infinity;
}
}
goto default;
default: {}
}
bool isHex = false;
bool startsWithZero = customFront(p) == '0';
if (startsWithZero)
{
customPopFront(p);
if (p.empty)
{
return (sign) ? -0.0 : 0.0;
}
isHex = customFront(p) == 'x' || customFront(p) == 'X';
}
real ldval = 0.0;
char dot = 0; /* if decimal point has been seen */
int exp = 0;
long msdec = 0, lsdec = 0;
ulong msscale = 1;
if (isHex)
{
int guard = 0;
int anydigits = 0;
uint ndigits = 0;
customPopFront(p);
while (!p.empty)
{
int i = customFront(p);
while (isHexDigit(i))
{
anydigits = 1;
i = isAlpha(i) ? ((i & ~0x20) - ('A' - 10)) : i - '0';
if (ndigits < 16)
{
msdec = msdec * 16 + i;
if (msdec)
ndigits++;
}
else if (ndigits == 16)
{
while (msdec >= 0)
{
exp--;
msdec <<= 1;
i <<= 1;
if (i & 0x10)
msdec |= 1;
}
guard = i << 4;
ndigits++;
exp += 4;
}
else
{
guard |= i;
exp += 4;
}
exp -= dot;
customPopFront(p);
if (p.empty)
break;
i = customFront(p);
if (i == '_')
{
customPopFront(p);
if (p.empty)
break;
i = customFront(p);
}
}
if (i == '.' && !dot)
{
customPopFront(p);
dot = 4;
}
else
break;
}
// Round up if (guard && (sticky || odd))
if (guard & 0x80 && (guard & 0x7F || msdec & 1))
{
msdec++;
if (msdec == 0) // overflow
{
msdec = 0x8000000000000000L;
exp++;
}
}
enforce(anydigits, bailOut());
enforce(!p.empty && (customFront(p) == 'p' || customFront(p) == 'P'),
bailOut("Floating point parsing: exponent is required"));
char sexp;
int e;
sexp = 0;
customPopFront(p);
if (!p.empty)
{
switch (customFront(p))
{
case '-': sexp++;
goto case;
case '+': customPopFront(p); enforce(!p.empty,
new ConvException("Error converting input"~
" to floating point"));
break;
default: {}
}
}
ndigits = 0;
e = 0;
while (!p.empty && isDigit(customFront(p)))
{
if (e < 0x7FFFFFFF / 10 - 10) // prevent integer overflow
{
e = e * 10 + customFront(p) - '0';
}
customPopFront(p);
ndigits = 1;
}
exp += (sexp) ? -e : e;
enforce(ndigits, new ConvException("Error converting input"~
" to floating point"));
static if (real.mant_dig == 64)
{
if (msdec)
{
int e2 = 0x3FFF + 63;
// left justify mantissa
while (msdec >= 0)
{
msdec <<= 1;
e2--;
}
// Stuff mantissa directly into real
()@trusted{ *cast(long*)&ldval = msdec; }();
()@trusted{ (cast(ushort*)&ldval)[4] = cast(ushort) e2; }();
import std.math : ldexp;
// Exponent is power of 2, not power of 10
ldval = ldexp(ldval,exp);
}
}
else static if (real.mant_dig == 53)
{
if (msdec)
{
//Exponent bias + 52:
//After shifting 52 times left, exp must be 1
int e2 = 0x3FF + 52;
// right justify mantissa
// first 11 bits must be zero, rest is implied bit + mantissa
// shift one time less, do rounding, shift again
while ((msdec & 0xFFC0_0000_0000_0000) != 0)
{
msdec = ((cast(ulong)msdec) >> 1);
e2++;
}
//Have to shift one more time
//and do rounding
if ((msdec & 0xFFE0_0000_0000_0000) != 0)
{
auto roundUp = (msdec & 0x1);
msdec = ((cast(ulong)msdec) >> 1);
e2++;
if (roundUp)
{
msdec += 1;
//If mantissa was 0b1111... and we added +1
//the mantissa should be 0b10000 (think of implicit bit)
//and the exponent increased
if ((msdec & 0x0020_0000_0000_0000) != 0)
{
msdec = 0x0010_0000_0000_0000;
e2++;
}
}
}
// left justify mantissa
// bit 11 must be 1
while ((msdec & 0x0010_0000_0000_0000) == 0)
{
msdec <<= 1;
e2--;
}
// Stuff mantissa directly into double
// (first including implicit bit)
()@trusted{ *cast(long *)&ldval = msdec; }();
//Store exponent, now overwriting implicit bit
()@trusted{ *cast(long *)&ldval &= 0x000F_FFFF_FFFF_FFFF; }();
()@trusted{ *cast(long *)&ldval |= ((e2 & 0xFFFUL) << 52); }();
import std.math : ldexp;
// Exponent is power of 2, not power of 10
ldval = ldexp(ldval,exp);
}
}
else
static assert(false, "Floating point format of real type not supported");
goto L6;
}
else // not hex
{
if (toUpper(customFront(p)) == 'N' && !startsWithZero)
{
// nan
customPopFront(p);
enforce(!p.empty && toUpper(customFront(p)) == 'A',
new ConvException("error converting input to floating point"));
customPopFront(p);
enforce(!p.empty && toUpper(customFront(p)) == 'N',
new ConvException("error converting input to floating point"));
// skip past the last 'n'
customPopFront(p);
return typeof(return).nan;
}
bool sawDigits = startsWithZero;
while (!p.empty)
{
int i = customFront(p);
while (isDigit(i))
{
sawDigits = true; /* must have at least 1 digit */
if (msdec < (0x7FFFFFFFFFFFL-10)/10)
msdec = msdec * 10 + (i - '0');
else if (msscale < (0xFFFFFFFF-10)/10)
{
lsdec = lsdec * 10 + (i - '0');
msscale *= 10;
}
else
{
exp++;
}
exp -= dot;
customPopFront(p);
if (p.empty)
break;
i = customFront(p);
if (i == '_')
{
customPopFront(p);
if (p.empty)
break;
i = customFront(p);
}
}
if (i == '.' && !dot)
{
customPopFront(p);
dot++;
}
else
{
break;
}
}
enforce(sawDigits, new ConvException("no digits seen"));
}
if (!p.empty && (customFront(p) == 'e' || customFront(p) == 'E'))
{
char sexp;
int e;
sexp = 0;
customPopFront(p);
enforce(!p.empty, new ConvException("Unexpected end of input"));
switch (customFront(p))
{
case '-': sexp++;
goto case;
case '+': p.popFront();
break;
default: {}
}
bool sawDigits = 0;
e = 0;
while (!p.empty && isDigit(customFront(p)))
{
if (e < 0x7FFFFFFF / 10 - 10) // prevent integer overflow
{
e = e * 10 + customFront(p) - '0';
}
customPopFront(p);
sawDigits = 1;
}
exp += (sexp) ? -e : e;
enforce(sawDigits, new ConvException("No digits seen."));
}
ldval = msdec;
if (msscale != 1) /* if stuff was accumulated in lsdec */
ldval = ldval * msscale + lsdec;
if (ldval)
{
uint u = 0;
int pow = 4096;
while (exp > 0)
{
while (exp >= pow)
{
ldval *= postab[u];
exp -= pow;
}
pow >>= 1;
u++;
}
while (exp < 0)
{
while (exp <= -pow)
{
ldval *= negtab[u];
enforce(ldval != 0, new ConvException("Range error"));
exp += pow;
}
pow >>= 1;
u++;
}
}
L6: // if overflow occurred
enforce(ldval != HUGE_VAL, new ConvException("Range error"));
L1:
return (sign) ? -ldval : ldval;
}
void main()
{
enum n = 50_000_000;
string test = "123456.789";
double result;
StopWatch sw;
Duration sum;
TickDuration last = TickDuration.from!"seconds"(0);
foreach(i; 0 .. n)
{
sw.start();
//result = parse!double(test);
result = parse2!double(test);
sw.stop();
test = "123456.789";
auto time = sw.peek() - last;
last = sw.peek();
sum += time.to!Duration();
}
writeln("Total time: ", sum);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment