陳 帆，徐金甫，常忠祥

（信息工程大學(xué) 密碼工程學(xué)院，河南 鄭州450001）

0 引 言

插入排序操作可以將一個(gè)序列轉(zhuǎn)化成任意的指定序列，在密碼算法中有著廣泛的應(yīng)用，尤其是硬件級(jí)的可重構(gòu)密碼算法的實(shí)現(xiàn)方面應(yīng)用普遍［1］。然而插入排序算法的硬件實(shí)現(xiàn)過(guò)程比較復(fù)雜，如何高效、快速的實(shí)現(xiàn)成為密碼算法硬件實(shí)現(xiàn)技術(shù)的研究熱點(diǎn)之一。

目前主流的方法一般基于ibutterfly （inverse butterfly）網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)插入排序算法，這其中的典型代表有Kolay S等結(jié)合歸并算法的思想，利用雙ibutterfly 網(wǎng)絡(luò)設(shè)計(jì)實(shí)現(xiàn)的GRP算法［2，3］，其能夠快速實(shí)現(xiàn)序列的插入排序操作，提高插入排序操作的實(shí)現(xiàn)速度。然而該GRP算法實(shí)現(xiàn)過(guò)程沒(méi)有考慮到序列的自身特點(diǎn)，過(guò)多的使用網(wǎng)絡(luò)導(dǎo)致序列實(shí)現(xiàn)過(guò)于復(fù)雜。據(jù)此，本文針對(duì)該算法進(jìn)行了研究與并提出了改進(jìn)方案。

文中首先對(duì)ibutterfly網(wǎng)絡(luò)的置換原理與特性進(jìn)行了分析，提出了一種利用單個(gè)ibutterfly網(wǎng)絡(luò)實(shí)現(xiàn)插入排序操作復(fù)雜度評(píng)估的方法，其次基于該評(píng)估方法搜尋優(yōu)選方案，對(duì)GRP算法進(jìn)行了改進(jìn)，提出一種能夠根據(jù)目標(biāo)序列特點(diǎn)選用不同工作模式的算法，最后給出了改進(jìn)后方案的實(shí)現(xiàn)效率和性能指標(biāo)。

1 ibutterfly網(wǎng)絡(luò)與GRP算法

1.1 butterfly/ibutterfly網(wǎng)絡(luò)分析

ibutterfly網(wǎng)絡(luò)是實(shí)現(xiàn)輸入數(shù)據(jù)與輸出數(shù)據(jù)一一對(duì)應(yīng)的排序的較好選擇［4，5］。圖1表示一個(gè)n－bit的ibutterfly網(wǎng)絡(luò)（n＝8），該網(wǎng)絡(luò)有l(wèi)g（n）級(jí)，從左到右依次為第一級(jí)、第二級(jí)、第三級(jí) （最右邊），每一級(jí)由n/2 個(gè)2 輸入開(kāi)關(guān)構(gòu)成，而每一個(gè)2輸入開(kāi)關(guān)由兩個(gè)二選一數(shù)據(jù)選擇器組成。

圖1 8－8ibutterfly網(wǎng)絡(luò)

數(shù)據(jù)A、B在開(kāi)關(guān)控制信息Sel的控制下選擇交叉或者直通。n－bit的數(shù)據(jù)在進(jìn)入ibutterfly網(wǎng)絡(luò)各級(jí)時(shí)以位置間距為2i－1（i為級(jí)數(shù)）的行兩兩分組。如第一級(jí)ibutterfly網(wǎng)絡(luò)中位置7的數(shù)據(jù)與位置6的數(shù)據(jù)就組成了一個(gè)數(shù)據(jù)組，第二級(jí)中位置7的數(shù)據(jù)與位置5的數(shù)據(jù)就組成了一個(gè)數(shù)據(jù)組。然后將分組后的數(shù)據(jù)輸入到2輸入開(kāi)關(guān)中，在控制信息sel的作用下 “路由”出相應(yīng)結(jié)果。Butterfly網(wǎng)絡(luò)是ibutterfly網(wǎng)絡(luò)的逆結(jié)構(gòu)［6］，其數(shù)據(jù)間距為2lg（n）－i。

