С давних пор единственным моим архиватором является программа 7-Zip. Мне нравится его степень сжатия и скорость работы, поэтому я использую его практически повсеместно: для сжатия дистрибутивов программ, для архивирования коллекций картинок, а так же для хранения музыкальных релизов. Музыку я качаю с сетевых некоммерческих лейблов, где она чаще всего поставляется в виде архива (zip или rar), содержащего композиции и картинки-обложки. После скачивания архивы пережимаются программой 7-Zip и в таком виде хранятся на жестком диске. Для прослушивания музыки архивы не требуется распаковывать, так как современные плееры умеют играть музыку прямо из них (в частности, я использую Foobar2000). И хотя суммарный объем памяти, занимаемой всеми архивами, еще далек от емкости жесткого диска, меня начала занимать мысль об улучшении степени сжатия mp3-файлов. Как говорил один мой преподаватель, задача — это неудовлетворенное чувство беспокойства; и это было именно то чувство, которое испытывал я. Изобретать свой перекодировщик мне не хотелось, поэтому было решено попробовать написать фильтр, удаляющий какую-нибудь избыточную информацию.
Под mp3 мы будем понимать MPEG-1/2/2.5 Layer 3. Посмотрим, что из себя представляет mp3-файл.
Итак, mp3-файл состоит из множества фреймов, причем фреймы могут быть связанны друг с другом, то есть для декодирования одного фрейма может понадобиться заглянуть в другой. В файле могут присутствовать теги, как перед аудиоданными, так и после. Каждый фрейм хранит 1152 сэмплов (для стерео режима) и имеет продолжительность в 26 мс. Размер фрейма зависит от используемого битрейта и частоты дискретизации, и вычисляется по следующей формуле:
Padding — это специальный флаг в заголовке фрейма означающий, что фрейм дополнен одним байтом.
Фрейм состоит из заголовка, проверочного кода (необязательно), информации, необходимой для декодирования сэмплов (будем называть эту информацию «side info», так как придумать приемлемого русского перевода этого словосочетания мне не удалось), собственно самих упакованных сэмплов и дополнительных данных, не имеющих прямого отношения к закодированным сэмплам:
Заголовок, размером в 32 бита, имеет следующую структуру:
На практике некоторые поля заголовка не используются и/или остаются одними и теми же на протяжении всего mp3-файла. Например, версия MPEG, индекс слоя, private bit, copyright bit, original bit, etc. Если файл был создан с использованием постоянного битрейта (CBR), то не меняется и поле bitrate index.
Первая мысль заключается в том, что необязательно хранить все поля заголовка фрейма, а только те, которые меняются на протяжении файла. Остальные, не меняющиеся поля, можно сохранить только один раз. Пройдясь по заголовкам всех фреймов можно собрать статистику и выявить поля, которые реально используются.
Сразу за заголовком может располагаться проверочный код CRC. Он представляет собой 16-ти битное целое, вычисляемое с использованием алгоритма CRC16 по последним 16-ти битам заголовка фрейма и по всем байтам side info.
Вторая мысль заключается в том, что раз мы знаем как вычислить проверочный код, то его можно не хранить. Разумеется, просто так взять и выкинуть CRC из фрейма мы не имеем права. Сперва нужно убедиться, что оно представляет собой правильное значение, ведь в сам проверочный код или в байты, по которым он вычисляется, могла закрасться ошибка.
Подробно останавливаться на анатомии side info я не буду. Side info представляет из себя достаточно сложную структуру со множеством полей, которые меняются в каждом фрейме. Провернуть такой же фокус с полями side info, как с полями заголовка фрейма не выйдет.
Следом за side info идут сжатые кодом Хаффмана аудиоданные. На самом деле это не совсем так, так как коды Хаффмана чередуются с масштабными коэффициентами (scale factors), но мы для простоты положим, что после side info и до конца фрейма располагаются аудиоданные.
Между фреймами могут находиться любые другие данные, лишь бы среди этих данных не было сигнатур заголовка фрейма (Sync word).
Поизучав исходный код 7-Zip я натолкнулся на реализацию фильтра BCJ2, предназначенного для улучшения сжатия исполняемых файлов (*.exe, *.dll). Отличительной особенностью этого фильтра является то, что у него один вход и четыре выхода. На каждый из выходов навешан свой кодировщик. Таким образом получается, что входной файл разделяется на 4 потока и каждый поток сжимается своим отдельным кодером.
Идея нескольких выходов мне приглянулась и я решил применить ее в своем фильтре:
— в один поток упаковывать поля заголовков фреймов в соответствии с первой мыслью
— во второй поток упаковывать side info
— и, наконец, в третий поток упаковывать оставшуюся информацию: теги и коды Хаффмана
Первые два потока сжимаются с помощью алгоритма LZMA с настройками, используемыми внутри 7-Zip для сжатия заголовков архива, а третий поток сжимается алгоритмом, выбранным пользователей в окне «Добавить в архив».
Кодировщик работает так: последовательно перебираются все фреймы файла. Фрейм разделяется на три части: side info отправляется в поток side info, коды Хаффмана отправляются в главный выходной поток, а поля заголовков складируются в буфер. Если во фрейме присутствует CRC и оно оказывается верным, то оно пропускается, в противном случае его значение переписывается в поток заголовков, чтобы при распаковке его можно было восстановить.
Sync word (11 бит) каждого заголовка просто выбрасывается. Значения полей, которые не менялись в течении файла, записываются в поток заголовков только один раз, тогда как меняющиеся поля записываются последовательно друг за другом.
Декодер работает зеркально кодировщику: сначала восстанавливаются все заголовки, затем по ним начинается восстановление каждого фрейма. Вычисляется, либо восстанавливается из первого потока CRC, следом записывается side info и остаток фрейма.
Реализация не представляет собой ничего особенно сложного и поэтому приводить ее здесь я не вижу смысла. Исходники выложены на гитхабе. Отмечу лишь, что поддержка подобных фильтров (с одним входом и несколькими выходами) в 7-Zip реализована недостаточно прозрачно и мне пришлось не без мыла лезть внутрь 7-Zip, в частности, в файл 7zUpdate.cpp. Да, кстати, при разработке фильтра использовались исходники 7-Zip 9.20.
Скомпилированная dll лежит на том же гитхабе. Ею нужно заменить 7z.dll в папке, где у вас установлен 7-Zip.
Тестирование работы проводилось на выборке из 1351 файлов суммарным объемом 16755839778 байт (15.605 Гб), на компьютере с операционной системой Windows XP, процессором Intel Core 2 6700 (2.66 Ггц) и тремя гигами оперативки. Каждый файл по отдельности был сжат в архив и распакован. Сначала без использования фильтра, затем с фильтром. Везде использовался уровень сжатия Ultra.
Фильтр позволил сэкономить:
— 236199251 байт (~225 Мб) памяти на жестком диске
— 908 секунд (~15 минут) на упаковке
— 407 секунд (~8 минут) на распаковке
Как видно, скорость упаковки возросла на 8%, а скорость распаковки на целых 15%.
Фильтр улучшил коэффициент сжатия mp3-файлов на 1.5%. Выдающимся этот результат не назовешь, но и плохим тоже, ведь фильтр работает с сжатыми данными.
На этом все. Спасибо за внимание.
Анализ условий задачи
Под mp3 мы будем понимать MPEG-1/2/2.5 Layer 3. Посмотрим, что из себя представляет mp3-файл.
Итак, mp3-файл состоит из множества фреймов, причем фреймы могут быть связанны друг с другом, то есть для декодирования одного фрейма может понадобиться заглянуть в другой. В файле могут присутствовать теги, как перед аудиоданными, так и после. Каждый фрейм хранит 1152 сэмплов (для стерео режима) и имеет продолжительность в 26 мс. Размер фрейма зависит от используемого битрейта и частоты дискретизации, и вычисляется по следующей формуле:
Padding — это специальный флаг в заголовке фрейма означающий, что фрейм дополнен одним байтом.
Фрейм состоит из заголовка, проверочного кода (необязательно), информации, необходимой для декодирования сэмплов (будем называть эту информацию «side info», так как придумать приемлемого русского перевода этого словосочетания мне не удалось), собственно самих упакованных сэмплов и дополнительных данных, не имеющих прямого отношения к закодированным сэмплам:
Заголовок, размером в 32 бита, имеет следующую структуру:
| Название | Длина поля | Назначение |
|---|---|---|
| Sync word | 11 | Используется для поиска заголовка. Все 11 бит установлены в «1» |
| Версия MPEG | 2 | |
| Индекс слоя (layer) | 2 | |
| Бит защиты | 1 | Если не установлен, то во фрейме присутствует CRC |
| Индекс битрейта | 4 | |
| Индекс частоты дискретизации | 2 | |
| Padding bit | 1 | Тот самый флаг, сигнализирующий, что фрейм дополнен одним байтом |
| Private bit | 1 | Несет какую-либо специфическую информацию |
| Режим кодирования каналов | 2 | Может быть mono, stereo, joint stereo, dual channel |
| Mode extension | 2 | Используется в режиме кодирования каналов joint stereo |
| Copyright bit | 1 | Если этот бит установлен, то это означает, что копирование файла неправомерно |
| Original bit | 1 | Если этот бит установлен, то это означает, что файл находится на своем оригинальном носителе |
| Акцент (Emphasis) | 2 | Сообщает декодеру, что требуется дополнительная обработка аудиоданных |
На практике некоторые поля заголовка не используются и/или остаются одними и теми же на протяжении всего mp3-файла. Например, версия MPEG, индекс слоя, private bit, copyright bit, original bit, etc. Если файл был создан с использованием постоянного битрейта (CBR), то не меняется и поле bitrate index.
Первая мысль заключается в том, что необязательно хранить все поля заголовка фрейма, а только те, которые меняются на протяжении файла. Остальные, не меняющиеся поля, можно сохранить только один раз. Пройдясь по заголовкам всех фреймов можно собрать статистику и выявить поля, которые реально используются.
Сразу за заголовком может располагаться проверочный код CRC. Он представляет собой 16-ти битное целое, вычисляемое с использованием алгоритма CRC16 по последним 16-ти битам заголовка фрейма и по всем байтам side info.
Вторая мысль заключается в том, что раз мы знаем как вычислить проверочный код, то его можно не хранить. Разумеется, просто так взять и выкинуть CRC из фрейма мы не имеем права. Сперва нужно убедиться, что оно представляет собой правильное значение, ведь в сам проверочный код или в байты, по которым он вычисляется, могла закрасться ошибка.
Подробно останавливаться на анатомии side info я не буду. Side info представляет из себя достаточно сложную структуру со множеством полей, которые меняются в каждом фрейме. Провернуть такой же фокус с полями side info, как с полями заголовка фрейма не выйдет.
Следом за side info идут сжатые кодом Хаффмана аудиоданные. На самом деле это не совсем так, так как коды Хаффмана чередуются с масштабными коэффициентами (scale factors), но мы для простоты положим, что после side info и до конца фрейма располагаются аудиоданные.
Между фреймами могут находиться любые другие данные, лишь бы среди этих данных не было сигнатур заголовка фрейма (Sync word).
Алгоритм
Поизучав исходный код 7-Zip я натолкнулся на реализацию фильтра BCJ2, предназначенного для улучшения сжатия исполняемых файлов (*.exe, *.dll). Отличительной особенностью этого фильтра является то, что у него один вход и четыре выхода. На каждый из выходов навешан свой кодировщик. Таким образом получается, что входной файл разделяется на 4 потока и каждый поток сжимается своим отдельным кодером.
Идея нескольких выходов мне приглянулась и я решил применить ее в своем фильтре:
— в один поток упаковывать поля заголовков фреймов в соответствии с первой мыслью
— во второй поток упаковывать side info
— и, наконец, в третий поток упаковывать оставшуюся информацию: теги и коды Хаффмана
Первые два потока сжимаются с помощью алгоритма LZMA с настройками, используемыми внутри 7-Zip для сжатия заголовков архива, а третий поток сжимается алгоритмом, выбранным пользователей в окне «Добавить в архив».
Кодировщик работает так: последовательно перебираются все фреймы файла. Фрейм разделяется на три части: side info отправляется в поток side info, коды Хаффмана отправляются в главный выходной поток, а поля заголовков складируются в буфер. Если во фрейме присутствует CRC и оно оказывается верным, то оно пропускается, в противном случае его значение переписывается в поток заголовков, чтобы при распаковке его можно было восстановить.
Sync word (11 бит) каждого заголовка просто выбрасывается. Значения полей, которые не менялись в течении файла, записываются в поток заголовков только один раз, тогда как меняющиеся поля записываются последовательно друг за другом.
Декодер работает зеркально кодировщику: сначала восстанавливаются все заголовки, затем по ним начинается восстановление каждого фрейма. Вычисляется, либо восстанавливается из первого потока CRC, следом записывается side info и остаток фрейма.
Реализация и практические результаты
Реализация не представляет собой ничего особенно сложного и поэтому приводить ее здесь я не вижу смысла. Исходники выложены на гитхабе. Отмечу лишь, что поддержка подобных фильтров (с одним входом и несколькими выходами) в 7-Zip реализована недостаточно прозрачно и мне пришлось не без мыла лезть внутрь 7-Zip, в частности, в файл 7zUpdate.cpp. Да, кстати, при разработке фильтра использовались исходники 7-Zip 9.20.
Скомпилированная dll лежит на том же гитхабе. Ею нужно заменить 7z.dll в папке, где у вас установлен 7-Zip.
Тестирование работы проводилось на выборке из 1351 файлов суммарным объемом 16755839778 байт (15.605 Гб), на компьютере с операционной системой Windows XP, процессором Intel Core 2 6700 (2.66 Ггц) и тремя гигами оперативки. Каждый файл по отдельности был сжат в архив и распакован. Сначала без использования фильтра, затем с фильтром. Везде использовался уровень сжатия Ultra.
| Без фильтра | С фильтром | |
|---|---|---|
| Суммарный объем сжатых данных | 16300442691 байт (15.181 Гб) | 16064243440 байт (14.961 Гб) |
| Суммарное время, потраченное на упаковку | 12181.09 сек | 11273.47 сек |
| Суммарное время, потраченное на распаковку | 3215.44 сек | 2744.76 сек |
Фильтр позволил сэкономить:
— 236199251 байт (~225 Мб) памяти на жестком диске
— 908 секунд (~15 минут) на упаковке
— 407 секунд (~8 минут) на распаковке
Как видно, скорость упаковки возросла на 8%, а скорость распаковки на целых 15%.
Заключение
Фильтр улучшил коэффициент сжатия mp3-файлов на 1.5%. Выдающимся этот результат не назовешь, но и плохим тоже, ведь фильтр работает с сжатыми данными.
На этом все. Спасибо за внимание.
