Компрессия на спектруме: MegaLZ

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

MegaLZ начинал свою карьеру как нативный упаковщик данных ещё в середине 1990х. В ранние версии я пока не заглядывал, поэтому не знаю, менялся ли формат упакованных данных между совсем старыми версиями от Megafire Software, Programmers Group, Bitmunchers и Omega Hackers Group, и последними версиями, уже от Mayhem. Сейчас MegaLZ — это более-менее стандартная вариация на тему LZB. Это означает, что компрессор работает со смешанным битово-байтовым потоком данных, в котором один бит передаётся для того, чтобы отличить литерал от ссылки (это изобретение из LZSS), длина ссылки передаётся гамма-кодом Элиаса, а смещение — упрощённым кодом длиной либо 9, либо 13 бит для ближних и дальних ссылок соответственно. Длина дальней ссылки поэтому оказывается ограниченной 4.5Кб — это и есть размер окна с которым работает MegaLZ. Вообще, MegaLZ довольно похож на Hrum — битовые коды для коротких ссылок у этих двух упаковщиков совпадают по длине, так что очевидно, что они целят на примерно однотипные данные. Вот только в Hrum окно на 500 байт короче; кроме того, длина ссылок в Hrum хранится в виде вариации кода Райса вместо гамма-кода Элиаса. Трудно сказать по которой именно из этих двух причин, но коэффициент сжатия у MegaLZ чуть-чуть выше; на моём корпусе данных — примерно на 0.6%.

MegaLZ был видимо первым спектрумовским компрессором, для которого написали оптимальный парсер (LVD сделал это в ещё 2005 году, невзирая на различные вещи, написанные Einar Saukas в документации на ZX7). Поскольку компрессоры у других упаковщиков были обычно далеки от оптимальных, в сети до сих пор можно найти результаты тестов в которых MegaLZ выносит Hrust1 и прочие хорошие компрессоры. Видимо из-за этого MegaLZ до сих пор очень популярен. Тем не менее, сейчас оптимальные или близкие к оптимальным компрессоры распространены намного шире, поэтому современное сравнение с другими популярными компрессорами выглядит не так впечатляюще:

                       corpora  demos    games    gfx      music    texts      total

exomizer3               35662   223514   343299   464843   130916   206026     1,404,260
aplib(apc12)            35430   228228   344631   477264   129344   208601     1,423,498
hrust13(oh1c)           37069   222955   345123   481785   133856   215126     1,435,914
epcompress(-m3 -9)      36928   227112   346628   487596   136733   214172     1,449,169
hrust21(oh2c)           37005   226013   349276   487812   137582   214274     1,451,962

MEGALZ                  38045   235582   358090   488909   137393   217601     1,475,620

lzsa(-f2)               38022   229148   351632   497298   137949   225356     1,479,405
pletter5d               37743   237918   359857   489015   139437   217903     1,481,873
hrum(mhmt)              38615   235900   359626   491572   138390   220267     1,484,370
zx7                     39484   238903   362443   489624   143457   226092     1,500,003

Если очень кратко, выводы из этой таблички такие. По коэффициенту сжатия MegaLZ практически всегда уступает компрессорам посложнее — Exomizer, ApLib, Hrust1, EpCompress(M3) и Hrust2. Тем не менее, среди компрессоров с битовым потоком и без адаптивности, MegaLZ превосходит большинство конкурентов: Pletter5, Hrum и, разумеется, ZX7. Самый близкий по сжатию компрессор LZSA2 превосходит MegaLZ по сжатию на больших блоках данных т.к. у него нет ограничения на размер окна, но на мелких файлах это преимущество нивелируется и MegaLZ сжимает сильнее LZSA2 как на графике, так и на текстах.

Два года назад я написал, что MegaLZ морально устарел, т.к. стандартный распаковщик, написанный Fyrex, оказался довольно таки нетороплив: ~130 тактов на каждый распакованный байт. Хотя у этого распаковщика были и плюсы — сравнительно небольшой размер (110 байт), релоцируемость, тем не менее, уже в 2017 году можно было распаковывать данные Pletter5d, или тем же ZX7, со скоростью ~70 тактов на байт. Выигрыш в коэффициенте сжатия был невелик, a почти двухкратные потери в скорости распаковки просто сводили с моей точки зрения это достоинство на нет. Тем не менее, прошлой зимой я нашёл время разобраться в формате и переписал распаковщик MegaLZ так, как с моей точки зрения должен выглядеть современный распаковщик LZ на спектруме. Результаты меня приятно удивили. Оптимизированный по размеру распаковщик удалось вместить в 92 байта, и это при том, что скорость распаковки данных с ним выросла до ~98 тактов на распакованный байт. Распаковщик заточенный на скорость у меня получилось довести до ~63 тактов на байт, т.е. до скорости некоторых ротозумеров, или 3*LDIR, и всё это счастье — всего в 234 байтах. (см. Дополнение в конце.)

