gpt4 book ai didi

c - 如何优化KASUMI算法的S盒?

转载 作者:太空宇宙 更新时间:2023-11-03 23:41:00 25 4
gpt4 key购买 nike

非常感谢,我正在尝试优化用C编写的Kasumi算法。FI函数中有S-box用于加密数据,S7-box有127个元素,S9-box有512个元素。 FI 函数代码如下:

static u16 FI(u16 in, u16 subkey)
{
static u16 s7[] = {...};
static u16 s9[] = {...};

nine = (u16)(in>>7);
seven = (u16)(in&0x7F);
/* Now run the various operations */
nine = (u16)(S9[nine] ^ seven);
seven = (u16)(S7[seven] ^ (nine & 0x7F));
seven ^= (subkey>>9);
nine ^= (subkey&0x1FF);
nine = (u16)(S9[nine] ^ seven);
seven = (u16)(S7[seven] ^ (nine & 0x7F));
in = (u16)((seven<<9) + nine);
return( in );
}

u16代表unsigned short。

通过一些转换。我将S7-box和S9-box合并到S16-box,我用avx指令让16个数据并行。 FI函数的代码如下:

static u16 FI(__m256i in, u16 subkey)
{
u16 arr[16];
_mm256_store_si256((__m256i*)arr, in);
u8 i;
for(i = 0; i < 16; i++)
{
arr[i] = (u16)(s16[arr[i]] ^ subkey);
arr[i] = (arr[i] << 7) | (arr[i] >> 9);
arr[i] = s16[arr[i]];
}
in = _mm256_load_si256((__m256i*)arr);
}

S16-box 有 65536 个元素,所以可能会发生一些缓存未命中。我还使用收集指令,如:

inline static __m256i FI( __m256i in, u16 subkey )
{
__m256i _tmp = _mm256_set1_epi32(0xffff);
__m256i even_sequence = _mm256_and_si256(in, _tmp);
__m256i odd_sequence = _mm256_srli_epi32(in, 16);
even_sequence = _mm256_i32gather_epi32((int const*)s16, even_sequence, 2);
__m256i _subkey = _mm256_set1_epi16(subkey);
even_sequence = _mm256_xor_si256(even_sequence, _subkey);
even_sequence = _mm256_and_si256(even_sequence, _tmp);
odd_sequence = _mm256_i32gather_epi32((int const*)s16, odd_sequence, 2);
odd_sequence = _mm256_xor_si256(odd_sequence, _subkey);
odd_sequence = _mm256_and_si256(odd_sequence, _tmp);
// rotate
__m256i hi = _mm256_slli_epi16(even_sequence, 7);
__m256i lo = _mm256_srli_epi16(even_sequence, 9);
even_sequence = _mm256_or_si256(hi, lo);
//same for odd
hi = _mm256_slli_epi16(odd_sequence, 7);
lo = _mm256_srli_epi16(odd_sequence, 9);
odd_sequence = _mm256_or_si256(hi, lo);
even_sequence = _mm256_i32gather_epi32((int const*)s16, even_sequence, 2);
odd_sequence = _mm256_i32gather_epi32((int const*)s16, odd_sequence, 2);
even_sequence = _mm256_and_si256(even_sequence, _tmp);
odd_sequence = _mm256_slli_epi32(odd_sequence, 16);
in = _mm256_or_si256(even_sequence, odd_sequence);

return in;
}

但是性能达不到要求,我也在考虑bit-slice。我读了一篇可以并行处理 128 个数据但需要一些硬件支持的论文。我认为位转置操作很耗时,而且有很多约束。

非常感谢!

最佳答案

这段代码可能会解释性能问题以及您在其下方的评论。

static u16 FI(__m256i in, u16 subkey) {
u16 arr[16];
_mm256_store_si256((__m256i*)arr, in);
u8 i;
for(i = 0; i < 16; i++)
{
arr[i] = (u16)(s16[arr[i]] ^ subkey);
arr[i] = (arr[i] << 7) | (arr[i] >> 9);
arr[i] = s16[arr[i]];
}
in = _mm256_load_si256((__m256i*)arr);
}

S16-box has 65536 elements, so maybe some cache miss will happen.

平均 x64 处理器只有 32KB 的 L1(AMD 的有时有 64K,但现在让我们忽略它)。

这意味着如果没有其他数据结构使用任何 L1 并且您没有运行 hypertrhreading,您的 64K 阵列将获得 32KB/64KB * 100% = 50% 的缓存命中率另一个线程。

让我们将其简化为您只有 64KB 中的 16KB,每次访问都有 75% 的失误几率。所以你的循环在每一行之间都有数据依赖性,即。下一个语句不能在上一个语句完成之前开始。幸运的是,每次迭代都是独立于其他迭代的数据。

arr[i] = (u16)(s16[arr[i]] ^ subkey);
arr[i] = (arr[i] << 7) | (arr[i] >> 9);
arr[i] = s16[arr[i]];

arr此时几乎肯定会在L1缓存中,只产生4个周期的启动成本,每次访问s16平均成本为0.25*4+0.75*12 = 1+9 = 10 个周期。这给出了每个语句的以下近似延迟成本(忽略 arr[i] 的存储和重新加载的成本,假设 arr[i] 存储在寄存器中)

arr[i] = (u16)(s16[arr[i]] ^ subkey); // arr: 4 + S16: 10 + ^:1
arr[i] = (arr[i] << 7) | (arr[i] >> 9); // << : 1 + |: 1
arr[i] = s16[arr[i]]; // s16 : 10 + store arr : 4

每次迭代有 31 个周期延迟,幸运的是每次迭代之间没有数据依赖性。每次迭代大约需要 3 个周期来发布,因此最后一次将在 ~3*16+31=79 个周期内完成,假设完美的分支预测并忽略最后分配 in 的数据风险。

我认为您的下一个代码是这个重写为 AVX2 的循环将具有许多相同的加载依赖性和完全相同的缓存未命中,循环开销将消失但一些更长的延迟 AVX 指令可能会增加时间。平均时间仍然是大约 31 个周期的延迟 + 一些 AVX 延迟 + 16 个负载/(每个周期最多 2 个负载),比方说 40 个周期。

如果您没有合并 S7 和 S9,它们将只占用 (128+512)*2 个字节,并且当您运行更长的编码时,它们几乎肯定总是在 L1 缓存中。然后,循环延迟将减半,代价是负载数量翻倍,您的完整 AVX 达到大约 15 + 32 负载/每个周期 2,比方说 30 个周期。

好消息是每个 16 字节的迭代似乎都独立于前一个,因此它们可以在时间上重叠。但是您最终会受到加载和存储数量的限制,一次初始加载,来自 s7+s9 的 32 次加载和一次存储,最多 2 次存储或加载将最佳吞吐量限制为 16 字节/((1+32+ 1)/2) 周期。

这是在做出很多乐观的假设,只有对 2 种不同代码(s16 vs s7+s9)的实际测量才能决定什么是最好的。

关于c - 如何优化KASUMI算法的S盒?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45704142/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com