本文首發(fā)于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。

關(guān)卡展示

本關(guān)的【關(guān)鍵字】輸入會不定時地發(fā)送一些長度為 2 的數(shù)據(jù)包。當其中的數(shù)據(jù)包和特定的敏感詞一致時，將耳機靜音（音頻輸出變?yōu)?50），直到出現(xiàn)【撤銷】信號后，再恢復正常播放。敏感詞列表參考數(shù)據(jù)手冊：

本關(guān)要求出現(xiàn)《權(quán)力的戰(zhàn)爭》中的任意一個敏感詞時將耳機靜音。

我們首先想到的是：將這些關(guān)鍵字放入一個 ROM 里，出現(xiàn)關(guān)鍵字數(shù)據(jù)包時在 ROM 里一一比對，匹配上則立刻將耳機靜音，直到出現(xiàn)撤銷信號時，恢復原先的聲音。電路圖和代碼如下：

首先我們將當前時鐘周期的數(shù)據(jù)包中的兩個數(shù)分別放入 acc 和 dat 寄存器中（mov x1 acc, mov x1 dat）。然后我們和 ROM 中的敏感詞列表做一一比對。首先檢查當前指針指向的第一個數(shù)字是否與 acc 相等（teq x2 acc）。如果不相等，說明沒有匹配上這組敏感詞，第二個數(shù)字直接跳過，不用比對（- mov x2 null）。如果第一個數(shù)字相等，則需要再判定這組敏感詞的第二個數(shù)字是否與 dat 相等（+ teq x2 dat）。如果第二個數(shù)字不相等，自然萬事大吉，跳到第 10 行，檢查當前的 ROM 地址是否為 0（tcp x3 0）。如果當前 ROM 的地址大于 0，說明這個 ROM 還沒有完整地跑完一圈，還有其他沒有嘗試配對的敏感詞，跳回到第 3 行繼續(xù)嘗試匹配（+ jmp 3），直到所有的關(guān)鍵詞都沒有匹配上為止，這一秒內(nèi)揚聲器正常輸出音頻（mov p0 p1），睡一秒后進入下一時鐘周期（slp 1）。

回到第 6 行，如果第一個數(shù)和 acc 相等，第二個數(shù)也同時和 dat 相等，說明觸發(fā)了敏感詞，將耳機的輸出波形置為 50，令耳機靜音（+ mov 50 p1）。靜音的過程中，不斷檢查是否觸發(fā)了【撤銷】信號（+ teq?x0 0）。如果沒有觸發(fā)撤銷信號，則睡一秒進入下一個周期后（+ slp 1），跳到第 7 行繼續(xù)判定是否有【撤銷】信號（+ jmp 7）。直到撤銷信號出現(xiàn)后才能脫離這個靜音循環(huán)。

點擊左下角的【模擬】，稍等片刻，便會彈出結(jié)算界面：

利用【哈希表】數(shù)據(jù)結(jié)構(gòu)加快查找速度，優(yōu)化電量

我們的第一版設(shè)計方案里，因為每秒鐘都要遍歷整個 ROM 來檢查是否匹配上了敏感詞，所以耗電量相當大，達到了 1.4K。

【哈希表】數(shù)據(jù)結(jié)構(gòu)就是為了解決這樣的“查找慢”的問題的。它的核心思想是：用一個數(shù)學公式將我們的數(shù)據(jù)映射成某個特征值（hash），然后將數(shù)據(jù)放在特征值所對應(yīng)的空間里。這個特征值必須滿足：對于同一個數(shù)據(jù)而言，其特征值無論什么時候計算都是同一個值。也就是滿足數(shù)學上的函數(shù)關(guān)系，對于同樣的自變量，一定能得到同樣的因變量。當我們需要檢查某個數(shù)據(jù)是否在表中時，只需要先把這份數(shù)據(jù)的特征值計算出來，然后到對應(yīng)的空間里去找就行了，不需要去翻遍整個表格。因為別的空間里的數(shù)據(jù)，特征值都和當前數(shù)據(jù)的特征值不一樣，根據(jù)【原命題和逆否命題等價】的原理，可得：如果某個數(shù)據(jù)連特征值都和當前數(shù)據(jù)不一樣，那么其實際內(nèi)容也一定和當前數(shù)據(jù)不一樣。

