Списки свойств предлагают структурированный и эффективный способ представления и сохранения иерархий объектов на диске. Они широко используются в операционных системах Apple для хранения небольших объемов данных, наиболее известным примером которых является Info.plist, файл, содержащий информацию о конфигурации в кодировке "ключ-значение" для связанных исполняемых файлов. Какао позволяет использовать различные взаимозаменяемые представления для списков, включая XML, JSON и двоичные файлы. Первые два имеют то преимущество, что они удобочитаемы, в то время как последний предлагает наиболее эффективное представление на диске, а также быструю сериализацию / десериализацию. В этом сообщении блога мы рассмотрим внутреннюю структуру двоичных списков.

Определение бинарных списков

Двоичные списки (bplists) можно легко идентифицировать с помощью команды file в macOS.

$ file config.plist
config.plist: Apple binary property list

Преобразование между разными форматами списков может быть выполнено с помощью командыplutil, например чтобы преобразовать приведенный выше список bplist в XML:

$ plutil -convert xml1 config.plist
$ file config.plist
config.plist: XML 1.0 document text, ASCII text

Двоичная структура списка

Структуру bplist можно найти в комментариях к предоставленному Apple источнику с открытым исходным кодом CFBinaryPList.c и в объявлениях ForFoundationOnly.h. Он состоит из 4 отдельных разделов: заголовка, таблицы объектов, таблицы смещения и концевой части.

Заголовок

Файл начинается с 8-байтового заголовка, содержащего волшебный «bplist» и версию. Для bplist00 версия - 00, но известно, что существуют и другие версии, например bplist15, bplist16. Мы будем иметь дело только с bplist00, который на сегодняшний день является наиболее распространенной версией в операционных системах Apple.

Таблица объектов

2-й раздел соответствует таблице объектов. Таблица объектов содержит все объекты списка. Все типы объектов идентифицируются одним байтом, также называемым маркером (см. Рис. 1). Этот байт кодирует важные метаданные об объекте, например информацию о его типе и размере.

Байта маркера иногда бывает достаточно, чтобы полностью идентифицировать объект. Например, нулевое значение имеет маркер, равный нулю, логическое значение имеет маркер 0x08, если оно ложно, или 0x09, если оно истинно. Все остальные объекты можно однозначно идентифицировать по их 4 старшим битам (с этого момента я буду использовать термины крайний левый и крайний правый вместо MSB и LSB). Например, 4 крайних левых бита для целого числа - 0001 (0x1), а для строки - 0110 (0x5).

Остальные крайние правые 4 бита обозначают информацию о размере, то есть сколько байтов будет занимать фактическое значение этого типа после маркера. В некоторых случаях, если объект достаточно мал, размер кодируется сразу в 4 крайних правых бита. Например, строка ASCII «Hello» будет закодирована как 0x55, а затем последуют фактические значения символов. В других случаях маркер заполнения (0x0F) объединяется оператором ИЛИ с маркером объекта, что означает, что следующие байты кодируют информацию о размере до байтов фактического значения. Более конкретно, если крайние правые 4 бита маркера равны 1111 (0xF), следующий байт будет иметь следующую структуру:

  • его 4 крайних левых бита равны 0001 (0x1)
  • его 4 крайних правых бита говорят нам, сколько байтов нам нужно для кодирования размера объекта. если 4 крайних правых бита содержат значение x, для размера потребуется pow (2, x) байты

Затем следуют байты pow (2, x), которые следует читать с прямым порядком байтов, чтобы получить фактический размер объекта. После этого следуют фактические значения объекта. Например, строка «Это длинная строка» содержит 21 символ ASCII. Маркер будет 0x5F, за которым следует байт 0x10 (поскольку pow (2, 0) = 1 и 1 байт достаточно для кодирования значения 21), тогда 0x15 (десятичное число 21 в шестнадцатеричном формате), затем один за другим 21 символ.

