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_DTOA_
 20#define RAPIDJSON_DTOA_
 21
 22#include "itoa.h" // GetDigitsLut()
 23#include "diyfp.h"
 24#include "ieee754.h"
 25
 26RAPIDJSON_NAMESPACE_BEGIN
 27namespace internal {
 28
 29#ifdef __GNUC__
 30RAPIDJSON_DIAG_PUSH
 31RAPIDJSON_DIAG_OFF(effc++)
 32RAPIDJSON_DIAG_OFF(array-bounds) // some gcc versions generate wrong warnings https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124
 33#endif
 34
 35inline void GrisuRound(char* buffer, int len, uint64_t delta, uint64_t rest, uint64_t ten_kappa, uint64_t wp_w) {
 36    while (rest < wp_w && delta - rest >= ten_kappa &&
 37           (rest + ten_kappa < wp_w ||  /// closer
 38            wp_w - rest > rest + ten_kappa - wp_w)) {
 39        buffer[len - 1]--;
 40        rest += ten_kappa;
 41    }
 42}
 43
 44inline unsigned CountDecimalDigit32(uint32_t n) {
 45    // Simple pure C++ implementation was faster than __builtin_clz version in this situation.
 46    if (n < 10) return 1;
 47    if (n < 100) return 2;
 48    if (n < 1000) return 3;
 49    if (n < 10000) return 4;
 50    if (n < 100000) return 5;
 51    if (n < 1000000) return 6;
 52    if (n < 10000000) return 7;
 53    if (n < 100000000) return 8;
 54    // Will not reach 10 digits in DigitGen()
 55    //if (n < 1000000000) return 9;
 56    //return 10;
 57    return 9;
 58}
 59
 60inline void DigitGen(const DiyFp& W, const DiyFp& Mp, uint64_t delta, char* buffer, int* len, int* K) {
 61    static const uint32_t kPow10[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
 62    const DiyFp one(uint64_t(1) << -Mp.e, Mp.e);
 63    const DiyFp wp_w = Mp - W;
 64    uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e);
 65    uint64_t p2 = Mp.f & (one.f - 1);
 66    unsigned kappa = CountDecimalDigit32(p1); // kappa in [0, 9]
 67    *len = 0;
 68
 69    while (kappa > 0) {
 70        uint32_t d = 0;
 71        switch (kappa) {
 72            case  9: d = p1 /  100000000; p1 %=  100000000; break;
 73            case  8: d = p1 /   10000000; p1 %=   10000000; break;
 74            case  7: d = p1 /    1000000; p1 %=    1000000; break;
 75            case  6: d = p1 /     100000; p1 %=     100000; break;
 76            case  5: d = p1 /      10000; p1 %=      10000; break;
 77            case  4: d = p1 /       1000; p1 %=       1000; break;
 78            case  3: d = p1 /        100; p1 %=        100; break;
 79            case  2: d = p1 /         10; p1 %=         10; break;
 80            case  1: d = p1;              p1 =           0; break;
 81            default:;
 82        }
 83        if (d || *len)
 84            buffer[(*len)++] = static_cast<char>('0' + static_cast<char>(d));
 85        kappa--;
 86        uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2;
 87        if (tmp <= delta) {
 88            *K += kappa;
 89            GrisuRound(buffer, *len, delta, tmp, static_cast<uint64_t>(kPow10[kappa]) << -one.e, wp_w.f);
 90            return;
 91        }
 92    }
 93
 94    // kappa = 0
 95    for (;;) {
 96        p2 *= 10;
 97        delta *= 10;
 98        char d = static_cast<char>(p2 >> -one.e);
 99        if (d || *len)
100            buffer[(*len)++] = static_cast<char>('0' + d);
101        p2 &= one.f - 1;
102        kappa--;
103        if (p2 < delta) {
104            *K += kappa;
105            int index = -static_cast<int>(kappa);
106            GrisuRound(buffer, *len, delta, p2, one.f, wp_w.f * (index < 9 ? kPow10[-static_cast<int>(kappa)] : 0));
107            return;
108        }
109    }
110}
111
112inline void Grisu2(double value, char* buffer, int* length, int* K) {
113    const DiyFp v(value);
114    DiyFp w_m, w_p;
115    v.NormalizedBoundaries(&w_m, &w_p);
116
117    const DiyFp c_mk = GetCachedPower(w_p.e, K);
118    const DiyFp W = v.Normalize() * c_mk;
119    DiyFp Wp = w_p * c_mk;
120    DiyFp Wm = w_m * c_mk;
121    Wm.f++;
122    Wp.f--;
123    DigitGen(W, Wp, Wp.f - Wm.f, buffer, length, K);
124}
125
126inline char* WriteExponent(int K, char* buffer) {
127    if (K < 0) {
128        *buffer++ = '-';
129        K = -K;
130    }
131
132    if (K >= 100) {
133        *buffer++ = static_cast<char>('0' + static_cast<char>(K / 100));
134        K %= 100;
135        const char* d = GetDigitsLut() + K * 2;
136        *buffer++ = d[0];
137        *buffer++ = d[1];
138    }
139    else if (K >= 10) {
140        const char* d = GetDigitsLut() + K * 2;
141        *buffer++ = d[0];
142        *buffer++ = d[1];
143    }
144    else
145        *buffer++ = static_cast<char>('0' + static_cast<char>(K));
146
147    return buffer;
148}
149
150inline char* Prettify(char* buffer, int length, int k, int maxDecimalPlaces) {
151    const int kk = length + k;  // 10^(kk-1) <= v < 10^kk
152
153    if (0 <= k && kk <= 21) {
154        // 1234e7 -> 12340000000
155        for (int i = length; i < kk; i++)
156            buffer[i] = '0';
157        buffer[kk] = '.';
158        buffer[kk + 1] = '0';
159        return &buffer[kk + 2];
160    }
161    else if (0 < kk && kk <= 21) {
162        // 1234e-2 -> 12.34
163        std::memmove(&buffer[kk + 1], &buffer[kk], static_cast<size_t>(length - kk));
164        buffer[kk] = '.';
165        if (0 > k + maxDecimalPlaces) {
166            // When maxDecimalPlaces = 2, 1.2345 -> 1.23, 1.102 -> 1.1
167            // Remove extra trailing zeros (at least one) after truncation.
168            for (int i = kk + maxDecimalPlaces; i > kk + 1; i--)
169                if (buffer[i] != '0')
170                    return &buffer[i + 1];
171            return &buffer[kk + 2]; // Reserve one zero
172        }
173        else
174            return &buffer[length + 1];
175    }
176    else if (-6 < kk && kk <= 0) {
177        // 1234e-6 -> 0.001234
178        const int offset = 2 - kk;
179        std::memmove(&buffer[offset], &buffer[0], static_cast<size_t>(length));
180        buffer[0] = '0';
181        buffer[1] = '.';
182        for (int i = 2; i < offset; i++)
183            buffer[i] = '0';
184        if (length - kk > maxDecimalPlaces) {
185            // When maxDecimalPlaces = 2, 0.123 -> 0.12, 0.102 -> 0.1
186            // Remove extra trailing zeros (at least one) after truncation.
187            for (int i = maxDecimalPlaces + 1; i > 2; i--)
188                if (buffer[i] != '0')
189                    return &buffer[i + 1];
190            return &buffer[3]; // Reserve one zero
191        }
192        else
193            return &buffer[length + offset];
194    }
195    else if (kk < -maxDecimalPlaces) {
196        // Truncate to zero
197        buffer[0] = '0';
198        buffer[1] = '.';
199        buffer[2] = '0';
200        return &buffer[3];
201    }
202    else if (length == 1) {
203        // 1e30
204        buffer[1] = 'e';
205        return WriteExponent(kk - 1, &buffer[2]);
206    }
207    else {
208        // 1234e30 -> 1.234e33
209        std::memmove(&buffer[2], &buffer[1], static_cast<size_t>(length - 1));
210        buffer[1] = '.';
211        buffer[length + 1] = 'e';
212        return WriteExponent(kk - 1, &buffer[0 + length + 2]);
213    }
214}
215
216inline char* dtoa(double value, char* buffer, int maxDecimalPlaces = 324) {
217    RAPIDJSON_ASSERT(maxDecimalPlaces >= 1);
218    Double d(value);
219    if (d.IsZero()) {
220        if (d.Sign())
221            *buffer++ = '-';     // -0.0, Issue #289
222        buffer[0] = '0';
223        buffer[1] = '.';
224        buffer[2] = '0';
225        return &buffer[3];
226    }
227    else {
228        if (value < 0) {
229            *buffer++ = '-';
230            value = -value;
231        }
232        int length, K;
233        Grisu2(value, buffer, &length, &K);
234        return Prettify(buffer, length, K, maxDecimalPlaces);
235    }
236}
237
238#ifdef __GNUC__
239RAPIDJSON_DIAG_POP
240#endif
241
242} // namespace internal
243RAPIDJSON_NAMESPACE_END
244
245#endif // RAPIDJSON_DTOA_