Итого, с новыми распаковщиками MegaLZ кажется мне снова конкурентноспособным выбором для случаев, если требуется совместить разумный коэффициент сжатия с неплохой скоростью распаковки. LZSA2 всегда существенно выиграет у MegaLZ по скорости распаковки (процентов на 30% как минимум), но на типичных небольших файлах данных, особенно графических, MegaLZ выиграет на пару процентов по коэффициенту сжатия. У себя в демоядре я пока оставил MegaLZ, так как мои данные он пакует заметно лучше, но если я в какой-то момент упрусь в скорость распаковки — переключусь на LZSA2.

По сравнению с прочими пакерами, с новыми распаковщиками, MegaLZ вполне себе уделывает Pletter5 и ZX7. Я считаю, что единственная причина всё ещё использовать ZX7 — это развитая инфраструктура распаковщиков заточенных под спектрумовский экран (речь идёт о проекте RCS и т.п.). Pletter5, мне кажется, уже почти упёрся в свой потолок и сильно уже не улучшится. Кроме того, с учётом сходства MegaLZ и Hrum, видимо есть смысл переписать ещё и распаковщик Hrum — не окажется ли он ещё более быстрым?

Приложения:
Совсем старая страница проекта MegaLZ — полуживая, на архиве.
Зеркало проекта MegaLZ на GitHub, с исходным кодом и собранным упаковщиком.
Страница проекта mhmt, поддерживающего MegaLZ — нерабочая.
Кажется, новая официальная страница проекта mhmt на GitHub, с исходным кодом.
Зеркало проекта mhmt на GitHub, с исходным кодом и собранным упаковщиком.
Новый компактный распаковщик (92 байта, ~98 тактов на байт): unmegalz_small_v2.asm
Новый быстрый распаковщик (234 байта, ~63 такта на байт): unmegalz_fast_v2.asm


Дополнение от 13/01/2021:
За прошедший год я немного улучшил оба декомпрессора. Компактный распаковщик удалось сократить до 88 байт (если у кого-то будут мысли, как его можно ещё сократить — буду очень благодарен, так как у меня там уже начались реально неприятные оптимизации). Быстрый распаковщик тоже удалось ускорить на несколько процентов, ещё и сократив его до 229 байт, в т.ч. благодаря идеям uniabis.
Последний компактный распаковщик (88 байт): unmegalz_small.asm
Последний быстрый распаковщик (229 байт): unmegalz_fast.asm

12 комментариев

avatar
Круто! А у тебя нет свежего графика «коэффициент сжатия/скорость распаковки» посмотреть где теперь что?
avatar
Учти что график генерируется на основе старого корпуса (того же, что в 2017 году), а табличка выше — на основе нового. Я буду переходить на новый корпус из-за того, что в старом было маловато графики (где-то 20% данных) и великовата средняя длина файла, что слегка искажает результаты тестов (скажем, на старом корпусе LZSA2 слегка обходит MegaLZ по сжатию, т.к. имеет намного большее окно, а отставание на графике не так заметно из-за небольшого кол-ва графики в корпусе). С поправкой на эти моменты, вот где я сейчас:

avatar
На этом графике показаны результаты 3х распаковщиков MegaLZ — самый медленный это старый («DEC40.asm», 110 байт), совпадающий по скорости с Hrum — это новый оптимизированный по размеру (92 байта) и тот, который чуть быстрее 3*LDIR — новый оптимизированный по скорости (234 байта).
avatar
Отлично, спасибо!
avatar
Напомни, что именно является «святым граалем» твоих поисков оптимального компрессора.
Могу ошибаться, но с моей точки зрения, это поиск наиболее сильного сжатия (требование №1 к любому компрессору) в то же время при самой высокой скорости _распаковки_ на z80.
При этом запаковка на z80, как таковая, абсолютно не принимается в расчет.
Видимо, всё это для целей демо-«анимы», т.е. основанных на быстро распаковываемых данных. Подтверди, так это или не так.
Изучал ли ты успехи товарищей на других 8-битных платформах? Каковы они?
avatar
Я не считаю что всё нужно паковать одним компрессором. Есть компрессоры которые жмут хуже, но намного быстрее распаковывают; они полезны в своей нише. Есть компрессоры, которые прекрасно жмут, но распаковывают часами (см. Shrinkler на диаграмме в комментарии чуть выше).

