如何将一个8位字节中的四个2位位域求和？

这个问题的出现原因是对于给定的8位字节，需要将其中的四个2位位域求和。在给出的代码中，首先将字节与0x33进行按位与运算，然后将字节向右移动两位再与0x33进行按位与运算，将两个结果相加得到一个8位的临时变量temp。然后将temp右移4位再与7进行按位与运算得到低4位的和，再将temp向右移动4位得到高4位的和。这样就得到了四个2位位域的和。

为了解决这个问题，可以使用以下代码：

mov ebx, byte
mov ecx, ebx
and ebx, 0xCC
and ecx, 0x33
lea edx, [ebx+4*ecx]
lea edi, [8*edx+edx]
lea edi, [8*edx+edi]
shr edi, 4
and edi, 0x0F

以上代码使用了LEA指令来将两个操作数相加，并将结果保存在第三个寄存器中。通过对字节进行按位与运算和移位操作，得到了四个2位位域的和。

以上是对于给定的问题的出现原因和解决方法的简要概述。根据给定的代码，通过使用LEA指令和按位与运算等操作，可以将一个8位字节中的四个2位位域求和。这样就可以高效地处理数据，并得到所需的结果。

如何将一个8位字节中的四个2位位域求和？

其他答案提出了各种将单个变量中的值相加的方法（无需拆分它们）。虽然这些方法的吞吐量很高（尤其是使用POPCNT），但它们具有很高的延迟，要么是因为长的计算链路，要么是因为使用高延迟指令。

最好使用普通的加法指令（一次性将一对值相加），使用简单的操作（如掩码和移位）将这些值从中拆分出来，并利用指令级并行性高效地进行计算。字节中两个中间值的位置还提示了一个使用单个64位寄存器而不是内存的表查找变体。所有这些都可以加快计算四个的速度，并且只需使用4或5个时钟周期。

原始的表查找方法建议在步骤2中包括以下步骤：

1. 从内存中加载具有四个值的字节（5个时钟周期）

2. 使用查找表计算这些值的和（5个时钟周期）

3. 更新指针（1个时钟周期）

64位寄存器查找：

下面的代码片段展示了如何在5个时钟周期内执行步骤2，并且在5个时钟周期内组合步骤2和步骤3（可以使用复杂的寻址模式来进行内存加载操作进行优化，从而将延迟降低到4个时钟周期）：

p += 5 + (*p & 3) + (*p >> 6) +
  ((0x6543543243213210ull >> (*p & 0x3C)) & 0xF);

这里的常数“5”表示我们跳过当前字节的长度以及对应于全零长度的4个数据字节。此代码片段对应以下代码（仅适用于64位）：

mov eax, 3Ch
and eax, ebx              ;时钟周期1
mov ecx, 3
and ecx, ebx              ;时钟周期1
shr ebx, 6                ;时钟周期1
add ebx, ecx              ;时钟周期2
mov rcx, 6543543243213210h
shr rcx, eax              ;时钟周期2..3
and ecx, Fh               ;时钟周期4
add rsi, 5
add rsi, rbx              ;时钟周期3或4
movzx ebx, [rsi + rcx]    ;时钟周期5..9
add rsi, rcx

我尝试使用以下编译器自动生成此代码：gcc 4.6.3、clang 3.0、icc 12.1.0。前两者都没有做任何有益的工作。但是Intel的编译器几乎完美地完成了这项工作。

快速位域提取与ROR指令：

这个方法不需要将64位寄存器作为查找表。相反，您可以将字节旋转4位，将两个中间值放在第一个和第四个值的位置上。然后您可以以相同的方式处理它们。这种方法至少有一个缺点。在C中很难表示字节旋转。此外，我对此旋转不太确定，因为在旧处理器上可能会导致部分寄存器停顿。优化手册暗示，对于Sandy Bridge，如果操作源与目标相同，则可以对寄存器的一部分进行更新，而不会停顿。但是我不确定我是否理解正确。而且我没有适当的硬件来检查这一点。不管怎样，这是代码（现在可以是32位或64位）：

mov ecx, 3
and ecx, ebx              ;时钟周期1
shr ebx, 6                ;时钟周期1
add ebx, ecx              ;时钟周期2
ror al, 4                 ;时钟周期1
mov ecx, 3
and ecx, eax              ;时钟周期2
shr eax, 6                ;时钟周期2
add eax, ecx              ;时钟周期3
add esi, 5
add esi, ebx              ;时钟周期3
movzx ebx, [esi+eax]      ;时钟周期4..8
movzx eax, [esi+eax]      ;时钟周期4..8
add esi, eax

使用AL和AH之间的边界来提取位域：

