assembly

SolidityにおけるInline AssemblyのMemory Spaceについて

Inline AssemblyとMemory Spaceについて、stringのconcatをベースに、AssemblyコードとMemory Spaceに関するコメントを書いてみました。

https://github.com/eggdragons/how-to-use-foundry

今回は、先ほどのリポジトリの中のsrc/utils/ConcatConvertAssembly.solが対象になります。

test/utils/ConcatConvertAssembly.t.solが上記のテストになっています。

通常のstringのconcat

普段よく使う標準のstringのconcatです。str1が"hello"、str2が"world"だとすると、"helloworld"が帰ってきます。

    function concatBasic(string memory str1, string memory str2) public pure returns (string memory) {
        return string.concat(str1, str2);
    }

自前のstringのconcat

Inline Assemblyにコンバートするために、まずはstringのconcatを自前で書いていきます。

    function concatStep(string memory str1, string memory str2) public pure returns (string memory) {
        bytes memory str1Bytes = bytes(str1);
        bytes memory str2Bytes = bytes(str2);

        uint256 str1Len = bytes(str1).length;
        uint256 str2Len = bytes(str2).length;

        string memory result = new string(str1Len + str2Len);
        bytes memory resultBytes = bytes(result);

        uint256 j;
        for (uint256 i = 0; i < str1Len;) {
            unchecked {
                resultBytes[j++] = str1Bytes[i];
                i++;
            }
        }
        for (uint256 i = 0; i < str2Len;) {
            unchecked {
                resultBytes[j++] = str2Bytes[i];
                i++;
            }
        }
        return string(resultBytes);
    }

それぞれのstringをbytesに変換します。

resultBytesに、それぞれのstringを前から順番に格納していき、最後にstringに変換して戻しています。

stringのconcatをInline Assembly化してみる

まずは、メモリースペースについて

            // memory space
            // | 0x00 - 0x3f | scratch space
            // | 0x40 - 0x5f | free memory pointer (init = 0x80)
            // | 0x60 - 0x7f | zero slot
            // | 0x80 - 0x9f | dynamic memory arrays

メモリー構造について非常に説明しづらいのですが、例えば長さ80の文字があったとすると、下記の様な配置になります。

           // str1
            // | 0x00 - 0x1f | length
            // | 0x20 - 0x3f | byte32
            // | 0x40 - 0x5f | byte32
            // | 0x60 - 0x6f | byte16

動的配列の場合、長さが最初のSlotに入り、その後内容が格納されていくことになります。

そのため、長さ80の文字(Str1)と長さ72の文字(Str2)を結合する場合、最終的には下記の様な配置になります。

            // memory space
            // | 0x00  - 0x3f  | scratch space
            // | 0x40  - 0x5f  | free memory pointer (init = 0x80)
            // | 0x60  - 0x7f  | zero slot
            // | 0x80  - 0x9f  | str1.length + str2.length = result
            // | 0xA0  - 0xBF  | str1 0x20 - 0x3f
            // | 0xC0  - 0xDF  | str1 0x40 - 0x5f
            // | 0xE0  - 0xEF  | str1 0x60 - 0x6f
            // | 0xF0  - 0xFF  | str2 0x20 - 0x2f
            // | 0x100 - 0x120 | str2 0x30 - 0x4f
            // | 0x100 - 0x117 | str2 0x50 - 0x67

これを最初に意識すれば、簡単にInline Assemblyがかけると思います。

1slot 32bytesを意識する必要があるため、最後におまじないをすれば完成です

            // abracadabra
            // to 32bytes
            mstore(0x40, and(add(last, 31), not(31)))

テストにおいては、念の為、32bytesを意識してFuzzテストを行なっています。

function testConcatAssmeblyFuzz32bytes(string memory _str1, string memory _str2) public {
        uint256 totalLength = bytes(_str1).length + bytes(_str2).length;

        vm.assume(totalLength % 32 == 0);
        // console.logUint(totalLength);

        string memory data = testContract.concatAssembly(_str1, _str2);
        string memory result = string.concat(_str1, _str2);

        assertEq(result, data);
    }

    function testConcatAssmeblyFuzzNot32bytes(string memory _str1, string memory _str2) public {
        uint256 totalLength = bytes(_str1).length + bytes(_str2).length;

        vm.assume(totalLength % 32 != 0);
        // console.logUint(totalLength);

        string memory data = testContract.concatAssembly(_str1, _str2);
        string memory result = string.concat(_str1, _str2);

        assertEq(result, data);
    }

