c - 将 fwrite() 与霍夫曼编码一起使用 - 位移位和位操作

Question

我正在进行霍夫曼编码，但我无法理解如何使用 fwrite() 将我们的编码写入输出。

假设我有这些编码:

Character A (65) gets an encoding of 101
Character B (66) gets an encoding of 1100111

但是，这些编码被保存为整数，所以

101 actually has a decimal value of 5 which is saved in memory as 00000101
1100111 actually has a decimal value of 103 which is saved in memory as 01100111

因此，当我们想使用 fwrite() 将它们写出时，假设我们使用缓冲区

int buff[4]

开始于

buff[0]    buff[1]    buff[2]    buff[3]
XXXXXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

(用X表示未初始化)为什么要用4个字节？因为我们需要考虑非常长的编码。如果我们有一个 27 位长的编码呢？我们需要完全填充其中的三个字节和第四个字节。

现在，假设我们需要对这一系列字符进行编码并将它们写入输出文件:

“ABB”

首先，我们对 A 进行编码，我们的 buff[] 应该变成:

buff[0]    buff[1]    buff[2]    buff[3]
101XXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

然后，我们需要对 B 进行编码，所以我们的 buff[] 应该变成:

buff[0]    buff[1]    buff[2]    buff[3]
10111001 - 11XXXXXX - XXXXXXXX - XXXXXXXX

现在，buff[] 的一个字节已满，因此我们需要对该字节进行编码并将 buff[] 的其他槽向下移动

fwrite(buff[0], 1, 1, fptOutput);
/* insert code to shift buff down */

所以现在我们的 buff 变成了:

buff[0]    buff[1]    buff[2]    buff[3]
11XXXXXX - XXXXXXXX - XXXXXXXX - XXXXXXXX

接下来，我们编码另一个“B”，我们的 buff[] 变成:

buff[0]    buff[1]    buff[2]    buff[3]
11110011 - 1XXXXXXX - XXXXXXXX - XXXXXXXX

然后，我们再次 fwrite() buff[0] 并再次进行移位。

但是，我们没有其他任何东西要编码，所以我们必须用 0 填充剩余的字节，所以我们的 buff 现在是:

buff[0]    buff[1]    buff[2]    buff[3]
10000000 - XXXXXXXX - XXXXXXXX - XXXXXXXX

然后 fwrite 最后一个字节，然后我们就完成了。

问题是我完全不知道如何系统地编程。我了解位操作。例如，在我们的第一个“A”编码中，我们需要将“00000101”向左移动 5 个位置，使其变为“101-----”，我理解这一步，但我不知道如何跟踪将我们的下一个编码转移到哪里。

如果我手动操作，我可以弄清楚如何根据需要移动每个变量，但我不知道如何提出一系列方程式，这些方程式适用于一个系列中的每个编码系列很长的文件。

Answer 1

您需要存储每个字符的编码数组以及每个字符编码中的位数数组，因为它们都是不同的。

然后您需要跟踪 buff 数组中还剩下多少位。

然后每次你想添加一个字符时，你都将该字符编码复制到另一个临时缓冲区中。然后你将该编码向上移动 buff 数组中已经留下的位数。然后你按位或将你的移位编码放到你的 buff 数组上。

然后您从 buff 数组中写入数据并将剩余的 buff 数据向下移动并调整 buff 数组中剩余的位数。

以下是一个将 16 位整数(短整数)数组按位向上或向下移动的函数。这有点矫枉过正，因为它会向上或向下移动位。您可以修改它以处理字节或长整数:

void 
shiftBits(unsigned short int *buffer, int bufferSize, int bitsToShiftUp)
{
int wordsToShift;
int bitsToShift;
int backBitsToShift;
int iTo;
int iFrom;

if (bitsToShiftUp > 0)
{
    //Shift up
    wordsToShift = bitsToShiftUp / 16;
    bitsToShift = bitsToShiftUp - (wordsToShift * 16);

    iTo = bufferSize - 1;
    iFrom = iTo - wordsToShift;

    if (bitsToShift == 0)
    {
        while (iFrom >= 0)
        {
            buffer[iTo] = buffer[iFrom];
            iTo--;
            iFrom--;
        }
        while (iTo >= 0)
        {
            buffer[iTo] = 0;
            iTo--;
        }
    }
    else
    {
        backBitsToShift = 16 - bitsToShift;
        while (iFrom >= 1)
        {
            buffer[iTo] = (buffer[iFrom] << bitsToShift) | (buffer[iFrom-1] >> backBitsToShift);
            iTo--;
            iFrom--;
        }
        if (iFrom >= 0)
        {
            buffer[iTo] = buffer[iFrom] << bitsToShift;
            iTo--;
        }
        while (iTo >= 0)
        {
            buffer[iTo] = 0;
            iTo--;
        }
    }
}
else if (bitsToShiftUp  < 0)
{
    //Shift down
    wordsToShift = (-bitsToShiftUp) / 16;
    bitsToShift = (-bitsToShiftUp) - (wordsToShift * 16);

    iTo = 0;
    iFrom = wordsToShift;

    if (bitsToShift == 0)
    {
        while (iFrom < bufferSize)
        {
            buffer[iTo] = buffer[iFrom];
            iTo++;
            iFrom++;
        }
        while (iTo < bufferSize)
        {
            buffer[iTo] = 0;
            iTo++;
        }
    }
    else
    {
        backBitsToShift = 16 - bitsToShift;
        while (iFrom < bufferSize - 1)
        {
            buffer[iTo] = (buffer[iFrom] >> bitsToShift) | (buffer[iFrom+1] << backBitsToShift);
            iTo++;
            iFrom++;
        }
        if (iFrom < bufferSize)
        {
            buffer[iTo] = buffer[iFrom] >> bitsToShift;
            iTo++;
        }
        while (iTo < bufferSize)
        {
            buffer[iTo] = 0;
            iTo++;
        }
    }
}
}