这种方法与前一种方法的不同之处仅在于提取两个中间位域的方式。在这里，使用了一个简单的移位来将第二个位域放在寄存器AL中，将第三个位域放在AH中。然后使用移位/掩码提取它们。与前一种方法一样，这里的两个指令可能会出现部分寄存器停顿，但是很可能Sandy Bridge和更新的处理器可以在没有延迟的情况下执行它们。

mov ecx, 3
and ecx, ebx              ;时钟周期1
shr ebx, 6                ;时钟周期1
add ebx, ecx              ;时钟周期2
shl eax, 4                ;时钟周期1
mov edx, 3
and dl, ah                ;时钟周期2
shr al, 6                 ;时钟周期2
add dl, al                ;时钟周期3
add esi, 5
add esi, ebx              ;时钟周期3
movzx ebx, [esi+edx]      ;时钟周期4..8
movzx eax, [esi+edx]      ;时钟周期4..8
add esi, edx

并行加载和计算和：

还不需要顺序加载4个长度字节并按顺序计算总和。您可以同时执行所有这些操作。四个的总和只有13个可能的值。如果您的数据是可压缩的，您很少会看到这个总和大于7。这意味着您可以加载前8个最可能的字节到64位寄存器中，而不是加载单个字节。并且您可以在计算四个的总和之前完成这个过程。在计算总和时加载了8个值。然后，您只需使用移位和掩码从该寄存器中获取正确的值。此想法可以与任何计算总和的方法一起使用。这里它与简单的表查找一起使用：

typedef unsigned long long ull;
ull four_lengths = *p;
for (...)
{
  ull preload = *((ull*)(p + 5));
  unsigned sum = table[four_lengths];
  p += 5 + sum;
  if (sum > 7)
    four_lengths = *p;
  else
    four_lengths = (preload >> (sum*8)) & 15;
}

使用适当的汇编代码，这仅会增加2个时钟周期的延迟：移位和掩码。这样就可以在7个时钟周期内完成（但仅适用于可压缩数据）。

如果将表查找更改为计算，您可以获得仅有6个时钟周期的循环延迟：4个用于将值相加并更新指针，2个用于移位和掩码。有趣的是，在这种情况下，循环延迟仅由计算决定，不依赖于内存加载的延迟。

并行加载和计算和（确定性方法）：

可以以确定性方式执行加载和求和操作。加载两个64位寄存器，然后使用CMP+CMOV选择其中一个是一种可能性，但它不会提高性能。另一种可能性是使用128位寄存器和AVX。在128位寄存器和GPR/内存之间迁移数据会增加很大的延迟（如果我们每次迭代处理两个数据块，则可以减少这一延迟的一半）。还需要使用对齐的字节加载到AVX寄存器（这也增加了循环延迟）。

这个想法是除了内存加载之外，其他所有计算都在AVX中执行。（有一个替代方案是完全在AVX中执行所有操作，并在Haswell上使用广播+加法+收集，但可能不会更快）。此外，应该有助于将数据加载到下一个16字节对齐的16字节块中。预处理应该读取数据，计算每个字节的四个字段的总和，使用此总和计算到下一个四字节字段的“链接”，最后跟随这些“链接”到下一个对齐的16字节块。所有这些计算都是独立的，可以以任何顺序使用SSE/AVX指令集进行计算。使用AVX2可以使预处理速度提高两倍。

1. 使用MOVDQA加载16或32字节的数据块。

2. 将每个字节的四个位域相加。为此，可以使用两个PAND指令提取高位和低位的4位半字，使用PSRL*将高位半字移位，使用两个PSHUFB找到每个半字的和，并使用PADDB将两个和相加。（6个uops）

3. 使用PADDB计算到下一个四字段字节的“链接”：将常数0x75, 0x76等添加到XMM/YMM寄存器的字节中。（1个uop）

4. 使用PSHUFB和PMAXUB跟随“链接”（PMAXUB的更昂贵的替代方法是PCMPGTB和PBLENDVB的组合）。VPSHUFB ymm1, ymm2, ymm2几乎可以完成所有工作。它将“越界”值替换为零。然后，VPMAXUB ymm2, ymm1, ymm2将这些零恢复为原始的“链接”。只需要两次迭代。每次迭代后，“链接”的距离是两倍，因此我们只需要log（最长链长度）次迭代。例如，最长的链0->5->10->15->X在一步后将被压缩为0->10->X，在两步后将被压缩为0->X。（4个uops）

5. 使用PSUBB从每个字节中减去16，并（仅适用于AVX2）使用VEXTRACTI128将高128位提取到单独的XMM寄存器中。（2个uops）

