在执行某些任务之后,我有一段代码以每秒约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 并使用经过修改的Speed版本维护密码恢复解决方案。您可以看到我在ReverseBits中以各种解决方案和基准速度提高了速度。

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

最佳答案

当然,您要做的工作比需要做的还要多。请注意ReverseBits()函数如何努力以正确的顺序放置反转单词的字节,以及接下来发生的事情(归因于减速的部分)是如何对这些相同的字节重新排序。

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

关于c++ - 优化位移入阵列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41797566/

10-09 07:42