該網(wǎng)絡(luò)具有很好的可拆分性和迭代性，將n—n的ibutterfly網(wǎng)絡(luò)的最外層去掉，可以看作兩個(gè) （n/2）— （n/2）的子網(wǎng)絡(luò)［7］。如果實(shí)現(xiàn)位寬為n/2的操作，只需將網(wǎng)絡(luò)最外一層開(kāi)關(guān)置為直通，剩余的控制信息正常配置即可。輸入數(shù)據(jù)在各級(jí)移位的規(guī)律性較強(qiáng)，對(duì)于不同類型的置換操作，控制信息便于實(shí)時(shí)生成［8］。

通過(guò)對(duì)ibutterfly網(wǎng)絡(luò)的分析與研究，總結(jié)出如圖2所示的排序方式。數(shù)據(jù)進(jìn)入ibutterfly網(wǎng)絡(luò)后，網(wǎng)絡(luò)能夠?qū)崿F(xiàn)數(shù)據(jù)按照控制序列中 “0”、 “1”指示排序序列。即將控制序列中為 “1”的控制位對(duì)應(yīng)的原數(shù)據(jù)依次排在新序列右側(cè)，將控制序列中為 “0”的控制位對(duì)應(yīng)的原數(shù)據(jù)依次逆序排在新序列的左側(cè)。

圖2 ibutterfly網(wǎng)絡(luò)排序方式

由ibutterfly網(wǎng)絡(luò)分析得出的這一排序功能可知：由于控制位列中 “0”所對(duì)應(yīng)的原數(shù)據(jù)在進(jìn)入到新序列后順序顛倒了，所以這種實(shí)現(xiàn)方式是從右側(cè)開(kāi)始先將與目的序列同序的數(shù)據(jù)放置后，再將剩余與目的序列順序不同的序列顛倒；如此重復(fù)進(jìn)行，直至完成目的序列順序調(diào)整。從上述分析發(fā)現(xiàn)，目的序列中數(shù)據(jù)的排列順序?qū)τ诓迦肱判虻挠绊懯呛艽蟮模虼藢?duì)于序列數(shù)據(jù)排列順序的研究是很有必要的。

1.2 GRP算法分析

GRP算法是一種快速高效排序算法，它利用歸并的思想將一個(gè)大的排序任務(wù)分割成若干個(gè)子排序任務(wù)，再將子排序任務(wù)兩兩組合，并通過(guò)指令完成各組合子排序任務(wù)，重復(fù)此操作直至完成最終排序任務(wù)［9，10］。完成全部排序任務(wù)所需的指令條數(shù)為lg（n）條，很好地限制了指令周期數(shù)，即提高了排序操作的運(yùn)行速度。

GRP算法在實(shí)現(xiàn)時(shí)是由兩個(gè)ibutterfly網(wǎng)絡(luò)并行連接而成，通過(guò)源序列多次通過(guò)ibutterfly網(wǎng)絡(luò)實(shí)現(xiàn)序列的插入排序［11］。

如圖3所示，GRP算法的運(yùn)算實(shí)現(xiàn)過(guò)程共分為3個(gè)步驟：①根據(jù)歸并算法得到控制信息，將控制信息和控制信息的逆分別同源序列相與得到兩個(gè)互補(bǔ)序列。②將兩個(gè)互補(bǔ)序列分別送入各自對(duì)應(yīng)的ibutterfly網(wǎng)絡(luò)，使得兩個(gè)互補(bǔ)序列其中一個(gè)序列中數(shù)據(jù)按指定順序序列排列在輸出序列的左側(cè)，同時(shí)另一個(gè)序列中數(shù)據(jù)按指定順序序列排列在輸出序列的右側(cè)。③將兩個(gè)網(wǎng)絡(luò)的輸出序列相或，合并為一個(gè)序列作為輸出，即可得到目的序列。

