15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/**************************************************************** 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * The author of this software is David M. Gay. 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (c) 1991, 2000, 2001 by Lucent Technologies. 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2002, 2005, 2006, 2007, 2008, 2010, 2012 Apple Inc. All rights reserved. 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Permission to use, copy, modify, and distribute this software for any 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * purpose without fee is hereby granted, provided that this entire notice 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is included in all copies of any software which is or includes a copy 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * or modification of this software and in all copies of the supporting 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation for such software. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ***************************************************************/ 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* Please send bug reports to David M. Gay (dmg at acm dot org, 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * with " at " changed at "@" and " dot " changed to "."). */ 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* On a machine with IEEE extended-precision registers, it is 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * necessary to specify double-precision (53-bit) rounding precision 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * before invoking strtod or dtoa. If the machine uses (the equivalent 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * of) Intel 80x87 arithmetic, the call 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * _control87(PC_53, MCW_PC); 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * does this with many compilers. Whether this or another call is 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * appropriate depends on the compiler; for this to work, it may be 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * necessary to #include "float.h" or another system-dependent header 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * file. 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "dtoa.h" 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "wtf/CPU.h" 3993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "wtf/MathExtras.h" 403c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch#include "wtf/ThreadingPrimitives.h" 4193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "wtf/Vector.h" 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if COMPILER(MSVC) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#pragma warning(disable: 4244) 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#pragma warning(disable: 4245) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#pragma warning(disable: 4554) 471e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 481e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#if _MSC_VER == 1800 491e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)// TODO(scottmg): VS2013 currently ICEs on a bunch of functions in this file. 501e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)// Upstream bug fixed in next release. See http://crbug.com/288498. 511e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#pragma optimize("", off) 521e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#endif 531e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Mutex* s_dtoaP5Mutex; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)typedef union { 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double d; 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t L[2]; 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} U; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if CPU(BIG_ENDIAN) || CPU(MIDDLE_ENDIAN) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define word0(x) (x)->L[0] 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define word1(x) (x)->L[1] 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define word0(x) (x)->L[1] 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define word1(x) (x)->L[0] 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define dval(x) (x)->d 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_shift 20 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_shift1 20 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_msk1 0x100000 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_msk11 0x100000 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_mask 0x7ff00000 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define P 53 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Bias 1023 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Emin (-1022) 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_1 0x3ff00000 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Exp_11 0x3ff00000 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Ebits 11 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Frac_mask 0xfffff 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Frac_mask1 0xfffff 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Ten_pmax 22 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Bletch 0x10 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Bndry_mask 0xfffff 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Bndry_mask1 0xfffff 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define LSB 1 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Sign_bit 0x80000000 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Log2P 1 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Tiny0 0 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Tiny1 1 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Quick_max 14 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Int_max 14 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define rounded_product(a, b) a *= b 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define rounded_quotient(a, b) a /= b 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Big0 (Frac_mask1 | Exp_msk1 * (DBL_MAX_EXP + Bias - 1)) 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Big1 0xffffffff 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1058abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)#if CPU(X86_64) 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// FIXME: should we enable this on all 64-bit CPUs? 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 64-bit emulation provided by the compiler is likely to be slower than dtoa own code on 32-bit hardware. 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define USE_LONG_LONG 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#ifndef USE_LONG_LONG 11251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)/* The following definition of Storeinc is appropriate for MIPS processors. 11351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * An alternative that might be better on some machines is 11451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * *p++ = high << 16 | low & 0xffff; 11551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) */ 11651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)static ALWAYS_INLINE uint32_t* storeInc(uint32_t* p, uint16_t high, uint16_t low) 11751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 11851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) uint16_t* p16 = reinterpret_cast<uint16_t*>(p); 11951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#if CPU(BIG_ENDIAN) 12051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) p16[0] = high; 12151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) p16[1] = low; 12251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#else 12351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) p16[1] = high; 12451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) p16[0] = low; 12551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#endif 12651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return p + 1; 12751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 12851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#endif 12951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct BigInt { 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BigInt() : sign(0) { } 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int sign; 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear() 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sign = 0; 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_words.clear(); 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t size() const 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_words.size(); 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void resize(size_t s) 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_words.resize(s); 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* words() 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_words.data(); 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* words() const 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return m_words.data(); 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void append(uint32_t w) 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_words.append(w); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<uint32_t, 16> m_words; 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static void multadd(BigInt& b, int m, int a) /* multiply by m and add a */ 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long carry; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t carry; 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int wds = b.size(); 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* x = b.words(); 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i = 0; 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = a; 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long y = *x * (unsigned long long)m + carry; 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = y >> 32; 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *x++ = (uint32_t)y & 0xffffffffUL; 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t xi = *x; 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t y = (xi & 0xffff) * m + carry; 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t z = (xi >> 16) * m + (y >> 16); 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z >> 16; 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *x++ = (z << 16) + (y & 0xffff); 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (++i < wds); 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (carry) 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.append((uint32_t)carry); 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static int hi0bits(uint32_t x) 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k = 0; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xffff0000)) { 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 16; 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x <<= 16; 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xff000000)) { 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 8; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x <<= 8; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xf0000000)) { 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 4; 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x <<= 4; 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xc0000000)) { 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 2; 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x <<= 2; 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0x80000000)) { 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k++; 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0x40000000)) 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 32; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return k; 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static int lo0bits(uint32_t* y) 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int k; 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t x = *y; 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x & 7) { 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x & 1) 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (x & 2) { 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *y = x >> 1; 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 1; 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *y = x >> 2; 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 2; 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 0; 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xffff)) { 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = 16; 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x >>= 16; 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xff)) { 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 8; 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x >>= 8; 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0xf)) { 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 4; 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x >>= 4; 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 0x3)) { 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 2; 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x >>= 2; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(x & 1)) { 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k++; 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x >>= 1; 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!x) 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 32; 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *y = x; 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return k; 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static void i2b(BigInt& b, int i) 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.sign = 0; 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(1); 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.words()[0] = i; 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static void mult(BigInt& aRef, const BigInt& bRef) 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* a = &aRef; 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* b = &bRef; 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BigInt c; 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int wa, wb, wc; 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* x = 0; 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xa; 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xb; 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xae; 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xbe; 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* xc; 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* xc0; 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t y; 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long carry, z; 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t carry, z; 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a->size() < b->size()) { 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* tmp = a; 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) a = b; 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b = tmp; 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wa = a->size(); 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wb = b->size(); 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wc = wa + wb; 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.resize(wc); 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (xc = c.words(), xa = xc + wc; xc < xa; xc++) 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc = 0; 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xa = a->words(); 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xae = xa + wa; 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xb = b->words(); 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xbe = xb + wb; 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc0 = c.words(); 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; xb < xbe; xc0++) { 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((y = *xb++)) { 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = xa; 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = xc0; 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = 0; 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = *x++ * (unsigned long long)y + *xc + carry; 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z >> 32; 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc++ = (uint32_t)z & 0xffffffffUL; 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (x < xae); 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc = (uint32_t)carry; 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; xb < xbe; xb++, xc0++) { 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((y = *xb & 0xffff)) { 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = xa; 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = xc0; 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = 0; 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = (*x & 0xffff) * y + (*xc & 0xffff) + carry; 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z >> 16; 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t z2 = (*x++ >> 16) * y + (*xc >> 16) + carry; 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z2 >> 16; 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = storeInc(xc, z2, z); 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (x < xae); 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc = carry; 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((y = *xb >> 16)) { 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = xa; 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = xc0; 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = 0; 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t z2 = *xc; 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = (*x & 0xffff) * y + (*xc >> 16) + carry; 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z >> 16; 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = storeInc(xc, z, z2); 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry; 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = z2 >> 16; 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (x < xae); 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc = z2; 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (xc0 = c.words(), xc = xc0 + wc; wc > 0 && !*--xc; --wc) { } 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.resize(wc); 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) aRef = c; 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct P5Node { 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) WTF_MAKE_NONCOPYABLE(P5Node); WTF_MAKE_FAST_ALLOCATED; 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) P5Node() { } 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BigInt val; 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) P5Node* next; 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static P5Node* p5s; 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static int p5sCount; 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static ALWAYS_INLINE void pow5mult(BigInt& b, int k) 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int p05[3] = { 5, 25, 125 }; 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (int i = k & 3) 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(b, p05[i - 1], 0); 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(k >>= 2)) 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s_dtoaP5Mutex->lock(); 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) P5Node* p5 = p5s; 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!p5) { 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* first time */ 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5 = new P5Node; 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i2b(p5->val, 625); 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5->next = 0; 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5s = p5; 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5sCount = 1; 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int p5sCountLocal = p5sCount; 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s_dtoaP5Mutex->unlock(); 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int p5sUsed = 0; 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (;;) { 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k & 1) 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mult(b, p5->val); 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(k >>= 1)) 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (++p5sUsed == p5sCountLocal) { 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s_dtoaP5Mutex->lock(); 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (p5sUsed == p5sCount) { 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!p5->next); 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5->next = new P5Node; 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5->next->next = 0; 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5->next->val = p5->val; 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mult(p5->next->val, p5->next->val); 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++p5sCount; 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5sCountLocal = p5sCount; 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s_dtoaP5Mutex->unlock(); 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) p5 = p5->next; 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static ALWAYS_INLINE void lshift(BigInt& b, int k) 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int n = k >> 5; 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int origSize = b.size(); 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int n1 = n + origSize + 1; 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k &= 0x1f) 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(b.size() + n + 1); 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(b.size() + n); 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* srcStart = b.words(); 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* dstStart = b.words(); 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* src = srcStart + origSize - 1; 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* dst = dstStart + n1 - 1; 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k) { 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t hiSubword = 0; 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int s = 32 - k; 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; src >= srcStart; --src) { 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *dst-- = hiSubword | *src >> s; 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) hiSubword = *src << k; 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *dst = hiSubword; 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(dst == dstStart + n); 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(origSize + n + !!b.words()[n1 - 1]); 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *--dst = *src--; 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (src >= srcStart); 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (dst = dstStart + n; dst != dstStart; ) 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *--dst = 0; 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(b.size() <= 1 || b.words()[b.size() - 1]); 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static int cmp(const BigInt& a, const BigInt& b) 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t *xa, *xa0, *xb, *xb0; 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i, j; 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = a.size(); 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = b.size(); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(i <= 1 || a.words()[i - 1]); 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(j <= 1 || b.words()[j - 1]); 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i -= j) 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return i; 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xa0 = a.words(); 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xa = xa0 + j; 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xb0 = b.words(); 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xb = xb0 + j; 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (;;) { 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (*--xa != *--xb) 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return *xa < *xb ? -1 : 1; 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (xa <= xa0) 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static ALWAYS_INLINE void diff(BigInt& c, const BigInt& aRef, const BigInt& bRef) 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* a = &aRef; 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* b = &bRef; 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i, wa, wb; 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* xc; 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = cmp(*a, *b); 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!i) { 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.sign = 0; 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.resize(1); 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.words()[0] = 0; 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i < 0) { 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const BigInt* tmp = a; 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) a = b; 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b = tmp; 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 1; 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 0; 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wa = a->size(); 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xa = a->words(); 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xae = xa + wa; 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wb = b->size(); 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xb = b->words(); 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t* xbe = xb + wb; 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.resize(wa); 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.sign = i; 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = c.words(); 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long borrow = 0; 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long y = (unsigned long long)*xa++ - *xb++ - borrow; 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = y >> 32 & (uint32_t)1; 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc++ = (uint32_t)y & 0xffffffffUL; 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (xb < xbe); 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (xa < xae) { 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long y = *xa++ - borrow; 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = y >> 32 & (uint32_t)1; 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *xc++ = (uint32_t)y & 0xffffffffUL; 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t borrow = 0; 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t y = (*xa & 0xffff) - (*xb & 0xffff) - borrow; 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (y & 0x10000) >> 16; 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t z = (*xa++ >> 16) - (*xb++ >> 16) - borrow; 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (z & 0x10000) >> 16; 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = storeInc(xc, z, y); 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (xb < xbe); 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (xa < xae) { 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t y = (*xa & 0xffff) - borrow; 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (y & 0x10000) >> 16; 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t z = (*xa++ >> 16) - borrow; 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (z & 0x10000) >> 16; 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) xc = storeInc(xc, z, y); 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (!*--xc) 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) wa--; 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.resize(wa); 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static ALWAYS_INLINE void d2b(BigInt& b, U* d, int* e, int* bits) 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int de, k; 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* x; 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t y, z; 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i; 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define d0 word0(d) 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define d1 word1(d) 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.sign = 0; 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(1); 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = b.words(); 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = d0 & Frac_mask; 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) d0 &= 0x7fffffff; /* clear sign bit, which we ignore */ 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((de = (int)(d0 >> Exp_shift))) 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z |= Exp_msk1; 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((y = d1)) { 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((k = lo0bits(&y))) { 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x[0] = y | (z << (32 - k)); 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z >>= k; 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x[0] = y; 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (z) { 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(2); 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x[1] = z; 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = b.size(); 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = lo0bits(&z); 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x[0] = z; 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 1; 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(1); 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k += 32; 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (de) { 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *e = de - Bias - (P - 1) + k; 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *bits = P - k; 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *e = 0 - Bias - (P - 1) + 1 + k; 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *bits = (32 * i) - hi0bits(x[i - 1]); 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#undef d0 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#undef d1 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static const double tens[] = { 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1e20, 1e21, 1e22 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static const double bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 }; 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define Scale_Bit 0x10 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define n_bigtens 5 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static ALWAYS_INLINE int quorem(BigInt& b, BigInt& S) 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t n; 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* bx; 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* bxe; 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t q; 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* sx; 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t* sxe; 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned long long borrow, carry, y, ys; 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t borrow, carry, y, ys; 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t si, z, zs; 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(b.size() <= 1 || b.words()[b.size() - 1]); 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(S.size() <= 1 || S.words()[S.size() - 1]); 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) n = S.size(); 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_WITH_MESSAGE(b.size() <= n, "oversize b in quorem"); 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (b.size() < n) 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sx = S.words(); 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sxe = sx + --n; 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = b.words(); 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bxe = bx + n; 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT_WITH_MESSAGE(q <= 9, "oversized quotient in quorem"); 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (q) { 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = 0; 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = 0; 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ys = *sx++ * (unsigned long long)q + carry; 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = ys >> 32; 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = *bx - (ys & 0xffffffffUL) - borrow; 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = y >> 32 & (uint32_t)1; 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *bx++ = (uint32_t)y & 0xffffffffUL; 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) si = *sx++; 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ys = (si & 0xffff) * q + carry; 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) zs = (si >> 16) * q + (ys >> 16); 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = zs >> 16; 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (y & 0x10000) >> 16; 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = (*bx >> 16) - (zs & 0xffff) - borrow; 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (z & 0x10000) >> 16; 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = storeInc(bx, z, y); 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (sx <= sxe); 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!*bxe) { 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = b.words(); 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (--bxe > bx && !*bxe) 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --n; 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(n); 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (cmp(b, S) >= 0) { 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) q++; 6705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = 0; 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = 0; 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = b.words(); 6735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sx = S.words(); 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef USE_LONG_LONG 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ys = *sx++ + carry; 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = ys >> 32; 6785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = *bx - (ys & 0xffffffffUL) - borrow; 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = y >> 32 & (uint32_t)1; 6805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *bx++ = (uint32_t)y & 0xffffffffUL; 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) si = *sx++; 6835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ys = (si & 0xffff) + carry; 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) zs = (si >> 16) + (ys >> 16); 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = zs >> 16; 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (y & 0x10000) >> 16; 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) z = (*bx >> 16) - (zs & 0xffff) - borrow; 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = (z & 0x10000) >> 16; 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = storeInc(bx, z, y); 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (sx <= sxe); 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bx = b.words(); 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bxe = bx + n; 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!*bxe) { 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (--bxe > bx && !*bxe) 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --n; 6985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b.resize(n); 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return q; 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* dtoa for IEEE arithmetic (dmg): convert double to ASCII string. 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Inspired by "How to Print Floating-Point Numbers Accurately" by 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126]. 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Modifications: 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Rather than iterating, we use a simple numeric overestimate 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to determine k = floor(log10(d)). We scale relevant 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * quantities using O(log2(k)) rather than O(k) multiplications. 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * try to generate digits strictly left to right. Instead, we 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * compute with fewer bits and propagate the carry if necessary 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * when rounding the final digit up. This is often faster. 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3. Under the assumption that input will be rounded nearest, 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22. 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * That is, we allow equality in stopping tests when the 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * round-nearest rule will give the same floating-point value 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * as would satisfaction of the stopping test with strict 7225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * inequality. 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 4. We remove common factors of powers of 2 from relevant 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * quantities. 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 5. When converting floating-point integers less than 1e16, 7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * we use floating-point arithmetic rather than resorting 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to multiple-precision integers. 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 6. When asked to produce fewer than 15 digits, we first try 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to get by with floating-point arithmetic; we resort to 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * multiple-precision integer arithmetic only if we cannot 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * guarantee that the floating-point calculation has given 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the correctly rounded result. For k requested digits and 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "uniformly" distributed input, the probability is 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * something like 10^(k-15) that we must resort to the int32_t 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * calculation. 7365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Note: 'leftright' translates to 'generate shortest possible string'. 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 7395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)template<bool roundingNone, bool roundingSignificantFigures, bool roundingDecimalPlaces, bool leftright> 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void dtoa(DtoaBuffer result, double dd, int ndigits, bool& signOut, int& exponentOut, unsigned& precisionOut) 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Exactly one rounding mode must be specified. 7435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(roundingNone + roundingSignificantFigures + roundingDecimalPlaces == 1); 7445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // roundingNone only allowed (only sensible?) with leftright set. 7455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!roundingNone || leftright); 7465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 747926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(std::isfinite(dd)); 7485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bbits, b2, b5, be, dig, i, ieps, ilim = 0, ilim0, ilim1 = 0, 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j, j1, k, k0, k_check, m2, m5, s2, s5, 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) spec_case; 7525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int32_t L; 7535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int denorm; 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint32_t x; 7555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BigInt b, delta, mlo, mhi, S; 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) U d2, eps, u; 7575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double ds; 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) char* s; 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) char* s0; 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) u.d = dd; 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Infinity or NaN */ 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT((word0(&u) & Exp_mask) != Exp_mask); 7655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // JavaScript toString conversion treats -0 as 0. 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!dval(&u)) { 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) signOut = false; 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponentOut = 0; 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) precisionOut = 1; 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result[0] = '0'; 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result[1] = '\0'; 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (word0(&u) & Sign_bit) { 7775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) signOut = true; 7785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) word0(&u) &= ~Sign_bit; // clear sign bit 7795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) signOut = false; 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) d2b(b, &u, &be, &bbits); 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((i = (int)(word0(&u) >> Exp_shift1 & (Exp_mask >> Exp_shift1)))) { 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&d2) = dval(&u); 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) word0(&d2) &= Frac_mask1; 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) word0(&d2) |= Exp_11; 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* log(x) ~=~ log(1.5) + (x-1.5)/1.5 7895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * log10(x) = log(x) / log(10) 7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10)) 7915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2) 7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This suggests computing an approximation k to log10(d) by 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * k = (i - Bias)*0.301029995663981 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 ); 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * We want k to be too large rather than too small. 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * The error in the first-order Taylor series approximation 8005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is in our favor, so we just round up the constant enough 8015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to compensate for any error in the multiplication of 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077, 8035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14, 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * adding 1e-13 to the constant term more than suffices. 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Hence we adjust the constant term to 0.1760912590558. 8065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (We could get a more accurate k by invoking log10, 8075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but this is probably not worthwhile.) 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 8095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i -= Bias; 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denorm = 0; 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* d is denormalized */ 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = bbits + be + (Bias + (P - 1) - 1); 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) x = (i > 32) ? (word0(&u) << (64 - i)) | (word1(&u) >> (i - 32)) 8175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : word1(&u) << (32 - i); 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&d2) = x; 8195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) word0(&d2) -= 31 * Exp_msk1; /* adjust exponent */ 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i -= (Bias + (P - 1) - 1) + 1; 8215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denorm = 1; 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ds = (dval(&d2) - 1.5) * 0.289529654602168 + 0.1760912590558 + (i * 0.301029995663981); 8245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = (int)ds; 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ds < 0. && ds != k) 8265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k--; /* want k = floor(ds) */ 8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k_check = 1; 8285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k >= 0 && k <= Ten_pmax) { 8295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) < tens[k]) 8305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k--; 8315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k_check = 0; 8325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = bbits - i - 1; 8345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j >= 0) { 8355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 = 0; 8365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 = j; 8375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 = -j; 8395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 = 0; 8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k >= 0) { 8425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b5 = 0; 8435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s5 = k; 8445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 += k; 8455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 8465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 -= k; 8475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b5 = -k; 8485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s5 = 0; 8495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (roundingNone) { 8525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = ilim1 = -1; 8535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 18; 8545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ndigits = 0; 8555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (roundingSignificantFigures) { 8575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ndigits <= 0) 8585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ndigits = 1; 8595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = ilim1 = i = ndigits; 8605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (roundingDecimalPlaces) { 8625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = ndigits + k + 1; 8635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = i; 8645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim1 = i - 1; 8655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i <= 0) 8665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 1; 8675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s = s0 = result; 8705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ilim >= 0 && ilim <= Quick_max) { 8725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Try to get by with floating-point arithmetic. */ 8735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 0; 8755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&d2) = dval(&u); 8765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k0 = k; 8775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim0 = ilim; 8785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ieps = 2; /* conservative */ 8795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k > 0) { 8805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ds = tens[k & 0xf]; 8815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = k >> 4; 8825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j & Bletch) { 8835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* prevent overflows */ 8845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j &= Bletch - 1; 8855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) /= bigtens[n_bigtens - 1]; 8865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ieps++; 8875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; j; j >>= 1, i++) { 8895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j & 1) { 8905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ieps++; 8915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ds *= bigtens[i]; 8925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) /= ds; 8955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if ((j1 = -k)) { 8965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) *= tens[j1 & 0xf]; 8975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (j = j1 >> 4; j; j >>= 1, i++) { 8985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j & 1) { 8995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ieps++; 9005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) *= bigtens[i]; 9015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k_check && dval(&u) < 1. && ilim > 0) { 9055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ilim1 <= 0) 9065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto fastFailed; 9075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = ilim1; 9085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k--; 9095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) *= 10.; 9105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ieps++; 9115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&eps) = (ieps * dval(&u)) + 7.; 9135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) word0(&eps) -= (P - 1) * Exp_msk1; 9145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!ilim) { 9155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) S.clear(); 9165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mhi.clear(); 9175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) -= 5.; 9185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) > dval(&eps)) 9195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto oneDigit; 9205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) < -dval(&eps)) 9215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto noDigits; 9225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto fastFailed; 9235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (leftright) { 9255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Use Steele & White method of only 9265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * generating digits needed. 9275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 9285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&eps) = (0.5 / tens[ilim - 1]) - dval(&eps); 9295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 0;;) { 9305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) L = (long int)dval(&u); 9315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) -= L; 9325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '0' + (int)L; 9335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) < dval(&eps)) 9345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 9355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (1. - dval(&u) < dval(&eps)) 9365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto bumpUp; 9375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (++i >= ilim) 9385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 9395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&eps) *= 10.; 9405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) *= 10.; 9415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 9435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Generate ilim digits, then fix them up. */ 9445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&eps) *= tens[ilim - 1]; 9455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 1;; i++, dval(&u) *= 10.) { 9465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) L = (int32_t)(dval(&u)); 9475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!(dval(&u) -= L)) 9485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = i; 9495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '0' + (int)L; 9505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i == ilim) { 9515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) > 0.5 + dval(&eps)) 9525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto bumpUp; 9535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) < 0.5 - dval(&eps)) { 9545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (*--s == '0') { } 9555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s++; 9565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 9575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 9595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)fastFailed: 9635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s = s0; 9645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) = dval(&d2); 9655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k = k0; 9665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = ilim0; 9675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Do we have a "small" integer? */ 9705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 9715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (be >= 0 && k <= Int_max) { 9725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Yes. */ 9735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ds = tens[k]; 9745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ndigits < 0 && ilim <= 0) { 9755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) S.clear(); 9765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mhi.clear(); 9775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ilim < 0 || dval(&u) <= 5 * ds) 9785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto noDigits; 9795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto oneDigit; 9805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 1;; i++, dval(&u) *= 10.) { 9825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) L = (int32_t)(dval(&u) / ds); 9835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) -= L * ds; 9845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '0' + (int)L; 9855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!dval(&u)) { 9865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 9875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i == ilim) { 9895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dval(&u) += dval(&u); 9905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dval(&u) > ds || (dval(&u) == ds && (L & 1))) { 9915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)bumpUp: 9925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (*--s == '9') 9935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (s == s0) { 9945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k++; 9955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s = '0'; 9965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 9975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++*s++; 9995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 10015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 10045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m2 = b2; 10075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m5 = b5; 10085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mhi.clear(); 10095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mlo.clear(); 10105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (leftright) { 10115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = denorm ? be + (Bias + (P - 1) - 1 + 1) : 1 + P - bbits; 10125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 += i; 10135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 += i; 10145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i2b(mhi, 1); 10155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m2 > 0 && s2 > 0) { 10175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = m2 < s2 ? m2 : s2; 10185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 -= i; 10195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m2 -= i; 10205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 -= i; 10215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (b5 > 0) { 10235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (leftright) { 10245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m5 > 0) { 10255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pow5mult(mhi, m5); 10265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mult(b, mhi); 10275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((j = b5 - m5)) 10295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pow5mult(b, j); 10305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else 10315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pow5mult(b, b5); 10325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i2b(S, 1); 10345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (s5 > 0) 10355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pow5mult(S, s5); 10365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Check for special case that d is a normalized power of 2. */ 10385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) spec_case = 0; 10405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((roundingNone || leftright) && (!word1(&u) && !(word0(&u) & Bndry_mask) && word0(&u) & (Exp_mask & ~Exp_msk1))) { 10415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* The special case */ 10425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 += Log2P; 10435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 += Log2P; 10445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) spec_case = 1; 10455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Arrange for convenient computation of quotients: 10485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * shift left if necessary so divisor has 4 leading 0 bits. 10495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 10505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Perhaps we should just compute leading 28 bits of S once 10515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * and for all and pass them and a shift to quorem, so it 10525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * can do shifts and ors to compute the numerator for q. 10535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 10545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((i = ((s5 ? 32 - hi0bits(S.words()[S.size() - 1]) : 1) + s2) & 0x1f)) 10555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i = 32 - i; 10565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i > 4) { 10575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i -= 4; 10585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 += i; 10595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m2 += i; 10605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 += i; 10615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (i < 4) { 10625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) i += 28; 10635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) b2 += i; 10645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m2 += i; 10655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s2 += i; 10665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (b2 > 0) 10685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(b, b2); 10695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (s2 > 0) 10705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(S, s2); 10715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (k_check) { 10725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (cmp(b, S) < 0) { 10735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k--; 10745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(b, 10, 0); /* we botched the k estimate */ 10755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (leftright) 10765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(mhi, 10, 0); 10775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ilim = ilim1; 10785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ilim <= 0 && roundingDecimalPlaces) { 10815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (ilim < 0) 10825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto noDigits; 10835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(S, 5, 0); 10845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For IEEE-754 unbiased rounding this check should be <=, such that 0.5 would flush to zero. 10855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (cmp(b, S) < 0) 10865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto noDigits; 10875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto oneDigit; 10885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 10895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (leftright) { 10905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m2 > 0) 10915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(mhi, m2); 10925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Compute mlo -- check for special case 10945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * that d is a normalized power of 2. 10955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 10965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mlo = mhi; 10985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (spec_case) 10995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(mhi, Log2P); 11005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 1;;i++) { 11025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dig = quorem(b, S) + '0'; 11035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Do we yet have the shortest decimal string 11045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * that will round to d? 11055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 11065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = cmp(b, mlo); 11075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) diff(delta, S, mhi); 11085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j1 = delta.sign ? 1 : cmp(b, delta); 11095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef DTOA_ROUND_BIASED 11105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j < 0 || !j) { 11115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#else 11125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: ECMA-262 specifies that equidistant results round away from 11135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // zero, which probably means we shouldn't be on the unbiased code path 11145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // (the (word1(&u) & 1) clause is looking highly suspicious). I haven't 11155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // yet understood this code well enough to make the call, but we should 11165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // probably be enabling DTOA_ROUND_BIASED. I think the interesting corner 11175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // case to understand is probably "Math.pow(0.5, 24).toString()". 11185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // I believe this value is interesting because I think it is precisely 11195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // representable in binary floating point, and its decimal representation 11205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // has a single digit that Steele & White reduction can remove, with the 11215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // value 5 (thus equidistant from the next numbers above and below). 11225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We produce the correct answer using either codepath, and I don't as 11235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // yet understand why. :-) 11245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!j1 && !(word1(&u) & 1)) { 11255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dig == '9') 11265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto round9up; 11275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j > 0) 11285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dig++; 11295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = dig; 11305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j < 0 || (!j && !(word1(&u) & 1))) { 11335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 11345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((b.words()[0] || b.size() > 1) && (j1 > 0)) { 11355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(b, 1); 11365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j1 = cmp(b, S); 11375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For IEEE-754 round-to-even, this check should be (j1 > 0 || (!j1 && (dig & 1))), 11385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // but ECMA-262 specifies that equidistant values (e.g. (.5).toFixed()) should 11395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // be rounded away from zero. 11405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j1 >= 0) { 11415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dig == '9') 11425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto round9up; 11435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dig++; 11445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = dig; 11475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j1 > 0) { 11505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dig == '9') { /* possible if i == 1 */ 11515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)round9up: 11525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '9'; 11535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto roundoff; 11545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = dig + 1; 11565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = dig; 11595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i == ilim) 11605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 11615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(b, 10, 0); 11625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(mlo, 10, 0); 11635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(mhi, 10, 0); 11645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 11665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 1;; i++) { 11675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = dig = quorem(b, S) + '0'; 11685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!b.words()[0] && b.size() <= 1) 11695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i >= ilim) 11715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 11725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) multadd(b, 10, 0); 11735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /* Round off last digit */ 11775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 11785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) lshift(b, 1); 11795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) j = cmp(b, S); 11805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For IEEE-754 round-to-even, this check should be (j > 0 || (!j && (dig & 1))), 11815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // but ECMA-262 specifies that equidistant values (e.g. (.5).toFixed()) should 11825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // be rounded away from zero. 11835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (j >= 0) { 11845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)roundoff: 11855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (*--s == '9') 11865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (s == s0) { 11875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k++; 11885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '1'; 11895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++*s++; 11925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 11935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (*--s == '0') { } 11945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) s++; 11955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 11965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 11975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)noDigits: 11985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponentOut = 0; 11995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) precisionOut = 1; 12005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result[0] = '0'; 12015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result[1] = '\0'; 12025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 12035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)oneDigit: 12045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s++ = '1'; 12055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) k++; 12065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) goto ret; 12075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ret: 12085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(s > result); 12095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *s = 0; 12105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponentOut = k; 12115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) precisionOut = s - result; 12125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void dtoa(DtoaBuffer result, double dd, bool& sign, int& exponent, unsigned& precision) 12155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // flags are roundingNone, leftright. 12175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dtoa<true, false, false, true>(result, dd, 0, sign, exponent, precision); 12185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void dtoaRoundSF(DtoaBuffer result, double dd, int ndigits, bool& sign, int& exponent, unsigned& precision) 12215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // flag is roundingSignificantFigures. 12235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dtoa<false, true, false, false>(result, dd, ndigits, sign, exponent, precision); 12245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)void dtoaRoundDP(DtoaBuffer result, double dd, int ndigits, bool& sign, int& exponent, unsigned& precision) 12275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // flag is roundingDecimalPlaces. 12295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dtoa<false, false, true, false>(result, dd, ndigits, sign, exponent, precision); 12305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)const char* numberToString(double d, NumberToStringBuffer buffer) 12335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 12355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 12365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) converter.ToShortest(d, &builder); 12375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 12385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)static inline const char* formatStringTruncatingTrailingZerosIfNeeded(NumberToStringBuffer buffer, double_conversion::StringBuilder& builder) 12415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t length = builder.position(); 12435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t decimalPointPosition = 0; 12445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; decimalPointPosition < length; ++decimalPointPosition) { 12455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer[decimalPointPosition] == '.') 12465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 12475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 12485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // No decimal seperator found, early exit. 12505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (decimalPointPosition == length) 12515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 12525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t truncatedLength = length - 1; 12545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (; truncatedLength > decimalPointPosition; --truncatedLength) { 12555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer[truncatedLength] != '0') 12565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 12575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 12585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // No trailing zeros found to strip. 12605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (truncatedLength == length - 1) 12615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 12625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If we removed all trailing zeros, remove the decimal point as well. 12645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (truncatedLength == decimalPointPosition) { 12655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(truncatedLength > 0); 12665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) --truncatedLength; 12675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 12685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Truncate the StringBuilder, and return the final result. 12705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) builder.SetPosition(truncatedLength + 1); 12715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 12725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)const char* numberToFixedPrecisionString(double d, unsigned significantFigures, NumberToStringBuffer buffer, bool truncateTrailingZeros) 12755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Mimic String::format("%.[precision]g", ...), but use dtoas rounding facilities. 12775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "g": Signed value printed in f or e format, whichever is more compact for the given value and precision. 12785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The e format is used only when the exponent of the value is less than –4 or greater than or equal to the 12795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // precision argument. Trailing zeros are truncated, and the decimal point appears only if one or more digits follow it. 12805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "precision": The precision specifies the maximum number of significant digits printed. 12815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 12825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 12835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) converter.ToPrecision(d, significantFigures, &builder); 12845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!truncateTrailingZeros) 12855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 12865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return formatStringTruncatingTrailingZerosIfNeeded(buffer, builder); 12875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 12885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 12895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)const char* numberToFixedWidthString(double d, unsigned decimalPlaces, NumberToStringBuffer buffer) 12905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 12915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Mimic String::format("%.[precision]f", ...), but use dtoas rounding facilities. 12925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "f": Signed value having the form [ – ]dddd.dddd, where dddd is one or more decimal digits. 12935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The number of digits before the decimal point depends on the magnitude of the number, and 12945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the number of digits after the decimal point depends on the requested precision. 12955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "precision": The precision value specifies the number of digits after the decimal point. 12965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If a decimal point appears, at least one digit appears before it. 129702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch // The value is rounded to the appropriate number of digits. 12985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double_conversion::StringBuilder builder(buffer, NumberToStringBufferLength); 12995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const double_conversion::DoubleToStringConverter& converter = double_conversion::DoubleToStringConverter::EcmaScriptConverter(); 13005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) converter.ToFixed(d, decimalPlaces, &builder); 13015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return builder.Finalize(); 13025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 13035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace Internal { 13055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)double parseDoubleFromLongString(const UChar* string, size_t length, size_t& parsedLength) 13075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 13085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<LChar> conversionBuffer(length); 13095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (size_t i = 0; i < length; ++i) 13105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) conversionBuffer[i] = isASCII(string[i]) ? string[i] : 0; 13115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return parseDouble(conversionBuffer.data(), length, parsedLength); 13125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 13135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace Internal 13155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 13165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 1317