有沒有一種更有效的方法將char擴展爲uint64_t？

Question

我想通過重複每個位8次來將unsigned char充氣到uint64_t。例如。然而

#include <stdint.h> 
#include <inttypes.h> 

#define BIT_SET(var, pos) ((var) & (1 << (pos))) 

static uint64_t inflate(unsigned char a) 
{ 
    uint64_t MASK = 0xFF; 
    uint64_t result = 0; 
    for (int i = 0; i < 8; i++) { 
     if (BIT_SET(a, i)) 
      result |= (MASK << (8 * i));  
    } 

    return result; 
} 

，我是相當新的C，故有此擺弄：

char -> uint64_t 
0x00 -> 0x00 
0x01 -> 0xFF 
0x02 -> 0xFF00 
0x03 -> 0xFFFF 
0xAA -> 0xFF00FF00FF00FF00 

我現在有下面的實現，使用位轉移到測試，如果一個位被設置，做到這一點個別位讓我有所不同，可能有更好的（即更有效率）的方式來做到這一點。

編輯添加的
好了，施展出了查表的解決方案後，這裏的結果。但是請記住，我沒有直接測試例程，而是作爲更大函數的一部分（二進制矩陣的乘法是精確的），所以這可能會影響結果的結果。所以，在我的電腦上，乘以億8×8矩陣時，和編譯：

gcc -O2 -Wall -std=c99 foo.c 

我這樣至少我的機器（虛擬機的64位Linux Mint的，我應該提上了

./a.out original 
real 0m0.127s 
user 0m0.124s 
sys  0m0.000s 

./a.out table_lookup 
real 0m0.012s 
user 0m0.012s 
sys  0m0.000s 

），查表方式似乎提供了大約10倍的加速，所以我會接受這個答案。

Answer 1

如果您正在尋找效率，請使用查找表：一個包含256個條目的靜態數組，每個條目已經保存了所需的結果。你可以使用你的代碼來生成它。

Answer 2

兩個小優化：
一個用於在輸入測試位（一個將被銷燬，但是這並不重要）
其他用於移動所述掩模。

static uint64_t inflate(unsigned char a) 
{ 
    uint64_t mask = 0xFF; 
    uint64_t result = 0; 
    for (int i = 0; i < 8; i++) { 
     if (a & 1) 
      result |= mask; 
     mask <<= 8;  
     a >>= 1; 
    } 

    return result; 
} 

也許也可以取代 '用於（INT I = 0;我< 8;我++）' - 環由 '而（A）' - 循環。 然而，只有右移a >> = 1才能正常工作，無符號 （就我所知，C標準允許編譯器對其進行簽名或未簽名）。 否則在某些情況下您將會出現無限循環。

編輯：
爲了看到結果，我編譯了gcc -std=c99 -S source.c這兩個變種。 快速瀏覽生成的彙編程序輸出結果，顯示上面顯示的優化生成ca. 1/3的瀏覽器指令，其中大部分都在循環中。

Answer 3

如果你願意在內存上花費256 * 8 = 2kB的內存（即在內存方面效率較低，但在所需的CPU週期方面效率更高），最有效的方法是預先安裝，計算一個查找表：

static uint64_t inflate(unsigned char a) { 
    static const uint64_t charToUInt64[256] = { 
     0x0000000000000000, 0x0101010101010101, 0x0202020202020202, 0x0303030303030303, 
     // ... 
    }; 

    return charToUInt64[a]; 
} 

Answer 4

你應該簡介你的代碼的功能，然後再考慮優化它。

在我的編譯器本地，您的代碼被完全內聯，展開並在值未知時變爲8常量test +或指令，並且在編譯時知道該值時變爲常量。我可以通過刪除一些分支來稍微改進它，但編譯器自己做了一個合理的工作。

優化循環是沒有意義的。查表可能更有效，但可能會阻止編譯器本身進行優化。

Answer 5

在選定的體系結構（SSE，Neon）中，有快速向量操作可以加速此任務或設計爲執行此操作。如果沒有特別的說明，建議的查找表方法是最快和最便攜的。

如果2K大小是一個問題，並行矢量算術運算可以模擬：

static uint64_t inflate_parallel(unsigned char a) { 
    uint64_t vector = a * 0x0101010101010101ULL; 
    // replicate the word all over qword 
    // A5 becomes A5 A5 A5 A5 A5 A5 A5 A5 
    vector &= 0x8040201008040201; // becomes 80 00 20 00 00 04 00 01 <-- 
    vector += 0x00406070787c7e7f; // becomes 80 40 80 70 78 80 7e 80 
           // MSB is correct 
    vector = (vector >> 7) & 0x0101010101010101ULL; // LSB is correct 
    return vector * 255;        // all bits correct 
} 

EDIT：2^31次迭代，（四個時間UNROLL減輕循環評價）

time ./parallel   time ./original   time ./lookup 
real  0m2.038s  real  0m14.161s  real  0m1.436s 
user  0m2.030s  user  0m14.120s  user  0m1.430s 
sys   0m0.000s  sys  0m0.000s  sys  0m0.000s 

這是大約7倍的加速，而查找表給出了〜10倍加速

Answer 6

與@Aki ans在同一主題上的變化WER。其中有些是更好地在這裏，但它可能取決於你的編譯器和目標機（它們應該更適合於Aki的功能，即使他們做更多的工作，因爲有數據較少依賴超標量處理器）

// Aki Suuihkonen: 1.265 
static uint64_t inflate_parallel1(unsigned char a) { 
    uint64_t vector = a * 0x0101010101010101ULL; 
    vector &= 0x8040201008040201; 
    vector += 0x00406070787c7e7f; 
    vector = (vector >> 7) & 0x0101010101010101ULL; 
    return vector * 255; 
} 

// By seizet and then combine: 1.583 
static uint64_t inflate_parallel2(unsigned char a) { 
    uint64_t vector1 = a * 0x0002000800200080ULL; 
    uint64_t vector2 = a * 0x0000040010004001ULL; 
    uint64_t vector = (vector1 & 0x0100010001000100ULL) | (vector2 & 0x0001000100010001ULL); 
    return vector * 255; 
} 

// Stay in 32 bits as much as possible: 1.006 
static uint64_t inflate_parallel3(unsigned char a) { 
    uint32_t vector1 = (((a & 0x0F)  * 0x00204081) & 0x01010101) * 255; 
    uint32_t vector2 = ((((a & 0xF0) >> 4) * 0x00204081) & 0x01010101) * 255; 
    return (((uint64_t)vector2) << 32) | vector1; 
} 

// Do the common computation in 64 bits: 0.915 
static uint64_t inflate_parallel4(unsigned char a) { 
    uint32_t vector1 = (a & 0x0F)  * 0x00204081; 
    uint32_t vector2 = ((a & 0xF0) >> 4) * 0x00204081; 
    uint64_t vector = (vector1 | (((uint64_t)vector2) << 32)) & 0x0101010101010101ULL; 
    return vector * 255; 
} 

// Some computation is done in 64 bits a little sooner: 0.806 
static uint64_t inflate_parallel5(unsigned char a) { 
    uint32_t vector1 = (a & 0x0F) * 0x00204081; 
    uint64_t vector2 = (a & 0xF0) * 0x002040810000000ULL; 
    uint64_t vector = (vector1 | vector2) & 0x0101010101010101ULL; 
    return vector * 255; 
}