舉例說明：我們生活中的快遞驛站其實就是一個【哈希表】數(shù)據(jù)結(jié)構(gòu)。顧客前來取件時，驛站管理員往往需要你報出手機尾號，然后根據(jù)你的手機尾號到對應(yīng)的柜子處去找你的快遞。這時候，對于這家驛站而言，快遞的特征值 = 收件人的手機尾號。我們的管理人員在得到你的手機尾號信息時，會前往有著同樣手機尾號的快遞格去找你的快遞，而不會從頭開始一件一件亂翻。這樣就大大提高了取件效率。哈希表體現(xiàn)了一個【數(shù)據(jù)分類】的思想。

回到題目，對于這 6 個敏感詞數(shù)據(jù)，我們能提取出什么樣的“各不相同”的特征呢？我們仔細觀察后發(fā)現(xiàn)，這 6 個敏感詞的第二個數(shù)字的百位乘以 2 并模 14 后的結(jié)果各不相同：

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

• 百夫長，495 160，1 × 2 mod 14 = 2

• 毒藥師，575 645，6 × 2 mod 14 = 12

• 助產(chǎn)士，712 917，9 × 2 mod 14 = 4

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

• 陰影地帶，138 420，4 × 2 mod 14 = 8

也就是說，如果將一個關(guān)鍵詞的第二個數(shù)字的百位 × 2 mod 14 作為特征值的話，這六個敏感詞正好可以放在一個 ROM 中，位置上沒有任何沖突，互不干擾。那么，我們就可以設(shè)計這樣的一個算法：

1. 收到一個關(guān)鍵詞數(shù)據(jù)包后，設(shè)第一個數(shù)字為 a，第二個數(shù)字為 b。計算其特征值 ?b / 100? × 2 mod 14，并將 ROM 的指針置為該值。

2. 連續(xù)比較 ROM 中接下來的兩個數(shù)是否分別和 a, b 相等。滿足條件時靜音，不滿足條件時正常播放。

電路圖和代碼如下：

這次，我們將 6 個敏感詞按照其特征值放在了 ROM 的固定位置。地址 2 處放的是“百夫長”（495 160），地址 4 處放的是“助產(chǎn)士”（712 917），地址 6 處放的是“矮人起義”（356 361）……比對后可以發(fā)現(xiàn)，除了占位用的 0 號地址，每個敏感詞放置的位置都和其特征值??b / 100? × 2 mod 14 完美對應(yīng)。

我們先看上面的芯片。上面的芯片的作用是接收下方芯片傳來的關(guān)鍵詞（其中第一個數(shù)字傳一遍，第二個數(shù)字傳兩遍），判定它是否是敏感詞。若是敏感詞，則回傳 1?告知下方芯片令耳機靜音。若不是敏感詞，則回傳 0 告知下方芯片令耳機正常播放。

上方的芯片首先等待下方芯片傳關(guān)鍵詞上來（slx x2），然后依次將第一個數(shù)和第二個數(shù)放入 dat?和 acc（mov x2?dat, mov x2?acc）。此時我們開始計算這個關(guān)鍵詞的特征值，取出第二個數(shù)字的百位（dgt 2），將它乘以 2 后（add acc）設(shè)置為 ROM 的地址，會自動對 14 取模（mov acc x1）。此時，因為第二個數(shù)字經(jīng)過了處理，丟失了原始信息，所以我們需要從下方芯片處重新獲取一份原始的第二個數(shù)（mov x2?acc）。此時，我們判斷給定的關(guān)鍵詞是否和相同特征值處的敏感詞完全一致（teq x0?dat, + teq x0 acc）。如果完全一致，則觸發(fā)敏感詞，回傳 1?令耳機靜音（+ mov 1?x1）。若和對應(yīng)的敏感詞不是完全一致時，回傳 0 令耳機正常播放（- mov 0 x1）。

