c++ - 优化 block 位操作 : base-4 numbers

Question

这应该是一个有趣的问题，至少对我而言。

我的意图是操纵base-4 数字，编码为无符号整数。然后，每个两位 block 代表一个 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;
}

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 将这两个 vector 的高位存储到 short 中。

对于二进制到字符串的转换，我想不出一个有意义的 SSE 实现，因为没有 _mm_movemask_epi8 的对应物可以让您有效地解包。