【深圳 IO 攻略】第 28 关：防剧透耳机
本文首发于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原创不易，转载请注明出处。
关卡展示
本关的【关键字】输入会不定时地发送一些长度为 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 中，位置上没有任何冲突，互不干扰。那么，我们就可以设计这样的一个算法：
收到一个关键词数据包后，设第一个数字为 a，第二个数字为 b。计算其特征值 ⌊b / 100⌋ × 2 mod 14，并将 ROM 的指针置为该值。
连续比较 ROM 中接下来的两个数是否分别和 a, b 相等。满足条件时静音，不满足条件时正常播放。
电路图和代码如下：
这次，我们将 6 个敏感词按照其特征值放在了 ROM 的固定位置。地址 2 处放的是“百夫长”（495 160），地址 4 处放的是“助产士”（712 917），地址 6 处放的是“矮人起义”（356 361）……比对后可以发现，除了占位用的 0 号地址，每个敏感词放置的位置都和其特征值 ⌊b / 100⌋ × 2 mod 14 完美对应。
我们先看上面的芯片。上面的芯片的作用是接收下方芯片传来的关键词（其中第一个数字传一遍，第二个数字传两遍），判定它是否是敏感词。若是敏感词，则回传 1 告知下方芯片令耳机静音。若不是敏感词，则回传 0 告知下方芯片令耳机正常播放。
上方的芯片首先等待下方芯片传关键词上来（slx x2），然后依次将第一个数和第二个数放入 dat 和 acc（mov x2 dat, mov x2 acc）。此时我们开始计算这个关键词的特征值，取出第二个数字的百位（dgt 2），将它乘以 2 后（add acc）设置为 ROM 的地址，会自动对 14 取模（mov acc x1）。此时，因为第二个数字经过了处理，丢失了原始信息，所以我们需要从下方芯片处重新获取一份原始的第二个数（mov x2 acc）。此时，我们判断给定的关键词是否和相同特征值处的敏感词完全一致（teq x0 dat, + teq x0 acc）。如果完全一致，则触发敏感词，回传 1 令耳机静音（+ mov 1 x1）。若和对应的敏感词不是完全一致时，回传 0 令耳机正常播放（- mov 0 x1）。
再看下面的芯片。下方芯片的 dat 寄存器用来表示当前是静音还是正常播放状态。由于 dat 的初值是 0，耳机最初也处于正常播放状态，所以我们用 0 表示正常播放，1 表示静音。首先我们需要判断是否出现了【撤销】信号（tcp x0 50）。如果出现了【撤销】信号，则强制令耳机解除静音（+ mov 0 dat），并跳过敏感词的检查过程，直接跳到第 12 行放音（+ mov p0 p1）。若没有出现撤销信号，则检查耳机是否处于静音状态（- tcp dat 1）。如果耳机处于静音状态，也跳过敏感词的判定过程，关闭所有 +/- 号指令，直接跳到最后休眠，保持静音（slp 1）。仅当没有【撤销】信号，耳机也正常放音时，才需要监测是否触发了敏感词。我们首先将当前时钟周期的首数字读入 acc（- mov x1 acc），然后判断其是否是 -999（- teq acc -999）。如果是 -999，说明目前我们尚未收到关键词数据，也就不需要判断是否是敏感词，直接跳到第 12 行正常放音即可（+ mov p0 p1）。如果首数字不是 -999，则需要具体判断当前关键字是否是敏感词。我们先将第一个数字发送给上边的芯片（- mov acc x3），然后，由于第二个数字要发两份，所以我们要先将第二个数字暂存到 acc 里（- mov x1 acc），然后再将第二个数字向上方的芯片发送两份（- mov acc x3, - mov acc x3），等待上方芯片告知是否需要静音，将结果放入 dat 中（- mov x3 dat）。至此，检查 dat 的值为 0 还是 1（- teq dat 0）。dat 的值为 0 时，正常放音（+ mov p0 p1），否则静音（- mov 50 p1）。做完这些事后，休眠一秒，进入下一个时钟周期（slp 1）。
点击左下角的【模拟】，稍等片刻，便会弹出结算界面：
电量降低到了 694！相比于之前的 1.4K，耗电量减少了约 50%，效率提升了一倍！哈希表的“快速查找”成效十足。
极致优化电量
之前的方案里，下方的芯片每次要把第二个数字给上方的芯片发送两次。我们这里做个微操，给上方芯片发送关键词数据时，先发第二个数字（让上方芯片自我复制一份），再发第一个数字，如此便可将电量优化到极致。更改后的芯片代码如下：
上下两块芯片都做了一些微操，上方芯片省去了一行代码，下方芯片省去了两行代码。
先看下方芯片。注意一下 6~7 行的代码：
相比于上一版方案的 6~9 行代码来说：
这一版方案里：①改变了传输顺序，先从 C2S-RF901 读取第二个数字传出去，再把 acc 里记录的第一个数字传出去。②两个数字都只传一次。
为什么改变了传输顺序以后就不需要把第二个数字传两次了呢？因为我们的特征值只跟第二个数字有关。我们先把第二个数字传上去以后，上方的芯片就可以直接开始计算特征值了，原先用于存储第一个数字的空间可以用来存储第二个数字，这样就避免了之前【因计算特征值的需要，不得不丢弃第二个数字的原始信息，需要委托下方芯片重新传一次第二个数字】这样荒唐的现象。而我们的第一个数字完全不需要早早地就存下来，因为第一个数字是仅当计算完特征值后才是需要的。这时候再委托下方芯片传上来，才是恰到好处的。如果早早地把第一个数字传上去，反而欲速则不达。
上方芯片的代码，改动的地方是比较多的，需要彻底重新解释一遍。首先，我们等待下方芯片把【第二个数字】传上来（slx x2）。传上来第二个数字后，将该数字的原始信息放到 dat 里（mov x2 dat），然后复制一份到 acc 里，准备计算特征值（mov dat acc）。我们提取出这个数字的百位（dgt 2），将它乘以 2 后（add acc）设置为 ROM 的地址，会自动对 14 取模（mov acc x1）。这时候，我们从下方芯片接收【第一个数字】，判断该数字是否和相同特征值处的敏感词的【第一个数字】一致（teq x0 x2），再判断预存在 dat 里的【第二个数字】是否和敏感词的【第二个数字】一致（+ teq x0 dat）。如果两个数字都完全一致，则触发敏感词，回传 1 令耳机静音（+ mov 1 x1）。若和对应的敏感词不是完全一致时，回传 0 令耳机正常播放（- mov 0 x1）。
点击左下角的【模拟】，稍等片刻，便会弹出结算界面：
代码行数相比于上一版哈希表方案，减少了两行。同时，电量只有 616 了，甚至打破了我自己的记录！这次的效率相比于线性查找的 1.4K，提升了 56%！果然写攻略教别人，是提升自己的最好方式呢。