再看下面的芯片。下方芯片的 dat 寄存器用來表示當前是靜音還是正常播放狀態(tài)。由于 dat 的初值是 0，耳機最初也處于正常播放狀態(tài)，所以我們用 0 表示正常播放，1?表示靜音。首先我們需要判斷是否出現(xiàn)了【撤銷】信號（tcp x0 50）。如果出現(xiàn)了【撤銷】信號，則強制令耳機解除靜音（+?mov 0 dat），并跳過敏感詞的檢查過程，直接跳到第 12?行放音（+ mov p0 p1）。若沒有出現(xiàn)撤銷信號，則檢查耳機是否處于靜音狀態(tài)（- tcp dat 1）。如果耳機處于靜音狀態(tài)，也跳過敏感詞的判定過程，關(guān)閉所有 +/- 號指令，直接跳到最后休眠，保持靜音（slp 1）。僅當沒有【撤銷】信號，耳機也正常放音時，才需要監(jiān)測是否觸發(fā)了敏感詞。我們首先將當前時鐘周期的首數(shù)字讀入 acc（- mov x1 acc），然后判斷其是否是 -999（- teq acc -999）。如果是 -999，說明目前我們尚未收到關(guān)鍵詞數(shù)據(jù)，也就不需要判斷是否是敏感詞，直接跳到第 12?行正常放音即可（+ mov p0 p1）。如果首數(shù)字不是 -999，則需要具體判斷當前關(guān)鍵字是否是敏感詞。我們先將第一個數(shù)字發(fā)送給上邊的芯片（- mov acc x3），然后，由于第二個數(shù)字要發(fā)兩份，所以我們要先將第二個數(shù)字暫存到 acc 里（- mov x1 acc），然后再將第二個數(shù)字向上方的芯片發(fā)送兩份（- mov acc x3, - mov acc x3），等待上方芯片告知是否需要靜音，將結(jié)果放入 dat 中（- mov x3 dat）。至此，檢查 dat 的值為 0 還是 1（- teq dat 0）。dat 的值為 0 時，正常放音（+ mov p0 p1），否則靜音（-?mov 50 p1）。做完這些事后，休眠一秒，進入下一個時鐘周期（slp 1）。

點擊左下角的【模擬】，稍等片刻，便會彈出結(jié)算界面：

電量降低到了 694！相比于之前的 1.4K，耗電量減少了約 50%，效率提升了一倍！哈希表的“快速查找”成效十足。

極致優(yōu)化電量

之前的方案里，下方的芯片每次要把第二個數(shù)字給上方的芯片發(fā)送兩次。我們這里做個微操，給上方芯片發(fā)送關(guān)鍵詞數(shù)據(jù)時，先發(fā)第二個數(shù)字（讓上方芯片自我復制一份），再發(fā)第一個數(shù)字，如此便可將電量優(yōu)化到極致。更改后的芯片代碼如下：

上下兩塊芯片都做了一些微操，上方芯片省去了一行代碼，下方芯片省去了兩行代碼。

先看下方芯片。注意一下 6~7 行的代碼：

相比于上一版方案的 6~9 行代碼來說：

這一版方案里：①改變了傳輸順序，先從 C2S-RF901 讀取第二個數(shù)字傳出去，再把 acc 里記錄的第一個數(shù)字傳出去。②兩個數(shù)字都只傳一次。

為什么改變了傳輸順序以后就不需要把第二個數(shù)字傳兩次了呢？因為我們的特征值只跟第二個數(shù)字有關(guān)。我們先把第二個數(shù)字傳上去以后，上方的芯片就可以直接開始計算特征值了，原先用于存儲第一個數(shù)字的空間可以用來存儲第二個數(shù)字，這樣就避免了之前【因計算特征值的需要，不得不丟棄第二個數(shù)字的原始信息，需要委托下方芯片重新傳一次第二個數(shù)字】這樣荒唐的現(xiàn)象。而我們的第一個數(shù)字完全不需要早早地就存下來，因為第一個數(shù)字是僅當計算完特征值后才是需要的。這時候再委托下方芯片傳上來，才是恰到好處的。如果早早地把第一個數(shù)字傳上去，反而欲速則不達。

上方芯片的代碼，改動的地方是比較多的，需要徹底重新解釋一遍。首先，我們等待下方芯片把【第二個數(shù)字】傳上來（slx x2）。傳上來第二個數(shù)字后，將該數(shù)字的原始信息放到 dat 里（mov x2 dat），然后復制一份到 acc 里，準備計算特征值（mov dat acc）。我們提取出這個數(shù)字的百位（dgt 2），將它乘以 2 后（add acc）設(shè)置為 ROM 的地址，會自動對 14 取模（mov acc x1）。這時候，我們從下方芯片接收【第一個數(shù)字】，判斷該數(shù)字是否和相同特征值處的敏感詞的【第一個數(shù)字】一致（teq?x0 x2），再判斷預存在 dat 里的【第二個數(shù)字】是否和敏感詞的【第二個數(shù)字】一致（+ teq x0 dat）。如果兩個數(shù)字都完全一致，則觸發(fā)敏感詞，回傳 1?令耳機靜音（+ mov 1?x1）。若和對應(yīng)的敏感詞不是完全一致時，回傳 0 令耳機正常播放（- mov 0 x1）。

點擊左下角的【模擬】，稍等片刻，便會彈出結(jié)算界面：

代碼行數(shù)相比于上一版哈希表方案，減少了兩行。同時，電量只有 616 了，甚至打破了我自己的記錄！這次的效率相比于線性查找的 1.4K，提升了 56%！果然寫攻略教別人，是提升自己的最好方式呢。