© Иван Рощин, Москва

Повышение степени сжатия музыкальных модулей

(«Радиомир. Ваш компьютер» 7/2002)
Дата последнего редактирования: 1.04.2003.

Введение
О музыкальных модулях
Основная идея
Реализация
Руководство пользователя
Получаемый выигрыш
О скорости эмуляции
Ограничения эмуляции

Скачать текст программы (8 КБ ZIP)

Введение

Чтобы программа занимала меньше места на диске, её часто сжимают каким-либо упаковщиком. Если в программе содержатся музыкальные модули, то, повысив степень их сжатия, можно добиться дополнительного сокращения длины программы. Это особенно необходимо, если длина программы не должна превышать определённой величины — например, при написании intro.

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

Но есть другой способ — так преобразовать модуль, чтобы он более эффективно сжался обычным упаковщиком, тем же, которым сжимается вся программа. Тогда проблемы, связанные с необходимостью наличия специального распаковщика, отпадут. Также, как мы увидим дальше, не возникнет необходимости подробно разбираться в формате модулей. Об этом способе и пойдёт речь.

О музыкальных модулях

Как известно, музыку пишут с помощью специальных программ — музыкальных редакторов. Чтобы использовать написанную мелодию отдельно от редактора, её подвергают специальной обработке — компиляции. Компилятор может быть как встроенным в редактор, так и независимым.

Музыкальный модуль может быть откомпилирован без плеера (тогда там будут только данные о мелодии) или с плеером, т.е. с набором процедур для проигрывания (тогда в модуле сначала идёт плеер, а за ним — данные). Длина плеера, как правило, постоянна для данного компилятора, а длина данных зависит от конкретной мелодии.

Для вызова процедур плеера (обычно таких процедур три) используются точки входа, находящиеся по определённому смещению от начала плеера.

Первая процедура — INIT (инициализация), вызывается перед началом проигрывания.

Вторая процедура — PLAY (проигрывание), вызывается каждые 1/50 секунды (обычно синхронно с маскируемыми прерываниями). Время работы этой процедуры составляет от нескольких процентов до нескольких десятков процентов от промежутка между двумя прерываниями (в зависимости от редактора, в котором создан модуль, и от используемого плеера), так что на проигрывание музыки тратится лишь небольшая часть времени процессора.

Третья процедура — STOP (заглушение звука). Она может и не использоваться в конкретной программе.

Основная идея

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

В данных о мелодии не использоваться при проигрывании могут, например, название мелодии или данные о конце длинного сэмпла (если мелодия такова, что после одной ноты через короткий промежуток времени следует другая, и в результате конец сэмпла никогда не проигрывается). В плеере неиспользуемыми могут быть некоторые элементы частотной таблицы (где указывается значение делителя частоты для каждой ноты): ведь, как правило, в мелодии используются не все ноты. Также в плеере могут не использоваться некоторые обработчики так называемых команд (не путать с командами процессора), таких как «изменить темп», «изменить частоту ноты»: ведь обычно в мелодии присутствуют не все возможные команды. Может не использоваться первоначальное значение определённых ячеек памяти, выделенных для хранения переменных при работе плеера. Может быть и другая неиспользуемая информация.

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

Ещё чуть-чуть подумав, нетрудно догадаться, что лучше не обнулять ячейки, а заполнять их значением, взятым из предыдущей используемой ячейки — тогда сжатие станет ещё более эффективным. В самом деле, если раньше был участок длиной n, занятый нулевыми байтами, то теперь будет участок длиной как минимум n+1, занятый одинаковыми байтами, а значит, и сожмётся он лучше.

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

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

Реализация

Для определения неиспользуемых ячеек заведём в памяти массив с количеством элементов, равным длине обрабатываемого модуля. Сначала обнулим все элементы. Нулевое значение будет обозначать, что к соответствующей ячейке памяти не было обращения. При эмуляции, если произошло обращение к какой-либо ячейке памяти (естественно, относящейся к модулю), проверяем: это первое обращение к данной ячейке или нет? Нас будет интересовать только первое обращение — т.е. когда соответствующий элемент массива равен нулю. Если выполняется чтение из ячейки, вместо нуля записываем 1, а если запись — 2.

