如何優化MATLAB位操作

Question

我已經寫在MATLAB我自己的SHA1的實現，它給正確的哈希值。然而，它非常慢（我的Core i7-2760QM上的字符串1000 a需要9.9秒），我認爲這種慢度是由MATLAB如何實現按位邏輯運算（bitand,bitor,,bitcmp）和按位整數的位移（bitshift，bitrol，bitror）。

尤其是我不知道需要建造定點數值對象爲bitrol和bitror使用fi命令，因爲反正在英特爾x86彙編有rol和ror既爲各種規模的寄存器和存儲器地址。然而，bitshift速度相當快（它不需要任何定點數字結構，常規uint64變量工作正常），這使情況變得陌生：爲什麼在MATLAB bitrol和bitror需要使用fi構建的定點數字對象，而bitshift不，當裝配水平都歸結到shl，shr，rol和ror？

因此，在C/C寫這個函數++作爲.mex文件之前，我很樂意知道是否有什麼辦法改善這種功能的性能。我知道對SHA1有一些特定的優化，但如果按位旋轉的基本實現非常慢，那不是問題。

測試一點點與tic和toc，這是顯而易見的是什麼使得它慢是與bitrol和fi環。有兩個這樣的循環：

%# Define some variables. 
FFFFFFFF = uint64(hex2dec('FFFFFFFF')); 

%# constants: K(1), K(2), K(3), K(4). 
K(1) = uint64(hex2dec('5A827999')); 
K(2) = uint64(hex2dec('6ED9EBA1')); 
K(3) = uint64(hex2dec('8F1BBCDC')); 
K(4) = uint64(hex2dec('CA62C1D6')); 

W = uint64(zeros(1, 80)); 

... some other code here ... 

%# First slow loop begins here. 

for index = 17:80 
    W(index) = uint64(bitrol(fi(bitxor(bitxor(bitxor(W(index-3), W(index-8)), W(index-14)), W(index-16)), 0, 32, 0), 1)); 
end 

%# First slow loop ends here. 

H = sha1_handle_block_struct.H; 

A = H(1); 
B = H(2); 
C = H(3); 
D = H(4); 
E = H(5); 

%# Second slow loop begins here. 

for index = 1:80 
    rotatedA = uint64(bitrol(fi(A, 0, 32, 0), 5)); 

    if (index <= 20) 
     % alternative #1. 
     xorPart = bitxor(D, (bitand(B, (bitxor(C, D))))); 
     xorPart = bitand(xorPart, FFFFFFFF); 
     temp = rotatedA + xorPart + E + W(index) + K(1); 
    elseif ((index >= 21) && (index <= 40)) 
     % FIPS. 
     xorPart = bitxor(bitxor(B, C), D); 
     xorPart = bitand(xorPart, FFFFFFFF); 
     temp = rotatedA + xorPart + E + W(index) + K(2); 
    elseif ((index >= 41) && (index <= 60)) 
     % alternative #2. 
     xorPart = bitor(bitand(B, C), bitand(D, bitxor(B, C))); 
     xorPart = bitand(xorPart, FFFFFFFF); 
     temp = rotatedA + xorPart + E + W(index) + K(3); 
    elseif ((index >= 61) && (index <= 80)) 
     % FIPS. 
     xorPart = bitxor(bitxor(B, C), D); 
     xorPart = bitand(xorPart, FFFFFFFF); 
     temp = rotatedA + xorPart + E + W(index) + K(4); 
    else 
     error('error in the code of sha1_handle_block.m!'); 
    end 

temp = bitand(temp, FFFFFFFF); 
E = D; 
D = C; 
C = uint64(bitrol(fi(B, 0, 32, 0), 30)); 
B = A; 
A = temp; 
end 

%# Second slow loop ends here. 

與tic和toc，消息的SHA1哈希整個計算abc發生在我的筆記本電腦周圍0.63秒，其中約0.23秒在第一個慢環和周圍通過測量在第二個慢循環中爲0.38秒。那麼在編寫.mex文件之前，有什麼方法可以在MATLAB中優化這些循環？

