배열로 비트 시프트 최적화

Question

일부 작업을 수행 한 후 초당 120 만 회 실행되는 코드 조각이 있는데, 벌 키스트는 두 개의 uint32_t 데이터에서 비트 시프트 된 데이터로 uint8_t 배열을 설정합니다. 발췌 코드는 다음과 같습니다.

static inline uint32_t RotateRight(uint32_t val, int n) 
{ 
    return (val >> n) + (val << (32 - n)); 

} 

static inline uint32_t CSUInt32BE(const uint8_t *b) 
{ 
    return ((uint32_t)b[0] << 24) | ((uint32_t)b[1] << 16) | ((uint32_t)b[2] << 8) | (uint32_t)b[3]; 
} 

static uint32_t ReverseBits(uint32_t val) // Usually just static, tried inline/static inline 
{ 
    // uint32_t res = 0; 
    // for (int i = 0; i<32; i++) 
    // { 
    //  res <<= 1; 
    //  res |= val & 1; 
    //  val >>= 1; 
    // } 
    // Original code above, benched ~220k l/s 

    //val = ((val & 0x55555555) << 1) | ((val >> 1) & 0x55555555); 
    //val = ((val & 0x33333333) << 2) | ((val >> 2) & 0x33333333); 
    //val = ((val & 0x0F0F0F0F) << 4) | ((val >> 4) & 0x0F0F0F0F); 
    //val = ((val & 0x00FF00FF) << 8) | ((val >> 8) & 0x00FF00FF); 
    //val = (val << 16) | (val >> 16); 
    // Option 0, benched ~770k on MBP 

    uint32_t c = 0; 
    c = (BitReverseTable256[val & 0xff] << 24) | 
     (BitReverseTable256[(val >> 8) & 0xff] << 16) | 
     (BitReverseTable256[(val >> 16) & 0xff] << 8) | 
     (BitReverseTable256[val >> 24]); // was (val >> 24) & 0xff 
             // Option 1, benched ~970k l/s on MBP, Current, minor tweak to 24 

             //unsigned char * p = (unsigned char *)&val; 
             //unsigned char * q = (unsigned char *)&c; 
             //q[3] = BitReverseTable256[p[0]]; 
             //q[2] = BitReverseTable256[p[1]]; 
             //q[1] = BitReverseTable256[p[2]]; 
             //q[0] = BitReverseTable256[p[3]]; 
             // Option 2 at ~970k l/s on MBP from http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c 


    return c; // Current 
       // return val; // option 0 
       // return res; // original 


       //uint32_t m; 
       //val = (val >> 16) | (val << 16);       // swap halfwords 
       //m = 0x00ff00ff; val = ((val >> 8) & m) | ((val << 8) & ~m); // swap bytes 
       //m = m^(m << 4); val = ((val >> 4) & m) | ((val << 4) & ~m); // swap nibbles 
       //m = m^(m << 2); val = ((val >> 2) & m) | ((val << 2) & ~m); 
       //m = m^(m << 1); val = ((val >> 1) & m) | ((val << 1) & ~m); 
       //return val; 
       // Benches at 850k l/s on MBP 

       //uint32_t t; 
       //val = (val << 15) | (val >> 17); 
       //t = (val^(val >> 10)) & 0x003f801f; 
       //val = (t + (t << 10))^val; 
       //t = (val^(val >> 4)) & 0x0e038421; 
       //val = (t + (t << 4))^val; 
       //t = (val^(val >> 2)) & 0x22488842; 
       //val = (t + (t << 2))^val; 
       //return val; 
       // Benches at 820k l/s on MBP 
} 
static void StuffItDESCrypt(uint8_t data[8], StuffItDESKeySchedule *ks, BOOL enc) 
{ 
uint32_t left = ReverseBits(CSUInt32BE(&data[0])); 
uint32_t right = ReverseBits(CSUInt32BE(&data[4])); 

right = RotateRight(right, 29); 
left = RotateRight(left, 29); 

//Encryption function runs here 

left = RotateRight(left, 3); 
right = RotateRight(right, 3); 

uint32_t left1 = ReverseBits(left); 
uint32_t right1 = ReverseBits(right); 

data[0] = right1 >> 24; 
data[1] = (right1 >> 16) & 0xff; 
data[2] = (right1 >> 8) & 0xff; 
data[3] = right1 & 0xff; 
data[4] = left1 >> 24; 
data[5] = (left1 >> 16) & 0xff; 
data[6] = (left1 >> 8) & 0xff; 
data[7] = left1 & 0xff; 

이 작업을 수행하는 가장 좋은 방법입니까? 나는뿐만 아니라 uint64_t 버전이 있습니다

나는 완전히이 과제를 생략하면 무슨 일이 일어날 지 테스트

uint64_t both = ((uint64_t)ReverseBits(left) << 32) | (uint64_t)ReverseBits(right); 

data[0] = (both >> 24 & 0xff); 
data[1] = (both >> 16) & 0xff; 
data[2] = (both >> 8) & 0xff; 
data[3] = both & 0xff; 
data[4] = (both >> 56); 
data[5] = (both >> 48) & 0xff; 
data[6] = (both >> 40) & 0xff; 
data[7] = (both >> 32) & 0xff; 

가합니다 (ReverseBits 기능이 아직 완료)를, 그리고 코드는 초당 ~ 650 만 실행에서 실행됩니다. 또한이 스피드 히트는 다른 하나의 과제를 건드리지 않고도 120 만분의 1로만 조정하면 발생합니다.

나는이 작업으로 인해이 작업이 80 %의 속도로 큰 타격을 입었고 더 빨리 만들 수 없다고 생각하지 않았습니다.

이것은 Windows Visual Studio 2015 (가능하면 소스를 macOS 및 Linux로 유지하려고 시도하지만)입니다.

편집 : 전체 기본 코드는 Github입니다. 나는 코드의 원래 작성자가 아니지만, 나는 그것을 포크하고 비밀 번호 복구 솔루션을 사용하여 수정 된 속도 버전을 사용합니다. 당신은 다양한 솔루션과 benched 속도와 ReverseBits에서 성공을 내 속도를 볼 수 있습니다.

이 파일은 20 세 이상이며 몇 년 동안 낮은 속도로 파일을 성공적으로 복구했습니다. blog post을 참조하십시오.

Answer 1

당신이해야 할 일보다 확실히 많은 일을하고 있습니다. 함수 ReverseBits()이 올바른 순서로 반전 된 단어의 바이트를 넣으려는 시도에 어떻게 영향을 미치는지, 그리고 그 다음에 일어나는 일 (느려지는 부분)이 어떻게 동일한 바이트를 재정렬하는지에 유의하십시오.

ReverseBits()의 수정 된 버전을 쓰고 사용할 수 있습니다.이 버전은 반전 된 표현의 바이트를 다시 포장을 풀기 위해 정수로 포장하는 대신 배열의 올바른 위치에 직접 넣습니다. 작업을 엄격하게 제거해야하므로 최소한 조금 더 빠릅니다.

Answer 2

내 즉각적인 생각은 "보기"그들은 그러나

uint8_t data2[8]; 
*((uint32_t*)&data2[0]) = right1; 
*((uint32_t*)&data2[4]) = left1; 

같은 int8_t의 배열 것처럼, 당신은이 방법이 최하위를 할 수있는 반면, data[0]에 right1의 최상위 비트를 저장 int32_t에 있었다 비트는 data[0]입니다. 어쨌든, ReverseBits이 무엇인지 모르거나 다른 순서에 따라 코드를 적용 할 수 있는지 여부는 ...