从缓冲区中移除第n位，并将其余位进行移位

Question

给定长度为x的uint8_t缓冲区，我正在尝试编写一个函数或宏，以便可以删除第n位（或从n到n+i），然后左移剩余的位。

例子1：对于输入0b76543210 0b76543210 ...，输出应为0b76543217 0b654321 ... 例子2：如果输入是：

uint8_t input[8] = {
    0b00110011,
    0b00110011,
    ...
};

去掉第一位后的输出应该是：

uint8_t output[8] = {
    0b00110010,
    0b01100100,
    ...
};

我尝试过以下方法来删除第一个位，但对于第二组位没有起作用。

/* A macro to extract (a-b) range of bits without shifting */
#define BIT_RANGE(N,x,y) ((N) & ((0xff >> (7 - (y) + (x))) << ((x))))
void removeBit0(uint8_t *n) {
    for (int i=0; i < 7; i++) {
        n[i] = (BIT_RANGE(n[i], i + 1, 7)) << (i + 1) |
               (BIT_RANGE(n[i + 1], 1, i + 1)) << (7 - i); /* This does not extract the next element bits */
    }
    n[7] = 0;
}

更新 #1 在我的情况下，输入将是 uint64_t 数字，然后我将使用 memmov 将其向左移动一位。

更新 #2 解决方案可以使用 C/C++、汇编语言（x86-64）或内联汇编语言。

- Mohamed El-Sayed

---

在x86上，有一个指令可以实现这个功能（等等，什么？）：pdep/pext，由BMI2指令集扩展添加。 - EOF

谢谢，这非常有趣，我会试一试。 - Mohamed El-Sayed

我对这个问题有点困惑。图表表明，您不仅想删除一个比特，而且想从由x个八位字节表示的比特流中删除比特s+8i，其中s*在[0,7]之间，即这是一种特定形式的比特流压缩。一种天真的方法是简单地循环输入比特，保持源和目标的比特数的分别运行总数，指示何时抑制比特复制以及何时检索/存储下一个八位字节。这对于您的目的来说是否太慢了？ - njuffa

如果这个应该是“跨平台”的，为什么你使用了“汇编”和“内联汇编”标签？另外，你还没有回答njuffa的问题，即你的图表如何与你的问题相矛盾。 - Ross Ridge

你的问题的第一行说你想从缓冲区中删除一个位（或一系列连续的位）。图表显示删除了多个非连续位。你必须决定你的问题是要求跨平台解决方案还是特定于平台的解决方案。在前一种情况下，你发布特定于平台的答案是不合适的，在后一种情况下，你需要命名平台。 - Ross Ridge

Answer 1

这实际上是两个子问题：从每个字节中删除位并打包结果。以下是代码的流程。我不会为此使用宏。操作过于复杂。如果您担心该级别的性能，请内联函数。

#include <stdio.h>
#include <stdint.h>

// Remove bits n to n+k-1 from x.
unsigned scrunch_1(unsigned x, int n, int k) {
  unsigned hi_bits = ~0u << n;
  return (x & ~hi_bits) | ((x >> k) & hi_bits);
}

// Remove bits n to n+k-1 from each byte in the buffer,
// then pack left. Return number of packed bytes.
size_t scrunch(uint8_t *buf, size_t size, int n, int k) {
  size_t i_src = 0, i_dst = 0;
  unsigned src_bits = 0; // Scrunched source bit buffer.
  int n_src_bits = 0;    // Initially it's empty.
  for (;;) {
    // Get scrunched bits until the buffer has at least 8.
    while (n_src_bits < 8) {
      if (i_src >= size) { // Done when source bytes exhausted.
        // If there are left-over bits, add one more byte to output.
        if (n_src_bits > 0) buf[i_dst++] = src_bits << (8 - n_src_bits);
        return i_dst;
      }
      // Pack 'em in.
      src_bits = (src_bits << (8 - k)) | scrunch_1(buf[i_src++], n, k);
      n_src_bits += 8 - k;
    }
    // Write the highest 8 bits of the buffer to the destination byte.
    n_src_bits -= 8;
    buf[i_dst++] = src_bits >> n_src_bits;
  }
}

