Hello, world!!!


(Последние новости - внизу ;)

08.12.2k - Вот DC-kit#1. Набор для конструирования дистансных кодеров (того, что я так называю ;). Описание на русском внутри.

22.12.2k - sh 0.02 & sh 0.02s (исходники прилагаются). Мой вариант кодировки для использования вместо base64 и прочих uue. Использует некое обобщение интервального кодирования, так что легко можно работать с произвольным подмножеством символов. В отличие от "битовых" решений, для кодирования любого символа требуется один и тот же (практически ;) объем кода, размер закодированного файла, как минимум, на 20% меньше, чем при применении base64. Что, увы, полностью компенсируется за счет "удобства" использования :(.

27.12.2k - Выложил исходники дистансного кодера: lng-dc1.

21.02.2l - huffcomp. Шимон Грабовский предположил, что encode.com - "самостоятельная" версия хаффмановского кодировщика из архиватора ESP - самый быстрый и вообще лучший, и я попытался доказать, что он был неправ. Вот исходники и экзешники для моего собственного статического хаффмановского кодировщика - уже на 30% быстрее ESP'шного, и можно дальше оптимизировать.

22.02.2l - Демо-версия CL-D 1.08+. Адаптивный арифметик (точнее, rangecoder) нулевого порядка, основанный на последнем из моих арифметических извращений. Для вычислений используется FPU, полученный код выдается dword'ами, carryless. Все очень просто, поэтому быстро, а в качестве бонуса можно использовать масштабы вплоть до 231 (MaxFreq=231).
      ARK2 "Эвристики арифметического кодирования" - статья, описывающая процесс конструирования арифметического кодировщика (и некоторую теорию), как я все это себе представляю.

24.02.2l - Получил разрешение Шкарина и выложил его C++'ные исходники, демонстрирующие использование арифметического кодирования (интервального, собственно, там субботинский carryless). Вот aridemo v0, aridemo v1 и моя мояутилитка для замера времени.

25.02.2l - Добавил скрипт для показа нижней части страницы после загрузки ;).
      Объявился еще один комплект исходников - еще одна версия шкаринского order0 - безымянная, но пусть это будет aridemo v2 ;).

27.02.2l - Все шкаринские order0-модели и три версии кодировщика (субботинская, шиндлерская, и моя) переделаны под работу с общим интерфейсом. Теперь можно #include'нуть модель и кодер на своей вкус, откомпилировать (VC/IntelC), и получить работающий кодек. Собственно, сделал я это чтобы доказать, что CL-D (мой кодер) быстрее остальных ;). Но к глубокому моему удивлению это оказалось совершенно не так :). Хотя он действительно эффективней - для Calgary Corpus шиндлерский кодер генерирует код на 1179 меньше субботинского, а мой - еще на 148 байт меньше... Но мои планы представить CL-D как лучший с любой точки зрения явно провалились ;)... возможно, удастся оптимизировать его и сравнять его скорость с целочисленными соперниками, но определенно я не смогу ускорить его _вдвое_. ...А! Чуть не забыл дать ссылку... Вот оно - aridemo 1.00.

01.03.2l - Весна :). Так что aridemo продолжают разможаться ;). Вот aridemo 1.01, содержащее несколько новых сравнительных графиков и множество изменений, главное из которых - исправление долгожданного глюка в CLD (большое спасибо А.Ратушняку за тестирование). CLD также слегка ускорен; для графиков теперь используется не полное время выполнения программ, а конкретно время кодирования / декодирования; добавлено несколько опций etc.
      И на сегодня еще не все, т.к. я решил опубликовать мою программу (RKGraph 1.06), которая мне рисует все эти графики. Она весьма "сырая", там плохо с "защитой от дурака", но работает, если вы умеете ее заставить :).

04.03.2l - Процесс идет. CLD полностью переписан во измежание дальнейших глюков - так что он теперь, собственно, даже и не "CL", на самом-то деле :). А.Ратушняк обнаружил несколько ошибок в моем "шиндлеровском" кодировщике, но я с ними еще не справился :). В.Семенюк пожелал участвовать в наших "тараканьих бегах" и предоставил собственную модель - первую с использованием бинарного дерева в этом проекте. Впрочем, он считает, что aridemo содержит слишком много лишнего, так что вот его кодировщик отдельно - вместе с текстовкой, объясняющей работу модели. Ну и aridemo 1.02 появилось, конечно :).

