1/*
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "ecmascript/base/dtoa_helper.h"
17#include "ecmascript/base/number_helper.h"
18
19#ifndef UINT64_C2
20#define UINT64_C2(high32, low32) ((static_cast<uint64_t>(high32) << 32) | static_cast<uint64_t>(low32))
21#endif
22namespace panda::ecmascript::base {
23DtoaHelper::DiyFp DtoaHelper::GetCachedPowerByIndex(size_t index)
24{
25    // 10^-348, 10^-340, ..., 10^340
26    static const uint64_t kCachedPowers_F[] = {
27        UINT64_C2(0xfa8fd5a0, 0x081c0288), UINT64_C2(0xbaaee17f, 0xa23ebf76), UINT64_C2(0x8b16fb20, 0x3055ac76),
28        UINT64_C2(0xcf42894a, 0x5dce35ea), UINT64_C2(0x9a6bb0aa, 0x55653b2d), UINT64_C2(0xe61acf03, 0x3d1a45df),
29        UINT64_C2(0xab70fe17, 0xc79ac6ca), UINT64_C2(0xff77b1fc, 0xbebcdc4f), UINT64_C2(0xbe5691ef, 0x416bd60c),
30        UINT64_C2(0x8dd01fad, 0x907ffc3c), UINT64_C2(0xd3515c28, 0x31559a83), UINT64_C2(0x9d71ac8f, 0xada6c9b5),
31        UINT64_C2(0xea9c2277, 0x23ee8bcb), UINT64_C2(0xaecc4991, 0x4078536d), UINT64_C2(0x823c1279, 0x5db6ce57),
32        UINT64_C2(0xc2109436, 0x4dfb5637), UINT64_C2(0x9096ea6f, 0x3848984f), UINT64_C2(0xd77485cb, 0x25823ac7),
33        UINT64_C2(0xa086cfcd, 0x97bf97f4), UINT64_C2(0xef340a98, 0x172aace5), UINT64_C2(0xb23867fb, 0x2a35b28e),
34        UINT64_C2(0x84c8d4df, 0xd2c63f3b), UINT64_C2(0xc5dd4427, 0x1ad3cdba), UINT64_C2(0x936b9fce, 0xbb25c996),
35        UINT64_C2(0xdbac6c24, 0x7d62a584), UINT64_C2(0xa3ab6658, 0x0d5fdaf6), UINT64_C2(0xf3e2f893, 0xdec3f126),
36        UINT64_C2(0xb5b5ada8, 0xaaff80b8), UINT64_C2(0x87625f05, 0x6c7c4a8b), UINT64_C2(0xc9bcff60, 0x34c13053),
37        UINT64_C2(0x964e858c, 0x91ba2655), UINT64_C2(0xdff97724, 0x70297ebd), UINT64_C2(0xa6dfbd9f, 0xb8e5b88f),
38        UINT64_C2(0xf8a95fcf, 0x88747d94), UINT64_C2(0xb9447093, 0x8fa89bcf), UINT64_C2(0x8a08f0f8, 0xbf0f156b),
39        UINT64_C2(0xcdb02555, 0x653131b6), UINT64_C2(0x993fe2c6, 0xd07b7fac), UINT64_C2(0xe45c10c4, 0x2a2b3b06),
40        UINT64_C2(0xaa242499, 0x697392d3), UINT64_C2(0xfd87b5f2, 0x8300ca0e), UINT64_C2(0xbce50864, 0x92111aeb),
41        UINT64_C2(0x8cbccc09, 0x6f5088cc), UINT64_C2(0xd1b71758, 0xe219652c), UINT64_C2(0x9c400000, 0x00000000),
42        UINT64_C2(0xe8d4a510, 0x00000000), UINT64_C2(0xad78ebc5, 0xac620000), UINT64_C2(0x813f3978, 0xf8940984),
43        UINT64_C2(0xc097ce7b, 0xc90715b3), UINT64_C2(0x8f7e32ce, 0x7bea5c70), UINT64_C2(0xd5d238a4, 0xabe98068),
44        UINT64_C2(0x9f4f2726, 0x179a2245), UINT64_C2(0xed63a231, 0xd4c4fb27), UINT64_C2(0xb0de6538, 0x8cc8ada8),
45        UINT64_C2(0x83c7088e, 0x1aab65db), UINT64_C2(0xc45d1df9, 0x42711d9a), UINT64_C2(0x924d692c, 0xa61be758),
46        UINT64_C2(0xda01ee64, 0x1a708dea), UINT64_C2(0xa26da399, 0x9aef774a), UINT64_C2(0xf209787b, 0xb47d6b85),
47        UINT64_C2(0xb454e4a1, 0x79dd1877), UINT64_C2(0x865b8692, 0x5b9bc5c2), UINT64_C2(0xc83553c5, 0xc8965d3d),
48        UINT64_C2(0x952ab45c, 0xfa97a0b3), UINT64_C2(0xde469fbd, 0x99a05fe3), UINT64_C2(0xa59bc234, 0xdb398c25),
49        UINT64_C2(0xf6c69a72, 0xa3989f5c), UINT64_C2(0xb7dcbf53, 0x54e9bece), UINT64_C2(0x88fcf317, 0xf22241e2),
50        UINT64_C2(0xcc20ce9b, 0xd35c78a5), UINT64_C2(0x98165af3, 0x7b2153df), UINT64_C2(0xe2a0b5dc, 0x971f303a),
51        UINT64_C2(0xa8d9d153, 0x5ce3b396), UINT64_C2(0xfb9b7cd9, 0xa4a7443c), UINT64_C2(0xbb764c4c, 0xa7a44410),
52        UINT64_C2(0x8bab8eef, 0xb6409c1a), UINT64_C2(0xd01fef10, 0xa657842c), UINT64_C2(0x9b10a4e5, 0xe9913129),
53        UINT64_C2(0xe7109bfb, 0xa19c0c9d), UINT64_C2(0xac2820d9, 0x623bf429), UINT64_C2(0x80444b5e, 0x7aa7cf85),
54        UINT64_C2(0xbf21e440, 0x03acdd2d), UINT64_C2(0x8e679c2f, 0x5e44ff8f), UINT64_C2(0xd433179d, 0x9c8cb841),
55        UINT64_C2(0x9e19db92, 0xb4e31ba9), UINT64_C2(0xeb96bf6e, 0xbadf77d9), UINT64_C2(0xaf87023b, 0x9bf0ee6b)};
56    static const int16_t kCachedPowers_E[] = {
57        -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007, -980, -954, -927, -901, -874, -847,
58        -821,  -794,  -768,  -741,  -715,  -688,  -661,  -635,  -608,  -582, -555, -529, -502, -475, -449,
59        -422,  -396,  -369,  -343,  -316,  -289,  -263,  -236,  -210,  -183, -157, -130, -103, -77,  -50,
60        -24,   3,     30,    56,    83,    109,   136,   162,   189,   216,  242,  269,  295,  322,  348,
61        375,   402,   428,   455,   481,   508,   534,   561,   588,   614,  641,  667,  694,  720,  747,
62        774,   800,   827,   853,   880,   907,   933,   960,   986,   1013, 1039, 1066};
63    return DtoaHelper::DiyFp(kCachedPowers_F[index], kCachedPowers_E[index]);
64}
65
66void DtoaHelper::GrisuRound(char *buffer, int len, uint64_t delta, uint64_t rest, uint64_t tenKappa, uint64_t distance)
67{
68    while (rest < distance && delta - rest >= tenKappa &&
69        (rest + tenKappa < distance || distance - rest > rest + tenKappa - distance)) {
70        buffer[len - 1]--;
71        rest += tenKappa;
72    }
73}
74
75int DtoaHelper::CountDecimalDigit32(uint32_t n)
76{
77    if (n < TEN) {
78        return 1; // 1: means the decimal digit
79    } else if (n < TEN2POW) {
80        return 2; // 2: means the decimal digit
81    } else if (n < TEN3POW) {
82        return 3; // 3: means the decimal digit
83    } else if (n < TEN4POW) {
84        return 4; // 4: means the decimal digit
85    } else if (n < TEN5POW) {
86        return 5; // 5: means the decimal digit
87    } else if (n < TEN6POW) {
88        return 6; // 6: means the decimal digit
89    } else if (n < TEN7POW) {
90        return 7; // 7: means the decimal digit
91    } else if (n < TEN8POW) {
92        return 8; // 8: means the decimal digit
93    } else {
94        return 9; // 9: means the decimal digit
95    }
96}
97
98void DtoaHelper::DigitGen(const DiyFp &W, const DiyFp &Mp, uint64_t delta, char *buffer, int *len, int *K)
99{
100    const DiyFp one(uint64_t(1) << -Mp.e, Mp.e);
101    const DiyFp distance = Mp - W;
102    uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e);
103    ASSERT(one.f > 0);
104    uint64_t p2 = Mp.f & (one.f - 1);
105    int kappa = CountDecimalDigit32(p1); // kappa in [0, 9]
106    int localLen = 0;
107    while (kappa > 0) {
108        uint32_t d = 0;
109        switch (kappa) {
110            case 9: // 9: means the decimal digit
111                d = p1 / TEN8POW;
112                p1 %= TEN8POW;
113                break;
114            case 8: // 8: means the decimal digit
115                d = p1 / TEN7POW;
116                p1 %= TEN7POW;
117                break;
118            case 7: // 7: means the decimal digit
119                d = p1 / TEN6POW;
120                p1 %= TEN6POW;
121                break;
122            case 6: // 6: means the decimal digit
123                d = p1 / TEN5POW;
124                p1 %= TEN5POW;
125                break;
126            case 5: // 5: means the decimal digit
127                d = p1 / TEN4POW;
128                p1 %= TEN4POW;
129                break;
130            case 4: // 4: means the decimal digit
131                d = p1 / TEN3POW;
132                p1 %= TEN3POW;
133                break;
134            case 3: // 3: means the decimal digit
135                d = p1 / TEN2POW;
136                p1 %= TEN2POW;
137                break;
138            case 2: // 2: means the decimal digit
139                d = p1 / TEN;
140                p1 %= TEN;
141                break;
142            case 1: // 1: means the decimal digit
143                d = p1;
144                p1 = 0;
145                break;
146            default:;
147        }
148        if (d || localLen) {
149            buffer[localLen++] = static_cast<char>('0' + static_cast<char>(d));
150        }
151        kappa--;
152        uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2;
153        if (tmp <= delta) {
154            *K += kappa;
155            GrisuRound(buffer, localLen, delta, tmp, POW10[kappa] << -one.e, distance.f);
156            *len = localLen;
157            return;
158        }
159    }
160
161    // kappa = 0
162    for (;;) {
163        p2 *= TEN;
164        delta *= TEN;
165        char d = static_cast<char>(p2 >> -one.e);
166        if (d || localLen) {
167            buffer[localLen++] = static_cast<char>('0' + d);
168        }
169        ASSERT(one.f > 0);
170        p2 &= one.f - 1;
171        kappa--;
172        if (p2 < delta) {
173            *K += kappa;
174            int index = -kappa;
175            if (index < kIndex) {
176                GrisuRound(buffer, localLen, delta, p2, one.f, distance.f * POW10[index]);
177            }
178            *len = localLen;
179            return;
180        }
181    }
182}
183
184// Grisu2 algorithm use the extra capacity of the used integer type to shorten the produced output
185void DtoaHelper::Grisu(double value, char *buffer, int *length, int *K)
186{
187    const DiyFp v(value);
188    DiyFp mMinus;
189    DiyFp mPlus;
190    v.NormalizedBoundaries(&mMinus, &mPlus);
191
192    const DiyFp cached = GetCachedPower(mPlus.e, K);
193    const DiyFp W = v.Normalize() * cached;
194    DiyFp wPlus = mPlus * cached;
195    DiyFp wMinus = mMinus * cached;
196    wMinus.f++;
197    wPlus.f--;
198    DigitGen(W, wPlus, wPlus.f - wMinus.f, buffer, length, K);
199}
200
201void DtoaHelper::Dtoa(double value, char *buffer, int *point, int *length)
202{
203    // Exceptional case such as NAN, 0.0, negative... are processed in DoubleToEcmaString
204    // So use Dtoa should avoid Exceptional case.
205    ASSERT(value > 0);
206    int k;
207    Grisu(value, buffer, length, &k);
208    *point = *length + k;
209}
210
211void DtoaHelper::FillDigits32FixedLength(uint32_t number, int requested_length,
212                                         BufferVector<char> buffer, int* length)
213{
214    for (int i = requested_length - 1; i >= 0; --i) {
215        buffer[(*length) + i] = '0' + number % TEN;
216        number /= TEN;
217    }
218    *length += requested_length;
219}
220
221void DtoaHelper::FillDigits32(uint32_t number, BufferVector<char> buffer, int* length)
222{
223    int number_length = 0;
224    // We fill the digits in reverse order and exchange them afterwards.
225    while (number != 0) {
226        int digit = static_cast<int>(number % TEN);
227        number /= TEN;
228        buffer[(*length) + number_length] = '0' + digit;
229        number_length++;
230    }
231    // Exchange the digits.
232    int i = *length;
233    int j = *length + number_length - 1;
234    while (i < j) {
235        char tmp = buffer[i];
236        buffer[i] = buffer[j];
237        buffer[j] = tmp;
238        i++;
239        j--;
240    }
241    *length += number_length;
242}
243
244void DtoaHelper::FillDigits64FixedLength(uint64_t number, [[maybe_unused]] int requested_length,
245                                         BufferVector<char> buffer, int* length)
246{
247    // For efficiency cut the number into 3 uint32_t parts, and print those.
248    uint32_t part2 = static_cast<uint32_t>(number % TEN7POW);
249    number /= TEN7POW;
250    uint32_t part1 = static_cast<uint32_t>(number % TEN7POW);
251    uint32_t part0 = static_cast<uint32_t>(number / TEN7POW);
252    FillDigits32FixedLength(part0, 3, buffer, length); // 3: parameter
253    FillDigits32FixedLength(part1, 7, buffer, length); // 7: parameter
254    FillDigits32FixedLength(part2, 7, buffer, length); // 7: parameter
255}
256
257void DtoaHelper::FillDigits64(uint64_t number, BufferVector<char> buffer, int* length)
258{
259    // For efficiency cut the number into 3 uint32_t parts, and print those.
260    uint32_t part2 = static_cast<uint32_t>(number % TEN7POW);
261    number /= TEN7POW;
262    uint32_t part1 = static_cast<uint32_t>(number % TEN7POW);
263    uint32_t part0 = static_cast<uint32_t>(number / TEN7POW);
264    if (part0 != 0) {
265        FillDigits32(part0, buffer, length);
266        FillDigits32FixedLength(part1, 7, buffer, length); // 7: means the decimal digit
267        FillDigits32FixedLength(part2, 7, buffer, length); // 7: means the decimal digit
268    } else if (part1 != 0) {
269        FillDigits32(part1, buffer, length);
270        FillDigits32FixedLength(part2, 7, buffer, length); // 7: means the decimal digit
271    } else {
272        FillDigits32(part2, buffer, length);
273    }
274}
275
276void DtoaHelper::RoundUp(BufferVector<char> buffer, int* length, int* decimal_point)
277{
278    // An empty buffer represents 0.
279    if (*length == 0) {
280        buffer[0] = '1';
281        *decimal_point = 1;
282        *length = 1;
283        return;
284    }
285    buffer[(*length) - 1]++;
286    for (int i = (*length) - 1; i > 0; --i) {
287        if (buffer[i] != '0' + 10) { // 10: means the decimal digit
288            return;
289        }
290        buffer[i] = '0';
291        buffer[i - 1]++;
292    }
293    if (buffer[0] == '0' + 10) { // 10: means the decimal digit
294        buffer[0] = '1';
295        (*decimal_point)++;
296    }
297}
298
299void DtoaHelper::FillFractionals(uint64_t fractionals, int exponent, int fractional_count,
300                                 BufferVector<char> buffer, int* length, int* decimal_point)
301{
302    ASSERT(NEGATIVE_128BIT <= exponent && exponent <= 0);
303    // 'fractionals' is a fixed-point number, with binary point at bit
304    // (-exponent). Inside the function the non-converted remainder of fractionals
305    // is a fixed-point number, with binary point at bit 'point'.
306    if (-exponent <= EXPONENT_64) {
307        // One 64 bit number is sufficient.
308        ASSERT((fractionals >> 56) == 0); // 56: parameter
309        int point = -exponent;
310        for (int i = 0; i < fractional_count; ++i) {
311            if (fractionals == 0) break;
312            fractionals *= 5; // 5: parameter
313            point--;
314            int digit = static_cast<int>(fractionals >> point);
315            buffer[*length] = '0' + digit;
316            (*length)++;
317            fractionals -= static_cast<uint64_t>(digit) << point;
318        }
319        // If the first bit after the point is set we have to round up.
320        if (point > 0 && ((fractionals >> (point - 1)) & 1) == 1) {
321            RoundUp(buffer, length, decimal_point);
322        }
323    } else {  // We need 128 bits.
324        ASSERT(EXPONENT_64 < -exponent && -exponent <= EXPONENT_128);
325        UInt128 fractionals128 = UInt128(fractionals, 0);
326        fractionals128.Shift(-exponent - EXPONENT_64);
327        int point = 128;
328        for (int i = 0; i < fractional_count; ++i) {
329            if (fractionals128.IsZero()) break;
330            // As before: instead of multiplying by 10 we multiply by 5 and adjust the
331            // point location.
332            // This multiplication will not overflow for the same reasons as before.
333            fractionals128.Multiply(5); // 5: parameter
334            point--;
335            int digit = fractionals128.DivModPowerOf2(point);
336            buffer[*length] = '0' + digit;
337            (*length)++;
338        }
339        if (fractionals128.BitAt(point - 1) == 1) {
340            RoundUp(buffer, length, decimal_point);
341        }
342    }
343}
344
345// Removes leading and trailing zeros.
346// If leading zeros are removed then the decimal point position is adjusted.
347void DtoaHelper::TrimZeros(BufferVector<char> buffer, int* length, int* decimal_point)
348{
349    while (*length > 0 && buffer[(*length) - 1] == '0') {
350        (*length)--;
351    }
352    int first_non_zero = 0;
353    while (first_non_zero < *length && buffer[first_non_zero] == '0') {
354        first_non_zero++;
355    }
356    if (first_non_zero != 0) {
357        for (int i = first_non_zero; i < *length; ++i) {
358            buffer[i - first_non_zero] = buffer[i];
359        }
360        *length -= first_non_zero;
361        *decimal_point -= first_non_zero;
362    }
363}
364
365bool DtoaHelper::FixedDtoa(double v, int fractional_count, BufferVector<char> buffer,
366                           int* length, int* decimal_point)
367{
368    if (v == 0) {
369        buffer[0] = '0';
370        buffer[1] = '\0';
371        *length = 1;
372        *decimal_point = 1;
373        return true;
374    }
375    uint64_t significand = NumberHelper::Significand(v);
376    int exponent = NumberHelper::Exponent(v);
377    if (exponent > 20) return false; // 20: max parameter
378    if (fractional_count > 20) return false; // 20: max parameter
379    *length = 0;
380    if (exponent + kDoubleSignificandSize > EXPONENT_64) {
381        const uint64_t kFive17 = 0xB1'A2BC'2EC5;  // 5^17
382        uint64_t divisor = kFive17;
383        int divisor_power = 17;
384        uint64_t dividend = significand;
385        uint32_t quotient;
386        uint64_t remainder;
387        if (exponent > divisor_power) {
388            // We only allow exponents of up to 20 and therefore (17 - e) <= 3
389            dividend <<= exponent - divisor_power;
390            quotient = static_cast<uint32_t>(dividend / divisor);
391            remainder = (dividend % divisor) << divisor_power;
392        } else {
393            divisor <<= divisor_power - exponent;
394            quotient = static_cast<uint32_t>(dividend / divisor);
395            remainder = (dividend % divisor) << exponent;
396        }
397        FillDigits32(quotient, buffer, length);
398        FillDigits64FixedLength(remainder, divisor_power, buffer, length);
399        *decimal_point = *length;
400    } else if (exponent >= 0) {
401        // 0 <= exponent <= 11
402        significand <<= exponent;
403        FillDigits64(significand, buffer, length);
404        *decimal_point = *length;
405    } else if (exponent > -kDoubleSignificandSize) {
406        // We have to cut the number.
407        uint64_t integrals = significand >> -exponent;
408        uint64_t fractionals = significand - (integrals << -exponent);
409        if (integrals > kMaxUInt32) {
410            FillDigits64(integrals, buffer, length);
411        } else {
412            FillDigits32(static_cast<uint32_t>(integrals), buffer, length);
413        }
414        *decimal_point = *length;
415        FillFractionals(fractionals, exponent, fractional_count,
416                        buffer, length, decimal_point);
417    } else if (exponent < NEGATIVE_128BIT) {
418        ASSERT(fractional_count <= 20); // 20: parameter
419        buffer[0] = '\0';
420        *length = 0;
421        *decimal_point = -fractional_count;
422    } else {
423        *decimal_point = 0;
424        FillFractionals(significand, exponent, fractional_count,
425                        buffer, length, decimal_point);
426    }
427    TrimZeros(buffer, length, decimal_point);
428    buffer[*length] = '\0';
429    if ((*length) == 0) {
430        *decimal_point = -fractional_count;
431    }
432    return true;
433}
434}
435