Если после окончания эмуляции элемент массива равен нулю — значит, к соответствующей ячейке модуля не было обращений; если элемент равен 1 — значит, значение этой ячейки было прочитано; если равен 2 — значит, первоначальное значение не было прочитано, а на его место было записано другое. Понятно, что ячейки, которым соответствуют значения 0 и 2, и будут искомыми.

Теперь более подробно об эмуляции. При проигрывании музыки вначале вызывается процедура INIT, затем — процедура PLAY (определённое количество раз), и, если надо, процедура STOP. Рассмотрим, как производится эмуляция действий процессора при выполнении какой-либо из этих процедур.

Имеются следующие структуры данных: область памяти, в которой располагается стек выполняемой процедуры, и массив, где хранятся значения регистров при её выполнении (так называемые эмулируемые регистры; их я буду в дальнейшем обозначать, добавляя «EM» к названию регистра: например, EM_HL). Перед выполнением процедуры в вышеописанный массив записываются начальные значения регистров, при этом в EM_SP помещается адрес конца области памяти, выделенной под стек (не забываем: стек растёт вниз), а в EM_PC — адрес начала процедуры.

Выполнение происходит по отдельным командам. Рассмотрим выполнение одной команды. Значения регистров на момент её выполнения известны. Адрес начала команды также известен (он содержится в EM_PC).

Во-первых, определяется длина команды. Далее определяется, прозводит ли команда чтение из памяти или запись в память, и если да, то по каким адресам (понятно, что из ячеек, в которых хранится код команды, также произойдёт чтение). Эти сведения помещаются в массив с информацией об используемых ячейках памяти.

Если выполняемая команда не является командой передачи управления, то она копируется в специальный буфер и непосредствено запускается на выполнение. Перед этим содержимое массива регистров загружается в регистры процессора, а после выполнения — значения регистров процессора записываются в массив. EM_PC увеличивается на длину выполненной команды и, таким образом, указывает теперь на следующую команду.

Выполнение команды передачи управления происходит с помощью специальной подпрограммы (для каждой такой команды подпрограмма своя).

Если текущая выполняемая команда — RET, и при этом значение EM_SP совпадает с адресом конца области памяти, выделенной под стек, то считается, что эта команда обеспечивает выход из выполняемой процедуры. На этом выполнение процедуры завершается.

Руководство пользователя

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

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

Итак, вам нужно обработать модуль с плеером или без (если модуль без плеера, то плеер должен быть загружен отдельно). Вам должна быть известна следующая информация: адрес и длина модуля, адреса процедур INIT, PLAY и STOP плеера (если STOP не используется — адрес считается равным #0052), количество вызовов процедуры PLAY (если модуль зациклен и проигрывается «бесконечно», то количество вызовов устанавливается таким, чтобы цикл был проигран два раза).

Так как для хранения количества вызовов процедуры PLAY используется двухбайтная переменная, количество вызовов не может превышать 65535. Исходя из того, что между двумя вызовами проходит 1/50 секунды, получаем, что максимальное время проигрывания модуля — 21 минута и 50,7 секунды. Я не стал усложнять программу, выделяя под переменную три байта для увеличения максимального времени проигрывания, так как для подавляющего большинства модулей это время не превышает нескольких минут. Тем не менее, изменение программы при необходимости не представляет каких-либо сложностей.

Итак, устанавливаете значения соответствующих переменных в тексте программы, компилируете её, затем загружаете модуль и вызываете процедуру «эмуляция с обнулением массива RW_MEMORY» (это массив с информацией об используемых ячейках памяти). Для вызова этой процедуры используется точка входа по смещению 0 от начала программы.

Эмуляция займёт довольно продолжительное время, при этом вы будете слышать замедленное проигрывание мелодии. Если после её окончания флаг C будет сброшен, то всё в порядке; если же установлен — значит, при эмуляции встретилась неподдерживаемая недокументированная команда (см. раздел «Ограничения эмуляции»). Адрес этой команды вы сможете узнать из переменной EM_PC.

После окончания эмуляции модуль следует перезагрузить: вдруг при его проигрывании значения каких-либо ячеек изменились? Затем вызовите процедуру «установка новых значений неиспользуемых ячеек памяти» (точка входа по смещению 4 от начала программы). После этого остаётся только записать обработанный модуль на диск.

Когда нужно обработать один за другим несколько модулей, удобнее устанавливать значения переменных не в исходном тексте программы с последующей перекомпиляцией, а непосредственно в коде программы с помощью отладчика. Смещения переменных от начала программы приведены в табл. 1. При установке значений не забывайте, что они должны быть в формате low-high: сначала младший байт, потом старший.

Если в вашей программе используются несколько модулей без плеера, проигрываемые отдельным плеером, и вы хотите обработать только этот плеер, то порядок действий следующий. Устанавливаете значения соответствующих переменных в тексте программы, подставляя при этом вместо адреса начала модуля и длины модуля соответственно адрес начала плеера и длину плеера. Компилируете программу, в отладчике загружаете плеер и первый музыкальный модуль. Вызываете процедуру «эмуляция с обнулением массива RW_MEMORY». После окончания эмуляции загружаете второй модуль и вызываете процедуру «эмуляция без обнуления массива RW_MEMORY» (точка входа по смещению 2 от начала программы). Так же повторяете и со всеми остальными модулями. Так как очистка массива с информацией об используемых ячейках памяти не производится, информация в нём будет накапливаться: если при проигрывании хотя бы одного модуля значение какой-то ячейки плеера будет использоваться, она будет помечена в массиве. Затем перезагружаете плеер, вызываете процедуру «установка новых значений неиспользуемых ячеек памяти» и записываете обработанный плеер на диск.

Получаемый выигрыш

А стоит ли овчинка выделки? Ещё бы! :–) Для примера я взял десять PT3-модулей с плеером, которые были представлены на demoparty «Chaos Constructions 1», и сравнил степень их сжатия до обработки и после обработки. Результаты приведены в табл. 2. Упаковка модулей производилась с помощью HRUST 1.3 в режиме normal.

