Как преобразовать биты разной длины в массив байтов?

Вам нужна «система», которая принимает на вход последовательность битов и длин и выводит серию байтов.

Пользователь будет перебирать серию входных битов. Когда «система» имеет достаточно входных данных для генерации байтов, пользователь может их извлечь.

Я представляю себе API, который выглядит так

typedef struct {
    // holds a user-supplied buffer pointer
    char* buf_ptr;
    int buf_size;

    // pointer to usable data within the user-supplied buffer
    char* front;
    int bit_size;
} BitToByteMachine;

// initializes the BitToByteMachine
// The user supplied buffer must be at least large enough to hold the largest
// single input that the user will supply
void bit_to_byte_machine_init(BitToByteMachine*, char* buffer, int buf_size);

// Takes a uint32_t bitfield and a uint8_t num_bits
// Adds the bits into the current machine
// Returns the number of FULL BYTES available for extraction
// Undefined behavior if the buffer is too full to hold the data provided
int bit_to_byte_machine_insert(BitToByteMachine*, uint32_t bitfield, uint8_t num_bits);

// Returns the number of FULL BYTES available
// This can be called when there are still more pending calls to
// bit_to_byte_machine_insert(), for example to start transmitting data
// on a serial line before you've filled up the internal buffer
unsigned char bit_to_byte_machine_full_bytes(BitToByteMachine*);

// Returns the number of FULL OR PARTIAL BYTES available
// This should only be used after all data has been inserted and the only
// thing left to do is finish transmitting the data
unsigned char bit_to_byte_machine_full_or_partial_bytes(BitToByteMachine*);

// Extracts the next available byte
// If the next byte is a FULL BYTE, then will return the FULL BYTE
// If the next byte is a PARTIAL BYTE, then
// it will be zero-padded in the least significant bits
unsigned char bit_to_byte_machine_pop_byte(BitToByteMachine*);

Обычное взаимодействие с пользователем будет выглядеть примерно так

unsigned char my_buffer[4];
BitToByteMachine machine;
bit_to_byte_machine_init(&machine, my_buffer, 4);

while(there_are_codes_to_insert) {
    uint32_t next_code = get_next_code();
    uint8_t next_code_bit_size = get_next_code_bit_size();

    if (bit_to_byte_machine_insert(next_code, next_code_bit_size)) {
        while(bit_to_byte_machine_full_bytes(&machine)) {
            USART_transmit_byte(bit_to_byte_machine_pop_byte(&machine));
        }
    }
}

// no more codes to insert
// send the last bytes with padding
while (bit_to_byte_machine_full_or_partial_bytes(&machine)) {
    USART_transmit_byte(bit_to_byte_machine_pop_byte(&machine));
}

Как этот API работает для вас?

Решение требует:

// Returns false if nothing left.
int get_next_bits( uint8_t *len, uint32_t *bits );

// Sends the first `output_len` bytes pointed by `output`.
send_buffer( uint16_t output_len, const uint8_t *output );

// Allocated memory or array large enough for output.
// See below if this can't be guaranteed.
uint8_t *buf;

Решение:

uint16_t output_len = 0;
uint8_t *output = buf;     // Assumed to be large enough. But see below.
uint8_t available = 0;     // Number of unassigned bits in `*output`.
uint32_t bits;             // Bits to add to output.
uint8_t unassigned;        // Number of bits (left) in `bits`.

while ( get_next_byte( &unassigned, &bits ) ) {
   while ( unassigned > 0 ) {
      if ( available == 0 ) {
         // We need another byte of output.
         // `output` already points to this byte.
         ++output_len;
         *output = 0;
         available = 8;
      }

      if ( available <= unassigned ) {
         // We get here, for example, when we have
         // 5 bits to insert but only 3 bits available in current output byte.
         // So we shift the unassigned bits by 2 to place into position.
         // And we're left with 0 available bits and 2 unassigned bits.
         // We can't forget to "remove" from `bits` the 3 bits we assigned.
         uint8_t shift = unassigned - available;
         *output |= bits >> shift;
         unassigned = shift;
         bits &= ~( ( (uint32_t)0xFFFFFFFF ) << unassigned );
         available = 0;
         ++output;
      } else {
         // We get here, for example, when we have
         // 3 bits to insert and 5 bits available in current output byte.
         // So we shift the unassigned bits by 2 to place into position.
         // And we're left with 2 available bits and 0 unassigned bits.
         uint8_t shift = available - unassigned;
         *output |= bits << shift;
         unassigned = 0;
         available = shift;
      }
   }
}

send_buffer( output_len, output );

При желании случай available == unassigned можно обработать специально.

if ( available == unassigned ) {
   // We get here, for example, when we have
   // 5 bits to insert and 5 bits available in current output byte.
   // We're left with 0 available bits and 0 unassigned bits.
   *output |= bits;
   unassigned = 0;
   available = 0;
   ++output;
}

Если вы не можете гарантировать, что буфер будет достаточно большим, чтобы вместить все биты, замените

if ( available == 0 ) {
   // We need another byte of output.
   // `output` already points to this byte.
   *output = 0;
   available = 8;
   ++output_len;
}

с

if ( available == 0 ) {
   // We need another byte of output.
   // `output` already points to this byte.

   if ( output_len == buf_size ) {
      // Buffer is full, so send and empty it.
      output -= buf_size;
      output_len = 0;
      send_buffer( buf_size, output );
   }

   *output = 0;
   available = 8;
   ++output_len;
}

