CTF_Brain Fuck语言

Brainfuck是一门晦涩难以捉摸的语言巨星,这个语言是出了名的难以编写,只有 8 个简单命令与 1 个指令指标。Brainfuck 大概只是为了挑战程式设计师,或纯粹娱乐用,没有什麼实际作用。Urban Müller 於 1993 年创造了 Brainfuck,以下是用这门语言编写「Hello World!」的样子:

首先谈到这个语言的定义和运行原理该语言定义在这样一个环境之上:你有一列无限长的小火车,每个车厢里装了一个数字,初始为0。还有一个列车员,初始在最头上那节车厢上。好了,你把你写的BrainFK程序交给列车员,列车员会做如下的事情:从左向右、由上自下一个字符一个字符地读取你的程序

当读到+的时候,将所在车厢里的数字加一
当读到-的时候,将所在的车厢里的数字减一
当读到>的时候,跑到后一个车厢去
当读到<的时候,跑到前一个车厢去
当读到[的时候,如果该车厢里面的数字为0,则跳去执行下一个]之后的程序内容
当读到]的时候,如果该车想里面的数字不为0,则跳去执行上一个[之后的程序内容
当读到.的时候,将所在车厢里面的数字翻译成ASCII字符,显示在你的屏幕上
当读到,的时候,从等待使用者输入一个ASCII字符,转码成数字写进所在车厢里

接下来让我们仔细看这段程序:++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

加上换行整理一下,将其变为:

++++++++++
[

+++++++
++++++++++
+++

<<<<-
]

++.
+.
+++++++..
+++.
++.
<<+++++++++++++++.
.
+++.
------.
--------.
+.
.
'''
'

为了提高可读性,我在此(狂妄地)引入一个宏:让我们用 oX 来代替连续的X个o号吧!(比如 +5 <=> +++++
为了进一步提高可读性,我在此(更加狂妄地)引入一个宏:让我们用 // 在后方形成注释吧!

于是上面的代码变成

+10 //火车头车厢置为10
[

+7 //下一个车厢值加 7
+10 //下一个车厢值加 10
+3 //下一个车厢值加 3
+1 //下一个车厢值加 1
<4 - //前移四个车厢,并将其值减 1
] //此时列车员在第0车厢,如果该车厢内数字不为0,则跳转到前面的[之后
//稍有常识的人都能看出,只要我们的程序执行到这里之后
//前五个车厢的最终值就分别为 0, 70, 100, 30, 10
//此时列车员在第 0 车厢

+2 . //向后一车厢并+2然后输出到屏幕,此时列车员在第1车厢,ASCII(72)='H'

+1 . //向后一车厢并+1然后输出到屏幕,此时列车员在第2车厢,ASCII(101)='e'
+7 .. //列车员不动,将所在(第2)车厢内容继续加7之后输出两次,ASCII(108)='l'
+3 . //列车员不动,将所在(第2)车厢内容继续加3之后输出,ASCII(111)='o'

+2 . //向后一车厢并+2然后输出,此时列车员在第3车厢,ASCII(32)='<空格>'

<2 +15 . //向前两车厢并+15然后输出,此时列车员在第1车厢,ASCII(87)='W'

. //向后一车厢并直接输出,此时列车员在第2车厢,该车厢保留原值111,ASCII(111)='o'
+3 . //不动,+3而后输出,ASCII(114)='r'
-6 . //ASCII(108)='l'
-8 . //ASCII(100)='e'

+1 . //再向后一车厢,此时列车员在第3车厢,+1,ASCII(33)='!'

. //再向后一车厢,此时列车员在第4车厢,直接输出,ASCII(10)='<换行符>'

所以事实上只用一个车厢就能写就这个helloword,但是那样写程序就太长太没有可读性了。所以我们需要在前面用一个循环,来初始化70,100,30,10四个车厢(并且预先用第0个车厢来标记循环次数),这四个车厢分别提供了对大写字母、小写字母、特殊文字符号、特殊控制符号的方便访问。说起来,这个语言简单优雅易学,一旦熟悉之后,如果能借助上面定义的数字宏,写起来方便快捷读起来行云流水,简直就是数组处理界的Regex(知乎为什么不能给字加删除线。。)用这个语言可以有很多趣题,比如说我以前曾经想过一个问题:能不能实现一个动态指针,即列车员读取某车厢的数值,然后向后走该数值所表述数量的车厢,以操作目标车厢的数字。
这个问题后来是这样解决的(摘自我之前的某个博客),下面这段文字里,[X]代表第X节车厢,指针即是列车员:
经过这样的讨论,之前的“是否可以实现指针的动态定位”问题变成了下面的问题:是否可以找到一种方法,让指针查找的时候,每一次移动都能够找回原来的位置。在这里解释一下,比如[4]用来存储另一个地址,或者说[4]中存储着一个自定义的指针,如果*[4] = 8,那么当程序执行到[4]的时候应该将主指针定位到[12] // (12 = 8+4)

我们用BF语言试写一下:我们先初始化主指针到[4]:>>>>接下来我们将指针自增 [4] = 8 次,问题就来了如果我们只要自增八次,我们只要写下>>>>>>>>即可但是我们在编写程序的时候可能并不知道[4]的值,或者说,[4]里面是动态的最早想到的一个办法是指针每自增一次,[4] - 1,但是事实上 [4] - 1 这个语句在BF语言中就是一个 '-' ,但是主指针必须指向[4]。如果我们写 [><-] 那么到最后指针还是停留在[4]上如果我们把过程拆开,就是[4]值先自减,指针自增,然后自减,值自减,然后自增两次,再自减两次,值自减,自增三次,自减三次,值自减,以此类推,直到[4] = 0,然后指针自增8次
如果看到这你还没笑,那你看了下面的代码,一定就笑了:

  • [

<-

<<-

<<<-

<<<<-

<<<<<-

<<<<<<-

<<<<<<<-
] >>>>>>>>
真是笑死了,这和>>>>>>>>没有任何区别,[]循环形同虚设,还浪费资源,到头来编写者还是要在写程序时得知*[4]
上面的代码唯一值得赞扬的就是画面美感
当然如果你写成
-[><->><<->>><<<->>>><<<<->>>>><<<<<->>>>>><<<<<<->>>>>>><<<<<<<-] >>>>>>>>
那就连画面美感也没了

那么到底有没有一种办法可以在指针自增的同时,让其还可以每一次自增之后再找回原来的[4]呢。我脑袋比较笨,在讨论的当天并没有想出一个可行的算法来。想了很多很多办法,包括用五个连续的地址存储一个变量,[n]存储值,[n+1],[n-1],[n+2][n-2]分别存储变量的左右信息等等,但最后都被证明不可行。然而当天清晨,我鬼使神差地梦到了自己用冒泡排序算法解题。醒来一拍大腿,哎呀我C,成了。

我所想到的算法类似冒泡排序中冒泡的过程,如下:
指针每自增一次,[n]与[n-1]的值便交换,然后*[n]自减,重复这一过程直到 [n] = 0
[n]与[n-1]的值交换,可以有两种方法实现,一种是对
[n] 和 *[n-1] 进行异或,还有一种就是利用第三方[m]
鄙人不才,尚未找到在BF中实现抑或的办法,所以决定使用后者。

那么初步的算法如下:
规定当[n]表示一个地址时,[n-1]必须为零,作为临时区域,比如上面的例子,就必须*[4] = 8, *[3] = 0,该指针变量由[3]和[4]构成,长度为2,头地址为[3]。
1 指针指向[n+2],将当前指针位记为[n]
2 [n-2] = [n]; [n] = [n-1]; [n-1] = [0]
3 [n]--
4 如果[n+1] 非零,跳转到1
5 指针自减2

这个算法用BF语言书写如下:
'''
[

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

-<
]<<
'''
当然,如果你嫌行数太多看着难受,也可以写成这样
[>>[<<+>>-]<[>+<-]>-<]<<

接下来把后面的所有内容向前移动两格,填充那个多出来的部分就行了

当然,这段文字提出的方法是有缺陷的:当列车员被正确定位之后,定位列车员所使用的那个车厢就被置0而无法再次使用(变量被破坏)了。
这个缺陷也是有解决方案,可以自己试试看哈哈哈哈

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,348评论 6 491
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,122评论 2 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 156,936评论 0 347
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,427评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,467评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,785评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,931评论 3 406
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,696评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,141评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,483评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,625评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,291评论 4 329
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,892评论 3 312
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,741评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,977评论 1 265
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,324评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,492评论 2 348

推荐阅读更多精彩内容