Micro Property — минималистичный сериализатор двоичных данных для embedded систем. Часть 2

    Некоторое время назад я опубликовал свою статью о разработке велосипедного велосипеда, в которой описал причины, побудившие меня этим заняться.

    Если вкратце, то мне была нужна миниатюрная библиотека для микроконтроллеров с сериализатором двоичных данных и последующей передачей этих сообщений по низко скоростным линиям связи, тогда как обычные форматы xml, json, bson, yaml, protobuf, Thrift, ASN.1 и др. мне по разным причинам не подходили.

    Как и ожидалось, решение оказалось более чем велосипедом, и тем не менее, сама публикация статьи на Хабре мне очень сильно помогла. Дело в том, что при первоначальном анализе возможных библиотек, я почему то упустил из вида сериализаторы MessagePack, CBOR и UBJSON.

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

    После этого я прикрутил к библиотеке CBOR свой интерфейс (чтобы не перелопачивать исходники), и … решил от этого формата отказаться в пользу MessagePack :-)




    CBOR vs. MessagePack


    На самом деле CBOR и MessagePack форматы используют один и тот же принцип сериализации данных. В их основе лежит практичный метод записи TLV, за тем лишь исключением, что в классическом виде TLV всегда содержит поле тега и поле длины данных. А вот поле с самими данными может отсутствовать (если размер данных ноль).

    А в этих сериализаторах разработчики пошли еще дальше, и сделали практически гениальные форматы, в которых наличие поля с размером данных зависит от типа данных, и не требуется для полей фиксированного размера, а в первом байте хранится одновременно и тип поля с размером данных и его непосредственное значение (конечно, если позволяет разрядность).

    В исходной статье я писал про то, что мне требуется максимальная упаковка бинарных данных и оба эти формата справляются с такой задачей на ура. Они между собой очень похожи, и отличаются только количеством бит, в котором хранится значения типа поля.

    В формате CBOR минимальные накладные расходы на хранение каждого поля составляет три бита, т.е. в первом байте каждого поля первые три бита отвечают за тип содержимого, и в зависимости от него интерпретируют наличие и размер других полей, а оставшиеся 5 бит могут содержать уже само значение поля.

    А вот в MessagePack пошли еще дальше! В этом формате минимальные накладные расходы на хранение значения составляют всего 1 (ОДИН!) бит информации. Соответственно, для хранения дополнительной информации может использоваться уже 7 бит, а для указания дополнительной информации о типе поля используются значения с установленным старшим битом.

    Понятно, что диапазон представления отрицательных значений при таком способе кодирования уменьшается за счет положительных чисел (в одном байте можно хранить только 32 отрицательных числа, а для остальных значений уже потребуется второй байт). Но это правильный дисбаланс и смещен он в нужную сторону, т.к. на практике положительные числа используются значительно чаще отрицательных.

    Другими словами, в одном байте в формате CBOR умещаются целочисленные значения от 0 до 23, а в формате MessagePack от 0 до 127!

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

    В итоге, изначальный формат сериализатора удалось сделать еще компактнее, в том числе и за счет некоторых соглашений (например, структуру кодируемых данных ограничить только плоским списком и отказом от использования невостребованных типов), а мой сон стал спокойнее, т.к. уже не болит голова насчет совместимости на уровне форматов пересылаемых сообщений между устройствами.
    Большое спасибо Хабра-юзерам Spym и edo1h, что ответили на предыдущую публикацию и тем самым помогли найти решение действительно серьезной проблемы такими малыми усилиями!

    Первоисточники:


    Спецификация CBOR. Есть хорошая статья с описанием на Хабре.

    Спецификация MessagePack очень легко читается в документации и не требует какого либо перевода или дополнительных пояснений.

    Комментарии 4

      +3

      В исходных требованиях вы, кажется, не писали о том, что формат должен быть самоописывающим (self-describing). Во встраиваемых системах это применяется сравнительно редко. Мы решали схожую задачу в протоколе, ссылку на статью о котором я давал в комментарии к вашей прошлой публикации; если интересно, можете взглянуть здесь: https://uavcan.org/specification/UAVCAN_Specification_v1.0-beta.pdf#page=15 (раздел "data structure description language"). Удаление метаданных из сериализованного сообщения не только уменьшает избыточность (что важно в вашем случае, как я вижу из требований), но и уменьшает вариативность представлений (есть только один способ закодировать данные, в то время как в TLV формате можно, к примеру, поменять местами поля структуры, не затронув семантику сообщения; этот вопрос рассматривается в спецификациях ASN.1 тоже), что удешевляет тестирование в отказоустойчивых приложениях.

        0
        Да, вы совершено правы насчет передачи структуры в самом сообщении, чего например нет в формате protobuf. Мне действительно было важно иметь информацию именно о самых полях, а не сообщении в целом, хотя в явном виде это действительно нигде не отмечено.
        +1
        А вот в MessagePack пошли еще дальше! В этом формате минимальные накладные расходы на хранение значения составляют всего 1 (ОДИН!) бит информации. Соответственно, для хранения дополнительной информации может использоваться уже 7 бит, а для указания дополнительной информации о типе поля используются значения с установленным старшим битом.

        ну это же явно небесплатно, раз отвели меньше бит на целочисленные переменные — значит что-то будет кодироваться большим числом бит.


        какая у вас в итоге вышла экономия на размере сообщений?

          0
          Так вроде в следующем абзаце это написано, что за счет количества отрицательных чисел, которых можно закодировать с помощью одного байта
          (в одном байте можно хранить только 32 отрицательных числа, а для остальных значений уже потребуется второй байт)

          В общем итоге, у меня как правило умещаются три значения в одном CAN сообщении, у которого размер полезных данных до 8 байт.

          До этого было 1-2 сообщения, т.к. использовалось не упакованное представление двоичных данных не зависимо от его значения. (т.е. 16-бит всегда 2 байт, 32-бит всегда 4 байта + всегда обязательный идентификатор поля или номер версии формата).
          Теперь выходит, что выигрыш составляет фактически 1.5-2 раза для отдельных сообщений, т.е. не нужно пересылать номер версии формата, а сами данных хранятся в минимально возможном размере.

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

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое