优化块位操作：base-4 数字
Optimize blockwise bit operations: base-4 numbers
这应该是一个有趣的问题，至少对我来说是这样。
我的目的是操纵 base-4 数字，编码为无符号整数。每个两位块代表一个 base-4 数字，从 最低有效位开始 :
01 00 11 = base4(301)
我想使用 SSE 指令优化我的代码，因为我不确定我在这里的得分如何，也许很差。
代码从字符串开始（并使用它们来检查正确性），并实现：
- 将字符串转换为二进制
- 将二进制转换为字符串
- 反转数字
欢迎任何提示！
uint32_t tobin(std::string s)
{
uint32_t v, bin = 0;
// Convert to binary
for (int i = 0; i < s.size(); i++)
{
switch (s[i])
{
case '0':
v = 0;
break;
case '3':
v = 3;
break;
case '1':
v = 1;
break;
case '2':
v = 2;
break;
default:
throw "UNKOWN!";
}
bin = bin | (v << (i << 1));
}
return bin;
}
std::string tostr(int size, const uint32_t v)
{
std::string b;
// Convert to binary
for (int i = 0; i < size; i++)
{
uint32_t shl = 0, shr = 0, q;
shl = (3 << (i << 1));
shr = i << 1;
q = v & shl;
q = q >> shr;
unsigned char c = static_cast<char>(q);
switch (c)
{
case 0:
b += '0';
break;
case 3:
b += '3';
break;
case 1:
b += '1';
break;
case 2:
b += '2';
break;
default:
throw "UNKOWN!";
}
}
return b;
}
uint32_t revrs(int size, const uint32_t v)
{
uint32_t bin = 0;
// Convert to binary
for (int i = 0; i < size; i++)
{
uint32_t shl = 0, shr = 0, q;
shl = (3 << (i << 1));
shr = i << 1;
q = v & shl;
q = q >> shr;
unsigned char c = static_cast<char>(q);
shl = (size - i - 1) << 1;
bin = bin | (c << shl);
}
return bin;
}
bool ckrev(std::string s1, std::string s2)
{
std::reverse(s1.begin(), s1.end());
return s1 == s2;
}
int main(int argc, char* argv[])
{
// Binary representation of base-4 number
uint32_t binr;
std::vector<std::string> chk { "123", "2230131" };
for (const auto &s : chk)
{
std::string b, r;
uint32_t c;
binr = tobin(s);
b = tostr(s.size(), binr);
c = revrs(s.size(), binr);
r = tostr(s.size(), c);
std::cout << "orig " << s << std::endl;
std::cout << "binr " << std::hex << binr << " string " << b << std::endl;
std::cout << "revs " << std::hex << c << " string " << r << std::endl;
std::cout << ">>> CHK " << (s == b) << " " << ckrev(r, b) << std::endl;
}
return 0;
}
这对 SSE 来说有点挑战，因为几乎没有位打包的规定（你想从每个字符中取出两个位并将它们连续打包）。不管怎样，特殊说明_mm_movemask_epi8可以帮到你。
对于字符串到二进制的转换，您可以进行如下操作：
加载16个字符的字符串（如有必要，加载后用零填充或清除）；
按字节减去 ASCII 零。
按字节比较 'unsigned greater than' 为 16 个“3”字节的字符串；这将在存在无效字符的地方设置字节 0xFF
使用_mm_movemask_epi8检测压缩短值中的此类字符
如果一切正常，您现在需要打包位对。为此，您需要
复制 16 个字节
将权重 1 和 2 的位向左移动 7 或 6 个位置，使它们最重要（_mm_sll_epi16。没有 epi8 版本，但是来自一个元素的位变为另一个元素的低位垃圾对此并不重要。）
将它们交错排列（_mm_unpack..._epi8，一次用 lo，一次用 hi）
将这两个向量的高位存储到 _mm_movemask_epi8 的短裤中。
对于二进制到字符串的转换，我想不出一个有意义的 SSE 实现，因为没有 _mm_movemask_epi8 的对应物可以让您有效地解包。
我会解决SSE上32位整数转base4字符串的问题。
不考虑删除前导零的问题，即 base4 字符串的长度始终为 16.
总的来说
显然，我们必须提取向量化形式的位对。
为此，我们可以执行一些字节操作和按位操作。
让我们看看我们可以用 SSE 做什么：
单个内在 _mm_shuffle_epi8（来自 SSSE3）允许以您想要的任何方式随机播放 16 个字节。
显然，一些结构良好的洗牌和寄存器混合可以使用 SSE2 中更简单的指令来完成，
但重要的是要记住，任何寄存器内洗牌都可以用一条廉价指令完成。
改组无助于更改字节中的位索引。
为了移动大块的位，我们通常使用位移。
遗憾的是，SSE 无法将 XMM 寄存器的不同元素移动不同的数量。
正如@PeterCorder 在评论中提到的，AVX2 中有这样的指令（例如 _mm_sllv_epi32），但它们至少以 32 位粒度运行。
自古以来，我们就不断地被教导，位移快，乘法慢。今天的算术速度如此之快，以至于不再如此。在 SSE 中，移位和乘法似乎具有相同的吞吐量，尽管乘法有更多的延迟。
- 使用乘以 2 的幂，我们可以将单个 XMM 寄存器的不同元素左移不同的量。有很多像
_mm_mulhi_epi16这样的指令允许16位粒度。另外一条指令 _mm_maddubs_epi16 允许 8 位粒度的移位。
右移可以通过左移完成，就像人们做 division via multiplication 一样：左移 16-k，然后右移两个字节（回想一下任何字节改组是便宜）。
我们实际上想要进行 16 次不同的移位。如果我们使用16位粒度的乘法，那么我们至少要用到两个XMM寄存器进行移位，然后它们才能合并在一起。另外，我们可以尝试使用 8 位粒度的乘法，在单个寄存器中完成所有操作。
16 位粒度
首先，我们要将32位整数移动到XMM寄存器的低4字节。然后我们打乱字节，使 XMM 寄存器的每个 16 位部分包含一个字节的输入：
|abcd|0000|0000|0000| before shuffle (little-endian)
|a0a0|b0b0|c0c0|d0d0| after shuffle (to low halves)
|0a0a|0b0b|0c0c|0d0d| after shuffle (to high halves)
然后我们可以调用_mm_mulhi_epi16将每个部分右移k = 1..16。实际上，将输入字节放入16位元素的高半部分更方便，这样我们就可以左移k = -8..7。因此，我们希望看到 XMM 寄存器的一些字节包含定义一些 base4 数字（作为它们的低位）的位对。之后我们可以通过_mm_and_si128去掉不需要的高位，把有价值的字节shuffle到合适的地方。
由于 16 位粒度一次只能完成 8 次移位，因此我们必须将移位部分做两次。然后我们把两个XMM寄存器合二为一
下面你可以看到使用这个想法的代码。它有点优化：位移后没有字节改组。
__m128i reg = _mm_cvtsi32_si128(val);
__m128i bytes = _mm_shuffle_epi8(reg, _mm_setr_epi8(-1, 0, -1, 0, -1, 1, -1, 1, -1, 2, -1, 2, -1, 3, -1, 3));
__m128i even = _mm_mulhi_epu16(bytes, _mm_set1_epi32(0x00100100)); //epi16: 1<<8, 1<<4 x4 times
__m128i odd = _mm_mulhi_epu16(bytes, _mm_set1_epi32(0x04004000)); //epi16: 1<<14, 1<<10 x4 times
even = _mm_and_si128(even, _mm_set1_epi16(0x0003));
odd = _mm_and_si128(odd , _mm_set1_epi16(0x0300));
__m128i res = _mm_xor_si128(even, odd);
res = _mm_add_epi8(res, _mm_set1_epi8('0'));
_mm_storeu_si128((__m128i*)s, res);
8 位粒度
当然，首先我们将 32 位整数移动到 XMM 寄存器中。然后我们打乱字节，使结果的每个字节等于包含该位置所需的两位的输入字节：
|abcd|0000|0000|0000| before shuffle (little-endian)
|aaaa|bbbb|cccc|dddd| after shuffle
现在我们使用 _mm_and_si128 来过滤位：在每个字节中只保留需要的两个位。之后我们只需要将每个字节右移 0/2/4/6 位。这应该通过内部 _mm_maddubs_epi16 来实现，它允许一次移动 16 个字节。不幸的是，我看不到如何仅使用此指令正确移动所有字节，但至少我们可以将每个奇数字节右移 2 位（偶数字节保持原样）。然后索引为 4k+2 和 4k+3 的字节可以用单个 _mm_madd_epi16 指令右移 4 位。
这是结果代码：
__m128i reg = _mm_cvtsi32_si128(val);
__m128i bytes = _mm_shuffle_epi8(reg, _mm_setr_epi8(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3));
__m128i twobits = _mm_and_si128(bytes, _mm_set1_epi32(0xC0300C03)); //epi8: 3<<0, 3<<2, 3<<4, 3<<6 x4 times
twobits = _mm_maddubs_epi16(twobits, _mm_set1_epi16(0x4001)); //epi8: 1<<0, 1<<6 x8 times
__m128i res = _mm_madd_epi16(twobits, _mm_set1_epi32(0x10000001)); //epi16: 1<<0, 1<<12 x4 times
res = _mm_add_epi8(res, _mm_set1_epi8('0'));
_mm_storeu_si128((__m128i*)s, res);
P.S.
这两种解决方案都使用了大量编译时常量 128 位值。它们没有编码成 x86 指令，因此每次使用它们时处理器都必须从内存（很可能是 L1 缓存）加载它们。但是，如果您要在一个循环中进行 运行 多次转换，那么编译器会在循环之前将所有这些常量加载到寄存器中（我希望如此）。
Here 您可以找到完整的代码（没有计时），包括由@YvesDaoust 实施的 str2bin 解决方案。
这应该是一个有趣的问题，至少对我来说是这样。
我的目的是操纵 base-4 数字，编码为无符号整数。每个两位块代表一个 base-4 数字，从 最低有效位开始 :
01 00 11 = base4(301)
我想使用 SSE 指令优化我的代码，因为我不确定我在这里的得分如何，也许很差。
代码从字符串开始（并使用它们来检查正确性），并实现：
- 将字符串转换为二进制
- 将二进制转换为字符串
- 反转数字
欢迎任何提示！
uint32_t tobin(std::string s)
{
uint32_t v, bin = 0;
// Convert to binary
for (int i = 0; i < s.size(); i++)
{
switch (s[i])
{
case '0':
v = 0;
break;
case '3':
v = 3;
break;
case '1':
v = 1;
break;
case '2':
v = 2;
break;
default:
throw "UNKOWN!";
}
bin = bin | (v << (i << 1));
}
return bin;
}
std::string tostr(int size, const uint32_t v)
{
std::string b;
// Convert to binary
for (int i = 0; i < size; i++)
{
uint32_t shl = 0, shr = 0, q;
shl = (3 << (i << 1));
shr = i << 1;
q = v & shl;
q = q >> shr;
unsigned char c = static_cast<char>(q);
switch (c)
{
case 0:
b += '0';
break;
case 3:
b += '3';
break;
case 1:
b += '1';
break;
case 2:
b += '2';
break;
default:
throw "UNKOWN!";
}
}
return b;
}
uint32_t revrs(int size, const uint32_t v)
{
uint32_t bin = 0;
// Convert to binary
for (int i = 0; i < size; i++)
{
uint32_t shl = 0, shr = 0, q;
shl = (3 << (i << 1));
shr = i << 1;
q = v & shl;
q = q >> shr;
unsigned char c = static_cast<char>(q);
shl = (size - i - 1) << 1;
bin = bin | (c << shl);
}
return bin;
}
bool ckrev(std::string s1, std::string s2)
{
std::reverse(s1.begin(), s1.end());
return s1 == s2;
}
int main(int argc, char* argv[])
{
// Binary representation of base-4 number
uint32_t binr;
std::vector<std::string> chk { "123", "2230131" };
for (const auto &s : chk)
{
std::string b, r;
uint32_t c;
binr = tobin(s);
b = tostr(s.size(), binr);
c = revrs(s.size(), binr);
r = tostr(s.size(), c);
std::cout << "orig " << s << std::endl;
std::cout << "binr " << std::hex << binr << " string " << b << std::endl;
std::cout << "revs " << std::hex << c << " string " << r << std::endl;
std::cout << ">>> CHK " << (s == b) << " " << ckrev(r, b) << std::endl;
}
return 0;
}
这对 SSE 来说有点挑战，因为几乎没有位打包的规定（你想从每个字符中取出两个位并将它们连续打包）。不管怎样，特殊说明_mm_movemask_epi8可以帮到你。
对于字符串到二进制的转换，您可以进行如下操作：
加载16个字符的字符串（如有必要，加载后用零填充或清除）；
按字节减去 ASCII 零。
按字节比较 'unsigned greater than' 为 16 个“3”字节的字符串；这将在存在无效字符的地方设置字节 0xFF
使用
_mm_movemask_epi8检测压缩短值中的此类字符
如果一切正常，您现在需要打包位对。为此，您需要
复制 16 个字节
将权重 1 和 2 的位向左移动 7 或 6 个位置，使它们最重要（_mm_sll_epi16。没有 epi8 版本，但是来自一个元素的位变为另一个元素的低位垃圾对此并不重要。）
将它们交错排列（_mm_unpack..._epi8，一次用 lo，一次用 hi）
将这两个向量的高位存储到 _mm_movemask_epi8 的短裤中。
对于二进制到字符串的转换，我想不出一个有意义的 SSE 实现，因为没有 _mm_movemask_epi8 的对应物可以让您有效地解包。
我会解决SSE上32位整数转base4字符串的问题。 不考虑删除前导零的问题，即 base4 字符串的长度始终为 16.
总的来说
显然，我们必须提取向量化形式的位对。 为此，我们可以执行一些字节操作和按位操作。 让我们看看我们可以用 SSE 做什么：
单个内在
_mm_shuffle_epi8（来自 SSSE3）允许以您想要的任何方式随机播放 16 个字节。 显然，一些结构良好的洗牌和寄存器混合可以使用 SSE2 中更简单的指令来完成， 但重要的是要记住，任何寄存器内洗牌都可以用一条廉价指令完成。改组无助于更改字节中的位索引。 为了移动大块的位，我们通常使用位移。 遗憾的是，SSE 无法将 XMM 寄存器的不同元素移动不同的数量。 正如@PeterCorder 在评论中提到的，AVX2 中有这样的指令（例如
_mm_sllv_epi32），但它们至少以 32 位粒度运行。
自古以来，我们就不断地被教导，位移快，乘法慢。今天的算术速度如此之快，以至于不再如此。在 SSE 中，移位和乘法似乎具有相同的吞吐量，尽管乘法有更多的延迟。
- 使用乘以 2 的幂，我们可以将单个 XMM 寄存器的不同元素左移不同的量。有很多像
_mm_mulhi_epi16这样的指令允许16位粒度。另外一条指令_mm_maddubs_epi16允许 8 位粒度的移位。 右移可以通过左移完成，就像人们做 division via multiplication 一样：左移 16-k，然后右移两个字节（回想一下任何字节改组是便宜）。
我们实际上想要进行 16 次不同的移位。如果我们使用16位粒度的乘法，那么我们至少要用到两个XMM寄存器进行移位，然后它们才能合并在一起。另外，我们可以尝试使用 8 位粒度的乘法，在单个寄存器中完成所有操作。
16 位粒度
首先，我们要将32位整数移动到XMM寄存器的低4字节。然后我们打乱字节，使 XMM 寄存器的每个 16 位部分包含一个字节的输入：
|abcd|0000|0000|0000| before shuffle (little-endian)
|a0a0|b0b0|c0c0|d0d0| after shuffle (to low halves)
|0a0a|0b0b|0c0c|0d0d| after shuffle (to high halves)
然后我们可以调用_mm_mulhi_epi16将每个部分右移k = 1..16。实际上，将输入字节放入16位元素的高半部分更方便，这样我们就可以左移k = -8..7。因此，我们希望看到 XMM 寄存器的一些字节包含定义一些 base4 数字（作为它们的低位）的位对。之后我们可以通过_mm_and_si128去掉不需要的高位，把有价值的字节shuffle到合适的地方。
由于 16 位粒度一次只能完成 8 次移位，因此我们必须将移位部分做两次。然后我们把两个XMM寄存器合二为一
下面你可以看到使用这个想法的代码。它有点优化：位移后没有字节改组。
__m128i reg = _mm_cvtsi32_si128(val);
__m128i bytes = _mm_shuffle_epi8(reg, _mm_setr_epi8(-1, 0, -1, 0, -1, 1, -1, 1, -1, 2, -1, 2, -1, 3, -1, 3));
__m128i even = _mm_mulhi_epu16(bytes, _mm_set1_epi32(0x00100100)); //epi16: 1<<8, 1<<4 x4 times
__m128i odd = _mm_mulhi_epu16(bytes, _mm_set1_epi32(0x04004000)); //epi16: 1<<14, 1<<10 x4 times
even = _mm_and_si128(even, _mm_set1_epi16(0x0003));
odd = _mm_and_si128(odd , _mm_set1_epi16(0x0300));
__m128i res = _mm_xor_si128(even, odd);
res = _mm_add_epi8(res, _mm_set1_epi8('0'));
_mm_storeu_si128((__m128i*)s, res);
8 位粒度
当然，首先我们将 32 位整数移动到 XMM 寄存器中。然后我们打乱字节，使结果的每个字节等于包含该位置所需的两位的输入字节：
|abcd|0000|0000|0000| before shuffle (little-endian)
|aaaa|bbbb|cccc|dddd| after shuffle
现在我们使用 _mm_and_si128 来过滤位：在每个字节中只保留需要的两个位。之后我们只需要将每个字节右移 0/2/4/6 位。这应该通过内部 _mm_maddubs_epi16 来实现，它允许一次移动 16 个字节。不幸的是，我看不到如何仅使用此指令正确移动所有字节，但至少我们可以将每个奇数字节右移 2 位（偶数字节保持原样）。然后索引为 4k+2 和 4k+3 的字节可以用单个 _mm_madd_epi16 指令右移 4 位。
这是结果代码：
__m128i reg = _mm_cvtsi32_si128(val);
__m128i bytes = _mm_shuffle_epi8(reg, _mm_setr_epi8(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3));
__m128i twobits = _mm_and_si128(bytes, _mm_set1_epi32(0xC0300C03)); //epi8: 3<<0, 3<<2, 3<<4, 3<<6 x4 times
twobits = _mm_maddubs_epi16(twobits, _mm_set1_epi16(0x4001)); //epi8: 1<<0, 1<<6 x8 times
__m128i res = _mm_madd_epi16(twobits, _mm_set1_epi32(0x10000001)); //epi16: 1<<0, 1<<12 x4 times
res = _mm_add_epi8(res, _mm_set1_epi8('0'));
_mm_storeu_si128((__m128i*)s, res);
P.S.
这两种解决方案都使用了大量编译时常量 128 位值。它们没有编码成 x86 指令，因此每次使用它们时处理器都必须从内存（很可能是 L1 缓存）加载它们。但是，如果您要在一个循环中进行 运行 多次转换，那么编译器会在循环之前将所有这些常量加载到寄存器中（我希望如此）。
Here 您可以找到完整的代码（没有计时），包括由@YvesDaoust 实施的 str2bin 解决方案。