08.03.2l - aridemo 1.03. Доказана корректность последней версии CL-D (спасибо А.Ратушняку), "шиндлерский" rangecoder также исправлен, наконец. Кроме того, теперь есть _две_ версии CL-D - полностью на C++ и полностью (почти) на ассемблере. По-моему, интересно, что C++'ная версия с int64 кодирует на 20% быстрее ассемблерной - которая использует FPU :).

13.03.2l - Со времени моей первой удачной реализации дистансного кодирования мне хотелось изобрести подобный, но _поточный_ алгоритм. И вот он есть - Distance Mixing. С++'ные исходники прилагаются. Увы, правда, но оказалось, что этот "прямолинейный" подход работает несколько хуже, чем даже мой DC из DC-Kit (235k против 229k на book1.bwt).
Есть у кого-нибудь идеи, как его усовершенствовать? ;)

16.03.2l - Заимел идею и написал некий алфавитный сортировщик. В основном, он ориентирован на применение вместе с BWT - для переупорядочивания алфавита перед блочной сортировкой. Берет таблицу частот пар символов, сортирует колонки по возрастанию энтропии и выдает таблицу с отсортированными колонками и - в отдельном файле - использованную перестановку.

22.03.2l - После нескольких тестов и обсуждений выяснилось, что алгоритм, использованный в cnksort1 практически бесполезен :). Его применение к данным перед BWT ухудшает сжатие... и теперь я думаю, что это можно было предвидеть - нет особого смысла в сортировке просто по энтропии распределения символов-суффиксов. Практически нет корреляции между похожестью двух блоков суффиксов и их энтропий. Так что я переделал кое-что - может, оно и не помогает при блочной сортировке, но может быть использовано иначе :). Идея (возникшая благодаря Вадиму Юкину) заключалась в том, чтобы переупорядочить блоки символов в файле так, чтобы похожие фрагменты располагались рядом и получить лучшее статистическое сжатие. Это - работает! :)
(AridemoV6 сжимает book1.bwt в 326,972 байта без перестановки блоков и в 318,160 с ней (блоки по 2k), включая информацию об их порядке!)
Мне кажется, это полезнаая идея... хотя, может быть, и не с моим нынешним алгоритмом расчета оптимальной перестановки :).

23.03.2l - Вот усовершенствованная версия переупорядочивания блоков в файле - тоже медлительная, но теперь оптимизация имеет сложность O(N^3) - что сравнительно терпимо :). Заодно, теперь оно генерирует диаграммы распределения частот в данных перед и после перестановки - номер блока по горизонтали, код символа по вертикали.

16.04.2l - Потратил массу времени, пытаясь найти весовую функцию. Похоже, что оценить реальную вероятность нулевого бита при наличие _двух_ (возможно, различных) оценок p1 и p2, данных двумя моделями, совсем несложно. Есть общеизвестное предположение, что в таком случае должно использоваться значение, вычисляемое по формуле pm = w1*p1+w2*p2, где w? - веса моделей. Если обе модели считать равноценными, то это будет просто средняя вероятность. Но вместо этого мы можем использовать p? в качестве контекстов и собрать реальные частоты битов, соответствующих каждой паре {p1;p2}. Так и выяснилось, что весовая функция далека от простого среднего. Но все же она довольно гладкая, хотя я и обломался подобрать функцию, дающую подобные результаты :(. Может, вам повезет ;).
Вот комплект материалов, полезных для этого - программа для сбора статистики, кодер, показывающий, что среднее - не лучшее etc.

04.05.2l - Только что переписал на Си свою схему контекстного смешивания - PPM211. Медленная штука, но очень простая, особенно в сравнении с PPMd :). Хуже относится к бинарникам, но тексты c текстами справляется несколько лучше, чем PPMd v.F. Сжимает book1 в ~210.9k. ...И расжимает :).

14.05.2l - PPM211 - фигня, поскольку основывается на некой эвристической "магии". Так что я только что разработал новый кодировщик, гораздо более логичный по натуре, чем предыдущий. Ну, случайно он оказался и более эффективным, но я этого не ожидал :). Так что вот PPM210 - моя новая модель, в данный момент дающая 209,890 на book1.

