拉伸掩码 - 位运算

Question

我可以帮助您翻译。以下是翻译的结果，但请注意，由于保留了原始格式和标签，它可能不太自然。要拉伸每个位表示4位的拉伸掩码。我正在寻找一种优雅的位操作，使用c++和systemC进行拉伸。

例如：

输入:

mask (32 bits) = 0x0000CF00

输出：

stretched mask (128 bits) = 0x00000000 00000000 FF00FFFF 00000000

为了澄清这个例子，让我们看一下字节C：

0xC = 1100 after stretching: 1111111100000000 = 0xFF00

- Noa Yehezkel

---

_pdep_u32 是被允许的吗？ - harold

你想要扩展任意数量的位数，比如17、78等吗？还是只需要16或32的倍数？ - izlin

你能解释一下你实际要解决的根本问题是什么吗？像这样拉伸一个掩码听起来像是一个非常奇怪的操作。 - abelenky

https://dev59.com/WGgt5IYBdhLWcg3wygab#27592777 - dtech

Answer 1

以优雅的方式完成这个任务并不容易。简单的方法可能是使用位移运算符创建循环。

sc_biguint<128> result = 0;
for(int i = 0; i < 32; i++){
    if(bit_test(var, i)){
        result +=0x0F;
    }
    result << 4;
}

- rodrigo

---

请注意，result需要一个至少为32*4=128位的类型。 - izlin

是的，所以我相信你可以创建一个变量类型或使用向量。 - rodrigo

我正在使用 SystemC 库，所以有 sc_biguint<128> 这种类型。 第三行缺少括号。 - Noa Yehezkel

Answer 2

这是一种将16位掩码拉伸为64位的方法，其中每个位表示4位拉伸掩码的方法：

uint64_t x = 0x000000000000CF00LL;

x = (x | (x << 24)) & 0x000000ff000000ffLL;
x = (x | (x << 12)) & 0x000f000f000f000fLL;
x = (x | (x << 6)) & 0x0303030303030303LL;
x = (x | (x << 3)) & 0x1111111111111111LL;
x |= x << 1;
x |= x << 2;

首先，它从底部16位中获取掩码。然后将掩码的前8位移动到顶部32位中，如下所示：

0000000000000000 0000000000000000 0000000000000000 ABCDEFGHIJKLMNOP

变成

0000000000000000 00000000ABCDEFGH 0000000000000000 00000000IJKLMNOP

然后它解决了一个类似的问题，即将32位字的底部8位拉伸到顶部和底部的32位同时：

000000000000ABCD 000000000000EFGH 000000000000IJKL 000000000000MNOP

然后它会在16位中处理4位，以此类推，直到所有位都被分散开来。

000A000B000C000D 000E000F000G000H 000I000J000K000L 000M000N000O000P

然后它通过将结果与两个自身的OR运算符"涂抹"在4位上。

AAAABBBBCCCCDDDD EEEEFFFFGGGGHHHH IIIIJJJJKKKKLLLL MMMMNNNNOOOOPPPP

您可以通过添加一个额外的第一步骤，即将其向左移动48个比特并与一个128位常量进行掩码处理，从而将其扩展到128位：

x = (x | (x << 48)) & 0x000000000000ffff000000000000ffffLLL;

你还需要将其他常量通过重复比特模式扩展到128位。但是（据我所知），在C ++中没有声明128位常量的方法，但也许你可以使用宏或其他方式来实现（参见此问题）。你也可以通过将64位版本分别用于顶部和底部16位来创建128位版本。

如果加载掩码常数变得困难或成为瓶颈，您可以使用移位和掩码从前一个常数生成每个常数：

uint64_t m = 0x000000ff000000ffLL;

m &= m >> 4; m |= m << 16;  // gives 0x000f000f000f000fLL
m &= m >> 2; m |= m << 8;  // gives 0x0303030303030303LL
m &= m >> 1; m |= m << 4; // gives 0x1111111111111111LL

- samgak

---

最后两条指令（x |= x<<2; x |= x<<1）可以被替换为x*=0xf。 - MSalters

看起来掩码也可以成对组合。也就是说，您可以从 (x *= (1+1ULL<<12+1ULL<<24+1ULL<<36) 开始。您会有一些位碰撞的位置，但无论如何都可以屏蔽它们。 - MSalters

Answer 3

这对您有用吗？

#include <stdio.h>

long long Stretch4x(int input)
{
    long long output = 0;

    while (input & -input)
    {
        int b = (input & -input);
        long long s = 0;
        input &= ~b;
        s = b*15;
        while(b>>=1)
        {
            s <<= 3;
        }

        output |= s;
    }
    return output;  
}

int main(void) {
    int input = 0xCF00;

    printf("0x%0x ==> 0x%0llx\n", input, Stretch4x(input));
    return 0;
}

输出:

0xcf00 ==> 0xff00ffff00000000

- abelenky

Answer 4

其他解决方案都不错。然而，它们大多数更偏向于C语言而非C++。这个解决方案非常直接：它使用 std::bitset 并为每个输入位设置四个位。

#include <bitset>
#include <iostream>

std::bitset<128> 
starch_32 (const std::bitset<32> &input)
{
    std::bitset<128> output;

    for (size_t i = 0; i < input.size(); ++i) {
        // If `input[N]` is `true`, set `output[N*4, N*4+4]` to true.
        if (input.test (i)) {
            const size_t output_index = i * 4;

            output.set (output_index);
            output.set (output_index + 1);
            output.set (output_index + 2);
            output.set (output_index + 3);
        }
    }

    return output;
}

// Example with 0xC. 
int main() {
    std::bitset<32> input{0b1100};

    auto result = starch_32 (input);

    std::cout << "0x" << std::hex << result.to_ullong() << "\n";
}

Try it online!

- Shmuel H.

Answer 5

在x86上，您可以使用PDEP 内嵌函数将16位掩码位移动到64位字的正确半字节中（例如，每个半字节的低位），然后使用一对shift +或操作将它们扩散到单词的其余部分：

unsigned long x = _pdep_u64(m, 0x1111111111111111);
x |= x << 1;
x |= x << 2;

您可以通过单个乘法运算符 0xF 来代替这两个OR和两个shift操作，以达到相同的扩散效果。

最后，您可以考虑采用SIMD方法：像上面samgak提出的解决方案应该可以自然地映射到SIMD。

- BeeOnRope