可适配多路并行移位操作指令及其硬件实现研究

为CROL Rd, Rs1, Rs2, #imm,这时指令格式中func域的com值是1,表示级联。Rs1、Rs2是64bit源操作数,Rs1中存放的是64bit中高32bit,Rs2中存放的是64bit中低32bit,Rd为目的操作数,运算后存放的是64bit移位的高32bit结果。下一个时钟(第二步),交换64bit的高低32bit,运算后Rd存放64bit移位的低32bit结果。

这样就在32bit的数据路径上实现了64bit的移位操作。其功能示意图如图2所示。

同理可执行循环右移操作。但在执行级联的逻辑移位操作时有所不同,进行逻辑左移时,第一步与循环移位相同,在第二步时,Rs1中存放的是64bit中低32bit,Rs2中存放的操作数是全零;进行逻辑右移时,在第一步时,Rs1中存放的是64bit中高32bit,Rs2中存放的操作数全为零,第二步与循环移位相同。

2.3 RPSI的组合执行

某些密码算法的移位操作位宽是128bit,例如IDEA算法的子密钥生成中,就用到了长字移位操作。在级联移位指令的基础上,通过指令的组合实现128bit移位操作,或者更长位宽的移位操作,例如:要完成128bit的移位,需要执行四条级联移位指令。

以128bit逻辑左移5位为例,假设R4&R3&R2&R1表示128bit待移位的数据,则执行指令CSHL Rd, R1, Rs, #5(Rs中的数是全零),得到移位后最终结果的31~0位;执行指令CSHL Rd, R2, R1, #5,得到移位后最终结果的63～32位,执行指令CSHL Rd, R3, R2, #5,得到移位后最终结果的95~64位;执行指令CSHL Rd, R4, R3, #5,得到移位后最终结果的127～96位。

再以128bit循环左移5位为例,假设R4&R3&R2&R1表示128bit待移位的数据,则执行指令CROL Rd, R1,R4,#5,得到移位后最终结果的31～0位,执行指令CROL Rd,R2,R1,#5,得到移位后最终结果的63～32位;执行指令CROL Rd,R3,R2,#5,得到移位后最终结果的95～64位;执行指令CROL Rd,R4,R2,#5,得到移位后最终结果的127～96位。

同理,可以用这种多条指令组合的方式实现256bit的移位。128bit移位操作功能示意图如图3所示。

3 RPSI的硬件实现及其性能分析

3.1 移位操作硬件实现算法研究

传统的实现方法中,基于线性反馈移位寄存器LFSR是实现移位操作的一种主要方式,LFSR通常以移1位运算为基础,循环移k位通过k次调用移1位基本运算实现,占用k个时钟周期,移位速度受移位位数的影响。因此对于移位位数较大的操作,采用LFSR进行循环移位运算很难满足高速数据处理的需求。

循环移位操作还可以看作是一类特殊的置换,采用基于BENES网络的实现方法。但是,由于移位位数k的不确定性,导致配置信息生成电路较为复杂,不利于软硬件实现。下面在对循环移位及逻辑移位分别研究的基础上,给出了基于数据选择器的实现方法。

(1) 循环移位的实现

令移位位数k=kn-12n-1+kn-22n-2+…+…k12+k0,则循环移位可以表示为: y=RSH(a,k),y的第j位y(j)可以表示为: y(j)=a((j±k)modN)

其中,执行左移操作时操作符为"-",执行右移操作时操作符为"+",N为操作数a的位宽。由此可得:

即:任意位的循环移位操作分解为若干加减2i置换操作的级联。对于循环左移而言,循环移位操作可以分解为减2i置换操作。

循环左移操作算法描述:

Input:操作数a, k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y

(1) y←a

(2) For i=n-1 downto 0 do

(3) For j= 0 to N-1 do

If ki=1 then

If j≤k then b(j)=y((j-2i)modN)

else b(j)=0

else b(j)=y(j)

(4) y=b Return (y)

当N=2n时,循环左移操作可以采用n级数据选择器实现,每一级使用N个二选一数据选择器,共计需要nN个二选一数据选择器,系统的延迟相当于n级二选一数据选择器的延迟。循环右移操作可以看作循环移位位数为N-k的循环左移操作,由此可以构造如图4所示的循环移位结构。

(2) 逻辑移位的实现

对于逻辑左移,上述算法可以修改如下:

Input:操作数 a,移位位数 k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y

① y←a

② For i=n-1 downto 0 do

③ For j= 0 to N-1 do

If ki=1 then

If j≤k then b(j)=y((j-2i)modN)

else b(j)=0

else b(j)=y(j)

④ y=b Return (y)

可以采用类似的方法对逻辑右移操作算法进行修改,本文不再赘述。在硬件实现时,可以通过将上述循环移位电路的每一个数据选择器扩展为四选一实现支持循环移位和逻辑移位的电路。

3.2 移位操作硬件单元的实现及性能分析

根据基于数据选择器的实现原理,用verilog语言实现了32bit数据路径上的移位操作硬件单元,用modelsim SE 6.0仿真软件进行了功能仿真,对于RPSI所指定的功能,均能正确完成。使用Design Compiler综合工具进行了综合,在0.18μm工艺下综合结果如表3。

由前面分析可知,要完成32bit数据路径上RPSI不同