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

user_755370 0
Viewed 443

I have a uint256 that I'm using as a byte array consisting of 10 numbers, 3 bytes each (which takes up 30 bytes, the first 2 bytes of the 32 bytes are ignored):

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

I need to validate that these numbers are within a certain range. They are uint24 so they are always positive, and the lowest index is 0 so I only really need to check if they are below a certain upper threshold.

At present I am reading the relevant bytes into uint24 objects and checking that the number is below the threshold:

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"
        ); 
    }

however I was wondering if there was a better way to check it involving less computation? This check happens in a loop with an array of uint256 so I'm attempting to achieve maximum efficiency to reduce gas cost.

solidity validation arrays
1 Answers

The 24-bit unsigned binary representation of 129,600 is 000000011111101001000000, which has all 0s in its 7 leftmost bits.

Checking a 24-bit Number

If a 24-bit unsigned number has all 0s in its 8 leftmost bits, then it is less than or equal to 65,535, and consequently less than 129,600.

If a 24-bit unsigned number has a 1 in its 7 leftmost bits, then it is greater than or equal to 131,072, and consequently greater than 129,600.

This can be used to check if a 24-bit unsigned number definitely passes or definitely fails to be less than 129,600.

If a bitwise and between the number and 0xFF0000 is zero, then the number passes the check (less than 129,600).

Otherwise, if a bitwise and between the number and 0xFE0000 is non-zero, then the number fails the check (greater than 129,600).

Otherwise, the number can be compared directly with 129,600.

Extending the Check to Ten 24-bit Numbers

For the 256-bit uint256 value that encodes 10 24-bit numbers—as described in the question—each of the first two checks (definitely pass or definitely fail) can be conducted for all 10 numbers with a 256-bit mask and corresponding bitwise and.

If a bitwise and between the uint256 value and the following mask is zero, then the 10 numbers pass the check, since none of the numbers have 1s in their 8 leftmost bits (all numbers are less than or equal to 65,535, and consequntly less than 129,600).

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

Otherwise, if a bitwise and between the uint256 value and the following mask is non-zero, then the numbers fail the check, since at least one number has a 1 in its 7 leftmost bits (at least one number is greater than or equal to 131,072, and consequently greater than 129,600).

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

Otherwise, the 10 numbers can be compared directly with 129,600 using the approach proposed in the question.

Summary

This approach allows a way to quickly check if all 10 numbers definitely pass or at least one number definitely fails. In the case where there is no definite pass or definite fail, then a more computationally demanding procedure can be used to check each of the 10 numbers individually (with short-circuiting on failure).

Pseudocode

(& is used to represent bitwise 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;
}
user_15094330
Related