Understanding solidity inline assembly code

Question

Here is a code from solidity documentation:

 function sumAsm(uint[] _data) public returns (uint o_sum) {
        for (uint i = 0; i < _data.length; ++i) {
            assembly {
                o_sum := add(o_sum, mload(add(add(_data, 0x20), mul(i, 0x20))))
            }
        }
    }

Can any one explain this code. _data is an array of uint. How are can we add 0x20 to an array. If the array name represents the address of first element why are we offsetting it? How does this line (add(add(_data, 0x20), mul(i, 0x20))) give the address of the first and the subsequent elements of the array.

Answer 1

Within the assembly code, _data is the memory address of the start of the array data.

However, the first memory word (32 bytes = 0x20 bytes) is reserved for the length of the array, so we need to step over this. Thus, _data[0] is at memory address _data + 0x20. In the code, this looks like add(_data, 0x20).

The array elements follow consecutively, numbered from 0, each occupying one 32 byte (0x20 byte) word. Thus, element [N] is offset N * 0x20 from the start of the array data that we found above. In the code this offset is mul(i, 0x20).

Putting it all together, _data[i] is found at (_data + 0x20) + (i * 0x20), which is the expression (add(add(_data, 0x20), mul(i, 0x20))).

The net effect of the loop is to add up all the array elements into o_sum. It is likely done in assembly to avoid the overhead of array bounds checking that Solidity always inserts.

Answer 2

@benjaminion's answer is fantastic, but I made his assembly code easier to understand:

assembly {
    let ithpos := mul(add(i, 0x01), 0x20)
    let ithnumber := mload(add(_data, ithpos))
    o_sum := add(o_sum, ithnumber)
}

What I did:

1. Instead of adding 0x20 to the memory location of _data, I simply increment i by add(i, 0x01). This is funnelled into the multiplier function mul which gets the right word index (recall that assembly only works with 32 bytes variables)
2. Load from memory the number at the ith position
3. Finally, add the ithnumber to o_sum by doing a simple addition

Also, if you started to use solidity ^0.5.0, note that your _data parameter has to be defined like this now:

function sumAsm(uint[] memory _data) public returns (uint o_sum) {
    ...
}

There's an extra memory keyword between the type and the name.

Answer 3

for pauls answer:

o_sum := add(o_sum, mload(add(_data, mul(add(i, 0x01), 0x20)))) is actually cheaper to use since it doesn't allocate memory for 2 varaibles and store a value for both. it also doesn't have to use a mload for each of those variables