Turing Complete

Turing Complete

Not enough ratings
图灵完备2.0 alpha指南
By Ineffabilis
本指南介绍2.0版本的关卡引导和过关解法。
   
Award
Favorite
Favorited
Unfavorite
0.概述
本指南开始编写于2025年6月10日,指南的游戏版本为编写时期的2.0版本,该版本为测试版,因此未完全汉化,且存在影响游玩的bug,部分成就在该版本下无法获得。
对于非相关专业的玩家来说,游戏本身的引导可能不够清晰,且跳跃性较大,因此本指南将介绍关卡引导和过关解法,未汉化的关卡标题将保留原文,忽略剧情以及其他不重要的信息。
部分影响游玩的bug的修复方法将在对应关卡列出,不保证一定可以解决问题。如果未能解决问题,请查阅官方网页或等待正式版更新。官方的2.0bug修复网页为:
图灵完备2.0已知问题 [turingcomplete.wiki]
本指南按照个人理解翻译和解释游戏中的概念,与相关专业知识不一定相符。
本指南持续更新。
参考书目:
1. 阎石,王红.数字电子技术基础.6版.北京:高等教育出版社,2016.
2. Patt, Y. N.,Patel, S. J.计算机系统概论(原书第2版).梁阿磊,蒋兴昌,林凌译.北京:机械工业出版社,2007.
3. Patterson, D. A.,Hennessy, J. L.计算机组成与设计:硬件/软件接口(原书第5版).王党辉,康继昌,安建峰译.北京:机械工业出版社,2015.
1.关卡引导
1.1 基础逻辑电路
1.1.1 Crude Awakening

数字逻辑电路中,信号具有开和关两种状态,分别用二进制数码0和1表示,游戏中也用红色和绿色表示。信号通过信号线从输入端传送到输出端。
关卡任务:
将输入端设置为0。

1.1.2 NAND Gate

门是完成逻辑运算的元件。与非门一共有2个输入和1个输出。一般输入用A、B等字母表示,输出用Y1、Y2等字母表示。n个输入一共有2^n种情况,将所有情况下输入和输出的对应关系列表,称为该逻辑运算或该元件的真值表。
与非运算表述为:当两个输入均为1时输出为0,否则输出为1。与非运算的真值表如下:
A
B
Y
0
0
1
1
0
1
0
1
1
1
1
0
关卡任务:
切换输入端,观察输出结果并将结果填入表中。
通关解锁:与非门

1.1.3 NOT Gate

