Сжатие и упаковка. hrum3.5, hrust1, hrust2, laser compact x.x.

[Hrumer]

Добрый вечер!

В День Дурака хотелось бы открыть свою новую тему, в которой осветить особенности, хитрости, и прочие радости сабжа, тем более что, в общем то и обещал.

Алгоритмы выдуманные(в т.ч. велосипедные), реализованные, не реализованные и непридуманные(пока еще). Буду пополнять тему, а пока начну с краткого. Вдруг кому пригодится. Буду рад, если кто поделится мыслями.

Совершенно ясно, что писатели пакеров-депакеров, архиваторов берут, придумывают всякие эммм... хорошие вещи, и никому ничего не говорят. Но бывают и говорят, но очень уж редко. Или того хуже, патентуют . Но здесь не об этом. Заглянете в какой архиватор(исходники), а там такого напридумано... И никто ниче не пишет, что такого придумал. Высшая математика, теоремы, теория вероятностей и прочее...


Для сабжа все проще! Никакой вышки. 15-19 лет прошло, можно кое что вспомнить

Итак, общее для сабжевых пакеров: в них не все коды задействованы... Почему? Инфу выложу позже...

Для затравки, с хруста1:
Где то в середине 2013г понял, что кое чего пропустил в формате хруста1. Открыл записи, и правда, ага. Светокопию где была зарыта собака выложу завтра. Или в ближайшие полгода. Шутка. Записи 96-97 года. Хех.

Итак, в хрусте1, помимо обычного LZ применяется еще кодирование вида AxC, т.е. такого, когда при ранее встреченной последовательности ABC вдруг(ну надо же!) встречается AEC. Берем, и вместо неё пишем код особый, далее расстояние, а потом и символ "Е". Это позволяет на уж совсем вроде бы непакующихся данных кое что сжимать.

Дистанция при этом кодировалась вариантами 16+32+32-1 = 79. т.е. от 1 до 79. Дистанциям от 1 до 16 присваивался код более короткий. После какого то ветвления (т.е. префикса), в виде 4 бит. Однако, такую же последовательность, AEC, при ранее встреченной последовательности ABC на дистанции от 1 до 8 байт можно было закодировать по другому, в виде <LEN=1, DIST=1..8>. В результате последний вариант проверялся первым, и кодирование типа AxC для дистанций 1..8 не применялось. А значит, для кодирования дистанций для случая 1..16, а фактически для 9..16 хватало бы 3 бит, а не 4. Что привело бы к повышению сжатия.

Продолжу не 1 апреля...

[Advertiser]

[alone]

Приклеивать к распаковываемому блоку слева депакер. Т.е. сжатие с опорой на код депакера. (ПЗУ использовать нельзя - оно у всех разное.)

Пробовать паковать не только вперёд, но и назад, и выбирать лучший вариант из двух.

[Hrumer]

Приклеивать к распаковываемому блоку слева депакер. Т.е. сжатие с опорой на код депакера. (ПЗУ использовать нельзя - оно у всех разное.)

Пробовать паковать не только вперёд, но и назад, и выбирать лучший вариант из двух.

Зачётный словарь! Это свежо и круто! Паковать и из двух направлений выбирать - это да, слыхал, тоже хорошо.

Про варианты laser compact 6 и 7 и hrust3 застолблю, есть интересная инфа, выложу позже.

[alone]

Ещё можно посмотреть, какие литералы не используются, и засунуть на их место контрольные коды.

[introspec]

Приклеивать к распаковываемому блоку слева депакер. Т.е. сжатие с опорой на код депакера. (ПЗУ использовать нельзя - оно у всех разное.)

Пробовать паковать не только вперёд, но и назад, и выбирать лучший вариант из двух.

Опасные идеи! Первая приведёт к тому, что мелкие правки распаковщика могут испортить сжатый заранее блок. Кроме того, они привяжут сжатый блок к конкретному распаковщику, в то время как в наше время очень часто бывает удобным именно что выбирать распаковщик из нескольких возможных.

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

[alone]

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

Использование общего распаковщика на несколько блоков - это одна опция, а затачивание распаковщика под конкретный блок - другая. Просьба не путать.

[introspec]

Использование общего распаковщика на несколько блоков - это одна опция, а затачивание распаковщика под конкретный блок - другая. Просьба не путать.

Я не путаю. Я прошу не делать это магистральным путём развития.

[Hrumer]

Я не путаю. Я прошу не делать это магистральным путём развития.

Не боись, тут люди в ветке тему понимают, что для чего.

В депакере лазеркомпакта, я делал еще короче депакер, но выкинул, ибо очень тормозно распаковывает. А надо было приложить вариант, вдруг кому пригодилось бы. Так и тут. Вдруг(!) кому пригодится.

[alone]

А как же паковать 1K/4K интры, если не делать это магистральным путём развития?

---------- Post added at 20:35 ---------- Previous post was at 20:34 ----------

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

[introspec]

А как же паковать 1K/4K интры, если не делать это магистральным путём развития?

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