1-Wire搜尋算法詳解（2）
4 執行個體及算法分析
要了解算法，或制定算法，我們需要通過一個執行個體來解釋：
ROM示例（僅列出前4位）
| ROM編号 | 1234…… |
| ROM1 | 0011…… |
| ROM2 | 1010…… |
| ROM3 | 1111…… |
| ROM4 | 0001…… |
圖8、4個ROM的執行個體
假設1-Wire挂有4個ROM如上表，這裡ROM碼僅設4位，編号從1到4，而實際器件ROM位序号從1到64。右圖則是按“先0後1”周遊順序所構造的二叉樹，可見第一次周遊得到ROM4：0001，第二次周遊得到ROM1：0011，依次類推。圖中打有⊕的位置就是分叉點，即差異位（或稱為混碼位）。
現在根據上例觀察各次周遊，提煉出算法及實作細節：
1.第一次周遊時，第1位Bit1時遇到第一個差異位，按左序周遊即先0後1的順序，我們選擇0（稱為方向0）；Bit2不是差異位，算法根據“二讀”後友善地選0；Bit3又是差異位，再選擇方向0，Bit4也不是差異位。周遊結果得到ROM4。這裡可得出結論1：凡遇到新的差異位，選擇0。
2.第二次周遊，按執行個體分析，Bit1處再選擇方向0；Bit2取0；Bit3不能再選0了，改選1；Bit4取1；得到ROM1。問題随即産生：問題1、Bit1為何走0？此處确為差異位，但已不是首次經過，不能套用結論1。問題2、Bit3處為何改走1？簡單分析問題2可得出結論2：凡上次周遊時最後一個走0的差異位本次應走1。很明顯，“上次周遊時最後一個差異位”下的左分支已經走過，這次應該往右走了。再回答問題1可以得到結論3：凡上次周遊時最後一個走0的差異位之前的差異位仍按上次周遊的老路走。這個結論比較拗口，觀察執行個體來解釋：Bit3是差異位，右分支還沒走過，現在我要走Bit3下邊的右分支，Bit3之前當然是按上次路線來走了。
3．然後是否就可以進行第三次周遊了呢？且慢，有一個重要的問題還沒處理。第二次周遊前，那個“上次周遊時最後一個走0的差異位”應該Bit3，我們先設定一個變量LastDiscripancy來記住這個值，即LastDiscripancy=3；從前面的分析我們知道，這個變量的值是決定本次周遊時算法在哪個位置改道的依據，而且這個變量在本次周遊全過程中應該保持不變的，如果在該節點前或後有任意多少的差異位，均按結論1（新差異位）和結論3（老差異位）來處理。也可以了解成結論2在一次周遊中必須适用且僅适用一次，這也就是每次周遊都能找出一個新的ROM的核心所在。那麼第二次周遊後，變量LastDiscripancy應該指向哪個節點呢？直接觀察就可發現應該指向Bit1。
4．那麼算法中如何實作每次周遊後變量LastDiscripancy的更新呢？要知道這個指針随着每次周遊在或上或下地移動，如第一次周遊後指向Bit3，第二次後指向Bit1，第三次後指向Bit2。還有，第一次開始周遊前、第四次周遊後該變量又指向哪裡呢？由于實際ROM多達64位，從機如果資料多的話，差異位也會随之增加，是以算法再引入一個變量Last_Zero，在每次周遊前設為0，即指向起始位置前，然後周遊ROM碼的1-64位時，該變量始終指向最後一個走0的差異位，等到周遊完成後，将該變量的值賦給LastDiscripancy即可。這樣我們再觀察執行個體的第二次周遊，Last_Zero周遊前為0，Bit1時，符合“走0的差異位”，于是Last_Zero=1，後續Bit3盡管是差異位，但不走0，是以周遊完成後，該值還是1，最後交給LastDiscripancy，自己又指向0，為第三次周遊作好準備。
5．第三次周遊就變得順理成章：LastDiscripancy=1，Bit1處需運用結論2，算法改走1。而且第三次周遊讓Bit2成為了“最後一個走0的差異位”，第四次周遊就在此處改走1了。第四次周遊搜尋到最後一個rom，但還得告訴程式結束信号，進而退出搜尋。結束信号用什麼判定？4個ROM循環4次？當然不是，上述表圖隻是舉例，實際總路線上挂接多少從機是未知的。答案還是利用變量LastDiscripancy來判定，開始搜尋前自然有LastDiscripancy=0，但一旦進入搜尋程式，每次周遊後該變量總是指向ROM碼中間可能的某一位（1-64），直至周遊到最後一個從機，這時必定是所有差異位均走1，如果Last_Zero保持為初始值0，周遊過程中未作修改，周遊完成後LastDiscripancy=Last_Zero=0。以此為條件可判定搜尋全部完成。
6．綜上，當算法執行到一個差異位時，需判斷區分為三種情況：首次遇到型、上次最後走0型、上次非最後走0型。可以通過二個變量的比較來表征這三種情況，即比較目前搜尋的位id_bit_number和上次最後走0的位LastDiscrepancy的大小來判别，如下表：
表3.搜尋路徑方向的确定
| 三種情況 | 目前搜尋位 vs 最後走0差異位 | 路徑（變量：search_direction） |
| 結論2：上輪最後差異位 | Id_bit_number=LastDiscripancy | 選1 |
| 結論3：非最後差異位 | Id_bit_number < LastDiscripancy | 同上次 (來自存儲的最近ROM碼) |
| 結論1：新遇差異位 | Id_bit_number > LastDiscripancy | 選0 |
其中變量Id_bit_number表示目前搜尋位，每一次周遊時從1至64步進；
變量search_direction表示目前節點經過二讀及判斷後确定的搜尋方向，是0還是1；
其他變量說明請參見流程圖中附文。
5 流程圖：
圖9列出了對一個從器件進行搜尋的流程圖；注意：流程圖附文中列出了涉及到的一些關鍵變量，并進行了說明，在本文描述内容、流程圖及源代碼中也将用到這些名稱的變量。
其他說明：
1、該流程最終被代碼表達成一個函數，可以執行對一個器件的搜尋；
2、當主機複位後未收到從機的存在脈沖、最後裝置變量LastDeviceFlat=1、二讀後均為1這三種情況，函數執行初始化變量後傳回False；
3、紅色虛線框中流程，是針對差異位的處理，分3種情況走不同分支，該部分是本算法的精華；
4、紅色虛線框中最下面的二個綠色背景框，是對家族碼的處理，适用于多類型器件混合網絡的指定處理，如單類器件組網，可以跳過此部分；
5、圖中各指令框邊上列出了部分變量、變量比較、變量指派表達式，以友善後續了解代碼；
| 程式每步搜尋确定的ROM碼将存入數組變量ROM_no[]中，流程圖中“同上次”框中将調用此數組變量的值，擷取上輪周遊時該位值。  |
6 實作
上述流程圖算法實際上是一個通用的函數，可實作一次從機ROM碼的搜尋，在附錄代碼中即為OWSearch（）函數，執行一次該函數，可以有以下幾種結果：
1.複位信号發出後，未收到任何應答信号，表明無器件挂接或硬體電路故障，函數傳回False退出；
2.上輪搜尋中程式判斷為最後一個器件，本次執行函數也是傳回False退出；
3.在某位“二讀”時出現“11”的信号，這是執行中出現的異常，函數也是傳回False退出；
4.首次或再次進入此函數，信号也正常，函數将搜尋到總線上的第一個器件ROM碼；
在上述4種結果中，第1和第3是異常後退出，第2是器件搜尋完畢後結束退出。第4是首次執行搜尋和再次執行搜尋這二種情況，可以表述後下面二個函數：First和Next，二個函數通過對LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag和ROM_NO值的處理，利用同一流程實作了兩個不同類型的搜尋操作；這兩個操作是搜尋1-Wire器件ROM碼的基礎，本文附後列出了全部代碼，可供測試。
First
‘FIRST’操作是搜尋1-Wire總線上的第一個從機器件。該操作是通過将LastDiscrepancy、LastFamilyDiscrepancy和LastDeviceFlag置零，然後進行搜尋完成的。最後ROM碼從ROM_NO寄存器中讀出。若1-Wire總線上沒有器件，複位序列就檢測不到應答脈沖，搜尋過程中止。
Next
‘NEXT’操作是搜尋1-Wire總線上的下一個從機器件；一般情況下，此搜尋操作是在‘FIRST’操作之後或上一次‘NEXT’操作之後進行；保持上次搜尋後這些值的狀态不變、執行又一次搜尋即可實作‘NEXT’操作。之後從ROM_NO寄存器中來讀出新一個ROM碼。若前一次搜尋到的是1-Wire上的最後一個器件，則傳回一個無效标記FALSE，并且把狀态設定成下一次調用搜尋算法時将是‘FIRST’操作的狀态。
Maxim的AN187應用筆記圖3(a, b, c)例舉了三個器件的搜尋過程，為簡單起見該示例中的ROM碼隻有2位。具體過程有二個圖和一個表。與本文中的示例也大同小異，是以本文不再列出。有興趣的可直接閱讀AN187應用筆記。
7 進階變量搜尋
有3種利用同一組狀态變量LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag、ROM_NO實作的進階變量搜尋算法，這幾種進階搜尋算法允許來指定作為搜尋目标或需要跳過搜尋的器件的類型(家族碼)以及驗證某類型的器件是否線上(參見表4)。
如果了解了算法原理及各個變量的作用，不難了解“進階變量搜尋”的三種功能。本文附帶代碼為簡便起見，删除了這些内容，讀者如感興趣可直接通路AN187應用筆記。
Verify
‘VERIFY’操作用來檢驗已知ROM碼的器件是否連接配接在1-Wire總線上，通過提供ROM碼并對該碼進行目标搜尋就可确定此器件是否線上。首先，将ROM_NO寄存器值設定為已知的ROM碼值，然後将LastDiscrepancy和LastDeviceFlag标志位分别設定為64(40h)和0；進行搜尋操作，然後讀ROM_NO的輸出結果；如果搜尋成功并且ROM_NO中存儲的仍是要搜尋器件的ROM碼值，那麼此器件就在1-Wire總線上。
Target Setup
‘TARGET SETUP’操作就是用預置搜尋狀态的方式首先查找一個特殊的家族類型，每個1-Wire器件都有一個位元組的家族碼内嵌在ROM碼中(參見圖1)，主機可以通過家族碼來識别器件所具有的特性和功能。若1-Wire總線上有多片器件時，通常是将搜尋目标首先定位在需注意的器件類型上。為了将一個特殊的家族作為搜尋目标，需要将所希望的家族碼位元組放到ROM_NO寄存器的第一個位元組中，并且将ROM_NO寄存器的複位狀态置零，然後将LastDiscrepancy設定為64(40h)；把LastDeviceFlag和LastFamilyDiscrepancy設定為0。在執行下一次搜尋算法時就能找出所期望的産品類型的第一個器件；并将此值存入ROM_NO寄存器。需要注意的是如果1-Wire總線上沒有挂接所期望的産品類型的器件，就會找出另一類型的器件，是以每次搜尋完成後，都要對ROM_NO寄存器中存儲的結果進行校驗。
Family Skip Setup
‘FAMILY SKIP SETUP’操作用來設定搜尋狀态以便跳過搜尋到的指定家族中的所有器件，此操作隻有在一個搜尋過程結束後才能使用。通過把LastFamilyDiscrepancy複制到LastDiscrepancy，并清除LastDeviceFlag即可實作該操作；在下一搜尋過程就會找到指定家族中的下一個器件。如果目前家族碼分組是搜尋過程中的最後一組，那麼搜尋過程結束并将LastDeviceFlag置位。
要注意的是，FamilySkipSetup和TargetSetup函數實際上并沒有進行搜尋操作，它們隻不過是用來設定搜尋寄存器，以便在下一次執行‘NEXT’操作時能跳過或找到所期望的類型。
表4.搜尋變量狀态的設定
| 功能函數 | LastDiscrepancy | LastFamily- Discrepancy | LastDeviceFlag | ROM_NO |
| FIRST | 搜尋結果 | |||
| NEXT | 保持原值 | 保持原值 | 保持原值 | 保持搜尋結果 |
| VERIFY | 64 | 驗證與預設相同 | ||
| TARGET SETUP | 64 | 僅設家族碼，其他為0 | ||
| FAMILY SKIP SETUP | 複制于LastFamilyDiscrepancy | 保持原值 |
8 結論
本文提供的搜尋算法可以找出任意給定的1-Wire器件組中獨一無二的ROM碼，這是保證多點1-Wire總線應用的關鍵，已知ROM碼後就可以對逐一標明的某個1-Wire器件來進行操作。本文還對一些變量搜尋算法做了詳細論述，這些變量搜尋算法能夠查找或跳過特定類型的1-Wire器件。
或許Maxim覺得1-Wire器件的軟體開銷讓人望而生畏，是以設計了專用晶片DS2480B系列，可以實作序列槽到1-Wire線路的驅動，包括與本文檔中相同的搜尋算法，詳細資料請參閱DS2480B資料資料和應用筆記192；以及DS2490晶片，實作USB口到1-Wire橋接，也可實作了整個搜尋過程；還有一款I2C橋接1-Wire的晶片。使用這些晶片，無須編寫複雜算法，隻需向晶片發送指令即可實作多種控制，其最大優點是晶片中內建了1-Wire操作控制的硬體，省卻了1-Wire複雜的時序控制，因而其他程式設計可使用進階語言來編寫，甚至直接使用Maxim提供的平台軟體在PC上開發1-Wire應用系統。
9 附錄
《詳解3》中将給出了實作搜尋過程的例程，并給出了‘C’程式代碼，需要注意的是，Maxim并沒有給出“複位、讀寫總線”等低級1-Wire函數的C代碼，而是提示我們可以調用TMEXAPI實作，考慮到本程式在51系列平台上獨立調試，代碼中提供了這些函數。關于TMEXAPI和其它一些1-WireAPI的詳細資料請參考應用筆記155。