Учитывая массив uint8_t, что является хорошим способом извлечь любую последовательность битов как uint32_t?

Question

В последнее время я столкнулся с интересной проблемой:

Допустим, у меня есть массив байтов (точнее, uint8_t) длиной не менее одного. Теперь мне нужна функция, которая получит подпоследовательность битов из этого массива, начиная с бита X (индекс на основе нуля включительно) и имеющий длину L, и вернет его как uint32_t. Если L меньше 32, оставшиеся старшие биты должны быть равны нулю.

Хотя это не очень трудно решить, мои нынешние мысли о том, как это сделать, кажутся мне несколько обременительными. Я имею в виду таблицу всех возможных масок для данного байта (начните с бита 0-7, берите 1-8 бит), а затем создайте номер один байт за раз, используя эту таблицу.

Может кто-нибудь придумать более приятное решение? Обратите внимание, что я не могу использовать Boost или STL для этого - и нет, это не домашняя работа, это проблема, с которой я сталкиваюсь на работе, и мы не используем Boost или STL в коде, где эта штука идет. Вы можете предположить, что: 0

Один пример правильного ввода / вывода:

массив: 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

Ради полноты, я добавляю свое решение, вдохновленное комментариями и ответами здесь. Спасибо всем, кто удосужился подумать о проблеме.

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;
}

Несколько замечаний: я протестировал код, и он, кажется, работает нормально, однако могут быть ошибки. Если я найду, я обновлю код здесь. Также, возможно, есть лучшие решения!

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

Посмотрите на std :: bitset и boost :: dynamic_bitset.