如何优化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如果有人已经:)