一種在嵌入式系統中實現乘法運算的方法和裝置的製作方法

2023-05-13 03:35:16

專利名稱：一種在嵌入式系統中實現乘法運算的方法和裝置的製作方法
技術領域：
本發明涉及密碼學領域，尤其涉及一種在嵌入式系統中實現乘法運算的方法和裝置。
背景技術：
許多已知的計算機算法都需要進行乘法運算，如公鑰加密等算法。現有技術中可以通過中央處理器(Central Processing Unit,CPU)實現乘法運算。但是當乘法運算中的數據為大數時，CPU執行乘法運算時的運算速度比較低。發明內容
本發明的實施例提供一種在嵌入式系統中實現乘法運算的方法和裝置，能夠提高乘法運算的運算速度。
一方面，提供一種在嵌入式系統中實現乘法運算的方法，包括
(1).接收到乘法運算指令時，獲取所述乘法運算指令中第一待處理數據和第二待處理數據；
(2).判斷所述第一待處理數據的比特位位數與所述第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數；
如果是，返回錯誤信息；如果否，執行(3)；
(3).對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據；
(4).根據所述運算裝置支持的比特位位數生成第一參數；
(5).將所述第三待處理數據的最低位、所述第四待處理數據的最低位分別與所述第一參數的最低位對齊；
(6).將所述第三待處理數據按預設位長由最低位到最高位進行劃分；
(J).根據所述預設位長對應的比特位位數生成第二參數，並根據所述第一參數和所述第二參數生成第三參數；
(8).將當前偏移單元中的數據和所述第四待處理數據的乘積與當前迭代數據相加，得到第一數據；
偏移單元的初始單元為對所述第三待處理數據進行劃分得到的第一個單元，迭代數據的初始值為0 ；
(9).將所述第二參數作為模數，對所述第一數據與所述第三參數進行模乘運算， 得到第二數據；
(10).將所述第一參數和所述第二數據的乘積與所述第一數據進行加法運算，得到第三數據；
(11).將所述第三數據右移所述預設位長，並將移位後得到的數據替換當前迭代5數據；
(12).判斷當前偏移單元是否為最後一個單元；
如果是，執行(14)；如果否，執行(13)；
(13).將偏移單元指向當前偏移單元的下一個單元，返回(8)；
(14).判斷當前迭代數據是否小於所述第一參數；
如果是，執行(16)；如果否，執行(15)；
(15).將當前迭代數據自減所述第一參數；
(16).存儲或輸出指示所述第一待處理數據與所述第二待處理數據乘積的當前迭代數據。
其中，所述對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據，包括
在所述第一待處理數據的最高位前補零生成第三待處理數據，在所述第二待處理數據的最高位前補零生成第四待處理數據，所述第三待處理數據與所述第四待處理數據的比特位位數與所述運算裝置支持的比特位位數相同。
其中，所述根據所述運算裝置支持的比特位位數生成第一參數，包括
生成各個比特位均置1的第一參數，所述第一參數的比特位位數與所述運算裝置支持的比特位位數相同。
其中，所述預設位長對應的比特位位數，具體為
能整除所述運算裝置支持的比特位位數的整數。
其中，所述根據所述預設位長對應的比特位位數生成第二參數，包括
以2為底數，以所述預設位長對應的比特位位數為冪數生成所述第二參數。
其中，所述根據所述第一參數和所述第二參數生成第三參數，包括
生成所述第二參數的值減去所述第一參數關於所述第二參數的乘法逆元的差值；
生成值與所述差值相同的第三參數。另一方面，提供一種在嵌入式系統中實現乘法運算的裝置，包括
待處理數據獲取模塊，用於接收到乘法運算指令時，獲取所述乘法運算指令中第一待處理數據和第二待處理數據；
第一判斷模塊，用於判斷所述第一待處理數據的比特位位數與所述第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數；
所述補位模塊，用於在所述第一判斷模塊判斷結果為是時對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據；
第一參數生成模塊，用於根據所述運算裝置支持的比特位位數生成第一參數；
對齊模塊，用於將所述第三待處理數據的最低位、所述第四待處理數據的最低位分別與所述第一參數的最低位對齊；
劃分模塊，用於將所述第三待處理數據按預設位長由最低位到最高位進行劃分；6
第二參數生成模塊，用於根據所述預設位長對應的比特位位數生成第二參數，並根據所述第一參數和所述第二參數生成第三參數；
第一數據生成模塊，用於將當前偏移單元中的數據和所述第四待處理數據的乘積與當前迭代數據相加，得到第一數據；
所述偏移單元的初始單元為所述第一單元，所述迭代數據的初始值為0 ；
第二數據生成模塊，用於將所述第二參數作為模數，對所述第一數據與所述第三參數進行模乘運算，得到第二數據；
第三數據處理模塊，用於將所述第一參數和所述第二數據的乘積與所述第一數據進行加法運算，得到第三數據；
數據替換模塊，用於將所述第三數據右移所述預設位長後得到的數據替換當前迭代數據；
第二判斷模塊，用於判斷當前偏移單元是否為最後一個單元；
所述移位模塊，用於在所述第二判斷模塊判斷結果為否時將偏移單元指向當前偏移單元的下一個單元，返回第一數據生成模塊；
所述第三判斷模塊，用於在所述第二判斷模塊判斷結果為是時判斷當前迭代數據是否小於所述第一參數；
所述自減模塊，用於在所述第三判斷模塊判斷結果為否時將當前迭代數據自減所述第一參數；
所述輸出模塊，用於在所述第三判斷模塊判斷結果為是時存儲或輸出指示所述第一待處理數據與所述第二待處理數據乘積的當前迭代數據。
其中，所述補位模塊，包括
補位子模塊，用於在所述第一待處理數據的最高位前補零生成第三待處理數據， 在所述第二待處理數據的最高位前補零生成第四待處理數據，所述第三待處理數據與所述第四待處理數據的比特位位數與所述運算裝置支持的比特位位數相同。
其中，所述第一參數生成模塊，包括
第一生成子模塊，用於生成各個比特位均置1的第一參數，所述第一參數的比特位位數與所述運算裝置支持的比特位位數相同。
其中，所述預設位長對應的比特位位數，具體為
能整除所述運算裝置支持的比特位位數的整數。
其中，所述第二參數生成模塊，包括
第二生成子模塊，以2為底數，以所述預設位長對應的比特位位數為冪數生成第二參數的值。
其中，所述第二參數生成模塊，包括
第三生成子模塊，用於生成所述第二參數的值減去所述第一參數關於所述第二參數的乘法逆元的差值；
第四生成子模塊，用於生成值與所述差值相同的第三參數。
本發明實施例提供的在嵌入式系統中實現乘法運算的方法和裝置，在乘法運算指令中第一待處理數據比特位位數和第二待處理數據的比特位位數之和小於運算裝置支持的比特位位數時，可以首先將該第一待處理數據和第二待處理數據進行補位，得到第三待處理數據和第四待處理數據；然後在第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊時，將第三待處理數據按預設位長進行劃分，並分別生成第一參數、第二參數和第三參數；最後通過該第一參數、第二參數和第三參數對當前偏移單元中的數據和第四待處理數據進行處理，直到當前偏移單元為最後一個單元時，根據當前迭代數據與第一參數的大小關係，對當前迭代數據進行處理，得到指示第一待處理數據和第二待處理數據乘積的當前迭代數據。本發明實施例提供的技術方案，由於通過模乘算法實現相乘的運算，使得乘法運算的速度得到提高，解決了現有技術中CPU執行乘法運算時的運算速度比較低的問題。


