Skip to content

Instantly share code, notes, and snippets.

@atarpara
Last active August 26, 2022 08:55
Show Gist options
  • Save atarpara/d6d3773d0ce8958b95804fd36981825f to your computer and use it in GitHub Desktop.
Save atarpara/d6d3773d0ce8958b95804fd36981825f to your computer and use it in GitHub Desktop.
LSB Bit Using Solmate Log2
pragma solidity ^0.8.4;
library LibBit {
function lsbsolmate(uint256 x) pure internal returns(uint256 r){
assembly {
// Set Only Right Most Bit all other 0
//x := xor(x,and(x,sub(x,1)))
x:= and(x,add(not(x),1))
// solmate log2 logic
r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
r := or(r, shl(4, lt(0xffff, shr(r, x))))
r := or(r, shl(3, lt(0xff, shr(r, x))))
r := or(r, shl(2, lt(0xf, shr(r, x))))
r := or(r, shl(1, lt(0x3, shr(r, x))))
r := or(r, lt(0x1, shr(r, x)))
}
}
}
@Vectorized
Copy link

pragma solidity ^0.8.4;

library LibBit {
    function lsbsolmate(uint256 x) pure internal returns(uint256 r){
        assembly {
            if iszero(x) {
                // Store the function selector of `LSBUndefined()`.
                mstore(0x00, 0x6d4bda2c)
                // Revert with (offset, size).
                revert(0x1c, 0x04)
            }
            // Isolate the least significant bit.
            x := and(x, add(not(x), 1))

            r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
            r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
            r := or(r, shl(5, lt(0xffffffff, shr(r, x))))

            // prettier-ignore
            r := or(r, byte(and(31, shr(27, mul(shr(r, x), 0x077cb531))), 
                0x00011c021d0e18031e16140f191104081f1b0d17151310071a0c12060b050a09))
        }
   }
}

@atarpara
Copy link
Author

@Vectorized Your trick is good but for the average case solmate log2 is optimize. (+ small bytecode)

image

@Vectorized
Copy link

@atarpara Hmm...

[PASS] testFuzzLSB() (gas: 285358) // Original (with the revert)
[PASS] testFuzzLSB() (gas: 252334) // Original (without the revert)
[PASS] testFuzzLSB() (gas: 217774) // Optimizoor (with the revert)
function testFuzzLSB() public {
    uint256 brutalizer = uint256(keccak256(abi.encode(address(this), block.timestamp)));
    for (uint256 i = 0; i < 256; i++) {
        assertEq(FixedPointMathLib.lsb(1 << i), i);
        assertEq(FixedPointMathLib.lsb(type(uint256).max << i), i);
        assertEq(FixedPointMathLib.lsb((brutalizer | 1) << i), i);
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment