Величины переменной длины

Хватит лирических отступлений, сейчас наша задача — разобраться в формате хранения данных. И первая трудность, с которой столкнулись разработчики SMF, — как сохранять время наступления события.

Здесь есть два варианта: хранить для каждого события время от начала песни, либо от последнего события перед ним (на том же канале). Однако первый вариант не рационален, ведь чаще всего интервал между событиями невелик, соседние события имеют близкое друг к другу время исполнения. Так, в пассаже из трех нот, первая может иметь время, скажем, 22:3:152, вторая — 22:3:244, третья — 22:3:288. Для сохранения этих чисел (переведенных в тики от начала песни) нужно зарезервировать как минимум четыре байта на каждое. Если же пойти по второму пути, то вместо трех больших чисел можно сохранить одно большое стартовое (22:3:152), а за ним — два маленьких, разницу в тиках между первой и второй, и второй и третьей нотами (в данном случае, 92 и 44), для них достаточно одного байта. Но все равно проблема остается: в зависимости от события нужно отводить разное число байт для сохранения времени.

Если бы SMF разрабатывался в настоящее время (да еще фирмой Microsoft, которая вообще мало заботится о размере своих файлов и потребной памяти), на эту проблему закрыли бы глаза. Выделили под сохранение времени фиксированное поле, скажем, 8 байт на событие, и не мучались. Однако в 1988 году первичная (оперативная) память стоила очень дорого, на счету был каждый байт, да и вторичная (дисковые носители) имела очень скромный объем. Поэтому разработчики SMF хотели получить максимально компактный формат.

Было решено сохранять дельта-время, то есть разницу в тиках между данным событием и предыдущим (либо началом песни). Например, если первое событие — взятие ноты До первой октавы — произошло в момент 40 тиков от начала песни, то его дельта-время будет равно 40. Если спустя четыре тика будет взята нота Фа, то ее дельта-время будет равно 4. Если два события происходят одновременно, то одному из них назначается дельта-время, равное нулю. Если событие происходит точно в начале песни, оно также имеет нулевое дельта-время. Однако следующее событие может случиться и через полтора часа (то есть, через несколько миллионов тиков). Как быть в этом случае? Ведь память нужно экономить, а отводить под дельта-время фиксированное поле размером в несколько байт нежелательно.

На помощь приходят так называемые величины переменной длины. Они представляют удобный способ записи целых чисел — от самых малых до самых больших, без необходимости отводить под число фиксированное количество байт. Биты исходного числа упаковываются в один или более байтов: в каждый байт по семь бит (справа, биты с 0 по 6-й). Старший бит в байте является служебным; все байты в серии, кроме последнего, должны содержать в нем единицу, последний — ноль. Несколько примеров упаковки показаны на рис. 4.

Например, нужно упаковать в формат переменной длины число 64 (шестнадцатеричное 0x40). В двоичном виде это число записывается как 0100 0000. Здесь как раз семь значащих бит, поэтому упаковывается это число в один байт без изменений — 0100 0000 (он же является и последним байтом серии), старший бит равен 0.

Теперь число 128 (0x80). В двоичном виде записывается как 1000 0000. Здесь восемь значащих бит, поэтому в один байт все не влезет, нужно разбивать на два. Первый байт должен иметь в старшем бите единицу, второй (как завершающий байт серии) — ноль. Во второй байт помещаем семь младших битов исходного числа, получается 0 000 0000. Оставшийся один бит (единицу) помещаем в правую часть первого байта — получается 1000 0001. В итоге, число 0x80 записывается в виде двух байт: 0x81 0x00. Распаковка происходит очень просто. Мы не знаем заранее, сколько байт содержится в серии. Считываем первый байт — 1000 0001. Старший служебный бит (1) говорит о том, что это не последний байт серии, есть еще байты. Служебную единицу отбрасываем, остается семь бит — 000 0001. Считываем второй байт — 0000 0000. Старший служебный бит (0) говорит о том, что это завершающий байт серии (то есть в серии всего два байта). Служебный бит отбрасываем. Остаются также семь бит — 000 0000. Дописываем к ним слева семь бит, выделенных из первого байта, получаем 000 0001 000 0000. Отбросив первые шесть нулей, получаем искомое число 1000 0000 (0x80).

Итак, метод величин переменной длины позволяет под разные числа отводить разное количество байт: для чисел в диапазоне от 0 до 127 — один байт, от 128 до 16383 — два байта и так далее. Максимальное число, представляемое таким способом, в принципе, не ограничено. Однако в SMF длина серии ограничивается четырьмя байтами (три с установленным старшим битом и один завершающий, с нулевым). В результате максимальное дельта-время может составлять 0x0FFFFFFF (или 268 435 455 тиков), что при темпе 500 BPM и разрешении 96 PPQN составляет около четырех суток. Более чем достаточно!

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

Interchange File Format (IFF)

Структура стандартного MIDI-файла почти полностью заимствована из формата IFF (Interchange File Format), разработанного в 1985 году компанией Electronic Arts. Это формат хранения и обмена данными, который уже почти двадцать лет облегчает жизнь как пользователям, так и разработчикам программного обеспечения. Компания Electronic Arts не только предоставила открытую документацию, но также исходный код на языке C для считывания и записи IFF-файлов.

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

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

Существует несколько типов файлов IFF. Например, файлы ILBM и GIFF содержат в себе графическую информацию, файлы SMUS — нотную запись, файлы AIFF и WAVE — цифровой звук.

Файл IFF состоит из однотипных элементов, называемых блоками (chunks). Блок — это структура данных, состоящая из буквенного идентификатора (четыре ASCII-символа), размера блока (четыре байта) и самих данных (рис. 5). Блок удобно представлять как оболочку, в которую "завернуты" данные. Сами данные могут содержать что угодно: графику, текст, анимацию, звук, набор 3D-объектов и так далее.

Блоки в IFF-файле могут быть вложенными, рис. 6. Фактически, IFF-файл — это не что иное, как блок верхнего уровня, содержащий внутри себя один или несколько других блоков. Такой принцип хранения данных позволяет "заворачивать" в файл несколько разнородных данных, в том числе и несколько файлов IFF, что напоминает уже файловую систему внутри файла. Правда, при вложенной организации данных есть один недостаток — файл становится сложно интерпретировать, вычленять из него блоки.

Большинство IFF-файлов содержат блок верхнего уровня с идентификатором "FORM". В него входят другие блоки (рис. 7). Единственными данными блока FORM являются четыре байта, описывающие тип файла (например, "ILBM", InterLeaved Bit Map). Непосредственно за ними размещаются вложенные блоки, например, "BMHD" (заголовок изображения), "CMAP" (палитра) и "BODY" (сами пиксели). Названия блоков и формат данных придумывает разработчик конкретного типа файла. Другие программы, если встречают блок с незнакомым названием, могут спокойно пропустить его, ориентируясь по полю, содержащему длину блока.

Все числовые данные в файлах IFF хранятся в порядке big-endian, то есть сначала хранится старший байт числа (MSB), затем — младший. Подробнее об этом рассказано во врезке. Блоки внутри файла всегда должны начинаться с четного байта. Если предыдущий блок содержит нечетное число байт, он дополняется нулевым байтом до четного.