この話。
PHP の mt_rand() は一貫して壊れている(consistently broken)らしい - 唯物是真 @Scaled_Wurm
PHPのmt_rand()が実装にミスがあることを知ったので、「PHPのコミットログに名前を載せるぞ╭( ・ㅂ・)و」と思ってプルリクを送ったら、一旦マージされたけど、リバートされた。
詳細
https://github.com/php/php-src/pull/1681/files
ついでにテストコードも付けたけど、直すべきは1文字だけ。
twistというマクロの定義が1文字間違えている。
loBit(u)
ではなくloBit(v)
が正しい。
#define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
このマクロはオリジナルのソースコードの
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
という処理に対応している。最適化されていて分かりづらいけど、loBit(x)
は0
か1
を返すので、符号を反転させると、0x00000000
か0xffffffff
になり、andを取ることで0x00000000
と0x9908b0df
になる。オリジナルのソースコードのmag01
は{0x0UL, 0x9908b0df}
なので、表を引かずに同じ動作をするようになっている。オリジナルと同じ結果を得るためには、u
ではなくv
の下位1bitを使わなければいけない。
PHPにmt_randが実装された当初から間違っていたわけではなく、10年前にコードを最適化したときにエンバグしたらしい。 この前はオリジナルのメルセンヌ・ツイスタと同じ値を返していたはず。
普通に乱数を使う分には全く問題の無いレベルだと思うけど、この違いで乱数の周期性などがどの程度悪化しているのか、あるいは全く影響は無いのか、気になる。
経緯
2015年10月。とあるセキュリティ系のコンテストでmt_randを推測する問題を解いていて、なぜかC++での実装と上手く結果が合わなかった。乱数を推測するツールがあると教えてもらってそのツールを見ていたら、ソースコードの中にmt_twist
という関数とphp_twist
という関数があって、PHPは実装が異なっていることを知った。なので、このバグは私が見つけたわけではない。知っている人は知っている話だったらしい。1文字だけだし、直そうかとも思ったけど、面倒そうなので止めた。
有名OSSにプルリクだ!と思ったけど、面倒だから止めた。
— kusanoさん@がんばらない (@kusano_k) 2015, 10月 19
2015年12月。このインタビューを読んで「PHPすごいなー」と思い、コミットログに名前を残したくなったので、バグ報告をして、プルリクを送った。この時点で、「たしかにバグだけど、直したら互換性が崩れるのでは? どうしよう」というようなコメントがついていた。
2016年2月。このコミットと衝突していたので、解消して、ついでに、「そもそも10年前の修正で互換性が崩れていたけど、今まで誰も文句を言っていないし、もう一度崩れても別に良いのでは」とコメントを付けた。 mt_rand()の返す値が変わったら困るような状況があるのなら、10年前の変更の時点で気が付かれて、すぐに直されたのではないかと。 今にして思うと、ちょっと乱暴だったかもしれない。 すっとマージされたかと思いきや、直後にリバートされた。
PHPに送った1文字修正するプルリクエストがマージされた🎉 mt_rand()の返す値が元のメルセンヌツイスタと異なっていた。https://t.co/Z5WJhHVyNd
— kusanoさん@がんばらない (@kusano_k) 2016, 2月 17
この前マージされたPHPのmt_rand()を修正するコミットがリバートされていた(´・ω・`)知らんがなhttps://t.co/zKI1NlT46thttps://t.co/wZldV1Aqiv
— kusanoさん@がんばらない (@kusano_k) 2016, 2月 18
PHPのバグ修正の方法
この手の大規模なソフトウェアは開発環境を整えるだけで一苦労というイメージがあったけど、とても簡単だった。
git clone git@github.com:php/php-src.git
cd php-src
./buildconf
./configure
make
で、sapi/cli/php
に本体ができる。他のファイルを参考にして、tests/
にテスト用のスクリプトを置くと、make test
で実行される。
README.mdに書いてあるように、 https://bugs.php.net にチケットを作って、その番号を参照してプルリクを送れば良いらしい。
リバートについて
「だからPHPはダメなんだ」というような感じで叩かれているし、リバートされたときは「せっかくマージされたのにリバートするなよ……」と思ったけど、正しさよりもユーザーの利便性を優先しているからこそ、PHPはここまで流行っているのではないかと思う。 皮肉ではなく。 たとえ乱数の周期が2100になっていても困る人はいないけど、乱数の値が変わったら困る人ならいそう。
環境非依存の乱数
単に性能の良い乱数ならアルゴリズムの名前を付ける必要は無いので、各言語に実装されているメルセンヌ・ツイスタは言語が変わっても再現性のある乱数が得られるのが魅力だと思っていた。例えば、今回の修正が反映されれば、
<?php mt_srand(12345678); for ($i=0; $i<8; $i++) echo mt_rand().PHP_EOL;
と
#include <iostream> #include <random> int main() { std::mt19937 rand(12345678); for (int i=0; i<8; i++) std::cout<<rand()/2<<std::endl; }
はどちらも
527860569 1711027313 1280820687 688176834 770499160 412773096 813703253 898651287
という値を出力するようになる。C++は32bitで値を返すので、/2
しているのがちょっと残念だけど。
他の言語はどうなのかと、Pythonを見てみると、genrand_int32()
の値を直接取得するにはgetrandbits(32)
という無理矢理感のある方法だし、init_genrand()
を呼び出す手段は無いようだった。
言語間でも再現性のある乱数という需要はあまり無いのかもしれない。残念。
おまけ
私がバグチケットを作ったときに直前にあったバグが面白かった。
https://bugs.php.net/bug.php?id=71151
<?php
だけのファイルはHTMLからの脱出ができないらしい。「php
の後には空白文字が必要で、EOFは空白文字なのかという哲学的な問題だ」とRasmus氏がコメントしている。
追記
phpのmt_rand()の件についてRevertした方のアンサーソングのようです。ご確認ください。https://t.co/kgW5Tnnu68https://t.co/FYmMWacU6s
— sasezaki (@sasezaki) 2016年2月27日
PHPでの、メルセンヌツイスタと今のmt_rand()と等価な処理の実装。乱数の値が一致する必要がある場合にはこれを使えば良さそう。
lt/PHP-MT19937: PHP implementations of MT19937, MT19937-64 and PHPs MT variant