int main(void) {
  uint8_t x[] = { 0xaa, 0xaa, 0xaa, 0xaa };
  size_t n = scrunch(x, 4, 2, 3);
  for (size_t i = 0; i < n; i++) {
    printf("%x ", x[i]);
  }
  printf("\n");
  return 0;
}

这里写的是b5 ad 60，按照我的计算是正确的。还有几个其他的测试用例也可以正常工作。

糟糕，我第一次编码时移位方向错误，但在这里包含它以防对某些人有用。

#include <stdio.h>
#include <stdint.h>

// Remove bits n to n+k-1 from x.
unsigned scrunch_1(unsigned x, int n, int k) {
  unsigned hi_bits = 0xffu << n;
  return (x & ~hi_bits) | ((x >> k) & hi_bits);
}

// Remove bits n to n+k-1 from each byte in the buffer,
// then pack right. Return number of packed bytes.
size_t scrunch(uint8_t *buf, size_t size, int n, int k) {
  size_t i_src = 0, i_dst = 0;
  unsigned src_bits = 0; // Scrunched source bit buffer.
  int n_src_bits = 0;    // Initially it's empty.
  for (;;) {
    // Get scrunched bits until the buffer has at least 8.
    while (n_src_bits < 8) {
      if (i_src >= size) { // Done when source bytes exhausted.
        // If there are left-over bits, add one more byte to output.
        if (n_src_bits > 0) buf[i_dst++] = src_bits;
        return i_dst;
      }
      // Pack 'em in.
      src_bits |= scrunch_1(buf[i_src++], n, k) << n_src_bits;
      n_src_bits += 8 - k;
    }
    // Write the lower 8 bits of the buffer to the destination byte.
    buf[i_dst++] = src_bits;
    src_bits >>= 8;
    n_src_bits -= 8;
  }
}

int main(void) {
  uint8_t x[] = { 0xaa, 0xaa, 0xaa, 0xaa };
  size_t n = scrunch(x, 4, 2, 3);
  for (size_t i = 0; i < n; i++) {
    printf("%x ", x[i]);
  }
  printf("\n");
  return 0;
}

这里写成了d6 5a b。还有一些其他的测试用例也可以工作。

- Gene

---

谢谢，这真的起作用了。我想指出字节序问题，但你已经提到了，所以感谢你。 - Mohamed El-Sayed

Answer 2

类似这样的代码应该可以实现：

template<typename S> void removeBit(S* buffer, size_t length, size_t index)
{
  const size_t BITS_PER_UNIT = sizeof(S)*8;

  // first we find which data unit contains the desired bit
  const size_t unit = index / BITS_PER_UNIT;
  // and which index has the bit inside the specified unit, starting counting from most significant bit
  const size_t relativeIndex = (BITS_PER_UNIT - 1) - index % BITS_PER_UNIT;

  // then we unset that bit
  buffer[unit] &= ~(1 << relativeIndex);

  // now we have to shift what's on the right by 1 position
  // we create a mask such that if 0b00100000 is the bit removed we use 0b00011111 as mask to shift the rest
  const S partialShiftMask = (1 << relativeIndex) - 1;

  // now we keep all bits left to the removed one and we shift left all the others
  buffer[unit] = (buffer[unit] & ~partialShiftMask) | ((buffer[unit] & partialShiftMask) << 1);

  for (int i = unit+1; i < length; ++i)
  {
    //we set rightmost bit of previous unit according to last bit of current unit
    buffer[i-1] |= buffer[i] >> (BITS_PER_UNIT-1);
    // then we shift current unit by one
    buffer[i] <<= 1;
  }
}

我只是在一些基本案例上进行了测试，所以可能有些不完全正确，但这应该能帮助你朝着正确的方向前进。

- Jack

---

非常感谢，我喜欢你花时间提供模板函数的方式，但不幸的是这并没有产生期望的输出。我正在尝试修改代码，使其能够与uint8_t缓冲区一起工作。 - Mohamed El-Sayed