c - 将 13 位数组合并为 unsigned char 数组

Question

我正在编写一种压缩数据 (LZSS) 的算法，它要求我有两个 13 位值，稍后我必须将它们合并在一起。

但是，在某些情况下，我不需要 13 位； 8个就够了。为此，我有一个这样的结构:

typedef struct pattern
{
    char is_compressed:1; //flag
    short index :13; //first value
    short length :13;  //second value
    unsigned char c;   //is 8 bits are enough, use this instead
} Pattern;

因此，我有一个由这些结构组成的数组，每个结构可以包含两个 13 位值或一个 8 位值。

我现在正在循环这个数组，我的目标是将所有这些位合并在一起。

我轻松计算出所使用的总位数以及存储所有值所需的 unsigned char 数组(8 位)数量:

int compressed = 0, plain = 0;
  //count is the amount of patterns i have and p is the array of patterns (the structures)
for (int i = 0; i < count; i++)
{
    if (p[i]->is_compressed)
        compressed++;
    else
        plain++;
}
  //this stores the number of bits used in the pattern (13 for length and 13 for the index or 8 for the plain uchar)
int tot_bits = compressed * 26 + plain * 8;
  //since we can only write a minimum of 8 bits, we calculate how many arrays are needed to store the bits
int nr_of_arrays = (tot_bits % 8 == 0) ? tot_bits / 8 : (tot_bits / 8) + 1;
  //we allocate the needed memory for the array of unsigned chars that will contain, concatenated, all the bits
unsigned char* uc = (unsigned char*) malloc(nr_of_arrays * sizeof(unsigned char));

为要填充的数组分配内存后，我只需循环遍历结构数组并识别我正在查看的结构是包含两个 13 位值还是仅包含 8 位值

for (int i = 0; i < count; i++)
{
    if (p->is_compressed)
    {
        //The structure contains the two 13 bits value
    } 
    else
    {
        //The structure only contains the 8 bits value
    }
}

在这里我陷入困境，似乎无法找到完成工作的正确方法。

你们中有人知道如何在那里实现该部分吗？

<小时/>

一个实际的例子是:

模式 1 包含 2 个 13 位值:

1111 1111 1111 1
0000 0000 0000 0

模式 2 包含 8 位值

1010 1010

总位数:34
所需数组数量:5(将浪费 6 位)

结果数组是:

[0] 1111 1111
[1] 1111 1000
[2] 0000 0000
[3] 0010 1010
[4] 1000 0000 (the remaining 6 bits are set to 0)

Answer 1

一种方法是逐个写入字节并在写入时跟踪部分字节。

您需要一个指向字符数组的指针，以及一个整数来跟踪写入最后一个字节的位数。每次写入位时，您都会检查可以写入最后一个字节的位数，并相应地写入这些位(例如:如果有 5 位空闲，则将下一个值移动 3 并将其添加到最后一个字节) 。每次完成一个字节时，您都会增加数组指针并重置位跟踪器。

实现此目的的一种简洁方法是编写如下函数:

void BitWriter_init( char *myArray );
void BitWriter_write( int theBitsToWrite, int howManyBits );

现在您只需弄清楚如何实现这些功能，或使用您选择的任何其他方法。