优化块位操作:基-4位数

Question

这应该是个有趣的问题，至少对我来说。

我的目的是操纵基-4数字，编码为无符号整数。然后，每个两位块表示一个基-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;
}

Answer 1

对于SSE来说，这有点困难，因为几乎没有比特打包的规定(您希望从每个字符中提取两位，并将它们连续打包)。不管怎么说，_mm_movemask_epi8的特殊指令可以帮助你。

对于字符串到二进制转换，可以按以下方式进行：

• 加载16个字符字符串(垫与零或清除后，如果必要的加载)；
• 用ASCII零减去。
• 按字节顺序“无符号大于”与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可以让您高效地解压缩。

Answer 2

我将解决在SSE上将32位整数转换为base4字符串的问题。不考虑移除前导零的问题，即base4字符串的长度总是16。

一般通关

显然，我们必须以矢量化的形式提取对位。为了做到这一点，我们可以执行一些字节操作和按位操作。让我们看看我们能用SSE做些什么：

1. 一个单一的内部_mm_shuffle_epi8 (来自SSSE3)允许以任何你想要的方式洗牌16个字节。显然，一些结构良好的改组和注册混合可以用更简单的SSE2指令来完成，但重要的是要记住，任何寄存器内的改组都可以用一条廉价的指令来完成。
2. 洗牌无助于改变字节中的位索引。为了在周围移动比特块，我们通常使用位移位。不幸的是，SSE中没有办法将XMM寄存器的不同元素移动不同的数量。正如@PeterCorder在注释中提到的那样，在AVX2 (例如_mm_sllv_epi32)中有这样的指令，但是它们至少在32位粒度上操作。

自古以来，我们就不断地被教导，位变换是快的，乘法是慢的。今天的算术速度如此之快，以至于现在已不再如此。在SSE中，移位和乘法似乎具有相同的吞吐量，尽管乘法有更多的延迟。

1. 利用二次方乘积，可以将单个XMM寄存器的不同元素左移不同的个数。有许多像_mm_mulhi_epi16这样的指令，它们允许16位的粒度。另外，一条指令_mm_maddubs_epi16允许8位移位粒度.右移可以通过左移位完成，就像人们做乘除法一样:向左移动16-k，然后向右移动2字节(回想一下，任何字节洗牌都很便宜)。

我们实际上想做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删除不必要的高比特，并将有价值的字节洗牌到适当的位置。

由于只有8班可以一次完成16位粒度，我们必须做两次移动部分。然后我们将两个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);

附注：

这两种解决方案都使用大量的编译时常数128位值.它们没有被编码到x86指令中，所以每次使用它们时，处理器都必须从内存(很可能是L1缓存)加载它们。但是，如果要在一个循环中运行许多转换，那么编译器将在循环之前将所有这些常量加载到寄存器中(我希望如此)。

这里可以找到完整的代码(没有计时)，包括@YvesDaoust实现str2bin解决方案。