调整MIT的位计数算法以并行计算单词数?

| 我想使用一种著名的MIT位计数算法的版本,使用SSE2指令对康威生活游戏中的邻居进行计数。 这是c中的MIT位计数,已扩展为对> 63位的位计数。
int bitCount(unsigned long long n)
{
unsigned long long uCount;

uCount = n – ((n >> 1) & 0×7777777777777777)
           - ((n >> 2) & 0×3333333333333333)
           - ((n >> 3) & 0×1111111111111111);
return ((uCount + (uCount >> 4))
& 0x0F0F0F0F0F0F0F0F) % 255;
}
这是Pascal的版本
function bitcount(n: uint64): cardinal;
var ucount: uint64;
begin
  ucount:= n - ((n shr 1) and $7777777777777777)
             - ((n shr 2) and $3333333333333333) 
             - ((n shr 3) and $1111111111111111);
  Result:= ((ucount + (count shr 4)) 
           and $0F0F0F0F0F0F0F0F) mod 255;
end;
我希望并行计算此结构中的位数。
  32-bit word where the pixels are laid out as follows.
  lo-byte         lo-byte neighbor
  0 4 8 C  048C   0 4 8 C 
   +---------------+
  1|5 9 D  159D   1|5 9 D 
   |               |
  2|6 A E  26AE   2|6 A E  
   +---------------+
  3 7 B F  37BF   3 7 B F 
 |-------------|            << slice A
   |---------------|        << slice B
     |---------------|      << slice C
请注意,该结构中间有16位需要查询。 我想使用SSE2为中间的16位中的每一个计算邻居计数。 为此,我将切片A放入XMM0低双字,将切片B放入XXM0-dword1等。 我将XMM0复制到XMM1,并屏蔽XMM0低位字中的位
5
的位
012-456-89A
,对XMM0的字1进行相同操作,等等。不同的像素。 题 如何调整MIT位计数,以每个XMM字中每个字/像素的位计数结束? 备注 我不\'吨要使用查找表,因为我已经有办法,我想 进行测试以查看SSE2是否通过不要求对查找表进行内存访问来加快该过程。 使用SSE汇编的答案将是最佳选择,因为我正在Delphi中对此进行编程,因此我使用了x86 + SSE2汇编代码。     
已邀请:
        由于没有整数模数指令可用于最终的“ 5”表达式,因此MIT算法在SSE2中难以实现。在目前的各种popcnt方法中,最容易,最有效地适用于SSE的方法可能是Henry S. Warren撰写的“ Hackers Delight”的第5章中的第一个方法,我在这里使用SSE内在函数在C语言中实现了该方法。 :
#include <stdio.h>
#include <emmintrin.h>

__m128i _mm_popcnt_epi16(__m128i v)
{
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x5555)), _mm_and_si128(_mm_srli_epi16(v, 1), _mm_set1_epi16(0x5555)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x3333)), _mm_and_si128(_mm_srli_epi16(v, 2), _mm_set1_epi16(0x3333)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x0f0f)), _mm_and_si128(_mm_srli_epi16(v, 4), _mm_set1_epi16(0x0f0f)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x00ff)), _mm_and_si128(_mm_srli_epi16(v, 8), _mm_set1_epi16(0x00ff)));
    return v;
}

int main(void)
{
    __m128i v0 = _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0);
    __m128i v1;

    v1 = _mm_popcnt_epi16(v0);

    printf(\"v0 = %vhd\\n\", v0);
    printf(\"v1 = %vhd\\n\", v1);

    return 0;
}
编译和测试如下:
$ gcc -Wall -msse2 _mm_popcnt_epi16.c -o _mm_popcnt_epi16
$ ./_mm_popcnt_epi16 
v0 = 0 1 2 3 4 5 6 7
v1 = 0 1 1 2 1 2 2 3
$ 
看起来大约有16条算术/逻辑指令,因此每点应以16/8 = 2个时钟运行。 如果需要,您可以轻松地将其转换为原始汇编程序-每个内在映射都映射到一条指令。     

要回复问题请先登录注册