二进制数折半查找算法在DSP上的实现

sub * ;与AR3所指的存储单元的数据相减

bcnd nothere , LT ;ACC值小于0,要查找的数据不在本数列中

rptd nothere-1

bend found,EQ ;打到数据

xc 1, GT ;若ACC中的数据较大

mar *0+, AR0 ;

xc 1, LT ;若ACC中的数据较小

mar *0-, AR0 ;

mar *BR0+, AR3 ;查找空间减半

lacc LOOK

sub *

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

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

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

nothere retd

zac

nop

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

;找到数据,将数据地址存放在ACC中返回

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

found ldp #0

apl #0fffeh,PMST ;复位PMST位

retd

lamm AR3 ;存数据地址

nop

3 辅助说明

程序中较为详细的介绍了每个步骤所需完成的功能,下面就一些关键的地方进行一些说明。

（1）程序如果找到查找的数据则返回数据所在的地址,未找到则送0至ACC寄存器。

（2）程序中的mar BR0+,AR3是将当前AR（辅助寄存器）指定的数据存储器的内容按逆向进位方式加AR0的内容。由于在该指令前有一条mar*,AR0指令,这条指令指定了下一条指令的辅助寄存器。因此在执行MAR BR0+,AR3时,实际上是辅助寄存器AR0与自身逆向相位相加：

其结果是数据为原来的一半。实际上这条指令确定了折半查找算法中的“中间位置”。

（3）samm BRCR指令程序执行是是与rptp nothere-1指令配合使用的。Samm指令的功能是将循环次数的值（这里是11）存放在BRCR中。BRCR（Block Repeat Counter Register）是个16位的寄存器,用于存放程序块重复操作的次数。Rptp指令是重复操作指令,它的功能是重复执行下一条指令到该指令指定的地址之内的程序代码,重复执行的次数由brcr决定。在上面的程序中,RPTR指令指定的地址是nothere-1,也就是说：重复执行的程序代码从bcnd found直到nthere的前一指令Sub*。

xc指令的用法如下：

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

指令中的K=1或2。COND1、COND2是条件。xc指令功能是在条件满足的情况下,执行该指令下面的K条指令,K为1,则执行一条指令,K为2则执行两条指令。条件不满足就执行K条NOP指令。

（4）该源程序是采用TMS320C5X的指令集编写的,如果是TMS320C5X系列的DSP,则可以直接将上面给出的程序作为一个子程序来使用。而对于TMS320C2XX系列的DSP来说,由于TMS320C5X的指令对TMS320C2XX的指令是向下兼容的,所以在编写TMS320C2XX的折半查找程序时应作一些修改,比如前面提到的程序中的samm指令,在TMS320C2XX指令集中就没有。这样,如果希望用TMS320C2XX来实现本例中的samm语句 功能,则可以将重复操作的次数存放在内部的RAM中,再配合TMS320C2XX循环指令来完成samm与rptp指令的功能。但这样做将导致程序执行效率的降低。也可以认为TMS320C2XX的数据处理能力较TMS320C5X为弱,其原因主要是两者指令集的差异。