将 Bitshift 优化为数组

Question

我有一段代码在执行一些任务后每秒运行约 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 


    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。我不是代码的原始作者，但是我已经分叉它并使用修改后的速度版本维护密码恢复解决方案。您可以看到我在 ReverseBits 中通过各种解决方案和基准速度获得的加速成功。

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

Answer 1

我的直接想法是 "view" int32_t 就好像它们是 int8_t 的数组一样

uint8_t data2[8];
*((uint32_t*)&data2[0]) = right1;
*((uint32_t*)&data2[4]) = left1;

但是，您将 right1 的最高有效位存储在 data[0] 中，而这种方法让最低有效位进入 data[0]。无论如何，因为我不知道 ReverseBits 的作用以及您是否也可以根据不同的顺序调整您的代码，也许它有帮助...

Answer 2

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

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

将 Bitshift 优化为数组

Optimizing Bitshift into Array

c++

optimization

bit-shift

uint32

uint8t