Вот функция, которая копирует значение битового поля указанной ширины до 32 бит в строку назначения байта с прямым порядком байтов. Назначение указывается как указатель на первый байт строки назначения и смещение в битах до позиции, в которой наиболее значимый бит битового поля должен быть сохранен в строке байтов назначения. Сопоставление смещений соответствующим битам в байтах выглядит следующим образом:

• Смещение 0 — это бит 7 в байте 0.
• Смещение 1 — это бит 6 в байте 0.
• …
• Смещение 7 — это бит 0 в байте 0.
• Смещение 8 — это бит 7 в байте 1.
• …

Функция содержит цикл while, который копирует до 8 бит за раз из исходного битового поля в место назначения. В каждой итерации количество скопированных битов равно минимальному количеству оставшихся нескопированных битов в значении исходного битового поля и количеству битов от текущего смещения назначения (в битах) до следующего кратного 8 битам.

Для удобства функция сохраняет оставшиеся биты исходного битового поля смещенными влево, так что наиболее значимый оставшийся бит находится в битовой позиции 31. Цикл while нормализует позицию назначения, добавляя позицию бита назначения, разделенную на 8, к месту назначения. указатель байта и установка позиции бита назначения в остаток.

#include <stdint.h>
#include <stddef.h>

/**
 * \brief Copy a bit-field into a string of bytes in big-endian order.
 *
 * \param dest Pointer to start of destination byte string.
 * \param dest_ofs_bit Offset in bits to location of most-significant bit
 *        of bit-field in destination byte string.
 * \param srcval Bit-field value as a number.
 * \param srcval_nbits Width of bit-field in bits.
 *
 * The destination byte string buffer is assumed to be at least
 * (\a dest_ofs_bit + \a srcval_nbits + 7) / 8 bytes long.
 */
void set_bitfield_in_bytes(uint8_t *dest, size_t dest_ofs_bit,
        uint32_t srcval, unsigned int srcval_nbits)
{
    /*
     * Move bit-field value to most significant end of srcval for convenience.
     */
    if (srcval_nbits < 32 && srcval_nbits > 0)
    {
        srcval <<= (32 - srcval_nbits);
    }
    while (srcval_nbits > 0)
    {
        unsigned int dest_shift;
        unsigned int nbits;
        uint8_t src_byte;
        uint8_t dest_mask;

        /* Adjust destination byte pointer and offset. */
        dest += dest_ofs_bit / 8;
        dest_ofs_bit %= 8;
        /* Extract up to 8 bits from srcval. */
        src_byte = srcval >> (24 + dest_ofs_bit);
        /* Assume all remaining bits in destination byte will be filled. */
        nbits = 8 - dest_ofs_bit;   /* Number of bits to fill. */
        dest_shift = 0;             /* No left shift. */
        dest_mask = 1u << nbits;    /* Bit-mask will be adjusted below. */
        if (nbits > srcval_nbits)
        {
            /* Not enough bits remaining in source bit-field, so adjust. */
            dest_shift = nbits - srcval_nbits;  /* Left shift. */
            nbits = srcval_nbits;               /* Number of bits to fill. */
        }
        dest_mask -= (1u << dest_shift);    /* Bit-mask of bits to fill. */
        /* Update bits in destination byte. */
        *dest = (*dest & ~dest_mask) | (src_byte & dest_mask);
        /* Shift remaining source bits to most-significant end. */
        srcval <<= nbits;
        /* Account for the number of bits copied in this iteration. */
        dest_ofs_bit += nbits;
        srcval_nbits -= nbits;
    }
}

Обратите внимание, что функция изменяет только указанные биты строки байтов назначения. Если требуется заполнение, вызывающая сторона может либо инициализировать последний байт назначения битами заполнения перед заполнением битовых полей, которые его перезаписывают, либо может вызвать функцию с дополнительным битовым полем, чтобы явно установить заполнение.

Следующий код тестирует функцию с 4 последовательными значениями битовых полей, включая битовое поле заполнения. Значения битовых полей, их ширина и смещения:

• значение 9, ширина 7, смещение 0
• значение 3, ширина 3, смещение 7
• значение 17, ширина 9, смещение 10
• значение 0 (заполнение), ширина 5, смещение 19

Общая длина составляет 24 бита или 3 байта.

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

void set_bitfield_in_bytes(uint8_t *dest, size_t dest_ofs_bit,
        uint32_t srcval, unsigned int srcval_nbits);

int main(void)
{
    uint8_t bytes[3] = { 0xff, 0xff, 0xff };

    set_bitfield_in_bytes(bytes, 0, 9, 7);
    set_bitfield_in_bytes(bytes, 7, 3, 3);
    set_bitfield_in_bytes(bytes, 7 + 3, 17, 9);
    set_bitfield_in_bytes(bytes, 7 + 3 + 9, 0, 5); /* padding */
    printf("%02x %02x %02x\n", bytes[0], bytes[1], bytes[2]);
}

Выход:

12 c2 20

Функцию по-прежнему можно использовать в сценарии, где буфер назначения имеет фиксированный размер, общая длина исходных битовых полей больше, чем размер буфера в битах (размер буфера в байтах, умноженный на 8), а буфер назначения равен периодически сбрасывается на какое-либо устройство вывода. Вызывающей стороне просто нужно быть осторожным, чтобы не переполнить буфер и не отправить частично заполненные байты на устройство вывода. Если буфер назначения является циклическим буфером, ему просто нужно 4 байта (32 бита) дополнительного пространства после конца циклического буфера, чтобы справиться с битовыми полями, которые записывают за конец буфера, а затем он может переместить избыточное пространство. байтов в начало буфера и отрегулируйте смещение места назначения.