#StackBounty: #solidity #assembly #bytes32 #uint256 Most gas efficient way to check if byte array contains zeroes?

Bounty: 50

I have a contract that I pass data packed into an array of uint256 (as it’s apparently cheaper to use uint256 over bytes32) and each byte in the uint256 contains positions referencing another array of 256 objects, so in the following example, the first 00 is 1 index, then 01 is the next, 02 is the next etc etc:

0x000102030405060708090A0B0C0D0E0F0102030405060708090A0B0C0D0E0F01
  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

In my use case of this, 00 is representing "empty", so in the following example theres 6 empty slots e.g.:

0x0A0102030405060708090000000000000102030405060708090A0B0C0D0E0F01
                      ^ ^ ^ ^ ^ ^ 

What is the most gas efficient way to count how many bytes/slots are 00/"empty"?

At the moment I am iterating through each byte in the array, masking and shifting, which gets the job done:

function check32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
        assembly {
            let converted := and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF) // first is actually last 1 byte in the byte array (uint256 converted to uint8)
            if eq(converted, 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            let len := 0x1F //31 (we already have the first decoded)
            let offset := 0x1F
            
            for { let i := 0 } lt(i, len) { i := add(i, 1) } {
                mstore(offset, toCheck)
                converted := and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF)
                
                if eq(converted, 0x00) {
                    amountOfZeroes := add(amountOfZeroes, 1)
                }
                offset := sub(offset, 0x01)
            }
        }
    }

however as mentioned I have an array of uint256 objects which this check is applying to each entry, and the array is very large, so I want to reduce the work to the bare minimum to save on gas; is there a cheaper way to do this?

EDIT:

I can pretty much halve the gas by eliminating the for loop and adding explicit code to check every position, but it still seems far from ideal:

function checkEfficient32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
        assembly {
            // first is actually last 1 byte in the byte array (uint256 converted to uint8)
            if eq(and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1F, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1E, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1D, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1C, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1B, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1A, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x19, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x18, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x17, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x16, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x15, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x14, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x13, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x12, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x11, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x10, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0F, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0E, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0D, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0C, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0B, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0A, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x09, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x08, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x07, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x06, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x05, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x04, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x03, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x02, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x01, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
        }
    }

EDIT2: I just found out about iszero(...) which i replaced the eq(.., 0x00) with, which shaves the gas down by a few hundred but still involves the same individual checking of bytes


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.