Length-value-кодирование — это простейший способ сериализации бинарных данных.
Пусть у нас есть набор каких-то строк (точнее, последовательностей байтов), и требуется сериализовать эти строки (записать непрерывным куском на диск или в память). Пусть в этих "строках" могут встречаться управляющие символы (например, символы с кодами 0, 10, 13). Тогда наивная запись таких строк через разделитель (например, \n) невозможна, так как этот разделитель может сам встречаться внутри строки. В таких случаях обычно используют length-value формат: сначала записывают размер строки в байтах, а потом — саму строку.
Вам нужно написать функцию CountValues
, которая получает на вход блок байтов (через указатель на начало и размер).
Предполагается, что в этих байтах последовательно записаны какие-то строки с помощью length-value-кодирования.
Функция должна вернуть количество записанных строк.
Если блок байтов неожиданно заканчивается, а очередное значение из него не прочитано до конца, то требуется сгенерировать исключение типа RangeError
.
Вот заготовка:
#include <cstddef> // for size_t
class RangeError {
};
size_t CountValues(const char * data, size_t size);
Считайте, что длины строк записываются типом size_t
.
Пример: пусть у нас есть 2 строки со значениями "hello" и "world!".
Закодируем их с помощью length-value-кодирования.
Пусть наша платформа 64-битная, и тип size_t
имеет размер 8 байт.
Пусть мы имеем дело с архитектурой little-endian.
Тогда на вход функции CountValues
поступит блок памяти из (8 + 5) + (8 + 6) = 27 байтов.
Вот его hex dump (вывод утилиты hd):
00000000 05 00 00 00 00 00 00 00 68 65 6c 6c 6f 06 00 00 |........hello...|
00000010 00 00 00 00 00 77 6f 72 6c 64 21 |.....world!|
0000001b
Функция в этом случае должна вернуть 2.
Итак, нам дан кусок памяти в виде указателя на начальный байт и размера.
По старой традиции байты представляются типом char
.
К текстовым строкам эти байты могут не иметь никакого отношения.
Мы можем ходить указателем по адресам в пределах отрезка от data
до data + size
и разыменовывать эти указатели (кроме последнего data + size
).
Это очень похоже на итераторы стандартных контейнеров (точнее, наоборот: итераторы были сделаны похожими на указатели).
Предполагая, что данные записаны в память корректно, наша программа в цикле должна идти по адресам в памяти, считывать размер очередного блока, пропускать это число байтов и подсчитывать количество выполненных итераций.
size_t result = 0;
size_t i = 0;
while (i < size) {
size_t len = *reinterpret_cast<const size_t*>(data + i);
i += sizeof(size_t);
i += len;
++result;
}
Разберем подробнее конструкцию с reinterpret_cast
.
Здесь мы берем ячейку памяти с адресом data + i
и смотрим на него и последующие байты как на байты переменной size_t
.
Всего таких байтов sizeof(size_t)
(как правило, 8).
Мы используем для этого приведение типа указателя к const size_t*
.
Константность здесь необходима, так как исходный указатель нам передан как const char*
.
В этом фрагменте кода не хватает проверок на корректность данных.
Байтов с размером блока может оказаться меньше 8, и байтов с данными может оказаться меньше len
.
В таких случаях надо сгенерировать исключение, не пытаясь прочитать байты, расположенные за дозволенными пределами.
Вот итоговое решение:
#include <cstddef> // for size_t
class RangeError {
};
size_t CountValues(const char * data, size_t size) {
size_t result = 0;
size_t i = 0;
while (i < size) {
if (i + sizeof(size_t) > size) {
throw RangeError();
}
size_t len = *reinterpret_cast<const size_t*>(data + i);
i += sizeof(size_t);
if (i + len > size) {
throw RangeError();
}
i += len;
++result;
}
return result;
}