c++ - 上位ビット - それらを取り、uint64_t を uint8_t にします。

Question

uint64_t があり、uint64_t の各バイトの上位ビットのみを気にするとします。そのようです：

uint32_t: 0000 ... 1000 0000 1000 0000 1000 0000 1000 0000 ---> 0000 1111

次よりも速い方法はありますか？

   return
   (
     ((x >> 56) & 128)+
     ((x >> 49) &  64)+
     ((x >> 42) &  32)+
     ((x >> 35) &  16)+
     ((x >> 28) &   8)+
     ((x >> 21) &   4)+
     ((x >> 14) &   2)+
     ((x >>  7) &   1)
   )

別名、x をシフトし、マスキングし、各バイトに正しいビットを追加しますか? これは多くのアセンブリにコンパイルされ、より迅速な方法を探しています... 私が使用しているマシンには SSE2 命令までしかなく、役立つ SIMD ops を見つけることができませんでした。

助けてくれてありがとう。

Answer 1

コメントで述べたように、pmovmskbあなたが望むことをします。使用方法は次のとおりです。

MMX + SSE1:

movq mm0, input ; input can be r/m
pmovmskb output, mm0 ; output must be r

SSE2:

movq xmm0, input
pmovmskb output, xmm0

そして私は新しい道を見上げた

BMI2:

mov rax, 0x8080808080808080
pext output, input, rax ; input must be r

Answer 2

return ((x & 0x8080808080808080) * 0x2040810204081) >> 56;

動作します。＆は、保持するビットを選択します。すべてのビットを最上位バイトに乗算し、シフトによって最下位バイトに移動します。最近のほとんどのCPUでは乗算が高速であるため、アセンブリを使用するよりもそれほど遅くなることはありません。

Answer 3

そして、SSE組み込み関数を使用してそれを行う方法は次のとおりです。

#include <xmmintrin.h>
#include <inttypes.h>
#include <stdio.h>

int main (void)
{
  uint64_t x
  = 0b0000000010000000000000001000000000000000100000000000000010000000;

  printf ("%x\n", _mm_movemask_pi8 ((__m64) x));
  return 0;
}

正常に動作します：

gcc -msse

Answer 4

すべての個別の論理 AND は必要ありません。次のように単純化できます。

x &= 0x8080808080808080;
return (x >>  7) | (x >> 14) | (x >> 21) | (x >> 28) |
       (x >> 35) | (x >> 42) | (x >> 49) | (x >> 56);

(関数の戻り値の型が であると仮定しますuint8_t)。

これを展開されたループに変換することもできます。

uint8_t r = 0;

x &= 0x8080808080808080;

x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
return r;

どちらが実際にうまく機能するかはわかりませんが、最初のものに賭ける傾向があります.

Answer 5

まず、それほど多くの操作は必要ありません。一度に複数のビットを操作できます。

x = (x >> 7) & 0x0101010101010101; // 0x0101010101010101
x |= x >> 28;                      // 0x????????11111111
x |= x >> 14;                      // 0x????????????5555
x |= x >>  7;                      // 0x??????????????FF
return x & 0xFF;

別の方法として、モジュロを使用して横方向の加算を行うこともできます。x % n最初に、 は base の数字の合計であることに注意してくださいn+1。したがって、n+1is2^kの場合、k ビットのグループを追加しています。上記のように開始する場合 t = (x >> 7) & 0x0101010101010101、7 ビットのグループを合計する必要t % 127があるため、解決策になります。ただしt%127、126 までの結果に対してのみ機能します。私はいくつかの修正を試みましたが、どこも簡単ではありません。

モジュロを使用して、前のアルゴリズムの最後のステップだけが存在する状況にしようとすることは可能でした。必要なのは、2 つの下位ビットを保持し、残りのビットの合計を 14 でグループ化することです。

ull t = (x & 0x8080808080808080) >> 7;
ull u = (t & 3) | (((t>>2) % 0x3FFF) << 2);
return (u | (u>>7)) & 0xFF;

しかし、t>>2 は t/4 であり、<< 2 は 4 を掛けて(a % b)*c == (a*c % b*c)い(((t>>2) % 0x3FFF) << 2)ます(t & ~3) % 0xFFFC。しかし、c より小さい場合、a + b%c = (a+b)%c という事実もあります。したがって、単純にu = t % FFFC. 与える:

ull t = ((x & 0x8080808080808080) >> 7) % 0xFFFC;
return (t | (t>>7)) & 0xFF;

Answer 6

これはうまくいくようです：

return (x & 0x8080808080808080) % 127;