gpt4 book ai didi

c++ - 将 Bitshift 优化为数组

转载 作者:行者123 更新时间:2023-11-30 02:27:24 36 4
gpt4 key购买 nike

我有一段代码在执行一些任务后每秒运行约 120 万次,最大的是设置一个 uint8_t 数组,其中包含来自两个 uint32_t 数据的位移数据。摘录代码如下:

    static inline uint32_t RotateRight(uint32_t val, int n)
{
return (val >> n) + (val << (32 - n));

}

static inline uint32_t CSUInt32BE(const uint8_t *b)
{
return ((uint32_t)b[0] << 24) | ((uint32_t)b[1] << 16) | ((uint32_t)b[2] << 8) | (uint32_t)b[3];
}

static uint32_t ReverseBits(uint32_t val) // Usually just static, tried inline/static inline
{
// uint32_t res = 0;
// for (int i = 0; i<32; i++)
// {
// res <<= 1;
// res |= val & 1;
// val >>= 1;
// }
// Original code above, benched ~220k l/s

//val = ((val & 0x55555555) << 1) | ((val >> 1) & 0x55555555);
//val = ((val & 0x33333333) << 2) | ((val >> 2) & 0x33333333);
//val = ((val & 0x0F0F0F0F) << 4) | ((val >> 4) & 0x0F0F0F0F);
//val = ((val & 0x00FF00FF) << 8) | ((val >> 8) & 0x00FF00FF);
//val = (val << 16) | (val >> 16);
// Option 0, benched ~770k on MBP

uint32_t c = 0;
c = (BitReverseTable256[val & 0xff] << 24) |
(BitReverseTable256[(val >> 8) & 0xff] << 16) |
(BitReverseTable256[(val >> 16) & 0xff] << 8) |
(BitReverseTable256[val >> 24]); // was (val >> 24) & 0xff
// Option 1, benched ~970k l/s on MBP, Current, minor tweak to 24

//unsigned char * p = (unsigned char *)&val;
//unsigned char * q = (unsigned char *)&c;
//q[3] = BitReverseTable256[p[0]];
//q[2] = BitReverseTable256[p[1]];
//q[1] = BitReverseTable256[p[2]];
//q[0] = BitReverseTable256[p[3]];
// Option 2 at ~970k l/s on MBP from http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c


return c; // Current
// return val; // option 0
// return res; // original


//uint32_t m;
//val = (val >> 16) | (val << 16); // swap halfwords
//m = 0x00ff00ff; val = ((val >> 8) & m) | ((val << 8) & ~m); // swap bytes
//m = m^(m << 4); val = ((val >> 4) & m) | ((val << 4) & ~m); // swap nibbles
//m = m^(m << 2); val = ((val >> 2) & m) | ((val << 2) & ~m);
//m = m^(m << 1); val = ((val >> 1) & m) | ((val << 1) & ~m);
//return val;
// Benches at 850k l/s on MBP

//uint32_t t;
//val = (val << 15) | (val >> 17);
//t = (val ^ (val >> 10)) & 0x003f801f;
//val = (t + (t << 10)) ^ val;
//t = (val ^ (val >> 4)) & 0x0e038421;
//val = (t + (t << 4)) ^ val;
//t = (val ^ (val >> 2)) & 0x22488842;
//val = (t + (t << 2)) ^ val;
//return val;
// Benches at 820k l/s on MBP
}
static void StuffItDESCrypt(uint8_t data[8], StuffItDESKeySchedule *ks, BOOL enc)
{
uint32_t left = ReverseBits(CSUInt32BE(&data[0]));
uint32_t right = ReverseBits(CSUInt32BE(&data[4]));

right = RotateRight(right, 29);
left = RotateRight(left, 29);

//Encryption function runs here

left = RotateRight(left, 3);
right = RotateRight(right, 3);

uint32_t left1 = ReverseBits(left);
uint32_t right1 = ReverseBits(right);

data[0] = right1 >> 24;
data[1] = (right1 >> 16) & 0xff;
data[2] = (right1 >> 8) & 0xff;
data[3] = right1 & 0xff;
data[4] = left1 >> 24;
data[5] = (left1 >> 16) & 0xff;
data[6] = (left1 >> 8) & 0xff;
data[7] = left1 & 0xff;

这是实现此目标的最佳方式吗?我也有一个 uint64_t 版本:

uint64_t both = ((uint64_t)ReverseBits(left) << 32) | (uint64_t)ReverseBits(right);

data[0] = (both >> 24 & 0xff);
data[1] = (both >> 16) & 0xff;
data[2] = (both >> 8) & 0xff;
data[3] = both & 0xff;
data[4] = (both >> 56);
data[5] = (both >> 48) & 0xff;
data[6] = (both >> 40) & 0xff;
data[7] = (both >> 32) & 0xff;

我测试了如果我完全跳过这个赋值会发生什么(ReverseBits 函数仍然完成),并且代码以每秒约 650 万次运行的速度运行。此外,如果我也只做一个,即使不触及其他 7 个作业,速度也会达到 120 万。

我不愿意认为这个操作会因为这项工作而大幅降低 80% 的速度,而且不能再快了。

这是在 Windows Visual Studio 2015 上运行的(尽管我尽量使源代码尽可能适用于 macOS 和 Linux)。

编辑:完整的基本代码位于 Github .我不是代码的原始作者,但是我已经 fork 它并使用修改后的速度版本维护密码恢复解决方案。您可以看到我在 ReverseBits 中通过各种解决方案和基准速度取得的加速成功。

这些文件已有 20 多年的历史,多年来已成功恢复文件,尽管速度很慢。参见 blog post .

最佳答案

您所做的工作肯定比您需要做的要多。请注意函数 ReverseBits() 是如何努力将反转后的单词的字节按正确的顺序排列的,以及接下来发生的事情——您将减速归因于此的部分——是重新排序那些相同的字节。

您可以编写和使用 ReverseBits() 的修改版本,将反转表示的字节直接放入数组中的正确位置,而不是将它们打包成整数只是为了再次解包.这至少应该快一点,因为您将严格删除操作。

关于c++ - 将 Bitshift 优化为数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41797566/

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