并行/组合的多个64位值的按位置换

Question

这个问题不是关于"我如何按位排列"我们现在如何做到这一点,我们正在寻找的是一种更快的方式,更少的CPU指令,受到DES中sbox的bitlice实现的启发

为了加快一些密码,我们希望减少排列调用的数量.主要密码函数基于查找数组执行多个按位排列.由于置换操作只是位移,

我们的基本思想是采用需要相同排列的多个输入值,并将它们并行移位.例如,如果必须将输入位1移动到输出位6.

有没有办法做到这一点？我们现在没有示例代码,因为绝对不知道如何以高效的方式实现这一目标.

我们平台上的最大值大小为128位,最长输入值为64位.因此代码必须更快,然后进行128次整个排列.

编辑

这是一个简单的8位排列示例

+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | <= Bits
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | <= Input
+---+---+---+---+---+---+---+---+
| 3 | 8 | 6 | 2 | 5 | 1 | 4 | 7 | <= Output
+---+---+---+---+---+---+---+---+

密码使用多个输入密钥.它是块密码,因此必须将相同的模式应用于输入的所有64位块.

由于每个输入块的排列相同,我们希望在一个步骤中处理多个输入块/组合多个输入序列的操作.而不是每次呼叫移动128次一位,一次移动1次128位.

EDIT2

我们不能使用线程,因为我们必须在没有线程支持的情况下在嵌入式系统上运行代码.因此,我们也无法访问外部库,我们必须保持简单C.

解

在测试并使用给定的答案后,我们通过以下方式完成:

• 我们将128位64位值的单位放在uint128_t [64]*数组上.
• 对于排列,我们只需要复制指针
• 完成所有操作后,我们将恢复第一个操作并返回128个置换值

是的,这很简单.我们在项目早期就这样测试,但速度太慢了.看来我们在测试代码中有一个错误.

谢谢大家,提示和耐心.

Answer 1

通过使用八个将字节映射到 64 位字的查找表，您可以使 Stan 的逐位代码更快。要处理输入中的 64 位字，请将其拆分为八个字节，并从不同的查找表中查找每个字节，然后对结果进行“或”运算。在我的计算机上，后者比 32 位排列的逐位方法快 10 倍。显然，如果您的嵌入式系统缓存很少，那么32 kB 16 kB 的查找表可能会出现问题。如果一次处理4位，则只需要16个查找表，每个查找表16*8=128字节，即2 kB的查找表。

编辑：内部循环可能看起来像这样：

void permute(uint64_t* input, uint64_t* output, size_t n, uint64_t map[8][256])
{
    for (size_t i = 0; i < n; ++i) {
        uint8_t* p = (uint8_t*)(input+i);
        output[i] = map[0][p[0]] | map[1][p[1]] | map[2][p[2]] | map[3][p[3]]
            | map[4][p[4]] | map[5][p[5]] | map[6][p[6]] | map[7][p[7]];
    }
}