MATLAB 비트 연산을 최적화하는 방법

Question

MATLAB에서 내 자신의 SHA1 구현을 작성했으며 올바른 해시를 제공합니다. 그러나 매우 느립니다 (문자열은 1000 a의 코어 i7-2760QM에서 9.9 초 걸립니다). 느린 것은 MATLAB이 비트 논리 연산 (bitand, bitor, bitxor, bitcmp)을 구현하는 방법과 비트 단위로 논리 연산을 구현 한 결과라고 생각합니다. 교대 (bitshift, bitrol, bitror)의 정수입니다. 어쨌든 인텔 x86 어셈블리에 모든 크기의 레지스터와 메모리 주소를 rol 및 ror 모두가 있기 때문에

은 특히 나는 fi 명령을 사용하여 bitrol 및 bitror을위한 고정 소수점 숫자 객체를 구성 할 필요가 궁금합니다. 그러나 bitshift은 매우 빠릅니다 (어떤 고정 소수점 숫자 비용 구조도 필요하지 않습니다. 보통 uint64 변수가 잘 작동합니다). 낯선 이유는 다음과 같습니다. bitrol 및 bitror은 fi으로 구성된 고정 소수점 숫자 개체가 필요한 반면 bitshift은 어셈블리 레벨에서 모두 shl, shr, rol 및 ror으로 떨어집니다.

그래서이 함수를 C/C++에서 .mex 파일로 작성하기 전에이 함수의 성능을 향상시킬 방법이 있는지 알고 싶습니다. SHA1에 대한 몇 가지 구체적인 최적화가 있다는 것을 알고 있지만 비트 로테이션의 기본적인 구현이 너무 느리면 문제가되지 않습니다.

tic 및 toc에 조금 테스트, 그것을 만드는 것이 느린 bitrol와 fi와의 루프가 있음을 알 수있다. 이 개 같은 루프가 있습니다

tic 및 toc, abc 내 노트북에 약 0.23 초 주변의 첫번째 느린 루프 전달되는 약 0.63 초, 소요 메시지의 SHA1 해시의 전체 계산과 측정

%# 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. 

두 번째 슬로우 루프에서 0.38 초. 그렇다면 .mex 파일을 작성하기 전에 MATLAB에서 이러한 루프를 최적화 할 수있는 방법이 있습니까? bitshift하지 않는 반면

Answer 1

SHA-1 해시를 빠르게 계산하는 MATLAB File Exchange의 DataHash이 있습니다.다음과 같은 결과

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으로 결과를 확인했으며 계산이 실제로 정확했습니다. 또한, 10 a는 첫 번째 문장보다 1.5 배 빠른 해시입니다.

그래서 DataHash 어떻게 그렇게 빨리합니까 ??? java.security.MessageDigest 라이브러리를 사용하면 그만입니다!
빠른 MATLAB- 친화적 인 SHA-1 함수에 관심이 있으시면,이 방법을 사용하십시오.

그러나 이것이 빠른 비트 레벨 연산을 구현하기위한 연습 일 경우 MATLAB은 효율적으로 처리하지 않으며 대부분의 경우 MEX를 사용해야합니다.

Answer 2

왜 MATLAB의 bitrol과 bitror은 고정 소수점 숫자 개체는 파이로 구성 할 필요

bitrol 및 bitror가하는 uint에 적용 할 수있는 비트 로직 기능 세트의 일부가 아닌 . 그것들은 고정 소수점 입력에 적용되는 bitand, bitshift 등의 변형을 포함하는 고정 소수점 도구 상자의 일부입니다.

uint 기능 만 사용하려는 경우 비트 롤을 두 비트 시프트, 비트 및 비터로 표현할 수 있습니다. 그것은 비록 더 느릴 수도 있습니다.

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 계산은 잘 벡터화 될 수 없습니다. 따라서 이러한 벡터화를 활용하지 못할 수도 있습니다. 타이밍이었다

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

:이 성능면에서 더 악화이었다, 불행하게도

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 

: 실험으로

, 나는 같은 비트 연산을 계산하는 순수 MATLAB 기반 funciton를 구현 :

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

결론 : MEX 함수를 작성하거나 File Exchange를 검색하여 만약 누군가가 이미했으면 ee :