非运算表述为:当输入为1时输出为0,否则输出为1。非运算的真值表如下:
A
Y
0
1
1
0
非运算也称为取反,使用'表示。非运算的表达式为:
Y=A'
由真值表可得,若在非门后再接一个非门,则两个非门对信号的反转相互抵消,信号不变,可用下列表达式表示:
A=(A')'
操作方法
点击屏幕创建信号线,点击右上角的元件将其放置在电路中。
左键选择元件或拖动元件,与元件相连的信号线不会被拖动。左键双击可同时选择元件和相连的信号线。Alt+左键拖动信号线的导通孔,且与导通孔相连的信号线会被拖动。Shift+左键框选元件和导通孔。右键空白区域取消元件的选择,右键删除元件、导通孔和信号线。空格旋转元件。
使用滚轮放大和缩小视角,点击滚轮或使用WASD移动视角。
元件的输入不可依赖于自身的输出,即信号线不可与元件构成回路。(一种情况下例外)
元件的不同输出不可直接连接,否则直接连接的输出中既包含1又包含0时将造成短路。(一种情况下例外)
点击左上角的右箭头图标逐刻运行结果,点击三角形图标按规定速度运行结果,点击左箭头图标倒退一个时间刻,点击正方形图标重置时间刻。

关卡任务:
搭建非门。
通关解锁:非门

1.1.4 AND Gate

与运算表述为:当两个输入均为1时输出为1,否则输出为0。与运算的真值表如下:
A
B
Y
0
0
0
1
0
0
0
1
0
1
1
1
与运算使用·表示。与运算的表达式为:
Y=A·B=AB
由真值表可得,与非门可表示为在与门后再接一个非门,可用下列表达式表示:
Y=(A·B)'
式中括号内的表达式优先运算。
关卡任务:
搭建与门。
通关解锁:与门

1.1.5 NOR Gate

或非运算表述为:当两个输入均为0时输出为1,否则输出为0。或非运算的真值表如下:
A
B
Y
0
0
1
1
0
0
0
1
0
1
1
0
关卡任务:
搭建或非门。
通关解锁:或非门

1.1.6 OR Gate

或运算表述为:当两个输入均为0时输出为0,否则输出为1。或运算的真值表如下:
A
B
Y
0
0
0
1
0
1
0
1
1
1
1
1
或运算使用+表示。或运算的表达式为:
Y=A+B
由真值表可得,或非门可表示为在或门后再接一个非门,可用下列表达式表示:
Y=(A+B)'
摩根律、反演定理
下列两个表达式称为摩根律:
(A·B)'=A'+B',(A+B)'=A'·B'
摩根律揭示了逻辑运算与和或的关系。对一个复杂的表达式重复使用摩根律,则得到下列反演定理:
对于任意一个逻辑表达式Y,若将所有变量取反(即A变为A',B变为B',……),所有常量取反(即1变为0,0变为1),所有或运算变为与运算,与运算变为或运算,保持运算顺序不变,则变换后的表达式的结果为Y'。例如对下列表达式
Y=A+B'·C
应用反演定理,得到
Y'=A'·(B+C')
规定当表达式中与运算和或运算同时出现时优先进行与运算,若想优先进行或运算则应加括号。

关卡任务:
搭建或门。
通关解锁:或门

1.1.7 Always On

常量为不随任何输入改变而改变的量,在表达式中可直接使用0和1表示。
若元件的输入端没有接入任何输出信号,则输入视为0。
关卡任务:
搭建输出恒为1的常量。
通关解锁:高电平、低电平

1.1.8 Second Tick

非门、与门、或门为数字逻辑电路中最基本的逻辑门,所有由真值表表示的逻辑电路均可由这三个逻辑门搭建。
以本关为例,使用基本逻辑门搭建逻辑电路的方法如下:
列出所求逻辑电路的真值表:
A
B
Y
0
0
0
1
0
1
0
1
0
1
1
0
表中每一行的输出均可由输入的非运算和与运算表示为AB,AB',A'B,A'B',例如第二行的输出为1,即用表达式表示为:
Y2=AB'
其他行表示输出为0,即用表达式表示为:
Y1=0,Y3=0,Y4=0
总输出可由所有行的输出的或运算表示为:
Y=Y1+Y2+Y3+Y4=0+AB'+0+0=AB'
关卡任务:
搭建当输入1为1,输入2为0时输出为1,否则输出为0的电路。

1.1.9 XOR Gate

异或运算表述为:当两个输入不同时输出为1,否则输出为0。异或运算的真值表如下:
A
B
Y
0
0
0
1
0
1
0
1
1
1
1
0
异或运算使用⊕表示。异或运算的表达式为:
Y=A⊕B
由1.1.8节可得,异或运算可表示为:
Y=AB'+A'B
关卡任务:
搭建异或门。
通关解锁:异或门

1.1.10 Bigger OR Gate

多输入或运算表述为:当所有输入均为0时输出为0,否则输出为1。
多输入或运算的表达式为:
Y=A+B+C
不难证明,或运算满足交换律和结合律。
关卡任务:
搭建三路或门。
通关解锁:三路或门

1.1.11 Bigger AND Gate

多输入与运算表述为:当所有输入均为1时输出为1,否则输出为0。
多输入与运算的表达式为:
Y=ABC
不难证明,与运算满足交换律和结合律。
关卡任务:
搭建三路与门。
通关解锁:三路与门

1.1.12 XNOR Gate

同或运算表述为:当两个输入相同时输出为1,否则输出为0。同或运算的真值表如下:
A
B
Y
0
0
1
1
0
0
0
1
0
1
1
1
同或运算使用⊙表示。同或运算的表达式为:
Y=A⊙B
由1.1.8节可得,同或运算可表示为:
Y=(A⊕B)'=AB+A'B'
关卡任务:
搭建同或门。
通关解锁:同或门
1.2 算术运算、存储器
1.2.1 Binary Racer

数字逻辑电路中使用二进制表示0和正整数。在二进制数中,每一位仅有0和1两种可能的数字,与信号中的0和1相对应。低位和相邻高位间的进位关系是“逢二进一”,即第一位表示1,第二位表示2,第三位表示4,以此类推,整个编码表示的数字为每一位的1表示的数字之和。
关卡任务:
给出问题中的十进制正整数的二进制编码。

1.2.2 Double Trouble

关卡任务:
完成以下电路:当两个及以上的输入为1时,输出为1,否则输出为0。

1.2.3 Odd Number of Signals

关卡任务:
使用不超过3个元件完成以下电路:当输入为1的个数为奇数时,输出为1,否则输出为0。

1.2.4 Circular Dependency

元件的输入不可依赖于自身的输出,即信号线不可与元件构成回路。违反本规则将造成“循环依赖”报错。
关卡任务:
1.搭建一个产生“循环依赖”的电路。
2.搭建一个产生“循环依赖”的电路,且该循环至少包含2个元件。

1.2.5 Counting Signals

关卡任务:
统计输入为1的个数,转换成二进制数后输出。输出端靠上的引脚为低位。

1.2.6 Half Adder

不考虑来自低位的进位,计算两个1位二进制数相加的电路称为半加器,SUM为该位的和,CARRY为向高位的进位。
关卡任务:
搭建半加器。

1.2.7 Delated Lines

延迟线是在接收到输入后延迟1刻输出的元件,初始输出值为0。
关卡任务:
使用延迟线将输入延迟2刻后输出。
通关解锁:延迟线

1.2.8 Double the Number

将n个1位信号线合并在一起即可得到n位信号线,n位信号线上传输的信号使用二进制数表示。信号线的位数取决于元件输出的位数。
若元件输入信号的位数大于元件可处理的输入位数,则超出的部分将舍弃。若元件输入信号的位数小于元件可处理的输入位数,则不足的部分将视为0。
n位集线器可将n个1位信号线合并成n位信号线,n位分线器可将n位信号线拆分成n个1位信号线。
关卡任务:
将输入的数值翻倍后输出。
通关解锁:2位分线器、4位分线器、8位分线器、2位集线器、4位集线器、8位集线器

1.2.9 Full Adder

考虑来自低位的进位,计算两个1位二进制数相加的电路称为全加器,SUM为该位的和,CARRY为向高位的进位。
关卡任务:
搭建全加器。
通关解锁:全加器

1.2.10 Odd Ticks

延迟线允许与信号线构成回路,因为延迟线在接收到输入后延迟1刻输出,所以构成回路时延迟线的输入依赖于自身上一刻的输出,因此不会造成“循环依赖”。允许构成回路的输入端口为橙色。
关卡任务:
在时间刻为奇数时输出1,在时间刻为偶数时输出0。初始时间刻为0。

1.2.11 Bit Switch

开关是由输入A控制输入B是否通过的元件,用于控制的输入端在元件的下方。当输入A为1时,开关导通,输入B通过开关正常输出。当输入A为0时,开关截止,不输出任意信号。不输出任意信号的输出端口为灰色,允许与其他输出端口直接连接,只要控制开关使直接连接的非灰色输出端口不超过1个即可。
8位开关使用1位输入同时控制8位信号线的导通。
n位元件存放于右上角WORD一栏中,默认为8位。左键点击左上角更改位大小的按钮可更改已放置的n位元件的位数,右键点击可更改位数的默认值。
关卡任务:
使用2个开关和2个非门搭建异或门。
通关解锁:开关、8位开关

1.2.12 Bit Inverter

关卡任务:
当反转信号为1时反转输入信号,否则输入信号保持不变。

1.2.13 Byte NAND

两个n位信号的按位运算表示为对每一位分别进行该运算。
关卡任务:
对两个8位输入信号进行按位与非运算。
通关解锁:8位与非门

1.2.14 Byte NOT

关卡任务:
对两个8位输入信号进行按位非运算。
通关解锁:8位非门

1.2.15 Adding Bytes

关卡任务:
对两个8位输入信号进行加法运算。
通关解锁:8位加法器

1.2.16 Negative Numbers

数字逻辑电路中使用补码表示负整数。采用补码可使负数的加法运算与正数统一,从而实现减法运算。
原码、反码和补码
在二进制数的前面增加一个符号位,用0表示这个数是正数,用1表示这个数是负数,这种形式的数称为原码。为说明反码和补码的概念,以下用4位十进制数来举例,其中除1000为普通的十进制数以外,第4位为符号位。
例:计算693-478。
为避免计算退位减法,可以使用以下方法计算:
693-478 =693-(999-521) =693-999+521 =693+521+1-1000
由此可将减法运算转换成加法运算。式中521为478每一位用9减去该位后的结果,添加符号位后变为1521,称为-478的反码,1521+1=1522称为-478的补码。规定0和正数的反码、补码和原码相同。使用补码计算上式的结果如下:
693-478 =693+1522 =215
式中符号位的溢出忽略不计。不难证明,对补码再做一次求补码的运算即可得到原码。
对于二进制负数来说,求反码的运算变为对每一位用1减去该位,即对每一位取反,求补码的运算同样为对反码加1。
若8位二进制码的最高位不表示为符号位,则称该编码为无符号数,可表示范围为0~255。若8位二进制码的最高位表示为符号位,则称该编码为有符号数。
对于8位二进制补码10000000,它的补码仍为10000000。规定该编码对应的数为-128,因此8位有符号数可表示范围为-128~127。

关卡任务:
给出问题中的十进制整数的二进制补码编码。

1.2.17 Multiplexer

n位数据选择器由两个n位输入端A和B、一个1位输入端S构成,当S为0时输出A,否则输出B。
关卡任务:
搭建数据选择器。
通关解锁:8位数据选择器

1.2.18 Signed Negator

n位取反器输入n位有符号数,输出该数字的相反数。
由于8位有符号数可表示范围为-128~127,对-128取相反数会导致正向溢出使结果变为-128。
关卡任务:
搭建取反器。
通关解锁:8位取反器

1.2.19 The bus

关卡任务:
使用4个开关和2个非门完成以下电路:从两个8位输入端中选择一个、两个8位输出端中选择一个,将被选择的输入端的信号传递到被选择的输出端。当输入端FROM为0时选择第一个输入端,为1时选择第二个输入端,当输入端TO为0时选择第一个输出端,为1时选择第二个输出端。

1.2.20 Saving Gracefully

关卡任务:
搭建寄存器:当第一个输入端为1时,将第二个输入端的值保存到延迟线中,当第一个输入端为0时,保持延迟线存储的值不变。始终输出延迟线存储的值。
通关解锁:寄存器

1.2.21 Saving Bytes

关卡任务:
完成以下电路:当输入端1为1时,将8位输入端的值保存到寄存器中,当输入端1为0时,保持寄存器存储的值不变。当输入端0为1时,将寄存器存储的值输出到8为输出端中,当输入端0为0时,不输出任何信号。
通关解锁:64位寄存器、8位延迟线

1.2.22 1 Bit Decoder

n位译码器由一个n位输入端A、2^n个1位输出端构成,当输入一个二进制无符号数N时,从上到下第N+1个输出端为1,其余输出端为0。
关卡任务:
搭建1位译码器。
通关解锁:1位译码器

1.2.23 2 Bit Decoder

关卡任务:
搭建2位译码器。
通关解锁:2位译码器

1.2.24 3 Bit Decoder

关卡任务:
搭建3位译码器。
通关解锁:3位译码器

1.2.25 Little Box

关卡任务:
完成以下电路:当输入端LOAD为1时,将8位输入端的值保存到寄存器中,当输入端LOAD为0时,保持寄存器存储的值不变。当输入端SAVE为1时,将寄存器存储的值输出到8为输出端中,当输入端SAVE为0时,不输出任何信号。输入的值存储的寄存器取决于其余两个1位输入端。
通关解锁:随机存储器(RAM)

1.2.26 Counter

n位计数器由一个n位输入端A、一个1位输入端S构成,当S为0时,计数器内存储的数值在下一时间刻加1,当S为1时,计数器内存储的数值在下一时间刻设置为输入端A输入的二进制无符号数。计数器始终输出存储的值。
关卡任务:
搭建8位计数器。
通关解锁:8位计数器
1.3 处理器架构
本章开始搭建Overture处理器。

1.3.1 Arithmetic Logic Unit (ALU) 1

Overture处理器中,由一个8位的输入信号执行各种操作,称为指令。
关卡任务:
完成Overture处理器中的逻辑运算部分:根据指令,将输入信号A和B执行指定的运算并输出。
指令
运算
0
与非
1
2
3
或非
通关解锁:8位或门、8位与门、8位或非门

1.3.2 Registers

本关输入端和输出端各添加了一个控制端,当控制端的输入为1时启用,否则不输入、输出任何信号。
关卡任务:
完成Overture处理器中的数据迁移部分:根据指令,将A中的数据迁移至B中。A由指令的第4~6位决定,B由指令的第1~3位决定。表中Reg0~Reg5为8位寄存器。
指令
A
B
0
Reg0
Reg0
1
Reg1
Reg1
2
Reg2
Reg2
3
Reg3
Reg3
4
Reg4
Reg4
5
Reg5
Reg5
6
输入
输出

1.3.3 Arithmetic Logic Unit (ALU) 2

关卡任务:
完成Overture处理器中的逻辑运算部分:根据指令,将输入信号A和B执行指定的运算并输出。
指令
运算
0
与非
1
2
3
或非
4
相加
5
相减(A为被减数)

1.3.4 Component Factory

元件工坊内可以将特定的电路集成到元件内。放置右上角IO一栏中的输入引脚和输出引脚为自定义元件添加端口,调整输入、输出引脚和内部元件在背景网格的位置以改变自定义元件的形状和占据空间,放置IO一栏中的存储器探针和线路探针在自定义元件表面显示监测对象的数值,点击存储器探针上的“链接”按钮以选择要检测的元件。点击左上角的“切换电路图”新建或切换自定义元件。
自定义元件内可以放置其他自定义元件,但不能放置自身,也不能使多个自定义元件相互嵌套。
关卡任务:


1.3.5 Instruction Decoder

关卡任务:
完成Overture处理器中的解码指令部分:根据指令的第7~8位,向指定的输出端输出1。
指令
输出端
0
直接数(Immediate)
1
逻辑运算(ALU)
2
数据迁移(Move)
3
条件跳转(Condition)

1.3.6 ALU

关卡任务:
在关卡1.3.2的基础上,将已完成的逻辑运算部分、数据迁移部分、解码指令部分组合在一起,即根据解码部分的结果,执行对应部分的运算。对于逻辑运算,读取Reg1和Reg2中的数据并将运算后的结果存储到Reg3中。

1.3.7 Conditions

关卡任务:
完成Overture处理器中的条件跳转部分:根据指令,当输入信号满足指定的条件时输出1,否则输出0。
指令
条件
0
始终不满足
1
始终满足
2
等于0
3
不等于0
4
小于0
5
大于等于0
6
小于等于0
7
大于0

1.3.8 Immediate Values

关卡任务:
在关卡1.3.6的基础上,完成Overture处理器中的直接数部分:将指令的第1~6位存储到Reg0中。

1.3.9 Program

本关使用RAM代替输入端口输入指令。RAM以1字节(8位)为单位存储数据,必须添加加载端口、存储端口以读取、存储数据。加载端口的左侧第一个引脚为控制端,当控制端的输入为1时启用,否则不输出任何信号。左侧第二个引脚为地址端,以字节为单位读取该地址的数据。右侧第一个引脚为输出端,输出读取的数据。
关卡任务:
将搭建好的Overture处理器的输入端口连接RAM的输出端,将计数器的输出端口连接RAM的地址端,读取RAM中的指令并执行。
通关解锁:加载端口

1.3.10 Turing Complete

关卡任务:
在关卡1.3.7和1.3.9的基础上,完成Overture处理器中的条件跳转部分:读取Reg3中的数据进行条件跳转的判断,当判断结果为1时,读取Reg0中的数据并输入到计数器中使其重置为该数值。
1.4 编程
本章使用Overture处理器进行基本编程操作。所有任务均应通过Overture处理器完成。

1.4.1 Add 5

关卡任务:
点击RAM的编辑按钮,编辑RAM存储的机器指令,使输入值加5后输出。

1.4.2 Add 5 again

汇编语言
使用汇编语言可避免繁琐的编辑机器指令的操作。在编辑汇编代码之前,应首先编辑汇编代码和机器指令的对应关系,位置在汇编代码编辑器左侧的Assembly language中。
汇编语言位于[instructions]条目下,每条指令由以下三部分构成,每个部分各占一行。第一行为汇编代码语句,第二行为机器指令,第三行为注释,可留空。除第三行外,任何位置的分号之后的内容均视为注释。以下列指令为例:
mov %a(register), %b(register) 10aaabbb Move one byte %b to register %a.
%a和%b为占位符,在编写的汇编语句中表示此处应填入操作符。操作符表示填入机器指令的数值。机器指令中的a和b必须与汇编代码语句中的占位符相对应。“register”为操作符的种类,表示此处应填入的操作符的种类。操作符一共有三种:“immediate”、“label”、自定义,自定义操作符可在[fields]条目下定义,例如
register r0 000 r1 001 r2 010 r3 011 r4 100 r5 101 in 110 out 110
编写汇编代码语句时,必须将占位符用对应的操作符代替,其余除空格以外的字符一字不差地编写出来。在上述规则下,一条符合语法的汇编代码语句和对应的机器指令如下:
mov in, r2 10110010
除上述格式的语句外,汇编代码还支持下列格式的语句:
1.标签,格式为以字母开头的标签名称后接冒号,例如
label1:
标签可使用在操作符为“label”的语句中,标签的值为标签的下一条指令在RAM中的地址。使用标签可方便编写跳转指令。
2.常量,格式为const+以字母开头的常量名称+等于号+数值,例如
const x = 2
语句中的常量为定义的值。
3.直接数值,格式为
<U8> 123
表示在此处的机器指令中直接插入一个8位无符号数123。
4.包含,格式为
include ../std_lib
表示此处复制上一级目录中的std_lib.asm整个文件。若需要跳转到被包含的文件中的标签处,则定义标签时添加前缀“pub”,在使用标签时在前面添加文件名和“.”,例如
pub print: jmp std_lib.print
使用此功能可创建一个可以从任何层级调用的函数库,只需将库文件放在层级上方的文件夹中,并显示与每个函数对应的标签。
5.注释,任何位置的分号之后的内容均视为注释。

关卡任务:
编辑汇编代码,使输入值加5后输出。

1.4.3 Calibrating Lasor Cannons

关卡任务:
输入r,计算2×π×r并输出,式中π取3。

1.4.4 Conditional Jumps

关卡任务:
读取输入并记录读取的次数,当输入为37时输出读取的次数。

1.4.5 Storage cracker

关卡任务:
猜测给定数值并输出,如果输出值比待猜测数值大则输入为1,如果输出值比待猜测数值小则输入为0。

1.4.6 Masking Time

关卡任务:
输入a,计算a除以4得到的余数并输出,整个过程用时不超过8个时间刻。

1.4.7 The Maze

关卡任务:
控制小机器人走到迷宫左上角的门。输出0使小机器人原地左转,输出1使小机器人前进1格,输出2使小机器人原地右转。当小机器人面前为空地时输入为0,当小机器人面前为墙壁时输入为1。
解决该问题的算法如下:
向前走一步 左转 while 面前是墙: 右转 返回第一步
1.5 处理器架构 2
本章及之后章节的标题均有误,此处保留原文,游戏修改后更新。本章仅为搭建Symphony处理器制作必要元件。

1.5.1 XOR

关卡任务:
编辑汇编代码,读取两次输入并将两个值按位异或。

1.5.2 Byte Constant

关卡任务:
始终输出数字164。
通关解锁:64位常量

1.5.3 Byte XOR

关卡任务:
对两个8位输入信号进行按位异或运算。
通关解锁:8位异或门、8位同或门

1.5.4 Equality

判等器由两个输入端A和B、一个1位输出端构成,当A和B相同时输出1,否则输出0。
关卡任务:
搭建判等器。
通关解锁:8位判等器

1.5.5 Hex Racer

十六进制数的每一位有十六个不同的数码,分别用0~9、A(10)、B(11)、C(12)、D(13)、E(14)、F(15)表示。
由于4位二进制数恰好有16个状态,而把这4位二进制数看作一个整体时,它的进位输出又正好是逢十六进一,所以只要从低位到高位每4位二进制数分为一组并代之以等值的十六进制数,即可得到对应的十六进制数。同理,十六进制数转换为等值的二进制数时只需将十六进制数的每一位用等值的4位二进制数代替。
关卡任务:
给出问题中的十六进制正整数的二进制编码。

1.5.6 Unsigned Less

无符号小于比较器由两个输入端A和B、一个1位输出端构成,当A和B视为无符号数且A<B时输出1,否则输出0。
关卡任务:
搭建无符号小于比较器。
通关解锁:8位无符号小于比较器

1.5.7 Signed Less

有符号小于比较器由两个输入端A和B、一个1位输出端构成,当A和B视为有符号数且A<B时输出1,否则输出0。
关卡任务:
搭建有符号小于比较器。
通关解锁:8位有符号小于比较器

1.5.8 Shift

左移位器、右移位器、算数右移位器、循环左移位器、循环右移位器均由两个输入端A和B、一个输出端构成,A为被移位的信号,B为移动的位数,视为无符号数。定义低位在右,高位在左。
左/右移位器将A向左/右移动B位,被移出的位舍弃,未被移入的位视为0。
算数右移位器将A除符号位以外的其他位向右移动B位,被移出的位舍弃,未被移入的位取符号位的值。
循环左/右移位器将A向左/右移动B位,被移出的位移动到未被移入的位。
关卡任务:
搭建左移位器。
通关解锁:8位左移位器、8位右移位器、8位算数右移位器、8位循环左移位器、8位循环右移位器

1.5.9 Objective Beauty

游戏使用以下两个指标评价过关解答:整个电路使用的逻辑门数量、整个电路从输入到输出的总延迟数。一条线路上的延迟等于经过的各个元件的延迟之和,从输入到输出的总延迟等于所有线路延迟的最大值。对于编程类关卡,游戏还使用第三个指标评价过关解答:从开始到问题解答完毕的时间刻数。
关卡任务:
搭建自增器:使输入的值加1后输出,且电路的门数量不超过40,总延迟不超过10。
通关解锁:8位自增器
1.6 汇编挑战
本章开始搭建Symphony处理器。

1.6.1 One hot encoding

关卡任务:
使用不超过3个元件搭建3位译码器。
通关解锁:8线分线器、4线分线器、2线分线器、8线集线器、4线集线器、2线集线器、8线并线器、4线并线器、2线并线器
n位k线分线器:将n×k位信号平均分为k个n位信号。
n位k线集线器:将k个[n÷k]位信号合并为k×[n÷k]位信号,式中[x]表示对x向下取整。仅当n为k的正整数倍时输出信号为完整的n位信号。
k线并线器:将k个任意位信号合并,合并后信号的位数等于合并前所有信号的位数之和。

1.6.2 Symphony counter

Bug修复:
如果没有找到修改位数的工具,按照以下操作修复该bug:
1.点击主界面中的选项,打开存档路径中的levels.txt文件。
2.将下列代码粘贴到文件中:
symphony_register_1,true,10000,10000,0,Default
3.重启游戏。
关卡任务:
1.搭建16位计数器:当1位输入端S为0时,计数器内存储的数值在下一时间刻加4,当S为1时,计数器内存储的数值在下一时间刻设置为16位输入端A输入的二进制无符号数。
2.将存储器探针链接到寄存器上。

1.6.3 Instruction decoder

Symphony处理器的指令共32位,编码格式如下:
0MM0OOOO DDDDAAAA 0000BBBB 00000000 0MMIOOOO DDDDAAAA BBBBBBBB BBBBBBBB
各字母的含义如下表:
字母
含义
位置
M
模式(Mode)
第30~31位
O
运算码(Opcode)
第25~28位
I
直接数符号位(Immediate bit)
第29位
D
目的寄存器(Destination register)
第21~24位
A
参数A(Argument A)
第17~20位
B
参数B(Argument B),I=0
直接数(Immediate),I=1
第9~12位,I=0
第1~16位,I=1
关卡任务:
完成Symphony处理器中的解码指令部分:取出指令的各个部分输出到对应的输出端。
通关解锁:静态索引器、可配置静态索引器
静态索引器:对输入信号移位固定位数,正数向右移位,负数向左移位。
可配置静态索引器:对输入信号移位固定位数,输出位数和移位位数由上方蓝色输入端连接的信号线的位数决定。

1.6.4 Comparison flags

比较标志元件由两个输入端A和B和一个3位输出端Y组成,当A和B相等时输出001,当A无符号小于B时输出010,当A有符号小于B时输出100。
关卡任务:
搭建比较标志元件。

1.6.5 Wire Speghetti

Symphony处理器使用2个RAM,其中一个RAM储存机器指令,称为程序RAM,另一个RAM储存16个寄存器的数值,称为寄存器RAM。寄存器RAM中的16个寄存器的名称如下:
0 zr 1 r1 2 r2 3 r3 4 r4 5 r5 6 r6 7 r7 8 r8 9 r9 10 r10 11 r11 12 r12 13 r13 14 sp 15 flags
其中zr寄存器恒为0,忽略所有对该寄存器存储的数值,sp寄存器和flag寄存器功能与其他寄存器相同,留作特殊用途。
存储端口与加载端口类似,存储端口的左侧第一个引脚为控制端,当控制端的输入为1时启用,否则不输出任何信号。左侧第二个引脚为地址端,以字节为单位读取该地址的数据。左侧第三个引脚为数据端,输入存储的数据。
Bug修复:
本关及之后的所有关卡均可能对程序RAM和寄存器RAM识别错误,具体表现为异常报错和程序RAM界面不显示机器指令的数值。按照以下操作修复该bug(需按顺序执行):
1.按照1.6.2节的Bug修复部分修复不能找到修改位数的工具的bug。
2.删除程序RAM和寄存器RAM。
3.在沙盒模式中将位数设置为16位,放置一个16位的RAM(RAM的位数不显示)并复制到关卡中作为寄存器RAM。
4.在沙盒模式中将位数设置为32位,放置一个32位的RAM并复制到关卡中作为程序RAM。
关卡任务:
1.放置程序RAM,添加一个32位加载端口,在元件信息栏左侧设置大小为65536字节,在右侧设置初始数据集为“汇编程序”(Assembler)。
2.放置寄存器RAM,按顺序添加一个16位存储端口、两个16位加载端口。
3.将寄存器RAM中的数值链接到程序RAM中:点击程序RAM的编辑按钮,点击右侧Registers后的锁,点击“from register file”,点击寄存器RAM。
4.完成Symphony处理器的与非指令。
机器指令
指令说明
00100000 aaaabbbb 0000cccc 00000000
将寄存器%b和寄存器%c存储的值进行与非运算后存储到寄存器%a中
通关解锁:存储端口

1.6.6 Multiply

关卡任务:
搭建乘法器:将输入的两个无符号数相乘后输出,溢出的数值舍去。
通关解锁:8位乘法器

1.6.7 IO

关卡任务:
完成Symphony处理器中的输入输出部分。
机器指令
指令说明
00000000 00000000 00000000 00000000
空指令(什么都不做)
00000001 aaaa0000 00000000 00000000
读取输入的数值并存储到寄存器%a中
00000010 00000000 0000aaaa 00000000
读取寄存器%a的数值并输出

1.6.8 Symphony ALU

关卡任务:
完成Symphony处理器中的逻辑运算部分:根据指令,将输入信号A和B执行指定的运算并输出。
指令
运算
0
与非
1
2
3
或非
4
相加
5
相减(A为被减数)
6
异或
7
左移位(A为被移位信号)
8
右移位(A为被移位信号)
9
比较(使用比较标志元件)
10
相乘

1.6.9 Integrating ALU

Bug修复:
本关的测试中相乘运算的返回值恒为0,按照以下操作修复该bug:
在完成测试的关卡删除逻辑运算部分的相乘功能。
关卡任务:
将逻辑运算部分整合到Symphony处理器中。
机器指令
指令说明
0010dddd aaaabbbb 0000cccc 00000000
将寄存器%b和寄存器%c存储的值进行指定的运算后存储到寄存器%a中,运算由%d指定

1.6.10 Immediates

关卡任务:
完成Symphony处理器中的直接数部分:若直接数符号位为1,将直接数代替参数B表示的寄存器的值进行运算。

1.6.11 Condition match

关卡任务:
完成Symphony处理器中的条件配对部分:该部分由一个3位输入A、一个4位输入B和一个1位输出构成,逐位比较A和B的前三位,若任意一对都为1,则比较结果为1,否则比较结果为0。若B的第四位为0,输出以上比较结果,若B的第四位为1,反转以上比较结果并输出。

1.6.12 Jumps

关卡任务:
完成Symphony处理器中的条件跳转部分。
机器指令
指令说明
0100dddd 0000aaaa 0000bbbb 00000000
将寄存器%a存储的值和%d进行条件配对,若结果为1,读取寄存器%b存储的值并输入到计数器中使其重置为该数值

1.6.13 RAM

Symphony处理器使用程序RAM作为内存。
关卡任务:
1.修改程序RAM的端口,按顺序添加一个16位存储端口、一个8位存储端口、一个32位加载端口、一个16位加载端口、一个8位加载端口,仍使用32位加载端口读取机器指令。
2.完成Symphony处理器中的数据读写部分。
机器指令
指令说明
011000d0 aaaa0000 0000bbbb 00000000
读取寄存器%b存储的值作为地址,将RAM中该地址位的值存储到%a中
011000d1 0000aaaa 0000bbbb 00000000
读取寄存器%b存储的值作为地址,将%a存储到RAM中该地址位
表中%d为0时使用8位端口,%d为1时使用16位端口。

1.6.14 SSD

Symphony处理器使用SSD作为外存。SSD和RAM在存储功能上相同,不同之处是SSD在沙盒模式中复位时不会清除数据。
关卡任务:
1.放置SSD,在元件信息栏左侧设置大小为65536字节,按顺序添加一个16位存储端口、一个8位存储端口、一个16位加载端口、一个8位加载端口。
2.完成Symphony处理器中的数据读写部分。
机器指令
指令说明
011001d0 aaaa0000 0000bbbb 00000000
读取寄存器%b存储的值作为地址,将SSD中该地址位的值存储到%a中
011001d1 0000aaaa 0000bbbb 00000000
读取寄存器%b存储的值作为地址,将%a存储到SSD中该地址位
表中%d为0时使用8位端口,%d为1时使用16位端口。
通关解锁:固态驱动器(SSD)

1.6.15 IO Devices

本关添加三个外接输入、输出设备:系统时间、控制台、键盘。
系统时间元件的输入端输入为1时,输出64位当前的时间戳(单位为纳秒),输入为0时,不输出任何信号。
控制台元件可链接到RAM或SSD,将该RAM或SSD存储的值按照ASCII编码转换后显示。输入端输入的值设置控制台的偏移量。
键盘元件的按键为绿时,读取当前键盘的状态。若键盘按下,则Key down输出1,Key Value输出按下的键位值。键盘元件保存所有输出端待输出的数值,直到输入端Read next输入为1时输出。
在读取系统时间时,由于一次只能读取系统时间的16位,读取整个系统时间需要4个时间刻,因此读取系统时间的第1~2字节时应将读取到的64位时间值存储在64位寄存器中,之后读取系统时间的其他位时读取该寄存器的值。
在读取键盘数值时,存储数值的第1~8位为Key Value,第9~15位为0,第16位为Key down。
关卡任务:
1.放置系统时间、控制台、键盘,将控制台链接到程序RAM。
2.完成Symphony处理器中的输入输出部分。
机器指令
指令说明
00000011 00000000 0000aaaa 00000000
读取寄存器%a的数值并输出到控制台偏移量中,且保持偏移量的值不变
00000100 aaaa0000 00000000 00000000
读取系统时间数值的第1~2字节并存储到寄存器%a中
00000101 aaaa0000 00000000 00000000
读取系统时间数值的第3~4字节并存储到寄存器%a中
00000110 aaaa0000 00000000 00000000
读取系统时间数值的第5~6字节并存储到寄存器%a中
00000111 aaaa0000 00000000 00000000
读取系统时间数值的第7~8字节并存储到寄存器%a中
00001000 aaaa0000 00000000 00000000
读取计数器的数值并存储到寄存器%a中
00001001 aaaa0000 00000000 00000000
读取键盘的数值并存储到寄存器%a中
注意:由于输出到控制台偏移量的值需要经过一个寄存器,所以控制台接收到该数值的时刻要比指令发出的时刻晚1个时间刻。
通关解锁:系统时间、控制台、键盘

1.6.16 Instruction aliases

Bug修复:
打开游戏的本地文件,按照下列网址的方法修复。
图灵完备2.0已知问题 [turingcomplete.wiki]
关卡任务:
在汇编语言中添加以下指令:
汇编指令
指令说明
mov %a(register), %b(register)
读取寄存器%b的数值并存储到寄存器%a中
neg %a(register), %b(register)
读取寄存器%b的数值,计算相反数并存储到寄存器%a中
not %a(register), %b(register)
读取寄存器%b的数值,按位取反并存储到寄存器%a中
1.7 汇编挑战
本章使用Symphony处理器进行基本编程操作。所有任务均应通过Symphony处理器完成。

1.7.1 Stack

栈是一种特殊的线性存储结构,栈中存储的数据可类比为竖着摆放的一摞书。栈中第一个元素进入的位置称为栈底,允许进行插入和进行删除操作的位置称为栈顶。在栈顶位置插入元素的操作叫做入栈,删除栈顶元素的操作叫做出栈,类似于在一摞书的最上面放书和取书的操作。
Bug修复:
本关及关卡Functions给出的汇编语言中的机器指令存在错误,按照以下操作修复该bug:
1.打开游戏的本地文件,打开campaign\symphony_10_stack\meta.txt文件。对于关卡Functions,对应的文件夹为symphony_11_functions。
2.删除文件中的以下代码:
immutable_spec = true
3.重启游戏。
4.手动修改机器指令。仅部分指令的前三位有错误。关卡Functions中新增的汇编语言应按照注释修改。
关卡任务:
搭建一个栈,当输入不为0时将输入的数值入栈,当输入为0时出栈并输出出栈的元素。

1.7.2 Functions

编程中通常使用函数来重复使用一段代码。当重复使用这段代码时,应跳转到函数的开头,这个操作称为调用(call),代码使用完毕之后应在函数的末尾跳转回来,这个操作称为返回(return)。
为记录调用函数的语句所在位置以便返回时找到该位置,应在调用函数时将该地址入栈,在返回函数时出栈。
为使函数返回时寄存器的值与调用函数时的值保持不变,防止函数临时使用寄存器时被破坏,应在函数开头将需要保持不变的寄存器的值入栈,在函数结尾出栈到对应的寄存器。
关卡任务:
阅读并运行汇编代码,掌握函数的编写。

1.7.3 Random number generator

关卡任务:
输入种子,按照下列算法输出由该种子生成的随机数。
temp1 = seed xor (seed lsr 7) temp2 = temp1 xor (temp1 lsl 9) result = temp2 xor (temp2 lsr 8)
代码中seed为输入值,result为输出值。

1.7.4 AI Showdown

关卡任务:
桌面上有12张牌,每个玩家轮流拿起1~3张牌,拿起最后一张牌的玩家失败。编写先手玩家获胜的程序。输入为当前桌面上的卡片数量,输出1、2、3拿起该数量的牌。

1.7.5 Divide

关卡任务:
编写带余除法的程序。前2个时间刻的输入依次为被除数和除数,依次输出商和余数。
通关解锁:8位除法器、8位取模器

1.7.6 Tower of Alloy

汉诺塔问题的规则如下:
有三根柱子,开始时所有圆盘都按照从大到小的顺序叠放在其中一根柱子上,每次只能移动一个圆盘,且只能移动最顶端的圆盘,任何时刻都不能将大圆盘放在小圆盘上面,目标是将所有圆盘从一根柱子按照原有顺序移动到另一根柱子。
关卡任务:
编写程序解决汉诺塔问题。前4个时间刻的输入依次为编号最大的圆盘的编号(disk_nr)、圆盘初始位置的编号(source)、圆盘移动的目标位置的编号(dest)、既不是初始位置也不是目标位置的空闲位置的编号(spare)。输出0、1、2移动到该位置,输出5控制磁铁拿起、放下圆盘。
解决汉诺塔问题的算法如下:
func move(disk_nr, source, dest, spare): if disk_nr is 0: 将圆盘从source移动到dest else: move(disk_nr - 1, source, spare, dest) 将圆盘从source移动到dest move(disk_nr - 1, spare, dest, source)

1.7.7 Delicious Order

关卡任务:
从输入读取16个无符号数,对这16个数从小到大排序后依次输出。

1.7.8 Planet Names

关卡任务:
从输入读取文本的ASCII编码,该文本由若干个单词组成,单词之间用空格(ASCII码为32)隔开。对文本中每个单词的首字母转换为对应的大写格式后输出。
1.8 (无标题)
1.8.1 Calibrating Laser Cannons 2

关卡任务:
从输入读取文本格式的数学表达式的逆波兰表示法[baike.baidu.com],输出该数学表达式的结果。

1.8.2 Pipeline timer

本关开始对Symphony处理器进行优化,从本关开始,之后的所有关卡总延迟不超过60。
关卡任务:
搭建一个计时器,当输入为1时输出在接下来的两个时间刻输出1,之后输出0,当输出为1时忽略输入。

1.8.3 Symphony FAST ALU

关卡任务:
删除ALU元件中的乘法器,优化该元件使总延迟不超过60。

1.8.4 Pipelined counting

关卡任务:
在Symphony计数器的基础上添加一个hold输入引脚,当hold输入为1时,停止计数器加4的操作。新建一个电路图以添加hold引脚。

1.8.5 Pipeline

本关介绍Symphony处理器的第一个优化:流水线。流水线处理器将一条指令分成三个操作,每个操作由处理器的一部分来执行,用时1个时间刻,因此整条指令的执行用时3个时间刻。使用流水线处理器可将每个时间刻的总延迟降低,然而流水线处理器运行整个程序所花费的时间刻基本不变,这是因为流水线处理器运行整个程序的过程中,每个部分每个时间刻执行的操作如下:
时间刻
第一部分
第二部分
第三部分
0
指令1操作1
1
指令2操作1
指令1操作2
2
指令3操作1
指令2操作2
指令1操作3
3
指令4操作1
指令3操作2
指令2操作3
在Symphony处理器中,各指令被分成的三个操作如下。
操作1:读取指令并向寄存器INSTR中存储,向寄存器COUNTER 1中存储Symphony计数器的值。
操作2:解码指令,向寄存器MODE、OPCODE、DEST中存储解码后的指令,向寄存器COUNTER 2中存储寄存器COUNTER 1的值,读取寄存器RAM中寄存器A和B的值并存储到寄存器ARG_A、ARG_B中,若为直接数模式则将直接数存储到寄存器ARG_B中。
操作3:根据解码后的指令,使用寄存器ARG_A、ARG_B、COUNTER 2等元件中的值完成该指令的剩余操作。
注意:
1.当一条指令的目的寄存器和下一条指令读取数值的寄存器相同时,将在某一时间刻发生同时向该寄存器存储数值和读取数值的情况,此时由于RAM在同一时间刻的工作逻辑是先读取后存储,指令的运行将出错。因此应添加电路,使得当发生这种情况时,直接将上一条指令待存储的值输出给下一条指令。
2.在接收到跳转指令之后,处理器必须停止工作,直到跳转至指定的指令位置。因此应添加电路,使得当接收到跳转指令时,在接下来的两个时间刻停止Symphony计数器的计数,并向寄存器INSTR存储空指令(0)。
关卡任务:
在Symphony处理器的基础上添加流水线功能。

1.8.6 Reg use check

关卡任务:
本关的32位输入端输入的值为Symphony机器指令,4位输入端输入的值为寄存器编号。完成以下电路(优先级依次降低):
1.当寄存器编号为0时,输出0。
2.当机器指令的参数A或参数B与寄存器编号相同时,输出1。若直接数符号位为1则忽略参数B。

1.8.7 Data hazard

关卡任务:
检测两条机器指令能否同时执行,若能同时执行则输出1,否则输出0。当满足以下任意一个条件时则不能同时执行:
1.第一条指令是条件跳转指令。
2.第二条指令使用第一条指令的目标寄存器。
3.第二条指令不是逻辑运算指令。

1.8.8 Counter increment

关卡任务:
本关的16位输入端输入的值为计数器的值,两个1位输入端输入的值控制下一时刻计数器的值。当第一个1位输入端为0时,输出计数器的值。当第一个1位输入端为1,第二个1位输入端为0时,输出计数器的值+4。当两个1位输入端均为1时,输出计数器的值+8。

1.8.9 Superscalar counting

关卡任务:
在Symphony计数器的基础上添加两个输入引脚,按照关卡1.8.8中的要求使用新增的两个输入引脚控制下一时刻计数器的值。

1.8.10 Superscalar

本关介绍Symphony处理器的第二个优化:超标量。超标量Symphony处理器根据指令的类型决定下一时间刻执行0条、1条或2条指令。在Symphony处理器中,首先读取两条指令,若第一条指令是条件跳转指令,则接下来的两个时间刻执行0条指令,即计数器的值不变;若第一条指令不是条件跳转指令且两条指令满足关卡1.8.7中的条件,则接下来的两个时间刻执行1条指令,即计数器的值+4;否则执行2条指令,即计数器的值+8。
关卡任务:
在Symphony处理器的基础上按照以下步骤添加超标量功能。
1.将输出机器指令的加载端口设置为64位,并将输出拆分为两条指令。
2.使用关卡1.8.7和1.8.9制作的电路完成满足上述要求的计数器。
3.添加第二个逻辑运算元件,为寄存器RAM再添加一个16位存储端口、两个16位加载端口并连线。端口的放置顺序仍应保持存储端口在下、加载端口在上的原则。
4.修改判断一条指令的目的寄存器和下一条指令读取数值的寄存器是否相同的功能,在本关卡中需一次性判断上两条指令的目的寄存器和下两条指令读取数值的寄存器是否相同,并根据具体情况将上两条指令待存储的值输出给下两条指令。

1.8.11 Speculative execution

本关介绍Symphony处理器的第三个优化:推测。推测是一种允许处理器“猜测”指令结果的方法。在Symphony处理器中,我们始终猜测条件跳转指令不会发生跳转,因此读取到条件跳转指令后继续读取下一条指令。如果猜测成功,则处理器正常工作,节省2个时间刻;如果猜测失败,则处理器的第三部分停止工作2个时间刻,丢失这2个时间刻的结果。
关卡任务:
在Symphony处理器的基础上按照以下步骤添加推测功能。
1.删除读取到条件跳转指令时停止计数和停止读取指令的功能。
2.当重置计数器的信号为1时,停止第三部分的工作2个时间刻,即不存储、输出任何数据。

1.8.12 Register renamer

本关及之后的关卡均未完成,最后4个未连接到主线的关卡同样未完成,而不是隐藏关卡。
2.过关解法
除关卡要求外,所有解法均不考虑优化,以简明直观为主要目的。
2.1 基础逻辑电路
2.1.1 Crude Awakening



2.1.2 NAND Gate



2.1.3 NOT Gate



2.1.4 AND Gate



2.1.5 NOR Gate



2.1.6 OR Gate



2.1.7 Always On



2.1.8 Second Tick



2.1.9 XOR Gate



2.1.10 Bigger OR Gate



2.1.11 Bigger AND Gate



2.1.12 XNOR Gate


2.2 算术运算、存储器
2.2.1 Binary Racer



2.2.2 Double Trouble



2.2.3 Odd Number of Signals



2.2.4 Circular Dependency



2.2.5 Counting Signals

第1位输出1的条件是有奇数个输入为1,即2.2.3节的解法,第2位输出1的条件是有2或3个输入为1,即2.2.2节的解法中去掉有4个输入为1的情况,第3位输出1的条件是有4个输入为1。


2.2.6 Half Adder



2.2.7 Delayed Lines



2.2.8 Double the Number



2.2.9 Full Adder



2.2.10 Odd Ticks



2.2.11 Bit Switch



2.2.12 Bit Inverter



2.2.13 Byte NAND



2.2.14 Byte NOT



2.2.15 Adding Bytes



2.2.16 Negative Numbers



2.2.17 Multiplexer



2.2.18 Signed Negator



2.2.19 The bus



2.2.20 Saving Gracefully



2.2.21 Saving Bytes



2.2.22 1 Bit Decoder



2.2.23 2 Bit Decoder



2.2.24 3 Bit Decoder



2.2.25 Little Box



2.2.26 Counter


2.3 处理器架构
2.3.1 Arithmetic Logic Unit (ALU) 1



2.3.2 Registers

为便于扩展,使用控制端和输入端短接的开关控制寄存器的存储。


2.3.3 Arithmetic Logic Unit (ALU) 2



2.3.4 Component Factory



2.3.5 Instruction Decoder



2.3.6 ALU

后续关卡中未改变线路的部分不再展示。
图中自定义元件ALU添加一个控制端如下:


2.3.7 Conditions

首先搭建一个判断等于零和小于零的自定义元件如下:

设指令的前三位从高到低分别为A、B、C,若值等于零则D=1,否则D=0,若值小于零则E=1,否则E=0,得真值表如下:
A
B
C
Y
0
0
0
0
0
0
1
1
0
1
0
D
0
1
1
D'
1
0
0
E
1
0
1
E'
1
1
0
D+E
1
1
1
(D+E)'
观察可得该真值表可拆分为:
A
B
Y1
0
0
0
0
1
D
1
0
E
1
1
D+E
C
Y1
Y
0
0
0
0
1
1
1
0
1
1
1
0
得输出的表达式为
Y=Y1⊕C=(AE+BD)⊕C
解法如下:


2.3.8 Immediate Values



2.3.9 Program



2.3.10 Turing Complete

2.4 编程
Overture处理器汇编语言定义如下:
[settings] name = "Overture" [fields] Register r0 000 r1 001 r2 010 r3 011 r4 100 r5 101 in 110 out 110 Calculate nand 000 or 001 and 010 nor 011 add 100 sub 101 Condition false 000 true 001 z 010 notz 011 n 100 notn 101 notp 110 p 111 [instructions] imm %a(immediate | label) 00aaaaaa calc %a(Calculate) 01000aaa mov %a(Register), %b(Register) 10aaabbb jmp %a(Condition) 11000aaa

2.4.1 Add 5



2.4.2 Add 5 again

汇编代码:
imm 5 mov r0, r1 mov in, r2 calc add mov r3, out

2.4.3 Calibrating Lasor Cannons

汇编代码:
mov in, r1 mov in, r2 calc add mov r3, r1 mov r3, r2 calc add mov r3, r1 calc add mov r3, out

2.4.4 Conditional Jumps

汇编代码:
imm 37 mov r0, r5; input: imm 1 mov r0, r1 mov r4, r2 calc add mov r3, r4 mov in, r1 mov r5, r2 calc sub imm input jmp notz mov r4, out imm input jmp true

2.4.5 Storage cracker

本关使用一次粗寻和一次细寻,粗寻时每次将猜测值加16后比较,超过目标值则进入细寻,粗寻时每次将猜测值减1后比较。为防止粗寻时的猜测值达到240时下一次粗寻溢出,当粗寻值溢出至0时直接跳转至细寻。
汇编代码:
search_1: mov r4, r1 imm 16 mov r0, r2 calc add mov r3, r4 mov r4, out mov in, r3 imm search_2 jmp notz mov r4, r3 imm search_2 jmp z imm search_1 jmp true search_2: mov r4, r1 imm 1 mov r0, r2 calc sub mov r3, r4 mov r4, out mov in, r3 imm search_2 jmp true

2.4.6 Masking Time

汇编代码:
mov in, r2 imm 3 mov r0, r1 calc and mov r3, out

2.4.7 The Maze

汇编代码:
move_forward: imm 1 mov r0, out imm 0 mov r0, out mov in, r3 imm move_forward jmp z; turn_right: imm 2 mov r0, out mov in, r3 imm turn_right jmp notz imm move_forward jmp true
2.5 处理器架构 2
2.5.1 XOR

汇编代码:
mov in, r1 mov in, r2 calc or mov r3, r4 calc nand mov r3, r2 mov r4, r1 calc and mov r3, out

2.5.2 Byte Constant



2.5.3 Byte XOR



2.5.4 Equality



2.5.5 Hex Racer



2.5.6 Unsigned Less



2.5.7 Signed Less

当符号位相同时比较前7位,当符号位不同时比较符号位。


2.5.8 Shift


图中自定义元件为


2.5.9 Objective Beauty


通关本关需搭建以下最少门电路的异或门:

2.6 汇编挑战
2.6.1 One hot encoding



2.6.2 Symphony counter



2.6.3 Instruction decoder



2.6.4 Comparison flags



2.6.5 Wire Speghetti

图中的自定义元件为


2.6.6 Multiply



2.6.7 IO

后续关卡中未改变线路的部分不再展示。


2.6.8 Symphony ALU



2.6.9 Integrating ALU


图中自定义元件ALU添加一个控制端如下:


2.6.10 Immediates



2.6.11 Condition match



2.6.12 Jumps




2.6.13 RAM




2.6.14 SSD



2.6.15 IO Devices


图中自定义元件IO为

完整的Symphony处理器线路图如下:


2.6.16 Instruction aliases

汇编语言定义:
mov %a(register), %b(register) 00100001 aaaa0000 0000bbbb 00000000 Copies from register %b to register %a neg %a(register), %b(register) 00100101 aaaa0000 0000bbbb 00000000 Negate register %b and store the result in %a not %a(register), %b(register) 00100011 aaaa0000 0000bbbb 00000000 Bitwise NOT each bit in register %b and store the result in %a

2.7 汇编挑战
2.7.1 Stack

汇编代码:
main: in r1 cmp r1, 0 je pop push: sub sp, sp, 2 store_16 [sp], r1 jmp main pop: load_16 r1,[sp] add sp, sp, 2 out r1 jmp main

2.7.2 Functions



2.7.3 Random number generator

汇编代码:
in r1 RNG: lsr r2, r1, 7 xor r2, r1, r2 lsl r3, r2, 9 xor r3, r2, r3 lsr r4, r3, 8 xor r4, r3, r4 mov r1, r4 out r4 jmp RNG

2.7.4 AI Showdown

保持留给对方的牌数为4n+1即可获胜。
汇编代码:
mov r2, 9 take: in r1 sub r3, r1, r2 out r3 sub r2, r2, 4 jmp take

2.7.5 Divide

汇编代码:
in r1 in r2 divide: cmp r1, r2 jb end sub r1, r1, r2 add r3, r3, 1 jmp divide end: out r3 out r1

2.7.6 Tower of Alloy

汇编代码:
in r1 in r2 in r3 in r4 mov r13, 5 call move move: push r1 push r2 push r3 push r4 cmp r1, 0 je move_0 mov r5, r3 mov r3, r4 mov r4, r5 sub r1, r1, 1 call move out r2 out r13 out r4 out r13 mov r5, r2 mov r2, r3 mov r3, r4 mov r4, r5 call move jmp move_end move_0: out r2 out r13 out r3 out r13 jmp move_end move_end: pop r4 pop r3 pop r2 pop r1 ret

2.7.7 Delicious Order

汇编代码:
mov r13, 30 input: in r1 pstore_16 [sp], r1 add sp, sp, 2 cmp sp, 32 jne input mov sp, 0 sort: pload_16 r1, [sp] add sp, sp, 2 pload_16 r2, [sp] cmp r1, r2 jb sort_swap_end pstore_16 [sp], r1 sub sp, sp, 2 pstore_16 [sp], r2 add sp, sp, 2 sort_swap_end: cmp sp, r13 jne sort sub r13, r13, 2 mov sp, 0 cmp r13, 0 jne sort output: pload_16 r1, [sp] out r1 add sp, sp, 2 cmp sp, 32 jne output

2.7.8 Planet Names

汇编代码:
mov sp, 1 check: in r1 cmp sp, 1 je replace mov r2, r1 jmp replace_output replace: sub r2, r1, 32 replace_output: out r2 cmp r1, 32 je replace_is_space mov sp, 0 jmp check replace_is_space: mov sp, 1 jmp check
2.8 (无标题)
2.8.1 Calibrating Laser Cannons 2

汇编代码:
calc: in r1 cmp r1, 32 je calc_is_space cmp r1, 48 jb calc_isnot_number cmp r1, 57 ja calc_isnot_number jmp calc_is_number calc_isnot_number: cmp r1, 0 je calc_calc mov r2, r1 mov r13, 0 jmp calc calc_is_number: mov r13, 1 sub r1, r1, 48 mul r4, r4, 10 add r4, r4, r1 jmp calc calc_is_space: cmp r13, 0 je calc_calc cmp r2, 45 jne calc_is_positive neg r4, r4 mov r2, 0 calc_is_positive: push r4 mov r4, 0 jmp calc calc_calc: cmp r13, 1 je calc_only_1_number cmp r2, 43 je calc_is_add cmp r2, 45 je calc_is_sub cmp r2, 124 je calc_is_or cmp r2, 38 je calc_is_and cmp r2, 94 je calc_is_xor cmp r2, 60 je calc_is_lsl cmp r2, 62 je calc_is_lsr calc_is_add: pop r6 pop r5 add r7, r5, r6 push r7 jmp calc_end calc_is_sub: pop r6 pop r5 sub r7, r5, r6 push r7 jmp calc_end calc_is_or: pop r6 pop r5 or r7, r5, r6 push r7 jmp calc_end calc_is_and: pop r6 pop r5 and r7, r5, r6 push r7 jmp calc_end calc_is_xor: pop r6 pop r5 xor r7, r5, r6 push r7 jmp calc_end calc_is_lsl: pop r6 pop r5 lsl r7, r5, r6 push r7 jmp calc_end calc_is_lsr: pop r6 pop r5 lsr r7, r5, r6 push r7 jmp calc_end calc_end: mov r2, 0 cmp r1, 0 jne calc pop r1 out r1 calc_only_1_number: out r4

2.8.2 Pipeline timer

使用时序逻辑电路的分析方法分析本关。设输入为X,输出为Y,计数器当前的输出状态为Q,也是下一刻的输入状态,下一刻的输出状态为Q*,Q为n位信号,根据实际情况选择位数。设输入信号为1时状态依次变为00→10→11→00,得真值表如下:
X
Q1
Q2
Q1*
Q2*
Y
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
因此状态方程和输出方程为
Q1*=Q1Q2'+XQ1'
Q2*=Q1Q2'
Y=Q1
解法如下:


2.8.3 Symphony FAST ALU

按下图绘制一个2位并行加法器元件:

使用该元件完成1.2.15关卡中的8位加法器即可。



2.8.4 Pipelined counting



2.8.5 Pipeline



图中的自定义元件为


2.8.6 Reg use check



2.8.7 Data hazard



2.8.8 Counter increment



2.8.9 Superscalar counting



2.8.10 Superscalar



图中的自定义元件为


2.8.11 Speculative execution





2.8.12 Register renamer

本关及之后的关卡均未完成。