Бинарный формат для сериализации объектов

Я уже пару месяцев использую CatML для сохранения данных приложения в файлы, передачи объектов по сети и даже для дампа объектов в лог.
Формат хорош. В своих проектах я отказался от XML/Json/Yaml и не жалею.
Но с ростом объемов данных все более заметными становятся фундаментальные недостатки текстовых форматов:
- они избыточно-огромные,
- они долго записываются и еще дольше парсятся.

Поэтому, в общем, вот новый бинарный формат BinaryCatML.

• Он однозначно конвертируется в текстовый CatML и обратно. Для этого есть консольная утилитка. Вы можете открыть бинарный файл, просмотреть его содержимое, если надо исправить в любом текстовом редакторе и уаковать обратно в бинарный вид.
• Как и текстовый CatML, он имеет в себе всю метаинформацию и умеет кодировать произвольные графы объектов. 
• Он разумно компактен. Любое имя поля, имя структуры или объект присутствуют в файле ровно один раз. Это не компрессия, компрессия - убирает избыточность, а BinaryCatML просто не вносит ненужной избыточности.
• Он быстро записывается и быстро загружается. Все идентификаторы - стркутур, объектов - просто индексы в массивах. Никих look-up-ов в словари, никаких сравнений текстовых строк.
• Кодек по минимуму использует память и может работать даже на очень слабых устройствах.
• Он не зависит от разрядности или порядка байт архитектуры, в нем нет ни одного зашитого в формат ограничения.
• Его кодек занимает меньше 300 строк на Java и может быть портирован на любой язык буквально за день.

Формат

Формат BinaryCatML начинается с однобайтового magic 0x8D - улыбка чеширского кота.
За magic следует описние объекта.
Объекты, которые могут храниться в файле:

• знаковые и беззнаковые целые числа произвольной разрядности,
• числа с плафающей точкой произвольной точности,
• unicode-строки произвольной длины,
• бинарные данные - массивы байт произвольной длины,
• массивы объектов,
• структуры (при этом у каждой структуры есть именованный тип и набор именованных полей),
• перекрестные ссылки на структуры,
• специальные значения - null, undefined,
• глобальные имена объектов и записи импорта, чтобы связывать между собой данные, полученные из разных файлов.

Описание объекта начинается с тегового байта (и часто состоит из одного этого байта).
Теговый байт имеет следующий формат:
CTTT DDDD
D - data - четырехбитовое поле данных, его интерпретация зависит от поля TTT
C - бит продолжения.
T - трехбитное поле "тип объекта".

Поля D и C

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

Байты продолжения имеют формат:
CEEE EEEE
где
E - 7-битное поле, задающее следующие биты числа
С - бит продолжения.

Поле DDDD из тегового байта кодируют 4 младших бита значения.
Каждый байт продолжения несет значения следующих семи бит числа в порядке от младщих байтов к старшим.
Числа от 0 до 15 кодируются одним байтом. Числа 16..2047 - двумя байтми, 2047..262143 тремя и т.д.
Пример трехбайтной последовательности: 1TTTAAAA 1BBBBBBB 0CCCCCCC - двоичное число CC_CCCC_CBBB_BBBB_AAAA

Примеры:
0ТТТ 1100 - единственный теговый байт, хранящий число 1100 = 6 в своем поле D.
1TTT 1010   0010 0000 - два байта, описывающие число 010_0000_1010 = 0x20a = 522
1TTT 1111   1111 1111   0111 1111 - три байта, описывающие число 11_1111_1111_1111_1111 = 0x3FFFF = 262143

Поле T - "тип объекта":

• 000 положительнное число. Поле D кодирует целое число.
• 001 отрицательное число. Поле D кодирует его значение.
• 010 строка. Поле D - кодирует длину. За теговым байтом следуют unicode-символы в кодирвоании base 128 varint
• 011 бинарные данные. Поле D - кодирует длину. За теговым байтом следуют байты данных.
• 100 расширение типа. Поле D:
• 0 - null
• 1 - undefined
• 2 - import, за теговым байтом следует строка, см. "импорт и экспорт".
• 3 - export, за теговым байтом следует строка и определение объекта.
• 4 - число с плавающей точкой.
• 101 массив. Поле D задает длину. За теговым байтом следуют описания объектов - элементов массива.
• 110 мастер-ссылка на объект. Поле D кодирует идентификатор (id) объекта или идентификатор типа структуры.
• 111 weak-ссылка на объект. Кодируется аналогично типу 110.

Идентификаторы объектов.

При парсинге формата создаются и пополняются два массива - массив объектов (objects) и массив типов структур (structs).

