我在 MATLAB 中编写了自己的 SHA1 实现,它给出了正确的哈希值。但是,它非常慢(一个字符串 a 1000 a
在我的 Core i7-2760QM 上需要 9.9 秒),我认为这种缓慢是 MATLAB 如何实现按位逻辑运算的结果( bitand
、bitor
、bitxor
、bitcmp
)和位移位(bitshift
、bitrol
, bitror
) 的整数。
特别是我想知道是否需要使用 fi
命令为 bitrol
和 bitror
构造定点数字对象,因为无论如何在 Intel 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
进行测量,消息 abc
的 SHA1 哈希的整个计算在我的笔记本电脑上花费了大约 0.63 秒,其中大约在第一个慢循环中传递了 0.23 秒,在第二个慢循环中传递了大约 0.38 秒。那么在编写 .mex 文件之前,有没有什么方法可以在 MATLAB 中优化这些循环?
最佳答案
有这个 DataHash
来自可快速计算 SHA-1 哈希的 MATLAB 文件交换。
我运行了以下代码:
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 验证了结果,计算确实是正确的。此外,106 个 a 的散列处理速度比第一句话快 ~1.5 倍。
那么 DataHash
是如何做到这么快的呢???使用 java.security.MessageDigest
库,同样如此!
如果您对快速的 MATLAB 友好型 SHA-1 函数感兴趣,这是正确的选择。
但是,如果这只是实现快速位级运算的练习,那么 MATLAB 并不能真正有效地处理它们,在大多数情况下,您将不得不求助于 MEX。
关于performance - 如何优化 MATLAB 按位运算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11482505/