给定一个 uint8_t 数组，将任何位子序列提取为 uint32_t 的好方法是什么？

Question

我最近遇到了一个有趣的问题：

假设我有一个长度至少为 1 的字节数组（确切地说是 uint8_t）。现在我需要一个函数，该函数将从该数组中获取位的子序列，从位 X（基于零的索引，包括）开始，长度为 L，并将其作为 uint32_t 返回。如果 L 小于 32，则剩余的高位应为零。

虽然这并不是很难解决，但我目前关于如何做到这一点的想法对我来说似乎有点麻烦。我正在考虑一个给定字节的所有可能掩码的表（从位 0-7 开始，取 1-8 位），然后使用该表一次构造一个字节的数字。

有人能想出更好的解决方案吗？请注意，我不能为此使用 Boost 或 STL - 不，这不是作业，它是我在工作中遇到的问题，并且我们不会在该东西所在的代码中使用 Boost 或 STL。您可以假设： 0 < L <= 32 并且字节数组足够大以容纳子序列。

正确输入/输出的一个例子：

array: 00110011 1010 1010 11110011 01 101100
子序列：X = 12（从零开始的索引），L = 14
结果 uint32_t = 00000000 00000000 00 101011 11001101

Answer 1

只有子序列中的第一个和最后一个字节将涉及一些位切片以获取所需的位，而中间字节可以整体移入结果中。这是一些示例代码，绝对未经测试 - 它执行我所描述的操作，但某些位索引可能会偏离一位：

uint8_t bytes[];
int X, L;

uint32_t result;

int startByte  = X / 8,  /* starting byte number */
    startBit   = 7 - X % 8,  /* bit index within starting byte, from LSB */
    endByte    = (X + L) / 8, /* ending byte number */
    endBit     = 7 - (X + L) % 8; /* bit index within ending byte, from LSB */

/* Special case where start and end are within same byte:
   just get bits from startBit to endBit */
if (startByte == endByte) {
  uint8_t byte = bytes[startByte];
  result = (byte >> endBit) & ((1 << (startBit - endBit)) - 1);
}
/* All other cases: get ending bits of starting byte,
                    all other bytes in between,
                    starting bits of ending byte */
else {
  uint8_t byte = bytes[startByte];
  result = byte & ((1 << startBit) - 1);

  for (int i = startByte + 1; i < endByte; i++)
    result = (result << 8) | bytes[i];

  byte = bytes[endByte];
  result = (result << (8 - endBit)) | (byte >> endBit);
}

Answer 2

看一下 std::bitset 和 boost::dynamic_bitset。

Answer 3

我会想到类似加载 uint64_t 并进行强制转换，然后左右移动以丢失无趣的位。

uint32_t extract_bits(uint8_t* bytes, int start, int count)
{
    int shiftleft =  32+start;
    int shiftright = 64-count;
    uint64_t *ptr = (uint64_t*)(bytes);
    uint64_t hold = *ptr;
    hold <<= shiftleft;
    hold >>= shiftright;
    return (uint32_t)hold;
}

Answer 4

为了完整起见，我添加了受此处评论和答案启发的解决方案。感谢所有愿意思考这个问题的人。

static const uint8_t firstByteMasks[8] = { 0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };

uint32_t getBits( const uint8_t *buf, const uint32_t bitoff, const uint32_t len, const uint32_t bitcount )
{
    uint64_t result = 0;

    int32_t startByte = bitoff / 8; // starting byte number
    int32_t endByte = ((bitoff + bitcount) - 1) / 8; // ending byte number
    int32_t rightShift = 16 - ((bitoff + bitcount) % 8 );

    if ( endByte >= len ) return -1;

    if ( rightShift == 16 ) rightShift = 8; 

    result = buf[startByte] & firstByteMasks[bitoff % 8];
    result = result << 8;

    for ( int32_t i = startByte + 1; i <= endByte; i++ )
    {
        result |= buf[i];
        result = result << 8;
    }
    result = result >> rightShift;
    return (uint32_t)result;
}

几点说明：我测试了代码，它似乎工作得很好，但是，可能存在错误。如果我找到任何，我会在这里更新代码。此外，可能还有更好的解决方案！