[EIP145] SHL・SHR・SARオペコードについて理解しよう！

# はじめに

初めまして。
**CryptoGames**というブロックチェーンゲーム企業でエンジニアをしている **cardene（かるでね）** です！
スマートコントラクトを書いたり、フロントエンド・バックエンド・インフラと幅広く触れています。

https://cryptogames.co.jp/

代表的なゲームは**クリプトスペルズ**というブロックチェーンゲームです。

https://cryptospells.jp/

今回は、の仕組みを提案している**EIP145**についてまとめていきます！

:::note info
以下にまとめられているものを翻訳・要約・補足しながらまとめていきます。
:::

https://eips.ethereum.org/EIPS/eip-145

他にも様々なEIPについてまとめています。

https://cardene.notion.site/ERC-EIP-2a03fa3ea33d43baa9ed82288f98d4a9?pvs=4

# 概要

ネイティブのビットワイズシフト命令が導入されました。
これはホストでの処理効率が高く、コントラクトによって使用する時のコストも安くなります。

- **ネイティブのビットワイズシフト命令が導入された**
    - コンピュータのプロセッサが、ビット操作を行う特別な命令を持っていることを意味します。
    - ビットワイズシフトとは、データのビットを左または右に移動させる操作のことです。
    - この操作は、データの加工や数値の計算などに使用されます。
- **ホストでの処理効率が向上**
    - このビットワイズシフト命令を使うことで、コンピュータがデータを処理する速度が速くなることを意味しています。
    - ネイティブの命令は、プロセッサが直接理解できるため、実行速度が向上します。

- **コントラクトによって使用する時のコストも安くなる**
    - この命令を使用する時にかかるコスト（例えば、クラウドサービスや他のプログラミング環境での使用料など）が低くなることを示しています。
    - 効率的な命令は、リソースを節約するため、コスト削減にもつながります。

# 動機

EVM（イーサリアム仮想マシン）がビットワイズシフト演算子をサポートしていないというのは、EVMがビットレベルでのデータの移動を直接行う特殊な命令を持っていないことを意味します。
一方、他の種類の論理演算子や算術演算子はサポートされています。

シフト操作は、算術演算子を使って間接的に実装することが可能です。
しかし、この方法では、より多くの計算ステップが必要となり、それに伴い、処理にかかる時間とコストが増加します。
具体的には、左シフト（`SHL`）と右シフト（`SHR`）を算術演算で実装すると、それぞれ`35`ガス（EVMでの計算処理にかかるコストの単位）が必要になります。

対照的に、提案されている新しいビットワイズシフト命令を使用する場合、これらの操作にはわずか`3`ガスしか必要ありません。
これにより、EVM上での処理がはるかに効率的になり、コスト削減にも寄与することが期待されます。
これは、イーサリアムネットワーク上でスマートコントラクトを実行する時のガス消費量を大幅に削減することを意味しており、開発者やユーザーにとっての負担軽減に繋がります。

# 仕様

## `SHL`: `0x1b`

`SHL` 命令は、イーサリアムの仮想マシン（EVM）上でビットを左にシフトするために使用される命令です。
この命令は、スタックから2つの値を取り出し、1つ目の値（`arg1`）をシフト量として、2つ目の値（`arg2`）をシフト対象として使用します。
具体的には、`arg2`のビットを`arg1`の数だけ左に移動します。

```math
(arg2 * 2^{arg1}) mod 2^{256}
```

この命令の計算結果は、`arg2`の値を`2`の`arg1`乗倍したものです。
しかし、結果は`2`の`256`乗で割った余りとして計算されるため、結果は常に`256`ビット以内の範囲に収まります。
この特性は、イーサリアムの`256`ビットの固定サイズのデータ型に適合しています。

また、`arg1`（シフト量）が`256`以上の場合、結果は自動的に`0`に設定されます。
これは、`256`ビット以上シフトすると、どのビットも残らないためです。

この命令の挙動は、数学的には `PUSH1 2 EXP MUL` と等価です。
つまり、`2`を`arg1`乗して`arg2`に掛けることで、左シフト操作が実現されるということです。
この命令は、EVM上でのビット操作を効率的かつ正確に行うために重要であり、スマートコントラクトの実装において広く利用されます。

## `SHR`: `0x1c`

`SHR` 命令は、イーサリアムの仮想マシン（EVM）においてビットを右にシフトするために使用される命令です。
この命令は、スタックから2つの値を取り出し、1つ目の値（`arg1`）をシフト量として、2つ目の値（`arg2`）をシフト対象として使用します。
具体的には、`arg2`のビットを`arg1`の数だけ右に移動させ、左側の空いた部分を`0`で埋めます。

この命令の計算結果は、`arg2`を`2`の`arg1`乗で割った値です。
これにより、結果は常に整数値となり、`256`ビットの固定サイズのデータ型に適合します。
また、`arg1`（シフト量）が`256`以上の場合、結果は自動的に`0`になります。
これは、`256`ビット以上シフトすると、全てのビットが`0`に置き換えられるためです。

この命令の挙動は数学的には `PUSH1 2 EXP DIV` と等価です。
つまり、`2を`arg1`乗してから`arg2`を割ることで、論理右シフト操作が実現されます。
`SHR` 命令は、EVM上でのビット操作を効率的に行い、スマートコントラクトの実装において重要な役割を果たします。
このようなビット操作は、データの圧縮やビットレベルでの計算など、さまざまな用途に利用されます。

## `SAR`: `0x1d`

`SAR` 命令は、イーサリアムの仮想マシン（EVM）においてビットを右にシフトする命令ですが、`SHR`（論理右シフト）と異なり、符号を保持する点が特徴です。
この命令は、スタックから2つの値を取り出し、1つ目の値（`arg1`）をシフト量として、2つ目の値（`arg2`）をシフト対象として使用します。
`SAR` では、`arg2`の符号を維持しながら、`arg1`の数だけビットを右にシフトします。

この命令の計算結果は、`arg2`を`2`の`arg1`乗で割った値ですが、`arg2`が符号付き数として扱われるため、負の数の場合の挙動が特に重要です。
例えば、`arg2`が負の数で、`arg1`が`1`の場合、最上位ビット（符号ビット）が保持されるため、結果は`-1`になります。

また、`arg1`（シフト量）が`256`以上の場合、`arg2`の符号に応じて結果が`0`または`-1`になります。
これは、`256`ビット以上シフトすると、全てのビットがシフトされるため、非負の数では`0`に、負の数では符号ビットが保持されるため`-1`になるためです。

`SAR` 命令は、`PUSH1 2 EXP SDIV` とは異なる丸め方法を採用しており、算術的なコンテキストでの正確なビットシフトを可能にします。
この命令は、EVM上でのビット操作を効率的かつ正確に行い、特に符号付き数値の扱いにおいて重要な役割を果たします。
また、シフト命令のガスコストが非常に低い（`3`ガス）ことも、スマートコントラクトの効率的な実装に貢献しています。

:::note info
シフト系のオペコードについては以下の記事を参考にしてください。
:::

https://zenn.dev/heku/books/aef33b86ded3c0/viewer/acbba2

# 補足

ビットシフト命令におけるオペランド（命令で操作するデータ）の順序に関する説明です。
通常の算術命令では、第一オペランドと第二オペランドの順序は特定の規則に基づいていますが、ビットシフト命令ではこの順序が逆転しています。

例えば、一般的な加算命令では、最初にスタックからポップされる値が第二オペランドとして、次にポップされる値が第一オペランドとして扱われます。
しかし、ビットシフト命令の場合、最初にポップされる値がシフト量（第一オペランド）として、次にポップされる値がシフトされる値（第二オペランド）として扱われます。

この設計は、スタック上の既存の値をより自然かつ効率的にシフトするためのものです。
つまり、スタック上で操作される値の流れをより直感的にすることで、プログラマーがビットシフト命令を使いやすくし、プログラムの可読性を高める目的があります。
このような設計の選択は、プログラミングの慣習や実際の使用シナリオに基づいており、より効率的で理解しやすいコードの記述を促進します。

# テストケース

## `SHL`

<details><summary>テスト</summary><div>

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000002
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0xff
SHL
---
0x8000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x0100
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x0101
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SHL
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHL
---
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SHL
---
0x8000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHL
---
0x0000000000000000000000000000000000000000000000000000000000000000

```

```
PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHL
---
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
```

</div></details>


これらのテストケースは、`SHL`（左シフト）命令の動作を理解するための具体例です。
`SHL`命令は、与えられた数値（第二オペランド）を、特定のビット数（第一オペランド）だけ左にシフトします。
シフトすると、数値は2のシフト量乗倍され、空いたビット位置は`0`で埋められます。

- シフト量が`0`の場合、数値は変わりません。
    - 例えば、`1`を`0`ビット左シフトすると、結果は`1`のままです。
- シフト量が`1`の場合、数値は`2`倍になります。
    - `1`を`1`ビット左シフトすると、結果は`2`になります。
- シフト量が`255`の場合、数値は非常に大きくなり、最上位ビットだけが`1`になります。
    - これは、`2`の`255`乗の値に相当します。
- シフト量が`256`以上の場合、結果は常に`0`になります。
    - `256`ビット以上シフトすると、全てのビットが`0`に置き換えられます。
- 全てのビットが`1`の数値をシフトすると、シフト後もほとんどのビットが`1`のままですが、シフト量に応じて最下位ビットが変わります。

これらのケースは、`SHL`命令の基本的な動作と、特定の入力に対する挙動を示しています。
ビットシフトは、数値を効率的に操作するための基本的な手法であり、これらの例は、その動作原理を理解するのに役立ちます。
また、イーサリアムの仮想マシン（EVM）において、これらの操作はガスコストが低いため、スマートコントラクトの実行において効率的です。

## `SHR`

<details><summary>テスト</summary><div>

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHR
---
0x4000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0xff
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0100
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0101
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SHR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SHR
---
0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SHR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

</div></details>


これらのテストケースは、`SHR`（論理右シフト）命令の動作を示しています。
`SHR`命令は、指定された数値（第二オペランド）を、特定のビット数（第一オペランド）だけ右にシフトします。
シフトすると、数値は`2`のシフト量で割られ、空いたビット位置は`0`で埋められます。

- シフト量が`0`の場合、数値は変わりません。
    - 例えば、`1`を`0`ビット右シフトすると、結果は`1`のままです。
- シフト量が`1`の場合、数値は半分になります。
    - `1`を`1`ビット右シフトすると、結果は`0`になります。
- 最上位ビットが`1`で残りが`0`の数値をシフトすると、シフト量に応じてビットの位置が変わります。
    - `1`ビット右シフトすると、最上位ビットが中央に移動します。
- シフト量が`256`以上の場合、結果は常に`0`になります。
    - `256`ビット以上シフトすると、全てのビットが`0`に置き換えられます。
- 全てのビットが`1`の数値をシフトすると、シフト後もほとんどのビットが`1`のままですが、シフト量に応じて最下位ビットが変わります。

これらのケースは、`SHR`命令の基本的な動作と、特定の入力に対する挙動を示しています。
論理右シフトは、数値を効率的に操作するための基本的な手法であり、これらの例は、その動作原理を理解するのに役立ちます。
また、イーサリアムの仮想マシン（EVM）において、これらの操作はガスコストが低いため、スマートコントラクトの実行において効率的です。

## `SAR`

<details><summary>テスト</summary><div>

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x00
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000001
PUSH 0x01
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SAR
---
0xc000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0xff
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0100
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0x8000000000000000000000000000000000000000000000000000000000000000
PUSH 0x0101
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x00
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x01
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SAR
---
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
```

```
PUSH 0x0000000000000000000000000000000000000000000000000000000000000000
PUSH 0x01
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x4000000000000000000000000000000000000000000000000000000000000000
PUSH 0xfe
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xf8
SAR
---
0x000000000000000000000000000000000000000000000000000000000000007f
```

```
PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xfe
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000001
```

```
PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0xff
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

```
PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PUSH 0x0100
SAR
---
0x0000000000000000000000000000000000000000000000000000000000000000
```

</div></details>


これらのテストケースは、`SAR`（算術右シフト）命令の動作を示しています。
`SAR`命令は、指定された数値（第二オペランド）を、特定のビット数（第一オペランド）だけ右にシフトしますが、`SHR`（論理右シフト）と異なり、符号ビットを保持します。

- シフト量が`0`の場合、数値は変わりません。
    - 例えば、`1`を`0`ビット右シフトすると、結果は`1`のままです。
- シフト量が`1`の場合、数値は半分になりますが、符号ビットは維持されます。
- 最上位ビットが`1`の数値（負の数）をシフトすると、シフト量に応じてビットの位置が変わりますが、最上位ビット（符号ビット）は保持され、結果は負の数値として残ります。
- シフト量が`256`以上の場合、負の数値は全ビットが1の状態で保持されます。
    - これは、シフト後も負の数値を示すためです。
- 全てのビットが`1`の数値（最も大きい負の数値）をシフトすると、シフト量に関わらず、結果は全ビットが`1`のままです。
- `0`ビットの数値（`0`）をシフトすると、結果は常に`0`です。
- 最上位ビットが`0`で残りが`1`の数値（正の数値）をシフトすると、シフト量に応じて数値が減少し、結果は正の数値として残ります。

これらのケースは、`SAR`命令の基本的な動作と、特定の入力に対する挙動を示しています。
算術右シフトは、数値を効率的に操作するための基本的な手法であり、符号ビットの保持は負の数値の処理において重要です。
これらの例は、その動作原理を理解するのに役立ちます。
また、イーサリアムの仮想マシン（EVM）において、これらの操作はガスコストが低いため、スマートコントラクトの実行において効率的です。

# 実装

**Client support**

- [cpp-ethereum](https://github.com/ethereum/cpp-ethereum/pull/4054)

**Compiler support**

- [Solidity/LLL](https://github.com/ethereum/solidity/pull/2541)

# テスト


**Sources**

https://github.com/ethereum/tests/tree/develop/src/GeneralStateTestsFiller/stShift

**Filled Tests**

https://github.com/ethereum/tests/tree/develop/GeneralStateTests/stShift
https://github.com/ethereum/tests/tree/develop/BlockchainTests/GeneralStateTests/stShift

# 引用

Alex Beregszaszi (@axic), Paweł Bylica (@chfast), "EIP-145: Bitwise shifting instructions in EVM," Ethereum Improvement Proposals, no. 145, February 2017. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-145.

# 最後に

今回は「」についてまとめてきました！
いかがだったでしょうか？

質問などがある方は以下のTwitterのDMなどからお気軽に質問してください！

[Twitter @cardene777](https://twitter.com/cardene777)

他の媒体でも情報発信しているのでぜひ他も見ていってください！

https://chaldene.net/

https://zenn.dev/heku

https://mirror.xyz/0xcE77b9fCd390847627c84359fC1Bc02fC78f0e58

https://cardene.notion.site/ERC-EIP-2a03fa3ea33d43baa9ed82288f98d4a9?pvs=4