最後に全体のコード載せておきます。

function concatAssembly(string memory str1, string memory str2) public pure returns (string memory result) {
        assembly {
            // memory space
            // | 0x00 - 0x3f | scratch space
            // | 0x40 - 0x5f | free memory pointer (init = 0x80)
            // | 0x60 - 0x7f | zero slot
            // | 0x80 - 0x9f | dynamic memory arrays

            // free memory pointer
            // result = mload(0x40) => 0x80
            result := mload(0x40)

            // str1 ex.length = 80
            // | 0x00 - 0x1f | length
            // | 0x20 - 0x3f | byte32
            // | 0x40 - 0x5f | byte32
            // | 0x60 - 0x6f | byte16
            let length := mload(str1)

            // write memory space
            mstore(result, length)

            // memory space
            // | 0x00 - 0x3f | scratch space
            // | 0x40 - 0x5f | free memory pointer (init = 0x80)
            // | 0x60 - 0x7f | zero slot
            // | 0x80 - 0x9f | str1.length result
            // | 0xA0          ← memory counter start point

            // set memory counter & last point
            let mc := add(result, 0x20)
            let last := add(mc, length)

            // for { initialize } lt ( judge ) { loop preprocessing } { loop content }

            // initialize
            // str1
            // | 0x00 - 0x1f | length
            // | 0x20 - 0x3f | byte32 ← start(step by step 0x20)
            // | 0x40 - 0x5f | byte32
            // | 0x60 - 0x6f | byte16

            // judge
            // mc < last

            // loop preprocessing
            // mc : step by step 0x20
            // cc : step by step 0x20

            // loop content
            // | loop | mc   | memory space | str1        | cc   |
            // | 1    | 0xA0 | 0xA0 - 0xBF  | 0x20 - 0x3f | 0x20 |
            // | 2    | 0xC0 | 0xC0 - 0xDF  | 0x40 - 0x5f | 0x40 |
            // | 3    | 0xE0 | 0xE0 - 0xEF  | 0x60 - 0x6f | 0x60 |

            for { let cc := add(str1, 0x20) } lt(mc, last) {
                mc := add(mc, 0x20)
                cc := add(cc, 0x20)
            } { mstore(mc, mload(cc)) }

            // memory space
            // | 0x00 - 0x3f | scratch space
            // | 0x40 - 0x5f | free memory pointer (init = 0x80)
            // | 0x60 - 0x7f | zero slot
            // | 0x80 - 0x9f | str1.length = result
            // | 0xA0 - 0xBF | str1 0x20 - 0x3f
            // | 0xC0 - 0xDF | str1 0x40 - 0x5f
            // | 0xE0 - 0xEF | str1 0x60 - 0x6f
            // | 0xF0          ← memory counter start point

            // str2 ex.length = 72
            // | 0x00 - 0x1f | length
            // | 0x20 - 0x3f | byte32
            // | 0x40 - 0x5f | byte32
            // | 0x60 - 0x6f | byte8
            length := mload(str2)

            // write memory space
            mstore(result, add(length, mload(result)))

            // set memory counter & last point
            mc := last
            last := add(mc, length)

            for { let cc := add(str2, 0x20) } lt(mc, last) {
                mc := add(mc, 0x20)
                cc := add(cc, 0x20)
            } { mstore(mc, mload(cc)) }

            // memory space
            // | 0x00  - 0x3f  | scratch space
            // | 0x40  - 0x5f  | free memory pointer (init = 0x80)
            // | 0x60  - 0x7f  | zero slot
            // | 0x80  - 0x9f  | str1.length + str2.length = result
            // | 0xA0  - 0xBF  | str1 0x20 - 0x3f
            // | 0xC0  - 0xDF  | str1 0x40 - 0x5f
            // | 0xE0  - 0xEF  | str1 0x60 - 0x6f
            // | 0xF0  - 0xFF  | str2 0x20 - 0x2f
            // | 0x100 - 0x120 | str2 0x30 - 0x4f
            // | 0x100 - 0x117 | str2 0x50 - 0x67

            // abracadabra
            // to 32bytes
            mstore(0x40, and(add(last, 31), not(31)))
        }
        return result;
    }

今回は、Inline Assemblyのmemory spaceについて、まとめてみました。

-assembly