1 // Tencent is pleased to support the open source community by making RapidJSON available.
2 //
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
4 //
5 // Licensed under the MIT License (the "License"); you may not use this file except
6 // in compliance with the License. You may obtain a copy of the License at
7 //
8 // http://opensource.org/licenses/MIT
9 //
10 // Unless required by applicable law or agreed to in writing, software distributed
11 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
12 // CONDITIONS OF ANY KIND, either express or implied. See the License for the
13 // specific language governing permissions and limitations under the License.
14 
15 // This is a C++ header-only implementation of Grisu2 algorithm from the publication:
16 // Loitsch, Florian. "Printing floating-point numbers quickly and accurately with
17 // integers." ACM Sigplan Notices 45.6 (2010): 233-243.
18 
19 #ifndef RAPIDJSON_DIYFP_H_
20 #define RAPIDJSON_DIYFP_H_
21 
22 #include "../rapidjson.h"
23 
24 #if defined(_MSC_VER) && defined(_M_AMD64)
25 #include <intrin.h>
26 #pragma intrinsic(_BitScanReverse64)
27 #pragma intrinsic(_umul128)
28 #endif
29 
30 RAPIDJSON_NAMESPACE_BEGIN
31 namespace internal {
32 
33 #ifdef __GNUC__
34 RAPIDJSON_DIAG_PUSH
35 RAPIDJSON_DIAG_OFF(effc++)
36 #endif
37 
38 struct DiyFp {
DiyFpDiyFp39     DiyFp() {}
40 
DiyFpDiyFp41     DiyFp(uint64_t fp, int exp) : f(fp), e(exp) {}
42 
DiyFpDiyFp43     explicit DiyFp(double d) {
44         union {
45             double d;
46             uint64_t u64;
47         } u = { d };
48 
49         int biased_e = static_cast<int>((u.u64 & kDpExponentMask) >> kDpSignificandSize);
50         uint64_t significand = (u.u64 & kDpSignificandMask);
51         if (biased_e != 0) {
52             f = significand + kDpHiddenBit;
53             e = biased_e - kDpExponentBias;
54         }
55         else {
56             f = significand;
57             e = kDpMinExponent + 1;
58         }
59     }
60 
61     DiyFp operator-(const DiyFp& rhs) const {
62         return DiyFp(f - rhs.f, e);
63     }
64 
65     DiyFp operator*(const DiyFp& rhs) const {
66 #if defined(_MSC_VER) && defined(_M_AMD64)
67         uint64_t h;
68         uint64_t l = _umul128(f, rhs.f, &h);
69         if (l & (uint64_t(1) << 63)) // rounding
70             h++;
71         return DiyFp(h, e + rhs.e + 64);
72 #elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
73         __extension__ typedef unsigned __int128 uint128;
74         uint128 p = static_cast<uint128>(f) * static_cast<uint128>(rhs.f);
75         uint64_t h = static_cast<uint64_t>(p >> 64);
76         uint64_t l = static_cast<uint64_t>(p);
77         if (l & (uint64_t(1) << 63)) // rounding
78             h++;
79         return DiyFp(h, e + rhs.e + 64);
80 #else
81         const uint64_t M32 = 0xFFFFFFFF;
82         const uint64_t a = f >> 32;
83         const uint64_t b = f & M32;
84         const uint64_t c = rhs.f >> 32;
85         const uint64_t d = rhs.f & M32;
86         const uint64_t ac = a * c;
87         const uint64_t bc = b * c;
88         const uint64_t ad = a * d;
89         const uint64_t bd = b * d;
90         uint64_t tmp = (bd >> 32) + (ad & M32) + (bc & M32);
91         tmp += 1U << 31;  /// mult_round
92         return DiyFp(ac + (ad >> 32) + (bc >> 32) + (tmp >> 32), e + rhs.e + 64);
93 #endif
94     }
95 
NormalizeDiyFp96     DiyFp Normalize() const {
97 #if defined(_MSC_VER) && defined(_M_AMD64)
98         unsigned long index;
99         _BitScanReverse64(&index, f);
100         return DiyFp(f << (63 - index), e - (63 - index));
101 #elif defined(__GNUC__) && __GNUC__ >= 4
102         int s = __builtin_clzll(f);
103         return DiyFp(f << s, e - s);
104 #else
105         DiyFp res = *this;
106         while (!(res.f & (static_cast<uint64_t>(1) << 63))) {
107             res.f <<= 1;
108             res.e--;
109         }
110         return res;
111 #endif
112     }
113 
NormalizeBoundaryDiyFp114     DiyFp NormalizeBoundary() const {
115         DiyFp res = *this;
116         while (!(res.f & (kDpHiddenBit << 1))) {
117             res.f <<= 1;
118             res.e--;
119         }
120         res.f <<= (kDiySignificandSize - kDpSignificandSize - 2);
121         res.e = res.e - (kDiySignificandSize - kDpSignificandSize - 2);
122         return res;
123     }
124 
NormalizedBoundariesDiyFp125     void NormalizedBoundaries(DiyFp* minus, DiyFp* plus) const {
126         DiyFp pl = DiyFp((f << 1) + 1, e - 1).NormalizeBoundary();
127         DiyFp mi = (f == kDpHiddenBit) ? DiyFp((f << 2) - 1, e - 2) : DiyFp((f << 1) - 1, e - 1);
128         mi.f <<= mi.e - pl.e;
129         mi.e = pl.e;
130         *plus = pl;
131         *minus = mi;
132     }
133 
ToDoubleDiyFp134     double ToDouble() const {
135         union {
136             double d;
137             uint64_t u64;
138         }u;
139         const uint64_t be = (e == kDpDenormalExponent && (f & kDpHiddenBit) == 0) ? 0 :
140             static_cast<uint64_t>(e + kDpExponentBias);
141         u.u64 = (f & kDpSignificandMask) | (be << kDpSignificandSize);
142         return u.d;
143     }
144 
145     static const int kDiySignificandSize = 64;
146     static const int kDpSignificandSize = 52;
147     static const int kDpExponentBias = 0x3FF + kDpSignificandSize;
148     static const int kDpMaxExponent = 0x7FF - kDpExponentBias;
149     static const int kDpMinExponent = -kDpExponentBias;
150     static const int kDpDenormalExponent = -kDpExponentBias + 1;
151     static const uint64_t kDpExponentMask = RAPIDJSON_UINT64_C2(0x7FF00000, 0x00000000);
152     static const uint64_t kDpSignificandMask = RAPIDJSON_UINT64_C2(0x000FFFFF, 0xFFFFFFFF);
153     static const uint64_t kDpHiddenBit = RAPIDJSON_UINT64_C2(0x00100000, 0x00000000);
154 
155     uint64_t f;
156     int e;
157 };
158 
GetCachedPowerByIndex(size_t index)159 inline DiyFp GetCachedPowerByIndex(size_t index) {
160     // 10^-348, 10^-340, ..., 10^340
161     static const uint64_t kCachedPowers_F[] = {
162         RAPIDJSON_UINT64_C2(0xfa8fd5a0, 0x081c0288), RAPIDJSON_UINT64_C2(0xbaaee17f, 0xa23ebf76),
163         RAPIDJSON_UINT64_C2(0x8b16fb20, 0x3055ac76), RAPIDJSON_UINT64_C2(0xcf42894a, 0x5dce35ea),
164         RAPIDJSON_UINT64_C2(0x9a6bb0aa, 0x55653b2d), RAPIDJSON_UINT64_C2(0xe61acf03, 0x3d1a45df),
165         RAPIDJSON_UINT64_C2(0xab70fe17, 0xc79ac6ca), RAPIDJSON_UINT64_C2(0xff77b1fc, 0xbebcdc4f),
166         RAPIDJSON_UINT64_C2(0xbe5691ef, 0x416bd60c), RAPIDJSON_UINT64_C2(0x8dd01fad, 0x907ffc3c),
167         RAPIDJSON_UINT64_C2(0xd3515c28, 0x31559a83), RAPIDJSON_UINT64_C2(0x9d71ac8f, 0xada6c9b5),
168         RAPIDJSON_UINT64_C2(0xea9c2277, 0x23ee8bcb), RAPIDJSON_UINT64_C2(0xaecc4991, 0x4078536d),
169         RAPIDJSON_UINT64_C2(0x823c1279, 0x5db6ce57), RAPIDJSON_UINT64_C2(0xc2109436, 0x4dfb5637),
170         RAPIDJSON_UINT64_C2(0x9096ea6f, 0x3848984f), RAPIDJSON_UINT64_C2(0xd77485cb, 0x25823ac7),
171         RAPIDJSON_UINT64_C2(0xa086cfcd, 0x97bf97f4), RAPIDJSON_UINT64_C2(0xef340a98, 0x172aace5),
172         RAPIDJSON_UINT64_C2(0xb23867fb, 0x2a35b28e), RAPIDJSON_UINT64_C2(0x84c8d4df, 0xd2c63f3b),
173         RAPIDJSON_UINT64_C2(0xc5dd4427, 0x1ad3cdba), RAPIDJSON_UINT64_C2(0x936b9fce, 0xbb25c996),
174         RAPIDJSON_UINT64_C2(0xdbac6c24, 0x7d62a584), RAPIDJSON_UINT64_C2(0xa3ab6658, 0x0d5fdaf6),
175         RAPIDJSON_UINT64_C2(0xf3e2f893, 0xdec3f126), RAPIDJSON_UINT64_C2(0xb5b5ada8, 0xaaff80b8),
176         RAPIDJSON_UINT64_C2(0x87625f05, 0x6c7c4a8b), RAPIDJSON_UINT64_C2(0xc9bcff60, 0x34c13053),
177         RAPIDJSON_UINT64_C2(0x964e858c, 0x91ba2655), RAPIDJSON_UINT64_C2(0xdff97724, 0x70297ebd),
178         RAPIDJSON_UINT64_C2(0xa6dfbd9f, 0xb8e5b88f), RAPIDJSON_UINT64_C2(0xf8a95fcf, 0x88747d94),
179         RAPIDJSON_UINT64_C2(0xb9447093, 0x8fa89bcf), RAPIDJSON_UINT64_C2(0x8a08f0f8, 0xbf0f156b),
180         RAPIDJSON_UINT64_C2(0xcdb02555, 0x653131b6), RAPIDJSON_UINT64_C2(0x993fe2c6, 0xd07b7fac),
181         RAPIDJSON_UINT64_C2(0xe45c10c4, 0x2a2b3b06), RAPIDJSON_UINT64_C2(0xaa242499, 0x697392d3),
182         RAPIDJSON_UINT64_C2(0xfd87b5f2, 0x8300ca0e), RAPIDJSON_UINT64_C2(0xbce50864, 0x92111aeb),
183         RAPIDJSON_UINT64_C2(0x8cbccc09, 0x6f5088cc), RAPIDJSON_UINT64_C2(0xd1b71758, 0xe219652c),
184         RAPIDJSON_UINT64_C2(0x9c400000, 0x00000000), RAPIDJSON_UINT64_C2(0xe8d4a510, 0x00000000),
185         RAPIDJSON_UINT64_C2(0xad78ebc5, 0xac620000), RAPIDJSON_UINT64_C2(0x813f3978, 0xf8940984),
186         RAPIDJSON_UINT64_C2(0xc097ce7b, 0xc90715b3), RAPIDJSON_UINT64_C2(0x8f7e32ce, 0x7bea5c70),
187         RAPIDJSON_UINT64_C2(0xd5d238a4, 0xabe98068), RAPIDJSON_UINT64_C2(0x9f4f2726, 0x179a2245),
188         RAPIDJSON_UINT64_C2(0xed63a231, 0xd4c4fb27), RAPIDJSON_UINT64_C2(0xb0de6538, 0x8cc8ada8),
189         RAPIDJSON_UINT64_C2(0x83c7088e, 0x1aab65db), RAPIDJSON_UINT64_C2(0xc45d1df9, 0x42711d9a),
190         RAPIDJSON_UINT64_C2(0x924d692c, 0xa61be758), RAPIDJSON_UINT64_C2(0xda01ee64, 0x1a708dea),
191         RAPIDJSON_UINT64_C2(0xa26da399, 0x9aef774a), RAPIDJSON_UINT64_C2(0xf209787b, 0xb47d6b85),
192         RAPIDJSON_UINT64_C2(0xb454e4a1, 0x79dd1877), RAPIDJSON_UINT64_C2(0x865b8692, 0x5b9bc5c2),
193         RAPIDJSON_UINT64_C2(0xc83553c5, 0xc8965d3d), RAPIDJSON_UINT64_C2(0x952ab45c, 0xfa97a0b3),
194         RAPIDJSON_UINT64_C2(0xde469fbd, 0x99a05fe3), RAPIDJSON_UINT64_C2(0xa59bc234, 0xdb398c25),
195         RAPIDJSON_UINT64_C2(0xf6c69a72, 0xa3989f5c), RAPIDJSON_UINT64_C2(0xb7dcbf53, 0x54e9bece),
196         RAPIDJSON_UINT64_C2(0x88fcf317, 0xf22241e2), RAPIDJSON_UINT64_C2(0xcc20ce9b, 0xd35c78a5),
197         RAPIDJSON_UINT64_C2(0x98165af3, 0x7b2153df), RAPIDJSON_UINT64_C2(0xe2a0b5dc, 0x971f303a),
198         RAPIDJSON_UINT64_C2(0xa8d9d153, 0x5ce3b396), RAPIDJSON_UINT64_C2(0xfb9b7cd9, 0xa4a7443c),
199         RAPIDJSON_UINT64_C2(0xbb764c4c, 0xa7a44410), RAPIDJSON_UINT64_C2(0x8bab8eef, 0xb6409c1a),
200         RAPIDJSON_UINT64_C2(0xd01fef10, 0xa657842c), RAPIDJSON_UINT64_C2(0x9b10a4e5, 0xe9913129),
201         RAPIDJSON_UINT64_C2(0xe7109bfb, 0xa19c0c9d), RAPIDJSON_UINT64_C2(0xac2820d9, 0x623bf429),
202         RAPIDJSON_UINT64_C2(0x80444b5e, 0x7aa7cf85), RAPIDJSON_UINT64_C2(0xbf21e440, 0x03acdd2d),
203         RAPIDJSON_UINT64_C2(0x8e679c2f, 0x5e44ff8f), RAPIDJSON_UINT64_C2(0xd433179d, 0x9c8cb841),
204         RAPIDJSON_UINT64_C2(0x9e19db92, 0xb4e31ba9), RAPIDJSON_UINT64_C2(0xeb96bf6e, 0xbadf77d9),
205         RAPIDJSON_UINT64_C2(0xaf87023b, 0x9bf0ee6b)
206     };
207     static const int16_t kCachedPowers_E[] = {
208         -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007,  -980,
209         -954,  -927,  -901,  -874,  -847,  -821,  -794,  -768,  -741,  -715,
210         -688,  -661,  -635,  -608,  -582,  -555,  -529,  -502,  -475,  -449,
211         -422,  -396,  -369,  -343,  -316,  -289,  -263,  -236,  -210,  -183,
212         -157,  -130,  -103,   -77,   -50,   -24,     3,    30,    56,    83,
213         109,   136,   162,   189,   216,   242,   269,   295,   322,   348,
214         375,   402,   428,   455,   481,   508,   534,   561,   588,   614,
215         641,   667,   694,   720,   747,   774,   800,   827,   853,   880,
216         907,   933,   960,   986,  1013,  1039,  1066
217     };
218     return DiyFp(kCachedPowers_F[index], kCachedPowers_E[index]);
219 }
220 
GetCachedPower(int e,int * K)221 inline DiyFp GetCachedPower(int e, int* K) {
222 
223     //int k = static_cast<int>(ceil((-61 - e) * 0.30102999566398114)) + 374;
224     double dk = (-61 - e) * 0.30102999566398114 + 347;  // dk must be positive, so can do ceiling in positive
225     int k = static_cast<int>(dk);
226     if (dk - k > 0.0)
227         k++;
228 
229     unsigned index = static_cast<unsigned>((k >> 3) + 1);
230     *K = -(-348 + static_cast<int>(index << 3));    // decimal exponent no need lookup table
231 
232     return GetCachedPowerByIndex(index);
233 }
234 
GetCachedPower10(int exp,int * outExp)235 inline DiyFp GetCachedPower10(int exp, int *outExp) {
236      unsigned index = (static_cast<unsigned>(exp) + 348u) / 8u;
237      *outExp = -348 + static_cast<int>(index) * 8;
238      return GetCachedPowerByIndex(index);
239  }
240 
241 #ifdef __GNUC__
242 RAPIDJSON_DIAG_POP
243 #endif
244 
245 } // namespace internal
246 RAPIDJSON_NAMESPACE_END
247 
248 #endif // RAPIDJSON_DIYFP_H_
249