'memcpy' 类函数，支持按单个位进行偏移？

Question

我正在考虑解决这个问题，但它看起来是一项艰巨的任务。如果我自己拿这个，我可能会用几种不同的方式编写它并选择最好的，所以我想我会问这个问题，看看是否已经有一个很好的库可以解决这个问题，或者是否有人 thoughts/advice.

void OffsetMemCpy(u8* pDest, u8* pSrc, u8 srcBitOffset, size size)
{
    // Or something along these lines. srcBitOffset is 0-7, so the pSrc buffer 
    // needs to be up to one byte longer than it would need to be in memcpy.
    // Maybe explicitly providing the end of the buffer is best.
    // Also note that pSrc has NO alignment assumptions at all.
}

我的应用程序时间紧迫，所以我想以最小的开销来解决这个问题。这是difficulty/complexity的来源。在我的例子中，块可能非常小，可能是 4-12 字节，所以大规模的 memcpy 东西（例如预取）并不是那么重要。对于随机未对齐的 src 缓冲区，最好的结果是在 4 到 12 之间的常量 'size' 输入中最快的结果。

尽可能以字大小的块移动内存
对齐这些字大小的块很重要。 pSrc 是未对齐的，所以我们可能需要从前面读取几个字节，直到它对齐。

有人拥有或知道类似的实现吗？或者有人想尝试写这篇文章，让它尽可能干净高效吗？

编辑：似乎人们正在投票"close" "too broad"。一些缩小的细节将是 AMD64 是首选架构，所以让我们假设。这意味着 little endian 等。实现有望很好地适应答案的大小，所以我认为这不会太宽泛。尽管有几种方法，我要求的答案一次是一个单一的实现。

Answer 1

我将从一个简单的实现开始，例如：

inline void OffsetMemCpy(uint8_t* pDest, const uint8_t* pSrc, const uint8_t srcBitOffset, const size_t size)
{
    if (srcBitOffset == 0)
    {
        for (size_t i = 0; i < size; ++i)
        {
            pDest[i] = pSrc[i];
        }
    }
    else if (size > 0)
    {
        uint8_t v0 = pSrc[0];
        for (size_t i = 0; i < size; ++i)
        {
            uint8_t v1 = pSrc[i + 1];
            pDest[i] = (v0 << srcBitOffset) | (v1 >> (CHAR_BIT - srcBitOffset));
            v0 = v1;            
        }
    }
}

（警告：未经测试的代码！）。

一旦运行正常，然后在您的应用程序中对其进行配置 - 您可能会发现它的速度足以满足您的需求，从而避免过早优化的陷阱。如果没有，那么您有一个有用的基线参考实现，可用于进一步的优化工作。

请注意，对于小副本，测试对齐和字大小副本等的开销可能远远超过任何好处，因此像上面这样的简单逐字节循环可能接近最佳。

另请注意，优化很可能与体系结构相关 - 对一个人有益的微观优化 CPU 可能对另一个人产生反作用。

Answer 2

我认为简单的逐字节解决方案（参见@PaulR 的回答）是小块的最佳方法，除非您可以满足以下附加约束：

输入缓冲区分配了一些填充，即在最后一个字节之后访问一些字节不会崩溃。
输出缓冲区也分配了一些填充，即使覆盖了所需结果位置之后的几个字节也没有关系。如果它确实很重要，那么您将需要做更多的事情来保留那些结束后的字节。
涉及的输入和输出范围不重叠（包括结束后的几个填充字节），就像在memcpy中一样。

如果可以，则可以增加算法的粒度。很容易更改@PaulR 的答案以在所有地方使用 uint64_t 个单词而不是 uint8_t 个字节。因此，它会工作得更快。

我们可以使用 SSE 进一步增加字数。由于在 SSE 中无法按位移位整个寄存器，我们必须对 64 位整数进行两次移位，然后将结果粘合在一起。粘合是由 SSSE3 中的 _mm_shuffle_epi8 完成的，它允许以任意方式随机排列 XMM 寄存器中的字节。对于移位，我们使用 _mm_srl_epi64，因为这是将 64 位整数移位非立即位数的唯一方法。我已将 C 中的 restrict 关键字（作为宏）添加到指针参数，因为如果它们是别名，则该算法将无法正常工作。

代码如下：

void OffsetMemCpy_stgatilov(uint8_t *RESTRICT pDest, const uint8_t *RESTRICT pSrc, const uint8_t srcBitOffset, const size_t size) {
    __m128i bits = (sizeof(size_t) == 8 ? _mm_cvtsi64_si128(srcBitOffset) : _mm_cvtsi32_si128(srcBitOffset));
    const uint8_t *pEnd = pSrc + size;
    while (pSrc < pEnd) {
        __m128i input = _mm_loadu_si128((__m128i*)pSrc);
        __m128i reg = _mm_shuffle_epi8(input, _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14));
        __m128i shifted = _mm_srl_epi64(reg, bits);
        __m128i comp = _mm_shuffle_epi8(shifted, _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, -1, -1));
        _mm_storeu_si128((__m128i*)pDest, comp);
        pSrc += 14;  pDest += 14;
    }
}

它每次迭代处理 14 个字节。每次迭代都相当简单，循环之前也有一些代码。这是由 MSVC2013 x64 生成的整个函数体的汇编代码：

    movzx   eax, r8b
    movd    xmm3, rax
    lea rax, QWORD PTR [rdx+r9]
    cmp rdx, rax
    jae SHORT $LN1@OffsetMemC
    movdqa  xmm1, XMMWORD PTR __xmm@0e0d0c0b0a0908070706050403020100
    movdqa  xmm2, XMMWORD PTR __xmm@ffff0e0d0c0b0a090806050403020100
    sub rcx, rdx
    npad    11
$LL2@OffsetMemC:
    movdqu  xmm0, XMMWORD PTR [rdx]
    add rdx, 14
    pshufb  xmm0, xmm1
    psrlq   xmm0, xmm3
    pshufb  xmm0, xmm2
    movdqu  XMMWORD PTR [rcx+rdx-14], xmm0
    cmp rdx, rax
    jb  SHORT $LL2@OffsetMemC
$LN1@OffsetMemC:
    ret 0

IACA 表示整个函数在 Ivy Bridge 上需要 4.5 个周期的吞吐量和 13 个周期的延迟，假设循环执行一次并且 caches/branches/decoding 没有问题发生。然而，在基准测试中，平均一次此类调用花费 7.5 个周期。

以下是 Ivy Bridge 3.4 Ghz 吞吐量基准测试的简要结果（请参阅代码中的更多结果）：

(billions of calls per second)
size = 4:
  0.132  (Paul R)
  0.248  (Paul R x64)
  0.45  (stgatilov)
size = 8:
  0.0782  (Paul R)
  0.249  (Paul R x64)
  0.45  (stgatilov)
size = 12:
  0.0559  (Paul R)
  0.191  (Paul R x64)
  0.453  (stgatilov)

但是请注意，在现实世界中，性能可能与基准测试结果大不相同。

具有基准测试和更详细结果的完整代码是 here。

'memcpy' 类函数，支持按单个位进行偏移？

'memcpy'-like function that supports offsets by individual bits?

c

c++

optimization

bit-manipulation

memcpy