2018-06-14 Brainfuck程序手动解释执行

在 2018 Mossad Challenge 这篇文章里，我们遇到了手动解释一段brainfuck程序的问题，这里给出详细解释。

原代码：

+++++++++++[>++++
+++++++<-]>+[<+>-
]-[>+<-------]>--
-[<+>-][<+>-]>++>
+[>++[-<++++++>]<
<]>[<+>-]>+>++[++
>++[-<+++++>]<<]>
[<+>-]>+>+[>++++[
-<++++>]<<]>[<+>-
]++++++++[>++++++
+++++<-]>+[<+>-]+
++>>+>+[->+++[-<+
++++>]<<]>[<+>-]+
+++++++[>++++++++
<-]>+[<+>-]+++>++
++++>+>+-++<>-+--

第一步

+++++++++++
[>+++++++++++<-]

这是一个乘法器，11*11，得121。此时第一个位置为0，第二个位置为121，指针位于第一个位置。用 加粗加斜 表示指针的位置，那么此时的数据记为：

Position 1	Position 2	Position 3	Position 4
0	121

第二步

>+

再加一个1，得122，也就是 z

Position 1	Position 2	Position 3	Position 4
0	122

第三步

[<+>-]

这是一个swap函数，把当前位置的数交换到左边，后面会多次使用。

Position 1	Position 2	Position 3	Position 4
122	0

第四步

-

这里很关键，明明已经是0了，再减一是多少呢？
验证办法很简单，-.-.-.-. 不断地打印字符，直到发现一个可显示的字符

image.png
推断出，第一次-的结果是255（也可以理解为溢出了）。

Position 1	Position 2	Position 3	Position 4
122	255

第五步

[>+<-------]

这个就相当于一个除法器（除以7），但是比较特别，因为[]这个循环退出的唯一条件是 [ 左边这个位置的值为0。那么如果被除数不能被7整除，就要加上256，继续除，最终结果是 （255+256）/ 7 = 73

Position 1	Position 2	Position 3	Position 4
122	0	73

第六步

>---

Position 1	Position 2	Position 3	Position 4
122	0	70

第七步

[<+>-]，再进行一次swap，

Position 1	Position 2	Position 3	Position 4
122	70	0

再进行一次swap，[<+>-]，没有变化，因为当前位置就是0，所以是一个空循环。

第八步

>++>+

Position 1	Position 2	Position 3	Position 4	Position 5
122	70	0	2	1

第九步

[>++[-<++++++>]<<]

这个双重循环的作用是：把指针向右移动一位，把移动后的位置的值加上2，乘以6，再加到指针左边的位置上（也就是原指针位置），然后指针向左移动两位。

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	2	1	2

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	2	13	0

内层循环到这里结束了。

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	2	13	0

外层循环到这里，没有结束。

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	2	15	0

外层循环，先指针右移，加2。

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	92	0	0

然后乘以6，加到左边去。 15*6+2 = 92。内层循环结束

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	0	92	0	0

再左移两个位置，外层循环结束。
92 即为 \。

第十步

>[<+>-]

swap

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	0	0

第十一步

>+>++[++>++[-<+++++>]<<]

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	2

再来一个二重循环：
先右移加1，再右移加2，

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	2

然后进入外层循环，还没有进入内层循环：

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	4	2

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	14	0

走完第一次内层循环，即2*5+4=14

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	14	0

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	14	0

然后左移两个位置，继续外层循环

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	1	14	0

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	83	0	0

1+2+(14+2)*5 = 83

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	0	83	0	0

循环结束

第十二步

>[<+>-]

swap

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	0	0	0

第十三步

>+>+[>++++[-<++++>]<<]>[<+>-]

又是一个双重循环加swap，结果是：

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	0	0	0

第十四步

++++++++[>+++++++++++<-]>+[<+>-]

加上一个 8*11，再加1，然后swap，结果是：

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	0	0

第十五步

+++

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	0

第十六步

>>+>+[->+++[-<+++++>]<<]>[<+>-]

双重循环，swap，结果是：

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	0	0	0

第十七步

++++++++[>++++++++<-]>+[<+>-]

8*8 + 1 = 65，再swap，结果是

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	65	0	0

第十八步

+++

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	65	3	0

加3

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	65	3	0

第十九步

>++++++

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	65	3	6	0

右移加6

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
122	70	92	83	85	89	3	90	65	3	6	0

第二十步

>+>+-++<>-+--

只有 >+ 是有效的，即右移加1，剩下的就是0。

P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12	P13
122	70	92	83	85	89	3	90	65	3	6	1	0

好，至此已经手动执行完成，最终的输出为：
122, 70, 92, 83, 85, 89, 3, 90, 65, 3, 6, 1