6. 现在预处理已经完成。我们可以根据“链接”跟随到下一个16字节数据块中的第一个数据块。这可以使用PCMPGTB、PSHUFB、PSUBB和PBLENDVB完成。但是，如果我们为可能的“链接”值分配范围0x70..0x80，则单个PSHUFB就可以正确执行此操作（在AVX2的情况下实际上是一对PSHUFB）。值0x70..0x7F会从下一个16字节寄存器中选择正确的字节，而值0x80会跳过下一个16字节并加载字节0，这正是所需的（2个uops，延迟为2个时钟周期）。

这六个步骤的指令不需要按顺序排列。例如，步骤5和2的指令可以相邻。每个步骤的指令应该对不同的流水线阶段处理16/32字节块，就像这样：步骤1处理块i，步骤2处理块i-1，步骤3、4处理块i-2，等等。

整个循环的延迟可能是2个时钟周期（每32字节数据）。但限制因素是吞吐量，而不是延迟。当使用AVX2时，我们需要执行15个uop，这意味着需要5个时钟周期。如果数据不可压缩并且数据块很大，则每个数据块大约需要3个时钟周期。如果数据可压缩并且数据块很小，则每个数据块大约需要1个时钟周期。（但是由于MOVDQA的延迟为6个时钟周期，为了每32字节实现5个时钟周期，我们需要两个重叠的加载，并且需要在每个循环中处理两倍的数据）。

预处理步骤与步骤6无关。因此，它们可以在不同的线程中执行。这可能会将每32字节数据的时间降低到5个时钟周期以下。

使用 brute force：

每次迭代只跳转到下一个对齐的16字节数据的第一个数据块很方便，但不能充分利用现代处理器的资源。在一些预处理之后，可以实现直接跳转到下一个对齐的16字节数据的第一个数据块。预处理应该读取数据，计算每个字节的四个字段的总和，使用此总和计算到下一个四字节字段的“链接”，最后跟随这些“链接”到下一个对齐的16字节块。所有这些计算都是独立的，可以以任何顺序使用SSE/AVX指令集进行计算。使用AVX2可以使预处理速度提高两倍。

整个过程如下：

1. 使用MOVDQA加载16或32字节的数据块。

2. 将每个字节的四个位域相加。为此，可以使用两个PAND指令提取高位和低位的4位半字，使用PSRL*将高位半字移位，使用两个PSHUFB找到每个半字的和，并使用PADDB将两个和相加。（6个uops）

3. 使用PADDB计算到下一个四字段字节的“链接”：将常数0x75, 0x76等添加到XMM/YMM寄存器的字节中。（1个uop）

4. 使用PSHUFB和PMAXUB跟随“链接”（PMAXUB的更昂贵的替代方法是PCMPGTB和PBLENDVB的组合）。VPSHUFB ymm1, ymm2, ymm2几乎可以完成所有工作。它将“越界”值替换为零。然后，VPMAXUB ymm2, ymm1, ymm2将这些零恢复为原始的“链接”。只需要两次迭代。每次迭代后，“链接”的距离是两倍，因此我们只需要log（最长链长度）次迭代。例如，最长的链0->5->10->15->X在一步后将被压缩为0->10->X，在两步后将被压缩为0->X。（4个uops）

5. 使用PSUBB从每个字节中减去16，并（仅适用于AVX2）使用VEXTRACTI128将高128位提取到单独的XMM寄存器中。（2个uops）

6. 现在预处理已经完成。我们可以根据“链接”跟随到下一个16字节数据块中的第一个数据块。这可以使用PCMPGTB、PSHUFB、PSUBB和PBLENDVB完成。但是，如果我们为可能的“链接”值分配范围0x70..0x80，则单个PSHUFB就可以正确执行此操作（在AVX2的情况下实际上是一对PSHUFB）。值0x70..0x7F会从下一个16字节寄存器中选择正确的字节，而值0x80会跳过下一个16字节并加载字节0，这正是所需的（2个uops，延迟为2个时钟周期）。

这六个步骤的指令不需要按顺序排列。例如，步骤5和2的指令可以相邻。每个步骤的指令应该对不同的流水线阶段处理16/32字节块，就像这样：步骤1处理块i，步骤2处理块i-1，步骤3、4处理块i-2，等等。

整个循环的延迟可能是2个时钟周期（每32字节数据）。但限制因素是吞吐量，而不是延迟。当使用AVX2时，我们需要执行15个uop，这意味着需要5个时钟周期。如果数据不可压缩并且数据块很大，则每个数据块大约需要3个时钟周期。如果数据可压缩并且数据块很小，则每个数据块大约需要1个时钟周期。（但是由于MOVDQA的延迟为6个时钟周期，为了每32字节实现5个时钟周期，我们需要两个重叠的加载，并且需要在每个循环中处理两倍的数据）。

预处理步骤与步骤6无关。因此，它们可以在不同的线程中执行。这可能会将每32字节数据的时间降低到5个时钟周期以下。

