3. Битовые операции¶

Цель работы¶

Работа состоит из двух частей.

В первой части вам предлагается разобрать алгоритм кодирования целых чисел, называемый varint (variable integer). Такой способ кодирования позволяет использовать переменное количество байт для представления целых чисел и благодаря этому обеспечивает компактность данных. Вам нужно разработать приложение для записи и чтения чисел в сыром виде и в формате varint, сравнить эти два способа по эффективности и сделать выводы о применимости предложенного способа кодирования.

Во второй части необходимо самостоятельно реализовать алгоритм кодирования UTF-8. Этот алгоритм решает аналогичную задачу — позволяет кодировать целые числа переменным количеством байт, но используется для кодирования кодов символов и поддерживает обратную совместимость с кодировкой ASCII.

Base 128 Varint¶

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

В таких ситуациях применяется формат кодирования varint. Целые числа кодируются следующим образом:

Старший бит каждого байта служебный. Если в старшем бите 1 — это не последний байт, есть продолжение. Если в старшем бите 0 — это последний байт числа.
Младшие 7 бит используются для хранения части кодируемого числа. Мы будем рассматривать сериализацию с порядком байт Little Endian.

Пример¶

Пусть нам нужно закодировать число 1. В двоичном коде единица выглядит так:

0000 0001

Это единственный необходимый для кодирования байт, поэтому в старшем бите оставляем 0.

Закодируем число 300. Двоичный код:

0000 0001 0010 1100

Поскольку в каждом байте мы планируем хранить один служебный бит и 7 бит кодируемого числа, разобьем это представление на группы по 7 бит:

0000010 0101100

Изменим порядок на Little Endian:

0101100 0000010

Добавим служебный бит к каждой группе:

10101100 00000010

В open source проектах вы можете найти различные варианты реализации такого способа кодирования:

Git: varint.c
SQLite: lsm1/lsm_varint.c
Google Protobuf: CodedOutputStream::WriteVarint32ToArray

В работе мы будем использовать следующие варианты функций кодирования и декодирования:

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

size_t encode_varint(uint32_t value, uint8_t* buf)
{
    assert(buf != NULL);
    uint8_t* cur = buf;
    while (value >= 0x80) {
        const uint8_t byte = (value & 0x7f) | 0x80;
        *cur = byte;
        value >>= 7;
        ++cur;
    }
    *cur = value;
    ++cur;
    return cur - buf;
}

uint32_t decode_varint(const uint8_t** bufp)
{
    const uint8_t* cur = *bufp;
    uint8_t byte = *cur++;
    uint32_t value = byte & 0x7f;
    size_t shift = 7;
    while (byte >= 0x80) {
        byte = *cur++;
        value += (byte & 0x7f) << shift;
        shift += 7;
    }
    *bufp = cur;
    return value;
}

Задание 1¶

Разработайте приложение, которое генерирует 1000000 случайных чисел и записывает их в два бинарных файла. В файл uncompressed.dat запишите числа в несжатом формате, в файл compressed.dat — в формате varint. Сравните размеры файлов.

Реализуйте чтение чисел из двух файлов. Добавьте проверку: последовательности чисел из двух файлов должны совпадать.

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

#include <stdint.h>

/*
 * Диапазон             Вероятность
 * -------------------- -----------
 * [0; 128)             90%
 * [128; 16384)         5%
 * [16384; 2097152)     4%
 * [2097152; 268435455) 1%
 */
uint32_t generate_number()
{
    const int r = rand();
    const int p = r % 100;
    if (p < 90) {
        return r % 128;
    }
    if (p < 95) {
        return r % 16384;
    }
    if (p < 99) {
        return r % 2097152;
    }
    return r % 268435455;
}

UTF-8¶

Аналогичная задача компактного кодирования возникает при работе с текстами. Вы уже знакомы с однобайтными кодировками: ASCII, cp1251, koi8-r и др. Их проблема в том, что для кодирования символа они используют один байт, и документ, использующий одну из этих кодировок не может содержать символы более чем двух языков. Проблему решает использование кодировки UTF-8.