За маркерами, соответствующими таким объектам, как int, действительные числа, строки, сразу следует многобайтовая последовательность, которая представляет их фактические значения (например, отдельные строковые символы, как описано выше). Однако это не всегда так. В случае контейнеров объектов, таких как массивы и словари, за байтом маркера следуют ссылки на объекты , которые являются просто смещениями относительно таблицы смещений (см. Следующий раздел). Такие смещения имеют длину object_ref_size в байтах, как определено в конце bplist, и отсчитываются от начала таблицы смещений. Следовательно, элемент контейнера - это просто ссылка размером object_ref_size, которая указывает на позицию в таблице смещений, которая сама по себе является offset_table_offset_size байтов и указывает на таблицу объектов и, в частности, на маркер, соответствующий отдельному объекту. Примеры в следующем разделе прояснят любую путаницу.

Этот метод отображает фактическую многоуровневую иерархию и позволяет всем объектам иметь фиксированные размеры. Таким образом, мы всегда знаем, что за маркером со значением 0xA5 следует 5 * object_ref_size байтов. Этот уровень косвенного обращения также допускает базовую форму сжатия; когда значения контейнера точно такие же, они могут указывать на одно и то же смещение таблицы смещений.

Примеры контейнеров:

0xA5 - массив из 5 элементов. Значения этих 5 элементов не обнаруживаются сразу после маркера. Вместо этого после маркера мы находим 5 ссылок на объекты, которые действуют как смещения к таблице смещений. После этих ссылок возвращаются смещения к их индивидуальным байтовым маркерам в таблице объектов, где можно найти фактические значения (или, если маркер снова является контейнером, выполняется та же процедура).

0xAF 0x10 0x0F - массив из 15 элементов (то же, что и выше, но теперь информация о размере не умещается в 4 бита). Далее следуют 15 ссылок на объекты.

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

Таблица смещения

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

Трейлер

Прицеп имеет длину 32 байта и содержит информацию о размере. Байты с 0 по 4 не используются, а байт 5 включает версию сортировки.

Байт 6 сообщает нам, сколько байтов необходимо для каждого смещения таблицы смещений (offset_table_offset_size). Если список имеет большой размер, для перехода от таблицы смещений к маркеру в таблице объектов может потребоваться 2 или более байта. В конце концов, один байт может занять всего 255 байт от начала файла, и этого может быть недостаточно, если количество объектов велико.

Точно так же байт 7 сообщает нам, сколько байтов необходимо для каждой ссылки на объект в контейнере (object_ref_size) . Опять же, если список имеет большой размер, для перехода от таблицы объектов к позиции в таблице смещения может потребоваться 2 или более байта.

Байты с 8 по 15 содержат количество закодированных объектов (num_objects). Помните, что многобайтовые числовые значения кодируются с прямым порядком байтов.

top_object_offset (байты с 16 по 23) сообщает нам смещение от таблицы смещений, с которой мы должны начать (обычно с нуля, обозначающего первый элемент). Эта позиция таблицы смещений содержит смещение до первого маркера в таблице объектов.

offset_table_start (байты с 24 по 31) обозначает начало таблицы смещений, считая от начала файла.

Пример

Рассмотрим простой список ниже, как видно из Xcode:

Его XML-представление выглядит следующим образом:

Тот же список в двоичном формате показан на рисунке 3, где изображены заголовок (зеленый), таблица объектов (синий), таблица смещений (красный) и конец (желтый).

По первым 8 байтам заголовка мы сразу определяем тип списка как bplist00. А теперь давайте внимательнее посмотрим на трейлер:

Мы можем сразу вывести следующее (помните, все идет с прямым порядком байтов):

  • offset_table_offset_size: 0x01 байт (зеленый)
  • object_ref_size: 0x01 байт (желтый)
  • num_objects: 0x10 (16 объектов, оранжевый)
  • top_object_offset: 0x00 (красный)
  • offset_table_start: 0x7F (синий)

Затем давайте взглянем на таблицу смещений. Из трейлера мы уже знаем, где начинается таблица смещений (0x7F), на сколько объектов она указывает (0x10), какого размера слоты таблицы смещений (1 байт) и в каком смещении находится указатель первого объекта (позиция 0 ).

Каждая запись в таблице смещений содержит смещение, которое приводит нас к соответствующему маркеру в таблице объектов (показано ниже тем же цветом 🤯🧐):

Сфокусируемся на маркерах (… и отбросим многоцветный):

