Huff Challenge #2
Huff is a low-level EVM language to write optimized smart contracts. Huff's official Twitter account has shared a few challenges recently. I'll try to solve and share them here :)
Challenge #2
Challenge #2 is to write an optimized Huff program to find whether a number is Even. It should return 1 if the input is Even and 0 if the input is Odd. You can find the first challenge here (challenge #1).
Solution
I'll start from the solution I have arrived at, Then continue to a more optimized version shared by the EVM wizards.
#define macro MAIN() = takes(0) returns (0) {
0x02 //[0x02]
0x00 calldataload //[input, 0x02]
mod //[0 or 1]
iszero //[1 or 0]
0x00 mstore
0x20 0x00 return
}
In Huff, execution always starts from the MAIN
macro. takes(0) returns(0)
implies that this macro doesn't read any values from the stack and doesn't push any value to the stack upon completion.
The logic we are going to use is that When an Even number is divided by 2 the remainder will be 0.
We start by pushing the inputs to the stack.
0x02
0x00 calldataload
0x02
pushes 2 to the stack.
calldataload
opcode loads the transaction inputs to the stack. The opcode takes one argument, the offset to start load from (0x00)
.
Calldata is the place where the function arguments are stored. Usually, the function selector takes the first 4 bytes of calldata, followed by the inputs. But in this case, the input starts from offset 0 (As per the challenge's description).
0x00 calldataload
- pushes 0 to the stack first, followed by calldataload
. On execution, The calldataload opcode consumes 1 input (0x00) from the stack and pushes the output(our input number). The stack will now look like [INPUT, 0x02].
We have the inputs in place in the stack. Now we need to find the remainder of the division.
MOD
opcode returns the value we need.
mod
iszero
mod
takes two inputs from the stack and returns the remainder.
The result of MOD
will be either 0 or some number. Our goal is to return 0 for Odd numbers and 1(true) for Even numbers.
iszero
opcode returns takes the value at the top of the stack and returns 1 if the value at top of the stack is 0. So if the number is even, mod
will return 0 and iszero
turns it to 1 and vice-versa.
stack view: [0 or 1].
We now have the required value at the required position in the stack. To return the value, we need to use the RETURN
opcode. The RETURN opcode takes inputs from the memory, so we need to save our result to the memory.
To store a value in memory, MSTORE
opcode is used.
//[0 or 1]
0x00 mstore
0x20 0x00 return
MSTORE takes two inputs,
- The memory offset,
- The data to store
In the above snippet, We are storing the result at memory offset 0x00. EVM operates on 32 bytes, so the result will occupy the first 32 bytes from 0x00 (0x00 to 0x1f)
Finally, RETURN
opcode is pushed, which returns the result.
RETURN
opcode expects 2 inputs,
- The memory offset of the data to return,
- The size of the data in memory.
0x00
is the memory offset and 0x20
(32 bytes) is the size of the data(our result).
Optimization
The snippet in the previous section does the Job, But there is still room to save gas.
When a number is pushed to a stack (0x00
), Huff replaces it with the PUSH
opcode (PUSH 0x00). Push opcode costs 3 gas.
The EVM wizards in Huff Discord found another way to push 0 to the stack while saving 1 gas.
RETURNDATASIZE
opcode pushes the length of the data returned in the last CALL, DELEGATECALL, CALLCODE or STATICCALL. At this point we have not made any external calls to other contracts, so using RETURNDATASIZE
will push 0 to the stack.
The final code is,
#define macro MAIN() = takes(0) returns (0) {
0x02 //[0x02]
returndatasize calldataload //[input, 0x02]
mod //[0 or 1]
iszero
returndatasize mstore
0x20 returndatasize return
}
Thus by replacing 0x00
with RETURNDATASIZE
in three places we are able to save 3 gas, which is equivalent to one PUSH