PHPの整数同士の掛け算の実装を眺める

# PHPの掛け算の挙動
PHPの整数同士の掛け算では, 環境にも依りますが, 概ね64bit符号付き整数の範囲に収まる場合に整数値, 収まらない場合に倍精度浮動小数で結果を返します。

```php
var_dump(PHP_INT_MAX * 1); // -> int(9223372036854775807)
var_dump(PHP_INT_MAX * 2); // -> float(1.844674407371E+19)
```

ところが, **[PHPはときどき掛け算が出来ない][]**で言及されているように, PHP7.1系列まではWindowsなど一部環境の下では演算結果が64bit符号付き整数の範囲に収まる場合でも結果が浮動小数になる場合がありました。
この記事では実際の実装から, 何故そのようなことが起こったのか, またどのように修正されたのかを眺めてみたいと思います。

## TL; DR
[ソースを読んでみよう][php/php-src Zend/zend_multiply.h]。
アーキテクチャやコンパイラに依存した機能を使わないバージョンの掛け算のオーバーフロー検出がヤバい。
そしてそのコードは**今も残っている**。


# 整数同士の掛け算の実装を探す
(公式のミラーですが)GitHubの[php/php-src][]から掛け算の実装をしているコードを探します。
実際に読みたい部分のコードを探すのは割と手間がかかりますが, 今回は掛け算という言語のコアな部分のコードなので, 恐らくライブラリを記述している`ext/`以下ではなく`Zend/`以下のZendエンジンに含まれているだろうと当たりを付けて探したところ, `Zend/zend_multiply.h`というそのものズバリなファイルが見つかりました。

PHPに於ける掛け算の実体はこのヘッダファイルで定義されている`ZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval)`マクロであり, ターゲット環境毎に最適化されるように記述されています。
このマクロ関数の引数と実装を見ると, PHPの掛け算は内部的には次のようになっていることが分かります。

```c:PHPの掛け算の内側
long a = 1, b = 100; // 掛け算したい数
long lval;           // 結果が整数の場合の格納用変数
double dval;         // 結果が小数の場合の格納用変数
int usedval;         // 演算結果が整数か小数かを格納する変数, 0なら整数, 1なら小数

ZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval);

if (usedval == 0) {
    // 結果が整数の場合, lvalに格納されている
} else {
    // 結果が小数の場合, dvalに格納されている
}
```


# 掛け算の実装を眺める
実装は環境に応じて多岐に渡っており, 全てを解説するのは手間なので, ここでは幾つかを紹介します。

上記のソースの先頭のほうに書かれている下記の実装は, コンパイラが`__builtin_smull_overflow`関数を持っていて, かつPHPが内部的に`long`として扱う型のサイズと`long`のサイズが一致する場合に選択されます。


```c:php/php-src/Zend/zend_multiply.h#L27-L33
#define ZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval) do {	\
	long __tmpvar;		 											\
	if (((usedval) = __builtin_smull_overflow((a), (b), &__tmpvar))) {	\
		(dval) = (double) (a) * (double) (b);						\
	}																\
	else (lval) = __tmpvar;											\
} while (0)
```

`__builtin_smull_overflow`関数はgccやclangなどが実装しており, 以下のプロトタイプを持ちます[[1]][Using the GNU Compiler Collection (GCC): Integer Overflow Builtins][[2]][Clang Language Extensions]。

```c
bool __builtin_smull_overflow(long int a, long int b, long int *res);
```

このビルトイン関数は第1引数及び第2引数を内部的に無限精度に昇格して乗算を行い, 結果の無限精度整数を`long`型にキャストして第3引数`res`にストアします。
無限精度の掛け算の結果と`long`へのキャスト後の値が一致すれば`false`, 一致しなければ`true`を返します。
要するに掛け算の結果が`long`に収まれば`false`, オーバーフローするようであれば`true`が返ってきます。

この関数は内部的に`long`に収まらない結果となっても正しく動作することが保証されているため, 正しくオーバーフローを検出することが出来, その場合には`a, b`を`double`にキャストして掛け算し, 結果を`dval`に格納するようになっています。


# 最後に選ばれる実装
さて, `ZEND_SIGNED_MULTIPLY_LONG`マクロは環境に応じて最適化されたものが選ばれるようになっていますが, 最適化された実装が選択出来ない場合(具体的にどういう環境が該当するかはよく分かりませんが)に最後に選ばれる実装は次のようになっています。

```c:php/php-src/Zend/zend_multiply.h#L142-L151
#define ZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval) do {	\
	long   __lres  = (a) * (b);										\
	long double __dres  = (long double)(a) * (long double)(b);		\
	long double __delta = (long double) __lres - __dres;			\
	if ( ((usedval) = (( __dres + __delta ) != __dres))) {			\
		(dval) = __dres;											\
	} else {														\
		(lval) = __lres;											\
	}																\
} while (0)
```

読んでみると分かりますが, 何やら怪しいことをやっています。
とりあえず`a`と`b`とを掛けた結果を格納し, `long double`にキャストして得られた結果と比較しています。

実際, この実装は色々と問題があります。

## 符号付き整数の演算をオーバーフローさせている
標準Cの規格では符号付き整数のオーバーフローは**未定義動作**です。
符号付き整数については演算の結果がオーバーフローするかどうかを事前に判定しなければならず, とりあえずオーバーフローしてもかまわないから掛け算してしまえ, という思い切った実装は素性が良いとは言えません。

<font color="#cccccc">
~~ただ, 現実問題として, PHPの記述はANSI Cでされることになっており, これをC89だと理解すると, 符号付き整数のオーバーフロー検出はかなり面倒です。~~
~~というのもC89の段階では除数と被除数の少なくとも一方が負の数の場合, 剰余の符号がどうなるかは実装定義である[[3]][INT10-C. % 演算子を使用する際、結果の剰余が正であると想定しない]ため, コードの記述に於いてそれを考慮する必要があると思われるためです。~~
</font>
**符号無し整数で扱えば難しくないような気がしてきました。** (thanks @fujitanozomu)


## `long double`が倍精度であるとき正しく検出出来ない
この実装に於いては, `long double`が拡張倍精度以上, 即ち仮数部が64bit以上であることを暗に前提としています。
標準Cの規格では, **recommended practice**として`long double`は拡張倍精度であるべき, としてはいますが, 倍精度であることも認められており, 実際MSVCでは`long double`は倍精度になっています[[4]][Data Type Ranges - Language Reference]。

`long`が64bitかつ`long double`が倍精度である場合に, **[PHPはときどき掛け算が出来ない][]**で言及されている値を入れて計算してみましょう。

```cpp:gcc&#32;(double&#58;&#32;倍精度,&#32;long&#32;double&#58;&#32;拡張倍精度),&#32;書式が無いのでC++
#include <iostream>
#include <boost/format.hpp>

int main()
{
    uint64_t op1 = 117231566641875000;
    uint64_t op2 = 7;
    uint64_t lval = op1 * op2;

    long double ldval = static_cast<long double>(op1) * static_cast<long double>(op2);
    long double lddelta = static_cast<long double>(lval) - ldval;

    double dval = static_cast<double>(op1) * static_cast<double>(op2);
    double ddelta = static_cast<double>(lval) - dval;


    std::cout << boost::format("ldval:   %.f") % ldval << std::endl;
    std::cout << boost::format("lddelta: %.20e") % lddelta << std::endl;
    std::cout << boost::format("dval:    %.f") % dval << std::endl;
    std::cout << boost::format("ddelta:  %.20e") % ddelta << std::endl;

    return 0;
}
```
```:実行結果
ldval:   820620966493125000
lddelta: 0.00000000000000000000e+00
dval:    820620966493125120
ddelta:  -1.28000000000000000000e+02
```

このように, 倍精度では精度が足らず, 64bit符号付き整数に収まるにも拘らずオーバーフロー検出に引っかかってしまうことが分かります。
そもそも仮数部が53bitな時点で64bitの符号付き整数を表現するのに11bit不足するのは明らかですね。

そして, お気付きの方もいらっしゃるかもしれませんが, この場合のマクロと全く同じものが`Zend/zend_multiply.h`の98-108行目にも定義されており, そして嘗てPHP7.1系列以前ではWindowsではこのコードが内部的に利用されるようになっていました(というかPHP7.1系列では今でも使われています)。

Windows向けに配布されているバイナリはMSVCでビルドされたものであるため, ビルド時にこの実装が選択されることになり, 更に`long double`の精度が不足してオーバーフローを誤検出してしまうのが**ときどき掛け算が出来ない**原因であったわけです。

# 現在のMSVC実装
幸い, 上記のバグはPHP7.2.0から修正されました。
現在のMSVC向けの`ZEND_SIGNED_MULTIPLY_LONG`の実装は次のようになっています。

```c:php/php-src/Zend/zend_multiply.h#L85-L96
#  pragma intrinsic(_mul128)
#  define ZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval) do {       \
	__int64 __high; \
	__int64 __low = _mul128((a), (b), &__high); \
	if ((__low >> 63I64) == __high) { \
		(usedval) = 0; \
		(lval) = __low; \
	} else { \
		(usedval) = 1; \
		(dval) = (double)(a) * (double)(b); \
	} \
} while (0)
```

この実装では, MSVCのcompiler intrinsicである`__mul128`を利用してオーバーフロー検出を行っています。
このintrinsicのプロトタイプは次のようになっています[[5]][__mul128 - Compiler Intrinsics and Assembly Language]。

```c
__int64 _mul128(__int64 Multiplier, __int64 Multiplicand, __int64 *HighProduct);
```

このintrinsicは第1引数と第2引数に64bit符号付き整数を受け取り, 内部的に128bitで乗算をした上で計算結果の上位64bitを第3引数`HighProduct`にストア, 下位64bitを返値とします。
オーバーフロー検出は, 上位64bitと下位64bitが同じ符号bitを持つことに注意すれば, 乗算の結果が正の場合に`__high`が`0x0`, 負の場合に`0xFFFFFFFFFFFFFFFF`であることを確かめればよいので`__low`を右に63bit算術シフトして一致するかを確認すればよいということになります。

この実装は内部128bitで乗算出来るcompiler intrinsicを利用しているため, 以前の実装と比較して安全かつ確実にオーバーフロー検出が可能になっています。

## 修正のコミット
上記の現在のコードへの修正は[このあたり](https://github.com/php/php-src/compare/143ee7..e3ce4dc)の一連のコミットで行われています。
特に大部分のコードが記述された[コミットのコメント](https://github.com/php/php-src/commit/c5af4b)を読んてみると, 

> Improve multiplication on x64. - weltling

となっており, 元々の実装のバグを承知した上での修正であったかはよく分かりませんでした。

とりあえずPHP7.2.0以降のバージョンではWindowsに於いてはMSVCでビルドされたものであってもx86-64向けのものならば上記のcompiler intrinsicを用いた実装が採用されており, 正しくオーバーフロー検出がされるようになっています。

# まとめ
PHPはWindowsでもかなり広く使われていると思いますが, それでもこのような割と初歩的なバグがまだあるものなのだなと思いました。
これ, @takepan さんが踏むまで誰も踏まなかったんでしょうかね？

あとMSVC x64向けはよい実装に置き換えられましたが, 未定義動作だったりバグになる可能性のあるコードがまだ残っているのがやや気になるところではあります。
具体的にどういう環境で踏み抜くのかと言われると現実的には問題ないような気もしますが。

~~修正してコントリビュータになろうとか思ってコード書き始めてみたらC89縛りだと面倒だわ読みにくいコードが出来るわで先にも書いた多分現実的には問題ないということでモチベーションが空になってしまったので誰か直してみませんか。~~


# 資料・参考文献

* [PHPはときどき掛け算が出来ない][]
* [php/php-src][]
* [Using the GNU Compiler Collection (GCC): Integer Overflow Builtins][]
* [Clang Language Extensions][]
* [INT10-C. % 演算子を使用する際、結果の剰余が正であると想定しない][]
* [Data Type Ranges - Language Reference][]
* [__mul128 - Compiler Intrinsics and Assembly Language][]

[PHPはときどき掛け算が出来ない]: https://qiita.com/takepan/items/47c61aedd017b14bc61e
[php/php-src Zend/zend_multiply.h]: https://github.com/php/php-src/blob/master/Zend/zend_multiply.h
[php/php-src]: https://github.com/php/php-src
[Using the GNU Compiler Collection (GCC): Integer Overflow Builtins]: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
[Clang Language Extensions]: http://clang.llvm.org/docs/LanguageExtensions.html
[INT10-C. % 演算子を使用する際、結果の剰余が正であると想定しない]: https://www.jpcert.or.jp/sc-rules/c-int10-c.html
[Data Type Ranges - Language Reference]: https://docs.microsoft.com/cpp/cpp/data-type-ranges
[__mul128 - Compiler Intrinsics and Assembly Language]: https://docs.microsoft.com/en-us/cpp/intrinsics/mul128