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
22 namespace panda::ecmascript::base {
GetCachedPowerByIndex(size_t index)23 DtoaHelper::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 ASSERT_PRINT(index < sizeof(kCachedPowers_F) / sizeof(kCachedPowers_F[0]) &&
64 index < sizeof(kCachedPowers_E) / sizeof(kCachedPowers_E[0]), "invalid index: " << index);
65 return DtoaHelper::DiyFp(kCachedPowers_F[index], kCachedPowers_E[index]);
66 }
67
GrisuRound(char * buffer,int len,uint64_t delta,uint64_t rest,uint64_t tenKappa,uint64_t distance)68 void DtoaHelper::GrisuRound(char *buffer, int len, uint64_t delta, uint64_t rest, uint64_t tenKappa, uint64_t distance)
69 {
70 while (rest < distance && delta - rest >= tenKappa &&
71 (rest + tenKappa < distance || distance - rest > rest + tenKappa - distance)) {
72 buffer[len - 1]--;
73 rest += tenKappa;
74 }
75 }
76
CountDecimalDigit32(uint32_t n)77 int DtoaHelper::CountDecimalDigit32(uint32_t n)
78 {
79 if (n < TEN) {
80 return 1; // 1: means the decimal digit
81 } else if (n < TEN2POW) {
82 return 2; // 2: means the decimal digit
83 } else if (n < TEN3POW) {
84 return 3; // 3: means the decimal digit
85 } else if (n < TEN4POW) {
86 return 4; // 4: means the decimal digit
87 } else if (n < TEN5POW) {
88 return 5; // 5: means the decimal digit
89 } else if (n < TEN6POW) {
90 return 6; // 6: means the decimal digit
91 } else if (n < TEN7POW) {
92 return 7; // 7: means the decimal digit
93 } else if (n < TEN8POW) {
94 return 8; // 8: means the decimal digit
95 } else {
96 return 9; // 9: means the decimal digit
97 }
98 }
99
DigitGen(const DiyFp & W,const DiyFp & Mp,uint64_t delta,char * buffer,int * len,int * K)100 void DtoaHelper::DigitGen(const DiyFp &W, const DiyFp &Mp, uint64_t delta, char *buffer, int *len, int *K)
101 {
102 const DiyFp one(uint64_t(1) << -Mp.e, Mp.e);
103 const DiyFp distance = Mp - W;
104 uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e);
105 ASSERT(one.f > 0);
106 uint64_t p2 = Mp.f & (one.f - 1);
107 int kappa = CountDecimalDigit32(p1); // kappa in [0, 9]
108 int localLen = 0;
109 while (kappa > 0) {
110 uint32_t d = 0;
111 switch (kappa) {
112 case 9: // 9: means the decimal digit
113 d = p1 / TEN8POW;
114 p1 %= TEN8POW;
115 break;
116 case 8: // 8: means the decimal digit
117 d = p1 / TEN7POW;
118 p1 %= TEN7POW;
119 break;
120 case 7: // 7: means the decimal digit
121 d = p1 / TEN6POW;
122 p1 %= TEN6POW;
123 break;
124 case 6: // 6: means the decimal digit
125 d = p1 / TEN5POW;
126 p1 %= TEN5POW;
127 break;
128 case 5: // 5: means the decimal digit
129 d = p1 / TEN4POW;
130 p1 %= TEN4POW;
131 break;
132 case 4: // 4: means the decimal digit
133 d = p1 / TEN3POW;
134 p1 %= TEN3POW;
135 break;
136 case 3: // 3: means the decimal digit
137 d = p1 / TEN2POW;
138 p1 %= TEN2POW;
139 break;
140 case 2: // 2: means the decimal digit
141 d = p1 / TEN;
142 p1 %= TEN;
143 break;
144 case 1: // 1: means the decimal digit
145 d = p1;
146 p1 = 0;
147 break;
148 default:;
149 }
150 if (d || localLen) {
151 buffer[localLen++] = static_cast<char>('0' + static_cast<char>(d));
152 }
153 kappa--;
154 uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2;
155 if (tmp <= delta) {
156 *K += kappa;
157 GrisuRound(buffer, localLen, delta, tmp, POW10[kappa] << -one.e, distance.f);
158 *len = localLen;
159 return;
160 }
161 }
162
163 // kappa = 0
164 for (;;) {
165 p2 *= TEN;
166 delta *= TEN;
167 char d = static_cast<char>(p2 >> -one.e);
168 if (d || localLen) {
169 buffer[localLen++] = static_cast<char>('0' + d);
170 }
171 ASSERT(one.f > 0);
172 p2 &= one.f - 1;
173 kappa--;
174 if (p2 < delta) {
175 *K += kappa;
176 int index = -kappa;
177 if (index < kIndex) {
178 GrisuRound(buffer, localLen, delta, p2, one.f, distance.f * POW10[index]);
179 }
180 *len = localLen;
181 return;
182 }
183 }
184 }
185
186 // Grisu2 algorithm use the extra capacity of the used integer type to shorten the produced output
Grisu(double value,char * buffer,int * length,int * K)187 void DtoaHelper::Grisu(double value, char *buffer, int *length, int *K)
188 {
189 const DiyFp v(value);
190 DiyFp mMinus;
191 DiyFp mPlus;
192 v.NormalizedBoundaries(&mMinus, &mPlus);
193
194 const DiyFp cached = GetCachedPower(mPlus.e, K);
195 const DiyFp W = v.Normalize() * cached;
196 DiyFp wPlus = mPlus * cached;
197 DiyFp wMinus = mMinus * cached;
198 wMinus.f++;
199 wPlus.f--;
200 DigitGen(W, wPlus, wPlus.f - wMinus.f, buffer, length, K);
201 }
202
Dtoa(double value,char * buffer,int * point,int * length)203 void DtoaHelper::Dtoa(double value, char *buffer, int *point, int *length)
204 {
205 // Exceptional case such as NAN, 0.0, negative... are processed in DoubleToEcmaString
206 // So use Dtoa should avoid Exceptional case.
207 ASSERT(value > 0);
208 int k;
209 Grisu(value, buffer, length, &k);
210 *point = *length + k;
211 }
212
FillDigits32FixedLength(uint32_t number,int requested_length,BufferVector<char> buffer,int * length)213 void DtoaHelper::FillDigits32FixedLength(uint32_t number, int requested_length,
214 BufferVector<char> buffer, int* length)
215 {
216 for (int i = requested_length - 1; i >= 0; --i) {
217 buffer[(*length) + i] = '0' + number % TEN;
218 number /= TEN;
219 }
220 *length += requested_length;
221 }
222
FillDigits32(uint32_t value,BufferVector<char> outputBuffer,int * totalLength)223 void DtoaHelper::FillDigits32(uint32_t value, BufferVector<char> outputBuffer, int* totalLength)
224 {
225 int digitCount = 0;
226 while (value != 0) {
227 int currentDigit = static_cast<int>(value % TEN);
228 value /= TEN;
229 outputBuffer[(*totalLength) + digitCount] = '0' + currentDigit;
230 digitCount++;
231 }
232 int startIdx = *totalLength;
233 int endIdx = *totalLength + digitCount - 1;
234 while (startIdx < endIdx) {
235 char temp = outputBuffer[startIdx];
236 outputBuffer[startIdx] = outputBuffer[endIdx];
237 outputBuffer[endIdx] = temp;
238 startIdx++;
239 endIdx--;
240 }
241 *totalLength += digitCount;
242 }
243
FillDigits64FixedLength(uint64_t number,int requested_length,BufferVector<char> buffer,int * length)244 void 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
FillDigits64(uint64_t number,BufferVector<char> buffer,int * length)257 void 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
RoundUp(BufferVector<char> digitsBuffer,int * digitCount,int * decimalPosition)276 void DtoaHelper::RoundUp(BufferVector<char> digitsBuffer, int* digitCount, int* decimalPosition)
277 {
278 if (*digitCount == 0) {
279 digitsBuffer[0] = '1';
280 *decimalPosition = 1;
281 *digitCount = 1;
282 return;
283 }
284 digitsBuffer[(*digitCount) - 1]++;
285 for (int i = (*digitCount) - 1; i > 0; --i) {
286 if (digitsBuffer[i] != '0' + 10) {
287 return;
288 }
289 digitsBuffer[i] = '0';
290 digitsBuffer[i - 1]++;
291 }
292 if (digitsBuffer[0] == '0' + 10) {
293 digitsBuffer[0] = '1';
294 (*decimalPosition)++;
295 }
296 }
297
FillFractionals(uint64_t fractionalValue,int exponentValue,int fractionalDigitCount,BufferVector<char> targetBuffer,int * totalLength,int * decimalPointPos)298 void DtoaHelper::FillFractionals(uint64_t fractionalValue, int exponentValue, int fractionalDigitCount,
299 BufferVector<char> targetBuffer, int* totalLength, int* decimalPointPos)
300 {
301 ASSERT(NEGATIVE_128BIT <= exponentValue && exponentValue <= 0);
302 if (-exponentValue <= EXPONENT_64) {
303 ASSERT((fractionalValue >> 56) == 0);
304 int currentPoint = -exponentValue;
305 for (int i = 0; i < fractionalDigitCount; ++i) {
306 if (fractionalValue == 0) {
307 break;
308 }
309 fractionalValue *= 5;
310 currentPoint--;
311 int digitValue = static_cast<int>(fractionalValue >> currentPoint);
312 targetBuffer[*totalLength] = '0' + digitValue;
313 (*totalLength)++;
314 fractionalValue -= static_cast<uint64_t>(digitValue) << currentPoint;
315 }
316 if (currentPoint > 0 && ((fractionalValue >> (currentPoint - 1)) & 1) == 1) {
317 RoundUp(targetBuffer, totalLength, decimalPointPos);
318 }
319 } else {
320 ASSERT(EXPONENT_64 < -exponentValue && -exponentValue <= EXPONENT_128);
321 UInt128 fractionalValue128 = UInt128(fractionalValue, 0);
322 fractionalValue128.Shift(-exponentValue - EXPONENT_64);
323 int currentPoint = 128;
324 for (int i = 0; i < fractionalDigitCount; ++i) {
325 if (fractionalValue128.IsZero()) {
326 break;
327 }
328 fractionalValue128.Multiply(5);
329 currentPoint--;
330 int digitValue = fractionalValue128.DivModPowerOf2(currentPoint);
331 targetBuffer[*totalLength] = '0' + digitValue;
332 (*totalLength)++;
333 }
334 if (fractionalValue128.BitAt(currentPoint - 1) == 1) {
335 RoundUp(targetBuffer, totalLength, decimalPointPos);
336 }
337 }
338 }
339
340 // Removes leading and trailing zeros.
341 // If leading zeros are removed then the decimal point position is adjusted.
TrimZeros(BufferVector<char> digitBuffer,int * digitCount,int * decimalPointPos)342 void DtoaHelper::TrimZeros(BufferVector<char> digitBuffer, int* digitCount, int* decimalPointPos)
343 {
344 while (*digitCount > 0 && digitBuffer[(*digitCount) - 1] == '0') {
345 (*digitCount)--;
346 }
347 int firstNonZeroPos = 0;
348 while (firstNonZeroPos < *digitCount && digitBuffer[firstNonZeroPos] == '0') {
349 firstNonZeroPos++;
350 }
351 if (firstNonZeroPos != 0) {
352 for (int i = firstNonZeroPos; i < *digitCount; ++i) {
353 digitBuffer[i - firstNonZeroPos] = digitBuffer[i];
354 }
355 *digitCount -= firstNonZeroPos;
356 *decimalPointPos -= firstNonZeroPos;
357 }
358 }
359
FixedDtoa(double value,int fractionalDigitCount,BufferVector<char> outputBuffer,int * totalLength,int * decimalPointPosition)360 bool DtoaHelper::FixedDtoa(double value, int fractionalDigitCount, BufferVector<char> outputBuffer,
361 int* totalLength, int* decimalPointPosition)
362 {
363 if (value == 0) {
364 outputBuffer[0] = '0';
365 outputBuffer[1] = '\0';
366 *totalLength = 1;
367 *decimalPointPosition = 1;
368 return true;
369 }
370 uint64_t significandValue = NumberHelper::Significand(value);
371 int exponentValue = NumberHelper::Exponent(value);
372 if (exponentValue > 20) {
373 return false;
374 }
375 if (fractionalDigitCount > 20) {
376 return false;
377 }
378 *totalLength = 0;
379 if (exponentValue + kDoubleSignificandSize > EXPONENT_64) {
380 const uint64_t kFive17 = 0xB1'A2BC'2EC5;
381 uint64_t divisorValue = kFive17;
382 int divisorPower = 17;
383 uint64_t dividendValue = significandValue;
384 uint32_t quotientValue;
385 uint64_t remainderValue;
386 if (exponentValue > divisorPower) {
387 dividendValue <<= exponentValue - divisorPower;
388 quotientValue = static_cast<uint32_t>(dividendValue / divisorValue);
389 remainderValue = (dividendValue % divisorValue) << divisorPower;
390 } else {
391 divisorValue <<= divisorPower - exponentValue;
392 quotientValue = static_cast<uint32_t>(dividendValue / divisorValue);
393 remainderValue = (dividendValue % divisorValue) << exponentValue;
394 }
395 FillDigits32(quotientValue, outputBuffer, totalLength);
396 FillDigits64FixedLength(remainderValue, divisorPower, outputBuffer, totalLength);
397 *decimalPointPosition = *totalLength;
398 } else if (exponentValue >= 0) {
399 significandValue <<= exponentValue;
400 FillDigits64(significandValue, outputBuffer, totalLength);
401 *decimalPointPosition = *totalLength;
402 } else if (exponentValue > -kDoubleSignificandSize) {
403 uint64_t integralPart = significandValue >> -exponentValue;
404 uint64_t fractionalPart = significandValue - (integralPart << -exponentValue);
405 if (integralPart > kMaxUInt32) {
406 FillDigits64(integralPart, outputBuffer, totalLength);
407 } else {
408 FillDigits32(static_cast<uint32_t>(integralPart), outputBuffer, totalLength);
409 }
410 *decimalPointPosition = *totalLength;
411 FillFractionals(fractionalPart, exponentValue, fractionalDigitCount,
412 outputBuffer, totalLength, decimalPointPosition);
413 } else if (exponentValue < NEGATIVE_128BIT) {
414 ASSERT(fractionalDigitCount <= 20);
415 outputBuffer[0] = '\0';
416 *totalLength = 0;
417 *decimalPointPosition = -fractionalDigitCount;
418 } else {
419 *decimalPointPosition = 0;
420 FillFractionals(significandValue, exponentValue, fractionalDigitCount,
421 outputBuffer, totalLength, decimalPointPosition);
422 }
423 TrimZeros(outputBuffer, totalLength, decimalPointPosition);
424 outputBuffer[*totalLength] = '\0';
425 if ((*totalLength) == 0) {
426 *decimalPointPosition = -fractionalDigitCount;
427 }
428 return true;
429 }
430 }
431