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,

1. The memory offset,
2. 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,

1. The memory offset of the data to return,
2. 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