PHPのmt_rand()にプルリクを送った

この話。

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文字だけだし、直そうかとも思ったけど、面倒そうなので止めた。

https://github.com/GeorgeArgyros/Snowflake/blob/22d2a261f159e1a7b4233f0f4aac4020a90e079f/mt_rand/mt_rand.c#L39

2015年12月。このインタビューを読んで「PHPすごいなー」と思い、コミットログに名前を残したくなったので、バグ報告をして、プルリクを送った。この時点で、「たしかにバグだけど、直したら互換性が崩れるのでは？　どうしよう」というようなコメントがついていた。

2016年2月。このコミットと衝突していたので、解消して、ついでに、「そもそも10年前の修正で互換性が崩れていたけど、今まで誰も文句を言っていないし、もう一度崩れても別に良いのでは」とコメントを付けた。 mt_rand()の返す値が変わったら困るような状況があるのなら、10年前の変更の時点で気が付かれて、すぐに直されたのではないかと。 今にして思うと、ちょっと乱暴だったかもしれない。 すっとマージされたかと思いきや、直後にリバートされた。

PHPのバグ修正の方法

この手の大規模なソフトウェアは開発環境を整えるだけで一苦労というイメージがあったけど、とても簡単だった。

git clone [email protected]: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()と等価な処理の実装。乱数の値が一致する必要がある場合にはこれを使えば良さそう。

lt/PHP-MT19937: PHP implementations of MT19937, MT19937-64 and PHPs MT variant