14 сентября 2003 - Shelwien

EDS: Ходят определенные слухи о твоем новом компрессоре RКС, он даже успел появиться в кое-каких тестах и, вроде бы, неплохо себя показал. Как бы на него посмотреть?

MT: Э-э... Извини, но я не собираюсь его распространять ;). Это просто "испытательный стенд" для новых алгоритмов сжатия, а не законченный продукт. Но я очень много работаю над тем, чтобы получить все-таки настоящий продукт - архиватор с графическим интерфейсом на замену rk 1.04.1. А RКС я раздал строго ограниченному кругу людей, в основном, чтобы получить информацию в виде сравнительных тестов. Надеюсь, через пару месяцев у меня все же будет альфа- или бета-версия, которую можно будет слегка распространять. Спроси снова ближе к тому времени, и тогда, может быть, я смогу тебе помочь ;).

И еще надо иметь в виду, что я пытаюсь сделать законченный коммерческий продукт - такой, чтобы люди захотели его купить. По этой причине мне приходится тратить на пользовательский интерфейс почти столько же времени, как на алгоритмы сжатия. Также меня не очень волнует, если я не №1. Все, чего я хочу, это быть к этому достаточно близко. Так что вполне вероятно, что после выпуска первой версии алгоритмы сжатия будут "заморожены", и даже если я поставлю рекорд на тот момент, то он долго не продержится. С другой стороны, мой опыт с rk свидетельствует, что и этого должно быть достаточно для большинства людей.

EDS: Увы, большинству людей достаточно zip'а ;)

MT: Ну, я и не рассчитываю на огромный рынок. Однако на жизнь надеюсь заработать ;)

EDS: ...Ладно. Надеюсь, будет отдельная консольная версия, или хотя бы какая-то поддержка командной строки в графической. А то вот compressia 1.0, скажем, практически совершенно бесполезна из-за неудобства интерфейса.

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

EDS: ...Ага. Так, значит, ты думаешь, что у PPM-компрессоров в принципе нет возможности сохранять совместимость с предыдущими версиями, продолжая развиваться, как у LZ-шных?

MT: Это непросто. В случае LZ, ты можешь легко зафиксировать декодер и работать над сжатием, т.к. алгоритм несимметричный. А с PPM так не выйдет. Если я изменю модель после релиза, но мне придется оставить и старую - для совместимости. А совместимости с будущими версиями все равно не будет.

EDS: А над подходами вроде RAR-VM, которую Рошал использует для препроцессинга, ты не задумывался?

MT: А хорошая идея... Но не думаю, что сделаю что-то такое в ближайшем будущем - у меня и так запланировано неимоверное количество других вещей.

EDS: ...Ну, тогда о другой твоей программе. Я так понял, что вместе с RКС потихоньку разрабатывается и rkau2? Дело в том, что в связи с экспериментами по сжатию geo, меня сейчас эта тема особенно интересует ;). Сможет ли новый rkau обработать массив 24-битных чисел?

MT: Алгоритм нового rkau запросто может быть расширен до 24-х или даже 32-х бит, т.к. использует плавающую арифметику с двойной точностью. Старый алгоритм был продвинутым вариантом чего-то в духе shorten. А новый использует технику адаптивной фильтрации (метод нормализованных наименьших квадратов и рекурсивный метод наименьших квадратов - RLS). Не знаю уж, как работают OptimFrog и LA - вероятно, используют каскадированные адаптивные фильтры с эмпирически подобранными параметрами. Моя же реализация основана больше на теории. Хотелось бы еще попробовать "шахматную" версию RLS (LMS) - она, вероятно, будет работать быстрее. Но сначала еще надо найти объяснение этого метода с достаточным количеством деталей, чтобы его можно было понять ;)

EDS: Но ты же не собираешься останавливаться на алгоритмах, использованных в RКС? В каком направлении планируешь экспериментировать дальше?

MT: Да, вот, думаю о комбинировании статического и адаптивного подхода. Есть надежда, что это позволит избавиться от недостатков обоих (с существенным уменьшением скорости работы, конечно ;).

Кстати, должен тебе сказать, что меня впечатлила твоя программа PPMY. На протяжении последних 3-4 лет я неоднократно пытался сделать похожий алгоритм, но и близко не получал таких результатов! ;)

