Michael.W基于Foundry精读Openzeppelin第11期——Math.sol

  • Michael.W
  • 更新于 2023-07-22 17:34
  • 阅读 1829

Math库为合约开发提供了solidity内置的uint256运算以外的其他整形运算方法。solidity内置的整形运算,每一步都会做overflow revert(除非unchecked{}),而Math库会在不影响结果准确性的前提下利用位溢出进行更加tricky的操作。

0. 版本

[openzeppelin]:v4.8.3,[forge-std]:v1.5.6

0.1 Math.sol

Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/math/Math.sol

Math库为合约开发提供了solidity内置的uint256运算以外的其他整形运算方法。solidity内置的整形运算,每一步都会做overflow revert(除非unchecked{}),而Math库会在不影响结果准确性的前提下利用位溢出进行更加tricky的操作。

个人认为Math库可以算是openzeppelin中最复杂的库,里面涉及大量的数学理论操作(例如:牛顿迭代法和逆元)和内联汇编

1. 目标合约

封装Math library成为一个可调用合约:

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/utils/math/MockMath.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "openzeppelin-contracts/contracts/utils/math/Math.sol";

contract MockMath {
    using Math for uint;

    function max(uint a, uint b) external pure returns (uint){
        return a.max(b);
    }

    function min(uint a, uint b) external pure returns (uint){
        return a.min(b);
    }

    function average(uint a, uint b) external pure returns (uint){
        return a.average(b);
    }

    function ceilDiv(uint a, uint b) external pure returns (uint){
        return a.ceilDiv(b);
    }

    function mulDiv(uint x, uint y, uint denominator) external pure returns (uint){
        return x.mulDiv(y, denominator);
    }

    function mulDiv(uint x, uint y, uint denominator, Math.Rounding rounding) external pure returns (uint){
        return x.mulDiv(y, denominator, rounding);
    }

    function sqrt(uint a) external pure returns (uint){
        return a.sqrt();
    }

    function sqrt(uint a, Math.Rounding rounding) external pure returns (uint) {
        return a.sqrt(rounding);
    }

    function log2(uint value) external pure returns (uint){
        return value.log2();
    }

    function log2(uint value, Math.Rounding rounding) external pure returns (uint) {
        return value.log2(rounding);
    }

    function log10(uint value) external pure returns (uint) {
        return value.log10();
    }

    function log10(uint value, Math.Rounding rounding) external pure returns (uint) {
        return value.log10(rounding);
    }

    function log256(uint value) external pure returns (uint) {
        return value.log256();
    }

    function log256(uint value, Math.Rounding rounding) external pure returns (uint) {
        return value.log256(rounding);
    }
}

全部foundry测试合约:

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/math/Math.t.sol

2. 代码精读

2.1 枚举类型Rounding

Math库中,无论是取平方根还是各种对数运算都提供设置结果取整方式:向下取整和向上取整。但是,向零取整并未在代码中使用。

    enum Rounding {
        // 负无穷方向(向下)取整
        Down,
        // 正无穷方向(向上)取整
        Up,
        // 向0取整(目前未使用到)
        Zero
    }

2.2 max(uint256, uint256)

获取二值中的最大值。

    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        // 直接用三元运算符实现取二值取最大的操作
        return a > b ? a : b;
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Max() external {
        uint max = 1024;
        uint min = max - 1;
        assertEq(mm.max(max, min), max);
        assertEq(mm.max(min, max), max);
        assertEq(mm.max(min, min), min);
    }
}

2.3 min(uint256, uint256)

获取二值中的最小值。

    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        // 直接用三元运算符实现取二值取最小的操作
        return a < b ? a : b;
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Min() external {
        uint min = 1024;
        uint max = min + 1;
        assertEq(mm.min(max, min), min);
        assertEq(mm.min(min, max), min);
        assertEq(mm.min(max, max), max);
    }
}

2.4 average(uint256, uint256)

获取二值的均值。如果无法整除,结果向0取整。

