erc20-demurrage-token

ERC20 token with redistributed continual demurrage
Info | Log | Files | Refs | README

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 }