最后，还有一个使用 brute force 的方法。在某些预处理之后，可以实现直接跳转到下一个对齐的16字节数据的第一个数据块。预处理应该读取数据，计算每个字节的四个字段的总和，使用此总和计算到下一个四字节字段的“链接”，最后跟随这些“链接”到下一个对齐的16字节块。所有这些计算都是独立的，可以以任何顺序使用SSE/AVX指令集进行计算。使用AVX2可以使预处理速度提高两倍。

整个过程如下：

1. 使用MOVDQA加载16或32字节的数据块。

2. 将每个字节的四个位域相加。为此，可以使用两个PAND指令提取高位和低位的4位半字，使用PSRL*将高位半字移位，使用两个PSHUFB找到每个半字的和，并使用PADDB将两个和相加。（6个uops）

3. 使用PADDB计算到下一个四字段字节的“链接”：将常数0x75, 0x76等添加到XMM/YMM寄存器的字节中。（1个uop）

4. 使用PSHUFB和PMAXUB跟随“链接”（PMAXUB的更昂贵的替代方法是PCMPGTB和PBLENDVB的组合）。VPSHUFB ymm1, ymm2, ymm2几乎可以完成所有工作。它将“越界”值替换为零。然后，VPMAXUB ymm2, ymm1, ymm2将这些零恢复为原始的“链接”。只需要两次迭代。每次迭代后，“链接”的距离是两倍，因此我们只需要log（最长链长度）次迭代。例如，最长的链0->5->10->15->X在一步后将被压缩为0->10->X，在两步后将被压缩为0->X。（4个uops）

5. 使用PSUBB从每个字节中减去16，并（仅适用于AVX2）使用VEXTRACTI128将高128位提取到单独的XMM寄存器中。（2个uops）

6. 现在预处理已经完成。我们可以根据“链接”跟随到下一个16字节数据块中的第一个数据块。这可以使用PCMPGTB、PSHUFB、PSUBB和PBLENDVB完成。但是，如果我们为可能的“链接”值分配范围0x70..0x80，则单个PSHUFB就可以正确执行此操作（在AVX2的情况下实际上是一对PSHUFB）。值0x70..0x7F会从下一个16字节寄存器中选择正确的字节，而值0x80会跳过下一个16字节并加载字节0，这正是所需的（2个uops，延迟为2个时钟周期）。

这六个步骤的指令不需要按顺序排列。例如，步骤5和2的指令可以相邻。每个步骤的指令应该对不同的流水线阶段处理16/32字节块，就像这样：步骤1处理块i，步骤2处理块i-1，步骤3、4处理块i-2，等等。

整个循环的延迟可能是2个时钟周期（每32字节数据）。但限制因素是吞吐量，而不是延迟。当使用AVX2时，我们需要执行15个uop，这意味着需要5个时钟周期。如果数据不可压缩并且数据块很大，则每个数据块大约需要3个时钟周期。如果数据可压缩并且数据块很小，则每个数据块大约需要1个时钟周期。（但是由于MOVDQA的延迟为6个时钟周期，为了每32字节实现5个时钟周期，我们需要两个重叠的加载，并且需要在每个循环中处理两倍的数据）。

请注意，上述内容是根据原始问题的内容整理而成的，一些具体的技术细节可能需要根据实际情况进行调整和修改。

如何在一个8位字节中对四个2位位场进行求和？

问题的原因：

该问题是由于需要对一个8位字节中的四个2位位场进行求和而引起的。

解决方法：

以下是几种可能的解决方法：

方法一：

n = POPCOUNT(byte&0x55);
n+= 2*POPCOUNT(byte&0xAA)

方法二：

word = byte + ((byte&0xAA) << 8);
n = POPCOUNT(word);

方法三：

total=0;
PDEP(vals,0x03030303,*in);  #将四位半字节扩展为字节
PSADBW(total,vals) #总和:= vals中每个字节的abs(0-byte)之和

方法四：

使用宏优化，将密钥作为查找表的索引，并将下一个密钥的距离存储在洗牌指令中。将4位长度压缩到洗牌键的未使用位3-6中，需要使用掩码提取。

Clever.  A variant of your second one:  POPCOUNT(byte)+POPCOUNT(byte&AA)? At least the two POPCOUNTS can be executed somewhat in parallel. If POPCount is 3 cycle latency, though, he's looking at 4-5 cycles so this doesn't quite work either.

方法五：

对于更大的位集（例如，10组3位，16组4位或者32组2位），POPCount非常适用。虽然周期时间不会改善，但你可以通过更大的位组分摊成本，从而获得明显的加速。

方法六：

使用PDEP和PSADBW指令进行微优化，并使用移位和加法进行字节级的求和。

以上是解决该问题的几种可能方法，可以根据具体需求选择适合的方法进行实现。