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#ifndef ECMASCRIPT_BASE_DTOA_HELPER_H
17#define ECMASCRIPT_BASE_DTOA_HELPER_H
18
19#include <math.h>
20#include <stdint.h>
21#include <stdint.h>
22#include <limits>
23
24#include "ecmascript/common.h"
25
26namespace panda::ecmascript::base {
27
28template <typename T>
29class BufferVector {
30public:
31    BufferVector() : start_(NULL), length_(0) {}
32    BufferVector(T* data, int length) : start_(data), length_(length)
33    {
34        ASSERT(length == 0 || (length > 0 && data != NULL));
35    }
36    int length() const { return length_; }
37    T* start() const { return start_; }
38
39    // Access individual vector elements - checks bounds in debug mode.
40    T& operator[](int index) const
41    {
42        ASSERT(0 <= index && index < length_);
43        return start_[index];
44    }
45
46    T& first() { return start_[0]; }
47
48    T& last() { return start_[length_ - 1]; }
49
50private:
51    T* start_;
52    int length_;
53};
54
55class UInt128 {
56public:
57    UInt128() : high_bits_(0), low_bits_(0) { }
58    UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { }
59
60    static constexpr int SHIFT_32BIT = 32;
61    static constexpr int SHIFT_64BIT = 64;
62    static constexpr int NEGATIVE_64BIT = -64;
63
64    void Multiply(uint32_t multiplicand)
65    {
66        uint64_t accumulator = (low_bits_ & kMask32) * multiplicand;
67        uint32_t part = static_cast<uint32_t>(accumulator & kMask32);
68        accumulator >>= SHIFT_32BIT;
69        accumulator = accumulator + (low_bits_ >> SHIFT_32BIT) * multiplicand;
70        low_bits_ = (accumulator << SHIFT_32BIT) + part;
71        accumulator >>= SHIFT_32BIT;
72        accumulator = accumulator + (high_bits_ & kMask32) * multiplicand;
73        part = static_cast<uint32_t>(accumulator & kMask32);
74        accumulator >>= SHIFT_32BIT;
75        accumulator = accumulator + (high_bits_ >> SHIFT_32BIT) * multiplicand;
76        high_bits_ = (accumulator << SHIFT_32BIT) + part;
77        ASSERT((accumulator >> SHIFT_32BIT) == 0);
78    }
79
80    void Shift(int shift_amount)
81    {
82        ASSERT(NEGATIVE_64BIT <= shift_amount && shift_amount <= SHIFT_64BIT);
83        if (shift_amount == 0) {
84            return;
85        } else if (shift_amount == NEGATIVE_64BIT) {
86            high_bits_ = low_bits_;
87            low_bits_ = 0;
88        } else if (shift_amount == SHIFT_64BIT) {
89            low_bits_ = high_bits_;
90            high_bits_ = 0;
91        } else if (shift_amount <= 0) {
92            high_bits_ <<= -shift_amount;
93            high_bits_ += low_bits_ >> (SHIFT_64BIT + shift_amount);
94            low_bits_ <<= -shift_amount;
95        } else {
96            low_bits_ >>= shift_amount;
97            low_bits_ += high_bits_ << (SHIFT_64BIT - shift_amount);
98            high_bits_ >>= shift_amount;
99        }
100    }
101
102    // Modifies *this to *this MOD (2^power).
103    // Returns *this DIV (2^power).
104    int DivModPowerOf2(int power)
105    {
106        if (power >= SHIFT_64BIT) {
107            int result = static_cast<int>(high_bits_ >> (power - SHIFT_64BIT));
108            high_bits_ -= static_cast<uint64_t>(result) << (power - SHIFT_64BIT);
109            return result;
110        } else {
111            uint64_t part_low = low_bits_ >> power;
112            uint64_t part_high = high_bits_ << (SHIFT_64BIT - power);
113            int result = static_cast<int>(part_low + part_high);
114            high_bits_ = 0;
115            low_bits_ -= part_low << power;
116            return result;
117        }
118    }
119
120    bool IsZero() const
121    {
122        return high_bits_ == 0 && low_bits_ == 0;
123    }
124
125    int BitAt(int position)
126    {
127        if (position >= SHIFT_64BIT) {
128            return static_cast<int>((high_bits_ >> (position - SHIFT_64BIT)) & 1);
129        } else {
130            return static_cast<int>((low_bits_ >> position) & 1);
131        }
132    }
133
134private:
135    static const uint64_t kMask32 = 0xFFFFFFFF;
136    uint64_t high_bits_;
137    uint64_t low_bits_;
138};
139
140class DtoaHelper {
141public:
142    static const int kDoubleSignificandSize = 53;  // Includes the hidden bit.
143    static const uint32_t kMaxUInt32 = 0xFFFFFFFF;
144    static constexpr int CACHED_POWERS_OFFSET = 348;
145    static constexpr double kD_1_LOG2_10 = 0.30102999566398114;  //1 / lg(10)
146    static constexpr int kQ = -61;
147    static constexpr int kIndex = 20;
148    static constexpr int MIN_DECIMAL_EXPONENT = -348;
149    static constexpr int EXPONENT_64 = 64;
150    static constexpr int EXPONENT_128 = 128;
151    static constexpr int NEGATIVE_128BIT = -128;
152    static constexpr uint64_t POW10[] = { 1ULL, 10ULL, 100ULL, 1000ULL, 10000ULL, 100000ULL, 1000000ULL,
153                                          10000000ULL, 100000000ULL, 1000000000ULL, 10000000000ULL, 100000000000ULL,
154                                          1000000000000ULL, 10000000000000ULL, 100000000000000ULL, 1000000000000000ULL,
155                                          10000000000000000ULL, 100000000000000000ULL, 1000000000000000000ULL,
156                                          10000000000000000000ULL };
157
158    static constexpr uint32_t TEN = 10;
159    static constexpr uint32_t TEN2POW = 100;
160    static constexpr uint32_t TEN3POW = 1000;
161    static constexpr uint32_t TEN4POW = 10000;
162    static constexpr uint32_t TEN5POW = 100000;
163    static constexpr uint32_t TEN6POW = 1000000;
164    static constexpr uint32_t TEN7POW = 10000000;
165    static constexpr uint32_t TEN8POW = 100000000;
166
167    // DiyFp is a floating-point number type, consists of a uint64 significand and one integer exponent.
168    struct DiyFp {
169        DiyFp() : f(), e() {}
170        DiyFp(uint64_t fp, int exp) : f(fp), e(exp) {}
171
172        explicit DiyFp(double d)
173        {
174            union {
175                double d;
176                uint64_t u64;
177            } u = { d };
178
179            int biased_e = static_cast<int>((u.u64 & kDpExponentMask) >> kDpSignificandSize);
180            uint64_t significand = (u.u64 & kDpSignificandMask);
181            if (biased_e != 0) {
182                f = significand + kDpHiddenBit;
183                e = biased_e - kDpExponentBias;
184            } else {
185                f = significand;
186                e = kDpMinExponent + 1;
187            }
188        }
189
190        DiyFp operator - (const DiyFp &rhs) const
191        {
192            return DiyFp(f - rhs.f, e);
193        }
194
195        DiyFp operator*(const DiyFp &rhs) const
196        {
197            const uint64_t M32 = 0xFFFFFFFF;
198            const uint64_t a = f >> 32;
199            const uint64_t b = f & M32;
200            const uint64_t c = rhs.f >> 32;
201            const uint64_t d = rhs.f & M32;
202            const uint64_t ac = a * c;
203            const uint64_t bc = b * c;
204            const uint64_t ad = a * d;
205            const uint64_t bd = b * d;
206            uint64_t tmp = (bd >> kInt32Bits) + (ad & M32) + (bc & M32);
207            tmp += 1U << kRoundBits; // mult_round
208            return DiyFp(ac + (ad >> kInt32Bits) + (bc >> kInt32Bits) + (tmp >> kInt32Bits), e + rhs.e + kInt64Bits);
209        }
210
211        DiyFp Normalize() const
212        {
213            DiyFp res = *this;
214            while (!(res.f & kDpHiddenBit)) {
215                res.f <<= 1;
216                res.e--;
217            }
218            res.f <<= (kDiySignificandSize - kDpSignificandSize - 1);
219            res.e = res.e - (kDiySignificandSize - kDpSignificandSize - 1);
220            return res;
221        }
222
223        DiyFp NormalizeBoundary() const
224        {
225            DiyFp res = *this;
226            while (!(res.f & (kDpHiddenBit << 1))) {
227                res.f <<= 1;
228                res.e--;
229            }
230            res.f <<= (kDiySignificandSize - kDpSignificandSize - 2); // 2: parameter
231            res.e = res.e - (kDiySignificandSize - kDpSignificandSize - 2); // 2: parameter
232            return res;
233        }
234
235        void NormalizedBoundaries(DiyFp *minus, DiyFp *plus) const
236        {
237            DiyFp pl = DiyFp((f << 1) + 1, e - 1).NormalizeBoundary();
238            DiyFp mi = (f == kDpHiddenBit) ? DiyFp((f << 2) - 1, e - 2) : DiyFp((f << 1) - 1, e - 1); // 2: parameter
239            mi.f <<= mi.e - pl.e;
240            mi.e = pl.e;
241            *plus = pl;
242            *minus = mi;
243        }
244
245        static const int kInt64Bits = 64;
246        static const int kInt32Bits = 32;
247        static const int kRoundBits = 31;
248        static const int kDiySignificandSize = 64;
249        static const int kDpSignificandSize = 52;
250        static const int kDpExponentBias = 0x3FF + kDpSignificandSize;
251        static const int kDpMaxExponent = 0x7FF - kDpExponentBias;
252        static const int kDpMinExponent = -kDpExponentBias;
253        static const int kDpDenormalExponent = -kDpExponentBias + 1;
254        static const uint64_t kDpExponentMask =
255            (static_cast<uint64_t>(0x7FF00000) << 32) | static_cast<uint64_t>(0x00000000);
256        static const uint64_t kDpSignificandMask =
257            (static_cast<uint64_t>(0x000FFFFF) << 32) | static_cast<uint64_t>(0xFFFFFFFF);
258        static const uint64_t kDpHiddenBit =
259            (static_cast<uint64_t>(0x00100000) << 32) | static_cast<uint64_t>(0x00000000);
260
261        uint64_t f;
262        int e;
263    };
264
265    static DiyFp GetCachedPower(int e, int *K)
266    {
267        // dk must be positive, so can do ceiling in positive
268        double dk = (kQ - e) * kD_1_LOG2_10 + CACHED_POWERS_OFFSET - 1;
269        int k = static_cast<int>(dk);
270        if (dk - k > 0.0) {
271            k++;
272        }
273        unsigned index = static_cast<unsigned>((static_cast<unsigned>(k) >> 3) + 1); // 3: parameter
274        *K = -(MIN_DECIMAL_EXPONENT + static_cast<int>(index << 3)); // 3: parameter
275        return GetCachedPowerByIndex(index);
276    }
277
278    static DiyFp GetCachedPowerByIndex(size_t index);
279    static void GrisuRound(char* buffer, int len, uint64_t delta, uint64_t rest, uint64_t tenKappa, uint64_t distance);
280    static int CountDecimalDigit32(uint32_t n);
281    static void DigitGen(const DiyFp& W, const DiyFp& Mp, uint64_t delta, char* buffer, int* len, int* K);
282    static void Grisu(double value, char* buffer, int* length, int* K);
283    static void Dtoa(double value, char* buffer, int* point, int* length);
284    static void FillDigits32FixedLength(uint32_t number, int requested_length, BufferVector<char> buffer, int* length);
285    static void FillDigits32(uint32_t number, BufferVector<char> buffer, int* length);
286    static void FillDigits64FixedLength(uint64_t number, [[maybe_unused]] int requested_length,
287                                        BufferVector<char> buffer, int* length);
288    static void FillDigits64(uint64_t number, BufferVector<char> buffer, int* length);
289    static void RoundUp(BufferVector<char> buffer, int* length, int* decimal_point);
290    static void FillFractionals(uint64_t fractionals, int exponent, int fractional_count, BufferVector<char> buffer,
291                                int* length, int* decimal_point);
292    static void TrimZeros(BufferVector<char> buffer, int* length, int* decimal_point);
293    static bool FixedDtoa(double v, int fractional_count, BufferVector<char> buffer, int* length, int* decimal_point);
294};
295}
296#endif