// SPDX-License-Identifier: MIT pragma solidity ^0.8.4; /// @notice Library for bit twiddling and boolean operations. /// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibBit.sol) /// @author Inspired by (https://graphics.stanford.edu/~seander/bithacks.html) library LibBit { /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/ /* BIT TWIDDLING OPERATIONS */ /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/ /// @dev Find last set. /// Returns the index of the most significant bit of `x`, /// counting from the least significant bit position. /// If `x` is zero, returns 256. function fls(uint256 x) internal pure returns (uint256 r) { /// @solidity memory-safe-assembly assembly { r := or(shl(8, iszero(x)), 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)))) // forgefmt: disable-next-item r := or(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)), 0x0706060506020504060203020504030106050205030304010505030400000000)) } } /// @dev Count leading zeros. /// Returns the number of zeros preceding the most significant one bit. /// If `x` is zero, returns 256. function clz(uint256 x) internal pure returns (uint256 r) { /// @solidity memory-safe-assembly assembly { 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)))) // forgefmt: disable-next-item r := add(xor(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)), 0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff)), iszero(x)) } } /// @dev Find first set. /// Returns the index of the least significant bit of `x`, /// counting from the least significant bit position. /// If `x` is zero, returns 256. /// Equivalent to `ctz` (count trailing zeros), which gives /// the number of zeros following the least significant one bit. function ffs(uint256 x) internal pure returns (uint256 r) { /// @solidity memory-safe-assembly assembly { // Isolate the least significant bit. let b := and(x, add(not(x), 1)) r := or(shl(8, iszero(x)), shl(7, lt(0xffffffffffffffffffffffffffffffff, b))) r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, b)))) r := or(r, shl(5, lt(0xffffffff, shr(r, b)))) // For the remaining 32 bits, use a De Bruijn lookup. // forgefmt: disable-next-item r := or(r, byte(and(div(0xd76453e0, shr(r, b)), 0x1f), 0x001f0d1e100c1d070f090b19131c1706010e11080a1a141802121b1503160405)) } } /// @dev Returns the number of set bits in `x`. function popCount(uint256 x) internal pure returns (uint256 c) { /// @solidity memory-safe-assembly assembly { let max := not(0) let isMax := eq(x, max) x := sub(x, and(shr(1, x), div(max, 3))) x := add(and(x, div(max, 5)), and(shr(2, x), div(max, 5))) x := and(add(x, shr(4, x)), div(max, 17)) c := or(shl(8, isMax), shr(248, mul(x, div(max, 255)))) } } /// @dev Returns whether `x` is a power of 2. function isPo2(uint256 x) internal pure returns (bool result) { /// @solidity memory-safe-assembly assembly { // Equivalent to `x && !(x & (x - 1))`. result := iszero(add(and(x, sub(x, 1)), iszero(x))) } } /// @dev Returns `x` reversed at the bit level. function reverseBits(uint256 x) internal pure returns (uint256 r) { uint256 m0 = 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f; uint256 m1 = m0 ^ (m0 << 2); uint256 m2 = m1 ^ (m1 << 1); r = reverseBytes(x); r = (m2 & (r >> 1)) | ((m2 & r) << 1); r = (m1 & (r >> 2)) | ((m1 & r) << 2); r = (m0 & (r >> 4)) | ((m0 & r) << 4); } /// @dev Returns `x` reversed at the byte level. function reverseBytes(uint256 x) internal pure returns (uint256 r) { unchecked { // Computing masks on-the-fly reduces bytecode size by about 200 bytes. uint256 m0 = 0x100000000000000000000000000000001 * (~toUint(x == 0) >> 192); uint256 m1 = m0 ^ (m0 << 32); uint256 m2 = m1 ^ (m1 << 16); uint256 m3 = m2 ^ (m2 << 8); r = (m3 & (x >> 8)) | ((m3 & x) << 8); r = (m2 & (r >> 16)) | ((m2 & r) << 16); r = (m1 & (r >> 32)) | ((m1 & r) << 32); r = (m0 & (r >> 64)) | ((m0 & r) << 64); r = (r >> 128) | (r << 128); } } /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/ /* BOOLEAN OPERATIONS */ /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/ // A Solidity bool on the stack or memory is represented as a 256-bit word. // Non-zero values are true, zero is false. // A clean bool is either 0 (false) or 1 (true) under the hood. // Usually, if not always, the bool result of a regular Solidity expression, // or the argument of a public/external function will be a clean bool. // You can usually use the raw variants for more performance. // If uncertain, test (best with exact compiler settings). // Or use the non-raw variants (compiler can sometimes optimize out the double `iszero`s). /// @dev Returns `x & y`. Inputs must be clean. function rawAnd(bool x, bool y) internal pure returns (bool z) { /// @solidity memory-safe-assembly assembly { z := and(x, y) } } /// @dev Returns `x & y`. function and(bool x, bool y) internal pure returns (bool z) { /// @solidity memory-safe-assembly assembly { z := and(iszero(iszero(x)), iszero(iszero(y))) } } /// @dev Returns `x | y`. Inputs must be clean. function rawOr(bool x, bool y) internal pure returns (bool z) { /// @solidity memory-safe-assembly assembly { z := or(x, y) } } /// @dev Returns `x | y`. function or(bool x, bool y) internal pure returns (bool z) { /// @solidity memory-safe-assembly assembly { z := or(iszero(iszero(x)), iszero(iszero(y))) } } /// @dev Returns 1 if `b` is true, else 0. Input must be clean. function rawToUint(bool b) internal pure returns (uint256 z) { /// @solidity memory-safe-assembly assembly { z := b } } /// @dev Returns 1 if `b` is true, else 0. function toUint(bool b) internal pure returns (uint256 z) { /// @solidity memory-safe-assembly assembly { z := iszero(iszero(b)) } } }