PHPの掛け算の挙動
PHPの整数同士の掛け算では, 環境にも依りますが, 概ね64bit符号付き整数の範囲に収まる場合に整数値, 収まらない場合に倍精度浮動小数で結果を返します。
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
ソースを読んでみよう。
アーキテクチャやコンパイラに依存した機能を使わないバージョンの掛け算のオーバーフロー検出がヤバい。
そしてそのコードは今も残っている。
整数同士の掛け算の実装を探す
(公式のミラーですが)GitHubのphp/php-srcから掛け算の実装をしているコードを探します。
実際に読みたい部分のコードを探すのは割と手間がかかりますが, 今回は掛け算という言語のコアな部分のコードなので, 恐らくライブラリを記述しているext/以下ではなくZend/以下のZendエンジンに含まれているだろうと当たりを付けて探したところ, Zend/zend_multiply.hというそのものズバリなファイルが見つかりました。
PHPに於ける掛け算の実体はこのヘッダファイルで定義されているZEND_SIGNED_MULTIPLY_LONG(a, b, lval, dval, usedval)マクロであり, ターゲット環境毎に最適化されるように記述されています。
このマクロ関数の引数と実装を見ると, 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のサイズが一致する場合に選択されます。
#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][2]。
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マクロは環境に応じて最適化されたものが選ばれるようになっていますが, 最適化された実装が選択出来ない場合(具体的にどういう環境が該当するかはよく分かりませんが)に最後に選ばれる実装は次のようになっています。
#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の規格では符号付き整数のオーバーフローは未定義動作です。
符号付き整数については演算の結果がオーバーフローするかどうかを事前に判定しなければならず, とりあえずオーバーフローしてもかまわないから掛け算してしまえ, という思い切った実装は素性が良いとは言えません。
ただ, 現実問題として, PHPの記述はANSI Cでされることになっており, これをC89だと理解すると, 符号付き整数のオーバーフロー検出はかなり面倒です。
というのもC89の段階では除数と被除数の少なくとも一方が負の数の場合, 剰余の符号がどうなるかは実装定義である[3]ため, コードの記述に於いてそれを考慮する必要があると思われるためです。
符号無し整数で扱えば難しくないような気がしてきました。 (thanks @fujitanozomu)
long doubleが倍精度であるとき正しく検出出来ない
この実装に於いては, long doubleが拡張倍精度以上, 即ち仮数部が64bit以上であることを暗に前提としています。
標準Cの規格では, recommended practiceとしてlong doubleは拡張倍精度であるべき, としてはいますが, 倍精度であることも認められており, 実際MSVCではlong doubleは倍精度になっています[4]。
longが64bitかつlong doubleが倍精度である場合に, PHPはときどき掛け算が出来ないで言及されている値を入れて計算してみましょう。
#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の実装は次のようになっています。
# 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]。
__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を利用しているため, 以前の実装と比較して安全かつ確実にオーバーフロー検出が可能になっています。
修正のコミット
上記の現在のコードへの修正はこのあたりの一連のコミットで行われています。
特に大部分のコードが記述されたコミットのコメントを読んてみると,
Improve multiplication on x64. - weltling
となっており, 元々の実装のバグを承知した上での修正であったかはよく分かりませんでした。
とりあえずPHP7.2.0以降のバージョンではWindowsに於いてはMSVCでビルドされたものであってもx86-64向けのものならば上記のcompiler intrinsicを用いた実装が採用されており, 正しくオーバーフロー検出がされるようになっています。
まとめ
PHPはWindowsでもかなり広く使われていると思いますが, それでもこのような割と初歩的なバグがまだあるものなのだなと思いました。
これ, @takepan さんが踏むまで誰も踏まなかったんでしょうかね？
あとMSVC x64向けはよい実装に置き換えられましたが, 未定義動作だったりバグになる可能性のあるコードがまだ残っているのがやや気になるところではあります。
具体的にどういう環境で踏み抜くのかと言われると現実的には問題ないような気もしますが。
修正してコントリビュータになろうとか思ってコード書き始めてみたらC89縛りだと面倒だわ読みにくいコードが出来るわで先にも書いた多分現実的には問題ないということでモチベーションが空になってしまったので誰か直してみませんか。