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