3

我在 MATLAB 中编写了自己的 SHA1 实现，它提供了正确的哈希值。但是，它非常慢（在我的 Core i7-2760QM 上，一个 1000 的字符串a需要 9.9 秒），我认为缓慢是由于 MATLAB 如何实现按位逻辑运算（bitand, bitor, bitxor, bitcmp）和按位移位（bitshift, bitrol, bitror）整数。

bitrol特别是我想知道是否需要为命令和bitror使用命令构造定点数字对象fi，因为无论如何在 Intel x86 程序集中都有各种大小的寄存器rol和ror内存地址。但是，bitshift它非常快（它不需要任何定点数值结构，常规uint64变量可以正常工作），这使情况变得奇怪：为什么在 MATLAB 中bitrol需要bitror用 构造的定点数值对象fi，而bitshift在装配级别这一切都归结为shl,shr和?rolror

因此，在将这个函数用 C/C++ 编写为 .mex 文件之前，我很高兴知道是否有任何方法可以提高这个函数的性能。我知道 SHA1 有一些特定的优化，但这不是问题，如果按位旋转的基本实现是如此缓慢。

tic用and进行一点测试toc，很明显是什么让它变慢是用bitroland中的循环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 中的这些循环吗？

4

3 回答 3

4

来自 MATLAB File Exchange的这个DataHash可以快速计算 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.

我用随机的在线SHA-1工具验证了结果，计算确实是正确的。此外，10 个6 a 的散列速度比第一句快约 1.5 倍。

那怎么DataHash做的这么快？？？使用java.security.MessageDigest图书馆，不少！
如果您对 MATLAB 友好的快速 SHA-1 函数感兴趣，这就是您要走的路。

但是，如果这只是实现快速位级操作的练习，那么 MATLAB 并不能真正有效地处理它们，在大多数情况下，您将不得不求助于 MEX。

于 2012-07-14T11:21:44.353 回答
3

为什么在 MATLAB 中 bitroll 和 bitror 需要用 fi 构造的定点数值对象，而 bitshift 不需要

bitror 和 bitror 不是适用于 uint 的按位逻辑函数集的一部分。它们是定点工具箱的一部分，其中还包含适用于定点输入的 bitand、bitshift 等变体。

如果您想尝试仅使用 uint 函数，则 bitroll 可以表示为两个位移位，一个 bitand 和一个 bitor。不过，这可能会更慢。

于 2012-07-14T09:43:52.613 回答
3

与大多数 MATLAB 函数一样，bitand, bitor,bitxor是矢量化的。所以如果你给这些函数向量输入而不是在每个元素上循环调用它们，你会更快

例子：

%# create two sets of 10k random numbers
num = 10000;
hex = '0123456789ABCDEF';
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 函数或搜索文件交换以查看是否有人已经这样做了 :)

于 2012-07-14T16:14:45.897 回答