С первого взгляда мы можем увидеть следующие 16 объектов по порядку:

  1. 0xD3 - словарь с 3 парами ключ-значение
  2. 0x57 - строка ASCII из 7 символов
  3. 0x56 - строка ASCII из 6 символов
  4. 0x5B - строка ASCII из 11 символов
  5. 0x23 - Действительное число длиной 8 байт
  6. 0xA2 - массив из 2 элементов
  7. 0xD2 - словарь из 2 пар ключ-значение
  8. 0x56 - строка ASCII из 6 символов
  9. 0x5A - строка ASCII из 10 символов
  10. 0x09 - логическое истинное значение
  11. 0x33 - Дата
  12. 0xD2 - словарь из 2 пар ключ-значение
  13. 0x5A - строка ASCII из 10 символов
  14. 0x08 - логическое ложное значение
  15. 0x33 - Дата
  16. 0x5D - строка ASCII из 13 символов

Пройдем по пути к первому объекту. Глядя на трейлер, первое смещение таблицы смещений равно нулю от начала таблицы смещений, поэтому мы смотрим на начало таблицы смещений (0x7F). Содержащееся в нем значение (0x08) говорит нам, что первый объект находится в 8 байтах после начала файла. Имеется значение (0xD3), обозначающее словарь с 3 парами ключ-значение. В следующей позиции (0x09) начинаются ссылки на клавиши (а не на настоящие ключи). Эти 3 клавиши являются смещениями к таблице смещений. Смещения: 0x01, 0x02, 0x03. После этого появятся 3 значения. Это снова смещения к таблице смещений: 0x04, 0x05, 0x0F.

Найдем 1-й ключ словаря. Мы перемещаемся на 1 позицию от нашего маркера 0xD3, находим значение 0x01. Затем мы берем начало таблицы смещений (0x7F) и добавляем это значение, в результате чего получаем 0x80. В 0x80 мы находим значение 0x0F, которое переводит нас к маркеру 0x57, обозначающей строку из 7 байтов:

0x56 0x65 0x72 0x73 0x69 0x6F 0x6E

давая ключ словаря «Версия».

Чтобы получить его значение, мы перемещаемся от нашего маркера 0xD3 на 3 позиции вправо и следуем той же процедуре, в результате чего получаем маркер 0x23, который представляет собой 8-байтовое действительное число.

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

0x40 0x22 0xD1 0xEB 0x85 0x1E 0xB8 0x52

что соответствует 9,41 в 64-битном формате двойной точности IEEE754. Итак, у нас есть первая пара "ключ-значение": «Версия»: 9.41.

Давайте продолжим со вторым ключом, который содержит значение 0x02 и ведет нас к маркеру 0x56. Маркер обозначает строку ASCII с 6 последующими символами, что дает ключ «Электронные письма».

Соответствующее значение приводит к маркеру 0xA2, который представляет собой массив из 2 элементов:

Следующие два байта содержат ссылки на объекты, которые указывают на таблицу смещений (следуйте зеленым и белым путям):

Каждое смещение таблицы смещений указывает на словарь из 2 пар ключ-значение. Давайте посмотрим на первый словарь:

Первый ключ указывает на маркер 0x56 и строку isRead.

Второй ключ указывает на маркер 0x5A и строку «ReceiveAt».

Первое значение указывает на маркер 0x09, который является Bool со значением true.

Второе значение указывает на маркер 0x33, который представляет собой дату с 8-байтовой меткой времени Core Data, которая соответствует Sun 14 января 18:18:26 2018 UTC или Sun 14 января 20:18:26 2018 по местному времени Афины, Греция, как видел в Xcode.

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

Стоит заметить, что ключ словаря isRead сохраняется только один раз для обоих словарей, тогда как другой ключ receiveAt сохраняется дважды, несмотря на то, что он является одними и теми же символами. Если вы посчитаете удобочитаемые элементы представления XML, вы найдете 17 объектов, в то время как двоичная версия содержит 16 закодированных объектов. Разница в сжатом ключе isRead.

Заключение

Двоичные списки предлагают компактный способ эффективного хранения объектов в структурированном и переносимом виде. В этом сообщении блога мы взглянули на внутреннюю структуру наиболее распространенного bplist версии 00.