注:如果直接使用solidity的内置加法去计算均值—— (a + b) / 2,a + b可能会造成overflow而revert。而本方法可以在a+b溢出的情况下保证结果的准确性。

     function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // a & b: a和b都是1或0的位会被筛选出来。由于是求二者平均值,所以都是1的位仍然保留1,都是0的位仍然保留0
        // a ^ b: a和b对应位数字不同(一个是0一个是1)的位会被挑出。在求平均值的过程中,每一个这样的位都可以通过右移1位,即除以2来得到平均值
        // 最后将上述结果相加,就得到a和b的平均值
        return (a & b) + (a ^ b) / 2;
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Average() external {
        uint odd = 1023;
        uint even = 1024;
        // odd + odd
        assertEq(mm.average(odd, odd + 2), odd + 1);
        // even + even
        assertEq(mm.average(even, even + 2), even + 1);
        // odd + even
        assertEq(mm.average(even, odd), (even + odd) / 2);
        // a+b will cause overflow
        assertEq(mm.average(type(uint).max, type(uint).max - 2), type(uint).max - 1);
    }
}

2.5 ceilDiv(uint256, uint256)

天花板除法(即结果向上取整)。solidity中的内置/是地板除(即结果向下取整)

    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // 常规的天花板除的思路是(a + b - 1) / b,但是分子容易造成正向溢出。将分子拆分开:
        // (a+b-1)/b = ((a-1)+b)/b = (a-1)/b+1
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_CeilDiv() external {
        // exact division
        assertEq(mm.ceilDiv(1024, 2), 512);
        // rounds up on division with remainders
        assertEq(mm.ceilDiv(1024, 10), 103);
        // exact division without overflow
        assertEq(mm.ceilDiv(type(uint).max, 1), type(uint).max);
        // rounds up without overflow
        assertEq(mm.ceilDiv(type(uint).max, type(uint).max - 1), 2);
    }
}

2.6 mulDiv(uint256,uint256,uint256) && mulDiv(uint256,uint256,uint256,Rounding)

  • mulDiv(uint256 x,uint256 y,uint256 denominator):计算x*y/denominator的结果,向下取整。如果最后的结果大于type(uint256).max或denominator等于0,将revert;

  • mulDiv(uint256 x,uint256 y,uint256 denominator,Rounding rounding):计算x*y/denominator的结果(可选择取整方式——向负无穷方向取整、向正无穷方向取整或向0取整)。

