Optimizing Brainfuck interpreter in the C preprocessor

Source | HN Comments

该项目是一个用C预处理器实现的优化版Brainfuck解释器，符合C99标准。它使用替代指令名称（R, L, I, D, A, O, G, B, E）来代替Brainfuck的原始指令。文章提供了示例代码，并介绍了使用不同编译器（如tcc、gcc、clang、msvc、mcpp）进行编译的方法。此外，文章还提供了性能基准测试，并感谢了相关贡献者。

C预处理器优化Brainfuck解释器

这是一个符合C99标准的*，仅使用C预处理器编写（和执行）的优化版Brainfuck实现。

*如果您发现任何不符合标准或未明确/未定义的内容，请提交 issue。

示例

Hello World| 输出 ---|---

#include "bf.c"
BF(,I,I,I,I,I,I,I,I,B,R,I,I,I,I,B,R,I,I,R,I,I,
  I,R,I,I,I,R,I,L,L,L,L,D,E,R,I,R,I,R,D,R,R,
  I,B,L,E,L,D,E,R,R,A,R,D,D,D,A,I,I,I,I,I,I,
  I,A,A,I,I,I,A,R,R,A,L,D,A,L,A,I,I,I,A,D,D,
  D,D,D,D,A,D,D,D,D,D,D,D,D,A,R,R,I,A,R,I,I,A)

| ``` "Hello\x20World!\n"


**乘法 (0xc*0xa)**| **输出 (0xc*0xa=0x78)**
---|---

#include "bf.c" BF((c,a),G,R,G,L,B,R,B,D,R,I,R,I,L,L,E,R, R,B,D,L,L,I,R,R,E,L,L,L,D,E,R,R,O)

|  ```
"(78)"

查看 examples.c 获取更多示例。

开始使用

由于预处理器无法区分标准的Brainfuck符号，因此此实现使用以下替代指令名称：

原始指令 | 替代指令 | 描述 ---|---|---

| R | 将磁头向右移动 < | L | 将磁头向左移动

| I | 增加磁头

| D | 减少磁头 . | A | 将磁头作为ASCII输出* O | 将磁头作为十六进制数输出 , | G | 读取输入字符并将其设置为磁头 [ | B | 如果指针处的单元格为0，则跳过匹配的 ] ] | E | 如果指针处的单元格非零，则跳回到匹配的 [

*请注意，符号之间可能会插入额外的空格，因为我所知道的所有预处理器在S(a)b中插入空格时存在分歧，其中#define S(x) x和a和b中有不同的token。

预处理器/编译器

tcc: 使用 tcc -P -E。 tcc 拥有我所知道的最快的预处理器。
gcc: 使用 gcc -P -E -ftrack-macro-expansion=0。如果不能使用 tcc，我建议使用 gcc 而不是 clang，因为它更快，并能提供增量输出。
clang: 使用 clang -P -E -fmacro-backtrace-limit=1。
msvc: 使用 cl /P /C /Zc:preprocessor。你需要 /Zc:preprocessor，否则 msvc 将使用不符合标准的预处理器实现。
mcpp: 使用 mcpp -P -W0。需要 -W0，否则会收到警告 "Replacement text ... of macro ... involved subsequent text"，这是有效的，但 mcpp 会发出警告，因为在“正常”代码中，这可能不是有意的行为。目前还存在一个 mcpp bug，其中添加查找表会导致预处理器出现段错误，因此你需要禁用 BF_SUM 才能使 mcpp 预处理代码。

如果想要获得更精细的执行时间信息，可以对 tcc 进行 tinycc.diff 补丁。这会添加 __TIMER__ 宏，该宏会展开为执行的时间并重置计时器，因此 __TIMER__ FOO __TIMER__ 中的第二个 __TIMER__ 会展开为预处理 FOO 所花费的时间。

这是如何工作的？

如果想了解我是如何编写它的，请查看 tutorial。

与类似项目进行基准测试

测试的程序也存在于 examples.c 中。

程序 | bfcpp | bfi | CPP_COMPLETE | preprocessor_brainfuck ---|---|---|---|--- Hello World | 0.020s | 0.048s | 23s | ~20 分钟 insertion sort 1 | 0.049s | 0.11s | --- | --- insertion sort 2 | 0.09s | 0.22s | --- | --- insertion sort 3 | 0.75s | 1.7s | --- | --- insertion sort 4 | 2.15s | 5.1s | --- | --- sierpinski triangle | 5.32s | 6.6s | --- | --- square numbers from 0 to 10000 | 10.90s | 11.45s | --- | --- quine | 29.62s | 283.3s | --- | ---

鸣谢

感谢 notfoundry 和 Jad Lévesque 帮助我理解预处理器元编程。另外，感谢 bfi 提供了加法查找表的想法，并极大地激励我进一步优化我的实现。

许可

对于所有没有集成许可的文件，适用 LICENSE。