代码之家 › 专栏 › 技术社区 › BCS

如何获取跨步模式的校验和

checksum bit-manipulation language-agnostic

BCS · 技术社区 · 16 年前

bits at n , n+m , n+m*2 和 n+m*3

m=3 并且给定16位数字

0010 1011 0110 0001

我需要计算

2, 3, 1, 2, 3, 0, 3

有人对此有什么(很酷的)想法吗?我不介意有点无聊。

我目前的想法是制作输入的移位副本,以对齐要求和的值,然后构建一个逻辑树来做一个4x1位的加法器。

v1 = In;
v2 = In<<3;
v3 = In<<6;
v4 = In<<9;

a1 = v1 ^ v2;
a2 = v1 & v2;
b1 = v3 ^ v4;
b2 = v3 & v4;
c2 = a1 & b1;
d2 = a2 ^ b2;

o1 = a1 ^ b1;
o2 = c2 ^ d2;
o4 = a2 & b2;

这确实会导致结果的比特分布在3个不同的整数上,但很好。

编辑:碰巧我需要总和的直方图,所以做一个 bit-count 属于的 o4 , o2&o1 , o2 和 o1

arr = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];

for(int i = 0; i < N; i++)
{
   out[i] = arr[(In & 0b1001001001) % 30]; 
   In >>= 1;
}

附笔

正确胜过快速。快胜过清。我预计会运行数百万次。

2 回复 | 直到 16 年前

danielschemmel 16 年前

也许我疯了,但我玩得很开心:D 该解决方案基于数据并行性的使用,并在不实际使用SSE内部函数或任何类似方法的情况下伪造矢量cpu。

unsigned short out[64];
const unsigned long long mask      = 0x0249024902490249ul;
const unsigned long long shiftmask = 0x0001000100010001ul;

unsigned long long t = (unsigned short)(in >> 38) | (unsigned long long)(unsigned short)(in >> 39) > 40) > 41) << 48;
t &= mask;
*((unsigned long long*)(out + 38)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

[... snipsnap ...]

t = (unsigned short)(in >> 2) | (unsigned long long)(unsigned short)(in >> 3) > 4) > 5) << 48;
t &= mask;
*((unsigned long long*)(out + 2)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

t = (unsigned short)in | (unsigned long long)(unsigned short)(in >> 1) << 16;
t &= mask;
*((unsigned int*)out) = (unsigned int)((t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask));

通过重新排序计算,我们可以进一步显著减少执行时间,因为它大大减少了将某些内容加载到QWORD中的次数。其他一些优化非常明显,而且相当小,但总结起来是另一个有趣的加速。

unsigned short out[64];
const unsigned long long Xmask = 0x249024902490249ull;
const unsigned long long Ymask = 0x7000700070007u;

unsigned long long x = (in >> 14 & 0xFFFFu) | (in >> 20 & 0xFFFFu) > 26 & 0xFFFFu) > 32) << 48;
unsigned long long y;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[32] = (unsigned short)(y >> 48);
out[26] = (unsigned short)(y >> 32);
out[20] = (unsigned short)(y >> 16);
out[14] = (unsigned short)(y      );

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[33] = (unsigned short)(y >> 48);
out[27] = (unsigned short)(y >> 32);
out[21] = (unsigned short)(y >> 16);
out[15] = (unsigned short)(y      );

[snisnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[37] = (unsigned short)(y >> 48);
out[31] = (unsigned short)(y >> 32);
out[25] = (unsigned short)(y >> 16);
out[19] = (unsigned short)(y      );

x >>= 1;
x &= 0xFFFF000000000000ul;
x |= (in & 0xFFFFu) | (in >> 5 & 0xFFFFu) > 10 & 0xFFFFu) << 32;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[38] = (unsigned short)(y >> 48);
out[10] = (unsigned short)(y >> 32);
out[ 5] = (unsigned short)(y >> 16);
out[ 0] = (unsigned short)(y      );

[snipsnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[ 9] = (unsigned short)(y >> 16);
out[ 4] = (unsigned short)(y      );

在我的电脑上编译为64位二进制文件的本机c++中5000万次执行的运行时间(所有输出都经过验证以匹配^^):
基于阵列的解决方案:~5700毫秒
天真的硬编码解决方案:~4200毫秒
第一种解决方案:~2400毫秒
第二种解决方案:~1600ms

UncleO 16 年前

我现在不想编码的一个建议是使用循环、数组来保存部分结果,以及常量来一次提取位m。

loop 
   s[3*i] += x & (1 << 0);
   s[3*i+1] += x & (1 << 1);
   s[3*i+2] += x & (1 << 2);
   x >> 3;

这将在每个求和中选取太多的位。但你也可以跟踪中间结果,并在计算过程中从总和中减去,以解释可能不再存在的比特。

loop 
   s[3*i] += p[3*i]   = x & (1 << 0);
   s[3*i+1] += p[3*i+1] = x & (1 << 1);
   s[3*i+2] += p[3*i+2] = x & (1 << 2);

   s[3*i] -= p[3*i-10];
   s[3*i+1] -= p[3*i-9];
   s[3*i+2] -= p[3*i-8];
   x >> 3;

当然,通过适当的边界检查。

最快的方法是直接对总和进行硬编码。

s[0] = (x & (1<<0)) + (x & (1<<3)) + (x & (1<<6)) + (x & (1<<9));

等等(转换发生在编译时。)