圖3 GRP算法硬件實(shí)現(xiàn)電路

忽略GRP實(shí)現(xiàn)細(xì)節(jié)，GRP算法的實(shí)現(xiàn)則簡(jiǎn)化成根據(jù)控制序列中 “0”、 “1”指示排列序列。即將控制序列中為“1”的控制位對(duì)應(yīng)的原數(shù)據(jù)依次排在新序列右側(cè)，將控制序列中為 “0”的控制位對(duì)應(yīng)的原數(shù)據(jù)依次排在新序列左側(cè)，以此實(shí)現(xiàn)序列的插入排序。

GRP算法結(jié)合了ibutterfly網(wǎng)絡(luò)與歸并算法的優(yōu)勢(shì)，能夠快速而簡(jiǎn)便地實(shí)現(xiàn)插入排序操作。但由于GRP算法沒(méi)有考慮不同序列的特點(diǎn)，在針對(duì)某些特殊序列時(shí)，存在嚴(yán)重不足。

例如實(shí)現(xiàn)8bit序列 （0，1，2，3，4，5，6，7）排序成 （7，6，5，4，3，2，0，1）。對(duì)于GRP 網(wǎng)絡(luò)，根據(jù)排序原則，第一條控制序列為 （0，0，1，0，1，0，1，0），將源序列排列成 （0，1，3，5，7，2，4，6）；第二條控制序列為 （1，1，0，1，0，0，1，0），將序列排列成 （3，7，2，6，0，1，5，4）；第三條控制序列為 （1，0，1，0，1，1，0，0），得到目的序列 （7，6，5，4，3，2，0，1）。實(shí)現(xiàn)該操作共需3條指令。如果使用單個(gè)ibutterfly網(wǎng)絡(luò)，則只需執(zhí)行1 條控制序列，即 （1，1，0，0，0，0，0，0）。之所以如此，是因?yàn)镚RP算法只是針對(duì)普遍序列的一個(gè)算法，沒(méi)有考慮不同序列的特點(diǎn)。

2 GRP算法的改進(jìn)

2.1 插入排序算法復(fù)雜度評(píng)估算法

定義1 正序列：在一個(gè)給定整數(shù)序列A1，A2，……Ai，……Aj，……An中，若子序列Ai，……Aj滿足以下條件：i＜i＋1＜i＋2＜……＜j－1＜j，i－1＞i或者i＝1，j＋1＜j或者j＝n，則該子序列為正序列。

例如：對(duì)于源序列為 ｛0，1，2，3，4，5，6，7｝，給定的一個(gè)序列 ｛1，2，5，7，0，3，6，4｝，其正序列為｛（1，2，5，7），（0，3，6），（4）｝。

定義2 逆序列：在一個(gè)給定整數(shù)序列A1，A2，……Ai，……Aj，……An，如子序列Ai，……Aj滿足以下條件：i＞i＋1＞i＋2＞……＞j－1＞j，i－1＜i或者i＝1，j＋1＞j或者j＝n，則該子序列為正序列。

例如：對(duì)于源序列為 ｛0，1，2，3，4，5，6，7｝，給定的一個(gè)序列 ｛1，2，5，4，7，3，6，0｝，其逆序列為｛（1），（2），（5，4），（7，3），（6，0）｝。

用Numh來(lái)表示目的序列中正序列個(gè)數(shù)。用Numd來(lái)表示目的序列中降序序列個(gè)數(shù)。例如：對(duì)于源序列為 ｛0，1，2，3，4，5，6，7｝，An＝ ｛1，2，5，7，0，3，6，4｝，Bn＝ ｛1，2，5，4，7，3，6，0｝則Numh（An）＝2，Numd（Bn）＝5。

基于ibutterfly網(wǎng)絡(luò)的插入排序算法指令條數(shù)的判決值用Num 來(lái)表示。（通過(guò)Num 能夠成為插入排序算法復(fù)雜度評(píng)估值）在檢測(cè)目的序列開(kāi)始前，Num＝ “0”。檢測(cè)目的序列開(kāi)始后，按照規(guī)定方向輪流檢測(cè)正向序列和逆向序列，每檢測(cè)出一個(gè)單向序列則使Num 加 “1”。