注:个人认为这两个方法是Math库中最复杂且充满数学理论+位溢出技巧的方法。

    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator
    ) internal pure returns (uint256 result) {
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 定义两个uint256变量变量表示一个512位的整形结果,即x*y的乘积(假设是512位)表示为:prod1 * 2^256 + prod0
            uint256 prod0;
            uint256 prod1; 
            assembly {
                // not(0),即~uint256(0)=2^256-1
                // mm = x * y % (2^256-1)
                let mm := mulmod(x, y, not(0))
                // prod0 = x*y的低256位, 即x * y % (2^256)
                prod0 := mul(x, y)
                // lt(mm, prod0): 如果mm<prod0,结果为1;否则结果为0
                // sub(mm, prod0): mm-prod0
                // 如果mm<prod0, prod1=mm-prod0-1
                // 如果mm>=prod0, prod1=mm-prod0
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
                // 至此:x*y=prod1*2^256+prod0,用两个uint256表示了一个uint512的整数
            }

            // 如果prod1等于0,表示x*y的积小于2^256。即x*y=prod0
            if (prod1 == 0) {
                // 直接用uint256的除法计算结果
                return prod0 / denominator;
            }

            // (走到这表示x*y>=2^256)
            // 确保最后的商小于2^256(因为返回值为uint256,不能有溢出),同时也对除数不为0做了检查
            require(denominator > prod1);

            // 开始实现512位整数除以256位整数的计算
            uint256 remainder;
            assembly {
                // remainder为x*y对denominator的余数
                remainder := mulmod(x, y, denominator)

                // 如果remainder>prod0, prod1=prod1-1;
                // 如果remainder<=prod0, prod1不变
                prod1 := sub(prod1, gt(remainder, prod0))
                // prod0=prod0-remainder
                prod0 := sub(prod0, remainder)  
                // 注:此时的prod1*2^256+prod0已经是可以被denominator整除
            }

            // twos为可以整除denominator的最大的2的幂
            // 参考:https://cs.stackexchange.com/questions/138556/how-to-find-the-largest-power-of-two-divisor-of-a-given-integer
            // 注:由于前面已经检查过denominator不为0,所以 ~denominator + 1 不会溢出
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // 由于此时的prod1*2^256+prod0可以被denominator整除,denominator也可以被twos整除,所以prod1*2^256+prod0一定也可以被twos整除。分子分母同时除以twos,商不变:  (prod1*2^256+prod0)/twos与denominator/twos的商就是最后的结果

                // 1. 将分母缩小twos倍:denominator=denominator/twos
                denominator := div(denominator, twos)
                // 2. 将分子缩小twos倍:这里需要注意,由于(prod1*2^256+prod0)可以被twos整除,且prod1*2^256可以被twos整除,prod0一定也可以被twos整除
                // prod0=prod0/twos
                prod0 := div(prod0, twos)

                // 由于prod1*2^256是个超过uint256的数,所以不能直接用solidity里的内置整数除法。先计算2^256/twos,这样就可以在uint256的范围内计算prod1*2^256/twos的值:
                // sub(0, twos)其实就是溢出情况下的2^256-twos;
                // div(sub(0, twos), twos):(2^256-twos)/twos=2^256/twos-1
                // add(div(sub(0, twos), twos), 1): 就是2^256/twos
                twos := add(div(sub(0, twos), twos), 1)
            }

            // 由于此时的twos已经变成了2^256/twos,prod1 * twos其实就是prod1*2^256/原twos
            // 将已经缩小twos倍后的prod0和prod1做或运算,得到(prod1*2^256+prod0)/原twos,即x*y/原twos
            prod0 |= prod1 * twos;

            // denominator是原本denominator除以自己最大的2的幂的因子,所以denominator现在一定是奇数。去计算denominator对2^256的逆元inverse,那么denominator * inverse % 2^256 =1

            // 下面是计算逆元inverse的过程,该过程需要通过牛顿迭代法来逐步提升精度。每一次迭代,会双倍提升精度。我们从4位正确的seed开始迭代计算逆元inverse,即:denominator * inv = 1 mod 2^4
            // 注:具体数学内在逻辑参见 Hensel's lifting lemma,这里不做解释
            uint256 inverse = (3 * denominator) ^ 2;
            // inverse为denominator对2^8的逆元
            inverse *= 2 - denominator * inverse;
            // inverse为denominator对2^16的逆元
            inverse *= 2 - denominator * inverse;
            // inverse为denominator对2^32的逆元
            inverse *= 2 - denominator * inverse;
            // inverse为denominator对2^64的逆元
            inverse *= 2 - denominator * inverse;
            // inverse为denominator对2^128的逆元
            inverse *= 2 - denominator * inverse;
            // inverse为denominator对2^256的逆元
            inverse *= 2 - denominator * inverse; 

            // 由于denominator对2^256的逆元inverse已经求出,乘以该逆元inverse等于除以denominator
            result = prod0 * inverse;
            return result;
        }
    }

    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator,
        Rounding rounding
    ) internal pure returns (uint256) {  
        // 计算x*y/denominator的结果(向下取整)    
        uint256 result = mulDiv(x, y, denominator);
         // 如果为向正无穷方向取整 且 x*y/denominator>0,结果result自加1。否则直接返回result
         // 注: 这个 mulmod(x,y,denominator)>0的判断是为了排除"x*y正好被denominator整除却向上取整自加1"的情况
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_MulDiv() external {
        // 1. x*y without overflow with rounding options
        assertEq(mm.mulDiv(2, 3, 4, Math.Rounding.Down), 1);
        assertEq(mm.mulDiv(2, 3, 3, Math.Rounding.Down), 2);
        assertEq(mm.mulDiv(2, 3, 4, Math.Rounding.Up), 2);
        assertEq(mm.mulDiv(2, 3, 3, Math.Rounding.Up), 2);
        // revert if denominator==0
        vm.expectRevert();
        mm.mulDiv(1, 2, 0, Math.Rounding.Down);

        // 2. x*y overflow with rounding options
        uint uintMax = type(uint).max;
        assertEq(mm.mulDiv(uintMax - 2, uintMax - 1, uintMax, Math.Rounding.Down), uintMax - 3);
        assertEq(mm.mulDiv(uintMax - 1, uintMax, uintMax, Math.Rounding.Down), uintMax - 1);
        assertEq(mm.mulDiv(uintMax - 2, uintMax - 1, uintMax, Math.Rounding.Up), uintMax - 2);
        assertEq(mm.mulDiv(uintMax, uintMax - 1, uintMax, Math.Rounding.Up), uintMax - 1);
        // revert if denominator==0
        vm.expectRevert();
        mm.mulDiv(uintMax - 1, uintMax, 0, Math.Rounding.Down);

        // 3. x*y without overflow without rounding options
        assertEq(mm.mulDiv(2, 3, 4), 1);
        assertEq(mm.mulDiv(2, 3, 3), 2);
        // revert if denominator==0
        vm.expectRevert();
        mm.mulDiv(1, 2, 0);

        // 4. x*y overflow without rounding options
        assertEq(mm.mulDiv(uintMax - 2, uintMax - 1, uintMax), uintMax - 3);
        assertEq(mm.mulDiv(uintMax - 1, uintMax, uintMax), uintMax - 1);
        // revert if denominator==0
        vm.expectRevert();
        mm.mulDiv(uintMax - 1, uintMax, 0);
    }
}

