深圳SHENZHENIO第28关防剧透耳机攻略

深圳IO是一款硬核的编程游戏，有着严谨的游戏内容，那么一起来看看第28关防剧透耳机的攻略吧。

主界面

由于游戏过分硬核，先放个手册中的图看看冰山一角：

不过这也正对应了嵌入式开发中会遇到的海量数据手册，相当程度上还原了嵌入式日常开发的情景。

游戏中设计到部分的编程有些类似于汇编语言，这里上手还是有一些些难度的，大家请做好准备，继续直接扔核弹：

不用害怕，在游戏过程中，会逐步引导你学会使用新的指令，对于新的器件，也是随着主线的进行逐步开放的

在游戏中，你不仅可以完成指定的基本目标，还可以挑战全网玩家，看谁能达成最佳优化目标。

鱼和熊掌不可兼得，多数情况下想要达成更好的性能就要增加成本啦，不过这正是优秀的嵌入式开发人员的意义所在——比你好，还比你的便宜。

第28关：防剧透耳机

关卡展示

本关的【关键字】输入会不定时地发送一些长度为 2 的数据包。当其中的数据包和特定的敏感词一致时，将耳机静音(音频输出变为 50)，直到出现【撤销】信号后，再恢复正常播放。敏感词列表参考数据手册：

本关要求出现《权力的战争》中的任意一个敏感词时将耳机静音。

我们首先想到的是：

将这些关键字放入一个 ROM 里，出现关键字数据包时在 ROM 里一一比对，匹配上则立刻将耳机静音，直到出现撤销信号时，恢复原先的声音。电路图和代码如下：

首先我们将当前时钟周期的数据包中的两个数分别放入 acc 和 dat 寄存器中(mov x1 acc, mov x1 dat)。然后我们和 ROM 中的敏感词列表做一一比对。首先检查当前指针指向的第一个数字是否与 acc 相等(teq x2 acc)。如果不相等，说明没有匹配上这组敏感词，第二个数字直接跳过，不用比对(- mov x2 null)。如果第一个数字相等，则需要再判定这组敏感词的第二个数字是否与 dat 相等(+ teq x2 dat)。如果第二个数字不相等，自然万事大吉，跳到第 10 行，检查当前的 ROM 地址是否为 0(tcp x3 0)。如果当前 ROM 的地址大于 0，说明这个 ROM 还没有完整地跑完一圈，还有其他没有尝试配对的敏感词，跳回到第 3 行继续尝试匹配(+ jmp 3)，直到所有的关键词都没有匹配上为止，这一秒内扬声器正常输出音频(mov p0 p1)，睡一秒后进入下一时钟周期(slp 1)。

回到第 6 行，如果第一个数和 acc 相等，第二个数也同时和 dat 相等，说明触发了敏感词，将耳机的输出波形置为 50，令耳机静音(+ mov 50 p1)。静音的过程中，不断检查是否触发了【撤销】信号(+ teq x0 0)。如果没有触发撤销信号，则睡一秒进入下一个周期后(+ slp 1)，跳到第 7 行继续判定是否有【撤销】信号(+ jmp 7)。直到撤销信号出现后才能脱离这个静音循环。

点击左下角的【模拟】，稍等片刻，便会弹出结算界面：

利用【哈希表】数据结构加快查找速度，优化电量

我们的第一版设计方案里，因为每秒钟都要遍历整个 ROM 来检查是否匹配上了敏感词，所以耗电量相当大，达到了 1.4K。

【哈希表】数据结构就是为了解决这样的“查找慢”的问题的。它的核心思想是：用一个数学公式将我们的数据映射成某个特征值(hash)，然后将数据放在特征值所对应的空间里。这个特征值必须满足：对于同一个数据而言，其特征值无论什么时候计算都是同一个值。也就是满足数学上的函数关系，对于同样的自变量，一定能得到同样的因变量。当我们需要检查某个数据是否在表中时，只需要先把这份数据的特征值计算出来，然后到对应的空间里去找就行了，不需要去翻遍整个表格。因为别的空间里的数据，特征值都和当前数据的特征值不一样，所以一定和当前数据不相等。

举例说明：我们生活中的快递驿站其实就是一个【哈希表】数据结构。顾客前来取件时，驿站管理员往往需要你报出手机尾号，然后根据你的手机尾号到对应的柜子处去找你的快递。这时候，对于这家驿站而言，快递的特征值 = 收件人的手机尾号。我们的管理人员在得到你的手机尾号信息时，会前往有着同样手机尾号的快递格去找你的快递，而不会从头开始一件一件乱翻。这样就大大提高了取件效率。哈希表体现了一个【数据分类】的思想。

