#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) {
}
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)

if eq(converted, 0x00) {
}
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) {
}

mstore(0x1F, toCheck)
}

mstore(0x1E, toCheck)
}

mstore(0x1D, toCheck)
}

mstore(0x1C, toCheck)
}

mstore(0x1B, toCheck)
}

mstore(0x1A, toCheck)
}

mstore(0x19, toCheck)
}

mstore(0x18, toCheck)
}

mstore(0x17, toCheck)
}

mstore(0x16, toCheck)
}

mstore(0x15, toCheck)
}

mstore(0x14, toCheck)
}

mstore(0x13, toCheck)
}

mstore(0x12, toCheck)
}

mstore(0x11, toCheck)
}

mstore(0x10, toCheck)
}

mstore(0x0F, toCheck)
}

mstore(0x0E, toCheck)
}

mstore(0x0D, toCheck)
}

mstore(0x0C, toCheck)
}

mstore(0x0B, toCheck)
}

mstore(0x0A, toCheck)
}

mstore(0x09, toCheck)
}

mstore(0x08, toCheck)
}

mstore(0x07, toCheck)
}

mstore(0x06, toCheck)
}

mstore(0x05, toCheck)
}

mstore(0x04, toCheck)
}

mstore(0x03, toCheck)
}

mstore(0x02, toCheck)
}

mstore(0x01, toCheck)
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