22.05.2l - Надеюсь, это последний апдейт; модель опять полна мистики :). Хотя 207,879 на book1 это уже не так плохо... Еще соорудил кое-какой workaround для избежания генерации IntelC/VC слишком медленного кода в некоторых случаях - так что теперь оно на 20% (или даже больше) быстрее.

31.05.2l - Hopes are never true :) ...Так что вот еще кое-что. Вроде как доделанная версия, более стабильная на бинарниках. Кроме того, я добавил несколько опций для ограничения максимального порядка и объема используемой памяти. Сжимает book1 в 207,379.

02.06.2l - И еще одна версия, слегка усовершенствованная. Работает несколько быстрее и большинство файлов сжимает лучше, чем раньше, хотя не все, увы :). 206,991 на book1.

04.05.2002 - Нашел место для очередного "зеркала". Тут правда, меня заставили все на русский перевести, но, хотя бы, может никто теперь на тормозизм серверов не будет жаловаться ;).
      Со времени последней "новости" прошел почти год - неудивительно, что успело появиться кое-что еще. Просто лень заливать на сайты было - а теперь такой повод ;). Но даты я все равно не помню, так что все скопом:
1) ParCoder
"Параллельный" арифметический кодировщик. Это иногда возникает у некоторых людей идея приспособить векторные системы команд для компрессии, а "аксакалы", мылом и в эхе им разъясняют степень их ламеризма. Особенно в этом Булат Зиганшин преуспел ;). ...А я смотрел на это, смотрел... пока от В.Семенюка то же самое не услышал, и тут уж не выдержал ;).
В общем, "одновременно" работает несколько инстансов кодека, каждый из которых работает с собственным файлом, но пишут/читают они все один поток. Факт тот, что эти инстансы легко расселить в отдельные thread'ы и сделать реально параллельными. А если еще напрячься - то и посчитать арифметику сразу для пары символов при помощи MMX. Практического смысла в этом мало, но возможность есть.
И нечего со мной спорить! ;)
2) mCTW
Обчитавшись Садакане, решил попробовать и я реализовать байтовый CTW. Ничего хорошего из этого не вышло, как видно. ...Впрочем, 288k на book1 за 12 часов - может, это ничего? %)
3) Enthropy Logarithmic-Scale Coder
Ну, Ратушняк давно всех ELS'ом запугивал. Но когда у меня кто-то спросил, знаю ли я, что это такое есть... пришлось выяснять. Оказалось - достаточно логичная модификация арифметического кодирования в целях избежания умножений, предлагаемая некоторыми в качестве коммерческой замены перезапатентованному Q-Coder'у. Я от'OCR'ил их исходники из pdf'а, заставил работать, и сравнил с aridemo. Душераздирающее зрелище этот ELS, я вам скажу ;).
4) Coderz 6a
Устал я aridemo апдейтить, честно. Ну какой интерес вылизывать C++'ные классы и выкладывать узоры из кодеров и моделей, когда PPM некопан? ;) Но тут такое дело: изобрелась совершенно новая (и хорошая) разновидность carryless (в процессе переписки с Игорем Павловым, кажется). Скорость кодирования - как у обычного carryless, декодирования - как у обычного rangecoder'а, такой вот мутант. Пришлось релизить в упрощенном варианте ;).
5) PPMY 3c
Неожиданно обнаружил, что PPMY не такой, как на сайте
А, вспомнил! - я там работу с табличками параметров сделал читабельней (хотя и чуточку медленней). Заодно, видимо, еще их пооптимизировал - текущий результат, во всяком случае, 206,808 на book1.
6) FLT32
Это опять-таки в процессе обсуждения препроцессинга экзешников с Игорем Павловым у меня сотворилось вот такое, ну а у Игоря, соответственно, BCJ2. У меня, правда, декодер безнадежно отстал от кодера в процессе опробывания вариантов, так что он не прилагается. Но сделать его несложно. Зато последний ppmonstr с его помощью сжимает известный wcc386 до 231,738 байт (или 232,109 без pop reversing, которое чаще вредит ;).
А еще есть хорошая штука PEUtils, которая разбирает PE'шники на секции, а потом опять собирает. Вот ежели PE'шник разобрать на секции, а потом те из них, которые кодовые, обработать нап... то есть FLT32 ;), то получается особенно хорошо.

Не уверен, что это все, но что-то я уже устал ;). Вроде... ой, чуть самое главное не забыл ;).

