| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2012 Google Inc. All Rights Reserved. | |
| 2 | |
| 3 #include "vm/bigint_operations.h" | |
| 4 | |
| 5 #include "platform/assert.h" | |
| 6 #include "platform/utils.h" | |
| 7 | |
| 8 #include "vm/double_internals.h" | |
| 9 #include "vm/exceptions.h" | |
| 10 #include "vm/object_store.h" | |
| 11 #include "vm/zone.h" | |
| 12 | |
| 13 namespace dart { | |
| 14 | |
| 15 RawBigint* BigintOperations::NewFromSmi(const Smi& smi, Heap::Space space) { | |
| 16 intptr_t value = smi.Value(); | |
| 17 if (value == 0) { | |
| 18 return Zero(); | |
| 19 } | |
| 20 | |
| 21 bool is_negative = (value < 0); | |
| 22 if (is_negative) { | |
| 23 value = -value; | |
| 24 } | |
| 25 // Assert that there are no overflows. Smis reserve a bit for themselves, but | |
| 26 // protect against future changes. | |
| 27 ASSERT(-Smi::kMinValue > 0); | |
| 28 | |
| 29 // A single digit of a Bigint might not be sufficient to store a Smi. | |
| 30 // Count number of needed Digits. | |
| 31 intptr_t digit_count = 0; | |
| 32 intptr_t count_value = value; | |
| 33 while (count_value > 0) { | |
| 34 digit_count++; | |
| 35 count_value >>= kDigitBitSize; | |
| 36 } | |
| 37 | |
| 38 // Allocate a bigint of the correct size and copy the bits. | |
| 39 const Bigint& result = Bigint::Handle(Bigint::Allocate(digit_count, space)); | |
| 40 for (intptr_t i = 0; i < digit_count; i++) { | |
| 41 result.SetChunkAt(i, static_cast<Chunk>(value & kDigitMask)); | |
| 42 value >>= kDigitBitSize; | |
| 43 } | |
| 44 result.SetSign(is_negative); | |
| 45 ASSERT(IsClamped(result)); | |
| 46 return result.raw(); | |
| 47 } | |
| 48 | |
| 49 | |
| 50 RawBigint* BigintOperations::NewFromInt64(int64_t value, Heap::Space space) { | |
| 51 bool is_negative = value < 0; | |
| 52 | |
| 53 if (is_negative) { | |
| 54 value = -value; | |
| 55 } | |
| 56 | |
| 57 const Bigint& result = Bigint::Handle(NewFromUint64(value, space)); | |
| 58 result.SetSign(is_negative); | |
| 59 | |
| 60 return result.raw(); | |
| 61 } | |
| 62 | |
| 63 | |
| 64 RawBigint* BigintOperations::NewFromUint64(uint64_t value, Heap::Space space) { | |
| 65 if (value == 0) { | |
| 66 return Zero(); | |
| 67 } | |
| 68 // A single digit of a Bigint might not be sufficient to store the value. | |
| 69 // Count number of needed Digits. | |
| 70 intptr_t digit_count = 0; | |
| 71 uint64_t count_value = value; | |
| 72 while (count_value > 0) { | |
| 73 digit_count++; | |
| 74 count_value >>= kDigitBitSize; | |
| 75 } | |
| 76 | |
| 77 // Allocate a bigint of the correct size and copy the bits. | |
| 78 const Bigint& result = Bigint::Handle(Bigint::Allocate(digit_count, space)); | |
| 79 for (intptr_t i = 0; i < digit_count; i++) { | |
| 80 result.SetChunkAt(i, static_cast<Chunk>(value & kDigitMask)); | |
| 81 value >>= kDigitBitSize; | |
| 82 } | |
| 83 result.SetSign(false); | |
| 84 ASSERT(IsClamped(result)); | |
| 85 return result.raw(); | |
| 86 } | |
| 87 | |
| 88 | |
| 89 RawBigint* BigintOperations::NewFromCString(const char* str, | |
| 90 Heap::Space space) { | |
| 91 ASSERT(str != NULL); | |
| 92 if (str[0] == '\0') { | |
| 93 return Zero(); | |
| 94 } | |
| 95 | |
| 96 // If the string starts with '-' recursively restart the whole operation | |
| 97 // without the character and then toggle the sign. | |
| 98 // This allows multiple leading '-' (which will cancel each other out), but | |
| 99 // we have added an assert, to make sure that the returned result of the | |
| 100 // recursive call is not negative. | |
| 101 // We don't catch leading '-'s for zero. Ex: "--0", or "---". | |
| 102 if (str[0] == '-') { | |
| 103 const Bigint& result = Bigint::Handle(NewFromCString(&str[1], space)); | |
| 104 result.ToggleSign(); | |
| 105 ASSERT(result.IsZero() || result.IsNegative()); | |
| 106 ASSERT(IsClamped(result)); | |
| 107 return result.raw(); | |
| 108 } | |
| 109 | |
| 110 // No overflow check needed since overflowing str_length implies that we take | |
| 111 // the branch to FromDecimalCString() which contains a check itself. | |
| 112 const intptr_t str_length = strlen(str); | |
| 113 if ((str_length > 2) && | |
| 114 (str[0] == '0') && | |
| 115 ((str[1] == 'x') || (str[1] == 'X'))) { | |
| 116 const Bigint& result = Bigint::Handle(FromHexCString(&str[2], space)); | |
| 117 ASSERT(IsClamped(result)); | |
| 118 return result.raw(); | |
| 119 } else { | |
| 120 return FromDecimalCString(str, space); | |
| 121 } | |
| 122 } | |
| 123 | |
| 124 | |
| 125 intptr_t BigintOperations::ComputeChunkLength(const char* hex_string) { | |
| 126 ASSERT(kDigitBitSize % 4 == 0); | |
| 127 const intptr_t hex_length = strlen(hex_string); | |
| 128 if (hex_length < 0) { | |
| 129 FATAL("Fatal error in BigintOperations::ComputeChunkLength: " | |
| 130 "string too long"); | |
| 131 } | |
| 132 // Round up. | |
| 133 intptr_t bigint_length = ((hex_length - 1) / kHexCharsPerDigit) + 1; | |
| 134 return bigint_length; | |
| 135 } | |
| 136 | |
| 137 | |
| 138 RawBigint* BigintOperations::FromHexCString(const char* hex_string, | |
| 139 Heap::Space space) { | |
| 140 // If the string starts with '-' recursively restart the whole operation | |
| 141 // without the character and then toggle the sign. | |
| 142 // This allows multiple leading '-' (which will cancel each other out), but | |
| 143 // we have added an assert, to make sure that the returned result of the | |
| 144 // recursive call is not negative. | |
| 145 // We don't catch leading '-'s for zero. Ex: "--0", or "---". | |
| 146 if (hex_string[0] == '-') { | |
| 147 const Bigint& value = Bigint::Handle(FromHexCString(&hex_string[1], space)); | |
| 148 value.ToggleSign(); | |
| 149 ASSERT(value.IsZero() || value.IsNegative()); | |
| 150 ASSERT(IsClamped(value)); | |
| 151 return value.raw(); | |
| 152 } | |
| 153 intptr_t bigint_length = ComputeChunkLength(hex_string); | |
| 154 const Bigint& result = Bigint::Handle(Bigint::Allocate(bigint_length, space)); | |
| 155 FromHexCString(hex_string, result); | |
| 156 return result.raw(); | |
| 157 } | |
| 158 | |
| 159 | |
| 160 RawBigint* BigintOperations::FromDecimalCString(const char* str, | |
| 161 Heap::Space space) { | |
| 162 Isolate* isolate = Isolate::Current(); | |
| 163 // Read 8 digits a time. 10^8 < 2^27. | |
| 164 const int kDigitsPerIteration = 8; | |
| 165 const Chunk kTenMultiplier = 100000000; | |
| 166 ASSERT(kDigitBitSize >= 27); | |
| 167 | |
| 168 const intptr_t str_length = strlen(str); | |
| 169 if (str_length < 0) { | |
| 170 FATAL("Fatal error in BigintOperations::FromDecimalCString: " | |
| 171 "string too long"); | |
| 172 } | |
| 173 intptr_t str_pos = 0; | |
| 174 | |
| 175 // Read first digit separately. This avoids a multiplication and addition. | |
| 176 // The first digit might also not have kDigitsPerIteration decimal digits. | |
| 177 intptr_t first_digit_decimal_digits = str_length % kDigitsPerIteration; | |
| 178 Chunk digit = 0; | |
| 179 for (intptr_t i = 0; i < first_digit_decimal_digits; i++) { | |
| 180 char c = str[str_pos++]; | |
| 181 ASSERT(('0' <= c) && (c <= '9')); | |
| 182 digit = digit * 10 + c - '0'; | |
| 183 } | |
| 184 Bigint& result = Bigint::Handle(Bigint::Allocate(1)); | |
| 185 result.SetChunkAt(0, digit); | |
| 186 Clamp(result); // Multiplication requires the inputs to be clamped. | |
| 187 | |
| 188 // Read kDigitsPerIteration at a time, and store it in 'increment'. | |
| 189 // Then multiply the temporary result by 10^kDigitsPerIteration and add | |
| 190 // 'increment' to the new result. | |
| 191 const Bigint& increment = Bigint::Handle(Bigint::Allocate(1)); | |
| 192 while (str_pos < str_length - 1) { | |
| 193 HANDLESCOPE(isolate); | |
| 194 Chunk digit = 0; | |
| 195 for (intptr_t i = 0; i < kDigitsPerIteration; i++) { | |
| 196 char c = str[str_pos++]; | |
| 197 ASSERT(('0' <= c) && (c <= '9')); | |
| 198 digit = digit * 10 + c - '0'; | |
| 199 } | |
| 200 result = MultiplyWithDigit(result, kTenMultiplier); | |
| 201 if (digit != 0) { | |
| 202 increment.SetChunkAt(0, digit); | |
| 203 result = Add(result, increment); | |
| 204 } | |
| 205 } | |
| 206 Clamp(result); | |
| 207 if ((space == Heap::kOld) && !result.IsOld()) { | |
| 208 result ^= Object::Clone(result, Heap::kOld); | |
| 209 } | |
| 210 return result.raw(); | |
| 211 } | |
| 212 | |
| 213 | |
| 214 RawBigint* BigintOperations::NewFromDouble(double d, Heap::Space space) { | |
| 215 if ((-1.0 < d) && (d < 1.0)) { | |
| 216 // Shortcut for small numbers. Also makes the right-shift below | |
| 217 // well specified. | |
| 218 Smi& zero = Smi::Handle(Smi::New(0)); | |
| 219 return NewFromSmi(zero, space); | |
| 220 } | |
| 221 DoubleInternals internals = DoubleInternals(d); | |
| 222 if (internals.IsSpecial()) { | |
| 223 const Array& exception_arguments = Array::Handle(Array::New(1)); | |
| 224 exception_arguments.SetAt( | |
| 225 0, | |
| 226 PassiveObject::Handle(String::New("BigintOperations::NewFromDouble"))); | |
| 227 Exceptions::ThrowByType(Exceptions::kInternalError, exception_arguments); | |
| 228 } | |
| 229 uint64_t significand = internals.Significand(); | |
| 230 intptr_t exponent = internals.Exponent(); | |
| 231 intptr_t sign = internals.Sign(); | |
| 232 if (exponent <= 0) { | |
| 233 significand >>= -exponent; | |
| 234 exponent = 0; | |
| 235 } else if (exponent <= 10) { | |
| 236 // A double significand has at most 53 bits. The following shift will | |
| 237 // hence not overflow, and yield an integer of at most 63 bits. | |
| 238 significand <<= exponent; | |
| 239 exponent = 0; | |
| 240 } | |
| 241 // A significand has at most 63 bits (after the shift above). | |
| 242 // The cast to int64_t is hence safe. | |
| 243 const Bigint& result = | |
| 244 Bigint::Handle(NewFromInt64(static_cast<int64_t>(significand), space)); | |
| 245 result.SetSign(sign < 0); | |
| 246 if (exponent > 0) { | |
| 247 return ShiftLeft(result, exponent); | |
| 248 } else { | |
| 249 return result.raw(); | |
| 250 } | |
| 251 } | |
| 252 | |
| 253 | |
| 254 const char* BigintOperations::ToHexCString(intptr_t length, | |
| 255 bool is_negative, | |
| 256 void* data, | |
| 257 uword (*allocator)(intptr_t size)) { | |
| 258 NoGCScope no_gc; | |
| 259 | |
| 260 ASSERT(kDigitBitSize % 4 == 0); | |
| 261 | |
| 262 // Conservative maximum chunk length. | |
| 263 const intptr_t kMaxChunkLen = | |
| 264 (kIntptrMax - 2 /* 0x */ | |
| 265 - 1 /* trailing '\0' */ | |
| 266 - 1 /* leading '-' */) / kHexCharsPerDigit; | |
| 267 const intptr_t chunk_length = length; | |
| 268 // Conservative check assuming leading bigint-digit also takes up | |
| 269 // kHexCharsPerDigit. | |
| 270 if (chunk_length > kMaxChunkLen) { | |
| 271 FATAL("Fatal error in BigintOperations::ToHexCString: string too long"); | |
| 272 } | |
| 273 Chunk* chunk_data = reinterpret_cast<Chunk*>(data); | |
| 274 if (length == 0) { | |
| 275 const char* zero = "0x0"; | |
| 276 const intptr_t kLength = strlen(zero); | |
| 277 char* result = reinterpret_cast<char*>(allocator(kLength + 1)); | |
| 278 ASSERT(result != NULL); | |
| 279 memmove(result, zero, kLength); | |
| 280 result[kLength] = '\0'; | |
| 281 return result; | |
| 282 } | |
| 283 ASSERT(chunk_data != NULL); | |
| 284 | |
| 285 // Compute the number of hex-digits that are needed to represent the | |
| 286 // leading bigint-digit. All other digits need exactly kHexCharsPerDigit | |
| 287 // characters. | |
| 288 intptr_t leading_hex_digits = 0; | |
| 289 Chunk leading_digit = chunk_data[chunk_length - 1]; | |
| 290 while (leading_digit != 0) { | |
| 291 leading_hex_digits++; | |
| 292 leading_digit >>= 4; | |
| 293 } | |
| 294 // Sum up the space that is needed for the string-representation. | |
| 295 intptr_t required_size = 0; | |
| 296 if (is_negative) { | |
| 297 required_size++; // For the leading "-". | |
| 298 } | |
| 299 required_size += 2; // For the "0x". | |
| 300 required_size += leading_hex_digits; | |
| 301 required_size += (chunk_length - 1) * kHexCharsPerDigit; | |
| 302 required_size++; // For the trailing '\0'. | |
| 303 char* result = reinterpret_cast<char*>(allocator(required_size)); | |
| 304 // Print the number into the string. | |
| 305 // Start from the last position. | |
| 306 intptr_t pos = required_size - 1; | |
| 307 result[pos--] = '\0'; | |
| 308 for (intptr_t i = 0; i < (chunk_length - 1); i++) { | |
| 309 // Print all non-leading characters (which are printed with | |
| 310 // kHexCharsPerDigit characters. | |
| 311 Chunk digit = chunk_data[i]; | |
| 312 for (intptr_t j = 0; j < kHexCharsPerDigit; j++) { | |
| 313 result[pos--] = Utils::IntToHexDigit(static_cast<int>(digit & 0xF)); | |
| 314 digit >>= 4; | |
| 315 } | |
| 316 } | |
| 317 // Print the leading digit. | |
| 318 leading_digit = chunk_data[chunk_length - 1]; | |
| 319 while (leading_digit != 0) { | |
| 320 result[pos--] = Utils::IntToHexDigit(static_cast<int>(leading_digit & 0xF)); | |
| 321 leading_digit >>= 4; | |
| 322 } | |
| 323 result[pos--] = 'x'; | |
| 324 result[pos--] = '0'; | |
| 325 if (is_negative) { | |
| 326 result[pos--] = '-'; | |
| 327 } | |
| 328 ASSERT(pos == -1); | |
| 329 return result; | |
| 330 } | |
| 331 | |
| 332 | |
| 333 const char* BigintOperations::ToHexCString(const Bigint& bigint, | |
| 334 uword (*allocator)(intptr_t size)) { | |
| 335 NoGCScope no_gc; | |
| 336 | |
| 337 intptr_t length = bigint.Length(); | |
| 338 return ToHexCString(length, | |
| 339 bigint.IsNegative(), | |
| 340 length ? bigint.ChunkAddr(0) : NULL, | |
| 341 allocator); | |
| 342 } | |
| 343 | |
| 344 | |
| 345 const char* BigintOperations::ToDecimalCString( | |
| 346 const Bigint& bigint, uword (*allocator)(intptr_t size)) { | |
| 347 // log10(2) ~= 0.30102999566398114. | |
| 348 const intptr_t kLog2Dividend = 30103; | |
| 349 const intptr_t kLog2Divisor = 100000; | |
| 350 // We remove a small constant for rounding imprecision, the \0 character and | |
| 351 // the negative sign. | |
| 352 const intptr_t kMaxAllowedDigitLength = | |
| 353 (kIntptrMax - 10) / kLog2Dividend / kDigitBitSize * kLog2Divisor; | |
| 354 | |
| 355 const intptr_t length = bigint.Length(); | |
| 356 Isolate* isolate = Isolate::Current(); | |
| 357 if (length >= kMaxAllowedDigitLength) { | |
| 358 // Use the preallocated out of memory exception to avoid calling | |
| 359 // into dart code or allocating any code. | |
| 360 const Instance& exception = | |
| 361 Instance::Handle(isolate->object_store()->out_of_memory()); | |
| 362 Exceptions::Throw(isolate, exception); | |
| 363 UNREACHABLE(); | |
| 364 } | |
| 365 | |
| 366 // Approximate the size of the resulting string. We prefer overestimating | |
| 367 // to not allocating enough. | |
| 368 int64_t bit_length = length * kDigitBitSize; | |
| 369 ASSERT(bit_length > length || length == 0); | |
| 370 int64_t decimal_length = (bit_length * kLog2Dividend / kLog2Divisor) + 1; | |
| 371 // Add one byte for the trailing \0 character. | |
| 372 int64_t required_size = decimal_length + 1; | |
| 373 if (bigint.IsNegative()) { | |
| 374 required_size++; | |
| 375 } | |
| 376 ASSERT(required_size == static_cast<intptr_t>(required_size)); | |
| 377 // We will fill the result in the inverse order and then exchange at the end. | |
| 378 char* result = | |
| 379 reinterpret_cast<char*>(allocator(static_cast<intptr_t>(required_size))); | |
| 380 ASSERT(result != NULL); | |
| 381 intptr_t result_pos = 0; | |
| 382 | |
| 383 // We divide the input into pieces of ~27 bits which can be efficiently | |
| 384 // handled. | |
| 385 const intptr_t kChunkDivisor = 100000000; | |
| 386 const int kChunkDigits = 8; | |
| 387 ASSERT(pow(10.0, kChunkDigits) == kChunkDivisor); | |
| 388 ASSERT(static_cast<Chunk>(kChunkDivisor) < kDigitMaxValue); | |
| 389 ASSERT(Smi::IsValid(kChunkDivisor)); | |
| 390 const Chunk divisor = static_cast<Chunk>(kChunkDivisor); | |
| 391 | |
| 392 // Rest contains the remaining bigint that needs to be printed. | |
| 393 const Bigint& rest = Bigint::Handle(Copy(bigint)); | |
| 394 while (!rest.IsZero()) { | |
| 395 Chunk remainder = InplaceUnsignedDivideRemainderDigit(rest, divisor); | |
| 396 intptr_t part = static_cast<intptr_t>(remainder); | |
| 397 for (int i = 0; i < kChunkDigits; i++) { | |
| 398 result[result_pos++] = '0' + (part % 10); | |
| 399 part /= 10; | |
| 400 } | |
| 401 ASSERT(part == 0); | |
| 402 } | |
| 403 // Add a leading zero, so that we have at least one digit. | |
| 404 result[result_pos++] = '0'; | |
| 405 // Move the resulting position back until we don't have any zeroes anymore | |
| 406 // or we reach the first digit. This is done so that we can remove all | |
| 407 // redundant leading zeroes. | |
| 408 while (result_pos > 1 && result[result_pos - 1] == '0') { | |
| 409 result_pos--; | |
| 410 } | |
| 411 if (bigint.IsNegative()) { | |
| 412 result[result_pos++] = '-'; | |
| 413 } | |
| 414 // Reverse the string. | |
| 415 int i = 0; | |
| 416 int j = result_pos - 1; | |
| 417 while (i < j) { | |
| 418 char tmp = result[i]; | |
| 419 result[i] = result[j]; | |
| 420 result[j] = tmp; | |
| 421 i++; | |
| 422 j--; | |
| 423 } | |
| 424 ASSERT(result_pos >= 0); | |
| 425 result[result_pos] = '\0'; | |
| 426 return result; | |
| 427 } | |
| 428 | |
| 429 | |
| 430 bool BigintOperations::FitsIntoSmi(const Bigint& bigint) { | |
| 431 intptr_t bigint_length = bigint.Length(); | |
| 432 if (bigint_length == 0) { | |
| 433 return true; | |
| 434 } | |
| 435 if ((bigint_length == 1) && | |
| 436 (static_cast<size_t>(kDigitBitSize) < | |
| 437 (sizeof(intptr_t) * kBitsPerByte))) { | |
| 438 return true; | |
| 439 } | |
| 440 | |
| 441 uintptr_t limit; | |
| 442 if (bigint.IsNegative()) { | |
| 443 limit = static_cast<uintptr_t>(-Smi::kMinValue); | |
| 444 } else { | |
| 445 limit = static_cast<uintptr_t>(Smi::kMaxValue); | |
| 446 } | |
| 447 bool bigint_is_greater = false; | |
| 448 // Consume the least-significant digits of the bigint. | |
| 449 // If bigint_is_greater is set, then the processed sub-part of the bigint is | |
| 450 // greater than the corresponding part of the limit. | |
| 451 for (intptr_t i = 0; i < bigint_length - 1; i++) { | |
| 452 Chunk limit_digit = static_cast<Chunk>(limit & kDigitMask); | |
| 453 Chunk bigint_digit = bigint.GetChunkAt(i); | |
| 454 if (limit_digit < bigint_digit) { | |
| 455 bigint_is_greater = true; | |
| 456 } else if (limit_digit > bigint_digit) { | |
| 457 bigint_is_greater = false; | |
| 458 } // else don't change the boolean. | |
| 459 limit >>= kDigitBitSize; | |
| 460 | |
| 461 // Bail out if the bigint is definitely too big. | |
| 462 if (limit == 0) { | |
| 463 return false; | |
| 464 } | |
| 465 } | |
| 466 Chunk most_significant_digit = bigint.GetChunkAt(bigint_length - 1); | |
| 467 if (limit > most_significant_digit) { | |
| 468 return true; | |
| 469 } | |
| 470 if (limit < most_significant_digit) { | |
| 471 return false; | |
| 472 } | |
| 473 return !bigint_is_greater; | |
| 474 } | |
| 475 | |
| 476 | |
| 477 RawSmi* BigintOperations::ToSmi(const Bigint& bigint) { | |
| 478 ASSERT(FitsIntoSmi(bigint)); | |
| 479 intptr_t value = 0; | |
| 480 for (intptr_t i = bigint.Length() - 1; i >= 0; i--) { | |
| 481 value <<= kDigitBitSize; | |
| 482 value += static_cast<intptr_t>(bigint.GetChunkAt(i)); | |
| 483 } | |
| 484 if (bigint.IsNegative()) { | |
| 485 value = -value; | |
| 486 } | |
| 487 return Smi::New(value); | |
| 488 } | |
| 489 | |
| 490 | |
| 491 static double Uint64ToDouble(uint64_t x) { | |
| 492 #if _WIN64 | |
| 493 // For static_cast<double>(x) MSVC x64 generates | |
| 494 // | |
| 495 // cvtsi2sd xmm0, rax | |
| 496 // test rax, rax | |
| 497 // jns done | |
| 498 // addsd xmm0, static_cast<double>(2^64) | |
| 499 // done: | |
| 500 // | |
| 501 // while GCC -m64 generates | |
| 502 // | |
| 503 // test rax, rax | |
| 504 // js negative | |
| 505 // cvtsi2sd xmm0, rax | |
| 506 // jmp done | |
| 507 // negative: | |
| 508 // mov rdx, rax | |
| 509 // shr rdx, 1 | |
| 510 // and eax, 0x1 | |
| 511 // or rdx, rax | |
| 512 // cvtsi2sd xmm0, rdx | |
| 513 // addsd xmm0, xmm0 | |
| 514 // done: | |
| 515 // | |
| 516 // which results in a different rounding. | |
| 517 // | |
| 518 // For consistency between platforms fallback to GCC style converstion | |
| 519 // on Win64. | |
| 520 // | |
| 521 const int64_t y = static_cast<int64_t>(x); | |
| 522 if (y > 0) { | |
| 523 return static_cast<double>(y); | |
| 524 } else { | |
| 525 const double half = static_cast<double>( | |
| 526 static_cast<int64_t>(x >> 1) | (y & 1)); | |
| 527 return half + half; | |
| 528 } | |
| 529 #else | |
| 530 return static_cast<double>(x); | |
| 531 #endif | |
| 532 } | |
| 533 | |
| 534 | |
| 535 RawDouble* BigintOperations::ToDouble(const Bigint& bigint) { | |
| 536 ASSERT(IsClamped(bigint)); | |
| 537 if (bigint.IsZero()) { | |
| 538 return Double::New(0.0); | |
| 539 } | |
| 540 if (AbsFitsIntoUint64(bigint)) { | |
| 541 double absolute_value = Uint64ToDouble(AbsToUint64(bigint)); | |
| 542 double result = bigint.IsNegative() ? -absolute_value : absolute_value; | |
| 543 return Double::New(result); | |
| 544 } | |
| 545 | |
| 546 static const int kPhysicalSignificandSize = 52; | |
| 547 // The significand size has an additional hidden bit. | |
| 548 static const int kSignificandSize = kPhysicalSignificandSize + 1; | |
| 549 static const int kExponentBias = 0x3FF + kPhysicalSignificandSize; | |
| 550 static const int kMaxExponent = 0x7FF - kExponentBias; | |
| 551 static const uint64_t kOne64 = 1; | |
| 552 static const uint64_t kInfinityBits = | |
| 553 DART_2PART_UINT64_C(0x7FF00000, 00000000); | |
| 554 | |
| 555 // A double is composed of an exponent e and a significand s. Its value equals | |
| 556 // s * 2^e. The significand has 53 bits of which the first one must always be | |
| 557 // 1 (at least for then numbers we are working with here) and is therefore | |
| 558 // omitted. The physical size of the significand is thus 52 bits. | |
| 559 // The exponent has 11 bits and is biased by 0x3FF + 52. For example an | |
| 560 // exponent e = 10 is written as 0x3FF + 52 + 10 (in the 11 bits that are | |
| 561 // reserved for the exponent). | |
| 562 // When converting the given bignum to a double we have to pay attention to | |
| 563 // the rounding. In particular we have to decide which double to pick if an | |
| 564 // input lies exactly between two doubles. As usual with double operations | |
| 565 // we pick the double with an even significand in such cases. | |
| 566 // | |
| 567 // General approach of this algorithm: Get 54 bits (one more than the | |
| 568 // significand size) of the bigint. If the last bit is then 1, then (without | |
| 569 // knowledge of the remaining bits) we could have a half-way number. | |
| 570 // If the second-to-last bit is odd then we know that we have to round up: | |
| 571 // if the remaining bits are not zero then the input lies closer to the higher | |
| 572 // double. If the remaining bits are zero then we have a half-way case and | |
| 573 // we need to round up too (rounding to the even double). | |
| 574 // If the second-to-last bit is even then we need to look at the remaining | |
| 575 // bits to determine if any of them is not zero. If that's the case then the | |
| 576 // number lies closer to the next-higher double. Otherwise we round the | |
| 577 // half-way case down to even. | |
| 578 | |
| 579 intptr_t length = bigint.Length(); | |
| 580 if (((length - 1) * kDigitBitSize) > (kMaxExponent + kSignificandSize)) { | |
| 581 // Does not fit into a double. | |
| 582 double infinity = bit_cast<double>(kInfinityBits); | |
| 583 return Double::New(bigint.IsNegative() ? -infinity : infinity); | |
| 584 } | |
| 585 | |
| 586 | |
| 587 intptr_t digit_index = length - 1; | |
| 588 // In order to round correctly we need to look at half-way cases. Therefore we | |
| 589 // get kSignificandSize + 1 bits. If the last bit is 1 then we have to look | |
| 590 // at the remaining bits to know if we have to round up. | |
| 591 int needed_bits = kSignificandSize + 1; | |
| 592 ASSERT((kDigitBitSize < needed_bits) && (2 * kDigitBitSize >= needed_bits)); | |
| 593 bool discarded_bits_were_zero = true; | |
| 594 | |
| 595 Chunk firstDigit = bigint.GetChunkAt(digit_index--); | |
| 596 uint64_t twice_significand_floor = firstDigit; | |
| 597 intptr_t twice_significant_exponent = (digit_index + 1) * kDigitBitSize; | |
| 598 needed_bits -= CountBits(firstDigit); | |
| 599 | |
| 600 if (needed_bits >= kDigitBitSize) { | |
| 601 twice_significand_floor <<= kDigitBitSize; | |
| 602 twice_significand_floor |= bigint.GetChunkAt(digit_index--); | |
| 603 twice_significant_exponent -= kDigitBitSize; | |
| 604 needed_bits -= kDigitBitSize; | |
| 605 } | |
| 606 if (needed_bits > 0) { | |
| 607 ASSERT(needed_bits <= kDigitBitSize); | |
| 608 Chunk digit = bigint.GetChunkAt(digit_index--); | |
| 609 int discarded_bits_count = kDigitBitSize - needed_bits; | |
| 610 twice_significand_floor <<= needed_bits; | |
| 611 twice_significand_floor |= digit >> discarded_bits_count; | |
| 612 twice_significant_exponent -= needed_bits; | |
| 613 uint64_t discarded_bits_mask = (kOne64 << discarded_bits_count) - 1; | |
| 614 discarded_bits_were_zero = ((digit & discarded_bits_mask) == 0); | |
| 615 } | |
| 616 ASSERT((twice_significand_floor >> kSignificandSize) == 1); | |
| 617 | |
| 618 // We might need to round up the significand later. | |
| 619 uint64_t significand = twice_significand_floor >> 1; | |
| 620 intptr_t exponent = twice_significant_exponent + 1; | |
| 621 | |
| 622 if (exponent >= kMaxExponent) { | |
| 623 // Infinity. | |
| 624 // Does not fit into a double. | |
| 625 double infinity = bit_cast<double>(kInfinityBits); | |
| 626 return Double::New(bigint.IsNegative() ? -infinity : infinity); | |
| 627 } | |
| 628 | |
| 629 if ((twice_significand_floor & 1) == 1) { | |
| 630 bool round_up = false; | |
| 631 | |
| 632 if ((significand & 1) != 0 || !discarded_bits_were_zero) { | |
| 633 // Even if the remaining bits are zero we still need to round up since we | |
| 634 // want to round to even for half-way cases. | |
| 635 round_up = true; | |
| 636 } else { | |
| 637 // Could be a half-way case. See if the remaining bits are non-zero. | |
| 638 for (intptr_t i = 0; i <= digit_index; i++) { | |
| 639 if (bigint.GetChunkAt(i) != 0) { | |
| 640 round_up = true; | |
| 641 break; | |
| 642 } | |
| 643 } | |
| 644 } | |
| 645 | |
| 646 if (round_up) { | |
| 647 significand++; | |
| 648 // It might be that we just went from 53 bits to 54 bits. | |
| 649 // Example: After adding 1 to 1FFF..FF (with 53 bits set to 1) we have | |
| 650 // 2000..00 (= 2 ^ 54). When adding the exponent and significand together | |
| 651 // this will increase the exponent by 1 which is exactly what we want. | |
| 652 } | |
| 653 } | |
| 654 | |
| 655 ASSERT((significand >> (kSignificandSize - 1)) == 1 | |
| 656 || significand == kOne64 << kSignificandSize); | |
| 657 uint64_t biased_exponent = exponent + kExponentBias; | |
| 658 // The significand still has the hidden bit. We simply decrement the biased | |
| 659 // exponent by one instead of playing around with the significand. | |
| 660 biased_exponent--; | |
| 661 // Note that we must use the plus operator instead of bit-or. | |
| 662 uint64_t double_bits = | |
| 663 (biased_exponent << kPhysicalSignificandSize) + significand; | |
| 664 | |
| 665 double value = bit_cast<double>(double_bits); | |
| 666 if (bigint.IsNegative()) { | |
| 667 value = -value; | |
| 668 } | |
| 669 return Double::New(value); | |
| 670 } | |
| 671 | |
| 672 | |
| 673 bool BigintOperations::FitsIntoInt64(const Bigint& bigint) { | |
| 674 intptr_t bigint_length = bigint.Length(); | |
| 675 if (bigint_length == 0) { | |
| 676 return true; | |
| 677 } | |
| 678 if ((bigint_length < 3) && | |
| 679 (static_cast<size_t>(kDigitBitSize) < | |
| 680 (sizeof(intptr_t) * kBitsPerByte))) { | |
| 681 return true; | |
| 682 } | |
| 683 | |
| 684 uint64_t limit; | |
| 685 if (bigint.IsNegative()) { | |
| 686 limit = static_cast<uint64_t>(Mint::kMinValue); | |
| 687 } else { | |
| 688 limit = static_cast<uint64_t>(Mint::kMaxValue); | |
| 689 } | |
| 690 bool bigint_is_greater = false; | |
| 691 // Consume the least-significant digits of the bigint. | |
| 692 // If bigint_is_greater is set, then the processed sub-part of the bigint is | |
| 693 // greater than the corresponding part of the limit. | |
| 694 for (intptr_t i = 0; i < bigint_length - 1; i++) { | |
| 695 Chunk limit_digit = static_cast<Chunk>(limit & kDigitMask); | |
| 696 Chunk bigint_digit = bigint.GetChunkAt(i); | |
| 697 if (limit_digit < bigint_digit) { | |
| 698 bigint_is_greater = true; | |
| 699 } else if (limit_digit > bigint_digit) { | |
| 700 bigint_is_greater = false; | |
| 701 } // else don't change the boolean. | |
| 702 limit >>= kDigitBitSize; | |
| 703 | |
| 704 // Bail out if the bigint is definitely too big. | |
| 705 if (limit == 0) { | |
| 706 return false; | |
| 707 } | |
| 708 } | |
| 709 Chunk most_significant_digit = bigint.GetChunkAt(bigint_length - 1); | |
| 710 if (limit > most_significant_digit) { | |
| 711 return true; | |
| 712 } | |
| 713 if (limit < most_significant_digit) { | |
| 714 return false; | |
| 715 } | |
| 716 return !bigint_is_greater; | |
| 717 } | |
| 718 | |
| 719 | |
| 720 uint64_t BigintOperations::AbsToUint64(const Bigint& bigint) { | |
| 721 ASSERT(AbsFitsIntoUint64(bigint)); | |
| 722 uint64_t value = 0; | |
| 723 for (intptr_t i = bigint.Length() - 1; i >= 0; i--) { | |
| 724 value <<= kDigitBitSize; | |
| 725 value += static_cast<intptr_t>(bigint.GetChunkAt(i)); | |
| 726 } | |
| 727 return value; | |
| 728 } | |
| 729 | |
| 730 | |
| 731 int64_t BigintOperations::ToInt64(const Bigint& bigint) { | |
| 732 if (bigint.IsZero()) { | |
| 733 return 0; | |
| 734 } | |
| 735 ASSERT(FitsIntoInt64(bigint)); | |
| 736 int64_t value = AbsToUint64(bigint); | |
| 737 if (bigint.IsNegative()) { | |
| 738 value = -value; | |
| 739 } | |
| 740 return value; | |
| 741 } | |
| 742 | |
| 743 | |
| 744 uint32_t BigintOperations::TruncateToUint32(const Bigint& bigint) { | |
| 745 uint32_t value = 0; | |
| 746 for (intptr_t i = bigint.Length() - 1; i >= 0; i--) { | |
| 747 value <<= kDigitBitSize; | |
| 748 value += static_cast<uint32_t>(bigint.GetChunkAt(i)); | |
| 749 } | |
| 750 return value; | |
| 751 } | |
| 752 | |
| 753 | |
| 754 bool BigintOperations::AbsFitsIntoUint64(const Bigint& bigint) { | |
| 755 if (bigint.IsZero()) { | |
| 756 return true; | |
| 757 } | |
| 758 intptr_t b_length = bigint.Length(); | |
| 759 intptr_t num_bits = CountBits(bigint.GetChunkAt(b_length - 1)); | |
| 760 num_bits += (kDigitBitSize * (b_length - 1)); | |
| 761 if (num_bits > 64) return false; | |
| 762 return true; | |
| 763 } | |
| 764 | |
| 765 | |
| 766 bool BigintOperations::FitsIntoUint64(const Bigint& bigint) { | |
| 767 if (bigint.IsNegative()) return false; | |
| 768 return AbsFitsIntoUint64(bigint); | |
| 769 } | |
| 770 | |
| 771 | |
| 772 uint64_t BigintOperations::ToUint64(const Bigint& bigint) { | |
| 773 ASSERT(FitsIntoUint64(bigint)); | |
| 774 return AbsToUint64(bigint); | |
| 775 } | |
| 776 | |
| 777 | |
| 778 RawBigint* BigintOperations::Multiply(const Bigint& a, const Bigint& b) { | |
| 779 ASSERT(IsClamped(a)); | |
| 780 ASSERT(IsClamped(b)); | |
| 781 | |
| 782 intptr_t a_length = a.Length(); | |
| 783 intptr_t b_length = b.Length(); | |
| 784 intptr_t result_length = a_length + b_length; | |
| 785 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 786 | |
| 787 if (a.IsNegative() != b.IsNegative()) { | |
| 788 result.ToggleSign(); | |
| 789 } | |
| 790 | |
| 791 // Comba multiplication: compute each column separately. | |
| 792 // Example: r = a2a1a0 * b2b1b0. | |
| 793 // r = 1 * a0b0 + | |
| 794 // 10 * (a1b0 + a0b1) + | |
| 795 // 100 * (a2b0 + a1b1 + a0b2) + | |
| 796 // 1000 * (a2b1 + a1b2) + | |
| 797 // 10000 * a2b2 | |
| 798 // | |
| 799 // Each column will be accumulated in an integer of type DoubleChunk. We must | |
| 800 // guarantee that the column-sum will not overflow. We achieve this by | |
| 801 // 'blocking' the sum into overflow-free sums followed by propagating the | |
| 802 // overflow. | |
| 803 // | |
| 804 // Each bigint digit fits in kDigitBitSize bits. | |
| 805 // Each product fits in 2*kDigitBitSize bits. | |
| 806 // The accumulator is 8 * sizeof(DoubleChunk) == 2*kDigitBitSize + kCarryBits. | |
| 807 // | |
| 808 // Each time we add a product to the accumulator it could carry one bit into | |
| 809 // the carry bits, supporting kBlockSize = 2^kCarryBits - 1 addition | |
| 810 // operations before the DoubleChunk overflows. | |
| 811 // | |
| 812 // At the end of the column sum and after each batch of kBlockSize additions | |
| 813 // the high kCarryBits+kDigitBitSize of accumulator are flushed to | |
| 814 // accumulator_overflow. | |
| 815 // | |
| 816 // Diagramatically, using one char per 4 bits: | |
| 817 // | |
| 818 // 0aaaaaaa * 0bbbbbbb -> 00pppppppppppppp product of 2 digits | |
| 819 // | | |
| 820 // + ...added to | |
| 821 // v | |
| 822 // ccSSSSSSSsssssss accumulator | |
| 823 // ...flushed to | |
| 824 // 000000000sssssss accumulator | |
| 825 // vvvvvvvvvVVVVVVV accumulator_overflow | |
| 826 // | |
| 827 // 'sssssss' becomes the column sum an overflow is carried to next column: | |
| 828 // | |
| 829 // 000000000VVVVVVV accumulator | |
| 830 // 0000000vvvvvvvvv accumulator_overflow | |
| 831 // | |
| 832 // accumulator_overflow supports 2^(kDigitBitSize + kCarryBits) additions of | |
| 833 // products. | |
| 834 // | |
| 835 // Since the bottom (kDigitBitSize + kCarryBits) bits of accumulator_overflow | |
| 836 // are initialized from the previous column, that uses up the capacity to | |
| 837 // absorb 2^kCarryBits additions. The accumulator_overflow can overflow if | |
| 838 // the column has more than 2^(kDigitBitSize + kCarryBits) - 2^kCarryBits | |
| 839 // elements With current configuration that is 2^36-2^8 elements. That is too | |
| 840 // high to happen in practice. Comba multiplication is O(N^2) so overflow | |
| 841 // won't happen during a human lifespan. | |
| 842 | |
| 843 const intptr_t kCarryBits = 8 * sizeof(DoubleChunk) - 2 * kDigitBitSize; | |
| 844 const intptr_t kBlockSize = (1 << kCarryBits) - 1; | |
| 845 | |
| 846 DoubleChunk accumulator = 0; // Accumulates the result of one column. | |
| 847 DoubleChunk accumulator_overflow = 0; | |
| 848 for (intptr_t i = 0; i < result_length; i++) { | |
| 849 // Example: r = a2a1a0 * b2b1b0. | |
| 850 // For i == 0, compute a0b0. | |
| 851 // i == 1, a1b0 + a0b1 + overflow from i == 0. | |
| 852 // i == 2, a2b0 + a1b1 + a0b2 + overflow from i == 1. | |
| 853 // ... | |
| 854 // The indices into a and b are such that their sum equals i. | |
| 855 intptr_t a_index = Utils::Minimum(a_length - 1, i); | |
| 856 intptr_t b_index = i - a_index; | |
| 857 ASSERT(a_index + b_index == i); | |
| 858 | |
| 859 // Instead of testing for a_index >= 0 && b_index < b_length we compute the | |
| 860 // number of iterations first. | |
| 861 intptr_t iterations = Utils::Minimum(b_length - b_index, a_index + 1); | |
| 862 | |
| 863 // For large products we need extra bit for the overflow. The sum is broken | |
| 864 // into blocks to avoid dealing with the overflow on each iteration. | |
| 865 for (intptr_t j_block = 0; j_block < iterations; j_block += kBlockSize) { | |
| 866 intptr_t j_end = Utils::Minimum(j_block + kBlockSize, iterations); | |
| 867 for (intptr_t j = j_block; j < j_end; j++) { | |
| 868 DoubleChunk chunk_a = a.GetChunkAt(a_index); | |
| 869 DoubleChunk chunk_b = b.GetChunkAt(b_index); | |
| 870 accumulator += chunk_a * chunk_b; | |
| 871 a_index--; | |
| 872 b_index++; | |
| 873 } | |
| 874 accumulator_overflow += (accumulator >> kDigitBitSize); | |
| 875 accumulator &= kDigitMask; | |
| 876 } | |
| 877 result.SetChunkAt(i, static_cast<Chunk>(accumulator)); | |
| 878 // Overflow becomes the initial accumulator for the next column. | |
| 879 accumulator = accumulator_overflow & kDigitMask; | |
| 880 // And the overflow from the overflow becomes the new overflow. | |
| 881 accumulator_overflow = (accumulator_overflow >> kDigitBitSize); | |
| 882 } | |
| 883 ASSERT(accumulator == 0); | |
| 884 ASSERT(accumulator_overflow == 0); | |
| 885 | |
| 886 Clamp(result); | |
| 887 return result.raw(); | |
| 888 } | |
| 889 | |
| 890 | |
| 891 RawBigint* BigintOperations::Divide(const Bigint& a, const Bigint& b) { | |
| 892 Bigint& quotient = Bigint::Handle(); | |
| 893 Bigint& remainder = Bigint::Handle(); | |
| 894 DivideRemainder(a, b, "ient, &remainder); | |
| 895 return quotient.raw(); | |
| 896 } | |
| 897 | |
| 898 | |
| 899 RawBigint* BigintOperations::Modulo(const Bigint& a, const Bigint& b) { | |
| 900 Bigint& quotient = Bigint::Handle(); | |
| 901 Bigint& remainder = Bigint::Handle(); | |
| 902 DivideRemainder(a, b, "ient, &remainder); | |
| 903 // Emulating code in Integer::ArithmeticOp (Euclidian modulo). | |
| 904 if (remainder.IsNegative()) { | |
| 905 if (b.IsNegative()) { | |
| 906 return BigintOperations::Subtract(remainder, b); | |
| 907 } else { | |
| 908 return BigintOperations::Add(remainder, b); | |
| 909 } | |
| 910 } | |
| 911 return remainder.raw(); | |
| 912 } | |
| 913 | |
| 914 | |
| 915 RawBigint* BigintOperations::Remainder(const Bigint& a, const Bigint& b) { | |
| 916 Bigint& quotient = Bigint::Handle(); | |
| 917 Bigint& remainder = Bigint::Handle(); | |
| 918 DivideRemainder(a, b, "ient, &remainder); | |
| 919 return remainder.raw(); | |
| 920 } | |
| 921 | |
| 922 | |
| 923 RawBigint* BigintOperations::ShiftLeft(const Bigint& bigint, intptr_t amount) { | |
| 924 ASSERT(IsClamped(bigint)); | |
| 925 ASSERT(amount >= 0); | |
| 926 intptr_t bigint_length = bigint.Length(); | |
| 927 if (bigint.IsZero()) { | |
| 928 return Zero(); | |
| 929 } | |
| 930 // TODO(floitsch): can we reuse the input? | |
| 931 if (amount == 0) { | |
| 932 return Copy(bigint); | |
| 933 } | |
| 934 intptr_t digit_shift = amount / kDigitBitSize; | |
| 935 intptr_t bit_shift = amount % kDigitBitSize; | |
| 936 if (bit_shift == 0) { | |
| 937 const Bigint& result = | |
| 938 Bigint::Handle(Bigint::Allocate(bigint_length + digit_shift)); | |
| 939 for (intptr_t i = 0; i < digit_shift; i++) { | |
| 940 result.SetChunkAt(i, 0); | |
| 941 } | |
| 942 for (intptr_t i = 0; i < bigint_length; i++) { | |
| 943 result.SetChunkAt(i + digit_shift, bigint.GetChunkAt(i)); | |
| 944 } | |
| 945 if (bigint.IsNegative()) { | |
| 946 result.ToggleSign(); | |
| 947 } | |
| 948 return result.raw(); | |
| 949 } else { | |
| 950 const Bigint& result = | |
| 951 Bigint::Handle(Bigint::Allocate(bigint_length + digit_shift + 1)); | |
| 952 for (intptr_t i = 0; i < digit_shift; i++) { | |
| 953 result.SetChunkAt(i, 0); | |
| 954 } | |
| 955 Chunk carry = 0; | |
| 956 for (intptr_t i = 0; i < bigint_length; i++) { | |
| 957 Chunk digit = bigint.GetChunkAt(i); | |
| 958 Chunk shifted_digit = ((digit << bit_shift) & kDigitMask) + carry; | |
| 959 result.SetChunkAt(i + digit_shift, shifted_digit); | |
| 960 carry = digit >> (kDigitBitSize - bit_shift); | |
| 961 } | |
| 962 result.SetChunkAt(bigint_length + digit_shift, carry); | |
| 963 if (bigint.IsNegative()) { | |
| 964 result.ToggleSign(); | |
| 965 } | |
| 966 Clamp(result); | |
| 967 return result.raw(); | |
| 968 } | |
| 969 } | |
| 970 | |
| 971 | |
| 972 RawBigint* BigintOperations::ShiftRight(const Bigint& bigint, intptr_t amount) { | |
| 973 ASSERT(IsClamped(bigint)); | |
| 974 ASSERT(amount >= 0); | |
| 975 intptr_t bigint_length = bigint.Length(); | |
| 976 if (bigint.IsZero()) { | |
| 977 return Zero(); | |
| 978 } | |
| 979 // TODO(floitsch): can we reuse the input? | |
| 980 if (amount == 0) { | |
| 981 return Copy(bigint); | |
| 982 } | |
| 983 intptr_t digit_shift = amount / kDigitBitSize; | |
| 984 intptr_t bit_shift = amount % kDigitBitSize; | |
| 985 if (digit_shift >= bigint_length) { | |
| 986 return bigint.IsNegative() ? MinusOne() : Zero(); | |
| 987 } | |
| 988 | |
| 989 const Bigint& result = | |
| 990 Bigint::Handle(Bigint::Allocate(bigint_length - digit_shift)); | |
| 991 if (bit_shift == 0) { | |
| 992 for (intptr_t i = 0; i < bigint_length - digit_shift; i++) { | |
| 993 result.SetChunkAt(i, bigint.GetChunkAt(i + digit_shift)); | |
| 994 } | |
| 995 } else { | |
| 996 Chunk carry = 0; | |
| 997 for (intptr_t i = bigint_length - 1; i >= digit_shift; i--) { | |
| 998 Chunk digit = bigint.GetChunkAt(i); | |
| 999 Chunk shifted_digit = (digit >> bit_shift) + carry; | |
| 1000 result.SetChunkAt(i - digit_shift, shifted_digit); | |
| 1001 carry = (digit << (kDigitBitSize - bit_shift)) & kDigitMask; | |
| 1002 } | |
| 1003 Clamp(result); | |
| 1004 } | |
| 1005 | |
| 1006 if (bigint.IsNegative()) { | |
| 1007 result.ToggleSign(); | |
| 1008 // If the input is negative then the result needs to be rounded down. | |
| 1009 // Example: -5 >> 2 => -2 | |
| 1010 bool needs_rounding = false; | |
| 1011 for (intptr_t i = 0; i < digit_shift; i++) { | |
| 1012 if (bigint.GetChunkAt(i) != 0) { | |
| 1013 needs_rounding = true; | |
| 1014 break; | |
| 1015 } | |
| 1016 } | |
| 1017 if (!needs_rounding && (bit_shift > 0)) { | |
| 1018 Chunk digit = bigint.GetChunkAt(digit_shift); | |
| 1019 needs_rounding = (digit << (kChunkBitSize - bit_shift)) != 0; | |
| 1020 } | |
| 1021 if (needs_rounding) { | |
| 1022 Bigint& one = Bigint::Handle(One()); | |
| 1023 return Subtract(result, one); | |
| 1024 } | |
| 1025 } | |
| 1026 | |
| 1027 return result.raw(); | |
| 1028 } | |
| 1029 | |
| 1030 | |
| 1031 RawBigint* BigintOperations::BitAnd(const Bigint& a, const Bigint& b) { | |
| 1032 ASSERT(IsClamped(a)); | |
| 1033 ASSERT(IsClamped(b)); | |
| 1034 | |
| 1035 if (a.IsZero() || b.IsZero()) { | |
| 1036 return Zero(); | |
| 1037 } | |
| 1038 if (a.IsNegative() && !b.IsNegative()) { | |
| 1039 return BitAnd(b, a); | |
| 1040 } | |
| 1041 if ((a.IsNegative() == b.IsNegative()) && (a.Length() < b.Length())) { | |
| 1042 return BitAnd(b, a); | |
| 1043 } | |
| 1044 | |
| 1045 intptr_t a_length = a.Length(); | |
| 1046 intptr_t b_length = b.Length(); | |
| 1047 intptr_t min_length = Utils::Minimum(a_length, b_length); | |
| 1048 intptr_t max_length = Utils::Maximum(a_length, b_length); | |
| 1049 if (!b.IsNegative()) { | |
| 1050 ASSERT(!a.IsNegative()); | |
| 1051 intptr_t result_length = min_length; | |
| 1052 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1053 | |
| 1054 for (intptr_t i = 0; i < min_length; i++) { | |
| 1055 result.SetChunkAt(i, a.GetChunkAt(i) & b.GetChunkAt(i)); | |
| 1056 } | |
| 1057 Clamp(result); | |
| 1058 return result.raw(); | |
| 1059 } | |
| 1060 | |
| 1061 // Bigints encode negative values by storing the absolute value and the sign | |
| 1062 // separately. To do bit operations we need to simulate numbers that are | |
| 1063 // implemented as two's complement. | |
| 1064 // The negation of a positive number x would be encoded as follows in | |
| 1065 // two's complement: n = ~(x - 1). | |
| 1066 // The inverse transformation is hence (~n) + 1. | |
| 1067 | |
| 1068 if (!a.IsNegative()) { | |
| 1069 ASSERT(b.IsNegative()); | |
| 1070 // The result will be positive. | |
| 1071 intptr_t result_length = a_length; | |
| 1072 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1073 Chunk borrow = 1; | |
| 1074 for (intptr_t i = 0; i < min_length; i++) { | |
| 1075 Chunk b_digit = b.GetChunkAt(i) - borrow; | |
| 1076 result.SetChunkAt(i, a.GetChunkAt(i) & (~b_digit) & kDigitMask); | |
| 1077 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1078 } | |
| 1079 for (intptr_t i = min_length; i < a_length; i++) { | |
| 1080 result.SetChunkAt(i, a.GetChunkAt(i) & (kDigitMaxValue - borrow)); | |
| 1081 borrow = 0; | |
| 1082 } | |
| 1083 Clamp(result); | |
| 1084 return result.raw(); | |
| 1085 } | |
| 1086 | |
| 1087 ASSERT(a.IsNegative()); | |
| 1088 ASSERT(b.IsNegative()); | |
| 1089 // The result will be negative. | |
| 1090 // We need to convert a and b to two's complement. Do the bit-operation there, | |
| 1091 // and transform the resulting bits from two's complement back to separated | |
| 1092 // magnitude and sign. | |
| 1093 // a & b is therefore computed as ~((~(a - 1)) & (~(b - 1))) + 1 which is | |
| 1094 // equal to ((a-1) | (b-1)) + 1. | |
| 1095 intptr_t result_length = max_length + 1; | |
| 1096 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1097 result.ToggleSign(); | |
| 1098 Chunk a_borrow = 1; | |
| 1099 Chunk b_borrow = 1; | |
| 1100 Chunk result_carry = 1; | |
| 1101 ASSERT(a_length >= b_length); | |
| 1102 for (intptr_t i = 0; i < b_length; i++) { | |
| 1103 Chunk a_digit = a.GetChunkAt(i) - a_borrow; | |
| 1104 Chunk b_digit = b.GetChunkAt(i) - b_borrow; | |
| 1105 Chunk result_chunk = ((a_digit | b_digit) & kDigitMask) + result_carry; | |
| 1106 result.SetChunkAt(i, result_chunk & kDigitMask); | |
| 1107 a_borrow = a_digit >> (kChunkBitSize - 1); | |
| 1108 b_borrow = b_digit >> (kChunkBitSize - 1); | |
| 1109 result_carry = result_chunk >> kDigitBitSize; | |
| 1110 } | |
| 1111 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1112 Chunk a_digit = a.GetChunkAt(i) - a_borrow; | |
| 1113 Chunk b_digit = -b_borrow; | |
| 1114 Chunk result_chunk = ((a_digit | b_digit) & kDigitMask) + result_carry; | |
| 1115 result.SetChunkAt(i, result_chunk & kDigitMask); | |
| 1116 a_borrow = a_digit >> (kChunkBitSize - 1); | |
| 1117 b_borrow = 0; | |
| 1118 result_carry = result_chunk >> kDigitBitSize; | |
| 1119 } | |
| 1120 Chunk a_digit = -a_borrow; | |
| 1121 Chunk b_digit = -b_borrow; | |
| 1122 Chunk result_chunk = ((a_digit | b_digit) & kDigitMask) + result_carry; | |
| 1123 result.SetChunkAt(a_length, result_chunk & kDigitMask); | |
| 1124 Clamp(result); | |
| 1125 return result.raw(); | |
| 1126 } | |
| 1127 | |
| 1128 | |
| 1129 RawBigint* BigintOperations::BitOr(const Bigint& a, const Bigint& b) { | |
| 1130 ASSERT(IsClamped(a)); | |
| 1131 ASSERT(IsClamped(b)); | |
| 1132 | |
| 1133 if (a.IsNegative() && !b.IsNegative()) { | |
| 1134 return BitOr(b, a); | |
| 1135 } | |
| 1136 if ((a.IsNegative() == b.IsNegative()) && (a.Length() < b.Length())) { | |
| 1137 return BitOr(b, a); | |
| 1138 } | |
| 1139 | |
| 1140 intptr_t a_length = a.Length(); | |
| 1141 intptr_t b_length = b.Length(); | |
| 1142 intptr_t min_length = Utils::Minimum(a_length, b_length); | |
| 1143 intptr_t max_length = Utils::Maximum(a_length, b_length); | |
| 1144 if (!b.IsNegative()) { | |
| 1145 ASSERT(!a.IsNegative()); | |
| 1146 intptr_t result_length = max_length; | |
| 1147 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1148 | |
| 1149 ASSERT(a_length >= b_length); | |
| 1150 for (intptr_t i = 0; i < b_length; i++) { | |
| 1151 result.SetChunkAt(i, a.GetChunkAt(i) | b.GetChunkAt(i)); | |
| 1152 } | |
| 1153 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1154 result.SetChunkAt(i, a.GetChunkAt(i)); | |
| 1155 } | |
| 1156 return result.raw(); | |
| 1157 } | |
| 1158 | |
| 1159 // Bigints encode negative values by storing the absolute value and the sign | |
| 1160 // separately. To do bit operations we need to simulate numbers that are | |
| 1161 // implemented as two's complement. | |
| 1162 // The negation of a positive number x would be encoded as follows in | |
| 1163 // two's complement: n = ~(x - 1). | |
| 1164 // The inverse transformation is hence (~n) + 1. | |
| 1165 | |
| 1166 if (!a.IsNegative()) { | |
| 1167 ASSERT(b.IsNegative()); | |
| 1168 if (a.IsZero()) { | |
| 1169 return Copy(b); | |
| 1170 } | |
| 1171 // The result will be negative. | |
| 1172 // We need to convert b to two's complement. Do the bit-operation there, | |
| 1173 // and transform the resulting bits from two's complement back to separated | |
| 1174 // magnitude and sign. | |
| 1175 // a | b is therefore computed as ~((a & (~(b - 1))) + 1 which is | |
| 1176 // equal to ((~a) & (b-1)) + 1. | |
| 1177 intptr_t result_length = b_length; | |
| 1178 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1179 result.ToggleSign(); | |
| 1180 Chunk borrow = 1; | |
| 1181 Chunk result_carry = 1; | |
| 1182 for (intptr_t i = 0; i < min_length; i++) { | |
| 1183 Chunk a_digit = a.GetChunkAt(i); | |
| 1184 Chunk b_digit = b.GetChunkAt(i) - borrow; | |
| 1185 Chunk result_digit = ((~a_digit) & b_digit & kDigitMask) + result_carry; | |
| 1186 result.SetChunkAt(i, result_digit & kDigitMask); | |
| 1187 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1188 result_carry = result_digit >> kDigitBitSize; | |
| 1189 } | |
| 1190 ASSERT(result_carry == 0); | |
| 1191 for (intptr_t i = min_length; i < b_length; i++) { | |
| 1192 Chunk b_digit = b.GetChunkAt(i) - borrow; | |
| 1193 Chunk result_digit = (b_digit & kDigitMask) + result_carry; | |
| 1194 result.SetChunkAt(i, result_digit & kDigitMask); | |
| 1195 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1196 result_carry = result_digit >> kDigitBitSize; | |
| 1197 } | |
| 1198 ASSERT(result_carry == 0); | |
| 1199 Clamp(result); | |
| 1200 return result.raw(); | |
| 1201 } | |
| 1202 | |
| 1203 ASSERT(a.IsNegative()); | |
| 1204 ASSERT(b.IsNegative()); | |
| 1205 // The result will be negative. | |
| 1206 // We need to convert a and b to two's complement. Do the bit-operation there, | |
| 1207 // and transform the resulting bits from two's complement back to separated | |
| 1208 // magnitude and sign. | |
| 1209 // a & b is therefore computed as ~((~(a - 1)) | (~(b - 1))) + 1 which is | |
| 1210 // equal to ((a-1) & (b-1)) + 1. | |
| 1211 ASSERT(a_length >= b_length); | |
| 1212 ASSERT(min_length == b_length); | |
| 1213 intptr_t result_length = min_length + 1; | |
| 1214 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1215 result.ToggleSign(); | |
| 1216 Chunk a_borrow = 1; | |
| 1217 Chunk b_borrow = 1; | |
| 1218 Chunk result_carry = 1; | |
| 1219 for (intptr_t i = 0; i < b_length; i++) { | |
| 1220 Chunk a_digit = a.GetChunkAt(i) - a_borrow; | |
| 1221 Chunk b_digit = b.GetChunkAt(i) - b_borrow; | |
| 1222 Chunk result_chunk = ((a_digit & b_digit) & kDigitMask) + result_carry; | |
| 1223 result.SetChunkAt(i, result_chunk & kDigitMask); | |
| 1224 a_borrow = a_digit >> (kChunkBitSize - 1); | |
| 1225 b_borrow = b_digit >> (kChunkBitSize - 1); | |
| 1226 result_carry = result_chunk >> kDigitBitSize; | |
| 1227 } | |
| 1228 result.SetChunkAt(b_length, result_carry); | |
| 1229 Clamp(result); | |
| 1230 return result.raw(); | |
| 1231 } | |
| 1232 | |
| 1233 | |
| 1234 RawBigint* BigintOperations::BitXor(const Bigint& a, const Bigint& b) { | |
| 1235 ASSERT(IsClamped(a)); | |
| 1236 ASSERT(IsClamped(b)); | |
| 1237 | |
| 1238 if (a.IsZero()) { | |
| 1239 return Copy(b); | |
| 1240 } | |
| 1241 if (b.IsZero()) { | |
| 1242 return Copy(a); | |
| 1243 } | |
| 1244 if (a.IsNegative() && !b.IsNegative()) { | |
| 1245 return BitXor(b, a); | |
| 1246 } | |
| 1247 if ((a.IsNegative() == b.IsNegative()) && (a.Length() < b.Length())) { | |
| 1248 return BitXor(b, a); | |
| 1249 } | |
| 1250 | |
| 1251 intptr_t a_length = a.Length(); | |
| 1252 intptr_t b_length = b.Length(); | |
| 1253 intptr_t min_length = Utils::Minimum(a_length, b_length); | |
| 1254 intptr_t max_length = Utils::Maximum(a_length, b_length); | |
| 1255 if (!b.IsNegative()) { | |
| 1256 ASSERT(!a.IsNegative()); | |
| 1257 intptr_t result_length = max_length; | |
| 1258 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1259 | |
| 1260 ASSERT(a_length >= b_length); | |
| 1261 for (intptr_t i = 0; i < b_length; i++) { | |
| 1262 result.SetChunkAt(i, a.GetChunkAt(i) ^ b.GetChunkAt(i)); | |
| 1263 } | |
| 1264 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1265 result.SetChunkAt(i, a.GetChunkAt(i)); | |
| 1266 } | |
| 1267 Clamp(result); | |
| 1268 return result.raw(); | |
| 1269 } | |
| 1270 | |
| 1271 // Bigints encode negative values by storing the absolute value and the sign | |
| 1272 // separately. To do bit operations we need to simulate numbers that are | |
| 1273 // implemented as two's complement. | |
| 1274 // The negation of a positive number x would be encoded as follows in | |
| 1275 // two's complement: n = ~(x - 1). | |
| 1276 // The inverse transformation is hence (~n) + 1. | |
| 1277 | |
| 1278 if (!a.IsNegative()) { | |
| 1279 ASSERT(b.IsNegative()); | |
| 1280 // The result will be negative. | |
| 1281 // We need to convert b to two's complement. Do the bit-operation there, | |
| 1282 // and transform the resulting bits from two's complement back to separated | |
| 1283 // magnitude and sign. | |
| 1284 // a ^ b is therefore computed as ~((a ^ (~(b - 1))) + 1. | |
| 1285 intptr_t result_length = max_length + 1; | |
| 1286 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1287 result.ToggleSign(); | |
| 1288 Chunk borrow = 1; | |
| 1289 Chunk result_carry = 1; | |
| 1290 for (intptr_t i = 0; i < min_length; i++) { | |
| 1291 Chunk a_digit = a.GetChunkAt(i); | |
| 1292 Chunk b_digit = b.GetChunkAt(i) - borrow; | |
| 1293 Chunk result_digit = | |
| 1294 ((~(a_digit ^ ~b_digit)) & kDigitMask) + result_carry; | |
| 1295 result.SetChunkAt(i, result_digit & kDigitMask); | |
| 1296 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1297 result_carry = result_digit >> kDigitBitSize; | |
| 1298 } | |
| 1299 for (intptr_t i = min_length; i < a_length; i++) { | |
| 1300 Chunk a_digit = a.GetChunkAt(i); | |
| 1301 Chunk b_digit = -borrow; | |
| 1302 Chunk result_digit = | |
| 1303 ((~(a_digit ^ ~b_digit)) & kDigitMask) + result_carry; | |
| 1304 result.SetChunkAt(i, result_digit & kDigitMask); | |
| 1305 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1306 result_carry = result_digit >> kDigitBitSize; | |
| 1307 } | |
| 1308 for (intptr_t i = min_length; i < b_length; i++) { | |
| 1309 // a_digit = 0. | |
| 1310 Chunk b_digit = b.GetChunkAt(i) - borrow; | |
| 1311 Chunk result_digit = (b_digit & kDigitMask) + result_carry; | |
| 1312 result.SetChunkAt(i, result_digit & kDigitMask); | |
| 1313 borrow = b_digit >> (kChunkBitSize - 1); | |
| 1314 result_carry = result_digit >> kDigitBitSize; | |
| 1315 } | |
| 1316 result.SetChunkAt(max_length, result_carry); | |
| 1317 Clamp(result); | |
| 1318 return result.raw(); | |
| 1319 } | |
| 1320 | |
| 1321 ASSERT(a.IsNegative()); | |
| 1322 ASSERT(b.IsNegative()); | |
| 1323 // The result will be positive. | |
| 1324 // We need to convert a and b to two's complement, do the bit-operation there, | |
| 1325 // and simply store the result. | |
| 1326 // a ^ b is therefore computed as (~(a - 1)) ^ (~(b - 1)). | |
| 1327 ASSERT(a_length >= b_length); | |
| 1328 ASSERT(max_length == a_length); | |
| 1329 intptr_t result_length = max_length; | |
| 1330 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1331 Chunk a_borrow = 1; | |
| 1332 Chunk b_borrow = 1; | |
| 1333 for (intptr_t i = 0; i < b_length; i++) { | |
| 1334 Chunk a_digit = a.GetChunkAt(i) - a_borrow; | |
| 1335 Chunk b_digit = b.GetChunkAt(i) - b_borrow; | |
| 1336 Chunk result_chunk = (~a_digit) ^ (~b_digit); | |
| 1337 result.SetChunkAt(i, result_chunk & kDigitMask); | |
| 1338 a_borrow = a_digit >> (kChunkBitSize - 1); | |
| 1339 b_borrow = b_digit >> (kChunkBitSize - 1); | |
| 1340 } | |
| 1341 ASSERT(b_borrow == 0); | |
| 1342 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1343 Chunk a_digit = a.GetChunkAt(i) - a_borrow; | |
| 1344 // (~a_digit) ^ 0xFFF..FFF == a_digit. | |
| 1345 result.SetChunkAt(i, a_digit & kDigitMask); | |
| 1346 a_borrow = a_digit >> (kChunkBitSize - 1); | |
| 1347 } | |
| 1348 ASSERT(a_borrow == 0); | |
| 1349 Clamp(result); | |
| 1350 return result.raw(); | |
| 1351 } | |
| 1352 | |
| 1353 | |
| 1354 RawBigint* BigintOperations::BitNot(const Bigint& bigint) { | |
| 1355 if (bigint.IsZero()) { | |
| 1356 return MinusOne(); | |
| 1357 } | |
| 1358 const Bigint& one_bigint = Bigint::Handle(One()); | |
| 1359 if (bigint.IsNegative()) { | |
| 1360 return UnsignedSubtract(bigint, one_bigint); | |
| 1361 } else { | |
| 1362 const Bigint& result = Bigint::Handle(UnsignedAdd(bigint, one_bigint)); | |
| 1363 result.ToggleSign(); | |
| 1364 return result.raw(); | |
| 1365 } | |
| 1366 } | |
| 1367 | |
| 1368 | |
| 1369 int64_t BigintOperations::BitLength(const Bigint& bigint) { | |
| 1370 ASSERT(IsClamped(bigint)); | |
| 1371 intptr_t length = bigint.Length(); | |
| 1372 if (length == 0) return 0; | |
| 1373 intptr_t last = length - 1; | |
| 1374 | |
| 1375 Chunk high_chunk = bigint.GetChunkAt(last); | |
| 1376 ASSERT(high_chunk != 0); | |
| 1377 int64_t bit_length = | |
| 1378 static_cast<int64_t>(kDigitBitSize) * last + CountBits(high_chunk); | |
| 1379 | |
| 1380 if (bigint.IsNegative()) { | |
| 1381 // We are calculating the 2's complement bitlength but we have a sign and | |
| 1382 // magnitude representation. The length is the same except when the | |
| 1383 // magnitude is an exact power of two, 2^k. In 2's complement format, | |
| 1384 // -(2^k) takes one fewer bit than (2^k). | |
| 1385 | |
| 1386 if ((high_chunk & (high_chunk - 1)) == 0) { // Single bit set? | |
| 1387 for (intptr_t i = 0; i < last; i++) { | |
| 1388 if (bigint.GetChunkAt(i) != 0) return bit_length; | |
| 1389 } | |
| 1390 bit_length -= 1; | |
| 1391 } | |
| 1392 } | |
| 1393 return bit_length; | |
| 1394 } | |
| 1395 | |
| 1396 | |
| 1397 int BigintOperations::Compare(const Bigint& a, const Bigint& b) { | |
| 1398 bool a_is_negative = a.IsNegative(); | |
| 1399 bool b_is_negative = b.IsNegative(); | |
| 1400 if (a_is_negative != b_is_negative) { | |
| 1401 return a_is_negative ? -1 : 1; | |
| 1402 } | |
| 1403 | |
| 1404 if (a_is_negative) { | |
| 1405 return -UnsignedCompare(a, b); | |
| 1406 } | |
| 1407 return UnsignedCompare(a, b); | |
| 1408 } | |
| 1409 | |
| 1410 | |
| 1411 void BigintOperations::FromHexCString(const char* hex_string, | |
| 1412 const Bigint& value) { | |
| 1413 ASSERT(hex_string[0] != '-'); | |
| 1414 intptr_t bigint_length = ComputeChunkLength(hex_string); | |
| 1415 // The bigint's least significant digit (lsd) is at position 0, whereas the | |
| 1416 // given string has it's lsd at the last position. | |
| 1417 // The hex_i index, pointing into the string, starts therefore at the end, | |
| 1418 // whereas the bigint-index (i) starts at 0. | |
| 1419 const intptr_t hex_length = strlen(hex_string); | |
| 1420 if (hex_length < 0) { | |
| 1421 FATAL("Fatal error in BigintOperations::FromHexCString: string too long"); | |
| 1422 } | |
| 1423 intptr_t hex_i = hex_length - 1; | |
| 1424 for (intptr_t i = 0; i < bigint_length; i++) { | |
| 1425 Chunk digit = 0; | |
| 1426 int shift = 0; | |
| 1427 for (int j = 0; j < kHexCharsPerDigit; j++) { | |
| 1428 // Reads a block of hexadecimal digits and stores it in 'digit'. | |
| 1429 // Ex: "0123456" with kHexCharsPerDigit == 3, hex_i == 6, reads "456". | |
| 1430 if (hex_i < 0) { | |
| 1431 break; | |
| 1432 } | |
| 1433 ASSERT(hex_i >= 0); | |
| 1434 char c = hex_string[hex_i--]; | |
| 1435 ASSERT(Utils::IsHexDigit(c)); | |
| 1436 digit += static_cast<Chunk>(Utils::HexDigitToInt(c)) << shift; | |
| 1437 shift += 4; | |
| 1438 } | |
| 1439 value.SetChunkAt(i, digit); | |
| 1440 } | |
| 1441 ASSERT(hex_i == -1); | |
| 1442 Clamp(value); | |
| 1443 } | |
| 1444 | |
| 1445 | |
| 1446 RawBigint* BigintOperations::AddSubtract(const Bigint& a, | |
| 1447 const Bigint& b, | |
| 1448 bool negate_b) { | |
| 1449 ASSERT(IsClamped(a)); | |
| 1450 ASSERT(IsClamped(b)); | |
| 1451 Bigint& result = Bigint::Handle(); | |
| 1452 // We perform the subtraction by simulating a negation of the b-argument. | |
| 1453 bool b_is_negative = negate_b ? !b.IsNegative() : b.IsNegative(); | |
| 1454 | |
| 1455 // If both are of the same sign, then we can compute the unsigned addition | |
| 1456 // and then simply adjust the sign (if necessary). | |
| 1457 // Ex: -3 + -5 -> -(3 + 5) | |
| 1458 if (a.IsNegative() == b_is_negative) { | |
| 1459 result = UnsignedAdd(a, b); | |
| 1460 result.SetSign(b_is_negative); | |
| 1461 ASSERT(IsClamped(result)); | |
| 1462 return result.raw(); | |
| 1463 } | |
| 1464 | |
| 1465 // The signs differ. | |
| 1466 // Take the number with small magnitude and subtract its absolute value from | |
| 1467 // the absolute value of the other number. Then adjust the sign, if necessary. | |
| 1468 // The sign is the same as for the number with the greater magnitude. | |
| 1469 // Ex: -8 + 3 -> -(8 - 3) | |
| 1470 // 8 + -3 -> (8 - 3) | |
| 1471 // -3 + 8 -> (8 - 3) | |
| 1472 // 3 + -8 -> -(8 - 3) | |
| 1473 int comp = UnsignedCompare(a, b); | |
| 1474 if (comp < 0) { | |
| 1475 result = UnsignedSubtract(b, a); | |
| 1476 result.SetSign(b_is_negative); | |
| 1477 } else if (comp > 0) { | |
| 1478 result = UnsignedSubtract(a, b); | |
| 1479 result.SetSign(a.IsNegative()); | |
| 1480 } else { | |
| 1481 return Zero(); | |
| 1482 } | |
| 1483 ASSERT(IsClamped(result)); | |
| 1484 return result.raw(); | |
| 1485 } | |
| 1486 | |
| 1487 | |
| 1488 int BigintOperations::UnsignedCompare(const Bigint& a, const Bigint& b) { | |
| 1489 ASSERT(IsClamped(a)); | |
| 1490 ASSERT(IsClamped(b)); | |
| 1491 intptr_t a_length = a.Length(); | |
| 1492 intptr_t b_length = b.Length(); | |
| 1493 if (a_length < b_length) return -1; | |
| 1494 if (a_length > b_length) return 1; | |
| 1495 for (intptr_t i = a_length - 1; i >= 0; i--) { | |
| 1496 Chunk digit_a = a.GetChunkAt(i); | |
| 1497 Chunk digit_b = b.GetChunkAt(i); | |
| 1498 if (digit_a < digit_b) return -1; | |
| 1499 if (digit_a > digit_b) return 1; | |
| 1500 // Else look at the next digit. | |
| 1501 } | |
| 1502 return 0; // They are equal. | |
| 1503 } | |
| 1504 | |
| 1505 | |
| 1506 int BigintOperations::UnsignedCompareNonClamped( | |
| 1507 const Bigint& a, const Bigint& b) { | |
| 1508 intptr_t a_length = a.Length(); | |
| 1509 intptr_t b_length = b.Length(); | |
| 1510 while (a_length > b_length) { | |
| 1511 if (a.GetChunkAt(a_length - 1) != 0) return 1; | |
| 1512 a_length--; | |
| 1513 } | |
| 1514 while (b_length > a_length) { | |
| 1515 if (b.GetChunkAt(b_length - 1) != 0) return -1; | |
| 1516 b_length--; | |
| 1517 } | |
| 1518 for (intptr_t i = a_length - 1; i >= 0; i--) { | |
| 1519 Chunk digit_a = a.GetChunkAt(i); | |
| 1520 Chunk digit_b = b.GetChunkAt(i); | |
| 1521 if (digit_a < digit_b) return -1; | |
| 1522 if (digit_a > digit_b) return 1; | |
| 1523 // Else look at the next digit. | |
| 1524 } | |
| 1525 return 0; // They are equal. | |
| 1526 } | |
| 1527 | |
| 1528 | |
| 1529 RawBigint* BigintOperations::UnsignedAdd(const Bigint& a, const Bigint& b) { | |
| 1530 ASSERT(IsClamped(a)); | |
| 1531 ASSERT(IsClamped(b)); | |
| 1532 | |
| 1533 intptr_t a_length = a.Length(); | |
| 1534 intptr_t b_length = b.Length(); | |
| 1535 if (a_length < b_length) { | |
| 1536 return UnsignedAdd(b, a); | |
| 1537 } | |
| 1538 | |
| 1539 // We might request too much space, in which case we will adjust the length | |
| 1540 // afterwards. | |
| 1541 intptr_t result_length = a_length + 1; | |
| 1542 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1543 | |
| 1544 Chunk carry = 0; | |
| 1545 // b has fewer digits than a. | |
| 1546 ASSERT(b_length <= a_length); | |
| 1547 for (intptr_t i = 0; i < b_length; i++) { | |
| 1548 Chunk sum = a.GetChunkAt(i) + b.GetChunkAt(i) + carry; | |
| 1549 result.SetChunkAt(i, sum & kDigitMask); | |
| 1550 carry = sum >> kDigitBitSize; | |
| 1551 } | |
| 1552 // Copy over the remaining digits of a, but don't forget the carry. | |
| 1553 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1554 Chunk sum = a.GetChunkAt(i) + carry; | |
| 1555 result.SetChunkAt(i, sum & kDigitMask); | |
| 1556 carry = sum >> kDigitBitSize; | |
| 1557 } | |
| 1558 // Shrink the result if there was no overflow. Otherwise apply the carry. | |
| 1559 if (carry == 0) { | |
| 1560 // TODO(floitsch): We change the size of bigint-objects here. | |
| 1561 result.SetLength(a_length); | |
| 1562 } else { | |
| 1563 result.SetChunkAt(a_length, carry); | |
| 1564 } | |
| 1565 ASSERT(IsClamped(result)); | |
| 1566 return result.raw(); | |
| 1567 } | |
| 1568 | |
| 1569 | |
| 1570 RawBigint* BigintOperations::UnsignedSubtract(const Bigint& a, | |
| 1571 const Bigint& b) { | |
| 1572 ASSERT(IsClamped(a)); | |
| 1573 ASSERT(IsClamped(b)); | |
| 1574 ASSERT(UnsignedCompare(a, b) >= 0); | |
| 1575 | |
| 1576 const int kSignBitPos = Bigint::kChunkSize * kBitsPerByte - 1; | |
| 1577 | |
| 1578 intptr_t a_length = a.Length(); | |
| 1579 intptr_t b_length = b.Length(); | |
| 1580 | |
| 1581 // We might request too much space, in which case we will adjust the length | |
| 1582 // afterwards. | |
| 1583 intptr_t result_length = a_length; | |
| 1584 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1585 | |
| 1586 Chunk borrow = 0; | |
| 1587 ASSERT(b_length <= a_length); | |
| 1588 for (intptr_t i = 0; i < b_length; i++) { | |
| 1589 Chunk difference = a.GetChunkAt(i) - b.GetChunkAt(i) - borrow; | |
| 1590 result.SetChunkAt(i, difference & kDigitMask); | |
| 1591 borrow = difference >> kSignBitPos; | |
| 1592 ASSERT((borrow == 0) || (borrow == 1)); | |
| 1593 } | |
| 1594 // Copy over the remaining digits of a, but don't forget the borrow. | |
| 1595 for (intptr_t i = b_length; i < a_length; i++) { | |
| 1596 Chunk difference = a.GetChunkAt(i) - borrow; | |
| 1597 result.SetChunkAt(i, difference & kDigitMask); | |
| 1598 borrow = (difference >> kSignBitPos); | |
| 1599 ASSERT((borrow == 0) || (borrow == 1)); | |
| 1600 } | |
| 1601 ASSERT(borrow == 0); | |
| 1602 Clamp(result); | |
| 1603 return result.raw(); | |
| 1604 } | |
| 1605 | |
| 1606 | |
| 1607 RawBigint* BigintOperations::MultiplyWithDigit( | |
| 1608 const Bigint& bigint, Chunk digit) { | |
| 1609 ASSERT(digit <= kDigitMaxValue); | |
| 1610 if (digit == 0) return Zero(); | |
| 1611 if (bigint.IsZero()) return Zero(); | |
| 1612 | |
| 1613 intptr_t length = bigint.Length(); | |
| 1614 intptr_t result_length = length + 1; | |
| 1615 const Bigint& result = Bigint::Handle(Bigint::Allocate(result_length)); | |
| 1616 | |
| 1617 Chunk carry = 0; | |
| 1618 for (intptr_t i = 0; i < length; i++) { | |
| 1619 Chunk chunk = bigint.GetChunkAt(i); | |
| 1620 DoubleChunk product = (static_cast<DoubleChunk>(chunk) * digit) + carry; | |
| 1621 result.SetChunkAt(i, static_cast<Chunk>(product & kDigitMask)); | |
| 1622 carry = static_cast<Chunk>(product >> kDigitBitSize); | |
| 1623 } | |
| 1624 result.SetChunkAt(length, carry); | |
| 1625 | |
| 1626 result.SetSign(bigint.IsNegative()); | |
| 1627 Clamp(result); | |
| 1628 return result.raw(); | |
| 1629 } | |
| 1630 | |
| 1631 | |
| 1632 void BigintOperations::DivideRemainder( | |
| 1633 const Bigint& a, const Bigint& b, Bigint* quotient, Bigint* remainder) { | |
| 1634 // TODO(floitsch): This function is very memory-intensive since all | |
| 1635 // intermediate bigint results are allocated in new memory. It would be | |
| 1636 // much more efficient to reuse the space of temporary intermediate variables. | |
| 1637 ASSERT(IsClamped(a)); | |
| 1638 ASSERT(IsClamped(b)); | |
| 1639 ASSERT(!b.IsZero()); | |
| 1640 | |
| 1641 int comp = UnsignedCompare(a, b); | |
| 1642 if (comp < 0) { | |
| 1643 (*quotient) = Zero(); | |
| 1644 (*remainder) = Copy(a); // TODO(floitsch): can we reuse the input? | |
| 1645 return; | |
| 1646 } else if (comp == 0) { | |
| 1647 (*quotient) = One(); | |
| 1648 quotient->SetSign(a.IsNegative() != b.IsNegative()); | |
| 1649 (*remainder) = Zero(); | |
| 1650 return; | |
| 1651 } | |
| 1652 | |
| 1653 intptr_t b_length = b.Length(); | |
| 1654 | |
| 1655 if (b_length == 1) { | |
| 1656 const Bigint& dividend_quotient = Bigint::Handle(Copy(a)); | |
| 1657 Chunk remainder_digit = | |
| 1658 BigintOperations::InplaceUnsignedDivideRemainderDigit( | |
| 1659 dividend_quotient, b.GetChunkAt(0)); | |
| 1660 dividend_quotient.SetSign(a.IsNegative() != b.IsNegative()); | |
| 1661 *quotient = dividend_quotient.raw(); | |
| 1662 *remainder = Bigint::Allocate(1); | |
| 1663 remainder->SetChunkAt(0, remainder_digit); | |
| 1664 remainder->SetSign(a.IsNegative()); | |
| 1665 Clamp(*remainder); | |
| 1666 return; | |
| 1667 } | |
| 1668 | |
| 1669 // High level description: | |
| 1670 // The algorithm is basically the algorithm that is taught in school: | |
| 1671 // Let a the dividend and b the divisor. We are looking for | |
| 1672 // the quotient q = truncate(a / b), and | |
| 1673 // the remainder r = a - q * b. | |
| 1674 // School algorithm: | |
| 1675 // q = 0 | |
| 1676 // n = number_of_digits(a) - number_of_digits(b) | |
| 1677 // for (i = n; i >= 0; i--) { | |
| 1678 // Maximize k such that k*y*10^i is less than or equal to a and | |
| 1679 // (k + 1)*y*10^i is greater. | |
| 1680 // q = q + k * 10^i // Add new digit to result. | |
| 1681 // a = a - k * b * 10^i | |
| 1682 // } | |
| 1683 // r = a | |
| 1684 // | |
| 1685 // Instead of working in base 10 we work in base kDigitBitSize. | |
| 1686 | |
| 1687 int normalization_shift = | |
| 1688 kDigitBitSize - CountBits(b.GetChunkAt(b_length - 1)); | |
| 1689 Bigint& dividend = Bigint::Handle(ShiftLeft(a, normalization_shift)); | |
| 1690 const Bigint& divisor = Bigint::Handle(ShiftLeft(b, normalization_shift)); | |
| 1691 dividend.SetSign(false); | |
| 1692 divisor.SetSign(false); | |
| 1693 | |
| 1694 intptr_t dividend_length = dividend.Length(); | |
| 1695 intptr_t divisor_length = b_length; | |
| 1696 ASSERT(divisor_length == divisor.Length()); | |
| 1697 | |
| 1698 intptr_t quotient_length = dividend_length - divisor_length + 1; | |
| 1699 *quotient = Bigint::Allocate(quotient_length); | |
| 1700 quotient->SetSign(a.IsNegative() != b.IsNegative()); | |
| 1701 | |
| 1702 intptr_t quotient_pos = dividend_length - divisor_length; | |
| 1703 // Find the first quotient-digit. | |
| 1704 // The first digit must be computed separately from the other digits because | |
| 1705 // the preconditions for the loop are not yet satisfied. | |
| 1706 // For simplicity use a shifted divisor, so that the comparison and | |
| 1707 // subtraction are easier. | |
| 1708 int divisor_shift_amount = dividend_length - divisor_length; | |
| 1709 Bigint& shifted_divisor = | |
| 1710 Bigint::Handle(DigitsShiftLeft(divisor, divisor_shift_amount)); | |
| 1711 Chunk first_quotient_digit = 0; | |
| 1712 Isolate* isolate = Isolate::Current(); | |
| 1713 while (UnsignedCompare(dividend, shifted_divisor) >= 0) { | |
| 1714 HANDLESCOPE(isolate); | |
| 1715 first_quotient_digit++; | |
| 1716 dividend = Subtract(dividend, shifted_divisor); | |
| 1717 } | |
| 1718 quotient->SetChunkAt(quotient_pos--, first_quotient_digit); | |
| 1719 | |
| 1720 // Find the remainder of the digits. | |
| 1721 | |
| 1722 Chunk first_divisor_digit = divisor.GetChunkAt(divisor_length - 1); | |
| 1723 // The short divisor only represents the first two digits of the divisor. | |
| 1724 // If the divisor has only one digit, then the second part is zeroed out. | |
| 1725 Bigint& short_divisor = Bigint::Handle(Bigint::Allocate(2)); | |
| 1726 if (divisor_length > 1) { | |
| 1727 short_divisor.SetChunkAt(0, divisor.GetChunkAt(divisor_length - 2)); | |
| 1728 } else { | |
| 1729 short_divisor.SetChunkAt(0, 0); | |
| 1730 } | |
| 1731 short_divisor.SetChunkAt(1, first_divisor_digit); | |
| 1732 // The following bigint will be used inside the loop. It is allocated outside | |
| 1733 // the loop to avoid repeated allocations. | |
| 1734 Bigint& target = Bigint::Handle(Bigint::Allocate(3)); | |
| 1735 // The dividend_length here must be from the initial dividend. | |
| 1736 for (intptr_t i = dividend_length - 1; i >= divisor_length; i--) { | |
| 1737 // Invariant: let t = i - divisor_length | |
| 1738 // then dividend / (divisor << (t * kDigitBitSize)) <= kDigitMaxValue. | |
| 1739 // Ex: dividend: 53451232, and divisor: 535 (with t == 5) is ok. | |
| 1740 // dividend: 56822123, and divisor: 563 (with t == 5) is bad. | |
| 1741 // dividend: 6822123, and divisor: 563 (with t == 5) is ok. | |
| 1742 | |
| 1743 HANDLESCOPE(isolate); | |
| 1744 // The dividend has changed. So recompute its length. | |
| 1745 dividend_length = dividend.Length(); | |
| 1746 Chunk dividend_digit; | |
| 1747 if (i > dividend_length) { | |
| 1748 quotient->SetChunkAt(quotient_pos--, 0); | |
| 1749 continue; | |
| 1750 } else if (i == dividend_length) { | |
| 1751 dividend_digit = 0; | |
| 1752 } else { | |
| 1753 ASSERT(i + 1 == dividend_length); | |
| 1754 dividend_digit = dividend.GetChunkAt(i); | |
| 1755 } | |
| 1756 Chunk quotient_digit; | |
| 1757 // Compute an estimate of the quotient_digit. The estimate will never | |
| 1758 // be too small. | |
| 1759 if (dividend_digit == first_divisor_digit) { | |
| 1760 // Small shortcut: the else-branch would compute a value > kDigitMaxValue. | |
| 1761 // However, by hypothesis, we know that the quotient_digit must fit into | |
| 1762 // a digit. Avoid going through repeated iterations of the adjustment | |
| 1763 // loop by directly assigning kDigitMaxValue to the quotient_digit. | |
| 1764 // Ex: 51235 / 523. | |
| 1765 // 51 / 5 would yield 10 (if computed in the else branch). | |
| 1766 // However we know that 9 is the maximal value. | |
| 1767 quotient_digit = kDigitMaxValue; | |
| 1768 } else { | |
| 1769 // Compute the estimate by using two digits of the dividend and one of | |
| 1770 // the divisor. | |
| 1771 // Ex: 32421 / 535 | |
| 1772 // 32 / 5 -> 6 | |
| 1773 // The estimate would hence be 6. | |
| 1774 DoubleChunk two_dividend_digits = dividend_digit; | |
| 1775 two_dividend_digits <<= kDigitBitSize; | |
| 1776 two_dividend_digits += dividend.GetChunkAt(i - 1); | |
| 1777 DoubleChunk q = two_dividend_digits / first_divisor_digit; | |
| 1778 if (q > kDigitMaxValue) q = kDigitMaxValue; | |
| 1779 quotient_digit = static_cast<Chunk>(q); | |
| 1780 } | |
| 1781 | |
| 1782 // Refine estimation. | |
| 1783 quotient_digit++; // The following loop will start by decrementing. | |
| 1784 Bigint& estimation_product = Bigint::Handle(); | |
| 1785 target.SetChunkAt(0, ((i - 2) < 0) ? 0 : dividend.GetChunkAt(i - 2)); | |
| 1786 target.SetChunkAt(1, ((i - 1) < 0) ? 0 : dividend.GetChunkAt(i - 1)); | |
| 1787 target.SetChunkAt(2, dividend_digit); | |
| 1788 do { | |
| 1789 HANDLESCOPE(isolate); | |
| 1790 quotient_digit = (quotient_digit - 1) & kDigitMask; | |
| 1791 estimation_product = MultiplyWithDigit(short_divisor, quotient_digit); | |
| 1792 } while (UnsignedCompareNonClamped(estimation_product, target) > 0); | |
| 1793 // At this point the quotient_digit is fairly accurate. | |
| 1794 // At the worst it is off by one. | |
| 1795 // Remove a multiple of the divisor. If the estimate is incorrect we will | |
| 1796 // subtract the divisor another time. | |
| 1797 // Let t = i - divisor_length. | |
| 1798 // dividend -= (quotient_digit * divisor) << (t * kDigitBitSize); | |
| 1799 shifted_divisor = MultiplyWithDigit(divisor, quotient_digit); | |
| 1800 shifted_divisor = DigitsShiftLeft(shifted_divisor, i - divisor_length); | |
| 1801 dividend = Subtract(dividend, shifted_divisor); | |
| 1802 if (dividend.IsNegative()) { | |
| 1803 // The estimation was still too big. | |
| 1804 quotient_digit--; | |
| 1805 // TODO(floitsch): allocate space for the shifted_divisor once and reuse | |
| 1806 // it at every iteration. | |
| 1807 shifted_divisor = DigitsShiftLeft(divisor, i - divisor_length); | |
| 1808 // TODO(floitsch): reuse the space of the previous dividend. | |
| 1809 dividend = Add(dividend, shifted_divisor); | |
| 1810 } | |
| 1811 quotient->SetChunkAt(quotient_pos--, quotient_digit); | |
| 1812 } | |
| 1813 ASSERT(quotient_pos == -1); | |
| 1814 Clamp(*quotient); | |
| 1815 *remainder = ShiftRight(dividend, normalization_shift); | |
| 1816 remainder->SetSign(a.IsNegative()); | |
| 1817 } | |
| 1818 | |
| 1819 | |
| 1820 BigintOperations::Chunk BigintOperations::InplaceUnsignedDivideRemainderDigit( | |
| 1821 const Bigint& dividend_quotient, Chunk divisor_digit) { | |
| 1822 Chunk remainder = 0; | |
| 1823 for (intptr_t i = dividend_quotient.Length() - 1; i >= 0; i--) { | |
| 1824 DoubleChunk dividend_digit = | |
| 1825 (static_cast<DoubleChunk>(remainder) << kDigitBitSize) + | |
| 1826 dividend_quotient.GetChunkAt(i); | |
| 1827 Chunk quotient_digit = static_cast<Chunk>(dividend_digit / divisor_digit); | |
| 1828 remainder = static_cast<Chunk>( | |
| 1829 dividend_digit - | |
| 1830 static_cast<DoubleChunk>(quotient_digit) * divisor_digit); | |
| 1831 dividend_quotient.SetChunkAt(i, quotient_digit); | |
| 1832 } | |
| 1833 Clamp(dividend_quotient); | |
| 1834 return remainder; | |
| 1835 } | |
| 1836 | |
| 1837 | |
| 1838 void BigintOperations::Clamp(const Bigint& bigint) { | |
| 1839 intptr_t length = bigint.Length(); | |
| 1840 while (length > 0 && (bigint.GetChunkAt(length - 1) == 0)) { | |
| 1841 length--; | |
| 1842 } | |
| 1843 // TODO(floitsch): We change the size of bigint-objects here. | |
| 1844 bigint.SetLength(length); | |
| 1845 } | |
| 1846 | |
| 1847 | |
| 1848 RawBigint* BigintOperations::Copy(const Bigint& bigint) { | |
| 1849 intptr_t bigint_length = bigint.Length(); | |
| 1850 Bigint& copy = Bigint::Handle(Bigint::Allocate(bigint_length)); | |
| 1851 for (intptr_t i = 0; i < bigint_length; i++) { | |
| 1852 copy.SetChunkAt(i, bigint.GetChunkAt(i)); | |
| 1853 } | |
| 1854 copy.SetSign(bigint.IsNegative()); | |
| 1855 return copy.raw(); | |
| 1856 } | |
| 1857 | |
| 1858 | |
| 1859 intptr_t BigintOperations::CountBits(Chunk digit) { | |
| 1860 intptr_t result = 0; | |
| 1861 while (digit != 0) { | |
| 1862 digit >>= 1; | |
| 1863 result++; | |
| 1864 } | |
| 1865 return result; | |
| 1866 } | |
| 1867 | |
| 1868 } // namespace dart | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 509153003:
New bigint implementation in the vm. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/