3

MATLAB で独自の SHA1 実装を作成しましたが、正しいハッシュが得られます。しかし、それは非常に遅いです (a私の Core i7-2760QM では 1000 の文字列は 9.9 秒かかります)。その遅さは、MATLAB がビットごとの論理演算 ( bitand、bitor、bitxor、bitcmp) とビットごとのシフト ( bitshift、bitrol、bitror)を実装する方法の結果だと思います。整数の。

特に、Intel x86アセンブリにはすべてのサイズのレジスタとメモリアドレスの両方があるため、コマンド用およびbitrol使用bitror用の固定小数点数値オブジェクトを作成する必要があるのではないかと思います。ただし、は非常に高速です (固定小数点数値構造体は必要ありません。通常の変数は正常に機能します)。これにより、状況が奇妙になります。アセンブリ レベルでは、 、、および?firolrorbitshiftuint64bitrolbitrorfibitshiftshlshrrolror

したがって、この関数を C/C++ で .mex ファイルとして記述する前に、この関数のパフォーマンスを向上させる方法があれば教えていただければ幸いです。SHA1 にはいくつかの特定の最適化があることは知っていますが、ビットごとのローテーションの非常に基本的な実装が非常に遅い場合、それは問題ではありません。

ticandで少しテストすると、遅くなっているのは withとtocのループであることは明らかです。このようなループが 2 つあります。bitrolfi

%# 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 秒が 2 番目の低速ループで渡されます。.mex ファイルを書き込む前に、MATLAB でこれらのループを最適化する方法はありますか?

4

3 に答える 3

4

これDataHashは、SHA-1ハッシュを非常に高速に計算するMATLABFileExchangeからのものです。
次のコードを実行しました。

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でbitrolとbitrorがfiで構築された固定小数点数値オブジェクトを必要とするのに対し、bitshiftは必要ないのはなぜですか

bitrolとbitrorは、uintに適用できるビット単位の論理関数のセットの一部ではありません。これらは固定小数点ツールボックスの一部であり、固定小数点入力に適用されるbitand、bitshiftなどのバリアントも含まれています。

uint関数のみを使用してみたい場合は、bitrolをbitandとbitorの2つのビットシフトとして表すことができます。しかし、それはさらに遅いかもしれません。

于 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 関数を作成するか、File Exchange を検索して、誰かが既に作成しているかどうかを確認してください :)

于 2012-07-14T16:14:45.897 に答える