如何将不同长度的位转换为字节数组？

Question

我目前正在开展一个项目，我必须为嵌入式系统实现 Elias Gamma 编码（使用 C 进行 STM32F405 编程）。 主要优先事项是代码的效率和速度，因此我为 Elias Gamma 编码实现了一个查找表，其中包含每个“位数组”的位值和位数（我使用 uint32_t 表示符号，使用 uint8_t 表示长度）。 但是我在将这些位转换为字节数组时遇到问题。以下是我正在尝试做的事情的示例。

对于三个符号 -> 0b0001001（位长 7）、0b011（位长 3）、b000010001（位长 9），我必须得到 0b0001001011000010001，因此 0x12 0xC2 0x20 作为字节数组，通过 USART 等通信通道传输数据。

令我困惑的是，位符号的长度不同，并且必须将“追加”过程应用于使用字节作为最小数据结构的平台中的位。

有没有简单的方法可以做到这一点？

编辑： 为了清楚起见，我尝试将 4096“位数组”附加到 X 个字节。 X 数量取决于附加的位数（处理时未知）。

Answer 1

您需要一个“系统”，它接受一系列位和长度作为输入并输出一系列字节。

用户将迭代一系列输入位。当“系统”有足够的输入来生成字节时，用户就可以提取它们。

我正在想象一个像这样的 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 对您有何帮助？

Answer 2

int get_next_bits( uint8_t *len, uint32_t *bits );

uint16_t output_len = 0;
uint8_t *output = ...;    // Assumed to be large enough, plus one.
uint8_t avail = 0;        // Number of unassigned bits in `*output`.
uint32_t bits;
uint8_t bits_len;         // Number of bits in `bits`.

while ( get_next_byte( &bits_len, &bits ) ) {
   while ( bits_len > 0 ) {
      if ( avail == 0 ) {
         *output = 0;
         avail = 8;
         ++output_len;
      }

      uint8_t shift = avail - bits_len;
      if ( shift >= 0 ) {
         *output |= bits >> shift;
         bits_len = shift;
         ++output;
         avail = 0;
      } else {
         shift = -shift;
         *output |= bits << shift;
         avail -= shift;
         bits_len = 0;
      }
   }
}