2.7 sqrt(uint256) && sqrt(uint256,Rounding)

  • sqrt(uint256 a):计算a的平方根,向下取整;

  • sqrt(uint256 a, Rounding rounding):求a的平方根(可选择取整方式——向负无穷方向取整、向正无穷方向取整或向0取整)。如果传入0,返回0。

    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            // 如果a等于0,直接返回0
            return 0;
        }

    // 思路:
    // 假设a=15,二进制为b1111,那么 b1000<b1111<b10000
    // 这里a的最高有效位(msb)为b1000, 那么整数a存在于区间[msb(a),2*msb(a))。msb(a)可以表示为2^n,即n=log2(a),那么a就存在于区间[ 2^n,2^(n+1) ), sqrt(a)就存在于[ 2^(n/2),2^(n/2+1/2) ),进而可推导出 2^(n/2) <= sqrt(a) < 2^(n/2+1)
    // 因为n=log2(a),所以 2^(log2(a)/2) <= sqrt(a) < 2^(log2(a)/2+1)
    // 综上,2^(log2(a)/2)就是sqrt(a)的一个很好的近似,起码保证最高位是一样的

    // result为2^(log2(a)/2), 它其实是a的一位精度(最高有效位)的估计值。一个uint256的平方根其实就是一个uint128的数,即2^(256/2)=2^128
    // 之后使用Newton's method(牛顿迭代法)进行收敛,去寻找sqrt(a)的最佳近似值
        uint256 result = 1 << (log2(a) >> 1);

        // Newton's method是二次收敛的,每迭代一次精度加倍。result目前拥有最高位准确性(1位精度),因此我们最多需要迭代7次(2^7=128)才能将具有1位精度的result转换为预期的更近似真实平方根的结果(uint128)。

        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 对result进行7次Newton's method的迭代运算
            // 每次运算为:当前result + a/当前result的和取均值
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            // 由于要向下取整,最后的在迭代7次得到result和a/result中选择最小值作为平方根返回
            return min(result, a / result);
        }
    }

    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            // 计算a的平方根(向下取整)
            uint256 result = sqrt(a);
            // 如果为向正无穷方向取整 且 result^2 < a,结果result自加1。否则直接返回result
            // 注: 这个result^2 < value的判断是为了排除"result正好是a的平方根却向上取整自加1"的情况
            return result + (rounding == Rounding.Up && result * result < a ? 1 : 0);
        }
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Sqrt() external {
        uint sqrtMaxUintRoundingDown = 340282366920938463463374607431768211455;
        // without rounding option
        assertEq(mm.sqrt(0), 0);
        assertEq(mm.sqrt(1), 1);
        assertEq(mm.sqrt(2), 1);
        assertEq(mm.sqrt(3), 1);
        assertEq(mm.sqrt(4), 2);
        assertEq(mm.sqrt(101), 10);
        assertEq(mm.sqrt(120), 10);
        assertEq(mm.sqrt(type(uint).max), sqrtMaxUintRoundingDown);

        // with rounding down option
        assertEq(mm.sqrt(0, Math.Rounding.Down), 0);
        assertEq(mm.sqrt(1, Math.Rounding.Down), 1);
        assertEq(mm.sqrt(2, Math.Rounding.Down), 1);
        assertEq(mm.sqrt(3, Math.Rounding.Down), 1);
        assertEq(mm.sqrt(4, Math.Rounding.Down), 2);
        assertEq(mm.sqrt(101, Math.Rounding.Down), 10);
        assertEq(mm.sqrt(120, Math.Rounding.Down), 10);
        assertEq(mm.sqrt(type(uint).max, Math.Rounding.Down), sqrtMaxUintRoundingDown);

        // with rounding up option
        assertEq(mm.sqrt(0, Math.Rounding.Up), 0);
        assertEq(mm.sqrt(1, Math.Rounding.Up), 1);
        assertEq(mm.sqrt(2, Math.Rounding.Up), 2);
        assertEq(mm.sqrt(3, Math.Rounding.Up), 2);
        assertEq(mm.sqrt(4, Math.Rounding.Up), 2);
        assertEq(mm.sqrt(101, Math.Rounding.Up), 11);
        assertEq(mm.sqrt(120, Math.Rounding.Up), 11);
        assertEq(mm.sqrt(type(uint).max, Math.Rounding.Up), sqrtMaxUintRoundingDown + 1);
    }
}

