Получение битового потока из целых чисел и вывод его в файл

Question

Пишу реализацию алгоритма сжатия Хаффмана в учебных целях и застрял на собственно кодировании и записи закодированного файла.

Результатом кодирования Хаффмана является массив пар символ-код, где код — целое число произвольной битовой длины. Для достижения сжатия из кодов следует получать битовый поток, который записывается в закодированный файл.

В приведённом ответе makeAndSlice() создаёт битовый поток BitsStream из data[] и отсекает по 8 старших значимых битов в OutputByte по мере накопления их в потоке (while (BitsStreamCount >= ByteBits)). Чтобы получить лаконичный ответ, массивом data[] подменяется последовательность кодовых значений символов исходного файла.

Например, пускай data[] = {110, 1110, 11110, 1110, 110, 11110, 1110, 1}, где все числа записаны в двоичном представлении, тогда makeAndSlice() создаёт битовый поток 11011101111011101101111011101 и разделяет его на следующий список байтов: {11011101, 11101110, 11011110, 11101000}.

Answer 1

Ну, а в чём проблема? Всё делается легко, нужно лишь решить, как вы хотите кодировать «поток битов».

Например (для конвенции little endian):

int* data; // данные
size_t num_ints; // сколько их

size_t curr_int; // текущее слово, инициализируется нулём
size_t curr_bit; // текущий бит в слове, инициализируется нулём
#define BITS_IN_CHAR 8

int next_bit()
{
    if (curr_int >= num_ints)
        return -1; // конец потока

    int result = data[curr_int] & (1 << curr_bit);
    curr_bit++;
    if (curr_bit > sizeof(int) * BITS_IN_CHAR)
    {
        curr_bit = 0;
        curr_int++;
    }
    return result ? 1 : 0;
}

Answer 2

Делаю похожую вещь. К ответам выше добавлю только, что >> это сдвиг вправо, а не влево, а int и long будут иметь разное количество бит взависимости от платформы и лучше использовать uint8_t и подобные типы. Написал класс для таких задач, а для хранения информации о длине битовой последовательности добавил структуру BitRemedy с множеством различных методов: https://github.com/redmms/FineStream/tree/master/module

Answer 3

Решение в лоб видится таким:

int getBitsCount (unsigned long int NumberToCount)
{
  for (int BitsCount = 0; NumberToCount != 0; BitsCount++)
  {
    NumberToCount >>= 1;
  }
  return (BitsCount);
}

int makeAndSlice ()
{
  int *data;
  unsigned long int BitsStream = 0;
  int OutputByte = 0;
  int BitsStreamCount = 0;
  () // цикл прохождения массива целых
  {
    if ((BitsStreamCount = getBitsCount (BitsStream)) >= 8)
    {
      OutputByte = BitsStream >> (BitsStreamCount - 8);
      BitsStream -= ((unsigned long int) OutputByte) << (BitsStreamCount - 8);
      // делаем с нашим байтом, что хотим
    }

    BitsStream = BitsStream << getBitsCount (data [i]) + data [i]
  }
}

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

Answer 4

Подкину-ка я сюда на всякий случай известный битхак для определения числа установленных бит в 32 битном слове. Может ТСу пригодится:

uint32_t v; //v - входное слово.
uint32_t c; //c- число бит.

v = v - ((v >> 1) & 0x55555555);                    
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 

Answer 5

Работа над ошибками:

int getBitsCount (unsigned long int NumberToCount)
{
  for (int BitsCount = 0; NumberToCount != 0; BitsCount++)
  {
    NumberToCount >>= 1;
  }
  return (BitsCount);
}

int makeAndSlice ()
{
  const int ByteBits = 8 * sizeof (char) // мало ли…
  int *data;
  int BitsDataCount = 0;
  unsigned long int BitsStream = 0;
  int OutputByte = 0;
  int BitsStreamCount = 0;
  () // цикл прохождения массива целых
  {
    BitsDataCount = getBitsCount (data [i]);
    BitsStream = (BitsStream << BitsDataCount) + data [i];
    BitsStreamCount += BitsDataCount;
    while (BitsStreamCount >= ByteBits) // укорачиваем поток, пока он не меньше байта
    {
      OutputByte = BitsStream >> (BitsStreamCount - ByteBits);
      BitsStream -= ((unsigned long int) OutputByte) << (BitsStreamCount - ByteBits);
      BitsStreamCount -= ByteBits; // для битового потока нельзя применять getBitsCount
      // делаем с нашим байтом, что хотим
    }
  }
  OutputByte = BitsStream << (ByteBits - BitsStreamCount) // последний байт добиваем нулями справа
}

PS Держим в уме, что все наши коды должны начинаться с единицы, что, конечно, глупо, поэтому считаем при создании кодовой таблицы, храним и используем их битовые длины.