7) sUnrar
Это попался мне пару месяцев назад один архивчик rar'овский, запароленный, который очень открыть хочется ;). Ну и скорость работы лидеров в области "восстановления забытых rar'овских паролей" - Crark и RPC меня как-то не устроила... Так что я взял unrarsrc и... обломался. Оказалось, без BorlandC его скомпилить не так уж просто %). Поэтому вот, получился такой рип unrarsrc - 23k исходников вместо 138k, компилится VC/IntelC (отчего существенно быстрее работает ;). Можно изготовить SFX размером 7k, если upx'ом попаковать. Имхо полезно. Последняя версия, правда, вроде как вот эта, но она принципиально не создает подкаталогов и плохо обходится с архивами - т.е. хранит все распакованные файлы в памяти ;). Ну, промежуточная такая версия перед переходом к собственно кракеру паролей. Зато исходников уже всего 18k ;) и еще кое-что полезное в текстовках написано...
8) RarPass
Ну и собственно "вспоминатель забытых паролей" для rar2. В принципе, он еще довольно сырой, я над ним еще работаю... но скорость-то уже на 50% выше, чем у конкурентов. Точнее, вообще несравнимо выше - т.к. у меня скорость от длины пароля странным образом не зависит ;). По причине "сырости" еще есть масса ограничений - правильная работа обеспечивается только для файлов, запакованных без использования "мультимедийного" алгоритма. Кроме того, фиксирован алфавит - 0123456789abcdefghijklmnopqrstuvwxyz. Но все это не проблема, т.к. прилагаются исходники и описание нужной части формата архива. Да и вообще, мне кажется, что переборщик паролей особым "интеллектом" снабжать не следует. Он будет быстрее работать, если нужные параметры подставить непосредственно в исходники и откомпилировать нормальным компилятором.

Уф! Не, на сегодня все ;)

09.05.2002 - Новая версия rarpass. Еще 10% скорости.

14.05.2002 - Перекомпилил rarpass со статической линковкой. Скорость стала на 45p/s больше. Парадоксально, но факт ;). Ну, пришлось под это дело кое-какие косметические изменения в архив внести - чтоб на XX тянуло %).

Также вот ark2 в html и незапакованный - возможно, так его будет проще читать ;). См., кстати, там, в "библиографии", теперь ссылки нормальные %).
Н-да. Раз уж пошла такая пьянка, то можно и еще что-нибудь из старенького выложить. Вот, скажем, bwt1... и shc1 (за конвертирование которого в html большое спасибо Кириллу Волошину ;).

18.01.2003 - Уже и год сменился, а я все страничку ленюсь обновить. Ну ничего, теперь вот повод возник ;). В последнее время почему-то часто стали возникать вопросы, связанные с
sh 0.02 и реализованным там методом кодирования с использованием заданного набора символов. Но ассемблера почему-то никто не понимает ;). Пришлось все-таки сделать сишный вариант (для разнообразия - с не-carryless'ным кодером ;), Итак: MarcDemo.

01.03.2003 - PiLabs, где хостилось мое самое первое зеркало (и где до сих пор лежала большая часть старых файлов), склеил ласты. Оказывается. Но теперь я это заметил и принял к сведению. Кроме того, за прошедшее время пришлось выложить несколько файлов, на которые я собрался с силами дать ссылку:
1. Работа над MarcDemo вызвала несколько новых идей по реализации rangcecoder'ов, что привело к созданию нового апдейта Aridemo. Так что теперь кроме coders6a имеется еще и coders6b.
2. Сергей Оснач зачем-то приделал к PPMY коррекцию вероятности самого вероятного символа (MPC) при помощи Secondary Symbol Estimation (SSE), что привело к некоторому повышению эффективности, особенно на бинарниках, а также появлению новой версии PPMY.
3. И еще мне захотелось поиметь возможность отображать в графическом виде разную статистику, хотя бы и при работе консольного компрессора. В результате получился класс, который поддерживает картинку в окне и позволяет легко ее модифицировать. Пример использования находится здесь ("оконный" класс содержится в paint.inc). Идеи на тему того, какую реально полезную статистику можно отображать в таком виде (два измерения, яркость, цвет) ожидаются здесь ;-)
4. Еще есть BFA, но это слишком большая тема, когда-нибудь в следующей жизни.


Links Downloads