2.8 log2(uint256) && log2(uint256,Rounding)

  • log2(uint256 value):value对2取对数(向下取整)。如果传入0,返回0;

  • log2(uint256 value, Rounding rounding):value对2取对数(可选择取整方式——向负无穷方向取整、向正无穷方向取整或向0取整)。如果传入0,返回0。

    // 思路:value依次试着除以2^128、2^64、2^32...2^1,每当出现商大于0时,在result中自加当前的幂次。然后value自更新。
    function log2(uint256 value) internal pure returns (uint256) {
        // 用于记录value对2取对数的结果
        uint256 result = 0;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 如果value/(2^128)>0
            if (value >> 128 > 0) {
                // value=value/(2^128)
                value >>= 128;
                // result自增128
                result += 128;
            }
            // 如果value/(2^64)>0
            if (value >> 64 > 0) {
                // value=value/(2^64)
                value >>= 64;
                // result自增64
                result += 64;
            }
            // 如果value/(2^32)>0
            if (value >> 32 > 0) {
                // value=value/(2^32)
                value >>= 32;
                // result自增32
                result += 32;
            }
            // 如果value/(2^16)>0
            if (value >> 16 > 0) {
                // value=value/(2^16)
                value >>= 16;
                // result自增16
                result += 16;
            }
             // 如果value/(2^8)>0
            if (value >> 8 > 0) {
            // value=value/(2^8)
                value >>= 8;
                // result自增8
                result += 8;
            }
            // 如果value/(2^4)>0
            if (value >> 4 > 0) {
                // value=value/(2^4)
                value >>= 4;
                // result自增4
                result += 4;
            }
            // 如果value/(2^2)>0
            if (value >> 2 > 0) {
                // value=value/(2^2)
                value >>= 2;
                // result自增2
                result += 2;
            }
            // 如果value/2>0
            if (value >> 1 > 0) {
                // result自增1
                result += 1;
            }
        }
        return result;
    }

    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 计算value对2取对数(向下取整)
            uint256 result = log2(value);
            // 如果为向正无穷方向取整 且 2^result < value,结果result自加1。否则直接返回result
            // 注:这个2^result < value的判断是为了排除"value正好是2的整幂次向上取整自加1"的情况。
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Log2() external {
        // without rounding option
        assertEq(mm.log2(0), 0);
        assertEq(mm.log2(1), 0);
        assertEq(mm.log2(2), 1);
        assertEq(mm.log2(3), 1);
        assertEq(mm.log2(4), 2);
        assertEq(mm.log2(5), 2);
        assertEq(mm.log2(6), 2);
        assertEq(mm.log2(7), 2);
        assertEq(mm.log2(8), 3);
        assertEq(mm.log2(9), 3);
        assertEq(mm.log2(type(uint).max), 255);

        // with rounding down option
        assertEq(mm.log2(0, Math.Rounding.Down), 0);
        assertEq(mm.log2(1, Math.Rounding.Down), 0);
        assertEq(mm.log2(2, Math.Rounding.Down), 1);
        assertEq(mm.log2(3, Math.Rounding.Down), 1);
        assertEq(mm.log2(4, Math.Rounding.Down), 2);
        assertEq(mm.log2(5, Math.Rounding.Down), 2);
        assertEq(mm.log2(6, Math.Rounding.Down), 2);
        assertEq(mm.log2(7, Math.Rounding.Down), 2);
        assertEq(mm.log2(8, Math.Rounding.Down), 3);
        assertEq(mm.log2(9, Math.Rounding.Down), 3);
        assertEq(mm.log2(type(uint).max, Math.Rounding.Down), 255);

        // with rounding up option
        assertEq(mm.log2(0, Math.Rounding.Up), 0);
        assertEq(mm.log2(1, Math.Rounding.Up), 0);
        assertEq(mm.log2(2, Math.Rounding.Up), 1);
        assertEq(mm.log2(3, Math.Rounding.Up), 2);
        assertEq(mm.log2(4, Math.Rounding.Up), 2);
        assertEq(mm.log2(5, Math.Rounding.Up), 3);
        assertEq(mm.log2(6, Math.Rounding.Up), 3);
        assertEq(mm.log2(7, Math.Rounding.Up), 3);
        assertEq(mm.log2(8, Math.Rounding.Up), 3);
        assertEq(mm.log2(9, Math.Rounding.Up), 4);
        assertEq(mm.log2(type(uint).max, Math.Rounding.Up), 256);
    }
}