Подробнее об истории кодировок вы можете прочитать в статье Joel Spolsky — The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!).

Алгоритм кодирования:

Числа $[0; 2^8 - 1]$ будем представлять в виде 0xxxxxxx, «как есть»:
```
00000000 — 0
00000001 — 1
...
00000101 — 5
...
01111111 — 127
```
Для бо́льших значений в старшем байте будем хранить столько единиц, сколько байт требуется для представления закодированного числа. 110xxxxx — два, 1110xxxx — три, и т. д. Все последующие байты имеют вид 10xxxxxx.

Биты, обозначенные символами x, заполняются битами кодируемого числа.

Для выбора длины кода можно руководствоваться таблицей:

Количество значащих бит кодируемого числа	Количество байт в коде	Шаблон
7	1	0xxxxxxx
11	2	110xxxxx 10xxxxxx
16	3	1110xxxx 10xxxxxx 10xxxxxx
21	4	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Пример кодирования числа¶

Пусть требуется закодировать число 0xa8cc. Число занимает 2 байта, 16 бит. Следовательно, для закодированного числа потребуется 3 байта.

Используем шаблон: 1110xxxx 10xxxxxx 10xxxxxx

Двоичное представление числа 0xa8cc: 1010100011001100

Теперь значащие биты числа нужно подставить в шаблон:

Шаблон:    1110xxxx 10xxxxxx 10xxxxxx
Число:         1010   100011   001100
Результат: 11101010 10100011 10001100

Шестнадцатеричное представление закодированного числа: 0xa8cc

Пример декодирования числа¶

Выполним обратную операцию. Пусть на входе дан байтовый поток: 11101010 10100011 10001100.

Считываем первый байт: 11101010.

Байт начинается с трех единиц. Следовательно, всего в закодированном числе три байта. Один уже считан, нужно считать еще два: 10100011 10001100.
Шаблон для трехбайтового кода известен, осталось из закодированного числа выделить значащие биты:
```
Шаблон:        1110xxxx 10xxxxxx 10xxxxxx
Считанный код: 11101010 10100011 10001100
Значащие биты:     1010   100011   001100
```

Декодированное число: 0b1010100011001100 = 0xa8cc.

Потери данных¶

Во входном потоке возможны потери данных. Например, дана такая последовательность: 10001100 11101010 10100011 10001100. Первый байт имеет вид 10xxxxxx. Такой байт не может быть первым, т.к. в соответствии с алгоритмом кодирования было установлено, что такой вид принимают байты, следующие за первым. Следовательно, часть данных в начале была потеряна. В этом случае можно пропускать байты до тех пор, пока не будет считан байт, обозначающий начало кода.

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

Задание 2¶

Разработать приложение для кодирования и декодирования чисел по описанному выше алгоритму.

Пример кодирования:

$ ./coder encode points.txt units.bin

Здесь:

encode — команда кодирования
points.txt — входной текстовый файл, содержащий числа, записанные в шестнадцатеричной системе счисления.

Пример содержимого файла:
```
7
1e7
79e7
1e79e7
```
units.bin — выходной бинарный файл.

Пример результата (для просмотра используется утилита hexdump):
```
$ hexdump -C units.bin

00000000  07 c7 a7 e7 a7 a7 f7 a7  a7 a7
```

Пример декодирования:

$ ./coder decode units.bin points.txt

Запуск с некорректным количеством аргументов или некорректной командой:

$ ./coder foobar
Usage:
coder encode <in-file-name> <out-file-name>
coder decode <in-file-name> <out-file-name>

Кодируемые числа считывать в переменную типа uint32_t. Для представления в памяти закодированного числа можно использовать структуру:

enum {
    MaxCodeLength = 4
};

typedef struct {
    uint8_t code[MaxCodeLength];
    size_t length;
} CodeUnits;

Здесь:

code — закодированные байты, в порядке от старшего к младшему.
length — количество байт в закодированном представлении.

Предлагается следующая структура проекта:

.
|-- Makefile
`-- src
    |-- coder.c
    |-- coder.h
    |-- command.c
    |-- command.h
    `-- main.c`

Файлы command.h и command.c:

int encode_file(const char *in_file_name, const char *out_file_name)

Кодирование текстового файла в бинарный, реализация команды encode.

Параметры:	*char in_file_name** (const) – путь ко входному текстовому файлу *char out_file_name** (const) – путь к выходному бинарному файлу
Результат:	0 в случае успеха, -1 в случае ошибки

int decode_file(const char *in_file_name, const char *out_file_name)

Декодирование бинарного файла, реализация команды decode.

Параметры:	*char in_file_name** (const) – путь ко входному бинарному файлу *char out_file_name** (const) – путь к выходному текстовому файлу
Результат:	0 в случае успеха, -1 в случае ошибки

Файлы coder.h и coder.c:

int encode(uint32_t code_point, CodeUnits *code_units)

Параметры:	code_point – число, которое необходимо закодировать code_unit – выходной параметр, результат кодирования
Результат:	0, если кодирование успешно, -1 иначе

uint32_t decode(const CodeUnit *code_unit)

Допущение: code_unit - корректный код, полученный с помощью функции read_next_code_unit.

Return code_point:
Параметры:	code_unit – закодированное представление числа
	результат декодирования

int read_next_code_unit(FILE *in, CodeUnits *code_units)

Считывает последовательность code_units из потока in. Implementation note: если считываемый code_unit битый, то функция пропускает байты до тех пор, пока не найдет корректный лидирующий байт.

Результат:	0 в случае успеха, -1 в случае ошибки или EOF

int write_code_unit(FILE *out, const CodeUnit *code_unit)

Примечание: обычно в подобных задачах используется другая декомпозиция. Предлагаемый вариант намеренно упрощен в учебных целях.

Аргументы командной строки¶

Обработка аргументов командной строки осуществляется через параметры функции main. Прмер:

#include <stdio.h>

int main(int argc, char *argv[])
{
    // argc - количество аргументов
    // argv - массив указателей на строки.
    // Нулевой элемент - командна запуска приложения

    int i;
    for (i = 0; i < argc; ++i) {
        printf("argv[%d] = %s\n", i, argv[i]);
    }

    return 0;
}

Запуск приложения:

$ ./prog first second third
argv[0] = ./prog
argv[1] = first
argv[2] = second
argv[3] = third

Переносимое считывание значений¶

Для считывания переменных типа unsigned int используется спецификатор %x:

unsigned int var;
fscanf(in, "%x", &var);

В текущей работе мы будем использовать типы фиксированной разрядности: uint32_t, uint8_t. Каждый такой тип является синонимом одного из встроенных типов языка С. Не гарантируется, что uint32_t будет синонимом для unsigned int. Следовательно, использование спецификатора %x может быть непереносимым и вести себя некорректно на других платформах.

Для обеспечения переносимости в заголовочном файле inttypes.h определен ряд макросов вида SCNxN, где N — разрядность переменной. Так, для считывания переменной типа uint32_t следует использовать макрос SCNx32, а для ее вывода PRIx32.

Пример:

#include <inttypes.h>

// В функции считывания данных
uint32_t code_point;

fscanf(in, "%" SCNx32, &code_point);

printf("%" PRIx32, code_point);

После обработки препроцессором в строки могут принять вид:

uint32_t code_point;

fscanf(in, "%" "x", &code_point);

printf("%" "x", code_point);

Подробнее: Fixed width integer types

Контрольные вопросы¶

Дан массив чисел, из которого нужно считать i-тый элемент. Как выполнить эту операцию, если использована кодировка с фиксированным количеством байт? С переменным?
Дана неубывающая последовательность больших чисел (числа больше 2097152). Предложите компактный способ кодирования такой последовательности.

Источники¶

Bitwise operations in C — основы
Mask — не всегда удобно устанавливать биты по одному.
man 3 fopen — см. открытие файлов в бинарном режиме
man 3 fread — функции чтения/записи при работе с бинарными файлами