例如：對(duì)于源序列為 ｛0，1，2，3，4，5，6，7｝，目的序列為 ｛1，2，5，7，0，3，6，4｝，檢測(cè)規(guī)則定位為從左往右。

插入算法指令條數(shù)判決值的計(jì)算步驟為：

（1）檢測(cè)得出第一組正向序列為 （1，2，5，7），則Num＝1；

（2）繼續(xù)檢測(cè)逆向序列為 （0），則Num＝2；

（3）繼續(xù)檢測(cè)正向序列為 （3，6），則Num＝3；

（4）繼續(xù)檢測(cè)逆向序列為 （4），則Num＝4，檢測(cè)完畢。

所以該例中判決值Num 最終為4。

2.2 單個(gè)ibutterfly網(wǎng)絡(luò)插入排序算法研究

利用單獨(dú)一個(gè)ibutterfly網(wǎng)絡(luò)，讓數(shù)據(jù)多次通過(guò)網(wǎng)絡(luò)實(shí)現(xiàn)插入排序。假設(shè)存在一個(gè)n－bit的整數(shù)序列An，要求通過(guò)比特置換得到指定序列Bn。An為源序列，Bn為目的序列。按照ibutterfly網(wǎng)絡(luò)的排序方式實(shí)現(xiàn)排序時(shí)，實(shí)現(xiàn)排序所需指令條數(shù)的判斷方法為：對(duì)序列Bn按照從右向左的規(guī)則計(jì)算插入指令條數(shù)判決值；對(duì)序列Bn檢測(cè)完畢后得出判決值為Num；則從源序列向目的序列轉(zhuǎn)換所需要的指令個(gè)數(shù)為 （Num－1）條。

例：源序列為 ｛7，6，5，4，3，2，1，0｝，目的序列為 ｛3，4，2，5，1，6，0，7｝。因此由定義可知，在本次排序中，阿拉伯?dāng)?shù)字從高到低為正序列，從低到高為逆序列。以此來(lái)檢測(cè)目的序列。從右向左進(jìn)行檢測(cè)指令個(gè)數(shù)判決值，檢測(cè)結(jié)果為： ｛7｝， ｛0｝， ｛6｝， ｛1｝， ｛5｝， ｛2｝，｛4｝，｛3｝。所以Num＝8，指令條數(shù)即為n＝Num－1＝7。

假設(shè)源序列為 ｛7，6，5，4，3，2，1，0｝，目的序列為 ｛2，7，4，3，5，1，0，6｝。同理檢測(cè)，檢測(cè)結(jié)果為：｛6｝，｛0｝，｛5，1｝，｛3｝，｛7，4｝，｛2｝。所以指令條數(shù)為n＝5。

通過(guò)實(shí)驗(yàn)可知，多次通過(guò)ibutterfly網(wǎng)絡(luò)可以實(shí)現(xiàn)任意目的序列的插入排序操作，且根據(jù)目的序列不同特點(diǎn)，實(shí)現(xiàn)排序操作時(shí)所需指令條數(shù)差異較大。利用ibutterfly 網(wǎng)絡(luò)，由源序列 （0，1，2，3，4，5，6，7）通過(guò)y條指令實(shí)現(xiàn)向任意排列方式的目的序列排序，指令條數(shù)y的值在0～7之間。通過(guò)matlab仿真，對(duì)8bit數(shù)據(jù)的排序操作進(jìn)行統(tǒng)計(jì)，使用y條指令能夠?qū)崿F(xiàn)插入排序的目的序列個(gè)數(shù)及占任意排序組合序列總數(shù)的比例結(jié)果見(jiàn)表1。

表1 8比特排序指令個(gè)數(shù)