Answer 1

有此DataHash從MATLAB文件交換是快速計算SHA-1散列閃電。
我跑到下面的代碼：

x = 'The quick brown fox jumped over the lazy dog'; %# Just a short sentence 
y = repmat('a', [1, 1e6]);       %# A million a's 
opt = struct('Method', 'SHA-1', 'Format', 'HEX', 'Input', 'bin'); 
tic, x_hashed = DataHash(uint8(x), opt), toc 
tic, y_hashed = DataHash(uint8(y), opt), toc 

，並得到了以下結果：

x_hashed = F6513640F3045E9768B239785625CAA6A2588842
Elapsed time is 0.029250 seconds.

y_hashed = 34AA973CD4C4DAA4F61EEB2BDBAD27316534016F
Elapsed time is 0.020595 seconds.

我用random online SHA-1 tool驗證了結果，計算結果確實是正確的。另外，a的散列速度比第一句快1.5倍。

那麼如何DataHash這麼快呢？使用java.security.MessageDigest庫，不會少於！
如果您對使用MATLAB的SHA-1快速函數感興趣，這是一條可行的路線。但是，如果這只是一個實現快速位級操作的練習，那麼MATLAB並沒有真正處理它們，在大多數情況下，您將不得不求助於MEX。

Answer 2

爲什麼在MATLAB bitrol和bitror需要固定點數字對象與網絡連接構成，而位位移不

bitrol和bitror都不是適用於的uint該組的按位的邏輯功能的一部分。它們是定點工具箱的一部分，它還包含適用於定點輸入的bitand，bitshift等變體。

，如果你想只使用UINT函數嘗試bitrol可以表示成兩個bitshifts，一個BITAND和BITOR。雖然這可能會更慢。

Answer 3

由於大多數MATLAB函數，bitand,bitor，bitxor是向量化的。所以，你得到了很多更快，如果你給這些函數向量輸入，而不是對每個元素調用它們在一個循環

例子：

%# create two sets of 10k random numbers 
num = 10000; 
hex = 'ABCDEF'; 
A = uint64(hex2dec(hex(randi(16, [num 16])))); 
B = uint64(hex2dec(hex(randi(16, [num 16])))); 

%# compare loop vs. vectorized call 
tic 
C1 = zeros(size(A), class(A)); 
for i=1:numel(A) 
    C1(i) = bitxor(A(i),B(i)); 
end 
toc 

tic 
C2 = bitxor(A,B); 
toc 

assert(isequal(C1,C2)) 

的時機：

Elapsed time is 0.139034 seconds. 
Elapsed time is 0.000960 seconds. 

這是命令規模更快！

問題是，據我所知，SHA-1計算不能很好地矢量化。所以你可能無法利用這種矢量化。

作爲一個實驗，我實現了一個純粹基於MATLAB的功能可按計算這樣的位操作：

function num = my_bitops(op,A,B) 
    %# operation to perform: not, and, or, xor 
    if ischar(op) 
     op = str2func(op); 
    end 

    %# integer class: uint8, uint16, uint32, uint64 
    clss = class(A); 
    depth = str2double(clss(5:end)); 

    %# bit exponents 
    e = 2.^(depth-1:-1:0); 

    %# convert to binary 
    b1 = logical(dec2bin(A,depth)-'0'); 
    if nargin == 3 
     b2 = logical(dec2bin(B,depth)-'0'); 
    end 

    %# perform binary operation 
    if nargin < 3 
     num = op(b1); 
    else 
     num = op(b1,b2); 
    end 

    %# convert back to integer 
    num = sum(bsxfun(@times, cast(num,clss), cast(e,clss)), 2, 'native'); 
end 

不幸的是，在性能方面，這是更糟糕：

tic, C1 = bitxor(A,B); toc 
tic, C2 = my_bitops('xor',A,B); toc 
assert(isequal(C1,C2)) 

的時機：

Elapsed time is 0.000984 seconds. 
Elapsed time is 0.485692 seconds. 

結論：寫一個MEX函數或搜索文件交換到s如果有人已經:)