1/* 2 * Copyright (c) 2022 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/js_bigint.h" 17 18#include "ecmascript/global_env_constants-inl.h" 19#include "ecmascript/js_tagged_value-inl.h" 20#include "ecmascript/js_tagged_number.h" 21 22namespace panda::ecmascript { 23class ObjectFactory; 24constexpr char dp[] = "0123456789abcdefghijklmnopqrstuvwxyz"; 25static int CharToInt(char c) 26{ 27 uint32_t res = 0; 28 if (c >= '0' && c <= '9') { 29 res = c - '0'; 30 } else if (c >= 'A' && c <= 'Z') { 31 res = c - 'A' + 10; // 10:res must Greater than 10. 32 } else if (c >= 'a' && c <= 'z') { 33 res = c - 'a' + 10; // 10:res must Greater than 10 34 } 35 return static_cast<int>(res); 36} 37 38static void Division(CString &num, uint32_t conversionToRadix, uint32_t currentRadix, uint32_t &remain) 39{ 40 ASSERT(conversionToRadix != 0); 41 uint32_t temp = 0; 42 remain = 0; 43 for (size_t i = 0; i < num.size(); i++) { 44 temp = (currentRadix * remain + static_cast<uint32_t>(CharToInt(num[i]))); 45 num[i] = dp[temp / conversionToRadix]; 46 remain = temp % conversionToRadix; 47 } 48 size_t count = 0; 49 while (count < num.size() && num[count] == '0') { 50 count++; 51 } 52 num = num.substr(count); 53} 54 55CString BigIntHelper::Conversion(const CString &num, uint32_t conversionToRadix, uint32_t currentRadix) 56{ 57 ASSERT(conversionToRadix != 0); 58 CString newNum = num; 59 CString res; 60 uint32_t remain = 0; 61 while (newNum.size() != 0) { 62 Division(newNum, conversionToRadix, currentRadix, remain); 63 res = dp[remain] + res; 64 } 65 return res; 66} 67 68JSHandle<BigInt> BigInt::CreateUint64MaxBigInt(JSThread *thread) 69{ 70 JSHandle<BigInt> bigint = CreateBigint(thread, 3); // 3:The number of digits in an object of type BigInt 71 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 72 bigint->SetDigit(0, 0); 73 bigint->SetDigit(1, 0); 74 bigint->SetDigit(2, 1); // 2:The number of digits in an object of type BigInt 75 return bigint; 76} 77 78JSHandle<BigInt> BigInt::CreateInt64MaxBigInt(JSThread *thread) 79{ 80 JSHandle<BigInt> bigint = CreateBigint(thread, 2); // 2:The number of digits in an object of type BigInt 81 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 82 bigint->SetDigit(0, 0); 83 bigint->SetDigit(1, 0x80000000); // 0x80000000:Int MAX 84 return bigint; 85} 86 87JSHandle<BigInt> BigInt::GetUint64MaxBigInt(JSThread *thread) 88{ 89 return JSHandle<BigInt>::Cast(thread->GlobalConstants()->GetHandledUint64MaxBigInt()); 90} 91 92JSHandle<BigInt> BigInt::GetInt64MaxBigInt(JSThread *thread) 93{ 94 return JSHandle<BigInt>::Cast(thread->GlobalConstants()->GetHandledInt64MaxBigInt()); 95} 96 97JSHandle<BigInt> BigIntHelper::SetBigInt(JSThread *thread, const CString &numStr, uint32_t currentRadix) 98{ 99 int flag = 0; 100 if (numStr[0] == '-') { 101 flag = 1; 102 } 103 104 CString binaryStr = ""; 105 if (currentRadix != BigInt::BINARY) { 106 binaryStr = Conversion(numStr.substr(flag), BigInt::BINARY, currentRadix); 107 } else { 108 binaryStr = numStr.substr(flag); 109 } 110 111 JSHandle<BigInt> bigint; 112 size_t binaryStrLen = binaryStr.size(); 113 size_t len = binaryStrLen / BigInt::DATEBITS; 114 size_t mod = binaryStrLen % BigInt::DATEBITS; 115 int index = 0; 116 if (mod == 0) { 117 index = static_cast<int>(len - 1); 118 bigint = BigInt::CreateBigint(thread, len); 119 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 120 } else { 121 len++; 122 index = static_cast<int>(len - 1); 123 bigint = BigInt::CreateBigint(thread, len); 124 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 125 uint32_t val = 0; 126 for (size_t i = 0; i < mod; ++i) { 127 val <<= 1; 128 val |= static_cast<uint32_t>(binaryStr[i] - '0'); 129 } 130 bigint->SetDigit(index, val); 131 index--; 132 } 133 if (flag == 1) { 134 bigint->SetSign(true); 135 } 136 size_t i = mod; 137 while (i < binaryStrLen) { 138 uint32_t val = 0; 139 for (size_t j = 0; j < BigInt::DATEBITS && i < binaryStrLen; ++j, ++i) { 140 val <<= 1; 141 val |= static_cast<uint32_t>(binaryStr[i] - '0'); 142 } 143 bigint->SetDigit(index, val); 144 index--; 145 } 146 return BigIntHelper::RightTruncate(thread, bigint); 147} 148 149JSHandle<BigInt> BigIntHelper::RightTruncate(JSThread *thread, JSHandle<BigInt> x) 150{ 151 int len = static_cast<int>(x->GetLength()); 152 ASSERT(len != 0); 153 if (len == 1 && x->GetDigit(0) == 0) { 154 x->SetSign(false); 155 return x; 156 } 157 int index = len - 1; 158 if (x->GetDigit(index) != 0) { 159 return x; 160 } 161 while (index >= 0) { 162 if (x->GetDigit(index) != 0) { 163 break; 164 } 165 index--; 166 } 167 168 if (index == -1) { 169 return BigInt::Int32ToBigInt(thread, 0); 170 } else { 171 ASSERT(index >= 0); 172 return BigInt::Copy(thread, x, index + 1); 173 } 174} 175 176CString BigIntHelper::GetBinary(const BigInt *bigint) 177{ 178 ASSERT(bigint != nullptr); 179 int index = 0; 180 int len = static_cast<int>(bigint->GetLength()); 181 int strLen = BigInt::DATEBITS * len; 182 CString res(strLen, '0'); 183 int strIndex = strLen - 1; 184 while (index < len) { 185 int bityLen = BigInt::DATEBITS; 186 uint32_t val = bigint->GetDigit(index); 187 while (bityLen--) { 188 res[strIndex--] = (val & 1) + '0'; 189 val = val >> 1; 190 } 191 index++; 192 } 193 DeZero(res); 194 return res; 195} 196 197JSHandle<BigInt> BigInt::CreateBigint(JSThread *thread, uint32_t length) 198{ 199 if (length > MAXSIZE) { 200 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 201 THROW_RANGE_ERROR_AND_RETURN(thread, "Maximum BigInt size exceeded", bigint); 202 } 203 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory(); 204 JSHandle<BigInt> bigint = factory->NewBigInt(length); 205 return bigint; 206} 207 208// 6.1.6.2.13 209bool BigInt::Equal(const JSTaggedValue &x, const JSTaggedValue &y) 210{ 211 BigInt* xVal = BigInt::Cast(x.GetTaggedObject()); 212 BigInt* yVal = BigInt::Cast(y.GetTaggedObject()); 213 return Equal(xVal, yVal); 214} 215 216bool BigInt::Equal(const BigInt *x, const BigInt *y) 217{ 218 ASSERT(x != nullptr); 219 ASSERT(y != nullptr); 220 if (x->GetSign() != y->GetSign() || x->GetLength() != y->GetLength()) { 221 return false; 222 } 223 for (uint32_t i = 0; i < x->GetLength(); ++i) { 224 if (x->GetDigit(i) != y->GetDigit(i)) { 225 return false; 226 } 227 } 228 return true; 229} 230 231// 6.1.6.2.14 232bool BigInt::SameValue(const JSTaggedValue &x, const JSTaggedValue &y) 233{ 234 return Equal(x, y); 235} 236 237// 6.1.6.2.15 238bool BigInt::SameValueZero(const JSTaggedValue &x, const JSTaggedValue &y) 239{ 240 return Equal(x, y); 241} 242 243JSHandle<BigInt> BigInt::BitwiseOp(JSThread *thread, Operate op, JSHandle<BigInt> x, JSHandle<BigInt> y) 244{ 245 uint32_t maxLen = 0; 246 uint32_t minLen = 0; 247 uint32_t xlen = x->GetLength(); 248 uint32_t ylen = y->GetLength(); 249 if (xlen > ylen) { 250 maxLen = xlen; 251 minLen = ylen; 252 } else { 253 maxLen = ylen; 254 minLen = xlen; 255 } 256 JSHandle<BigInt> bigint = BigInt::CreateBigint(thread, maxLen); 257 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 258 for (size_t i = 0; i < minLen; ++i) { 259 if (op == Operate::OR) { 260 bigint->SetDigit(i, x->GetDigit(i) | y->GetDigit(i)); 261 } else if (op == Operate::AND) { 262 bigint->SetDigit(i, x->GetDigit(i) & y->GetDigit(i)); 263 } else { 264 ASSERT(op == Operate::XOR); 265 bigint->SetDigit(i, x->GetDigit(i) ^ y->GetDigit(i)); 266 } 267 } 268 if (op == Operate::OR || op == Operate::XOR) { 269 if (xlen > ylen) { 270 for (size_t i = ylen; i < xlen; ++i) { 271 bigint->SetDigit(i, x->GetDigit(i)); 272 } 273 } else if (ylen > xlen) { 274 for (size_t i = xlen; i < ylen; ++i) { 275 bigint->SetDigit(i, y->GetDigit(i)); 276 } 277 } 278 } 279 return BigIntHelper::RightTruncate(thread, bigint); 280} 281 282JSHandle<BigInt> OneIsNegativeAND(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 283{ 284 JSHandle<BigInt> yVal = BigInt::BitwiseSubOne(thread, y, y->GetLength()); 285 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 286 uint32_t xLength = x->GetLength(); 287 uint32_t yLength = yVal->GetLength(); 288 uint32_t minLen = xLength; 289 if (xLength > yLength) { 290 minLen = yLength; 291 } 292 JSHandle<BigInt> newBigint = BigInt::CreateBigint(thread, xLength); 293 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 294 uint32_t i = 0; 295 while (i < minLen) { 296 uint32_t res = x->GetDigit(i) & ~(yVal->GetDigit(i)); 297 newBigint->SetDigit(i, res); 298 ++i; 299 } 300 while (i < xLength) { 301 newBigint->SetDigit(i, x->GetDigit(i)); 302 ++i; 303 } 304 return BigIntHelper::RightTruncate(thread, newBigint); 305} 306 307// 6.1.6.2.20 BigInt::bitwiseAND ( x, y ) 308JSHandle<BigInt> BigInt::BitwiseAND(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 309{ 310 if (x->GetSign() && y->GetSign()) { 311 // (-x) & (-y) == -(((x-1) | (y-1)) + 1) 312 JSHandle<BigInt> xVal = BitwiseSubOne(thread, x, x->GetLength()); 313 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 314 JSHandle<BigInt> yVal = BitwiseSubOne(thread, y, y->GetLength()); 315 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 316 JSHandle<BigInt> temp = BitwiseOp(thread, Operate::OR, xVal, yVal); 317 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 318 JSHandle<BigInt> res = BitwiseAddOne(thread, temp); 319 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 320 return res; 321 } 322 if (x->GetSign() != y->GetSign()) { 323 // x & (-y) == x & ~(y-1) 324 if (!x->GetSign()) { 325 return OneIsNegativeAND(thread, x, y); 326 } else { 327 return OneIsNegativeAND(thread, y, x); 328 } 329 } 330 return BitwiseOp(thread, Operate::AND, x, y); 331} 332 333JSHandle<BigInt> OneIsNegativeXOR(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 334{ 335 JSHandle<BigInt> yVal = BigInt::BitwiseSubOne(thread, y, y->GetLength()); 336 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 337 JSHandle<BigInt> temp = BigInt::BitwiseOp(thread, Operate::XOR, x, yVal); 338 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 339 JSHandle<BigInt> res = BigInt::BitwiseAddOne(thread, temp); 340 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 341 return res; 342} 343 344// 6.1.6.2.21 BigInt::bitwiseOR ( x, y ) 345JSHandle<BigInt> BigInt::BitwiseXOR(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 346{ 347 if (x->GetSign() && y->GetSign()) { 348 // (-x) ^ (-y) == (x-1) ^ (y-1) 349 JSHandle<BigInt> xVal = BitwiseSubOne(thread, x, x->GetLength()); 350 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 351 JSHandle<BigInt> yVal = BitwiseSubOne(thread, y, y->GetLength()); 352 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 353 return BitwiseOp(thread, Operate::XOR, xVal, yVal); 354 } 355 if (x->GetSign() != y->GetSign()) { 356 // x ^ (-y) == -((x ^ (y-1)) + 1) 357 if (!x->GetSign()) { 358 return OneIsNegativeXOR(thread, x, y); 359 } else { 360 return OneIsNegativeXOR(thread, y, x); 361 } 362 } 363 return BitwiseOp(thread, Operate::XOR, x, y); 364} 365 366JSHandle<BigInt> BigInt::BitwiseSubOne(JSThread *thread, JSHandle<BigInt> bigint, uint32_t maxLen) 367{ 368 ASSERT(!bigint->IsZero()); 369 ASSERT(maxLen >= bigint->GetLength()); 370 371 JSHandle<BigInt> newBigint = BigInt::CreateBigint(thread, maxLen); 372 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 373 uint32_t bigintLen = bigint->GetLength(); 374 uint32_t carry = 1; 375 for (uint32_t i = 0; i < bigintLen; i++) { 376 uint32_t bigintCarry = 0; 377 newBigint->SetDigit(i, BigIntHelper::SubHelper(bigint->GetDigit(i), carry, bigintCarry)); 378 carry = bigintCarry; 379 } 380 ASSERT(!carry); 381 return BigIntHelper::RightTruncate(thread, newBigint); 382} 383 384JSHandle<BigInt> BigInt::BitwiseAddOne(JSThread *thread, JSHandle<BigInt> bigint) 385{ 386 uint32_t bigintLength = bigint->GetLength(); 387 388 bool needExpend = true; 389 for (uint32_t i = 0; i < bigintLength; i++) { 390 if (std::numeric_limits<uint32_t>::max() != bigint->GetDigit(i)) { 391 needExpend = false; 392 break; 393 } 394 } 395 uint32_t newLength = bigintLength; 396 if (needExpend) { 397 newLength += 1; 398 } 399 JSHandle<BigInt> newBigint = BigInt::CreateBigint(thread, newLength); 400 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 401 uint32_t carry = 1; 402 for (uint32_t i = 0; i < bigintLength; i++) { 403 uint32_t bigintCarry = 0; 404 newBigint->SetDigit(i, BigIntHelper::AddHelper(bigint->GetDigit(i), carry, bigintCarry)); 405 carry = bigintCarry; 406 } 407 if (needExpend) { 408 newBigint->SetDigit(bigintLength, carry); 409 } 410 newBigint->SetSign(true); 411 return BigIntHelper::RightTruncate(thread, newBigint); 412} 413 414JSHandle<BigInt> OneIsNegativeOR(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 415{ 416 uint32_t xLength = x->GetLength(); 417 uint32_t maxLen = xLength; 418 if (maxLen < y->GetLength()) { 419 maxLen = y->GetLength(); 420 } 421 JSHandle<BigInt> yVal = BigInt::BitwiseSubOne(thread, y, maxLen); 422 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 423 uint32_t yLength = yVal->GetLength(); 424 uint32_t minLen = xLength; 425 if (minLen > yLength) { 426 minLen = yLength; 427 } 428 JSHandle<BigInt> newBigint = BigInt::CreateBigint(thread, yLength); 429 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 430 uint32_t i = 0; 431 while (i < minLen) { 432 uint32_t res = ~(x->GetDigit(i)) & yVal->GetDigit(i); 433 newBigint->SetDigit(i, res); 434 ++i; 435 } 436 while (i < yLength) { 437 newBigint->SetDigit(i, yVal->GetDigit(i)); 438 ++i; 439 } 440 JSHandle<BigInt> temp = BigIntHelper::RightTruncate(thread, newBigint); 441 JSHandle<BigInt> res = BigInt::BitwiseAddOne(thread, temp); 442 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 443 res->SetSign(true); 444 return res; 445} 446 447// 6.1.6.2.22 BigInt::bitwiseOR ( x, y ) 448JSHandle<BigInt> BigInt::BitwiseOR(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 449{ 450 if (x->GetSign() && y->GetSign()) { 451 // (-x) | (-y) == -(((x-1) & (y-1)) + 1) 452 uint32_t maxLen = x->GetLength(); 453 uint32_t yLen = y->GetLength(); 454 maxLen < yLen ? maxLen = yLen : 0; 455 JSHandle<BigInt> xVal = BitwiseSubOne(thread, x, maxLen); 456 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 457 JSHandle<BigInt> yVal = BitwiseSubOne(thread, y, yLen); 458 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 459 JSHandle<BigInt> temp = BitwiseOp(thread, Operate::AND, xVal, yVal); 460 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 461 JSHandle<BigInt> res = BitwiseAddOne(thread, temp); 462 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 463 res->SetSign(true); 464 return res; 465 } 466 if (x->GetSign() != y->GetSign()) { 467 // x | (-y) == -(((y-1) & ~x) + 1) 468 if (!x->GetSign()) { 469 return OneIsNegativeOR(thread, x, y); 470 } else { 471 return OneIsNegativeOR(thread, y, x); 472 } 473 } 474 return BitwiseOp(thread, Operate::OR, x, y); 475} 476 477// 6.1.6.2.23 BigInt::toString ( x ) 478JSHandle<EcmaString> BigInt::ToString(JSThread *thread, JSHandle<BigInt> bigint, uint32_t conversionToRadix) 479{ 480 ObjectFactory *factory = thread->GetEcmaVM()->GetFactory(); 481 CString result = bigint->ToStdString(conversionToRadix); 482 return factory->NewFromASCII(result.c_str()); 483} 484 485CString BigInt::ToStdString(uint32_t conversionToRadix) const 486{ 487 CString result = 488 BigIntHelper::Conversion(BigIntHelper::GetBinary(this), conversionToRadix, BINARY); 489 if (GetSign()) { 490 result = "-" + result; 491 } 492 return result; 493} 494 495JSTaggedValue BigInt::NumberToBigInt(JSThread *thread, JSHandle<JSTaggedValue> number) 496{ 497 if (!number->IsInteger()) { 498 THROW_RANGE_ERROR_AND_RETURN(thread, "The number cannot be converted to a BigInt because it is not an integer", 499 JSTaggedValue::Exception()); 500 } 501 double num = number->GetNumber(); 502 if (num == 0.0) { 503 return Int32ToBigInt(thread, 0).GetTaggedValue(); 504 } 505 return DoubleToBigInt(thread, num); 506} 507 508JSTaggedValue BigInt::DoubleToBigInt(JSThread *thread, double num) 509{ 510 // Bit operations must be of integer type 511 uint64_t bits = 0; 512 if (memcpy_s(&bits, sizeof(bits), &num, sizeof(num)) != EOK) { 513 LOG_FULL(FATAL) << "memcpy_s failed"; 514 UNREACHABLE(); 515 } 516 // Take out bits 62-52 (11 bits in total) and subtract 1023 517 uint64_t integerDigits = ((bits >> base::DOUBLE_SIGNIFICAND_SIZE) & 0x7FF) - base::DOUBLE_EXPONENT_BIAS; 518 uint32_t mayNeedLen = integerDigits / DATEBITS + 1; 519 520 JSHandle<BigInt> bigint = CreateBigint(thread, mayNeedLen); 521 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 522 bigint->SetSign(num < 0); 523 uint64_t mantissa = (bits & base::DOUBLE_SIGNIFICAND_MASK) | base::DOUBLE_HIDDEN_BIT; 524 int mantissaSize = base::DOUBLE_SIGNIFICAND_SIZE; 525 526 int leftover = 0; 527 bool isFirstInto = true; 528 for (int index = static_cast<int>(mayNeedLen - 1); index >= 0; --index) { 529 uint32_t doubleNum = 0; 530 if (isFirstInto) { 531 isFirstInto = false; 532 leftover = mantissaSize - static_cast<int>(integerDigits % DATEBITS); 533 doubleNum = static_cast<uint32_t>(mantissa >> leftover); 534 mantissa = mantissa << (64 - leftover); // 64 : double bits size 535 bigint->SetDigit(index, doubleNum); 536 } else { 537 leftover -= DATEBITS; 538 doubleNum = static_cast<uint32_t>(mantissa >> DATEBITS); 539 mantissa = mantissa << DATEBITS; 540 bigint->SetDigit(index, doubleNum); 541 } 542 } 543 return BigIntHelper::RightTruncate(thread, bigint).GetTaggedValue(); 544} 545 546JSHandle<BigInt> BigInt::Int32ToBigInt(JSThread *thread, const int &number) 547{ 548 JSHandle<BigInt> bigint = CreateBigint(thread, 1); 549 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 550 uint32_t value = 0; 551 bool sign = number < 0; 552 if (sign) { 553 value = static_cast<uint32_t>(-(number + 1)) + 1; 554 } else { 555 value = number; 556 } 557 bigint->SetDigit(0, value); 558 bigint->SetSign(sign); 559 return bigint; 560} 561 562JSHandle<BigInt> BigInt::Uint32ToBigInt(JSThread *thread, const uint32_t &number) 563{ 564 JSHandle<BigInt> bigint = CreateBigint(thread, 1); 565 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 566 bigint->SetDigit(0, number); 567 return bigint; 568} 569 570JSHandle<BigInt> BigInt::Int64ToBigInt(JSThread *thread, const int64_t &number) 571{ 572 uint64_t value = 0; 573 bool sign = number < 0; 574 if (sign) { 575 value = static_cast<uint64_t>(-(number + 1)) + 1; 576 } else { 577 value = number; 578 } 579 JSHandle<BigInt> bigint = Uint64ToBigInt(thread, value); 580 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 581 bigint->SetSign(sign); 582 return BigIntHelper::RightTruncate(thread, bigint); 583} 584 585JSHandle<BigInt> BigInt::Uint64ToBigInt(JSThread *thread, const uint64_t &number) 586{ 587 JSHandle<BigInt> bigint = CreateBigint(thread, 2); // 2 : one int64_t bits need two uint32_t bits 588 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 589 uint32_t lowBits = static_cast<uint32_t>(number & 0xffffffff); 590 uint32_t highBits = static_cast<uint32_t>((number >> DATEBITS) & 0xffffffff); 591 bigint->SetDigit(0, lowBits); 592 bigint->SetDigit(1, highBits); 593 return BigIntHelper::RightTruncate(thread, bigint); 594} 595 596uint64_t BigInt::ToUint64() 597{ 598 uint32_t len = GetLength(); 599 ASSERT(len <= 2); // The maximum length of the BigInt data is less or equal 2 600 uint32_t lowBits = GetDigit(0); 601 uint32_t highBits = 0; 602 if (len > 1) { 603 highBits = GetDigit(1); 604 } 605 uint64_t value = static_cast<uint64_t>(lowBits); 606 value |= static_cast<uint64_t>(highBits) << DATEBITS; 607 if (GetSign()) { 608 value = ~(value - 1); 609 } 610 return value; 611} 612 613int64_t BigInt::ToInt64() 614{ 615 return static_cast<int64_t>(ToUint64()); 616} 617 618void BigInt::BigIntToInt64(JSThread *thread, JSHandle<JSTaggedValue> bigint, int64_t *cValue, bool *lossless) 619{ 620 ASSERT(cValue != nullptr); 621 ASSERT(lossless != nullptr); 622 if (bigint->IsBoolean()) { 623 bigint = JSHandle<JSTaggedValue>(thread, JSTaggedValue::ToBigInt(thread, bigint)); 624 RETURN_IF_ABRUPT_COMPLETION(thread); 625 } else if (!bigint->IsBigInt()) { 626 JSHandle<BigInt> bigInt64(thread, JSTaggedValue::ToBigInt64(thread, bigint)); 627 RETURN_IF_ABRUPT_COMPLETION(thread); 628 *cValue = bigInt64->ToInt64(); 629 return; 630 } 631 JSHandle<BigInt> bigInt64(thread, JSTaggedValue::ToBigInt64(thread, bigint)); 632 RETURN_IF_ABRUPT_COMPLETION(thread); 633 if (Equal(bigInt64.GetTaggedValue(), bigint.GetTaggedValue())) { 634 *lossless = true; 635 } else { 636 *lossless = false; 637 } 638 *cValue = bigInt64->ToInt64(); 639} 640 641void BigInt::BigIntToUint64(JSThread *thread, JSHandle<JSTaggedValue> bigint, uint64_t *cValue, bool *lossless) 642{ 643 ASSERT(cValue != nullptr); 644 ASSERT(lossless != nullptr); 645 if (bigint->IsBoolean()) { 646 bigint = JSHandle<JSTaggedValue>(thread, JSTaggedValue::ToBigInt(thread, bigint)); 647 RETURN_IF_ABRUPT_COMPLETION(thread); 648 } else if (!bigint->IsBigInt()) { 649 JSHandle<BigInt> bigInt64(thread, JSTaggedValue::ToBigUint64(thread, bigint)); 650 RETURN_IF_ABRUPT_COMPLETION(thread); 651 *cValue = bigInt64->ToInt64(); 652 return; 653 } 654 JSHandle<BigInt> bigUint64(thread, JSTaggedValue::ToBigUint64(thread, bigint)); 655 RETURN_IF_ABRUPT_COMPLETION(thread); 656 if (Equal(bigUint64.GetTaggedValue(), bigint.GetTaggedValue())) { 657 *lossless = true; 658 } else { 659 *lossless = false; 660 } 661 *cValue = bigUint64->ToUint64(); 662} 663 664JSHandle<BigInt> BigInt::CreateBigWords(JSThread *thread, bool sign, uint32_t size, const uint64_t *words) 665{ 666 ASSERT(words != nullptr); 667 if (size == 0) { 668 return Uint64ToBigInt(thread, 0); 669 } 670 const uint32_t MULTIPLE = 2; 671 uint32_t needLen = size * MULTIPLE; 672 if (needLen > MAXSIZE) { 673 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 674 THROW_RANGE_ERROR_AND_RETURN(thread, "Maximum BigInt size exceeded", bigint); 675 } 676 JSHandle<BigInt> bigint = CreateBigint(thread, needLen); 677 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 678 for (uint32_t index = 0; index < size; ++index) { 679 uint32_t lowBits = static_cast<uint32_t>(words[index] & 0xffffffff); 680 uint32_t highBits = static_cast<uint32_t>((words[index] >> DATEBITS) & 0xffffffff); 681 bigint->SetDigit(MULTIPLE * index, lowBits); 682 bigint->SetDigit(MULTIPLE * index + 1, highBits); 683 } 684 bigint->SetSign(sign); 685 return BigIntHelper::RightTruncate(thread, bigint); 686} 687 688JSHandle<BigInt> BigInt::Add(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 689{ 690 bool xSignFlag = x->GetSign(); 691 bool ySignFlag = y->GetSign(); 692 // x + y == x + y 693 // -x + -y == -(x + y) 694 if (xSignFlag == ySignFlag) { 695 return BigintAdd(thread, x, y, xSignFlag); 696 } 697 // x + -y == x - y == -(y - x) 698 // -x + y == y - x == -(x - y) 699 uint32_t xLength = x->GetLength(); 700 uint32_t yLength = y->GetLength(); 701 int i = static_cast<int>(xLength) - 1; 702 int subSize = static_cast<int>(xLength - yLength); 703 if (subSize > 0) { 704 return BigintSub(thread, x, y, xSignFlag); 705 } else if (subSize == 0) { 706 while (i > 0 && x->GetDigit(i) == y->GetDigit(i)) { 707 i--; 708 } 709 if ((x->GetDigit(i) > y->GetDigit(i))) { 710 return BigintSub(thread, x, y, xSignFlag); 711 } else { 712 return BigintSub(thread, y, x, ySignFlag); 713 } 714 } else { 715 return BigintSub(thread, y, x, ySignFlag); 716 } 717} 718JSHandle<BigInt> BigInt::Subtract(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 719{ 720 bool xSignFlag = x->GetSign(); 721 bool ySignFlag = y->GetSign(); 722 if (xSignFlag != ySignFlag) { 723 // x - (-y) == x + y 724 // (-x) - y == -(x + y) 725 return BigintAdd(thread, x, y, xSignFlag); 726 } 727 // x - y == -(y - x) 728 // (-x) - (-y) == y - x == -(x - y) 729 uint32_t xLength = x->GetLength(); 730 uint32_t yLength = y->GetLength(); 731 ASSERT(xLength > 0); 732 uint32_t i = xLength - 1; 733 int subSize = static_cast<int>(xLength - yLength); 734 if (subSize > 0) { 735 return BigintSub(thread, x, y, xSignFlag); 736 } else if (subSize == 0) { 737 while (i > 0 && x->GetDigit(i) == y->GetDigit(i)) { 738 i--; 739 } 740 if ((x->GetDigit(i) > y->GetDigit(i))) { 741 return BigintSub(thread, x, y, xSignFlag); 742 } else { 743 return BigintSub(thread, y, x, !ySignFlag); 744 } 745 } else { 746 return BigintSub(thread, y, x, !ySignFlag); 747 } 748} 749 750JSHandle<BigInt> BigInt::BigintAdd(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y, bool resultSign) 751{ 752 if (x->GetLength() < y->GetLength()) { 753 return BigintAdd(thread, y, x, resultSign); 754 } 755 JSHandle<BigInt> bigint = BigInt::CreateBigint(thread, x->GetLength() + 1); 756 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 757 uint32_t bigintCarry = 0; 758 uint32_t i = 0; 759 while (i < y->GetLength()) { 760 uint32_t newBigintCarry = 0; 761 uint32_t addPlus = BigIntHelper::AddHelper(x->GetDigit(i), y->GetDigit(i), newBigintCarry); 762 addPlus = BigIntHelper::AddHelper(addPlus, bigintCarry, newBigintCarry); 763 bigint->SetDigit(i, addPlus); 764 bigintCarry = newBigintCarry; 765 i++; 766 } 767 while (i < x->GetLength()) { 768 uint32_t newBigintCarry = 0; 769 uint32_t addPlus = BigIntHelper::AddHelper(x->GetDigit(i), bigintCarry, newBigintCarry); 770 bigint->SetDigit(i, addPlus); 771 bigintCarry = newBigintCarry; 772 i++; 773 } 774 bigint->SetDigit(i, bigintCarry); 775 bigint->SetSign(resultSign); 776 return BigIntHelper::RightTruncate(thread, bigint); 777} 778 779inline uint32_t BigIntHelper::AddHelper(uint32_t x, uint32_t y, uint32_t &bigintCarry) 780{ 781 uint32_t addPlus = x + y; 782 if (addPlus < x) { 783 bigintCarry += 1; 784 } 785 return addPlus; 786} 787 788JSHandle<BigInt> BigInt::BigintSub(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y, bool resultSign) 789{ 790 JSHandle<BigInt> bigint = BigInt::CreateBigint(thread, x->GetLength()); 791 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 792 uint32_t bigintCarry = 0; 793 uint32_t i = 0; 794 while (i < y->GetLength()) { 795 uint32_t newBigintCarry = 0; 796 uint32_t minuSub = BigIntHelper::SubHelper(x->GetDigit(i), y->GetDigit(i), newBigintCarry); 797 minuSub = BigIntHelper::SubHelper(minuSub, bigintCarry, newBigintCarry); 798 bigint->SetDigit(i, minuSub); 799 bigintCarry = newBigintCarry; 800 i++; 801 } 802 while (i < x->GetLength()) { 803 uint32_t newBigintCarry = 0; 804 uint32_t minuSub = BigIntHelper::SubHelper(x->GetDigit(i), bigintCarry, newBigintCarry); 805 bigint->SetDigit(i, minuSub); 806 bigintCarry = newBigintCarry; 807 i++; 808 } 809 bigint->SetSign(resultSign); 810 return BigIntHelper::RightTruncate(thread, bigint); 811} 812 813JSHandle<BigInt> BigInt::BigintAddOne(JSThread *thread, JSHandle<BigInt> x) 814{ 815 JSHandle<BigInt> temp = Int32ToBigInt(thread, 1); 816 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 817 return Add(thread, x, temp); 818} 819 820JSHandle<BigInt> BigInt::BigintSubOne(JSThread *thread, JSHandle<BigInt> x) 821{ 822 JSHandle<BigInt> temp = Int32ToBigInt(thread, 1); 823 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 824 return Subtract(thread, x, temp); 825} 826 827inline uint32_t BigIntHelper::SubHelper(uint32_t x, uint32_t y, uint32_t &bigintCarry) 828{ 829 ASSERT(x - y >= 0); 830 uint32_t minuSub = x - y; 831 if (minuSub > x) { 832 bigintCarry += 1; 833 } 834 return minuSub; 835} 836 837ComparisonResult BigInt::Compare(const JSTaggedValue &x, const JSTaggedValue &y) 838{ 839 BigInt* xVal = BigInt::Cast(x.GetTaggedObject()); 840 BigInt* yVal = BigInt::Cast(y.GetTaggedObject()); 841 return Compare(xVal, yVal); 842} 843 844ComparisonResult BigInt::Compare(const BigInt *x, const BigInt *y) 845{ 846 bool xSign = x->GetSign(); 847 bool ySign = y->GetSign(); 848 if (xSign != ySign) { 849 return xSign ? ComparisonResult::LESS : ComparisonResult::GREAT; 850 } 851 ComparisonResult compar = AbsolutelyCompare(x, y); 852 if (xSign && compar != ComparisonResult::EQUAL) { 853 return compar == ComparisonResult::LESS ? ComparisonResult::GREAT : ComparisonResult::LESS; 854 } 855 return compar; 856} 857 858bool BigInt::LessThan(const JSTaggedValue &x, const JSTaggedValue &y) 859{ 860 return Compare(x, y) == ComparisonResult::LESS; 861} 862 863bool BigInt::LessThan(const BigInt *x, const BigInt *y) 864{ 865 ASSERT(x != nullptr); 866 ASSERT(y != nullptr); 867 return Compare(x, y) == ComparisonResult::LESS; 868} 869 870JSHandle<BigInt> BigInt::SignedRightShift(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 871{ 872 if (x->IsZero() || y->IsZero()) { 873 return x; 874 } 875 if (y->GetSign()) { 876 return LeftShiftHelper(thread, x, y); 877 } else { 878 return RightShiftHelper(thread, x, y); 879 } 880} 881 882JSHandle<BigInt> BigInt::ReturnIfRightShiftOverMax(JSThread *thread, bool sign) 883{ 884 if (sign) { 885 return Int32ToBigInt(thread, -1); 886 } 887 return Int32ToBigInt(thread, 0); 888} 889 890void BigInt::RightShift(JSHandle<BigInt> bigint, JSHandle<BigInt> x, uint32_t digitMove, uint32_t bitsMove) 891{ 892 uint32_t size = x->GetLength(); 893 if (bitsMove == 0) { 894 for (uint32_t i = digitMove; i < size; i++) { 895 bigint->SetDigit(i - digitMove, x->GetDigit(i)); 896 } 897 } else { 898 uint32_t carry = x->GetDigit(digitMove) >> bitsMove; 899 ASSERT(size > digitMove); 900 uint32_t last = size - digitMove - 1; 901 for (uint32_t i = 0; i < last; i++) { 902 uint32_t value = x->GetDigit(i + digitMove + 1); 903 bigint->SetDigit(i, (value << (DATEBITS - bitsMove)) | carry); 904 carry = value >> bitsMove; 905 } 906 bigint->SetDigit(last, carry); 907 } 908} 909 910void BigInt::JudgeRoundDown(JSHandle<BigInt> x, uint32_t digitMove, uint32_t bitsMove, uint32_t &needLen, 911 bool &roundDown) 912{ 913 uint32_t stamp = (static_cast<uint32_t>(1U) << bitsMove) - 1; 914 if (x->GetDigit(digitMove) & stamp) { 915 roundDown = true; 916 } else { 917 for (uint32_t i = 0; i < digitMove; i++) { 918 if (x->GetDigit(i) != 0) { 919 roundDown = true; 920 break; 921 } 922 } 923 } 924 925 if (roundDown && bitsMove == 0) { 926 ASSERT(x->GetLength() > 0); 927 uint32_t highBits = x->GetDigit(x->GetLength() - 1); 928 // If all the most significant bits are 1, we think that carry will cause overflow, 929 // and needLen needs to be increased by 1 930 if ((~highBits) == 0) { 931 needLen++; 932 } 933 } 934} 935 936JSHandle<BigInt> BigInt::RightShiftHelper(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 937{ 938 bool sign = x->GetSign(); 939 if (y->GetLength() > 1 || y->GetDigit(0) > MAXBITS) { 940 return ReturnIfRightShiftOverMax(thread, sign); 941 } 942 uint32_t moveNum = y->GetDigit(0); 943 uint32_t digitMove = moveNum / DATEBITS; 944 uint32_t bitsMove = moveNum % DATEBITS; 945 if (x->GetLength() <= digitMove) { 946 return ReturnIfRightShiftOverMax(thread, sign); 947 } 948 uint32_t needLen = x->GetLength() - digitMove; 949 bool roundDown = false; 950 if (sign) { 951 // If it is a negative number, you need to consider whether it will carry after moving. 952 // NeedLen may need to increase by 1 953 JudgeRoundDown(x, digitMove, bitsMove, needLen, roundDown); 954 } 955 JSHandle<BigInt> bigint = CreateBigint(thread, needLen); 956 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 957 958 RightShift(bigint, x, digitMove, bitsMove); 959 bigint = BigIntHelper::RightTruncate(thread, bigint); 960 if (sign) { 961 bigint->SetSign(true); 962 if (roundDown) { 963 return BitwiseAddOne(thread, bigint); 964 } 965 } 966 return bigint; 967} 968 969JSHandle<BigInt> BigInt::LeftShift(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 970{ 971 if (y->GetSign()) { 972 return RightShiftHelper(thread, x, y); 973 } else { 974 return LeftShiftHelper(thread, x, y); 975 } 976} 977 978JSHandle<BigInt> BigInt::LeftShiftHelper(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 979{ 980 if (x->IsZero()) { 981 return x; 982 } 983 ASSERT(y->GetLength() > 0); 984 uint32_t moveNum = y->GetDigit(0); 985 uint32_t digitMove = moveNum / DATEBITS; 986 uint32_t bitsMove = moveNum % DATEBITS; 987 // If bitsMove is not zero, needLen needs to be increased by 1 988 uint32_t needLen = digitMove + x->GetLength() + static_cast<uint32_t>(!!bitsMove); 989 JSHandle<BigInt> bigint = CreateBigint(thread, needLen); 990 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 991 if (bitsMove == 0) { 992 uint32_t index = digitMove; 993 while (index < needLen) { 994 bigint->SetDigit(index, x->GetDigit(index - digitMove)); 995 ++index; 996 } 997 } else { 998 uint32_t carry = 0; 999 uint32_t index = 0; 1000 while (index < x->GetLength()) { 1001 uint32_t value = x->GetDigit(index); 1002 bigint->SetDigit(index + digitMove, (value << bitsMove) | carry); 1003 carry = value >> (DATEBITS - bitsMove); 1004 ++index; 1005 } 1006 if (carry != 0) { 1007 ASSERT(index + digitMove < needLen); 1008 bigint->SetDigit(index + digitMove, carry); 1009 } 1010 } 1011 bigint->SetSign(x->GetSign()); 1012 return BigIntHelper::RightTruncate(thread, bigint); 1013} 1014 1015JSTaggedValue BigInt::UnsignedRightShift(JSThread *thread) 1016{ 1017 THROW_TYPE_ERROR_AND_RETURN(thread, "BigInt have no unsigned right shift, use >> instead", 1018 JSTaggedValue::Exception()); 1019} 1020 1021JSHandle<BigInt> BigInt::Copy(JSThread *thread, JSHandle<BigInt> x, uint32_t len) 1022{ 1023 ASSERT(x->GetLength() >= len); 1024 JSHandle<BigInt> newBig = CreateBigint(thread, len); 1025 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1026 std::copy(x->GetData(), x->GetData() + len, newBig->GetData()); 1027 newBig->SetSign(x->GetSign()); 1028 return newBig; 1029} 1030 1031JSHandle<BigInt> BigInt::UnaryMinus(JSThread *thread, JSHandle<BigInt> x) 1032{ 1033 if (x->IsZero()) { 1034 return x; 1035 } 1036 JSHandle<BigInt> y = Copy(thread, x, x->GetLength()); 1037 y->SetSign(!y->GetSign()); 1038 return y; 1039} 1040 1041// 6.1.6.2.2 BigInt::bitwiseNOT ( x ) 1042JSHandle<BigInt> BigInt::BitwiseNOT(JSThread *thread, JSHandle<BigInt> x) 1043{ 1044 // ~(-x) == ~(~(x-1)) == x-1 1045 // ~x == -x-1 == -(x+1) 1046 JSHandle<BigInt> result = BigintAddOne(thread, x); 1047 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1048 if (x->GetSign()) { 1049 result->SetSign(false); 1050 } else { 1051 result->SetSign(true); 1052 } 1053 return result; 1054} 1055 1056JSHandle<BigInt> BigInt::Exponentiate(JSThread *thread, JSHandle<BigInt> base, JSHandle<BigInt> exponent) 1057{ 1058 if (exponent->GetSign()) { 1059 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 1060 THROW_RANGE_ERROR_AND_RETURN(thread, "Exponent must be positive", bigint); 1061 } 1062 ASSERT(exponent->GetLength() > 0); 1063 if (exponent->IsZero()) { 1064 return Int32ToBigInt(thread, 1); 1065 } 1066 if (base->IsZero()) { 1067 return base; 1068 } 1069 uint32_t expValue = exponent->GetDigit(0); 1070 if (base->GetLength() == 1 && base->GetDigit(0) == 1) { 1071 if (base->GetSign() && !(expValue & 1)) { 1072 return BigInt::UnaryMinus(thread, base); 1073 } 1074 return base; 1075 } 1076 if (exponent->GetLength() > 1) { 1077 // The result is at least 2n ** 2n ** 32n, which is too big. 1078 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 1079 THROW_RANGE_ERROR_AND_RETURN(thread, "Maximum BigInt size exceeded", bigint); 1080 } 1081 1082 if (base->GetLength() == 1 && base->GetDigit(0) == 2) { // 2 : We use fast path processing 2 ^ n 1083 uint32_t needLength = expValue / DATEBITS + 1; 1084 JSHandle<BigInt> bigint = CreateBigint(thread, needLength); 1085 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1086 uint32_t value = 1U << (expValue % DATEBITS); 1087 bigint->SetDigit(needLength - 1, value); 1088 if (base->GetSign()) { 1089 bigint->SetSign(static_cast<bool>(expValue & 1)); 1090 } 1091 return bigint; 1092 } 1093 JSMutableHandle<BigInt> result(thread, JSTaggedValue::Null()); 1094 JSMutableHandle<BigInt> temp(thread, base); 1095 if (expValue & 1) { 1096 result.Update(base); 1097 } 1098 expValue >>= 1; 1099 for (; expValue; expValue >>= 1) { 1100 temp.Update(BigInt::Multiply(thread, temp, temp)); 1101 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1102 if (expValue & 1) { 1103 if (result.GetTaggedValue().IsNull()) { 1104 result.Update(temp); 1105 } else { 1106 result.Update(BigInt::Multiply(thread, result, temp)); 1107 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1108 } 1109 } 1110 } 1111 ASSERT(result.GetTaggedValue().IsBigInt()); 1112 return result; 1113} 1114 1115std::tuple<uint32_t, uint32_t> BigInt::Mul(uint32_t x, uint32_t y) 1116{ 1117 uint32_t lowBitX = x & HALFDATEMASK; 1118 uint32_t highBitX = x >> HALFDATEBITS; 1119 uint32_t lowBitY = y & HALFDATEMASK; 1120 uint32_t highBitY = y >> HALFDATEBITS; 1121 // {highBitX lowBitX} * {highBitY lowBitY} 1122 uint32_t lowRes = lowBitX * lowBitY; 1123 uint32_t highRes = highBitX * highBitY; 1124 uint32_t midRes1 = lowBitX * highBitY; 1125 uint32_t midRes2 = highBitX * lowBitY; 1126 1127 uint32_t carry = 0; 1128 uint32_t low = BigIntHelper::AddHelper( 1129 BigIntHelper::AddHelper(lowRes, midRes1 << HALFDATEBITS, carry), midRes2 << HALFDATEBITS, carry); 1130 uint32_t high = (midRes1 >> HALFDATEBITS) + (midRes2 >> HALFDATEBITS) + highRes + carry; 1131 1132 return std::make_tuple(high, low); 1133} 1134 1135JSHandle<BigInt> BigInt::Multiply(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 1136{ 1137 if (x->IsZero()) { 1138 return x; 1139 } 1140 if (y->IsZero()) { 1141 return y; 1142 } 1143 uint32_t needLength = x->GetLength() + y->GetLength(); 1144 JSHandle<BigInt> bigint = BigInt::CreateBigint(thread, needLength); 1145 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1146 // the algorithm here is similar to the way we use paper money to calculate multiplication. 1147 // Generally, we first calculate the partial product, and then add up to get the result. 1148 // The only difference here is that multiplication and addition are calculated synchronously 1149 for (uint32_t i = 0; i < x->GetLength(); i++) { 1150 uint32_t xVal = x->GetDigit(i); 1151 // If the current multiplier is 0, we will skip this round of calculation to improve performance. 1152 // If we do not skip, the correctness of the calculation will not be affected 1153 if (xVal == 0) { 1154 continue; 1155 } 1156 uint32_t carry = 0; 1157 uint32_t high = 0; 1158 uint32_t index = i; 1159 for (uint32_t j = 0; j < y->GetLength(); j++) { 1160 uint32_t currentCarry = 0; 1161 uint32_t value = bigint->GetDigit(index); 1162 value = BigIntHelper::AddHelper(value, high, currentCarry); 1163 value = BigIntHelper::AddHelper(value, carry, currentCarry); 1164 1165 uint32_t low; 1166 std::tie(high, low) = Mul(xVal, y->GetDigit(j)); 1167 value = BigIntHelper::AddHelper(value, low, currentCarry); 1168 bigint->SetDigit(index, value); 1169 carry = currentCarry; 1170 index++; 1171 } 1172 while (carry != 0 || high != 0) { 1173 ASSERT(index < bigint->GetLength()); 1174 uint32_t value = bigint->GetDigit(index); 1175 uint32_t currentCarry = 0; 1176 value = BigIntHelper::AddHelper(value, high, currentCarry); 1177 high = 0; 1178 value = BigIntHelper::AddHelper(value, carry, currentCarry); 1179 bigint->SetDigit(index, value); 1180 carry = currentCarry; 1181 index++; 1182 } 1183 } 1184 1185 bigint->SetSign(x->GetSign() != y->GetSign()); 1186 return BigIntHelper::RightTruncate(thread, bigint); 1187} 1188 1189void BigIntHelper::DeZero(CString &a) 1190{ 1191 size_t count = 0; 1192 while (count < a.size() && a[count] == '0') { 1193 count++; 1194 } 1195 if (count == a.size()) { 1196 a = "0"; 1197 } else { 1198 a = a.substr(count); 1199 } 1200} 1201 1202ComparisonResult BigInt::AbsolutelyCompare(const BigInt *x, const BigInt *y) 1203{ 1204 uint32_t xLen = x->GetLength(); 1205 uint32_t yLen = y->GetLength(); 1206 if (xLen > yLen) { 1207 return ComparisonResult::GREAT; 1208 } else if (xLen < yLen) { 1209 return ComparisonResult::LESS; 1210 } else { 1211 int index = static_cast<int>(xLen) - 1; 1212 for (; index >= 0; --index) { 1213 if (x->GetDigit(index) != y->GetDigit(index)) { 1214 break; 1215 } 1216 } 1217 if (index < 0) { 1218 return ComparisonResult::EQUAL; 1219 } 1220 return x->GetDigit(index) > y->GetDigit(index) ? ComparisonResult::GREAT : ComparisonResult::LESS; 1221 } 1222} 1223 1224uint32_t BigInt::DivideAndRemainder(uint32_t highBit, uint32_t lowBit, uint32_t divisor, uint32_t& remainder) 1225{ 1226 uint32_t leadingZeros = base::CountLeadingZeros(divisor); 1227 // Before calculating, we need to align the operands to the left 1228 divisor <<= leadingZeros; 1229 uint32_t lowDividend = lowBit << leadingZeros; 1230 uint32_t highDividend = highBit; 1231 if (leadingZeros != 0) { 1232 // highBit is the remainder of the last calculation, which must be less than or equal to the divisor, 1233 // so high << leadingZeros will not lose the significant bit 1234 highDividend = (highBit << leadingZeros) | (lowBit >> (DATEBITS - leadingZeros)); 1235 } 1236 uint32_t highDivisor = divisor >> HALFDATEBITS; 1237 uint32_t lowDivisor = divisor & HALFDATEMASK; 1238 uint32_t lowDividend1 = lowDividend >> HALFDATEBITS; 1239 uint32_t lowDividend2 = lowDividend & HALFDATEMASK; 1240 uint32_t highQuotient = highDividend / highDivisor; 1241 uint32_t tempRemainder = highDividend - highQuotient * highDivisor; 1242 1243 // Similar to the ordinary division calculation, here we use HALFUINT32VALUE as the carry unit 1244 // Calculate high order results first 1245 while (highQuotient >= HALFUINT32VALUE || 1246 highQuotient * lowDivisor > tempRemainder * HALFUINT32VALUE + lowDividend1) { 1247 highQuotient--; 1248 tempRemainder += highDivisor; 1249 if (tempRemainder >= HALFUINT32VALUE) { 1250 break; 1251 } 1252 } 1253 uint32_t tempLowDividend = highDividend * HALFUINT32VALUE + lowDividend1 - highQuotient * divisor; 1254 uint32_t lowQuotient = tempLowDividend / highDivisor; 1255 tempRemainder = tempLowDividend - lowQuotient * highDivisor; 1256 1257 // Then calculate the low order result 1258 while (lowQuotient >= HALFUINT32VALUE || 1259 lowQuotient * lowDivisor > tempRemainder * HALFUINT32VALUE + lowDividend2) { 1260 lowQuotient--; 1261 tempRemainder += highDivisor; 1262 if (tempRemainder >= HALFUINT32VALUE) { 1263 break; 1264 } 1265 } 1266 1267 // In order to facilitate the calculation, we start to make left alignment 1268 // At this time, we need to move right to get the correct remainder 1269 remainder = (tempLowDividend * HALFUINT32VALUE + lowDividend2 - lowQuotient * divisor) >> leadingZeros; 1270 return highQuotient * HALFUINT32VALUE + lowQuotient; 1271} 1272 1273JSHandle<BigInt> BigInt::FormatLeftShift(JSThread *thread, uint32_t shift, JSHandle<BigInt> bigint, bool neeedAddOne) 1274{ 1275 if (!neeedAddOne && shift == 0) { 1276 return bigint; 1277 } 1278 uint32_t len = bigint->GetLength(); 1279 uint32_t needLen = len; 1280 if (neeedAddOne) { 1281 needLen += 1; 1282 } 1283 JSHandle<BigInt> result = CreateBigint(thread, needLen); 1284 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1285 if (shift == 0) { 1286 std::copy(bigint->GetData(), bigint->GetData() + len, result->GetData()); 1287 } else { 1288 uint32_t carry = 0; 1289 uint32_t index = 0; 1290 while (index < len) { 1291 uint32_t value = bigint->GetDigit(index); 1292 result->SetDigit(index, (value << shift) | carry); 1293 carry = value >> (DATEBITS - shift); 1294 index++; 1295 } 1296 if (carry != 0) { 1297 ASSERT(neeedAddOne); 1298 result->SetDigit(index, carry); 1299 } 1300 } 1301 return result; 1302} 1303 1304void BigInt::UnformattedRightShift(JSHandle<BigInt> bigint, uint32_t shift) 1305{ 1306 RightShift(bigint, bigint, 0, shift); 1307} 1308 1309bool BigInt::SpecialMultiplyAndSub(JSHandle<BigInt> u, JSHandle<BigInt> v, uint32_t q, JSHandle<BigInt> qv, 1310 uint32_t pos) 1311{ 1312 uint32_t lastCarry = 0; 1313 uint32_t lastHigh = 0; 1314 uint32_t len = v->GetLength(); 1315 // Calculate multiplication first 1316 for (uint32_t i = 0; i < len; ++i) { 1317 uint32_t value = v->GetDigit(i); 1318 uint32_t carry = 0; 1319 uint32_t high = 0; 1320 std::tie(high, value) = Mul(value, q); 1321 // The current value plus the high and carry of the last calculation 1322 value = BigIntHelper::AddHelper(value, lastHigh, carry); 1323 value = BigIntHelper::AddHelper(value, lastCarry, carry); 1324 qv->SetDigit(i, value); 1325 // Record the new high bit and carry for the next round 1326 lastCarry = carry; 1327 lastHigh = high; 1328 } 1329 qv->SetDigit(len, lastHigh + lastCarry); 1330 1331 // Next, subtract 1332 uint32_t lastBorrow = 0; 1333 for (uint32_t i = 0; i < qv->GetLength(); ++i) { 1334 uint32_t borrow = 0; 1335 uint32_t value = BigIntHelper::SubHelper(u->GetDigit(pos + i), qv->GetDigit(i), borrow); 1336 value = BigIntHelper::SubHelper(value, lastBorrow, borrow); 1337 u->SetDigit(pos + i, value); 1338 lastBorrow = borrow; 1339 } 1340 1341 return lastBorrow > 0; 1342} 1343 1344uint32_t BigInt::SpecialAdd(JSHandle<BigInt> u, JSHandle<BigInt> v, uint32_t pos) 1345{ 1346 uint32_t lastCarry = 0; 1347 for (uint32_t i = 0; i < v->GetLength(); ++i) { 1348 uint32_t carry = 0; 1349 uint32_t value = BigIntHelper::AddHelper(u->GetDigit(pos + i), v->GetDigit(i), carry); 1350 value = BigIntHelper::AddHelper(value, lastCarry, carry); 1351 u->SetDigit(pos + i, value); 1352 lastCarry = carry; 1353 } 1354 return lastCarry; 1355} 1356 1357uint32_t BigInt::ImproveAccuracy(uint32_t vHighest, uint32_t vHighestNext, uint32_t UHighest, 1358 uint32_t UHighestNext, uint32_t q) 1359{ 1360 uint32_t high = 0; 1361 uint32_t low = 0; 1362 std::tie(high, low) = Mul(q, vHighestNext); 1363 while (high > UHighest || (high == UHighest && low > UHighestNext)) { 1364 q--; 1365 UHighest += vHighest; 1366 // if r is less than the current base, continue the next round of inspection. Here, 1367 // we confirm whether r is greater than the current base by judging whether r overflows 1368 if (UHighest < vHighest) { 1369 break; 1370 } 1371 std::tie(high, low) = Mul(q, vHighestNext); 1372 } 1373 return q; 1374} 1375 1376JSHandle<BigInt> BigInt::DivideAndRemainderWithBigintDivisor(JSThread *thread, JSHandle<BigInt> dividend, 1377 JSHandle<BigInt> divisor, 1378 JSMutableHandle<BigInt> &remainder) 1379{ 1380 uint32_t divisorLen = divisor->GetLength(); 1381 // the length of the quota is the length of the dividend minus the divisor 1382 uint32_t quotientLen = dividend->GetLength() - divisorLen; 1383 JSMutableHandle<BigInt> quotient(thread, JSTaggedValue::Null()); 1384 if (remainder.GetTaggedValue().IsNull()) { 1385 quotient.Update(CreateBigint(thread, quotientLen + 1)); 1386 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1387 } 1388 // format the divisor and dividend so that the highest order of the divisor is 1389 // greater than or equal to half of uint32_t 1390 ASSERT(divisorLen > 0); 1391 uint32_t leadingZeros = base::CountLeadingZeros(divisor->GetDigit(divisorLen - 1)); 1392 JSHandle<BigInt> v = FormatLeftShift(thread, leadingZeros, divisor, false); 1393 JSHandle<BigInt> u = FormatLeftShift(thread, leadingZeros, dividend, true); 1394 // qv is used to store the result of quotient * divisor of each round 1395 JSHandle<BigInt> qv = CreateBigint(thread, divisorLen + 1); 1396 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1397 uint32_t vHighest = v->GetDigit(divisorLen - 1); 1398 for (int i = static_cast<int>(quotientLen); i >= 0; --i) { 1399 uint32_t currentUHighest = u->GetDigit(i + divisorLen); 1400 uint32_t r = 0; 1401 uint32_t q = DivideAndRemainder(currentUHighest, u->GetDigit(i + divisorLen - 1), vHighest, r); 1402 // VHighest = currentUHighest means that q may be equal to the current base 1403 // In the current program, the current base is the maximum value of uint32 plus 1 1404 if (vHighest == currentUHighest) { 1405 q = std::numeric_limits<uint32_t>::max(); 1406 } else { 1407 uint32_t vHighestNext = v->GetDigit(divisorLen - 2); // 2 : Get the second most significant bit 1408 uint32_t currentUHighestNext = u->GetDigit(i + divisorLen - 2); // 2 : ditto 1409 1410 // The following operations will make q only 1 greater than the value we want in most cases, 1411 // and will not be less than it 1412 q = ImproveAccuracy(vHighest, vHighestNext, r, currentUHighestNext, q); 1413 } 1414 // multiplication and subtraction 1415 if (SpecialMultiplyAndSub(u, v, q, qv, i)) { 1416 q--; 1417 uint32_t carry = SpecialAdd(u, v, i); 1418 u->SetDigit(i + divisorLen, u->GetDigit(i + divisorLen) + carry); 1419 } 1420 if (remainder.GetTaggedValue().IsNull()) { 1421 quotient->SetDigit(i, q); 1422 } 1423 } 1424 if (!remainder.GetTaggedValue().IsNull()) { 1425 // at the beginning of this procedure, we performed the left shift operation. 1426 // Here, we get the correct result by shifting the same number of digits to the right 1427 UnformattedRightShift(u, leadingZeros); 1428 remainder.Update(u); 1429 } 1430 return quotient; 1431} 1432 1433JSHandle<BigInt> BigInt::DivideAndRemainderWithUint32Divisor(JSThread *thread, JSHandle<BigInt> dividend, 1434 uint32_t divisor, JSMutableHandle<BigInt> &remainder) 1435{ 1436 uint32_t r = 0; 1437 JSMutableHandle<BigInt> quotient(thread, JSTaggedValue::Null()); 1438 if (!remainder.GetTaggedValue().IsNull()) { 1439 for (int i = static_cast<int>(dividend->GetLength()) - 1; i >= 0; --i) { 1440 DivideAndRemainder(r, dividend->GetDigit(i), divisor, r); 1441 remainder.Update(Uint32ToBigInt(thread, r)); 1442 } 1443 } else { 1444 quotient.Update(CreateBigint(thread, dividend->GetLength())); 1445 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1446 for (int i = static_cast<int>(dividend->GetLength()) - 1; i >= 0; --i) { 1447 uint32_t q = DivideAndRemainder(r, dividend->GetDigit(i), divisor, r); 1448 quotient->SetDigit(i, q); 1449 } 1450 } 1451 return quotient; 1452} 1453 1454// The algorithm here refers to algorithm D in Volume 2 of <The Art of Computer Programming> 1455JSHandle<BigInt> BigInt::Divide(JSThread *thread, JSHandle<BigInt> x, JSHandle<BigInt> y) 1456{ 1457 if (y->IsZero()) { 1458 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 1459 THROW_RANGE_ERROR_AND_RETURN(thread, "Division by zero", bigint); 1460 } 1461 // returns 0 if x is less than y 1462 JSMutableHandle<BigInt> quotient(thread, JSTaggedValue::Null()); 1463 bool sign = x->GetSign() != y->GetSign(); 1464 ComparisonResult compare = AbsolutelyCompare(*x, *y); 1465 if (compare == ComparisonResult::LESS) { 1466 return Int32ToBigInt(thread, 0); 1467 } 1468 if (compare == ComparisonResult::EQUAL) { 1469 quotient.Update(Int32ToBigInt(thread, 1)); 1470 quotient->SetSign(sign); 1471 return quotient; 1472 } 1473 // if y is 1, return +x or -x 1474 if (y->IsUint32() && y->GetDigit(0) == 1) { 1475 if (sign == x->GetSign()) { 1476 return x; 1477 } 1478 return UnaryMinus(thread, x); 1479 } 1480 JSMutableHandle<BigInt> remainder(thread, JSTaggedValue::Null()); 1481 if (y->IsUint32()) { 1482 // When the divisor is uint32_t, we have a faster and simpler algorithm to calculate 1483 quotient.Update(DivideAndRemainderWithUint32Divisor(thread, x, y->GetDigit(0), remainder)); 1484 } else { 1485 ASSERT(y->GetLength() >= 1); // 1 : Entering the current branch length must be greater than 1 1486 JSHandle<BigInt> newBigint = DivideAndRemainderWithBigintDivisor(thread, x, y, remainder); 1487 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1488 quotient.Update(newBigint); 1489 } 1490 ASSERT(quotient.GetTaggedValue().IsBigInt()); 1491 quotient->SetSign(sign); 1492 return BigIntHelper::RightTruncate(thread, quotient); 1493} 1494 1495JSHandle<BigInt> BigInt::Remainder(JSThread *thread, JSHandle<BigInt> n, JSHandle<BigInt> d) 1496{ 1497 if (d->IsZero()) { 1498 JSHandle<BigInt> bigint(thread, JSTaggedValue::Exception()); 1499 THROW_RANGE_ERROR_AND_RETURN(thread, "Division by zero", bigint); 1500 } 1501 ComparisonResult compare = AbsolutelyCompare(*n, *d); 1502 if (n->IsZero() || compare == ComparisonResult::LESS) { 1503 return n; 1504 } 1505 if (compare == ComparisonResult::EQUAL || (d->IsUint32() && d->GetDigit(0) == 1)) { 1506 return Int32ToBigInt(thread, 0); 1507 } 1508 JSMutableHandle<BigInt> remainder(thread, JSTaggedValue::Undefined()); 1509 if (d->IsUint32()) { 1510 // When the divisor is uint32_t, we have a faster and simpler algorithm to calculate 1511 DivideAndRemainderWithUint32Divisor(thread, n, d->GetDigit(0), remainder); 1512 } else { 1513 ASSERT(d->GetLength() > 1); // 1 : Entering the current branch length must be greater than 1 1514 DivideAndRemainderWithBigintDivisor(thread, n, d, remainder); 1515 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1516 } 1517 ASSERT(remainder.GetTaggedValue().IsBigInt()); 1518 remainder->SetSign(n->GetSign()); 1519 return BigIntHelper::RightTruncate(thread, remainder); 1520} 1521 1522JSHandle<BigInt> BigInt::FloorMod(JSThread *thread, JSHandle<BigInt> leftVal, JSHandle<BigInt> rightVal) 1523{ 1524 JSHandle<BigInt> remainder = Remainder(thread, leftVal, rightVal); 1525 RETURN_HANDLE_IF_ABRUPT_COMPLETION(BigInt, thread); 1526 if (leftVal->GetSign() && !remainder->IsZero()) { 1527 return Add(thread, remainder, rightVal); 1528 } 1529 return remainder; 1530} 1531 1532JSTaggedValue BigInt::AsUintN(JSThread *thread, JSTaggedNumber &bits, JSHandle<BigInt> bigint) 1533{ 1534 JSTaggedNumber number = JSTaggedValue::ToNumber(thread, bits); 1535 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 1536 int64_t bit = base::NumberHelper::DoubleToInt64(number.GetNumber()); 1537 if (bit == 0) { 1538 return Int32ToBigInt(thread, 0).GetTaggedValue(); 1539 } 1540 if (bigint->IsZero()) { 1541 return bigint.GetTaggedValue(); 1542 } 1543 JSHandle<BigInt> exponent = Uint64ToBigInt(thread, bit); 1544 JSHandle<BigInt> base = Int64ToBigInt(thread, 2); // 2 : base value 1545 if (bit >= kMaxLengthBits && !bigint->GetSign()) { 1546 return bigint.GetTaggedValue(); 1547 } 1548 JSHandle<BigInt> tValue = Exponentiate(thread, base, exponent); 1549 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 1550 return FloorMod(thread, bigint, tValue).GetTaggedValue(); 1551} 1552 1553JSTaggedValue BigInt::AsintN(JSThread *thread, JSTaggedNumber &bits, JSHandle<BigInt> bigint) 1554{ 1555 JSTaggedNumber number = JSTaggedValue::ToNumber(thread, bits); 1556 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 1557 int64_t bit = base::NumberHelper::DoubleToInt64(number.GetNumber()); 1558 if (bit == 0) { 1559 return Int32ToBigInt(thread, 0).GetTaggedValue(); 1560 } 1561 if (bigint->IsZero()) { 1562 return bigint.GetTaggedValue(); 1563 } 1564 JSHandle<BigInt> exp = Int64ToBigInt(thread, bit); 1565 JSHandle<BigInt> exponent = Int64ToBigInt(thread, bit - 1); 1566 JSHandle<BigInt> base = Int64ToBigInt(thread, 2); // 2 : base value 1567 if (bit >= kMaxLengthBits && !bigint->GetSign()) { 1568 return bigint.GetTaggedValue(); 1569 } 1570 JSHandle<BigInt> tValue = Exponentiate(thread, base, exp); 1571 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 1572 JSHandle<BigInt> modValue = FloorMod(thread, bigint, tValue); 1573 JSHandle<BigInt> resValue = Exponentiate(thread, base, exponent); 1574 RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread); 1575 // If mod ≥ 2bits - 1, return ℤ(mod - 2bits); otherwise, return (mod). 1576 if (Compare(*resValue, *modValue) != ComparisonResult::GREAT) { 1577 return Subtract(thread, modValue, tValue).GetTaggedValue(); 1578 } 1579 return modValue.GetTaggedValue(); 1580} 1581 1582static JSTaggedNumber CalculateNumber(const uint64_t &sign, const uint64_t &mantissa, uint64_t &exponent) 1583{ 1584 exponent = (exponent + base::DOUBLE_EXPONENT_BIAS) << base::DOUBLE_SIGNIFICAND_SIZE; 1585 uint64_t doubleBit = sign | exponent | mantissa; 1586 double res = 0; 1587 if (memcpy_s(&res, sizeof(res), &doubleBit, sizeof(doubleBit)) != EOK) { 1588 LOG_FULL(FATAL) << "memcpy_s failed"; 1589 UNREACHABLE(); 1590 } 1591 return JSTaggedNumber(res); 1592} 1593 1594static JSTaggedNumber Rounding(const uint64_t &sign, uint64_t &mantissa, uint64_t &exponent, bool needRound) 1595{ 1596 if (needRound || (mantissa & 1) == 1) { 1597 ++mantissa; 1598 if ((mantissa >> base::DOUBLE_SIGNIFICAND_SIZE) != 0) { 1599 mantissa = 0; 1600 exponent++; 1601 if (exponent > base::DOUBLE_EXPONENT_BIAS) { 1602 return JSTaggedNumber(sign ? -base::POSITIVE_INFINITY : base::POSITIVE_INFINITY); 1603 } 1604 } 1605 } 1606 return CalculateNumber(sign, mantissa, exponent); 1607} 1608 1609JSTaggedNumber BigInt::BigIntToNumber(JSHandle<BigInt> bigint) 1610{ 1611 if (bigint->IsZero()) { 1612 return JSTaggedNumber(0); 1613 } 1614 uint32_t bigintLen = bigint->GetLength(); 1615 ASSERT(bigintLen > 0); 1616 uint32_t BigintHead = bigint->GetDigit(bigintLen - 1); 1617 uint32_t leadingZeros = base::CountLeadingZeros(BigintHead); 1618 int bigintBitLen = static_cast<int>(bigintLen * BigInt::DATEBITS - leadingZeros); 1619 // if Significant bits greater than 1024 then double is infinity 1620 bool bigintSign = bigint->GetSign(); 1621 if (bigintBitLen > (base::DOUBLE_EXPONENT_BIAS + 1)) { 1622 return JSTaggedNumber(bigintSign ? -base::POSITIVE_INFINITY : base::POSITIVE_INFINITY); 1623 } 1624 uint64_t sign = bigintSign ? 1ULL << 63 : 0; // 63 : Set the sign bit of sign to 1 1625 int needMoveBit = static_cast<int>(leadingZeros + BigInt::DATEBITS + 1); 1626 // Align to the most significant bit, then right shift 12 bits so that the head of the mantissa is in place 1627 uint64_t mantissa = (needMoveBit == 64) ? 0 : 1628 ((static_cast<uint64_t>(BigintHead) << needMoveBit) >> 12); // 12 mantissa// just has 52 bits 1629 int remainMantissaBits = needMoveBit - 12; 1630 ASSERT(bigintBitLen > 0); 1631 uint64_t exponent = static_cast<uint64_t>(bigintBitLen - 1); 1632 int index = static_cast<int>(bigintLen - 1); 1633 uint32_t digit = 0; 1634 if (index > 0) { 1635 digit = bigint->GetDigit(--index); 1636 } else { 1637 return CalculateNumber(sign, mantissa, exponent); 1638 } 1639 // pad unset mantissa 1640 if (static_cast<uint32_t>(remainMantissaBits) >= BigInt::DATEBITS) { 1641 mantissa |= (static_cast<uint64_t>(digit) << (remainMantissaBits - BigInt::DATEBITS)); 1642 remainMantissaBits -= BigInt::DATEBITS; 1643 index--; 1644 } 1645 if (remainMantissaBits > 0 && index >= 0) { 1646 digit = bigint->GetDigit(index); 1647 mantissa |= (static_cast<uint64_t>(digit) >> (BigInt::DATEBITS - remainMantissaBits)); 1648 remainMantissaBits -= BigInt::DATEBITS; 1649 } 1650 // After the mantissa is filled, if the bits of bigint have not been used up, consider the rounding problem 1651 // The remaining bits of the current digit 1652 if (remainMantissaBits > 0) { 1653 return CalculateNumber(sign, mantissa, exponent); 1654 } 1655 int remainDigitBits = 0; 1656 if (remainMantissaBits < 0) { 1657 remainDigitBits = -remainMantissaBits; 1658 } else { 1659 if (index <= 0) { 1660 return CalculateNumber(sign, mantissa, exponent); 1661 } 1662 digit = bigint->GetDigit(index--); 1663 remainDigitBits = BigInt::DATEBITS; 1664 } 1665 uint32_t temp = 1ULL << (remainDigitBits - 1); 1666 if (!(digit & temp)) { 1667 return CalculateNumber(sign, mantissa, exponent); 1668 } 1669 if ((digit & (temp - 1)) != 0) { 1670 return Rounding(sign, mantissa, exponent, true); 1671 } 1672 while (index > 0) { 1673 if (bigint->GetDigit(--index) != 0) { 1674 return Rounding(sign, mantissa, exponent, true); 1675 } 1676 } 1677 return Rounding(sign, mantissa, exponent, false); 1678} 1679 1680static int CompareToBitsLen(JSHandle<BigInt> bigint, int numBitLen, int &leadingZeros) 1681{ 1682 uint32_t bigintLen = bigint->GetLength(); 1683 ASSERT(bigintLen > 0); 1684 uint32_t BigintHead = bigint->GetDigit(bigintLen - 1); 1685 leadingZeros = static_cast<int>(base::CountLeadingZeros(BigintHead)); 1686 int bigintBitLen = static_cast<int>(bigintLen * BigInt::DATEBITS) - leadingZeros; 1687 bool bigintSign = bigint->GetSign(); 1688 if (bigintBitLen > numBitLen) { 1689 return bigintSign ? 0 : 1; 1690 } 1691 1692 if (bigintBitLen < numBitLen) { 1693 return bigintSign ? 1 : 0; 1694 } 1695 return -1; 1696} 1697 1698ComparisonResult BigInt::CompareWithNumber(JSHandle<BigInt> bigint, JSHandle<JSTaggedValue> number) 1699{ 1700 double num = number->GetNumber(); 1701 bool numberSign = num < 0; 1702 if (std::isnan(num)) { 1703 return ComparisonResult::UNDEFINED; 1704 } 1705 if (!std::isfinite(num)) { 1706 return (!numberSign ? ComparisonResult::LESS : ComparisonResult::GREAT); 1707 } 1708 // Bit operations must be of integer type 1709 uint64_t bits = 0; 1710 if (memcpy_s(&bits, sizeof(bits), &num, sizeof(num)) != EOK) { 1711 LOG_FULL(FATAL) << "memcpy_s failed"; 1712 UNREACHABLE(); 1713 } 1714 int exponential = (bits >> base::DOUBLE_SIGNIFICAND_SIZE) & 0x7FF; 1715 1716 // Take out bits 62-52 (11 bits in total) and subtract 1023 1717 int integerDigits = exponential - base::DOUBLE_EXPONENT_BIAS; 1718 uint64_t mantissa = (bits & base::DOUBLE_SIGNIFICAND_MASK) | base::DOUBLE_HIDDEN_BIT; 1719 bool bigintSign = bigint->GetSign(); 1720 // Handling the opposite sign 1721 if (!numberSign && bigintSign) { 1722 return ComparisonResult::LESS; 1723 } else if (numberSign && !bigintSign) { 1724 return ComparisonResult::GREAT; 1725 } 1726 if (bigint->IsZero() && !num) { 1727 return ComparisonResult::EQUAL; 1728 } 1729 if (bigint->IsZero() && num > 0) { 1730 return ComparisonResult::LESS; 1731 } 1732 1733 if (integerDigits < 0) { 1734 return bigintSign ? ComparisonResult::LESS : ComparisonResult::GREAT; 1735 } 1736 1737 // Compare the significant bits of bigint with the significant integer bits of double 1738 int leadingZeros = 0; 1739 int res = CompareToBitsLen(bigint, integerDigits + 1, leadingZeros); 1740 if (res == 0) { 1741 return ComparisonResult::LESS; 1742 } else if (res == 1) { 1743 return ComparisonResult::GREAT; 1744 } 1745 int mantissaSize = base::DOUBLE_SIGNIFICAND_SIZE; // mantissaSize 1746 uint32_t bigintLen = bigint->GetLength(); 1747 int leftover = 0; 1748 bool IsFirstInto = true; 1749 ASSERT(bigintLen > 0); 1750 for (int index = static_cast<int>(bigintLen - 1); index >= 0; --index) { 1751 uint32_t doubleNum = 0; 1752 uint32_t BigintNum = bigint->GetDigit(index); 1753 if (IsFirstInto) { 1754 IsFirstInto = false; 1755 leftover = mantissaSize - BigInt::DATEBITS + leadingZeros + 1; 1756 doubleNum = static_cast<uint32_t>(mantissa >> leftover); 1757 mantissa = mantissa << (64 - leftover); // 64 : double bits 1758 if (BigintNum > doubleNum) { 1759 return bigintSign ? ComparisonResult::LESS : ComparisonResult::GREAT; 1760 } 1761 if (BigintNum < doubleNum) { 1762 return bigintSign ? ComparisonResult::GREAT : ComparisonResult::LESS; 1763 } 1764 } else { 1765 leftover -= BigInt::DATEBITS; 1766 doubleNum = static_cast<uint32_t>(mantissa >> BigInt::DATEBITS); 1767 mantissa = mantissa << BigInt::DATEBITS; 1768 if (BigintNum > doubleNum) { 1769 return bigintSign ? ComparisonResult::LESS : ComparisonResult::GREAT; 1770 } 1771 if (BigintNum < doubleNum) { 1772 return bigintSign ? ComparisonResult::GREAT : ComparisonResult::LESS; 1773 } 1774 leftover -= BigInt::DATEBITS; 1775 } 1776 } 1777 1778 if (mantissa != 0) { 1779 ASSERT(leftover > 0); 1780 return bigintSign ? ComparisonResult::GREAT : ComparisonResult::LESS; 1781 } 1782 return ComparisonResult::EQUAL; 1783} 1784} // namespace 1785