通過(guò)統(tǒng)計(jì)可知，8bit序列的不同排布方式共有40320種，且實(shí)現(xiàn)排序操作占用不超過(guò)3條指令 （包含3條指令）的序列個(gè)數(shù)共占總序列數(shù)的19.37%。

因?yàn)橥ㄟ^(guò)單一的ibutterfly網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)排序時(shí)，使用1條、2條、3條指令的序列所需指令條數(shù)與GRP 算法是不一樣的，且只用到一個(gè)ibutterfly網(wǎng)絡(luò)。所以將改進(jìn)的GRP算法針對(duì)這些特殊序列進(jìn)行特殊操作，能有效提升GRP算法的速度和效率。

2.3 GRP算法的改進(jìn)

由2.2節(jié)可知，在8bit序列排序過(guò)程中，在全部目的序列中有19%左右的序列在由源序列排序過(guò)程中只需要3條以下的指令個(gè)數(shù) （包括3條）。將這些序列定義為特殊序列。對(duì)于這些特殊的序列而言，可通過(guò)單個(gè)ibutterfly網(wǎng)絡(luò)很方便的就能實(shí)現(xiàn)，而GRP算法中依然需要兩個(gè)ibutterfly網(wǎng)絡(luò)配合完成。不能發(fā)揮出GRP算法的優(yōu)勢(shì)，反而增加了實(shí)現(xiàn)的復(fù)雜程度。

基于以上分析，本文提出GRP算法的改進(jìn)算法，改進(jìn)后實(shí)現(xiàn)電路結(jié)構(gòu)如圖4所示。

圖4 GRP改進(jìn)算法的電路結(jié)構(gòu)

在改進(jìn)的GRP算法中，通過(guò)模式選擇信號(hào)控制兩個(gè)二選一數(shù)據(jù)選擇器。當(dāng)模式為單個(gè)ibutterfly網(wǎng)絡(luò)工作時(shí)，則通過(guò)模式選擇信號(hào)控制數(shù)據(jù)選擇器選擇全 “1”序列進(jìn)入電路，與源序列相與，同時(shí)在輸出時(shí)選擇單個(gè)ibutterfly輸出的結(jié)果作為最終輸出。當(dāng)模式為GRP操作時(shí)，則通過(guò)模式選擇信號(hào)控制數(shù)據(jù)選擇器選擇控制序列進(jìn)入電路，與源序列相與，同時(shí)在輸出時(shí)將兩個(gè)ibutterfly網(wǎng)絡(luò)結(jié)果相或后作為最終輸出。

改進(jìn)后GRP算法執(zhí)行時(shí)，在開(kāi)始排序操作前，首先通過(guò)對(duì)目的序列特點(diǎn)的分析，先利用2.1節(jié)提出的評(píng)估算法判斷序列通過(guò)單個(gè)ibutterfly網(wǎng)絡(luò)所需指令個(gè)數(shù)。如果通過(guò)單個(gè)ibutterfly網(wǎng)絡(luò)所需的指令個(gè)數(shù)已經(jīng)小于lg（n）條指令了。則發(fā)出模式選擇信號(hào)，啟動(dòng)單個(gè)ibutterfly網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)插入排序操作。

如果通過(guò)2.1節(jié)評(píng)估算法得出通過(guò)單個(gè)ibutterfly網(wǎng)絡(luò)所需的指令個(gè)數(shù)大于lg（n）條指令，則發(fā)出模式選擇信號(hào)，啟動(dòng)全部網(wǎng)絡(luò)共同工作，完成插入排序操作。

3 性能評(píng)估

以8bit位寬序列為例，在實(shí)現(xiàn)排序過(guò)程中，特殊序列占整體序列的比重由表1可知，其中有19.37%數(shù)量的序列為特殊序列，不需使用GRP網(wǎng)絡(luò)，而只需開(kāi)啟一個(gè)ibutterfly網(wǎng)絡(luò)，用與GRP相同的指令數(shù)即可實(shí)現(xiàn)排序操作。如圖5所示，特殊序列的數(shù)量會(huì)隨數(shù)據(jù)位寬的增加而顯著增加。所以隨著位寬的增加，GRP算法改進(jìn)的效果會(huì)更加明顯。