Короче, есть некая условная грань оптимальности Парето. Как бы если ты готов затратить некое конечное кол-во вычислительных ресурсов, ты не сможешь получить сжатие выше, чем позволяет эта грань. Грань на данным момент показана на диаграмме в комментарии выше по треду. Глядя на эту грань, я выбираю себе лучший компрессор для текущей задачи. Например, для универсального сжатия в ядре демо я сейчас использую MegaLZ; LZSA2 для меня в этой роли сейчас на втором месте, из-за слегка худшего сжатия графики. Но если в демо что-то не будет успевать на стыках, я поставлю LZSA2 и решу эту проблему. В то же самое время, один из эффектов у меня сейчас в демо требует покадровой распаковки атрибутов (пикселы сделаны эффектом, а вот раскраска — анимацией). В этом случае скорость абсолютно важна, поэтому в эффекте задействован LZSA1.

Некоторые успехи товарищей на других платформах ты можешь увидеть на моей диаграмме. Если очень коротко, я протестировал дохренища всего, не думаю что много упущено. Всегда есть потенциал что-то упустить из вида; но фундаментально, на Z80, с моей точки зрения все ведущие игроки сейчас обозначены.

И, да, запаковка на Z80 представляется мне абсолютно архаичной. С моей точки зрения в ней тупо нет смысла.
avatar
Прочитал всё что ты написал, написанное очень осмысленно.
Мои мысли пока такие. Думаю что надо стремиться к тому что выбирать пакер не просто так, имея накопленные знания, а иметь практически легко доступный «интерфейс» компрессоров (а может и декомпрессоров) с тем чтобы пробовать их практически и сразу сравнить. Потому что знание это хорошо, но компрессия, штука порой непредсказуемая. Сжимаемые данные внезапно могут оказаться с какой-то совсем неожиданной спецификой, так что практика может оказаться далеко от ожидаемого, как в ту, так и в иную сторону.
Также надо исследовать пакеры на _наборах_ специфичных данных, например на спрайтах и тексте (или как насчет того чтобы паковать стрим регистров AY? :))) ). Ориентация на скорость/сжатие хорошо, но для игроделов требования более интересные. Основное добавочное требование игровых схем упаковки — это возможность распаковывать произвольные фрагменты упакованных данных, а не всё сразу и не потоково.
avatar
Относительно «демо-анимы» можно поговорить отдельно, хотя не знаю интересна ли тебе эта тема. Я лично считаю аниму просто один из приёмов в репертуаре, не главным, но безусловно полезным. Я делал демо чисто на аниме, я делал демо с элементами анимации; я не знаю всё, что закодил ты, но я смотрел Iris и я могу себе представить, что для тебя как для олдскул кодера у меня анимы очень много. Поэтому скажу так. Не всё что я делаю в своих демо основано на быстро распаковываемых данных. Но я безусловно держу эту опцию в уме и при необходимости/возможности — применяю.
avatar
Всё правильно, у меня такое же на самом деле отношение.
avatar
Немного не в тему, но интересно: является ли, например, формат pt3 оптимальным для компрессии AY-потока?
Чем проверить? (У каких компрессоров нет ограничения на длину файла? =)
avatar
Извини, пропустил вопрос. На твой вопрос нет простого ответа. pt3 разрабатывался чтобы быть достаточно компактным сам по себе, но вряд ли кто-то специально думал о том, как он будет компрессироваться. С другой стороны, я не знаю других форматов с эквивалентными возможностями, чтобы можно бы было хотя бы сконвертировать пачку файлов в конкурирующий формат и посмотреть, будет ли он лучше жаться.

Ограничения на размер файлов есть почти у всех спектрумовских пакеров. Как ты собираешься распаковывать файлы больше 64К на машине с адресным пространством в 64К и реально доступной памятью в 48К?
avatar
За прошедший год я немного улучшил оба декомпрессора. Компактный распаковщик удалось сократить до 88 байт (если у кого-то будут мысли, как его можно ещё сократить — буду очень благодарен, так как
у меня там уже начались реально неприятные оптимизации). Быстрый распаковщик тоже удалось ускорить на несколько процентов, ещё и сократив его до 229 байт, в т.ч. благодаря идеям uniabis.
Последний компактный распаковщик (88 байт): unmegalz_small.asm
Последний быстрый распаковщик (229 байт): unmegalz_fast.asm

Внимание, я немного поменял систему нумерования версий, теперь версия указана внутри файла. Поэтому по этим ссылкам всегда можно будет взять самые последние версии распаковщиков.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.