c - 按位记忆移动

Question

实现按位的最佳方法是什么memmove？该方法应该采用额外的目标和源位偏移量，并且计数也应该以位为单位。

• 我看到 ARM 提供了一个 non-standard _membitmove，这正是我需要的，但我找不到它的来源。
• Bind 的 bitset 包含isc_bitstring_copy，但效率不高
• 我知道 C 标准库没有提供这种方法，但我也找不到任何提供类似方法的第三方代码。

Answer 1

假设“最佳”意味着“最简单”，您可以逐位复制。从概念上讲，位的地址是一个对象（结构），它具有指向内存中字节的指针和字节中位的索引。

struct pointer_to_bit
{
    uint8_t* p;
    int b;
};

void membitmovebl(
    void *dest,
    const void *src,
    int dest_offset,
    int src_offset,
    size_t nbits)
{
    // Create pointers to bits
    struct pointer_to_bit d = {dest, dest_offset};
    struct pointer_to_bit s = {src, src_offset};

    // Bring the bit offsets to range (0...7)
    d.p += d.b / 8; // replace division by right-shift if bit offset can be negative 
    d.b %= 8; // replace "%=8" by "&=7" if bit offset can be negative
    s.p += s.b / 8;
    s.b %= 8;

    // Determine whether it's OK to loop forward
    if (d.p < s.p || d.p == s.p && d.b <= s.b)
    {
        // Copy bits one by one
        for (size_t i = 0; i < nbits; i++)
        {
            // Read 1 bit
            int bit = (*s.p >> s.b) & 1;

            // Write 1 bit
            *d.p &= ~(1 << d.b);
            *d.p |= bit << d.b;

            // Advance pointers
            if (++s.b == 8)
            {
                s.b = 0;
                ++s.p;
            }
            if (++d.b == 8)
            {
                d.b = 0;
                ++d.p;
            }
        }
    }
    else
    {
        // Copy stuff backwards - essentially the same code but ++ replaced by --
    }
}

如果你想编写一个针对速度优化的版本，你将不得不按字节（或者，更好的是，单词）复制，展开循环，并处理一些特殊情况（memmove这样做；你将不得不做更多，因为你的函数比较复杂）。

PS哦，看你调用isc_bitstring_copy效率低下，估计是要速度优化了。您可以使用以下想法：

开始逐个复制位，直到目标是字节对齐的 ( d.b == 0)。然后，很容易一次复制 8 位，做一些操作。这样做直到剩下少于 8 位要复制；然后继续逐位复制。

// Copy 8 bits from s to d and advance pointers
*d.p = *s.p++ >> s.b;
*d.p++ |= *s.p << (8 - s.b);

PPS 哦，看到您对代码的用途的评论，您实际上并不需要实现所有版本（字节/半字/字，大/小端）；您只需要最简单的一个 - 使用单词 ( uint32_t) 的那个。

Answer 2

这是部分实现（未测试）。有明显的效率和可用性改进。

将n字节从srcto复制到dest（不重叠src），并将位dest向右移动bit位，0 <= bit<= 7。这假设最低有效位在字节的右侧

void memcpy_with_bitshift(unsigned char *dest, unsigned char *src, size_t n, int bit)
{
  int i;

  memcpy(dest, src, n);

  for (i = 0; i < n; i++) {
    dest[i] >> bit;
  }

  for (i = 0; i < n; i++) {
    dest[i+1] |= (src[i] << (8 - bit));
  }
}

需要做的一些改进：

• 不要覆盖bit开头的第一位dest。
• 合并循环
• 有办法复制一些不能被 8 整除的位
• 修复 char 中 >8 位的问题