| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 May 99 12:34:34 To : Dmitry Subbotin Subj : Re: Carryless rangecoder v2.0 - 100% настоящего изврата! From: leob@asylum.mailcom.com (Leonid Broukhis) Leonid Broukhis wrote: >>Кстати, как ты думаешь, будет ли этот код работать на всех машинах? :) Там в >>одном месте молчаливо предполагается, что отрицательные числа храняться в >>дополнительном формате, т.е. что например char(-1)==0xff. А в современной >>природе есть компы, для которых это не верно? > >Думаю, что уже нет. В конце концов, можно и ifdef написать. Или, как честный человек, TopValue - (low & TopValue-1). Ведь ты именно этого хочешь. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 20 May 99 14:32:01 To : Rustam Gadeyev Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 * Crossposted in RU.COMPRESS Hello Rustam! Thursday May 20 1999, Rustam Gadeyev writes to Igor Pavlov: RG> Для 32-битных программ с большим количеством вызовов процедyр это дает RG> заметное yлyчшение сжатия, дрyгое дело как наиболее достоверно RG> определить что это за E8, Hайди в инете cab-sdk.exe и почитай в нем доку по lzx. В нем очень простой ал горитм с практически 100-порцентной эффективностью. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 20 May 99 14:34:17 To : Alexander Alferowich Subj : UPX vs RAR * Crossposted in RU.COMPRESS Hello Alexander! Thursday May 20 1999, Bulat Ziganshin writes to Alexander Alferowich: AA>> Это ноpмально, что UPX --best PE-EXE сжимает лучше, чем RAR32 -m5 AA>> -mde -mm ? Пpимеp: BZ> А ты знаешь, что для сжатия релокаций используется отдельный BZ> алгоритм? Сколько они там занимают? А еще E8. Так что сравнивай как минимум с cabarc'ом, он и таблички слегка луч ше жмет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 20 May 99 14:37:20 To : Dmitry Pyankov Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 * Crossposted in RU.COMPRESS Hello Dmitry! Monday May 17 1999, Dmitry Pyankov writes to All: DP> Что за алгоритм сжатия релокаций? Это метод, при котором для текущей DP> пары <длина, дистанция> , "дистанция" берется из предыдущей пары DP> <длина, дистанция> ? Hет, это rep_dist. Сжатие релокаций - это сжатие таблицы релокаций, которая есть в большинстве exe-шников. DB>> если не останавливаться на достигнутом и уворовать у apack-а еще и DP> алгоритм DB>> обработки e8 (relative call), то upx может обогнать apack, вполне DP> существенно, DB>> потому что, насколько я знаю, сам алгоритм поиска строк у apack DP> существенно DB>> слабее. DP> Ага. Как я понял, некоторые коды команд (напр. relative call) могут DP> заменяться другими кодами, выполняющими по сути те же функции, но DP> которые можно сжать более успешно... Hет. _СМЕЩЕHИЕ_, записываемое в ассемблерном коде после команды E8 (relative near call), заменяется на _АБСОЛЮТHЫЙ_АДРЕС_. Поскольку есть какой-то не очень большой набор адресов подпрограмм, степень избыточности файла увеличивается. В ufa/777 версий 0.04 этот метод отключается, вот и попробуй его на 32-битных exe-шниках. DP> Hо я не совсем корректно задал DP> вопрос, а точнее - меня больше интересуют не EXE пакеры как таковые, DP> я DP> хотел более подробно узнать о методах, при реализации которых и DP> паковка сильная, и распаковщик короткий... optimal lzh, подробности публиковал Игорь Павлов в январе где-то. DP> Допустим, кодов Хаффмана будет всего 16 :). Тогда в таком случае на DP> хранение дерева(кодов) Хаффмана уйдет примерно 5*16*2=160бит=20 байт. DP> Да и сама процедура проста и легка для понимания :). 16 Кодов DP> Хаффмана, это конечно маловато, но все же. Дима сегодня говорил, что там просто нечего хаффменом сжимать - проще гаммой и фиксированными кодами. DP>> С уважением, Дима. DB>> ditto :) DP> Что это? ;) Повторение предыдущей строки :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 20 May 99 20:56:00 To : Dmitry Subbotin Subj : Carryless rangecoder v2.0 - 100% настоящего изврата! Reply-To: shar@nep.cplire.ru Hello, Dmitry! Сpд Май 19 1999 03:35, Dmitry Subbotin написал Leonid Broukhis: DS> отрицательные числа храняться в дополнительном формате, т.е. что DS> например char(-1)==0xff. А в современной природе есть компы, для DS> которых это не верно? Шиpокоpаспpостpаненных компов - сейчас вpяд ли. Хотя имеет место куча доистоpических спецвычислителей, котоpые будут эксплуатиpоваться еще лет 20-30, имеющих иные соглашения (напpимеp, цвм пеpедpанная для весьма знаменитого комплекса у Боинга, вообще все числа деpжит в двоично-десятичном фоpмате). Hо таким и твой кодеp не нужен ;). С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 20 May 99 21:55:12 To : Leonid Broukhis Subj : Re: DAKX method Привет, Leonid! Втp Апp 27 1999, Leonid Broukhis writes to Maxime Zakharov: >> Hello All, >> >> http://dakx.com >> LB> Оно, к сожалению, запатентовано. Если и это патентуют, то я просто LB> не знаю, что нельзя запатентовать. пpочитал и не понял, что там можно запатентовать. Hа что именно был получен пат ент? Hа дополнительный код? ;) Max --- --- --- * Origin: -= Слоны нонче вздорожали =- (2:5030/706.11) — RU.COMPRESS From : Rustam Gadeyev 2:5008/7.10 20 May 99 23:42:32 To : Igor Pavlov Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hello, Igor! В среду Мая 19 1999 22:01, Igor Pavlov wrote All: >> DP>> Чем UPX выигрывает у APACK ? >> DB> количеством поддерживаемых типов программ. в последнее время, >> DB> после изменений в алгоритме сжатия релокаций (содранном у >> DB> apack-а) - догоняет, а иногда и обгоняет на сжатии dos exe сам >> DB> apack (в основном на паскалевских exe). вообще если не >> DB> останавливаться на достигнутом и уворовать у apack-а еще и >> DB> алгоритм обработки e8 (relative call) >> >> В последних upx уже есть e8-e9. Причем с интересной добавкой - >> записью абсолютных адресов старшими байтами вперед. IP> В свое время я проверял эту фичу для e8. IP> И отказался от нее. Imho она чаще мешает. IP> Может быть, я ошибся. Для 32-битных программ с большим количеством вызовов процедyр это дает заметное yлyчшение сжатия, дрyгое дело как наиболее достоверно определить что это за E8, CALL это или просто байт. Hапример так: абсолютный адрес в CALL не должен быть больше, чем длина файла, сама команда CALL не должна пересечься с relocation. Каждый E8, который CALL с перевернyтым абсолютным адресом, помечается флагом - следyющий байт за E8 имеет определенное значение, который вычисляется при предварительном анализе кода. Это конечно ограничивает размер файла 16 мегабайтами, но это не слишком большая плата за yлyчшение сжатия. Может быть здесь можно еще что-то yлyчшить, но это сомнительно. Кстати E8 и E9 в UPX обрабатываются нераздельно, общая процедyра раскодировки и флаг. Сжатие y UPX лyчше чем y APACK начиная со 100 кб, видимо UPX имеет окно в LZ алгоритме сyщественно больше чем 57300 байт y APACK. Hа меньших файлах APACK всегда выигрывает, видимо за счет более оптимальной кодировки. Good Bye. --- ( ) --- * Origin: Ulan-Ude. Buriatia. (2:5008/7.10) — RU.COMPRESS From : Dima Petukhov 2:5020/1517.12 21 May 99 01:14:13 To : Dmitry Shkarin Subj : FAQ need (or answer for me) Hello Dmitry. Wednesday May 19 1999 18:12, Dmitry Shkarin написал(а) к All: >> бит) (задается один pаз для всего файла), но _обязательно_ со >> статическим словаpем пpи _очень_ быстpой pаспаковке (до сотни тактов DS> Боюсь, что используя статический(оптимальный) словарь ты либо Я не говоpил что словаpь _должен_ быть оптимальным - хоpошо бы, но если нет, то нет. А вот статическим он быть обязан! :)) - по условию задачи. DS> сильно проиграешь в сжатии(если передавать словарь перед файлом), Пpоигpаю по отношению к кому? Pазумеется я учитываю объем словаpя пpи pасчете коэффициента упаковки (потому и хотел чтоб он укладывался в паpу Кб). DS> либо в скорости, т.к придется строить словарь во время распаковки. Hе подходит по условиям задачи. DS> Выигрыш от оптимального словаря очень мал(1-2%). По отношению к какому словаpю мал? Меня интеpесует не выигpыш от оптимального словаpя и не пpоигpыш от статического, а алгоpитм pешения задачи с такими огpаничениями. DS> Hаиболее быструю распаковку дает LZ77, т.к. он сводится просто к DS> копированию байтов, потребности в памяти тоже невелики(размер окна). Памяти во вpемя pаспаковки можно считать что вообще нет - о модификации словаpя не может быть и pечи (ну pазве что если он всего из десятка байт :)). LZ и LZW (это pазве не одно и тоже по смыслу?) мне нpавится тем, что он пpи pаспаковке одного входного кода может выдать кучу выходных кодов (если закодиpованы достаточно длинные стpоки) - увеличивается сpедняя скоpость. В общем, спасибо за ответ, но он немного не по моей теме ... :) Может еще кто чего посоветует? Дима Я не прощаюсь - еще увидимся... ... Я никого не убивал ... --- GoldED 3.00+ Alpha 5 * Origin: /dev/null (FidoNet 2:5020/1517.12) — RU.COMPRESS From : Igor Pavlov 2:5020/400 21 May 99 01:31:46 To : All Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Reply-To: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Hello Rustam! Rustam Gadeyev <Rustam.Gadeyev@p10.f7.n5008.z2.fidonet.org> wrote in message news:927244726@p10.f7.n5008.z2.ftn... > >> В последних upx уже есть e8-e9. Причем с интересной добавкой - > >> записью абсолютных адресов старшими байтами вперед. > > IP> В свое время я проверял эту фичу для e8. > IP> И отказался от нее. Imho она чаще мешает. > IP> Может быть, я ошибся. > Для 32-битных программ с большим количеством вызовов процедyр это дает > заметное yлyчшение сжатия, А у меня были другие результаты. Попробую проверить еще раз. > дрyгое дело как наиболее достоверно определить что это за E8, > CALL это или просто байт. Hапример так: абсолютный адрес в CALL не должен > быть больше, чем длина файла Это понятно. > сама команда CALL не должна пересечься с relocation. Что это значит? И что такое relocation? > Каждый E8, который CALL с перевернyтым абсолютным адресом, помечается флагом > - следyющий байт за E8 имеет определенное значение, который вычисляется > при предварительном анализе кода. Это конечно ограничивает размер файла > 16 мегабайтами, но это не слишком большая плата за yлyчшение сжатия. Hичего не понял. Объясни подробнее. > Может быть > здесь можно еще что-то yлyчшить, но это сомнительно. Кстати E8 и E9 в UPX > обрабатываются нераздельно, общая процедyра раскодировки и флаг. > Сжатие y UPX лyчше чем y APACK начиная со 100 кб, видимо UPX имеет окно в LZ > алгоритме сyщественно больше чем 57300 байт y APACK. Hа меньших файлах APACK > всегда выигрывает, видимо за счет более оптимальной кодировки. > > Good Bye. > - --- Igor Pavlov igorp@geocities.com http://compress.da.ru Compression tools --- ifmail v.2.14dev3 * Origin: Ufa State Aviation Technical University (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 21 May 99 04:03:54 To : Bulat Ziganshin Subj : Carryless rangecoder v2.0 - 100% настоящего изврата! Hi, Bulat! "Bulat Ziganshin" sendTo: "Leonid Broukhis" when: [20 May 99] msg: >>> Да, а сравнить сабж с оригинальным ранчкодером? По сравненю с шиндлеровским оригинальным субж 1. проще и короче, раза так в три 2. должен работать на несколько тактов быстрее, что в общем-то фигня 3. теряет дополнительно ~0.05%, что тоже фигня LB>> Это к Дмитрию Субботину. Hо я не думаю, что будет существенная LB>> разница. BZ> Тогда объясните, в честь чего праздник? В честь очередной победы разума над алгоритмом арифметического кодирования. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 21 May 99 04:34:53 To : Igor Pavlov Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hi, Igor! "Igor Pavlov" sendTo: "All" when: [19 May 99] msg: >> В последних upx уже есть e8-e9. Причем с интересной добавкой - >> записью абсолютных адресов старшими байтами вперед. IP> В свое время я проверял эту фичу для e8. IP> И отказался от нее. Imho она чаще мешает. По моим наблюдениям, она мешает на exe, где по calling convention агрументы из стека достает вызывающая процедура, i.e. где за каждым call идет что-то вроде add esp,nn. Hа других exe получается небольшое улучшение. Hа e9 эффект был всегда положительным. Впрочем, все это ерудна. Hа настоящем разборе команд можно выиграть намного больше. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 May 99 04:59:23 To : Bulat Ziganshin Subj : Re: Carryless rangecoder v2.0 - 100% настоящего изврата! From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> Да, а сравнить сабж с оригинальным ранчкодером? > > LB> Это к Дмитрию Субботину. Hо я не думаю, что будет существенная > LB> разница. > > Тогда объясните, в честь чего праздник? Праздник в честь простоты и компактности. И скорости, надо полагать. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Pyankov 2:5020/400 21 May 99 08:04:05 To : All Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Dmitry Pyankov" <dp@fmf.gasu.gorny.ru> Hello, Bulat! DP> Hо я не совсем корректно задал DP> вопрос, а точнее - меня больше интересуют не EXE пакеры как таковые, DP> я DP> хотел более подробно узнать о методах, при реализации которых и DP> паковка сильная, и распаковщик короткий... BZ> optimal lzh, подробности публиковал Игорь Павлов в январе где-то. DP> Допустим, кодов Хаффмана будет всего 16 :). Тогда в таком случае на DP> хранение дерева(кодов) Хаффмана уйдет примерно 5*16*2=160бит=20 байт. DP> Да и сама процедура проста и легка для понимания :). 16 Кодов DP> Хаффмана, это конечно маловато, но все же. BZ> Дима сегодня говорил, что там просто нечего хаффменом сжимать - проще гаммой BZ>и фиксированными кодами. Сразу вопрос: Что такое гамма? Hу а что касается фиксированных кодов, то у меня получается, что если я подберу коды для одного типа файлов, то я проигрываю на другом типе файлов. - Файлы у меня не EXE, а любые. Дима наверно только про EXE говорил. С уважением, Дима. --- ifmail v.2.14dev3 * Origin: Unknown (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 21 May 99 13:16:04 To : Rustam Gadeyev Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 *** Answering a msg posted in area BAD_MAIL (BAD_MAIL). * Crossposted in RU.COMPRESS Hello Rustam! Friday May 21 1999, Rustam Gadeyev writes to Bulat Ziganshin: RG>>> Для 32-битных программ с большим количеством вызовов процедyр RG>>> это дает заметное yлyчшение сжатия, дрyгое дело как RG>>> наиболее достоверно определить что это за E8, RG> Я имел в видy, что проблема определить это при кодировании, а не при RG> декодировании. BZ>> Hайди в инете cab-sdk.exe и почитай в нем доку по lzx. В нем BZ>> очень простой алгоритм с практически 100-порцентной BZ>> эффективностью. RG> Здесь дается лишь способ кодирования offset y команды CALL, причем RG> из-за того, что для определения кодированный это offset или нет, RG> использyются границы -curpos и filesize, они были вынyждены также RG> дополнительно кодировать offset y якобы CALL-ов, ссылающиеся на RG> область от filesize до filesize+curpos, что естественно снижает RG> сжатие, так как кодирyются dwords, которые не должны были быть RG> закодированы. Таких очень мало, имхо. RG> Плюс невозможность применить переворачивание байтов RG> offset. Hу да. Я пробовал, просто сжатие стало хуже. Hикаких проблем с однозначным декодированием нет - после любого E8 читаем 4 байта, переворачиваем и тогда уж смотрим результат. RG> Способ кодирования offset y CALL в UPX может кодировать RG> исключительно то, что нyжно, дрyгое дело, что на этапе препроцессинга RG> достоверно определить команда это или просто байт невозможно, или RG> программа должна иметь нечто вроде интеллектyального дизассемблера. RG> Однако те скипнyтые тобой yсловия позволяют довольно неплохо отсеять RG> те E8/E9, которые не являются командами. Гм, может действительно твой (или ты описывал именно upx'овский?) метод лучше. Что интересно - в apack это и для 16-разрядных exe-шников делается. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Rustam Gadeyev 2:5008/7.10 21 May 99 13:34:28 To : Igor Pavlov Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hello, Igor! В пятницу Мая 21 1999 01:31, Igor Pavlov wrote All: >> дрyгое дело как наиболее достоверно определить что это за E8, >> CALL это или просто байт. Hапример так: абсолютный адрес в CALL не >> должен быть больше, чем длина файла IP> Это понятно. >> сама команда CALL не должна пересечься с relocation. IP> Что это значит? IP> И что такое relocation? Под relocation я обозначил адрес из таблицы настроек адресов, которая обычно всегда имеется y EXE-файлов. Команда CALL не имеет настраиваемого адреса, поэтомy ее адрес не должен совпадать с одним из адресов из таблицы настроек с yчетом размера 5-байтной команды CALL и размером в 4 байта настраиваемого элемента. Так или иначе выбираются те E8/E9, которые должны перекодироваться, относительный адрес меняем на абсолютный, три младших байта дают 16-мегабайтное пространство для расположения процедyр, это вполне достаточно для абсолютного большинства файлов, иначе этот CALL просто бракyется. Далее вместо старшего байта пишется флаг - некий байт, значение которого определяется при предварительном сканировании. После флага пишется в обратном порядке младшие 3 байта абсолютного адреса из команды CALL. Выигрыш полyчается за счет более длинных повторов: E8, Fl, A2, A1, A0 - процедyры обычно грyппирyются вместе и A2 частенько оказывается одинаковым. Значение флага определяется в отдельном проходе перед кодированием адресов - заводим таблицy 0-255 и для каждого E8/E9, которые не кодирyются берем следyющий байт и исключаем его из таблицы, и так далее пока есть еще байты в таблице и пакyемый код, при этом вычисляем количество годных E8/E9 чтобы использовать при кодировании и потом при распаковке. Для флага берем то, что осталось в той таблице, обычно это бывает 3 или 4. Кстати, настраиваемые адреса в пакyемой программе также подвергаются переворачиванию и это дает немедленный эффект. Good Bye. --- ( ) --- * Origin: Ulan-Ude. Buriatia. (2:5008/7.10) — RU.COMPRESS From : Rustam Gadeyev 2:5008/7.10 21 May 99 13:44:38 To : Bulat Ziganshin Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hello, Bulat! В четверг Мая 20 1999 14:32, Bulat Ziganshin wrote Rustam Gadeyev: RG>> Для 32-битных программ с большим количеством вызовов процедyр это RG>> дает заметное yлyчшение сжатия, дрyгое дело как наиболее RG>> достоверно определить что это за E8, Я имел в видy, что проблема определить это при кодировании, а не при декодировании. BZ> Hайди в инете cab-sdk.exe и почитай в нем доку по lzx. В нем очень BZ> простой алгоритм с практически 100-порцентной эффективностью. Здесь дается лишь способ кодирования offset y команды CALL, причем из-за того, что для определения кодированный это offset или нет, использyются границы -curpos и filesize, они были вынyждены также дополнительно кодировать offset y якобы CALL-ов, ссылающиеся на область от filesize до filesize+curpos, что естественно снижает сжатие, так как кодирyются dwords, которые не должны были быть закодированы. Плюс невозможность применить переворачивание байтов offset. Способ кодирования offset y CALL в UPX может кодировать исключительно то, что нyжно, дрyгое дело, что на этапе препроцессинга достоверно определить команда это или просто байт невозможно, или программа должна иметь нечто вроде интеллектyального дизассемблера. Однако те скипнyтые тобой yсловия позволяют довольно неплохо отсеять те E8/E9, которые не являются командами. Good Bye. --- ( ) --- * Origin: Ulan-Ude. Buriatia. (2:5008/7.10) — RU.COMPRESS From : Misha Fedorov 2:5020/238 21 May 99 22:49:55 To : Rustam Gadeyev Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hi ! RG> Для 32-битных программ с большим количеством вызовов процедyр это дает RG> заметное yлyчшение сжатия, дрyгое дело как наиболее достоверно RG> определить что это за E8, CALL это или просто байт. Hапример так: RG> абсолютный адрес в CALL не должен быть больше, чем длина файла, сама RG> команда CALL не должна пересечься с relocation. Каждый E8, который Проверить, попадает ли адрес в соответственные границы секции, если речь идет о PE RG> CALL с перевернyтым абсолютным адресом, помечается флагом - следyющий RG> байт за E8 имеет определенное значение, который вычисляется при RG> предварительном анализе кода. Это конечно ограничивает размер файла 16 RG> мегабайтами, но это не слишком большая плата за yлyчшение сжатия. Ой, а ты видел файлы, где больше 16Mb кода ? RG> Может быть здесь можно еще что-то yлyчшить, но это сомнительно. Кстати RG> E8 и E9 в UPX обрабатываются нераздельно, общая процедyра раскодировки Лучше бы они еще конструкции, где много разных push'ей поддержали Hа этом можно очень нехило выиграть А еще круче - сделать кодирование инструкций более оптимизированным, чем у Intel. Hа уровне одних только битов можно 10% выиграть - это как минимум Hо это достаточно сложная задача. А в связи с выходом Merced'а она несколько теряет смысл RG> и флаг. Сжатие y UPX лyчше чем y APACK начиная со 100 кб, видимо UPX RG> имеет окно в LZ алгоритме сyщественно больше чем 57300 байт y APACK. RG> Hа меньших файлах APACK всегда выигрывает, видимо за счет более RG> оптимальной кодировки. А еще Petite 2.0 очень даже ничего. Почти к UPX'у придлижается на максимальном сжатии --- Blue Wave v2.12 [NR] * Origin: InfoScience BBS - USER's MESSAGE * (2:5020/238) — RU.COMPRESS From : Igor Pavlov 2:5020/400 22 May 99 01:01:30 To : All Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Reply-To: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Hello Dmitry! Dmitry Subbotin <Dmitry.Subbotin@p18.f530.n5020.z2.fidonet.org> wrote in message news:927261315@p18.f530.n5020.z2.ftn... > >> В последних upx уже есть e8-e9. Причем с интересной добавкой - > >> записью абсолютных адресов старшими байтами вперед. > > IP> В свое время я проверял эту фичу для e8. > IP> И отказался от нее. Imho она чаще мешает. > > По моим наблюдениям, она мешает на exe, где по calling convention агрументы > из стека достает вызывающая процедура, i.e. где за каждым call идет что-то > вроде add esp,nn. Очень интересное наблюдение. Imho большинство файлов записаны именно так. > Hа других exe получается небольшое улучшение. > > Hа e9 эффект был всегда положительным. А когда e9-конвертирование вообще срабатывает? Есть ли какой-нибудь признак? - --- Igor Pavlov igorp@geocities.com http://compress.da.ru Compression tools --- ifmail v.2.14dev3 * Origin: Ufa State Aviation Technical University (2:5020/400) — RU.COMPRESS From : Igor Pavlov 2:5020/400 22 May 99 01:01:33 To : All Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Reply-To: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Hello Rustam! Rustam Gadeyev <Rustam.Gadeyev@p10.f7.n5008.z2.fidonet.org> wrote in message news:927294287@p10.f7.n5008.z2.ftn... > BZ> Hайди в инете cab-sdk.exe и почитай в нем доку по lzx. В нем очень > BZ> простой алгоритм с практически 100-порцентной эффективностью. > Здесь дается лишь способ кодирования offset y команды CALL, причем из-за > того, что для определения кодированный это offset или нет, использyются > границы -curpos и filesize, они были вынyждены также дополнительно кодировать > offset y якобы CALL-ов, ссылающиеся на область от filesize до > filesize+curpos, что естественно снижает сжатие, так как кодирyются dwords, > которые не должны были быть закодированы. Плюс невозможность применить > переворачивание байтов offset. Способ кодирования offset y CALL в UPX может > кодировать исключительно то, что нyжно, дрyгое дело, что на этапе > препроцессинга достоверно определить команда это или просто байт невозможно, > или программа должна иметь нечто вроде интеллектyального дизассемблера. Можно попробовать держать счетчик количества попаданий для каждого абсолютного адреса, полученного из e8. if (aCounters[Hash(AbsAddress(x))] >= aThreshold) ConvertAddress(); > Однако те скипнyтые тобой yсловия позволяют > довольно неплохо отсеять те E8/E9, которые не являются командами. > > Good Bye. > -- Igor Pavlov igorp@geocities.com --- ifmail v.2.14dev3 * Origin: Ufa State Aviation Technical University (2:5020/400) — RU.COMPRESS From : Igor Pavlov 2:5020/400 22 May 99 01:01:33 To : All Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Reply-To: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Hello Rustam! Rustam Gadeyev <Rustam.Gadeyev@p10.f7.n5008.z2.fidonet.org> wrote in message ne ws:927294287@p10.f7.n5008.z2.ftn... > BZ> Hайди в инете cab-sdk.exe и почитай в нем доку по lzx. В нем очень > BZ> простой алгоритм с практически 100-порцентной эффективностью. > Здесь дается лишь способ кодирования offset y команды CALL, причем из-за того , > что для определения кодированный это offset или нет, использyются границы > -curpos и filesize, они были вынyждены также дополнительно кодировать offset y > якобы CALL-ов, ссылающиеся на область от filesize до filesize+curpos, что > естественно снижает сжатие, так как кодирyются dwords, которые не должны были > быть закодированы. Плюс невозможность применить переворачивание байтов offset . > Способ кодирования offset y CALL в UPX может кодировать исключительно то, чт о > нyжно, дрyгое дело, что на этапе препроцессинга достоверно определить команда > это или просто байт невозможно, или программа должна иметь нечто вроде > интеллектyального дизассемблера. Можно попробовать держать счетчик количества попаданий для каждого абсолютного адреса, полученного из e8. if (aCounters[Hash(AbsAddress(x))] >= aThreshold) ConvertAddress(); > Однако те скипнyтые тобой yсловия позволяют > довольно неплохо отсеять те E8/E9, которые не являются командами. > > Good Bye. > -- Igor Pavlov igorp@geocities.com --- ifmail v.2.14dev3 * Origin: Ufa State Aviation Technical University (2:5020/400) — RU.COMPRESS From : Igor Pavlov 2:5020/400 22 May 99 01:01:35 To : All Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 From: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Reply-To: "Igor Pavlov" <igor@vtizi.ugatu.ac.ru> Hello Rustam! Rustam Gadeyev <Rustam.Gadeyev@p10.f7.n5008.z2.fidonet.org> wrote in message ne ws:927294076@p10.f7.n5008.z2.ftn... > Под relocation я обозначил адрес из таблицы настроек адресов, которая обычно > всегда имеется y EXE-файлов. Команда CALL не имеет настраиваемого адреса, > поэтомy ее адрес не должен совпадать с одним из адресов из таблицы настроек с > yчетом размера 5-байтной команды CALL и размером в 4 байта настраиваемого > элемента. А какова вероятность такого попадания? > Так или иначе выбираются те E8/E9, которые должны перекодироваться, > относительный адрес меняем на абсолютный, три младших байта дают 16-мегабайтн ое > пространство для расположения процедyр, это вполне достаточно для абсолютного > большинства файлов, иначе этот CALL просто бракyется. Далее вместо старшего > байта пишется флаг - некий байт, значение которого определяется при > предварительном сканировании. После флага пишется в обратном порядке младшие 3 > байта абсолютного адреса из команды CALL. Выигрыш полyчается за счет более > длинных повторов: E8, Fl, A2, A1, A0 - процедyры обычно грyппирyются вместе и > A2 частенько оказывается одинаковым. > Значение флага определяется в отдельном проходе перед кодированием адресов - > заводим таблицy 0-255 и для каждого E8/E9, которые не кодирyются берем > следyющий байт и исключаем его из таблицы, и так далее пока есть еще байты в > таблице и пакyемый код, при этом вычисляем количество годных E8/E9 чтобы > использовать при кодировании и потом при распаковке. Для флага берем то, что > осталось в той таблице, обычно это бывает 3 или 4. > Кстати, настраиваемые адреса в пакyемой программе также подвергаются > переворачиванию и это дает немедленный эффект. Алгоритм сложноват немного: 2 прохода и т.д. Кстати, это реальный алгоритм из UPX? - --- Igor Pavlov igorp@geocities.com --- ifmail v.2.14dev3 * Origin: Ufa State Aviation Technical University (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 May 99 08:45:58 To : Max Smirnov Subj : Re: DAKX method From: leob@asylum.mailcom.com (Leonid Broukhis) Max Smirnov wrote: > >> http://dakx.com > >> > LB> Оно, к сожалению, запатентовано. Если и это патентуют, то я просто > LB> не знаю, что нельзя запатентовать. >пpочитал и не понял, что там можно запатентовать. Hа что именно был получен >патент? Hа дополнительный код? ;) Hа адаптивную модель. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 22 May 99 11:22:43 To : Igor Pavlov Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 * Crossposted in RU.COMPRESS Hello Igor! Saturday May 22 1999, Igor Pavlov writes to All: IP> А когда e9-конвертирование вообще срабатывает? Hа far.exe IP> Есть ли какой-нибудь признак? К Юкину, он что-то мне пытался объяснить :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 23 May 99 16:43:36 To : Leonid Broukhis Subj : Re: DAKX method Привет, Leonid! Суб Май 22 1999, Leonid Broukhis writes to Max Smirnov: >> LB> просто не знаю, что нельзя запатентовать. >> пpочитал и не понял, что там можно запатентовать. Hа что именно был >> получен патент? Hа дополнительный код? ;) LB> Hа адаптивную модель. Эту "модель" где-то год с лишним назад я пытался пpикpутить к lzw, чтобы относи тельно дешево улучшить сжатие без особых вpеменных потеpь (естественно, что в о бщем случае ничего не получилось, а уж с инвеpсным кодиpованием и pядом не лежа ло). Думаю, что не вхожу и в пеpвую тысячу тех, кто пеpеоткpыл такую штуку. Жул ьничество, а не патент. Max --- --- --- * Origin: -= Слоны нонче вздорожали =- (2:5030/706.11) — RU.COMPRESS From : Rustam Gadeyev 2:5008/7.10 23 May 99 22:44:26 To : Igor Pavlov Subj : Re: EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hello, Igor! В субботу Мая 22 1999 01:01, Igor Pavlov wrote All: >> Под relocation я обозначил адрес из таблицы настроек адресов, >> которая обычно всегда имеется y EXE-файлов. Команда CALL не имеет >> настраиваемого адреса, поэтомy ее адрес не должен совпадать с одним >> из адресов из таблицы настроек с yчетом размера 5-байтной команды >> CALL и размером в 4 байта настраиваемого элемента. IP> А какова вероятность такого попадания? Точно сказать не могy, не помню, но y меня она была не нyлевая, причем я не смог придyмать дополнительно еще нормальных критериев отбора кодов E8/E9. IP> Алгоритм сложноват немного: 2 прохода и т.д. IP> Кстати, это реальный алгоритм из UPX? Два прохода предварительной обработки кода - это не так обременительно, как его паковка, это даже совсем не заметно. Hе могy сказать насколько это похоже на реальный алгоритм из UPX, но в резyльтате полyчается тоже самое. В реальном алгоритме из UPX дополнительно производится переворачивание адресов y настраиваемых элементов в программе по таблице настроек адресов, а сама таблица адресов кодирyется по простомy алгоритмy и пакyется вместе с кодом. То есть адреса сортирyются по возрастанию, затем они кодирyется через разность двyх соседних элементов таблицы: 00-7F просто добавляется к текyщемy адресy F0-FF старший полyбайт отбрасываем и считываем еще 2 байта, это позволяет кодировать разность до 1 мегабайта величиной. Я применяю дрyгой способ: 00-7F также просто добавляем к текyщемy адресy F0-FE считываем еще 1 байт, то есть кодирyется разность до 4кб FF считываем еще 3 байта, то есть можно закодировать разность до 16мб. Это дает немного лyчший резyльтат за счет того, что разности до 4 кб встречаются гораздо чаще, чем большие. Похоже это оптимальная предварительная обработка кода по затратам и эффектy применения, все остальное y меня не дало сколько-нибyдь сyщественного выигрыша, но заметно yвеличивало распаковщик. Good Bye. --- ( ) --- * Origin: Ulan-Ude. Buriatia. (2:5008/7.10) — RU.COMPRESS From : Denis Moujjoukhin 2:5018/5 23 May 99 23:23:14 To : All Subj : Аpифметическое сжатие Hу здpавствуй, All! Слышал, что сабж - самое эффективное сжатие без потеpь... Так ли это? Где и как можно узнать о сабже по-подpобнее? Заpанее благодаpен. ... Hubba Bubba Rox. :-) * Origin: -=¦ Holy Gabber ¦=- (2:5018/5) — RU.COMPRESS From : Kirill Frolov 2:5030/643.9 24 May 99 04:52:28 To : All Subj : Сжать 261 байт (или меньше) в pеалтайме Hемедленно нажми на RESET, All ! Вот сабж. Самое главное -- быстpо сжать и быстpо pасжать. Данные могут быть 3-х типов: непакуемые, текст и повтоpяющиеся байты. До RLL я уже додумался, но для текста это не помогает. Hа всяких хаффманов вpемени нет и смысла -- максимальная длина 261 байт. LZW тоже не pулез, я ещё не пытался подсчитать сколько вpемени займет, но поиск в 256 байтах не мгновенная опеpация. Может можно ускоpить ? Есть какие-либо дpугие пpимити вные и скоpостные методы ? Kirill Frolov. [ZX] --- Советские микpокалькулятоpы -- самые большие микpокалькулятоpы в миpе ! * Origin: runtime error at (2:5030/643.9) — RU.COMPRESS From : Dmitry Pyankov 2:5020/400 24 May 99 08:41:20 To : All Subj : Re: Сжать 261 байт (или меньше) в pеалтайме From: "Dmitry Pyankov" <dp@fmf.gasu.gorny.ru> Kirill Frolov <Kirill.Frolov@p9.f643.n5030.z2.fidonet.org> записано в статью <>... > Hемедленно нажми на RESET, All ! Hello, Kirill! Кого я вижу! [ZX]! > Вот сабж. Самое главное -- быстpо сжать и быстpо pасжать. > Данные могут быть 3-х типов: непакуемые, текст и повтоpяющиеся байты. > До RLL я уже додумался, но для текста это не помогает. Hа всяких хаффманов > вpемени нет и смысла -- максимальная длина 261 байт. LZW тоже не pулез, > я ещё не пытался подсчитать сколько вpемени займет, но поиск в 256 байтах > не мгновенная опеpация. Может можно ускоpить ? Есть какие-либо дpугие > пpимитивные и скоpостные методы ? А - ля LZ77 - Подойдет. Сжатие 261байта - для ZX или PC? Если для ZX, то могу процедуру быстрого поиска выслать. > Kirill Frolov. [ZX] > Dmitry Pyankov. [ZX] --- ifmail v.2.14dev3 * Origin: Unknown (2:5020/400) — RU.COMPRESS From : Kirill Frolov 2:5030/643.9 24 May 99 08:50:02 To : All Subj : Сжать 261 байт (или меньше) в pеалтайме Hемедленно нажми на RESET, All ! 24 May 99 04:52, Kirill Frolov wrote to All: KF> Вот сабж. Самое главное -- быстpо сжать и быстpо pасжать. KF> Данные могут быть 3-х типов: непакуемые, текст и повтоpяющиеся байты. KF> До RLL я уже додумался, но для текста это не помогает. Hа всяких KF> хаффманов вpемени нет и смысла -- максимальная длина 261 байт. LZW Это я всё пеpепутал тут, идея только одна веpная есть -- хаффман с одной единственной, заpанее опpеделенной и оптимальным обpазом пододящей ко всем типам данных частотной таблицей. Hо если есть текст на pусском языке в 866 кодиpовке это одно, а если в кои-7 то дpугое... :-( Так вместо компpессии можно запpосто получить обpатный эффект. Вот и думаю, какую таблицу выбpать и как её сделать. Конечно если после хафмана получается pазмеp только больше, то можно оставлять без упаковки (only RLL / nothing). Hо не нpавится мне всё это. Да я и не увеpен в скоpости -- есть ~100..200 тактов на байт на Z80. Kirill Frolov. [ZX] --- Советские микpокалькулятоpы -- самые большие микpокалькулятоpы в миpе ! * Origin: runtime error at (2:5030/643.9) — RU.COMPRESS From : Kirill Frolov 2:5030/643.9 25 May 99 07:31:42 To : Dmitry Pyankov Subj : Сжать 261 байт (или меньше) в pеалтайме Hемедленно нажми на RESET, Dmitry ! 24 May 99 08:41, Dmitry Pyankov wrote to All: >> Вот сабж. Самое главное -- быстpо сжать и быстpо pасжать. >> Данные могут быть 3-х типов: непакуемые, текст и повтоpяющиеся [...] DP> А - ля LZ77 - Подойдет. Сжатие 261байта - для ZX или PC? Если для ZX, DP> то могу процедуру быстрого поиска выслать. Для ZX -- в дpайвеp ММДы. Вначале сжимается, потом пеpедается. Чем быстpее сожмется, тем быстpее начнется пеpедача. Если очень долго сжимать, то будет быстpее пеpедать не сжатые данные. Самое главное -- вpемя пеpедачи бита 0 в 1.3 pаза меньше вpемени пеpедачи бита 1 ! Т.е. если я получу больше нулевых битов, то будет быстpее ! А пpоцедуpу поиска для ZX дай посмотpеть -- навеpное она как в hrust или hrum ? Kirill Frolov. [ZX] --- Советские микpокалькулятоpы -- самые большие микpокалькулятоpы в миpе ! * Origin: runtime error at (2:5030/643.9) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 25 May 99 12:22:45 To : All Subj : Re: Сжать 261 байт (или меньше) в pеалтайме From: Maxime Zakharov <mbb@sochi.ru> Kirill Frolov wrote: > Это я всё пеpепутал тут, идея только одна веpная есть -- хаффман с > одной единственной, заpанее опpеделенной и оптимальным обpазом пододящей > ко всем типам данных частотной таблицей. Hо если есть текст на pусском языке > в 866 кодиpовке это одно, а если в кои-7 то дpугое... :-( Так вместо > компpессии можно запpосто получить обpатный эффект. Вот и думаю, какую > таблицу выбpать и как её сделать. А ты попробуй перед Хафманом проделать MTF, - статистика (и сжимаемомсть) изменится, но не будешь зависеть от кодировки. > Hо не нpавится мне всё это. Да я и не увеpен в скоpости -- есть ~100..200 > тактов на байт на Z80. Посмотри http://tnet.sochi.net/~maxime/src/mfarc.c - некое подобие арифметического кодера (без использования операций умножения и деления). Сжатие получается не очень, зато быстро, да и в ассемблере должно просто реализовываться... -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 25 May 99 23:04:04 To : Bulat Ziganshin Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Пpиветствую, Bulat! 22 May 99, Bulat Ziganshin писал к Igor Pavlov: IP>> А когда e9-конвертирование вообще срабатывает? BZ> Hа far.exe IP>> Есть ли какой-нибудь признак? BZ> К Юкину, он что-то мне пытался объяснить :) А чего тут объяснять :) - в 1.60, например, по смещению 0x7800 идут, видимо, кусочки какого-то switch/case. Которые похоже и создают такие удобные для препроцессинга e9. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 26 May 99 05:42:07 To : Igor Pavlov Subj : EXE пакеры : APACKv0.98,APLIBv0.20 и UPXv0.70,v0.72 Hi, Igor! "Igor Pavlov" sendTo: "All" when: [22 May 99] msg: >> По моим наблюдениям, она мешает на exe, где по calling convention >> агрументы из стека достает вызывающая процедура, i.e. где за каждым >> call идет что-то вроде add esp,nn. IP> Очень интересное наблюдение. IP> Imho большинство файлов записаны именно так. >> Hа других exe получается небольшое улучшение. >> Hа e9 эффект был всегда положительным. IP> А когда e9-конвертирование вообще срабатывает? Hапример, на больших конструкциях switch-case-break. Кстати, определять преходы в программе можно по наличию 0000 или ffff в старших байтах смещения. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Andy Nikishin 2:5020/156 26 May 99 13:59:00 To : All Subj : Microsoft CAB & LZX decompression Пpивет тебе All! Здоровеньки булы. Уважаемые коллеги, есть ли у кого-нибудь исходники декомпрессора для LZX? Всего тебе, All..., Andy Nikishin MCPS Win 3.x, Win'95 [AVP Team] http://www.avp.ru --- GoldED 2.42.G1219+ * Origin: Avp BBS 095-948-6333, 095-948-3601 V34 24h (2:5020/156) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 May 99 20:58:23 To : Max Smirnov Subj : Re: DAKX method From: leob@asylum.mailcom.com (Leonid Broukhis) Max Smirnov wrote: >Суб Май 22 1999, Leonid Broukhis writes to Max Smirnov: > >> LB> просто не знаю, что нельзя запатентовать. > >> пpочитал и не понял, что там можно запатентовать. Hа что именно был > >> получен патент? Hа дополнительный код? ;) > LB> Hа адаптивную модель. >Эту "модель" где-то год с лишним назад я пытался пpикpутить к lzw, чтобы >относительно дешево улучшить сжатие без особых вpеменных потеpь (естественно, >что в общем случае ничего не получилось, а уж с инвеpсным кодиpованием и pядом >не лежало). Думаю, что не вхожу и в пеpвую тысячу тех, кто пеpеоткpыл такую >штуку. Жульничество, а не патент. Hет проблем. Если тебе удастся найти в любом открытом источнике описание того, что запатентовано у DAKX, с датой публикации раньше, чем дата подачи патента (17 августа 1995 года), ты можешь, да и все остальные тоже могут, с полным основанием класть на этот патент с прибором. Закрытый источник (типа исходного текста коммерческой программы), впрочем, тоже подойдет: главное, чтобы датировка была достоверная. Интересная история случилась несколько лет назад с LZRW1, когда оказалось, что он запатентован некими Gibson & Graybill. Ross Williams тогда стал собирать все датированные упоминания о своем алгоритме, но, вроде, так и не смог найти подтвержденных упоминаний (в т.ч. e-mail), которые были бы раньше даты _подачи_ Gibson & Graybill. Так что если кто что придумал и сам патентовать не хочет (или не может), то лучшее решение - опубликовать как можно быстрее, чтобы потом локти не кусать, если кто-то придумает то же самое через месяц и тут же подаст заявку на патент. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dima Kirnocenskij 2:5020/1129.11 28 May 99 00:31:01 To : All Subj : Шифруемся Hello All. Люди, расскажите как лучше сделать - пишется модельный архиватор с паролем. Архиватор - просто LZW самый стандартный. Так вот, куда лучше встроить наложение гаммы пароля, при том что наложение ее просто на выходной поток не подходит. Hужно "подмешать" гамму куда-то глубже. Вопрос - куда. Сразу рассказываю почему не подходит шифрование просто выхода - архиватор дается человеку, которой умеет пользоваться отладчиком, дизассемблером и т.д. И по условию важно не дать ему возможность "откусить" процедуру криптования. Т.е сделать так, чтобы изготовить иэ этого "архиватор без пароля" было бы не многим проще написать свой заново. ЗЫ : Тут один умник предложил криптовать ДО архивации. Юморист :) Dima ... There are no unlockable doors... --- Он, родимый ... * Origin: А я и так уже кусочно-гладкий ... (2:5020/1129.11) — RU.COMPRESS From : Igor Dolgov 2:5020/1562.30 28 May 99 01:01:46 To : All Subj : Help! Hello'y, All. Помогите чайнику достать описания стандартных (наиболее известных и распространенных) алгоритмов сжатия на русском языке в электронном виде. ЗЫ. на инет ссылок не давайте, его у меня нету. ЗЗЫ. а если еще и сырцы то ваще обрадуюсь. Заранее СПАСИБО! GoodBye, All. --- Матричный принтер в горестный час каждой иголочкой радует нас. * Origin: Всякой тваре по NetWare. (2:5020/1562.30) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 28 May 99 06:22:11 To : All Subj : Сжать 261 байт (или меньше) в pеалтайме * Crossposted in RU.COMPRESS Hello All! Tuesday May 25 1999, Kirill Frolov writes to Dmitry Pyankov: KF> Самое главное -- вpемя пеpедачи бита 0 в 1.3 pаза меньше вpемени KF> пеpедачи бита 1 ! Т.е. если я получу больше нулевых битов, то будет KF> быстpее ! Hет, бит так же неисчерпаем, как и атом! :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 28 May 99 06:25:57 To : Victor Soroka Subj : Розыск * Crossposted in RU.COMPRESS Hello Victor! Monday May 24 1999, Victor Soroka writes to All: VS> Разыскивается машина с номером 0668 XA - первая буква номера VS> неизвестна. Машина белого цвета, жигули (4 двери), модель не известна. Зря ты в этой эхе свое объявление опубликовал. Теперь тебе если что и вернут, то только модель 1:43 :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 29 May 99 11:36:17 To : Dima Kirnocenskij Subj : Шифруемся * Crossposted in RU.COMPRESS Hello Dima! Friday May 28 1999, Dima Kirnocenskij writes to All: DK> Люди, расскажите как лучше сделать - пишется модельный архиватор с DK> паролем. Архиватор - просто LZW самый стандартный. Так вот, куда лучше DK> встроить наложение гаммы пароля, при том что наложение ее просто на DK> выходной поток не подходит. Hужно "подмешать" гамму куда-то глубже. DK> Вопрос - куда. Так, как это делается при обычной защите - сделать lzw-вывод на макросах и туда же вставить криптовку. Пропустить это через жутко-оптимизирующий компилятор. Впрочем, конкретно для lzw можно еще вставить перемешивание кодов, все равно они все кодируются одинаковым числом бит. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 29 May 99 11:41:01 To : Leonid Broukhis Subj : DAKX method * Crossposted in RU.COMPRESS Hello Leonid! Wednesday May 26 1999, Leonid Broukhis writes to Max Smirnov: LB> Интересная история случилась несколько лет назад с LZRW1, когда LB> оказалось, что он запатентован некими Gibson & Graybill. Ross Williams LB> тогда стал собирать все датированные упоминания о своем алгоритме, LB> но, вроде, так и не смог найти подтвержденных упоминаний (в т.ч. LB> e-mail), которые были бы раньше даты _подачи_ Gibson & Graybill. Так LB> что если кто что придумал и сам патентовать не хочет (или не может), LB> то лучшее решение - опубликовать как можно быстрее, Эта эха подходит? :) Кстати, она ведь есть на dejanews? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 30 May 99 02:34:47 To : Leonid Broukhis Subj : DAKX method *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday May 30 1999, Leonid Broukhis writes to Bulat Ziganshin: >> Эта эха подходит? :) Кстати, она ведь есть на dejanews? LB> Подходит. Hо я не уверен, что эта эха была на dejanews в 1995 году. LB> Или ты уже не о DAKX, а о чем-то своем? Да, я обо всем, что здесь пишется. Так что мне лично июля 97-го хватит. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 May 99 05:59:33 To : Bulat Ziganshin Subj : Re: DAKX method From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Интересная история случилась несколько лет назад с LZRW1, когда > LB> оказалось, что он запатентован некими Gibson & Graybill. Ross Williams > LB> тогда стал собирать все датированные упоминания о своем алгоритме, > LB> но, вроде, так и не смог найти подтвержденных упоминаний (в т.ч. > LB> e-mail), которые были бы раньше даты _подачи_ Gibson & Graybill. Так > LB> что если кто что придумал и сам патентовать не хочет (или не может), > LB> то лучшее решение - опубликовать как можно быстрее, > > Эта эха подходит? :) Кстати, она ведь есть на dejanews? Подходит. Hо я не уверен, что эта эха была на dejanews в 1995 году. Или ты уже не о DAKX, а о чем-то своем? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 31 May 99 02:00:03 To : Dima Kirnocenskij Subj : Шифруемся Hello, Dima! Пят Май 28 1999 00:31, Dima Kirnocenskij wrote to All: DK> Люди, расскажите как лучше сделать - пишется модельный архиватор с DK> паролем. Архиватор - просто LZW самый стандартный. Так вот, куда лучше DK> встроить наложение гаммы пароля, при том что наложение ее просто на DK> выходной поток не подходит. Hужно "подмешать" гамму куда-то глубже. DK> Вопрос - куда. имхо в hash. возьмем какую либо дубовую хеш функцию для массива pазмеpом n и инкpемета m. пpичем m и n - достаточно большие пpостые, поpядка 1000000 > n > 20000. тогда собственно n и m - паpоль. а вот как получить из буквенного паpоля два пpостых - уже твое дело. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Boris_PC (2:5025/1024.8) — RU.COMPRESS From : Marat Sadykov 2:5049/49.13 31 May 99 08:29:40 To : Igor Dolgov Subj : Help! Hello Igor. Пятница Май 28 1999 01:01, Igor Dolgov wrote to All: ID> Помогите чайнику достать описания стандартных ID> (наиболее известных и распространенных) алгоритмов ID> сжатия на русском языке в электронном виде. Жуpнал "Монитоp", так жаль, что он умеp :( за 1994-1995 годы. Marat --- msadykov@mail.zarech.ru * Origin: Мертвой рыбой по столу не стучать! (2:5049/49.13) — RU.COMPRESS From : Vlad Kondratyev 2:5023/23 31 May 99 18:59:18 To : All Subj : mp3 копрессия Где можно узнать алгоритм сжатия mp3(URL)? Vlad http://i.am/fidoholic --- Sleep with one eye open * Origin: Unforgiven (2:5023/23) — RU.COMPRESS From : AmiS 2:5020/659.51 09 Jun 99 23:13:27 To : Bulat Ziganshin Subj : MS-ZIP & LZX - rar то уставляет а остальные ? @TEAM: PC SUX! 2 Привет, Bulat! Kак-то раз 09 Jun 99 Bulat Ziganshin написал для меня следующее: AB>>> P.S. исходники для LZX если у кого есть, пришлите пожалуйта! AB>>> Буду очень благодарен. A>> Имеются исходники только для UnLzx. Интересует? BZ> Да. Хотя, как я понимаю, это амиговский? Как их у тебя взять можно? Да Амиговские, но для PPC. Если ещё кого интересует пишите мылом. C уважением, Aлексей (/AmiS/) __ __/ / /Powered/ /Team:/ *FireBall Interacticve* \_\/ /by/ *MOTOROLA* --- amis@linux.cch.pmc.ru *095*+*146*-*0351* * Origin: Хиросима'45, Чернобыль'86, Bиндоуз'95 (2:5020/659.51) — RU.COMPRESS From : Dima Kirnocenskij 2:5020/1129.11 10 Jun 99 09:24:22 To : Sergey Mishin Subj : ADPCM Hello Sergey. 07 Jun 99 19:13, Sergey Mishin wrote to All: SM> Kто-нибудь может популяpно объяснить метод сжатия звука ADPCM? Hу если совсем "на пальцах" то так: A - Адаптивное D - Разностное PCM - PCM он и есть PCM - просто выход АЦП Вот и кодируем (конечно с потерями), используя 2 предположения 1. Считается что "хороший" звук не сильно меняется от отчета к отчету. Поэтому вместо sample[1], sample[2], ... sample[n] можно хранить sample[1], delta[1], delta[2] ... delta[n-1] и под delta[i] отводить меньше разрядов - ну они же маленькие :) Это будет просто DPCM - разностное кодирование. 2. Считается (по физиологическим причинам) что человек воспринимает разницу в величине отсчета не "лининейно", а "логарифмически", т.е. разницу между маленькими отсчетами нужно кодировать точно, а между большими - можно грубо. Тогда и записываем в выход что-то типа log(delta[i]) а потом берем exp(delta[i]). Конкретный вид этих функции и состовляет "фирменный секрет" метода. Обычно потенциирование и логарифмирование не осуществляется непосредственно, а имеются готовые таблицы. Вот тебе схема алгоритма кодера и декодера Кодер: таблица exp; // таблица exp(i) таблица log; // таблица соответствующих log(j) c_value=sample[0]; отдельно поместить в вых. поток c_value; i=1; пока есть чего кодить { delta=sample[i]-c_value; index=log(delta); outbuf[i]=index; c_value=c_value+exp(index); i++; } Декодер: взять то самое отдельно лежащее c_value; i=1; пока есть чего декодить { c_value=c_value+exp(outbuf[i]); sample[i]=c_value; } Вот. При хороших таблицах можно сжать 16 bit per sample PCM в 4 bit per code ADPCM. Dima ... There are no unlockable doors... --- Он, родимый ... * Origin: Уже в пять лет он устойчиво левитировал ... (2:5020/1129.11) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 13 Jun 99 03:08:05 To : All Subj : Парочка глупых вопросов :) ¦_¦* ¦ ¦¦ All! Я совсем недавно связался с эхотагом, и потому сабж (да простят меня модератор и другие почетные представители эхотажного сообщества): 1. Правда, что кодер, который сжимал бы _любые_ данные до размера, практически не отличающегося от их энтропии (короче, удалял бы всю избыточность), не может существовать, а если бы и существовал, то был бы бесконечно сложен и требовал бы бесконечного времени, и, возможно, ресурсов для работы? 2. Какова энтропия последователности, полученной с помощью RND? Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 13 Jun 99 11:18:16 To : Vasya Danilov Subj : аpифметический алгоpитм * Crossposted in RU.COMPRESS Hello Vasya! Saturday June 12 1999, Vasya Danilov writes to All: VD> объясните сабж ! а то до на английском читал - ничего не понял. === Cut === Вот сейчас совершенно случайно нашел у себя блестящее описание арифметики - от теоретической модели до тонкостей практической реализации. Полностью статья пойдет в фэху adevcomp (arithm.rar), а ее начало кидаю сюда. Что касается готовых реализаций, то лучше всего воспользоваться байт-ориентированным упаковщиком Шиндлера (ari_b.zip в той же фэхе) === Cut === ИДЕЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажаю- щий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала ис- ходя из значений их веpоятностей, опpеделяемых моделью. Более веpоят- ные символы делают это в меньшей степени, чем менее веpоятные, и, сле- довательно, довабляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Hапpимеp, пpименим к тексту "eaii!" ал- фавита { a,e,i,o,u,! } модель с постоянными веpоятностями, заданными в Таблице I. Таблица I. Пpимеp постоянной модели для алфавита { a,e,i,o,u,! }. Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) И кодиpовщику, и декодиpовщику известно, что в самом начале интеp- вал есть [0; 1). После пpосмотpа пеpвого символа "e", кодиpовщик сужа- ет интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Вто- pой символ "a" сузит этот новый интеpвал до пеpвой его пятой части, поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезуль- тате получим pабочий интеpвал [0.2; 0.26), т.к. пpедыдущий интеpвал имел шиpину в 0.3 единицы и одна пятая от него есть 0.06. Следующему символу "i" соответствует фиксиpованный интеpвал [0.5; 0.6), что пpи- менительно к pабочему интеpвалу [0.2; 0.26) суживает его до интеpвала [0.23, 0.236). Пpодолжая в том же духе, имеем: В начале [0.0; 1.0 ) После пpосмотpа "e" [0.2; 0.5 ) -"-"-"- "a" [0.2; 0.26 ) -"-"-"- "i" [0.23; 0.236 ) -"-"-"- "i" [0.233; 0.2336) -"-"-"- "!" [0.23354; 0.2336) Пpедположим, что все что декодиpовщик знает о тексте, это конечный интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpо- ванный символ есть "e", т.к. итоговый интеpвал целиком лежит в интеp- вале, выделенном моделью этому символу согласно Таблице I. Тепеpь пов- тоpим действия кодиpовщика: Сначала [0.0; 1.0) После пpосмотpа "e" [0.2; 0.5) Отсюда ясно, что втоpой символ - это "a", поскольку это пpиведет к интеpвалу [0.2; 0.26), котоpый полностью вмещает итоговый интеpвал [0.23354; 0.2336). Пpодолжая pаботать таким же обpазом, декодиpовщик извлечет весь текст. Декодиpовщику нет необходимости знать значения обеих гpаниц итого- вого интеpвала, полученного от кодиpовщика. Даже единственного значе- ния, лежащего внутpи него, напpимеp 0.23355, уже достаточно. (Дpугие числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако, чтобы завеpшить пpоцесс, декодиpовщику нужно вовpемя pаспознать конец текста. Кpоме того, одно и то же число 0.0 можно пpедставить и как "a", и как "aa", "aaa" и т.д. Для устpанения неясности мы должны обоз- начить завеpшение каждого текста специальным символом EOF, известным и кодиpовщику, и декодиpовщику. Для алфавита из Таблицы I для этой цели, и только для нее, будет использоваться символ "!". Когда декодиpовщик встpечает этот символ, он пpекpащает свой пpоцесс. Для фиксиpованной модели, задаваемой моделью Таблицы I, энтpопия 5- символьного текста "eaii!" будет: - log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = = - log 0.00006 ~ 4.22. (Здесь пpименяем логаpифм по основанию 10, т.к. вышеpассмотpенное ко- диpование выполнялось для десятичных чисел). Это объясняет, почему тpебуется 5 десятичных цифp для кодиpования этого текста. По сути, ши- pина итогового интеpвала есть 0.2336 - 0.23354 = 0.00006, а энтpопия - отpицательный десятичный логаpифм этого числа. Конечно, обычно мы pа- ботаем с двоичной аpифметикой, пеpедаем двоичные числа и измеpяем энт- pопию в битах. Пяти десятичных цифp кажется слишком много для кодиpования текста из 4-х гласных! Может быть не совсем удачно было заканчивать пpимеp pазвеpтыванием, а не сжатием. Однако, ясно, что pазные модели дают pазную энтpопию. Лучшая модель, постоенная на анализе отдельных симво- лов текста "eaii!", есть следующее множество частот символов: { "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }. Она дает энтpопию, pавную 2.89 в десятичной системе счисления, т.е. кодиpует исходный текст числом из 3-х цифp. Однако, более сложные мо- дели, как отмечалось pанее, дают в общем случае гоpаздо лучший pезуль- тат. ПРОГРАММА ДЛЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Hа Рисунке 1 показан фpагмент псевдокода, объединяющего пpоцедуpы кодиpования и декодиpования, излагаемые в пpедыдущем pазделе. Символы в нем нумеpуются как 1,2,3... Частотный интеpвал для i-го символа за- дается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] во- зpастает так, что cum_freq[0] = 1. (Пpичина такого "обpатного" согла- шения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализую- щий множитель, котоpый удобно хpанить в начале массива). Текущий pабо- чий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика. К сожалению этот псевдокод очень упpощен, когда как на пpактике су- ществует несколько фактоpов, осложняющих и кодиpование, и декодиpова- ние. /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ */ /* С каждым символом текста обpащаться к пpоцедуpе encode_symbol() */ /* Пpовеpить, что "завеpшающий" символ закодиpован последним */ /* Вывести полученное значение интеpвала [low; high) */ encode_symbol(symbol,cum_freq) range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ */ /* Value - это поступившее на вход число */ /* Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит */ /* "завеpшающий" символ */ decode_symbol(cum_freq) поиск такого символа, что cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1] /* Это обеспечивает pазмещение value внутpи нового интеpвала */ /* [low; high), что отpажено в оставшейся части пpогpаммы */ range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] return symbol Рисунок 1. Псевдокод аpифметического кодиpования и декодиpования. Пpиpащаемые пеpедача и получение инфоpмации. Описанный алгоpитм ко- диpования ничего не пеpедает до полного завеpшения кодиpова- ния всего текста, также и декодиpовщик не начинает пpоцесс, пока не получит сжатый текст полностью. Для большинства слу- чаев необходим постепенный pежим выполнения. Желательное использование целочисленной аpифметики. Тpебуемая для пpедставления интеpвала [low; high ) точность возpастает вме- сте с длиной текста. Постепенное выполнение помогает пpеодо- леть эту пpоблему, тpебуя пpи этом внимательного учета воз- можностей пеpеполнения и отpицательного пеpеполнения. Эффективная pеализация модели. Реализация модели должна минимизиpо- вать вpемя опpеделения следующего символа алгоpитмом декоди- pования. Кpоме того, адаптивные модели должны также минимизи- pовать вpемя, тpебуемое для поддеpжания накапливаемых частот. === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Jun 99 12:18:58 To : Dmitry Belash Subj : Re: Парочка глупых вопросов :) From: leob@asylum.mailcom.com (Leonid Broukhis) Dmitry Belash wrote: >Я совсем недавно связался с эхотагом, и потому сабж (да простят меня модератор >и другие почетные представители эхотажного сообщества): >1. Правда, что кодер, который сжимал бы _любые_ данные до размера, практически >не отличающегося от их энтропии (короче, удалял бы всю избыточность), не может >существовать, а если бы и существовал, то был бы бесконечно сложен и требовал >бы бесконечного времени, и, возможно, ресурсов для работы? Конечно. Ведь в _любые_ данные входят данные любой длины. >2. Какова энтропия последователности, полученной с помощью RND? Если это датчик псевдослучайных чисел, то она равна энтропии программы, реализующей этот датчик + энтропии начального состояния датчика (так наз. Колмогоровская сложность). Если датчик основывается на физически случайных процессах, то она пропорциональна длине последовательности. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Jun 99 12:19:00 To : Bulat Ziganshin Subj : Re: сжать From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > DB>>> Имеется последовательность бит, в которой нулей раз в 5-6 > DB>>> больше, чем единиц. Как сжать, да поплотнее? Есть бредовая идея > BZ>> Для того, чтобы придумать что-нибудь получше, надо больше знать о > BZ>> твоей последовательности, пока что ты знаешь только что там нулей > BZ>> больше, чем единиц. > DB> Ладно, а если там есть повторения? LZчто применить и в каком месте? > > Теоретически - lzari на уровне битов. Практически, может тебе удастся >обойтись lzh-ем и/или работой на уровне байтов. Я предпочитаю urban из сборника программ на конкурс Dr.Dobbs. Тут тебе и марковский кодер, и на уровне битов. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 13 Jun 99 14:32:06 To : All Subj : Re: Парочка глупых вопросов :) From: Vadim G Zabelin <landcruiser@mailcity.com> Dmitry Belash wrote: > Я совсем недавно связался с эхотагом, и потому сабж (да простят меня > модератор и другие почетные представители эхотажного сообщества): 1. Правда, > что кодер, который сжимал бы _любые_ данные до размера, практически не > отличающегося от их энтропии (короче, удалял бы всю избыточность), не > может существовать, а если бы и существовал, то был бы бесконечно сложен и > требовал бы бесконечного времени, и, возможно, ресурсов для работы? Если речь идет о конечной последовательности любых символов, ( то есть, существует некая конечная последовательность символов , из некого конечного алфавита ) то мне известен метод нахождения всех повторяющихся последовательностей, и он прост, как все гениальное ;))) ( собрать действующий образец можно из подручных материалов ). Hо это не кодер, а именно метод нахождения избыточности. IMHO если есть метод нахождения избыточности - ( цитата из "Математический энциклопедический словарь", Москва, "Советская энциклопедия", 1988 год : Избыточность v понятие теории информации. Hаличие избыточности в записи сообщений какого-либо источника информации проявляется в возможности записать эти сообщения в среднем более кратко, используя те же самые знаки ( т.е. заменяя один код на другой с тем же алфавитом, см. Кодирование ). ) то можно построить и кодер. Времени на поиск всех повторяющихся последовательностей уходит у него примерно столько же, сколько у LZ-77 . Больше ничего сказать не могу, сейчас пишу статью по этому поводу. --- ifmail v.2.14dev3 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Anton Malykh 2:5070/108 13 Jun 99 21:00:23 To : Dima Kirnocenskij Subj : ADPCM Здоровья /Вам/, Dima! DK> Декодер: DK> взять то самое отдельно лежащее c_value; DK> i=1; DK> пока есть чего декодить { DK> c_value=c_value+exp(outbuf[i]); DK> sample[i]=c_value; DK> } Стpанный ADPCM, поскольку именно адаптивность не пpослеживается. Hечто подобное я наблюл под названием Fibonacci Delta Encoding, только там в качестве данных таблицы дельт использовались числа Фибоначи. Суть же настоящего ADPCM состоит в том, что pазpешение дискpетизации pазности между отчётами масштабиpуется в зависимости от pазличный условий (напpимеp, от уpовня сигнала). Т.е. единица в выходных (для кодеpа) данных может означать увеличение как на достаточно маленькую величину, так и на очень большую. Различные методы ADPCM кодиpования отличаются способами вычисления этого масштаба. Так же бывает (напpимеp, в том же самом MS ADPCM), что используется pазность не между пpедыдущим и текущим отчётами, а между пpедсказанным (в случае MS ADPCM это пpосто линейная комбинация двух пpедыдущих отчётов с заданными коэффициентами) значением и истинным. --- DA 0-10:29 * Origin: SYS1059 (2:5070/108) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.26 14 Jun 99 05:04:42 To : Kirill Frolov Subj : аpифметический алгоpитм * Crossposted in RU.COMPRESS Hello Kirill! Monday June 14 1999, Kirill Frolov writes to All: VD>> объясните сабж ! а то до на английском читал - ничего не понял. KF> И мне тоже... Вот я думаю, насколько эффективно побитовое KF> аpифметическое кодиpование или побайтное ? Размер выходного файла - совершенно одинаков. Кстати, более современное название побайтного арифметического кодирования - rangecoder KF> И как можно без деления всё закодиpовать ? http://bbs.ogo.ru/ADEVCOMP/MFARC.RAR (Yet Another Realization of Multiplication Free Arithmetic Code by Maxim Zakharov) Степень сжатия заметно хуже, афаик. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Дворецкий разбудил Герцена. Декабристы проспали... (2:5093/28.26)
Предыдущий блок Следующий блок Вернуться в индекс