為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
圖1為本發明實施例一提供的一種在嵌入式系統中實現乘法運算的方法的流程圖2為本發明實施例二提供的另一種在嵌入式系統中實現乘法運算的方法的流程圖3為本發明實施例三提供的在一種嵌入式系統中實現乘法運算的裝置的結構示意圖4為圖3所示的在嵌入式系統中實現乘法運算的裝置中補位模塊的結構示意圖5為圖3所示的在嵌入式系統中實現乘法運算的裝置中第一參數生成模塊的結構示意圖6為圖3所示的在嵌入式系統中實現乘法運算的裝置中第二參數生成模塊的結構示意圖一；
圖7為圖3所示的在嵌入式系統中實現乘法運算的裝置中第二參數生成模塊的結構示意圖二。
具體實施方式
下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
為了解決現有技術執行乘法運算的運算速度比較低的問題，本發明實施例提供了一種在嵌入式系統中實現乘法運算的方法和裝置。
如圖1所示，本發明實施例一提供的一種在嵌入式系統中實現乘法運算的方法， 包括
步驟101，接收到乘法運算指令時，獲取該乘法運算指令中第一待處理數據和第二待處理數據。
在本實施例中，步驟101中乘法運算指令可以為計算該第一待處理數據和第二待處理數據乘積的指令。具體的，該第一待處理數據和第二待處理數據可以均為大數，可以為其他數據，在此不作限制。
步驟102，判斷該第一待處理數據的比特位位數和第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數，是則執行步驟103，否則執行步驟104。
在本實施例中，由於運算裝置的配置決定其允許支持的比特位位數；而當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可能產生運算錯誤；因此在進行乘法運算之前，需要首先通過步驟102判斷第一待處理數據的比特位位數和第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數。
在本實施例中，當通過步驟102確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可以通過步驟103返回錯誤信息；當通過步驟102確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和不大於運算裝置支持的比特位位數時，可以通過步驟104對第一待處理數據和第二待處理數據分別進行補位。
步驟103，返回錯誤信息。
在本實施例中，由於當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，對第一待處理數據和第二待處理數據進行乘法運算的過程中可能產生運算錯誤，因此當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可以通過步驟103返回錯誤信肩、ο
步驟104，對第一待處理數據進行補位，生成比特位位數與運算裝置支持的比特位位數相同的第三待處理數據，對第二待處理數據進行補位，生成比特位位數與運算裝置支持的比特位位數相同的第四待處理數據。
在本實施例中，步驟104中對第一待處理數據進行補位可以為在該第一待處理數據的最高位前補零生成第三待處理數據；也可以為通過其他方式對第一待處理數據進行補位，在此不再一一贅述。其中，第三待處理數據的比特位位數和運算裝置支持的比特位位數相同。
在本實施例中，步驟104中對第二代處理數據進行補位可以為在該第二待處理數據的最高位前補零生成第四待處理數據；也可以為通過其他方式對第二待處理數據進行補位，在此不再一一贅述。其中，第四待處理數據的比特位位數與運算裝置支持的比特位位數相同。
步驟105，根據運算裝置支持的比特位位數生成第一參數。
在本實施例中，步驟105中根據運算裝置支持的比特位位數生成第一參數可以為生成各個比特位均置1的第一參數，該第一參數的比特位位數與運算裝置支持的比特位位數相同；也可以通過其他方式根據運算裝置支持的比特位位數生成第一參數，在此不再一一贅述。
步驟106，將第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊。
步驟107，由最低位到最高位，將第三待處理數據按預設位長進行劃分，依次得到第一單元、第二單元.......
在本實施例中，步驟107中預設位長對應的比特位位數可以為能整除運算裝置支持的比特位位數的整數；也可以為其他整數，在此不再一一贅述。
步驟108，根據該預設位長對應的比特位位數生成第二參數，並根據第一參數和第二參數生成第三參數。
在本實施例中，通過步驟108根據該預設位長對應的比特位位數生成的第二參數可以為以2為底數，以預設位長對應的比特位位數為冪數生成第二參數的值；也可以通過其他方式根據預設位長對應的比特位位數生成第二參數，在此不再一一贅述。
在本實施例中，通過步驟108根據第一參數和第二參數生成第三參數，可以包括 首先生成第二參數的值減去第一參數關於第二參數的乘法逆元的差值；然後生成值與該差值相同的第三參數。也可以通過其他方式根據第一參數和第二參數生成第三參數，在此不再一一贅述。
步驟109，將當前偏移單元中的數據和第四待處理數據的乘積與當前迭代數據相加，得到第一數據。
在本實施例中，偏移單元的初始單元為第一單元，迭代數據的初始值為0。
步驟110，將第二參數作為模數，對第一數據與第三參數進行模乘運算，得到第二數據。
步驟111，將第一參數和第二數據的乘積與第一數據進行加法運算，得到第三數據。
步驟112，將第三數據右移預設位長，並用移位後得到的數據替換當前迭代數據。
步驟113，判斷當前偏移單元是否為最後一個單元，是則實行步驟115，否則執行步驟114。
在本實施例中，通過步驟113確定當前偏移單元不為最後一個單元時，可以通過步驟114將偏移單元指向當前偏移單元的下一個單元；通過步驟113確定當前偏移單元為最後一個單元時，可以通過步驟115判斷當前迭代數據是否小於第一參數。
步驟114，將偏移單元指向當前偏移單元的下一個單元，返回步驟109。
步驟115，判斷當前迭代數據是否小於第一參數，是則執行步驟117，否則執行步驟 116。
在本實施例中，在本實施例中，通過步驟115確定當前迭代數據小於第一參數時， 可以通過步驟117直接存儲或輸出當前迭代數據；通過步驟115確定當前迭代數據不小於第一參數時，可以通過步驟116對當前迭代數據進行處理。
步驟116，將當前迭代數據自減第一參數，順序執行步驟117。
步驟117，存儲或輸出指示第一待處理數據與第二待處理數據乘積的當前迭代數據。
本發明實施例提供的在嵌入式系統中實現乘法運算的方法，在乘法運算指令中第一待處理數據比特位位數和第二待處理數據的比特位位數之和小於運算裝置支持的比特位位數時，可以首先將該第一待處理數據和第二待處理數據進行補位，得到第三待處理數據和第四待處理數據；然後在第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊時，將第三待處理數據按預設位長進行劃分，並分別生成第一參數、 第二參數和第三參數；最後通過該第一參數、第二參數和第三參數對當前偏移單元中的數據和第四待處理數據進行處理，直到當前偏移單元為最後一個單元時，根據當前迭代數據與第一參數的大小關係，對當前迭代數據進行處理，得到指示第一待處理數據和第二待處理數據乘積的當前迭代數據。本發明實施例提供的技術方案，由於通過模乘算法實現相乘的運算，使得乘法運算的速度得到提高，解決了現有技術中CPU執行乘法運算時的運算速度比較低的問題。
如圖2所示，本發明實施例二提供的另一種在嵌入式系統中實現乘法運算的方法，包括
步驟201，接收到乘法運算指令時，獲取該乘法運算指令中第一待處理數據和第二待處理數據。
在本實施例中，步驟201中乘法運算指令可以為計算該第一待處理數據和第二待處理數據乘積的指令。具體的，該第一待處理數據和第二待處理數據可以均為大數，可以為其他數據，在此不作限制。
在本實施例中，以下以第一待處理數據為十六進位數B4050A850C04B3ABF5413256 5044B0B7D7BFD8BA270B39432;355FFB4，第二待處理數據為十六進位數 B70E0CBD6BB4BF7F32 1390B94A03C1D356C21122343280D6115C1D21 為例進行說明。
步驟202，判斷該第一待處理數據的比特位位數和第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數，是則執行步驟203，否則執行步驟204。
在本實施例中，由於運算裝置的配置決定其允許支持的比特位位數；而當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可能產生運算錯誤；因此在進行乘法運算之前，需要首先通過步驟202判斷第一待處理數據的比特位位數和第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數。
在本實施例中，當通過步驟202確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可以通過步驟203返回錯誤信息；當通過步驟202確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和不大於運算裝置支持的比特位位數時，可以通過步驟204對第一待處理數據和第二待處理數據分別進行補位。
在本實施例中，以運算裝置支持的比特位位數為512為例。通過步驟101可知，第一待處理數據和第二待處理數據均為224比特，因此第一待處理數據的比特位位數和第二待處理數據的比特位位數之和為448，小於運算裝置支持的比特位位數。
步驟203，返回錯誤信息。
在本實施例中，由於當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，對第一待處理數據和第二待處理數據進行乘法運算的過程中可能產生運算錯誤，因此當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可以通過步驟203返回錯誤信肩、ο
步驟204，在該第一待處理數據的最高位前補零生成第三待處理數據，在該第二待處理數據的最高位前補零生成第四待處理數據。
在本實施例中，第三待處理數據與第四待處理數據的比特位位數與運算裝置支持的比特位位數相同。
相應地，在本實施例中，通過步驟204在第一待處理數據的最高位前補零生成的第三待處理數據為十六進位數 000000000000000000000000000000000000000000000000000000000000000000000000B4050 A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4o
在本實施例中，通過步驟204在第二待處理數據的最高位前補零生成的第四待處理數據為十六進位數 000000000000000000000000000000000000000000000000000000000000000000000000B70E0 CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21。
步驟205，生成各個比特位均置1的第一參數。
在本實施例中，步驟205中第一參數的比特位位數與運算裝置支持的比特位位數相同。
在本實施例中，運算裝置支持的比特位位數為512時，步驟205中第一參數為十六進位數 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFo
步驟206，將第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊。
步驟207，由最低位到最高位，將第三待處理數據按預設位長進行劃分，依次得到第一單元、第二單元.......
在本實施例中，步驟207中預設位長對應的比特位位數可以為能整除運算裝置支持的比特位位數的整數；也可以為其他整數，在此不再一一贅述。
在本實施例中，步驟207中預設位長對應的比特位位數以32為例進行說明。通過步驟207將第三代處理數據按預設位長進行劃分，得到16個單元，每個單元中包含的數據為一個，得到的各個單元中的數據分別為00000000、00000000、00000000、00000000、 00000000、00000000、00000000、00000000、00000000、B4050A85、0C04B3AB、F5413256、 5044B0B7, D7BFD8BA,270B3943,2355FFB4 其中，2!355FFB4 為第一單元包含的中的數據。
步驟208，根據該預設位長對應的比特位位數生成第二參數，並根據第一參數和第二參數生成第三參數。
在本實施例中，通過步驟208根據該預設位長對應的比特位位數生成的第二參數可以為以2為底數，以預設位長對應的比特位位數為冪數生成第二參數的值；也可以通過其他方式根據預設位長對應的比特位位數生成第二參數，在此不再一一贅述。在本實施例中，相應地，第二參數的值為2的32次冪，即為十六進位數100000000。
在本實施例中，通過步驟208根據第一參數和第二參數生成第三參數，可以包括 首先生成第二參數的值減去第一參數關於第二參數的乘法逆元得到的差值；然後生成值與該差值相同的第三參數。也可以通過其他方式根據第一參數和第二參數生成第三參數，在此不再一一贅述。相應地，在本實施例中，第三參數的值為1。
步驟209，將當前偏移單元中的數據和第四待處理數據的乘積與當前迭代數據相加，得到第一數據。
在本實施例中，步驟209中當前偏移單元中的數據為當前偏移單元包含的數據， 其中，偏移單元的初始單元為第一單元，迭代數據的初始值為0。
步驟210，將第二參數作為模數，對第一數據與第三參數進行模乘運算，得到第二數據。
步驟211，將第一參數和當前第二數據的乘積與第一數據進行加法運算，得到第三數據。
步驟212，用第三數據右移預設位長，並用第三數據右移預設位長得到的數據替換當前迭代數據。
步驟213，判斷當前偏移單元是否為最後一個單元，是則執行步驟214，否則執行步驟214。
在本實施例中，通過步驟213確定當前偏移單元不為最後一個單元時，可以通過步驟214將偏移單元指向當前偏移單元的下一個單元；通過步驟213確定當前偏移單元為最後一個單元時，可以通過步驟215判斷當前迭代數據是否小於第一參數。
在本實施例中，具體的，步驟213中最後一個單元為第十六單元。
步驟214，將偏移單元指向當前偏移單元的下一個單元，返回步驟209。
步驟215，判斷當前迭代數據是否小於第一參數，是則執行步驟217，否則執行步驟 216。
在本實施例中，在本實施例中，通過步驟215確定當前迭代數據小於第一參數時， 可以通過步驟217直接存儲或輸出當前迭代數據；通過步驟215確定當前迭代數據不小於第一參數時，可以通過步驟216對當前迭代數據進行處理。
步驟216，將當前迭代數據自減第一參數，順序執行步驟217。
步驟217，存儲或輸出指示第一待處理數據與第二待處理數據乘積的當前迭代數據。
在本實施例中，通過上述計算過程，存儲或輸出的指示第一待處理數據與第二待處理數據乘積的當前迭代數據具體為80B97BC11ED23B160DC05E92^392D7C97ABAF222EF0 D0A74E131B6C1FF0DD2A5EB8FCD20EC90DB9211A392082E285B0624E260324BD5A34。
本發明實施例提供的在嵌入式系統中實現乘法運算的方法，在乘法運算指令中第一待處理數據比特位位數和第二待處理數據的比特位位數之和小於運算裝置支持的比特位位數時，可以首先將該第一待處理數據和第二待處理數據進行補位，得到第三待處理數據和第四待處理數據；然後在第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊時，將第三待處理數據按預設位長進行劃分，並分別生成第一參數、 第二參數和第三參數；最後通過該第一參數、第二參數和第三參數對當前偏移單元中的數據和第四待處理數據進行處理，直到當前偏移單元為最後一個單元時，根據當前迭代數據與第一參數的大小關係，對當前迭代數據進行處理，得到指示第一待處理數據和第二待處理數據乘積的當前迭代數據。本發明實施例提供的技術方案，由於通過模乘算法實現相乘的運算，使得乘法運算的速度得到提高，解決了現有技術中CPU執行乘法運算時的運算速度比較低的問題。
如圖3所示，本發明實施例三提供的一種在嵌入式系統中實現乘法運算的裝置， 包括
待處理數據獲取模塊301，用於接收到乘法運算指令時，獲取乘法運算指令中第一待處理數據和第二待處理數據。
在本實施例中，待處理數據獲取模塊301中乘法運算指令可以為計算該第一待處理數據和第二待處理數據乘積的指令。具體的，該第一待處理數據和第二待處理數據可以均為大數，可以為其他數據，在此不作限制。
第一判斷模塊302，用於判斷第一待處理數據的比特位位數與第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數。
在本實施例中，由於運算裝置的配置決定其允許支持的比特位位數；而當第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可能產生運算錯誤；因此在進行乘法運算之前，需要首先通過第一判斷模塊302判斷第一待處理數據的比特位位數和第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數。
在本實施例中，當通過第一判斷模塊302確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和大於運算裝置支持的比特位位數時，可以返回錯誤信息； 當通過第一判斷模塊302確定第一待處理數據的比特位位數和第二待處理數據的比特位位數之和不大於運算裝置支持的比特位位數時，可以通過補位模塊303對第一待處理數據和第二待處理數據分別進行補位。
補位模塊303，用於對第一待處理數據進行補位，生成比特位位數與運算裝置支持的比特位位數相同的第三待處理數據，對第二待處理數據的進行補位，生成比特位位數與運算裝置支持的比特位位數相同的第四待處理數據。
在本實施例中，補位模塊303中對第一待處理數據進行補位可以為在該第一待處理數據的最高位前補零生成第三待處理數據；也可以為通過其他方式對第一待處理數據進行補位，在此不再一一贅述。其中，第三待處理數據的比特位位數和運算裝置支持的比特位位數相同。
在本實施例中，補位模塊303中對第二代處理數據進行補位可以為在該第二待處理數據的最高位前補零生成第四待處理數據；也可以為通過其他方式對第二待處理數據進行補位，在此不再一一贅述。其中，第四待處理數據的比特位位數與運算裝置支持的比特位位數相同。
第一參數生成模塊304，用於根據運算裝置支持的比特位位數生成第一參數。
在本實施例中，第一參數生成模塊304中根據運算裝置支持的比特位位數生成第一參數可以為生成各個比特位均置1的第一參數，該第一參數的比特位位數與運算裝置支持的比特位位數相同；也可以通過其他方式根據運算裝置支持的比特位位數生成第一參數，在此不再一一贅述。
對齊模塊305，用於將第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊。
劃分模塊306，用於由最低位到最高位，將第三待處理數據按預設位長進行劃分， 依次得到第一單元、第二單元.......14
在本實施例中，劃分模塊306中預設位長對應的比特位位數可以為能整除運算裝置支持的比特位位數的整數；也可以為其他整數，在此不再一一贅述。
第二參數生成模塊307，用於根據預設位長對應的比特位位數生成第二參數，並根據第一參數和第二參數生成第三參數。
在本實施例中，通過第二參數生成模塊307根據該預設位長對應的比特位位數生成的第二參數可以為以2為底數，以預設位長對應的比特位位數為冪數生成第二參數的值；也可以通過其他方式根據預設位長對應的比特位位數生成第二參數，在此不再一一贅述。
在本實施例中，通過第二參數生成模塊307根據第一參數和第二參數生成第三參數，包括用第二參數的值減去第一參數關於第二參數的乘法逆元得到的差值；該差值為第三參數的值。也可以通過其他方式根據第一參數和第二參數生成第三參數，在此不再一一贅述。
第一數據生成模塊308，用於將當前偏移單元中的數據和第四待處理數據的乘積與當前迭代數據相加，得到第一數據。
在本實施例中，第一數據生成模塊308中偏移單元的初始單元為第一單元，迭代數據的初始值為0。
第二數據生成模塊309，用於將第二參數作為模數，對所述第一數據與第三參數進行模乘運算，得到第二數據。
第三數據處理模塊310，用於將第一參數和當前第二數據的乘積與第一數據進行加法運算，得到第三數據。
數據替換模塊311，用於用第三數據右移預設位長後得到的數據替換當前迭代數據。
第二判斷模塊312，用於判斷當前偏移單元是否為最後一個單元。
在本實施例中，通過第二判斷模塊312確定當前偏移單元不為最後一個單元時， 可以通過移位模塊313將偏移單元指向當前偏移單元的下一個單元；通過第二判斷模塊 312確定當前偏移單元為最後一個單元時，可以通過第三判斷模塊314判斷當前迭代數據是否小於第一參數。
移位模塊313，用於將偏移單元指向當前偏移單元的下一個單元，返回第一數據生成模塊308。
第三判斷模塊314，用於判斷當前迭代數據是否小於第一參數。
在本實施例中，在本實施例中，通過第三判斷模塊314確定當前迭代數據小於第一參數時，可以通過輸出模塊316直接存儲或輸出當前迭代數據；通過第三判斷模塊314確定當前迭代數據不小於第一參數時，可以通過自減模塊315對當前迭代數據進行處理。
自減模塊315，用於將當前迭代數據自減第一參數。
輸出模塊316，用於存儲或輸出指示第一待處理數據與第二待處理數據乘積的當前迭代數據。
進一步的，如圖4所示，本實施例中補位模塊303，包括
補位子模塊3031，用於在第一待處理數據的最高位前補零生成第三待處理數據， 在第二待處理數據的最高位前補零生成第四待處理數據，第三待處理數據與第四待處理數據的比特位位數與運算裝置支持的比特位位數相同。
進一步的，如圖5所示，本實施例中，第一參數生成模塊304，包括
第一生成子模塊3041，用於生成各個比特位均置1的第一參數，第一參數的比特位位數與運算裝置支持的比特位位數相同。
進一步的，如圖6所示，在本實施例中，第二參數生成模塊307，包括
第二生成子模塊3071，用於用以2為底數，以預設位長對應的比特位位數為冪數的生成第二參數的值。
如圖7所示，該第二參數生成模塊307，還可以包括
第三生成子模塊3072，用於生成第二參數的值減去第一參數關於第二參數的乘法逆元的差值；
第四生成子模塊3073，用於生成值與差值相同的第三參數。
本發明實施例提供的在嵌入式系統中實現乘法運算的裝置，在乘法運算指令中第一待處理數據比特位位數和第二待處理數據的比特位位數之和小於運算裝置支持的比特位位數時，可以首先將該第一待處理數據和第二待處理數據進行補位，得到第三待處理數據和第四待處理數據；然後在第三待處理數據的最低位、第四待處理數據的最低位分別與第一參數的最低位對齊時，將第三待處理數據按預設位長進行劃分，並分別生成第一參數、 第二參數和第三參數；最後通過該第一參數、第二參數和第三參數對當前偏移單元中的數據和第四待處理數據進行處理，直到當前偏移單元為最後一個單元時，根據當前迭代數據與第一參數的大小關係，對當前迭代數據進行處理，得到指示第一待處理數據和第二待處理數據乘積的當前迭代數據。本發明實施例提供的技術方案，由於通過模乘算法實現相乘的運算，使得乘法運算的速度得到提高，解決了現有技術中CPU執行乘法運算時的運算速度比較低的問題。
本發明實施例提供的在嵌入式系統中實現乘法運算的方法和裝置，可以應用在嵌入式系統中。
結合本文中所公開的實施例描述的方法或算法的步驟可以直接用硬體、處理器執行的軟體模塊，或者二者的結合來實施。軟體模塊可以置於隨機存儲器(RAM)、內存、只讀存儲器(ROM)、電可編程ROM、電可擦除可編程ROM、寄存器、硬碟、可移動磁碟、CD-ROM、或技術領域內所公知的任意其它形式的存儲介質中。
以上所述，僅為本發明的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應所述以權利要求的保護範圍為準。
權利要求
1.一種在嵌入式系統中實現乘法運算的方法，其特徵在於，包括(1).接收到乘法運算指令時，獲取所述乘法運算指令中第一待處理數據和第二待處理數據；(2).判斷所述第一待處理數據的比特位位數與所述第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數；如果是，返回錯誤信息；如果否，執行(3)；(3).對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據；(4).根據所述運算裝置支持的比特位位數生成第一參數；(5).將所述第三待處理數據的最低位、所述第四待處理數據的最低位分別與所述第一參數的最低位對齊；(6).將所述第三待處理數據按預設位長由最低位到最高位進行劃分；(J).根據所述預設位長對應的比特位位數生成第二參數，並根據所述第一參數和所述第二參數生成第三參數；(8).將當前偏移單元中的數據和所述第四待處理數據的乘積與當前迭代數據相加，得到第一數據；偏移單元的初始單元為對所述第三待處理數據進行劃分得到的第一個單元，迭代數據的初始值為0 ；(9).將所述第二參數作為模數，對所述第一數據與所述第三參數進行模乘運算，得到第二數據；(10).將所述第一參數和所述第二數據的乘積與所述第一數據進行加法運算，得到第三數據；(11).將所述第三數據右移所述預設位長，並將移位後得到的數據替換當前迭代數據；(12).判斷當前偏移單元是否為最後一個單元； 如果是，執行(14)；如果否，執行(13)；(13).將偏移單元指向當前偏移單元的下一個單元，返回(8)；(14).判斷當前迭代數據是否小於所述第一參數； 如果是，執行(16)；如果否，執行(15)；(15).將當前迭代數據自減所述第一參數；(16).存儲或輸出指示所述第一待處理數據與所述第二待處理數據乘積的當前迭代數據。
2.根據權利要求1所述的在嵌入式系統中實現乘法運算的方法，其特徵在於，所述對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據，包括在所述第一待處理數據的最高位前補零生成第三待處理數據，在所述第二待處理數據的最高位前補零生成第四待處理數據，所述第三待處理數據與所述第四待處理數據的比特位位數與所述運算裝置支持的比特位位數相同。
3.根據權利要求1所述的在嵌入式系統中實現乘法運算的方法，其特徵在於，所述根據所述運算裝置支持的比特位位數生成第一參數，包括生成各個比特位均置1的第一參數，所述第一參數的比特位位數與所述運算裝置支持的比特位位數相同。
4.根據權利要求1所述的在嵌入式系統中實現乘法運算的方法，其特徵在於，所述預設位長對應的比特位位數，具體為能整除所述運算裝置支持的比特位位數的整數。
5.根據權利要求1所述的在嵌入式系統中實現乘法運算的方法，其特徵在於，所述根據所述預設位長對應的比特位位數生成第二參數，包括以2為底數，以所述預設位長對應的比特位位數為冪數生成所述第二參數。
6.根據權利要求1所述的在嵌入式系統中實現乘法運算的方法，其特徵在於，所述根據所述第一參數和所述第二參數生成第三參數，包括生成所述第二參數的值減去所述第一參數關於所述第二參數的乘法逆元的差值； 生成值與所述差值相同的第三參數。
7.—種在嵌入式系統中實現乘法運算的裝置，其特徵在於，包括待處理數據獲取模塊，用於接收到乘法運算指令時，獲取所述乘法運算指令中第一待處理數據和第二待處理數據；第一判斷模塊，用於判斷所述第一待處理數據的比特位位數與所述第二待處理數據的比特位位數之和是否大於運算裝置支持的比特位位數；所述補位模塊，用於在所述第一判斷模塊判斷結果為是時對所述第一待處理數據進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第三待處理數據，對所述第二待處理數據的進行補位，生成比特位位數與所述運算裝置支持的比特位位數相同的第四待處理數據；第一參數生成模塊，用於根據所述運算裝置支持的比特位位數生成第一參數； 對齊模塊，用於將所述第三待處理數據的最低位、所述第四待處理數據的最低位分別與所述第一參數的最低位對齊；劃分模塊，用於將所述第三待處理數據按預設位長由最低位到最高位進行劃分； 第二參數生成模塊，用於根據所述預設位長對應的比特位位數生成第二參數，並根據所述第一參數和所述第二參數生成第三參數；第一數據生成模塊，用於將當前偏移單元中的數據和所述第四待處理數據的乘積與當前迭代數據相加，得到第一數據；所述偏移單元的初始單元為所述第一單元，所述迭代數據的初始值為0 ； 第二數據生成模塊，用於將所述第二參數作為模數，對所述第一數據與所述第三參數進行模乘運算，得到第二數據；第三數據處理模塊，用於將所述第一參數和所述第二數據的乘積與所述第一數據進行加法運算，得到第三數據；數據替換模塊，用於將所述第三數據右移所述預設位長後得到的數據替換當前迭代數據；第二判斷模塊，用於判斷當前偏移單元是否為最後一個單元；所述移位模塊，用於在所述第二判斷模塊判斷結果為否時將偏移單元指向當前偏移單元的下一個單元，返回第一數據生成模塊；所述第三判斷模塊，用於在所述第二判斷模塊判斷結果為是時判斷當前迭代數據是否小於所述第一參數；所述自減模塊，用於在所述第三判斷模塊判斷結果為否時將當前迭代數據自減所述第一參數；所述輸出模塊，用於在所述第三判斷模塊判斷結果為是時存儲或輸出指示所述第一待處理數據與所述第二待處理數據乘積的當前迭代數據。
8.根據權利要求7所述的實現乘法運算的裝置，其特徵在於，所述補位模塊，包括補位子模塊，用於在所述第一待處理數據的最高位前補零生成第三待處理數據，在所述第二待處理數據的最高位前補零生成第四待處理數據，所述第三待處理數據與所述第四待處理數據的比特位位數與所述運算裝置支持的比特位位數相同。
9.根據權利要求7所述的實現乘法運算的裝置，其特徵在於，所述第一參數生成模塊， 包括第一生成子模塊，用於生成各個比特位均置1的第一參數，所述第一參數的比特位位數與所述運算裝置支持的比特位位數相同。
10.根據權利要求7所述的實現乘法運算的裝置，其特徵在於，所述預設位長對應的比特位位數，具體為能整除所述運算裝置支持的比特位位數的整數。
11.根據權利要求7所述的實現乘法運算的裝置，其特徵在於，所述第二參數生成模塊，包括第二生成子模塊，以2為底數，以所述預設位長對應的比特位位數為冪數生成第二參數的值。
12.根據權利要求7所述的實現乘法運算的裝置，其特徵在於，所述第二參數生成模塊，包括第三生成子模塊，用於生成所述第二參數的值減去所述第一參數關於所述第二參數的乘法逆元的差值；第四生成子模塊，用於生成值與所述差值相同的第三參數。
全文摘要
本發明公開了一種在嵌入式系統中實現乘法運算的方法和裝置，涉及密碼學領域。解決了現有技術執行乘法運算的運算速度比較低的問題。所述方法包括(1)獲取第一待處理數據和第二待處理數據；(2)判斷比特位位數之和是否大於運算裝置支持的比特位位數；(3)生成第三待處理數據，生成第四待處理數據；(4)生成第一參數；(5)將最低位對齊；(6)將第三待處理數據進行劃分；(7)生成第二參數，並生成第三參數；(8)得到第一數據；(9)得到第二數據；(10)得到第三數據；(11)替換當前迭代數據；(12)判斷當前偏移單元是否為最後一個單元；(13)將偏移單元指向下一個單元，返回(8)；(14)判斷當前迭代數據是否小於第一參數；(15)將當前迭代數據自減第一參數；(16)存儲或輸出當前迭代數據。
文檔編號G06F7/53GK102508632SQ20111030202
公開日2012年6月20日 申請日期2011年9月30日 優先權日2011年9月30日
發明者於華章, 陸舟 申請人:飛天誠信科技股份有限公司