Предыдущий блок Следующий блок Вернуться в индекс
 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)
 Предыдущий блок Следующий блок Вернуться в индекс