# 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](https://cdn.hashnode.com/res/hashnode/image/upload/v1661612862576/PMuv6giKZ.png align="center")

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)](https://seshanth.xyz/huff-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).

![Calldata view with input 2](https://cdn.hashnode.com/res/hashnode/image/upload/v1661665263021/4-Mq7ur9p.png align="left")


`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)

![Result is stored in memory at offset 0x00](https://cdn.hashnode.com/res/hashnode/image/upload/v1661664292880/o3Ebu-zsZ.png)

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`