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 26 namespace panda::ecmascript::base { 27 28 template <typename T> 29 class BufferVector { 30 public: BufferVector()31 BufferVector() : start_(NULL), length_(0) {} BufferVector(T * data,int length)32 BufferVector(T* data, int length) : start_(data), length_(length) 33 { 34 ASSERT(length == 0 || (length > 0 && data != NULL)); 35 } length()36 int length() const { return length_; } start()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 first()46 T& first() { return start_[0]; } 47 last()48 T& last() { return start_[length_ - 1]; } 49 50 private: 51 T* start_; 52 int length_; 53 }; 54 55 class UInt128 { 56 public: UInt128()57 UInt128() : high_bits_(0), low_bits_(0) { } UInt128(uint64_t high,uint64_t low)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 Multiply(uint32_t multiplicand)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 Shift(int shift_amount)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). DivModPowerOf2(int 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 IsZero()120 bool IsZero() const 121 { 122 return high_bits_ == 0 && low_bits_ == 0; 123 } 124 BitAt(int position)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 134 private: 135 static const uint64_t kMask32 = 0xFFFFFFFF; 136 uint64_t high_bits_; 137 uint64_t low_bits_; 138 }; 139 140 class DtoaHelper { 141 public: 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 static constexpr uint32_t TEN9POW = 1000000000; 167 // DiyFp is a floating-point number type, consists of a uint64 significand and one integer exponent. 168 struct DiyFp { DiyFpDiyFp169 DiyFp() : f(), e() {} DiyFpDiyFp170 DiyFp(uint64_t fp, int exp) : f(fp), e(exp) {} 171 DiyFpDiyFp172 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 NormalizeDiyFp211 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 NormalizeBoundaryDiyFp223 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 NormalizedBoundariesDiyFp235 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 GetCachedPower(int e,int * K)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