硬件實(shí)現(xiàn)前后硬件開(kāi)銷對(duì)比見(jiàn)表2。

圖5 特殊序列數(shù)量隨數(shù)據(jù)位寬變化趨勢(shì)

表2 硬件實(shí)現(xiàn)前后硬件開(kāi)銷對(duì)比

綜合分析，在針對(duì)一些特殊插入排序操作時(shí)，例如DES加密運(yùn)算中的P序操作，恰好使用的就是這些特殊序列。因此本文設(shè)計(jì)雖然略微增加了GRP硬件實(shí)現(xiàn)資源，但彌補(bǔ)了其應(yīng)用的靈活性。

本文提出結(jié)合序列自身特點(diǎn)對(duì)GRP算法進(jìn)行改進(jìn)，改進(jìn)后的GRP 算法針對(duì)不同的序列特點(diǎn)選擇相應(yīng)的工作模式，有效地增強(qiáng)了GRP算法的速度和效率。

4 結(jié)束語(yǔ)

由于GRP算法具有自身不足，即實(shí)現(xiàn)特殊序列的插入排序時(shí)效率不高。因此本文針對(duì)GRP算法的不足，提出了GRP算法的改進(jìn)的算法。通過(guò)加入序列自身特點(diǎn)的分析和歸納，提出了一種基于ibutterfly網(wǎng)絡(luò)下的簡(jiǎn)便插入排序操作復(fù)雜度評(píng)估規(guī)律。通過(guò)分析比較，通過(guò)評(píng)估規(guī)律對(duì)序列進(jìn)行分析后，在改進(jìn)后的GRP 算法中選擇合適的工作模式，能夠高效地實(shí)現(xiàn)插入排序操作。

［1］Nan Longmei，Dai Zhibin.Design and implementation of configurable extract instructions targeted at stream cipher processing ［C］//Sth International Conference on ASIC，2009.

［2］Yedidya Hilewitz.A new basis for shifters in general－purpose processors or exiting and advanced bit manipulations［J］.IEEE Transactions on Computers，2009，58 （8）：1035－1048.

［3］Kolay S，Khurana S，Sadhukhan A，et al.Bit permutation instructions for accelerating software cryptography ［C］//IEEE Conference Publications，2013：963－968.

［4］Li Hongyan，Gao Fei.Design and implementation of reconfigurable bit permutation system based on Waksman network［C］//IEEE Conference Publications，2010：113－116.

［5］Su Yang.Research of design technology of reconfigurable shift unit based on multilevel interconnection ［J］.Intelligent System and Applied Material，Advanced Materials Research，Advanced Materials Research，2012，466：1065－1069.

［6］Hilewitz Yedidya.Advanced bit manipulation instructions：Architecture，implementation and applications［D］.New Jersey：Princeton University，2008.

［7］Azaria Paz.A theory of decomposition into prime factors of layered interconnection networks ［J］.Discrete Applied Mathematics，2011，159 （7）：628－649

［8］John Garoflakis，Eleftherios Stergiou.An analytical model for the performance evaluation of multistage interconnection networks with two class priorities ［J］.Future Generation Computer Systems，2013，29 （1）：114－129.

［9］David Arroyo，JesusDiaz FB Rodriguez.Cryptanalysis of a one round chaos－based substitution permutation network ［J］.Signal Processing，2013，93 （5）：1358－1364.

［10］Hilewitz Y，Ruby B Lee.Fast bit gather，bit scatter and bit permutation instructions for commodity microprocessors ［J］.J Signal Processing Systems，2008，53 （1－2）：145－169.

［11］John Garofalakis，Eleftherios Stergiou.Analytical model for the performance evaluation of multilayer multistage interconnection networks servicing unicast and multicast traffic by partial multicast operation ［J］.Performance Evaluation，2010，67 （10）：959－976.