優化位位移入陣列

Question

我有一段代碼，在〜每秒120萬個運行執行一些任務後運行時，體積最大的是來自兩個數據uint32_t的片設置與bitshifted數據的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萬組的運行。另外，如果我只做一個，就會發生這種速度命中，即使沒有觸及其他7個任務，也會達到120萬。

我討厭認爲這一操作需要一個巨大的80％的速度，由於打這個工作，不能作出任何更快。

這是Windows的Visual Studio 2015年（雖然我儘量保持源作爲移植到MacOS和Linux作爲可能的）。

編輯：完整的基本代碼是Github。我不是代碼的原始作者，但是我已經分叉它並使用修改後的速度版本來維護密碼恢復解決方案。您可以通過各種解決方案和平臺速度看到我在ReverseBits中取得的成功。

這些文件已超過20年之久，並且已成功恢復文件，儘管速度很慢，多年以來一直保持不變。見blog post。

Answer 1

您當然做了比您需要做的更多的工作。請注意函數ReverseBits()如何將正確順序的反向字的字節放在一起，以及發生的下一個事件（您將歸因於放慢的部分）如何重新排序這些相同的字節。

您可以編寫並使用ReverseBits()的修改版本，將反轉表示的字節直接放入數組的正確位置，而不是將它們打包成整數，只是爲了再次打開它們。這應該至少快一點，因爲你會嚴格刪除操作。

Answer 2

我立即想到的是「觀點」的int32_t，如果他們的int8_t像

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

但是一個數組，你的right1最顯著位存儲在data[0]，而這種做法讓至少顯著位轉到data[0]。無論如何，因爲我不知道什麼ReverseBits做什麼，並且您是否也可以根據不同的順序調整您的代碼，也許這有助於...