dtoa.h
Engine/source/persistence/rapidjson/internal/dtoa.h
Namespaces:
namespace
Detailed Description
1 2// Tencent is pleased to support the open source community by making RapidJSON available. 3// 4// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. 5// 6// Licensed under the MIT License (the "License"); you may not use this file except 7// in compliance with the License. You may obtain a copy of the License at 8// 9// http://opensource.org/licenses/MIT 10// 11// Unless required by applicable law or agreed to in writing, software distributed 12// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 13// CONDITIONS OF ANY KIND, either express or implied. See the License for the 14// specific language governing permissions and limitations under the License. 15 16// This is a C++ header-only implementation of Grisu2 algorithm from the publication: 17// Loitsch, Florian. "Printing floating-point numbers quickly and accurately with 18// integers." ACM Sigplan Notices 45.6 (2010): 233-243. 19 20#ifndef RAPIDJSON_DTOA_ 21#define RAPIDJSON_DTOA_ 22 23#include "itoa.h" // GetDigitsLut() 24#include "diyfp.h" 25#include "ieee754.h" 26 27RAPIDJSON_NAMESPACE_BEGIN 28namespace internal { 29 30#ifdef __GNUC__ 31RAPIDJSON_DIAG_PUSH 32RAPIDJSON_DIAG_OFF(effc++) 33RAPIDJSON_DIAG_OFF(array-bounds) // some gcc versions generate wrong warnings https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124 34#endif 35 36inline void GrisuRound(char* buffer, int len, uint64_t delta, uint64_t rest, uint64_t ten_kappa, uint64_t wp_w) { 37 while (rest < wp_w && delta - rest >= ten_kappa && 38 (rest + ten_kappa < wp_w || /// closer 39 wp_w - rest > rest + ten_kappa - wp_w)) { 40 buffer[len - 1]--; 41 rest += ten_kappa; 42 } 43} 44 45inline int CountDecimalDigit32(uint32_t n) { 46 // Simple pure C++ implementation was faster than __builtin_clz version in this situation. 47 if (n < 10) return 1; 48 if (n < 100) return 2; 49 if (n < 1000) return 3; 50 if (n < 10000) return 4; 51 if (n < 100000) return 5; 52 if (n < 1000000) return 6; 53 if (n < 10000000) return 7; 54 if (n < 100000000) return 8; 55 // Will not reach 10 digits in DigitGen() 56 //if (n < 1000000000) return 9; 57 //return 10; 58 return 9; 59} 60 61inline void DigitGen(const DiyFp& W, const DiyFp& Mp, uint64_t delta, char* buffer, int* len, int* K) { 62 static const uint32_t kPow10[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; 63 const DiyFp one(uint64_t(1) << -Mp.e, Mp.e); 64 const DiyFp wp_w = Mp - W; 65 uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e); 66 uint64_t p2 = Mp.f & (one.f - 1); 67 int kappa = CountDecimalDigit32(p1); // kappa in [0, 9] 68 *len = 0; 69 70 while (kappa > 0) { 71 uint32_t d = 0; 72 switch (kappa) { 73 case 9: d = p1 / 100000000; p1 %= 100000000; break; 74 case 8: d = p1 / 10000000; p1 %= 10000000; break; 75 case 7: d = p1 / 1000000; p1 %= 1000000; break; 76 case 6: d = p1 / 100000; p1 %= 100000; break; 77 case 5: d = p1 / 10000; p1 %= 10000; break; 78 case 4: d = p1 / 1000; p1 %= 1000; break; 79 case 3: d = p1 / 100; p1 %= 100; break; 80 case 2: d = p1 / 10; p1 %= 10; break; 81 case 1: d = p1; p1 = 0; break; 82 default:; 83 } 84 if (d || *len) 85 buffer[(*len)++] = static_cast<char>('0' + static_cast<char>(d)); 86 kappa--; 87 uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2; 88 if (tmp <= delta) { 89 *K += kappa; 90 GrisuRound(buffer, *len, delta, tmp, static_cast<uint64_t>(kPow10[kappa]) << -one.e, wp_w.f); 91 return; 92 } 93 } 94 95 // kappa = 0 96 for (;;) { 97 p2 *= 10; 98 delta *= 10; 99 char d = static_cast<char>(p2 >> -one.e); 100 if (d || *len) 101 buffer[(*len)++] = static_cast<char>('0' + d); 102 p2 &= one.f - 1; 103 kappa--; 104 if (p2 < delta) { 105 *K += kappa; 106 int index = -kappa; 107 GrisuRound(buffer, *len, delta, p2, one.f, wp_w.f * (index < 9 ? kPow10[index] : 0)); 108 return; 109 } 110 } 111} 112 113inline void Grisu2(double value, char* buffer, int* length, int* K) { 114 const DiyFp v(value); 115 DiyFp w_m, w_p; 116 v.NormalizedBoundaries(&w_m, &w_p); 117 118 const DiyFp c_mk = GetCachedPower(w_p.e, K); 119 const DiyFp W = v.Normalize() * c_mk; 120 DiyFp Wp = w_p * c_mk; 121 DiyFp Wm = w_m * c_mk; 122 Wm.f++; 123 Wp.f--; 124 DigitGen(W, Wp, Wp.f - Wm.f, buffer, length, K); 125} 126 127inline char* WriteExponent(int K, char* buffer) { 128 if (K < 0) { 129 *buffer++ = '-'; 130 K = -K; 131 } 132 133 if (K >= 100) { 134 *buffer++ = static_cast<char>('0' + static_cast<char>(K / 100)); 135 K %= 100; 136 const char* d = GetDigitsLut() + K * 2; 137 *buffer++ = d[0]; 138 *buffer++ = d[1]; 139 } 140 else if (K >= 10) { 141 const char* d = GetDigitsLut() + K * 2; 142 *buffer++ = d[0]; 143 *buffer++ = d[1]; 144 } 145 else 146 *buffer++ = static_cast<char>('0' + static_cast<char>(K)); 147 148 return buffer; 149} 150 151inline char* Prettify(char* buffer, int length, int k, int maxDecimalPlaces) { 152 const int kk = length + k; // 10^(kk-1) <= v < 10^kk 153 154 if (0 <= k && kk <= 21) { 155 // 1234e7 -> 12340000000 156 for (int i = length; i < kk; i++) 157 buffer[i] = '0'; 158 buffer[kk] = '.'; 159 buffer[kk + 1] = '0'; 160 return &buffer[kk + 2]; 161 } 162 else if (0 < kk && kk <= 21) { 163 // 1234e-2 -> 12.34 164 std::memmove(&buffer[kk + 1], &buffer[kk], static_cast<size_t>(length - kk)); 165 buffer[kk] = '.'; 166 if (0 > k + maxDecimalPlaces) { 167 // When maxDecimalPlaces = 2, 1.2345 -> 1.23, 1.102 -> 1.1 168 // Remove extra trailing zeros (at least one) after truncation. 169 for (int i = kk + maxDecimalPlaces; i > kk + 1; i--) 170 if (buffer[i] != '0') 171 return &buffer[i + 1]; 172 return &buffer[kk + 2]; // Reserve one zero 173 } 174 else 175 return &buffer[length + 1]; 176 } 177 else if (-6 < kk && kk <= 0) { 178 // 1234e-6 -> 0.001234 179 const int offset = 2 - kk; 180 std::memmove(&buffer[offset], &buffer[0], static_cast<size_t>(length)); 181 buffer[0] = '0'; 182 buffer[1] = '.'; 183 for (int i = 2; i < offset; i++) 184 buffer[i] = '0'; 185 if (length - kk > maxDecimalPlaces) { 186 // When maxDecimalPlaces = 2, 0.123 -> 0.12, 0.102 -> 0.1 187 // Remove extra trailing zeros (at least one) after truncation. 188 for (int i = maxDecimalPlaces + 1; i > 2; i--) 189 if (buffer[i] != '0') 190 return &buffer[i + 1]; 191 return &buffer[3]; // Reserve one zero 192 } 193 else 194 return &buffer[length + offset]; 195 } 196 else if (kk < -maxDecimalPlaces) { 197 // Truncate to zero 198 buffer[0] = '0'; 199 buffer[1] = '.'; 200 buffer[2] = '0'; 201 return &buffer[3]; 202 } 203 else if (length == 1) { 204 // 1e30 205 buffer[1] = 'e'; 206 return WriteExponent(kk - 1, &buffer[2]); 207 } 208 else { 209 // 1234e30 -> 1.234e33 210 std::memmove(&buffer[2], &buffer[1], static_cast<size_t>(length - 1)); 211 buffer[1] = '.'; 212 buffer[length + 1] = 'e'; 213 return WriteExponent(kk - 1, &buffer[0 + length + 2]); 214 } 215} 216 217inline char* dtoa(double value, char* buffer, int maxDecimalPlaces = 324) { 218 RAPIDJSON_ASSERT(maxDecimalPlaces >= 1); 219 Double d(value); 220 if (d.IsZero()) { 221 if (d.Sign()) 222 *buffer++ = '-'; // -0.0, Issue #289 223 buffer[0] = '0'; 224 buffer[1] = '.'; 225 buffer[2] = '0'; 226 return &buffer[3]; 227 } 228 else { 229 if (value < 0) { 230 *buffer++ = '-'; 231 value = -value; 232 } 233 int length, K; 234 Grisu2(value, buffer, &length, &K); 235 return Prettify(buffer, length, K, maxDecimalPlaces); 236 } 237} 238 239#ifdef __GNUC__ 240RAPIDJSON_DIAG_POP 241#endif 242 243} // namespace internal 244RAPIDJSON_NAMESPACE_END 245 246#endif // RAPIDJSON_DTOA_ 247