Если посчитать средний выигрыш, получится 8,5% от исходной длины модуля, то есть для 10000-байтного модуля выигрыш составит примерно 850 байтов.

В табл. 3 приведена аналогичная информация для десяти PT3-модулей без плеера, которые также были взяты из представленных на demoparty «Chaos Constructions 1».

Как видим, здесь средний выигрыш составляет около 3% от длины исходного модуля, т.е. для 5000-байтного модуля — примерно 150 байтов.

О скорости эмуляции

При эмуляции выполнение программы сильно замедляется — в среднем в 125 раз (для разных команд замедление неодинаково). Это не значит, однако, что 5-минутный модуль будет обрабатываться более 10 часов. Как уже упоминалось выше, проигрывание музыки занимает лишь небольшую часть процессорного времени (для модулей, созданных в Pro Tracker 3, — примерно 8%). Соответственно, 5-минутный PT3-модуль будет обработан примерно за 50 минут.

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

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

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

Ограничения эмуляции

Так как программа предназначена для выполнения довольно специфической задачи — обработки музыкальных модулей, то эмуляция Z80 была несколько упрощена. Но если вы захотите обрабатывать с помощью этой программы не музыкальные модули, а что-нибудь ещё, то должны иметь представление об ограничениях эмуляции:

• каждая команда выполняется при запрещённых прерываниях (то есть при выполнении команды HALT всё зависнет);
• не поддерживаются недокументированные команды, начинающиеся с префикса ED, а также с последовательностей префиксов DD ED и FD ED;
• не поддерживается выполнение последовательности префиксов DD и FD (например, DD DD FD DD FD);
• команды блочного ввода-вывода (INIR, INDR, OTIR, OTDR) не выполняются (помечены в таблице как неподдерживаемые недокументированные команды), т.к. их эмуляция потребовала бы наличия специальных подпрограмм, определяющих, к каким ячейкам памяти будет обращение (так же, как и для команд LDDR, LDIR, CPDR, CPIR);
• эмуляция регистра R не производится;
• при выполнении команд LDIR и LDDR не отслеживается ситуация, когда при записи очередного байта происходит изменение кода команды (код этих команд считывается из памяти в каждом цикле выполнения);
• команды RST выполняются, но обращение к ячейкам памяти при их выполнении не учитывается;
• переключение банков памяти специально не отслеживается.