ABDKMath64x64.sol (25551B)
1 // SPDX-License-Identifier: BSD-4-Clause 2 /* 3 * ABDK Math 64.64 Smart Contract Library. Copyright © 2019 by ABDK Consulting. 4 * Author: Mikhail Vladimirov <mikhail.vladimirov@gmail.com> 5 */ 6 pragma solidity ^0.8.0; 7 8 /** 9 * Smart contract library of mathematical functions operating with signed 10 * 64.64-bit fixed point numbers. Signed 64.64-bit fixed point number is 11 * basically a simple fraction whose numerator is signed 128-bit integer and 12 * denominator is 2^64. As long as denominator is always the same, there is no 13 * need to store it, thus in Solidity signed 64.64-bit fixed point numbers are 14 * represented by int128 type holding only the numerator. 15 */ 16 library ABDKMath64x64 { 17 /* 18 * Minimum value signed 64.64-bit fixed point number may have. 19 */ 20 int128 private constant MIN_64x64 = -0x80000000000000000000000000000000; 21 22 /* 23 * Maximum value signed 64.64-bit fixed point number may have. 24 */ 25 int128 private constant MAX_64x64 = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF; 26 27 /** 28 * Convert signed 256-bit integer number into signed 64.64-bit fixed point 29 * number. Revert on overflow. 30 * 31 * @param x signed 256-bit integer number 32 * @return signed 64.64-bit fixed point number 33 */ 34 function fromInt (int256 x) internal pure returns (int128) { 35 unchecked { 36 require (x >= -0x8000000000000000 && x <= 0x7FFFFFFFFFFFFFFF); 37 return int128 (x << 64); 38 } 39 } 40 41 /** 42 * Convert signed 64.64 fixed point number into signed 64-bit integer number 43 * rounding down. 44 * 45 * @param x signed 64.64-bit fixed point number 46 * @return signed 64-bit integer number 47 */ 48 function toInt (int128 x) internal pure returns (int64) { 49 unchecked { 50 return int64 (x >> 64); 51 } 52 } 53 54 /** 55 * Convert unsigned 256-bit integer number into signed 64.64-bit fixed point 56 * number. Revert on overflow. 57 * 58 * @param x unsigned 256-bit integer number 59 * @return signed 64.64-bit fixed point number 60 */ 61 function fromUInt (uint256 x) internal pure returns (int128) { 62 unchecked { 63 require (x <= 0x7FFFFFFFFFFFFFFF); 64 return int128 (int256 (x << 64)); 65 } 66 } 67 68 /** 69 * Convert signed 64.64 fixed point number into unsigned 64-bit integer 70 * number rounding down. Revert on underflow. 71 * 72 * @param x signed 64.64-bit fixed point number 73 * @return unsigned 64-bit integer number 74 */ 75 function toUInt (int128 x) internal pure returns (uint64) { 76 unchecked { 77 require (x >= 0); 78 return uint64 (uint128 (x >> 64)); 79 } 80 } 81 82 /** 83 * Convert signed 128.128 fixed point number into signed 64.64-bit fixed point 84 * number rounding down. Revert on overflow. 85 * 86 * @param x signed 128.128-bin fixed point number 87 * @return signed 64.64-bit fixed point number 88 */ 89 function from128x128 (int256 x) internal pure returns (int128) { 90 unchecked { 91 int256 result = x >> 64; 92 require (result >= MIN_64x64 && result <= MAX_64x64); 93 return int128 (result); 94 } 95 } 96 97 /** 98 * Convert signed 64.64 fixed point number into signed 128.128 fixed point 99 * number. 100 * 101 * @param x signed 64.64-bit fixed point number 102 * @return signed 128.128 fixed point number 103 */ 104 function to128x128 (int128 x) internal pure returns (int256) { 105 unchecked { 106 return int256 (x) << 64; 107 } 108 } 109 110 /** 111 * Calculate x + y. Revert on overflow. 112 * 113 * @param x signed 64.64-bit fixed point number 114 * @param y signed 64.64-bit fixed point number 115 * @return signed 64.64-bit fixed point number 116 */ 117 function add (int128 x, int128 y) internal pure returns (int128) { 118 unchecked { 119 int256 result = int256(x) + y; 120 require (result >= MIN_64x64 && result <= MAX_64x64); 121 return int128 (result); 122 } 123 } 124 125 /** 126 * Calculate x - y. Revert on overflow. 127 * 128 * @param x signed 64.64-bit fixed point number 129 * @param y signed 64.64-bit fixed point number 130 * @return signed 64.64-bit fixed point number 131 */ 132 function sub (int128 x, int128 y) internal pure returns (int128) { 133 unchecked { 134 int256 result = int256(x) - y; 135 require (result >= MIN_64x64 && result <= MAX_64x64); 136 return int128 (result); 137 } 138 } 139 140 /** 141 * Calculate x * y rounding down. Revert on overflow. 142 * 143 * @param x signed 64.64-bit fixed point number 144 * @param y signed 64.64-bit fixed point number 145 * @return signed 64.64-bit fixed point number 146 */ 147 function mul (int128 x, int128 y) internal pure returns (int128) { 148 unchecked { 149 int256 result = int256(x) * y >> 64; 150 require (result >= MIN_64x64 && result <= MAX_64x64); 151 return int128 (result); 152 } 153 } 154 155 /** 156 * Calculate x * y rounding towards zero, where x is signed 64.64 fixed point 157 * number and y is signed 256-bit integer number. Revert on overflow. 158 * 159 * @param x signed 64.64 fixed point number 160 * @param y signed 256-bit integer number 161 * @return signed 256-bit integer number 162 */ 163 function muli (int128 x, int256 y) internal pure returns (int256) { 164 unchecked { 165 if (x == MIN_64x64) { 166 require (y >= -0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF && 167 y <= 0x1000000000000000000000000000000000000000000000000); 168 return -y << 63; 169 } else { 170 bool negativeResult = false; 171 if (x < 0) { 172 x = -x; 173 negativeResult = true; 174 } 175 if (y < 0) { 176 y = -y; // We rely on overflow behavior here 177 negativeResult = !negativeResult; 178 } 179 uint256 absoluteResult = mulu (x, uint256 (y)); 180 if (negativeResult) { 181 require (absoluteResult <= 182 0x8000000000000000000000000000000000000000000000000000000000000000); 183 return -int256 (absoluteResult); // We rely on overflow behavior here 184 } else { 185 require (absoluteResult <= 186 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 187 return int256 (absoluteResult); 188 } 189 } 190 } 191 } 192 193 /** 194 * Calculate x * y rounding down, where x is signed 64.64 fixed point number 195 * and y is unsigned 256-bit integer number. Revert on overflow. 196 * 197 * @param x signed 64.64 fixed point number 198 * @param y unsigned 256-bit integer number 199 * @return unsigned 256-bit integer number 200 */ 201 function mulu (int128 x, uint256 y) internal pure returns (uint256) { 202 unchecked { 203 if (y == 0) return 0; 204 205 require (x >= 0); 206 207 uint256 lo = (uint256 (int256 (x)) * (y & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)) >> 64; 208 uint256 hi = uint256 (int256 (x)) * (y >> 128); 209 210 require (hi <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 211 hi <<= 64; 212 213 require (hi <= 214 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF - lo); 215 return hi + lo; 216 } 217 } 218 219 /** 220 * Calculate x / y rounding towards zero. Revert on overflow or when y is 221 * zero. 222 * 223 * @param x signed 64.64-bit fixed point number 224 * @param y signed 64.64-bit fixed point number 225 * @return signed 64.64-bit fixed point number 226 */ 227 function div (int128 x, int128 y) internal pure returns (int128) { 228 unchecked { 229 require (y != 0); 230 int256 result = (int256 (x) << 64) / y; 231 require (result >= MIN_64x64 && result <= MAX_64x64); 232 return int128 (result); 233 } 234 } 235 236 /** 237 * Calculate x / y rounding towards zero, where x and y are signed 256-bit 238 * integer numbers. Revert on overflow or when y is zero. 239 * 240 * @param x signed 256-bit integer number 241 * @param y signed 256-bit integer number 242 * @return signed 64.64-bit fixed point number 243 */ 244 function divi (int256 x, int256 y) internal pure returns (int128) { 245 unchecked { 246 require (y != 0); 247 248 bool negativeResult = false; 249 if (x < 0) { 250 x = -x; // We rely on overflow behavior here 251 negativeResult = true; 252 } 253 if (y < 0) { 254 y = -y; // We rely on overflow behavior here 255 negativeResult = !negativeResult; 256 } 257 uint128 absoluteResult = divuu (uint256 (x), uint256 (y)); 258 if (negativeResult) { 259 require (absoluteResult <= 0x80000000000000000000000000000000); 260 return -int128 (absoluteResult); // We rely on overflow behavior here 261 } else { 262 require (absoluteResult <= 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 263 return int128 (absoluteResult); // We rely on overflow behavior here 264 } 265 } 266 } 267 268 /** 269 * Calculate x / y rounding towards zero, where x and y are unsigned 256-bit 270 * integer numbers. Revert on overflow or when y is zero. 271 * 272 * @param x unsigned 256-bit integer number 273 * @param y unsigned 256-bit integer number 274 * @return signed 64.64-bit fixed point number 275 */ 276 function divu (uint256 x, uint256 y) internal pure returns (int128) { 277 unchecked { 278 require (y != 0); 279 uint128 result = divuu (x, y); 280 require (result <= uint128 (MAX_64x64)); 281 return int128 (result); 282 } 283 } 284 285 /** 286 * Calculate -x. Revert on overflow. 287 * 288 * @param x signed 64.64-bit fixed point number 289 * @return signed 64.64-bit fixed point number 290 */ 291 function neg (int128 x) internal pure returns (int128) { 292 unchecked { 293 require (x != MIN_64x64); 294 return -x; 295 } 296 } 297 298 /** 299 * Calculate |x|. Revert on overflow. 300 * 301 * @param x signed 64.64-bit fixed point number 302 * @return signed 64.64-bit fixed point number 303 */ 304 function abs (int128 x) internal pure returns (int128) { 305 unchecked { 306 require (x != MIN_64x64); 307 return x < 0 ? -x : x; 308 } 309 } 310 311 /** 312 * Calculate 1 / x rounding towards zero. Revert on overflow or when x is 313 * zero. 314 * 315 * @param x signed 64.64-bit fixed point number 316 * @return signed 64.64-bit fixed point number 317 */ 318 function inv (int128 x) internal pure returns (int128) { 319 unchecked { 320 require (x != 0); 321 int256 result = int256 (0x100000000000000000000000000000000) / x; 322 require (result >= MIN_64x64 && result <= MAX_64x64); 323 return int128 (result); 324 } 325 } 326 327 /** 328 * Calculate arithmetics average of x and y, i.e. (x + y) / 2 rounding down. 329 * 330 * @param x signed 64.64-bit fixed point number 331 * @param y signed 64.64-bit fixed point number 332 * @return signed 64.64-bit fixed point number 333 */ 334 function avg (int128 x, int128 y) internal pure returns (int128) { 335 unchecked { 336 return int128 ((int256 (x) + int256 (y)) >> 1); 337 } 338 } 339 340 /** 341 * Calculate geometric average of x and y, i.e. sqrt (x * y) rounding down. 342 * Revert on overflow or in case x * y is negative. 343 * 344 * @param x signed 64.64-bit fixed point number 345 * @param y signed 64.64-bit fixed point number 346 * @return signed 64.64-bit fixed point number 347 */ 348 function gavg (int128 x, int128 y) internal pure returns (int128) { 349 unchecked { 350 int256 m = int256 (x) * int256 (y); 351 require (m >= 0); 352 require (m < 353 0x4000000000000000000000000000000000000000000000000000000000000000); 354 return int128 (sqrtu (uint256 (m))); 355 } 356 } 357 358 /** 359 * Calculate x^y assuming 0^0 is 1, where x is signed 64.64 fixed point number 360 * and y is unsigned 256-bit integer number. Revert on overflow. 361 * 362 * @param x signed 64.64-bit fixed point number 363 * @param y uint256 value 364 * @return signed 64.64-bit fixed point number 365 */ 366 function pow (int128 x, uint256 y) internal pure returns (int128) { 367 unchecked { 368 bool negative = x < 0 && y & 1 == 1; 369 370 uint256 absX = uint128 (x < 0 ? -x : x); 371 uint256 absResult; 372 absResult = 0x100000000000000000000000000000000; 373 374 if (absX <= 0x10000000000000000) { 375 absX <<= 63; 376 while (y != 0) { 377 if (y & 0x1 != 0) { 378 absResult = absResult * absX >> 127; 379 } 380 absX = absX * absX >> 127; 381 382 if (y & 0x2 != 0) { 383 absResult = absResult * absX >> 127; 384 } 385 absX = absX * absX >> 127; 386 387 if (y & 0x4 != 0) { 388 absResult = absResult * absX >> 127; 389 } 390 absX = absX * absX >> 127; 391 392 if (y & 0x8 != 0) { 393 absResult = absResult * absX >> 127; 394 } 395 absX = absX * absX >> 127; 396 397 y >>= 4; 398 } 399 400 absResult >>= 64; 401 } else { 402 uint256 absXShift = 63; 403 if (absX < 0x1000000000000000000000000) { absX <<= 32; absXShift -= 32; } 404 if (absX < 0x10000000000000000000000000000) { absX <<= 16; absXShift -= 16; } 405 if (absX < 0x1000000000000000000000000000000) { absX <<= 8; absXShift -= 8; } 406 if (absX < 0x10000000000000000000000000000000) { absX <<= 4; absXShift -= 4; } 407 if (absX < 0x40000000000000000000000000000000) { absX <<= 2; absXShift -= 2; } 408 if (absX < 0x80000000000000000000000000000000) { absX <<= 1; absXShift -= 1; } 409 410 uint256 resultShift = 0; 411 while (y != 0) { 412 require (absXShift < 64); 413 414 if (y & 0x1 != 0) { 415 absResult = absResult * absX >> 127; 416 resultShift += absXShift; 417 if (absResult > 0x100000000000000000000000000000000) { 418 absResult >>= 1; 419 resultShift += 1; 420 } 421 } 422 absX = absX * absX >> 127; 423 absXShift <<= 1; 424 if (absX >= 0x100000000000000000000000000000000) { 425 absX >>= 1; 426 absXShift += 1; 427 } 428 429 y >>= 1; 430 } 431 432 require (resultShift < 64); 433 absResult >>= 64 - resultShift; 434 } 435 int256 result = negative ? -int256 (absResult) : int256 (absResult); 436 require (result >= MIN_64x64 && result <= MAX_64x64); 437 return int128 (result); 438 } 439 } 440 441 /** 442 * Calculate sqrt (x) rounding down. Revert if x < 0. 443 * 444 * @param x signed 64.64-bit fixed point number 445 * @return signed 64.64-bit fixed point number 446 */ 447 function sqrt (int128 x) internal pure returns (int128) { 448 unchecked { 449 require (x >= 0); 450 return int128 (sqrtu (uint256 (int256 (x)) << 64)); 451 } 452 } 453 454 /** 455 * Calculate binary logarithm of x. Revert if x <= 0. 456 * 457 * @param x signed 64.64-bit fixed point number 458 * @return signed 64.64-bit fixed point number 459 */ 460 function log_2 (int128 x) internal pure returns (int128) { 461 unchecked { 462 require (x > 0); 463 464 int256 msb = 0; 465 int256 xc = x; 466 if (xc >= 0x10000000000000000) { xc >>= 64; msb += 64; } 467 if (xc >= 0x100000000) { xc >>= 32; msb += 32; } 468 if (xc >= 0x10000) { xc >>= 16; msb += 16; } 469 if (xc >= 0x100) { xc >>= 8; msb += 8; } 470 if (xc >= 0x10) { xc >>= 4; msb += 4; } 471 if (xc >= 0x4) { xc >>= 2; msb += 2; } 472 if (xc >= 0x2) msb += 1; // No need to shift xc anymore 473 474 int256 result = msb - 64 << 64; 475 uint256 ux = uint256 (int256 (x)) << uint256 (127 - msb); 476 for (int256 bit = 0x8000000000000000; bit > 0; bit >>= 1) { 477 ux *= ux; 478 uint256 b = ux >> 255; 479 ux >>= 127 + b; 480 result += bit * int256 (b); 481 } 482 483 return int128 (result); 484 } 485 } 486 487 /** 488 * Calculate natural logarithm of x. Revert if x <= 0. 489 * 490 * @param x signed 64.64-bit fixed point number 491 * @return signed 64.64-bit fixed point number 492 */ 493 function ln (int128 x) internal pure returns (int128) { 494 unchecked { 495 require (x > 0); 496 497 return int128 (int256 ( 498 uint256 (int256 (log_2 (x))) * 0xB17217F7D1CF79ABC9E3B39803F2F6AF >> 128)); 499 } 500 } 501 502 /** 503 * Calculate binary exponent of x. Revert on overflow. 504 * 505 * @param x signed 64.64-bit fixed point number 506 * @return signed 64.64-bit fixed point number 507 */ 508 function exp_2 (int128 x) internal pure returns (int128) { 509 unchecked { 510 require (x < 0x400000000000000000); // Overflow 511 512 if (x < -0x400000000000000000) return 0; // Underflow 513 514 uint256 result = 0x80000000000000000000000000000000; 515 516 if (x & 0x8000000000000000 > 0) 517 result = result * 0x16A09E667F3BCC908B2FB1366EA957D3E >> 128; 518 if (x & 0x4000000000000000 > 0) 519 result = result * 0x1306FE0A31B7152DE8D5A46305C85EDEC >> 128; 520 if (x & 0x2000000000000000 > 0) 521 result = result * 0x1172B83C7D517ADCDF7C8C50EB14A791F >> 128; 522 if (x & 0x1000000000000000 > 0) 523 result = result * 0x10B5586CF9890F6298B92B71842A98363 >> 128; 524 if (x & 0x800000000000000 > 0) 525 result = result * 0x1059B0D31585743AE7C548EB68CA417FD >> 128; 526 if (x & 0x400000000000000 > 0) 527 result = result * 0x102C9A3E778060EE6F7CACA4F7A29BDE8 >> 128; 528 if (x & 0x200000000000000 > 0) 529 result = result * 0x10163DA9FB33356D84A66AE336DCDFA3F >> 128; 530 if (x & 0x100000000000000 > 0) 531 result = result * 0x100B1AFA5ABCBED6129AB13EC11DC9543 >> 128; 532 if (x & 0x80000000000000 > 0) 533 result = result * 0x10058C86DA1C09EA1FF19D294CF2F679B >> 128; 534 if (x & 0x40000000000000 > 0) 535 result = result * 0x1002C605E2E8CEC506D21BFC89A23A00F >> 128; 536 if (x & 0x20000000000000 > 0) 537 result = result * 0x100162F3904051FA128BCA9C55C31E5DF >> 128; 538 if (x & 0x10000000000000 > 0) 539 result = result * 0x1000B175EFFDC76BA38E31671CA939725 >> 128; 540 if (x & 0x8000000000000 > 0) 541 result = result * 0x100058BA01FB9F96D6CACD4B180917C3D >> 128; 542 if (x & 0x4000000000000 > 0) 543 result = result * 0x10002C5CC37DA9491D0985C348C68E7B3 >> 128; 544 if (x & 0x2000000000000 > 0) 545 result = result * 0x1000162E525EE054754457D5995292026 >> 128; 546 if (x & 0x1000000000000 > 0) 547 result = result * 0x10000B17255775C040618BF4A4ADE83FC >> 128; 548 if (x & 0x800000000000 > 0) 549 result = result * 0x1000058B91B5BC9AE2EED81E9B7D4CFAB >> 128; 550 if (x & 0x400000000000 > 0) 551 result = result * 0x100002C5C89D5EC6CA4D7C8ACC017B7C9 >> 128; 552 if (x & 0x200000000000 > 0) 553 result = result * 0x10000162E43F4F831060E02D839A9D16D >> 128; 554 if (x & 0x100000000000 > 0) 555 result = result * 0x100000B1721BCFC99D9F890EA06911763 >> 128; 556 if (x & 0x80000000000 > 0) 557 result = result * 0x10000058B90CF1E6D97F9CA14DBCC1628 >> 128; 558 if (x & 0x40000000000 > 0) 559 result = result * 0x1000002C5C863B73F016468F6BAC5CA2B >> 128; 560 if (x & 0x20000000000 > 0) 561 result = result * 0x100000162E430E5A18F6119E3C02282A5 >> 128; 562 if (x & 0x10000000000 > 0) 563 result = result * 0x1000000B1721835514B86E6D96EFD1BFE >> 128; 564 if (x & 0x8000000000 > 0) 565 result = result * 0x100000058B90C0B48C6BE5DF846C5B2EF >> 128; 566 if (x & 0x4000000000 > 0) 567 result = result * 0x10000002C5C8601CC6B9E94213C72737A >> 128; 568 if (x & 0x2000000000 > 0) 569 result = result * 0x1000000162E42FFF037DF38AA2B219F06 >> 128; 570 if (x & 0x1000000000 > 0) 571 result = result * 0x10000000B17217FBA9C739AA5819F44F9 >> 128; 572 if (x & 0x800000000 > 0) 573 result = result * 0x1000000058B90BFCDEE5ACD3C1CEDC823 >> 128; 574 if (x & 0x400000000 > 0) 575 result = result * 0x100000002C5C85FE31F35A6A30DA1BE50 >> 128; 576 if (x & 0x200000000 > 0) 577 result = result * 0x10000000162E42FF0999CE3541B9FFFCF >> 128; 578 if (x & 0x100000000 > 0) 579 result = result * 0x100000000B17217F80F4EF5AADDA45554 >> 128; 580 if (x & 0x80000000 > 0) 581 result = result * 0x10000000058B90BFBF8479BD5A81B51AD >> 128; 582 if (x & 0x40000000 > 0) 583 result = result * 0x1000000002C5C85FDF84BD62AE30A74CC >> 128; 584 if (x & 0x20000000 > 0) 585 result = result * 0x100000000162E42FEFB2FED257559BDAA >> 128; 586 if (x & 0x10000000 > 0) 587 result = result * 0x1000000000B17217F7D5A7716BBA4A9AE >> 128; 588 if (x & 0x8000000 > 0) 589 result = result * 0x100000000058B90BFBE9DDBAC5E109CCE >> 128; 590 if (x & 0x4000000 > 0) 591 result = result * 0x10000000002C5C85FDF4B15DE6F17EB0D >> 128; 592 if (x & 0x2000000 > 0) 593 result = result * 0x1000000000162E42FEFA494F1478FDE05 >> 128; 594 if (x & 0x1000000 > 0) 595 result = result * 0x10000000000B17217F7D20CF927C8E94C >> 128; 596 if (x & 0x800000 > 0) 597 result = result * 0x1000000000058B90BFBE8F71CB4E4B33D >> 128; 598 if (x & 0x400000 > 0) 599 result = result * 0x100000000002C5C85FDF477B662B26945 >> 128; 600 if (x & 0x200000 > 0) 601 result = result * 0x10000000000162E42FEFA3AE53369388C >> 128; 602 if (x & 0x100000 > 0) 603 result = result * 0x100000000000B17217F7D1D351A389D40 >> 128; 604 if (x & 0x80000 > 0) 605 result = result * 0x10000000000058B90BFBE8E8B2D3D4EDE >> 128; 606 if (x & 0x40000 > 0) 607 result = result * 0x1000000000002C5C85FDF4741BEA6E77E >> 128; 608 if (x & 0x20000 > 0) 609 result = result * 0x100000000000162E42FEFA39FE95583C2 >> 128; 610 if (x & 0x10000 > 0) 611 result = result * 0x1000000000000B17217F7D1CFB72B45E1 >> 128; 612 if (x & 0x8000 > 0) 613 result = result * 0x100000000000058B90BFBE8E7CC35C3F0 >> 128; 614 if (x & 0x4000 > 0) 615 result = result * 0x10000000000002C5C85FDF473E242EA38 >> 128; 616 if (x & 0x2000 > 0) 617 result = result * 0x1000000000000162E42FEFA39F02B772C >> 128; 618 if (x & 0x1000 > 0) 619 result = result * 0x10000000000000B17217F7D1CF7D83C1A >> 128; 620 if (x & 0x800 > 0) 621 result = result * 0x1000000000000058B90BFBE8E7BDCBE2E >> 128; 622 if (x & 0x400 > 0) 623 result = result * 0x100000000000002C5C85FDF473DEA871F >> 128; 624 if (x & 0x200 > 0) 625 result = result * 0x10000000000000162E42FEFA39EF44D91 >> 128; 626 if (x & 0x100 > 0) 627 result = result * 0x100000000000000B17217F7D1CF79E949 >> 128; 628 if (x & 0x80 > 0) 629 result = result * 0x10000000000000058B90BFBE8E7BCE544 >> 128; 630 if (x & 0x40 > 0) 631 result = result * 0x1000000000000002C5C85FDF473DE6ECA >> 128; 632 if (x & 0x20 > 0) 633 result = result * 0x100000000000000162E42FEFA39EF366F >> 128; 634 if (x & 0x10 > 0) 635 result = result * 0x1000000000000000B17217F7D1CF79AFA >> 128; 636 if (x & 0x8 > 0) 637 result = result * 0x100000000000000058B90BFBE8E7BCD6D >> 128; 638 if (x & 0x4 > 0) 639 result = result * 0x10000000000000002C5C85FDF473DE6B2 >> 128; 640 if (x & 0x2 > 0) 641 result = result * 0x1000000000000000162E42FEFA39EF358 >> 128; 642 if (x & 0x1 > 0) 643 result = result * 0x10000000000000000B17217F7D1CF79AB >> 128; 644 645 result >>= uint256 (int256 (63 - (x >> 64))); 646 require (result <= uint256 (int256 (MAX_64x64))); 647 648 return int128 (int256 (result)); 649 } 650 } 651 652 /** 653 * Calculate natural exponent of x. Revert on overflow. 654 * 655 * @param x signed 64.64-bit fixed point number 656 * @return signed 64.64-bit fixed point number 657 */ 658 function exp (int128 x) internal pure returns (int128) { 659 unchecked { 660 require (x < 0x400000000000000000); // Overflow 661 662 if (x < -0x400000000000000000) return 0; // Underflow 663 664 return exp_2 ( 665 int128 (int256 (x) * 0x171547652B82FE1777D0FFDA0D23A7D12 >> 128)); 666 } 667 } 668 669 /** 670 * Calculate x / y rounding towards zero, where x and y are unsigned 256-bit 671 * integer numbers. Revert on overflow or when y is zero. 672 * 673 * @param x unsigned 256-bit integer number 674 * @param y unsigned 256-bit integer number 675 * @return unsigned 64.64-bit fixed point number 676 */ 677 function divuu (uint256 x, uint256 y) private pure returns (uint128) { 678 unchecked { 679 require (y != 0); 680 681 uint256 result; 682 683 if (x <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) 684 result = (x << 64) / y; 685 else { 686 uint256 msb = 192; 687 uint256 xc = x >> 192; 688 if (xc >= 0x100000000) { xc >>= 32; msb += 32; } 689 if (xc >= 0x10000) { xc >>= 16; msb += 16; } 690 if (xc >= 0x100) { xc >>= 8; msb += 8; } 691 if (xc >= 0x10) { xc >>= 4; msb += 4; } 692 if (xc >= 0x4) { xc >>= 2; msb += 2; } 693 if (xc >= 0x2) msb += 1; // No need to shift xc anymore 694 695 result = (x << 255 - msb) / ((y - 1 >> msb - 191) + 1); 696 require (result <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 697 698 uint256 hi = result * (y >> 128); 699 uint256 lo = result * (y & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 700 701 uint256 xh = x >> 192; 702 uint256 xl = x << 64; 703 704 if (xl < lo) xh -= 1; 705 xl -= lo; // We rely on overflow behavior here 706 lo = hi << 128; 707 if (xl < lo) xh -= 1; 708 xl -= lo; // We rely on overflow behavior here 709 710 assert (xh == hi >> 128); 711 712 result += xl / y; 713 } 714 715 require (result <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF); 716 return uint128 (result); 717 } 718 } 719 720 /** 721 * Calculate sqrt (x) rounding down, where x is unsigned 256-bit integer 722 * number. 723 * 724 * @param x unsigned 256-bit integer number 725 * @return unsigned 128-bit integer number 726 */ 727 function sqrtu (uint256 x) private pure returns (uint128) { 728 unchecked { 729 if (x == 0) return 0; 730 else { 731 uint256 xx = x; 732 uint256 r = 1; 733 if (xx >= 0x100000000000000000000000000000000) { xx >>= 128; r <<= 64; } 734 if (xx >= 0x10000000000000000) { xx >>= 64; r <<= 32; } 735 if (xx >= 0x100000000) { xx >>= 32; r <<= 16; } 736 if (xx >= 0x10000) { xx >>= 16; r <<= 8; } 737 if (xx >= 0x100) { xx >>= 8; r <<= 4; } 738 if (xx >= 0x10) { xx >>= 4; r <<= 2; } 739 if (xx >= 0x4) { r <<= 1; } 740 r = (r + x / r) >> 1; 741 r = (r + x / r) >> 1; 742 r = (r + x / r) >> 1; 743 r = (r + x / r) >> 1; 744 r = (r + x / r) >> 1; 745 r = (r + x / r) >> 1; 746 r = (r + x / r) >> 1; // Seven iterations should be enough 747 uint256 r1 = x / r; 748 return uint128 (r < r1 ? r : r1); 749 } 750 } 751 } 752 }