Другая вещь, с которой хотелось бы разобраться - это CTW. Добавить туда что-нибудь SSE-образное и, возможно, улучшить смешивание. ...Вот взять опубликованную реализацию - они получают наилучшие результаты с использованием "оценки с нулевой избыточностью" (zero-redundancy estimator). Мне кажется, что методы типа SEE должны, по идее, гораздо лучше справляться с "проблемой нулевой частоты", чем статическая оценка. Собственно, эта же проблема много лет была в PPM, пока не начали применять SEE.

Что же касается побитового моделирования текста, то это я бы сохранил. В основном, для упрощения алгоритма, и, есть такая надежда, увеличения скорости. Я думаю, должно быть довольно легко соорудить CTW на структурах данных типа используемых в PPMD Дмитрия Шкарина, так что все будет работать достаточно быстро. Однако, поскольку CTW запатентован, то я как-то и не очень хочу это пробовать ;)

EDS: Кстати о Шкарине. Конечно же, ты знаком с его "дурилкой" и модулями seg_file, disasm32 и flt32, которые там использованы?

MT: Ага. Я как-то полистал seg_file, чтобы узнать, могу ли я применить что-то подобное. Но все-таки пока я собираюсь оставить тот метод сегментации, который уже есть в моем "максимальном" алгоритме (несмотря на то, что он обычно хуже). Хотя, я еще вернусь к этому перед релизом. Кроме того, я использую дизассемблер для обработки EXE и DLL. Однако мои методы сильно отличаются от методов Дмитрия, т.к. его алгоритмы довольно странные (не говоря о том, что их трудно расшифровать ;) и, похоже, помогают только его собственной модели. Что действительно не очень хорошо, так это что у меня нет хорошего способа определения, что является кодом, а что - нет. Именно на этом "дурилка" по большей части меня и обходит (не считая ручного подбора настроек сегментации ;). Кстати, еще одна из моих целей - по возможности автоматизировать подбор всех параметров.

EDS: Хм. А по-моему, тут нет ничего сложного ;)
1. Ты можешь сделать парсер для известных форматов исполняемых файлов - так что не будет проблем с сегментацией и определением типов сегментов.

MT: Это у меня уже есть.

EDS: 2. Раз у тебя есть дизассемблер, ты можешь применить его и посмотреть, насколько много некорректных инструкций в данном фрагменте.

MT: Система команд x86 достаточно "плотная", так что встречается не так много действительно некорректных кодов. Хотя, вероятно, я мог бы сделать это статистически, путем определения "энтропии" блоков исходя из вероятностей отдельных инструкций (по идее, простая статическая модель подойдет), и использовать что-то вроде seg_file Дмитрия...

EDS: 3. Можно просто проверять, способен ли E8-препроцессинг улучшить сжатие фрагмента.

MT: Хм. Главная проблема с сегментацией по формату - это то, что не всегда возможно найти весь код. Скажем, WCC386.EXE имеет нестандартный формат, так что оттуда можно достать только загрузчики (для DOS и OS/2), но не саму программу. Или вот DLL с MaximumCompression - там содержится много case-таблиц (списков 32-битных адресов внутри кодового сегмента), которые надо игнорировать, чтобы не испортить сжатие.

EDS: Ну, вообще-то это довольно-таки стандартный формат, Watcom W32. И весьма простой - вот, смотри, на примере WCC386:

0050 aCf             db 'CF',0,0             ; Сигнатура
0054                 dd 2200h                ; Image Start
0058                 dd 80E30h               ; Image Size (code+data+relocs)
005C                 dd 7B2ECh               ; Code+Data Size
0060                 dd 90000h               ; BSS Size (code+data+BSS+stack)
0064                 dd 2FD30h               ; Code EntryPoint
0068                 dd 10000h               ; Размер стека
006C                 dd -1                   ; Min Mem
0070                 dd -1                   ; Max Mem

И еще там много релокаций по адресам 2200+7B2EC..2200+80E30

07D4EC               dw 2144 ; количество адресов с общими битам 16..32
07D4EE               dw 0    ; значение битов 16..32
07D4F0               dw 2144 dup( ? ) ; разности между младшими словами адресов

07E5B0               dw 2151 ; количество
07E5B2               dw 1    ; старшее слово
07E5B4               dw 2151 dup( ? ) ; дельты
[...] 
08302E               dw 0    ; количество = 0 -> релокации закончились

И вот по всем адресам, собираемым из этих старших слов и разностей, прибавляется 32-битный адрес, начиная с которого загружена программа. И все. Заголовок всегда находится по смещению 0x50 в exe-файле.

EDS: Пока все. Продолжение следует. Может быть ;).