今日、Wolfenstein 3DというゲームがLinear Feedback Shift Register（線形帰還シフトレジスタ、LFSR）を使ってフェードエフェクトを実装していたという興味深い記事を読んだ。画面のすべてのピクセルが疑似ランダムに赤く塗られていき、やがて画面全体が赤（ゲーム内のイベントによっては他の色）に染まるというものだ。その実装を解説したブログ記事はこちらにあり、一読の価値がある： http://fabiensanglard.net/fizzlefade/index.php

なぜオリジナルのコードがLFSRを使っていたのか、あるいはなぜ私が単純なsetPixel(rand(),rand())ではなく別のアプローチを提案するのか、疑問に思うかもしれない。ブログ記事でも指摘されているように、疑似乱数生成器でこれをやる方法は遅いだけでなく、見た目も非常に悪い。すでに赤くなっているピクセルが多いほど、まだ赤くなっていない新たなピクセルに当たる確率が低くなるため、最後の数ピクセルが赤くなるまでに永遠のような時間がかかってしまうのだ（SpectumやC64、あるいは後のQBASICやGWBasicの時代にこれを試したことがある読者も多いはずだと*思う*）。ブログ記事の最後で、著者はこう書いている：

「このエフェクトはピクセルを1つずつ描画することで実現されているため、ハードウェアアクセラレーションされたGPUへ移植しようとした開発者にとって再現が困難でした。320x200を超える解像度に対応するLFSRのタップ構成を見つけたWolf4SDLを除き、どの移植版もfizzlefadeを再現できませんでした。」

大した話ではないが、他の解像度で適切なLFSRを見つけるのは難しかったのかもしれない。しかし、他の解像度用の適切なLFSRを見つけることの実際の難易度がどうであれ、移植版の作者たちはFeistelネットワークと呼ばれる別の手法を使えば、全く同じ結果を簡単に得ることができたはずだ。

Feistelネットワークとは何か？

暗号の分野で典型的に使われる構成要素だ。ビット列を別のビット列へ変換するもので、Feistelネットワークの内部でどんな非線形変換を使っても、その変換が常に可逆になるように作られている。実用的に言えば、Feistelネットワークは例えば32ビットの数値Aを、ある関数F()に従って別の32ビットの数値Bに変換することができ、後でBからAに常に戻すことができる。関数が可逆であるということは、Feistelネットワークが入力値ごとに*異なる*出力値を生成することを意味する。

これは擬似コードで書いたシンプルなFeistelネットワークだ：

Split the input into L and R halves (Example: L = INPUT & 0xFF, R = INPUT >> 8)
REPEAT for N rounds:
    next_L = R
    R = L XOR F(R)
    L = next_L
END
RETURN the value composing L and R again into a single sequence of bits: R<<8 | L

つまり基本的には（例えば）16ビット整数を2つの8ビット整数LとRに分割し、Nラウンドにわたって何らかの変換を行い、再び1つの16ビット整数に合成して出力とする、という仕組みだ。

では、これがFizzleFadeの実装にどう役立つのだろうか？ 2次元の画面を1次元のピクセル配列として考えることができる。オリジナルのゲームと同じ320x200の解像度なら、ピクセルは0から63999まであることになる。そこで、0から63999までの整数ごとに、カウントしながらFeistelネットワークが返した位置のピクセルを塗っていけば、ランダムに見えるピクセル位置を生成できる。問題は、Feistelネットワークがビット単位で動作するため、0から63999までをちょうど扱うことはできず、十分な大きさの2のべき乗を選ばなければならないことだ。この場合最も近いのは16だ。16ビットあれば65536通りの整数から整数への変換が可能で、実際のピクセルの設定に使われないサイクルが少しあるだけなので、大きな無駄にはならない。

そこで、JavaScriptで書いたFeistelネットワークは次のようになる：

/* Transforms the 16 bit input into another seemingly psenduo random number
 * in the same range. Every input 16 bit input will generate a different
 * 16 bit output. This is called a Feistel network. */
function feistelNet(input) {
    var l = input & 0xff;
    var r = input >> 8;
    for (var i = 0; i < 8; i++) {
        var nl = r;
        var F = (((r * 11) + (r >> 5) + 7 * 127) ^ r) & 0xff;
        r = l ^ F;
        l = nl;
    }
    return ((r<<8)|l)&0xffff;
}

使っている非線形変換「F」は、ほとんどランダムに選んだいくつかの乗算とシフトを組み合わせただけのものだ。より良いF関数があれば8ラウンドも必要ないかもしれないが、見た目をランダムにしたかったので8ラウンドにしている（ちなみに、ランダムにピクセルを描画することは、自明な分布の偏りなどを視覚的に見つけるのにもそこそこ良い方法だ）。

これをJavaScriptのcanvasで実装するには、2Dコンテキストを取得してピクセルを描画するための関数があと少し必要になる。

最終的なコードはこちらのGistにある： https://gist.github.com/antirez/6d58860b221a6ae5622ced8ccdddbe47

結果はここで見ることができる： http://antirez.com/misc/fizzlefade.html

この記事で探求した本来の問題は、異なる解像度でこのエフェクトを実装する方法を見つけることだったので、320x200の場合の自明な拡張に過ぎないとはいえ、例として、同じことを1024*768で実装したいと想像してみよう。ピクセル数は786432なので、2^20の1048576通りの整数で十分収まる。Feistelネットワークを20ビットの入出力を持つように、LとRの変数を10ビットずつ使うように変更すれば、あとはほぼ同じだ。ただし停止条件（フレーム数をチェックしている部分）も変更するのを忘れないように。

実際、Feistelネットワークの1対1の疑似ランダムなマッピングという特性は、他の文脈でも非常に役立つ。例えば、私は自分の基数木（radix tree）の実装のテストでもこれを使った（興味があればhttps://github.com/antirez/raxを参照）。プログラマの頭の中の道具箱に入れておくと良い道具の一つだ。