2.9 log10(uint256) && log10(uint256,Rounding)

  • log10(uint256 value):value对10取对数(向下取整)。如果传入0,返回0;

  • log10(uint256 value, Rounding rounding):value对10取对数(可选择取整方式——向负无穷方向取整、向正无穷方向取整或向0取整)。如果传入0,返回0。

    // 思路:value依次试着除以10^64、10^32、10^16...10^1,每当出现商大于0时,在result中自加当前的幂次。然后value自更新。
    // 为什么是从10^64开始?
    // 10^64约等于2^(3.32*64)=2^212.48<2^256, 10^128约等于2^(3.32*128)=2^424.96>2^256,所以10^64是2^256以内最大的以10为底、2的整幂数为指数的整数
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 如果value>= 10^64 
            if (value >= 10**64) {
                // value=value/(10^64)
                value /= 10**64;
                // result自增64
                result += 64;
            }
            // 如果value>= 10^32
            if (value >= 10**32) {
                // value=value/(10^32)
                value /= 10**32;
                // result自增32
                result += 32;
            }
            // 如果value>= 10^16
            if (value >= 10**16) {
                // value=value/(10^16)
                value /= 10**16;
                // result自增16
                result += 16;
            }
            // 如果value>= 10^8
            if (value >= 10**8) {
                // value=value/(10^8)
                value /= 10**8;
                // result自增8
                result += 8;
            }
            // 如果value>= 10^4
            if (value >= 10**4) {
                // value=value/(10^4)
                value /= 10**4;
                // result自增4
                result += 4;
            }
            // 如果value>= 10^2
            if (value >= 10**2) {
                // value=value/(10^2)
                value /= 10**2;
                // result自增2
                result += 2;
            }
            // 如果value>= 10^1
            if (value >= 10**1) {
                // result自增1
                result += 1;
            }
        }
        return result;
    }

    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 计算value对10取对数(向下取整)
            uint256 result = log10(value);
            // 如果为向正无穷方向取整 且 10 ^ result < value,结果result自加1。否则直接返回result
            // 注: 这个10 ^ result < value的判断是为了排除"value正好是10的整幂次向上取整自加1"的情况。
            return result + (rounding == Rounding.Up && 10**result < value ? 1 : 0);
        }
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Log10() external {
        // without rounding option
        assertEq(mm.log10(0e1), 0);
        assertEq(mm.log10(0e1 + 1), 0);
        assertEq(mm.log10(1e1 - 1), 0);
        assertEq(mm.log10(1e1), 1);
        assertEq(mm.log10(1e1 + 1), 1);
        assertEq(mm.log10(1e2 - 1), 1);
        assertEq(mm.log10(1e2), 2);
        assertEq(mm.log10(1e2 + 1), 2);
        assertEq(mm.log10(1e3 - 1), 2);
        assertEq(mm.log10(1e3), 3);
        assertEq(mm.log10(1e3 + 1), 3);
        assertEq(mm.log10(type(uint).max), 77);

        // with rounding down option
        assertEq(mm.log10(0e1, Math.Rounding.Down), 0);
        assertEq(mm.log10(0e1 + 1, Math.Rounding.Down), 0);
        assertEq(mm.log10(1e1 - 1, Math.Rounding.Down), 0);
        assertEq(mm.log10(1e1, Math.Rounding.Down), 1);
        assertEq(mm.log10(1e1 + 1, Math.Rounding.Down), 1);
        assertEq(mm.log10(1e2 - 1, Math.Rounding.Down), 1);
        assertEq(mm.log10(1e2, Math.Rounding.Down), 2);
        assertEq(mm.log10(1e2 + 1, Math.Rounding.Down), 2);
        assertEq(mm.log10(1e3 - 1, Math.Rounding.Down), 2);
        assertEq(mm.log10(1e3, Math.Rounding.Down), 3);
        assertEq(mm.log10(1e3 + 1, Math.Rounding.Down), 3);
        assertEq(mm.log10(type(uint).max, Math.Rounding.Down), 77);

        // with rounding up option
        assertEq(mm.log10(0e1, Math.Rounding.Up), 0);
        assertEq(mm.log10(0e1 + 1, Math.Rounding.Up), 0);
        assertEq(mm.log10(1e1 - 1, Math.Rounding.Up), 1);
        assertEq(mm.log10(1e1, Math.Rounding.Up), 1);
        assertEq(mm.log10(1e1 + 1, Math.Rounding.Up), 2);
        assertEq(mm.log10(1e2 - 1, Math.Rounding.Up), 2);
        assertEq(mm.log10(1e2, Math.Rounding.Up), 2);
        assertEq(mm.log10(1e2 + 1, Math.Rounding.Up), 3);
        assertEq(mm.log10(1e3 - 1, Math.Rounding.Up), 3);
        assertEq(mm.log10(1e3, Math.Rounding.Up), 3);
        assertEq(mm.log10(1e3 + 1, Math.Rounding.Up), 4);
        assertEq(mm.log10(type(uint).max, Math.Rounding.Up), 78);
    }
}

