arrays - 检查字节数组值是否在范围内/低于阈值的最有效方法？

Question

我有一个 uint256，我将其用作由 10 个数字组成的字节数组，每个数字 3 个字节(占用 30 个字节，32 个字节的前 2 个字节被忽略):

0x0000aaaaaabbbbbbccccccddddddeeeeeeffffff111111222222333333444444
  xxxx^     ^     ^     ^     ^     ^     ^     ^     ^     ^

我需要验证这些数字是否在特定范围内。它们是 uint24，因此它们始终为正，最低索引为 0，因此我只需要检查它们是否低于某个上限阈值。

目前我正在将相关字节读入 uint24 对象并检查该数字是否低于阈值:

uint256 constant NUM_OF_GROUPS = 129600; // all numbers have to be between 0 and 129599

....... 

function decodeAndCheckGroupIndexes(uint256 x)
        public
        pure
        returns (
            uint24 a,
            uint24 b,
            uint24 c,
            uint24 d,
            uint24 e,
            uint24 f,
            uint24 g,
            uint24 h,
            uint24 i,
            uint24 j
        )
    {
        assembly {
            j := x
            mstore(0x1B, x)
            a := mload(0)
            mstore(0x18, x)
            b := mload(0)
            mstore(0x15, x)
            c := mload(0)
            mstore(0x12, x)
            d := mload(0)
            mstore(0x0F, x)
            e := mload(0)
            mstore(0x0C, x)
            f := mload(0)
            mstore(0x09, x)
            g := mload(0)
            mstore(0x06, x)
            h := mload(0)
            mstore(0x03, x)
            i := mload(0)
        }
        require(
            a < NUM_OF_GROUPS &&
                b < NUM_OF_GROUPS &&
                c < NUM_OF_GROUPS &&
                d < NUM_OF_GROUPS &&
                e < NUM_OF_GROUPS &&
                f < NUM_OF_GROUPS &&
                g < NUM_OF_GROUPS &&
                h < NUM_OF_GROUPS &&
                i < NUM_OF_GROUPS &&
                j < NUM_OF_GROUPS,
            "group is out of range"
        ); 
    }

但是我想知道是否有更好的方法来检查它并减少计算量？此检查在包含 uint256 数组的循环中进行，因此我试图实现最大效率以降低 gas 成本。

Answer 1

129,600 的 24 位无符号二进制表示为 000000011111101001000000 ，其最左边的 7 位全为 0。

检查 24 位数字

如果一个 24 位无符号数的最左边 8 位全为 0，则它小于或等于 65,535，因此小于 129,600。

如果一个 24 位无符号数的最左边 7 位为 1，则它大于或等于 131,072，因此大于 129,600。

这可用于检查 24 位无符号数是否肯定通过或肯定不小于 129,600。

如果数字和 and 之间的按位 0xFF0000 为零，则该数字通过检查(小于 129,600 )。

否则，如果数字和 and 之间的按位 0xFE0000 非零，则该数字未通过检查(大于 129,600)。

否则可以直接和129,600比较。

将检查扩展到十个 24 位数字

对于编码 10 个 24 位数字的 256 位 uint256 值(如问题中所述)，可以使用 256 位掩码对所有 10 个数字进行前两次检查(肯定通过或肯定失败)和相应的按位 and 。

如果 and 值和以下掩码之间的按位 uint256 为零，则这 10 个数字通过检查，因为没有一个数字在其最左边的 8 位中有 1(所有数字都小于或等于 65,535 ，并且因此小于 129,600 )。

0x0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000
  xxxx^     ^     ^     ^     ^     ^     ^     ^     ^     ^

否则，如果 and 值和以下掩码之间的按位 uint256 非零，则数字无法通过检查，因为至少有一个数字在其最左边的 7 位中为 1(至少有一个数字大于或等于 131,072 ，因此大于 129,600 )。

0x0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000
  xxxx^     ^     ^     ^     ^     ^     ^     ^     ^     ^

否则，可以使用问题中提出的方法将 10 个数字直接与 129,600 进行比较。

总结

这种方法提供了一种快速检查是否所有 10 个数字都肯定通过或至少一个数字肯定不通过的方法。在没有明确通过或明确失败的情况下，可以使用计算要求更高的程序来单独检查 10 个数字中的每一个(失败时短路)。

伪代码

(&用来表示按位and)

uint256 valid_mask = 0x0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000FF0000;
uint256 invalid_mask = 0x0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000;

// returns true if all ten numbers encoded in `input` are
// less than 129,600
bool less_than_129600(uint256 input) {
    // check if all ten numbers are definitely valid
    if (valid_mask & input == 0)
        return true;
    
    // check if at least one number is definitely invalid
    if (invalid_mask & input != 0)
        return false;

    // check each number and return false if an invalid number
    // is encountered
    ...

    // if we haven't returned after the last check, all numbers
    // are valid
    return true;
}