• Если id > structs.size, это ссылка на уже загруженный объект, objects[id - structs.size - 1]
• Если id == structs.size, далее следует описание новой структуры (имя и список полей) и описание объекта с этой структурой.
• Если id < structs.size, из массива structs[id] берется описание структуры и далее сделует описания объекта с этой структурой.

Ссылка на новый объект добавляется в конец массива objects.
Ссылка на новую структуру добавляется в конец массива structs.

Кодирование строк:

• длина строки base 128 varint.
• символы в base 128 varint.

Описание новой структуры:

• строка с именем структуры
• имена полей. 

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

Примеры

Пример1:

0 //число 0

Кодируется

8D00

Расшифровка

8d // magic=8d
00 // 0_000_0000 - нет байта продолжения. T=0 положительное целое. D=0

Пример2:

[1, [65536, 3]]
:
  1
  :
    65536
    3

Кодируется

8d52015280802003

Расшифровка

 8D             // magic
 52             // массив из двух элементов
    01          // нулевой элемент массива - число int 1
    52          // первый элемент массива - массив из двух элементов
       80 80 20 // int 65536
       03       // int 3

Пример3:

TBD

Пример4:

Point
x 10
y 20

Кодируется

8D6005506f696e74037802790a8401

Расшифровка

 8D             // magic 
 60             // master reference. новая структура
                // (структуре приписан id по порядку = 0) 
    05 'Point'  // имя структуры - строка со счетчиком
    03 'x'      // имя поля, длина строки сдвинута на 1 бит влево,
                // младший бит установлен - это признак, что есть еще поля
    02 'y'      // имя поля. младший бит сброшен. это последнее поле.
                // конец описания структуры, начало описания экземпляра.
                // эземпляр получает id по порядку = 0
       0a       // int 10
       84 01    // int 20

Пример5:

 Project
 priority 4
 tasks:
    Task.t1
    title "Analysis"
 
    Task.t2
    title "Coding"
    depends:
       =t1

    Task.t3
    title "Test Cases"
    depends:
       =t1

    Task.t4
    title "Test Cycles"
    depends:
       =t2
       =t4

Кодируется

 8D600750726f6a656374117072696f726974790a7461736b73045461045461736b
 0b7469746c650e646570656e647328416e616c79736973416126436f64696e6751
 74612a546573742043617365735174612b54657374204379636c6573527577

Расшифровка

 8d                         // magic
 60                         // master reference. Новая структура.
                            // StrucId=0
    07 'Project'            // имя структуры. строка со счетчиком
    11 'priority'           // имя поля. строка со счетчиком shr 1.
                            // признак не последнего поля установлен. 
    0a 'tasks'              // имя поля. строка со счетчиком shr 1.
                            // признак не последнего поля = 0
                            // конец поределения структуры.
                            // начало определения экземпляра.
                            // Экpемпляр получает id=0
    04                      // поле proirity = int 4
    54                      // поле tasks, массив из 4 элементов
       61                   // нулевой элемент массива tasks.
                            // master reference на новую структуру,
                            // structId=1 
          04 'Task'         // имя новой структуры. строка со счетчиком
          0b 'title'        // имя поля. не последнее
          0e 'depends'      // имя поля. последнее
                            // конец определения структуры.
                            // начало определения экземпляра.
                            // экземпляр получает id=1
          28 'Analysis'     // поле title. строка.
          41                // depends. undefined
       61                   // первый элемент массива tasks.
                            // maser ref на структурy уже известного типа
                            // (structId=1)
                            // далее идет определение нового экемпляра этой структуры.
                            // он получает id=2
          26 'Coding'       // поле title. строка.
          51                // поле depends. массив из одного элемента.
              74            // элемент массива. weak reference
                            // на уже определенный экземпляр.
                            // id = 4-structs.count-1 = 1 
       61                   // остальные элементы определяются аналогично.
          2a 'Test Cases'
          51
              74
       61
          2b 'Test Cycles'
          52
             75
             77

Библиотека и использование

Исходный код на Java можно забрать тут:CatML_src.zip

Бинарный формат использует тот же самый DOM, что и текстовый CatML.
Это не самостоятельный проект, а пара классов в CatML пакете. Поэтому собственно запись и чтение - это BinaryWriter.encode и BinaryReader.read.

Dom dom = new JavaDom(); 
Object root = new Object[]{1024, new Object[]{65536,24}};
OutputStream file = new FileOutputStream("test.8D"); 

// запись объекта в бинарный формат
BinaryWriter.encode(dom, root, file);
file.close();

// чтение из файла
Object r = BinaryReader.read(dom, new FileInputStream("test.8D"), dom); 

 // и вывод на консоль в текстовый CatML
CatWriter.encode(dom, r, new OutputStreamWriter(System.out));