2.10 log256(uint256) && log256(uint256,Rounding)

  • log256(uint256 value):value对256取对数(向下取整)。如果传入0,返回0;

  • log256(uint256 value, Rounding rounding:value对256取对数(可选择取整方式——向负无穷方向取整、向正无穷方向取整或向0取整)。如果传入0,返回0。

    // 其实该方法的思路跟log2一模一样,只是在result自增的时候缩小8倍。因为256=2^8,x对2的对数一定是x对256对数的8倍
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 如果value/(2^128)>0
            if (value >> 128 > 0) {
                // value=value/(2^128)
                value >>= 128;
                // result自增128/8=16
                result += 16;
            }
            // 如果value/(2^64)>0
            if (value >> 64 > 0) {
                // value=value/(2^64)
                value >>= 64;
                // result自增64/8=8
                result += 8;
            }
            // 如果value/(2^32)>0
            if (value >> 32 > 0) {
                // value=value/(2^32)
                value >>= 32;
                // result自增32/8=4
                result += 4;
            }
            // 如果value/(2^16)>0
            if (value >> 16 > 0) {
                // value=value/(2^16)
                value >>= 16;
                // result自增16/8=2
                result += 2;
            }
            // 如果value/(2^8)>0
            if (value >> 8 > 0) {
                // result自增8/8=1
                result += 1;
            }
        }
        return result;
    }

    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 计算value对256取对数(向下取整)
            uint256 result = log256(value);
            // 如果为向正无穷方向取整 且 256 ^ result < value,结果result自加1。否则直接返回result
            // 注: 这个256 ^ result < value的判断是为了排除"value正好是256的整幂次向上取整自加1"的情况。
            return result + (rounding == Rounding.Up && 1 << (result * 8) < value ? 1 : 0);
        }
    }

foundry代码验证

contract MathTest is Test {
    MockMath mm = new MockMath();

    function test_Log256() external {
        // without rounding option
        assertEq(mm.log256(0), 0);
        assertEq(mm.log256(1), 0);
        assertEq(mm.log256(1 << 8 - 1), 0);
        assertEq(mm.log256(1 << 8), 1);
        assertEq(mm.log256(1 << 8 + 1), 1);
        assertEq(mm.log256(1 << 8 * 2 - 1), 1);
        assertEq(mm.log256(1 << 8 * 2), 2);
        assertEq(mm.log256(1 << 8 * 2 + 1), 2);
        assertEq(mm.log256(1 << 8 * 3 - 1), 2);
        assertEq(mm.log256(1 << 8 * 3), 3);
        assertEq(mm.log256(1 << 8 * 3 + 1), 3);
        assertEq(mm.log256(type(uint).max), 31);

        // with rounding down option
        assertEq(mm.log256(0, Math.Rounding.Down), 0);
        assertEq(mm.log256(1, Math.Rounding.Down), 0);
        assertEq(mm.log256(1 << 8 - 1, Math.Rounding.Down), 0);
        assertEq(mm.log256(1 << 8, Math.Rounding.Down), 1);
        assertEq(mm.log256(1 << 8 + 1, Math.Rounding.Down), 1);
        assertEq(mm.log256(1 << 8 * 2 - 1, Math.Rounding.Down), 1);
        assertEq(mm.log256(1 << 8 * 2, Math.Rounding.Down), 2);
        assertEq(mm.log256(1 << 8 * 2 + 1, Math.Rounding.Down), 2);
        assertEq(mm.log256(1 << 8 * 3 - 1, Math.Rounding.Down), 2);
        assertEq(mm.log256(1 << 8 * 3, Math.Rounding.Down), 3);
        assertEq(mm.log256(1 << 8 * 3 + 1, Math.Rounding.Down), 3);
        assertEq(mm.log256(type(uint).max, Math.Rounding.Down), 31);

        // with rounding up option
        assertEq(mm.log256(0, Math.Rounding.Up), 0);
        assertEq(mm.log256(1, Math.Rounding.Up), 0);
        assertEq(mm.log256(1 << 8 - 1, Math.Rounding.Up), 1);
        assertEq(mm.log256(1 << 8, Math.Rounding.Up), 1);
        assertEq(mm.log256(1 << 8 + 1, Math.Rounding.Up), 2);
        assertEq(mm.log256(1 << 8 * 2 - 1, Math.Rounding.Up), 2);
        assertEq(mm.log256(1 << 8 * 2, Math.Rounding.Up), 2);
        assertEq(mm.log256(1 << 8 * 2 + 1, Math.Rounding.Up), 3);
        assertEq(mm.log256(1 << 8 * 3 - 1, Math.Rounding.Up), 3);
        assertEq(mm.log256(1 << 8 * 3, Math.Rounding.Up), 3);
        assertEq(mm.log256(1 << 8 * 3 + 1, Math.Rounding.Up), 4);
        assertEq(mm.log256(type(uint).max, Math.Rounding.Up), 32);
    }
}

ps:\ 本人热爱图灵,热爱中本聪,热爱V神。 以下是我个人的公众号,如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章,喜欢的小伙伴或者老伙计可以支持一下! 如果需要转发,麻烦注明作者。十分感谢!

1.jpeg

公众号名称:后现代泼痞浪漫主义奠基人

点赞 1
收藏 2
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
Michael.W
Michael.W
0x93E7...0000
狂热的区块链爱好者