c++ - 从缓冲区中删除第 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) 或内联汇编。

Answer 1

这实际上是 2 个子问题:从每个字节中删除位并打包结果。这是下面代码的流程。我不会为此使用宏。发生的事情太多了。如果您担心该级别的性能，只需内联函数即可。

#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。其他一些测试用例也适用。