二進制數(shù)折半查找算法在DSP上的實現(xiàn)

sub * ;與AR3所指的存儲單元的數(shù)據(jù)相減

bcnd nothere , LT ;ACC值小于0,要查找的數(shù)據(jù)不在本數(shù)列中

rptd nothere-1

bend found,EQ ;打到數(shù)據(jù)

xc 1, GT ;若ACC中的數(shù)據(jù)較大

mar *0+, AR0 ;

xc 1, LT ;若ACC中的數(shù)據(jù)較小

mar *0-, AR0 ;

mar *BR0+, AR3 ;查找空間減半

lacc LOOK

sub *

;***********************

;未找到,將ACC置0后返回

;***********************

nothere retd

zac

nop

;***********************

;找到數(shù)據(jù),將數(shù)據(jù)地址存放在ACC中返回

;***********************

found ldp #0

apl #0fffeh,PMST ;復位PMST位

retd

lamm AR3 ;存數(shù)據(jù)地址

nop

3 輔助說明

程序中較為詳細的介紹了每個步驟所需完成的功能,下面就一些關(guān)鍵的地方進行一些說明。

（1）程序如果找到查找的數(shù)據(jù)則返回數(shù)據(jù)所在的地址,未找到則送0至ACC寄存器。

（2）程序中的mar BR0+,AR3是將當前AR（輔助寄存器）指定的數(shù)據(jù)存儲器的內(nèi)容按逆向進位方式加AR0的內(nèi)容。由于在該指令前有一條mar*,AR0指令,這條指令指定了下一條指令的輔助寄存器。因此在執(zhí)行MAR BR0+,AR3時,實際上是輔助寄存器AR0與自身逆向相位相加：

其結(jié)果是數(shù)據(jù)為原來的一半。實際上這條指令確定了折半查找算法中的“中間位置”。

（3）samm BRCR指令程序執(zhí)行是是與rptp nothere-1指令配合使用的。Samm指令的功能是將循環(huán)次數(shù)的值（這里是11）存放在BRCR中。BRCR（Block Repeat Counter Register）是個16位的寄存器,用于存放程序塊重復操作的次數(shù)。Rptp指令是重復操作指令,它的功能是重復執(zhí)行下一條指令到該指令指定的地址之內(nèi)的程序代碼,重復執(zhí)行的次數(shù)由brcr決定。在上面的程序中,RPTR指令指定的地址是nothere-1,也就是說：重復執(zhí)行的程序代碼從bcnd found直到nthere的前一指令Sub*。

xc指令的用法如下：

xc K[,COND1][COND2][,…]

指令中的K=1或2。COND1、COND2是條件。xc指令功能是在條件滿足的情況下,執(zhí)行該指令下面的K條指令,K為1,則執(zhí)行一條指令,K為2則執(zhí)行兩條指令。條件不滿足就執(zhí)行K條NOP指令。

（4）該源程序是采用TMS320C5X的指令集編寫的,如果是TMS320C5X系列的DSP,則可以直接將上面給出的程序作為一個子程序來使用。而對于TMS320C2XX系列的DSP來說,由于TMS320C5X的指令對TMS320C2XX的指令是向下兼容的,所以在編寫TMS320C2XX的折半查找程序時應(yīng)作一些修改,比如前面提到的程序中的samm指令,在TMS320C2XX指令集中就沒有。這樣,如果希望用TMS320C2XX來實現(xiàn)本例中的samm語句 功能,則可以將重復操作的次數(shù)存放在內(nèi)部的RAM中,再配合TMS320C2XX循環(huán)指令來完成samm與rptp指令的功能。但這樣做將導致程序執(zhí)行效率的降低。也可以認為TMS320C2XX的數(shù)據(jù)處理能力較TMS320C5X為弱,其原因主要是兩者指令集的差異。