回到题目，对于这 6 个敏感词数据，我们能提取出什么样的“各不相同”的特征呢?我们仔细观察后发现，这 6 个敏感词的第二个数字的百位乘以 2 并模 14 后的结果各不相同：

君主，711 573，5 × 2 mod 14 = 10

百夫长，495 160，1 × 2 mod 14 = 2

毒药师，575 645，6 × 2 mod 14 = 12

助产士，712 917，9 × 2 mod 14 = 4

矮人起义，356 361，3 × 2 mod 14 = 6

阴影地带，138 420，4 × 2 mod 14 = 8

也就是说，如果将一个关键词的第二个数字的百位 × 2 mod 14 作为特征值的话，这六个敏感词正好可以放在一个 ROM 中，位置上没有任何冲突，互不干扰。那么，我们就可以设计这样的一个算法：

1，收到一个关键词数据包后，设第一个数字为 a，第二个数字为 b。计算其特征值 ⌊b / 100⌋ × 2 mod 14，并将 ROM 的指针置为该值。

2，连续比较 ROM 中接下来的两个数是否分别和 a, b 相等。满足条件时静音，不满足条件时正常播放。

电路图和代码如下：

这次，我们将 6 个敏感词按照其特征值放在了 ROM 的固定位置。地址 2 处放的是“百夫长”(495 160)，地址 4 处放的是“助产士”(712 917)，地址 6 处放的是“矮人起义”(356 361)……比对后可以发现，除了占位用的 0 号地址，每个敏感词放置的位置都和其特征值 ⌊b / 100⌋ × 2 mod 14 完美对应。

我们先看上面的芯片。

上面的芯片的作用是接收下方芯片传来的关键词(其中第一个数字传一遍，第二个数字传两遍)，判定它是否是敏感词。若是敏感词，则回传 100 告知下方芯片令耳机静音。若不是敏感词，则回传 0 告知下方芯片令耳机正常播放。

上方的芯片首先等待下方芯片传关键词上来(slx x1)，然后依次将第一个数和第二个数放入 dat 和 acc(mov x1 dat, mov x1 acc)。此时我们开始计算这个关键词的特征值，取出第二个数字的百位(dgt 2)，将它乘以 2 后(mul 2)设置为 ROM 的地址，会自动对 14 取模(mov acc x3)。此时，因为第二个数字经过了处理，丢失了原始信息，所以我们需要从下方芯片处重新获取一份原始的第二个数(mov x1 acc)。此时，我们判断给定的关键词是否和相同特征值处的敏感词完全一致(teq x2 dat, + teq x2 acc)。如果完全一致，则触发敏感词，回传 100 令耳机静音(+ mov 100 x1)。若和对应的敏感词不是完全一致时，回传 0 令耳机正常播放(- mov 0 x1)。

再看下面的芯片。

下方芯片的 dat 寄存器用来表示当前是静音还是正常播放状态。由于 dat 的初值是 0，耳机最初也处于正常播放状态，所以我们用 0 表示正常播放，100 表示静音。首先我们需要判断是否出现了【撤销】信号(tcp 0 x2)。如果出现了【撤销】信号，则强制令耳机解除静音(- mov 0 dat)，并跳过敏感词的检查过程，直接跳到最后放音(- jmp c)。若没有出现撤销信号，则检查耳机是否处于静音状态(tcp dat 0)。如果耳机处于静音状态，也跳过敏感词的判定过程，直接跳到最后保持静音(+ jmp d)。仅当没有【撤销】信号，耳机也正常放音时，才需要监测是否触发了敏感词。我们先将当前数据包的第一个数字发送给上边的芯片(mov x1 x0)，由于第二个数字要发两份，所以第二个数字需要先存到 acc 里(mov x1 acc)，然后再将第二个数字向上方的芯片发送两份(mov acc x0, mov acc x0)，等待上方芯片告知是否需要静音，将结果放入 dat 中(mov x0 dat)。至此，检查 dat 的值为 0 还是 100(tcp dat 50)。dat 的值为 0 时，正常放音(- mov p0 p1)，否则静音(+ mov 50 p1)。做完这些事后，休眠一秒，进入下一个时钟周期(slp 1)。

点击左下角的【模拟】，稍等片刻，便会弹出结算界面：

电量降低到了 895，相比于之前的 1.4K，耗电量减少了约 36%。哈希表的“快速查找”成效十足。