今天我读到一篇很有意思的文章，讲的是《Wolfenstein 3D》如何用线性反馈移位寄存器（Linear Feedback Shift Register）实现一种渐变效果。屏幕上的每个像素都会以伪随机的方式被设为红色，直到整个屏幕都变成红色（当然，根据游戏中发生的事件不同，也可能是其他颜色）。介绍这一实现的博客文章在这里，很值得一读：http://fabiensanglard.net/fizzlefade/index.php

你可能会好奇，为什么原始代码要用 LFSR，又为什么我要提出另一种方案，而不是直接用最朴素的 setPixel(rand(),rand())：正如那篇博客所指出的，用伪随机数生成器这么做不仅慢，视觉效果也非常糟糕，因为屏幕上已经变红的像素越多，随机命中一个新的、尚未变红的像素的概率就越低，所以最后剩下那几个像素要等很久才能变红（我*敢打赌*，很多读过这篇文章的人早年在 Spectrum、C64 时代，或者后来用 QBASIC、GWBasic 时都尝试过这种做法）。在那篇文章的结尾，作者这样写道：

“由于该效果是通过逐个绘制像素来实现的，当开发者尝试把它移植到硬件加速的 GPU 上时，很难复现。除了 Wolf4SDL 找到了一组能支持高于 320x200 分辨率的 LFSR 抽头配置外，没有任何移植版本成功复现了 fizzlefade。”

这虽然算不上什么高深技术，但要为其他分辨率找到合适的 LFSR，可能确实不容易。不过，不管为其他分辨率寻找合适 LFSR 的实际难度到底如何，移植者们完全可以用另一种叫做 Feistel 网络的技术，以一种极其简单的方式得到完全相同的结果。

什么是 Feistel 网络？

它是密码学中常用的一种基本结构：它能在两组比特序列之间建立一种变换，而且无论在 Feistel 网络内部使用了何种非线性变换，这种变换始终是可逆的。通俗地说，Feistel 网络可以按照某个函数 F()，把一个 32 位数 A 转换成另一个 32 位数 B，并且之后总能从 B 还原回 A。正因为该函数可逆，也就意味着对于每一个输入值，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 位整数拆成两个 8 位整数 L 和 R，进行 N 轮变换，再把它们重新组合成一个 16 位整数作为输出。

但这对我们实现 FizzleFade 有什么用呢？可以把二维屏幕想象成一个一维的像素数组。如果分辨率像原版游戏那样是 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”只是几个随机挑选的乘法和移位操作，基本是随意选的。我用了 8 轮，即便如果 F 函数设计得更好也许并不需要这么多，但我希望效果看起来足够随机（顺便说一句，用随机画点的方式也是在视觉上发现明显分布缺陷的好方法）。

要用 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 网络这种一一对应的伪随机映射特性在其他场景下也非常有用。比如，我就在自己的基数树实现测试中使用过它（如果你感兴趣，项目在这里：https://github.com/antirez/rax）。这是程序员工具箱里一件值得常备的好工具。