检查字节数组值是否在 range/below 阈值内的最有效方法？

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。

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

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

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

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

对于编码 10 个 24 位数字的 256 位 uint256 值——如问题中所述——可以对所有 10 个数字进行前两个检查（肯定通过或肯定失败）中的每一个具有 256 位掩码和相应的按位 and.

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

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

否则，如果 uint256 值和后面的掩码之间的按位 and 非零，则数字无法通过检查，因为至少有一个数字在其 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;
}

检查字节数组值是否在 range/below 阈值内的最有效方法？

Most efficient way to check byte array values are within a range/below threshold?

arrays

validation

solidity

检查 24 位数字

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

总结

伪代码