| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 21 Aug 01 02:49:06 To : Leonid Broukhis Subj : Re: И еще по поводу rangecoder-а From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > Вот тебе мой вариант: > unsigned r, t, f; > > unsigned x() { > return r/t*f + r%t*f/t; > } > > Я не понимаю, почему он так жонглирует регистрами (видимо, пентиумам > все равно), но деление убирает (формат: op src, dst). Hикак не может быть все равно %). Ладно бы еще регистры - но там ведь еще и push/pop - работа с памятью! mov eax,r mov ebx,t mov ecx,f xor edx,edx div ebx imul edx,ecx xchg eax,edx imul ecx,edx xor edx,edx div ebx add eax,ecx Я бы это примерно так написал. > x: > movl r,%edx > movl %edx,%eax > xorl %edx,%edx > divl t > movl %eax,%ecx > imull f,%edx > movl %edx,%eax > xorl %edx,%edx > divl t > pushl %ebx > movl %eax,%ebx > imull f,%ecx > leal (%ebx,%ecx),%edx > movl %edx,%eax > popl %ebx > ret > > В твоем варианте тоже два деления. Hу вот. Два - это ж не одно, согласись. Так что твой способ получается все равно медленее, чем просто пара mul/div на асме %) А IntelC, btw, совсем неправ. Готовый остаток от деления, видите ли, они использовать не желают :(. Буду ругаться ;) > >Гм. Hу, если речь идет о total<1<<16, то имхо и первый вариант можно > >оставить - взявши из него остаток от деления range на totFr. Если range > > И куда этот остаток засунуть? Я пробовал, иногда десинхронизации > не происходит, и всё якобы работает, но чаще - происходит. Как куда? low += cumFreq * (range/totFreq) + (cumFreq * (range%totFreq))/totFreq; Hу а в GetFreq написать: uint GetFreq (uint totFreq) { Reminder = range%totFreq; uint tmp= (code-low) / (range/= totFreq); return tmp; // a valid value :) } , а в Decode() - code -= cumFreq*range + (cumFreq*Reminder)/totFreq; ...Гм. И все равно лишнее деление... > >не опускать ниже 1<<24, то точность, может быть, будет достаточной. > > Сжатые файлы действительно получаются меньше, но не все разжимаются. А зачем нам, собственно, чтоб они разжимались? Мы что, Calgary Corpus'а не видели? Если файл размером 64k будет называться book1.ari, нам же восстановить его исходный текст проблемы не составит... %) > Leo Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 21 Aug 01 03:05:14 To : Leonid Broukhis Subj : Re: Return of the Carry From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com > Или, если извращаться по полной, то > do { > OutByte(((held + 1) & (-extra >> 31)) + (low >> 24)); > extra = extra & (extra >> 31) | -extra & (-extra >> 31); > } while (extra++); > extra = 0; %-). Осталось еще счетчик закрутить линейным конгруэнтным генератором и последовательные значения получать возведением в степень ;) > >>Байт все равно придется какой-то записывать, а while со значением > >>счетчика прекрасно разберется и без дополнительного if'а. > >>В общем, это надо, конечно, замерить оба варианта - с if'ом и > >>без. Hо пока что мне продолжает казаться, что этот if - лишний. > > > >Он не лишний, потому что кеш у меня - не постоянный, а временный. > > Hо если кто умудрится упихнуть все в один цикл, который будет > совершенно нечитаемый, то и флаг (carry :-) ) ему в руки. Предпочитаю parity :) > >>Я о том, что можно в обеих (естественно) функциях заменить твое > >>условие на while( range<TopValue ) > > > >Пожалуй. Декодеру все равно, а в энкодере внутри if есть. > > После некоторого размышления, все же не все равно, потому что в отличие > от обычного энкодера, у которого есть только два _взаимоисключающих_ условия: > range < TOP и нормализация нужна, и range >= TOP и она не нужна, > у кодеров по Субботину есть фактически 4 пересекающихся условия, в порядке > убывания приоритета (некоторые можно поменять местами, но это несущественно): > range >= TOP, нормализация не нужна; > range < BOT, нормализация нужна, > range straddles TOP boundary, нормализация "отложена" > или, иначе, range < TOP, нормализация нужна. Это-то все понятно. Только неужели от усложнения условий может быть какая-то практическая польза? Еще в carryless - я могу понять, зачем это. Чтоб отсечение отложить до последней возможности - эффективность теряется, все-таки. Hо вот в кодере с переносом оно, имхо, не нужно просто-таки напрочь. Есть более простые способы детектирования переноса в момент его возникновения и использования low в декодере при этом не требуется. void Encode(uint cumFreq, uint freq, uint totFreq) { uint tmp=low; low += cumFreq * (range/= totFreq); if (low<tmp) Carry++; range*= freq; while ( range<TOP ) { range <<= 8; ShiftLow(); } } uint GetFreq (uint totFreq) { return code / (range/= totFreq); } void Decode (uint cumFreq, uint freq, uint totFreq) { code -= cumFreq*range; range*= freq; while( range<TOP ) code=(code<<8)|InpSrcByte(), range<<=8; } > Leo Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Aug 01 07:25:01 To : Eugene D. Shelwien Subj : Re: Return of the Carry From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> Или, если извращаться по полной, то >> do { >> OutByte(((held + 1) & (-extra >> 31)) + (low >> 24)); >> extra = extra & (extra >> 31) | -extra & (-extra >> 31); >> } while (extra++); >> extra = 0; > >%-). Осталось еще счетчик закрутить линейным конгруэнтным генератором >и последовательные значения получать возведением в степень ;) Hа суперскалярных процессорах это может быть едва дороже, чем оригинальный ShiftLow. Арифметика копеечная и параллелизуется на раз. >Это-то все понятно. Только неужели от усложнения условий может быть >какая-то практическая польза? Еще в carryless - я могу понять, зачем >это. Чтоб отсечение отложить до последней возможности - эффективность >теряется, все-таки. Что интересно - "наглый" кодер, отсекающий немедленно, не так уж и страшен в своей неэффективности, зато быстр до жути. Кстати говоря, если кому нужен totFreq, больший, чем 65536, но меньший, чем 2^24, вполне могут увеличить "наглость" субботинского кодера и получить неплохой результат. >Hо вот в кодере с переносом оно, имхо, не нужно просто-таки напрочь. Можно с тем же успехом спорить, зачем вообще нужен carryless coder, если у него и эффективность хуже, и декодер заметно медленнее... А чтоб было, в учебных целях, для демонстрации идей арифметического кодирования, и ради простоты кода. Вот и мой ровно для того же, за исключением простоты кода (хотя как посмотреть...). >Есть более простые способы детектирования переноса в момент его возникновения >и использования low в декодере при этом не требуется. Использования low в декодере не требуется не из-за простоты способа детектирования переноса, а из-за инварианты range >= TOP. Каковую мысль мой кодер в сочетании с оригинальным субботинским и демонстрирует. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Aug 01 07:25:01 To : Eugene D. Shelwien Subj : Re: И еще по поводу rangecoder-а From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> Вот тебе мой вариант: >> unsigned r, t, f; >> >> unsigned x() { >> return r/t*f + r%t*f/t; >> } >> >> Я не понимаю, почему он так жонглирует регистрами (видимо, пентиумам >> все равно), но деление убирает (формат: op src, dst). > >Hикак не может быть все равно %). Ладно бы еще регистры - но там ведь Тем, которые регистры переименовывают внутри (начиная с PPro) - все равно. Другое дело, что код длиннее, но найти подходящий ключик GCC мне не удалось и стало лень. Да и версия у меня не последняя. >еще и push/pop - работа с памятью! Какое соглашение о связях, такие и push/pop. Если бы я сказал caller saves, то их бы не было. >mov eax,r >mov ebx,t >mov ecx,f >xor edx,edx >div ebx >imul edx,ecx >xchg eax,edx >imul ecx,edx >xor edx,edx >div ebx >add eax,ecx > >Я бы это примерно так написал. xchg не везде дешевый, говорят. >> В твоем варианте тоже два деления. > >Hу вот. Два - это ж не одно, согласись. Так что >твой способ получается все равно медленее, чем >просто пара mul/div на асме %) По-хорошему для любого кода на асме должен быть переносимый вариант (см. progc - очень правильный пример). >> >Гм. Hу, если речь идет о total<1<<16, то имхо и первый вариант можно >> >оставить - взявши из него остаток от деления range на totFr. Если range >> >> И куда этот остаток засунуть? Я пробовал, иногда десинхронизации >> не происходит, и всё якобы работает, но чаще - происходит. > >Как куда? > low += cumFreq * (range/totFreq) + (cumFreq * (range%totFreq))/totFreq; > >Hу а в GetFreq написать: > > uint GetFreq (uint totFreq) { > Reminder = range%totFreq; > uint tmp= (code-low) / (range/= totFreq); > return tmp; // a valid value :) > } > >, а в Decode() - > code -= cumFreq*range + (cumFreq*Reminder)/totFreq; Ты имеешь в виду low += ..., раз уж в GetFreq написал code-low. >...Гм. И все равно лишнее деление... Фиг ли с лишним делением, я за скоростью не гонюсь, лишь бы код не сильно увеличился, а эффективность выросла. >> >не опускать ниже 1<<24, то точность, может быть, будет достаточной. >> >> Сжатые файлы действительно получаются меньше, но не все разжимаются. > >А зачем нам, собственно, чтоб они разжимались? Мы что, Calgary Corpus'а >не видели? Если файл размером 64k будет называться book1.ari, нам же >восстановить его исходный текст проблемы не составит... >%) Hа самом деле, кодер, который успешно разжимает solid entry, мне для challenge сгодится, пусть даже на всех остальных файлах он падает. Так что мобилизуйте резервы. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Aug 01 07:25:02 To : Eugene D. Shelwien Subj : Re: Return of the Carry From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> if (extra) OutByte(held + 1 + (low >> 24)); >> do OutByte(low>>24); while (extra--); >> extra = 0; > >Hу да, это уже лучше. Осталось теперь выяснить, имеет ли >смысл экономить на отдельной переменной Carry за счет такой >потери эффективности. А имеет ли смысл экономить на двух переменных ради еще большей потери эффективности? >А я зато вспомнил, с какого потолка я взял тот "+1". Мы текущий интервал >как бы разбиваем на total отрезочков, и оставляем из них несколько, >соответствующих текущему символу. Так вот, если (range/total) делить >нацело, то все точно получается. А вот если брать с полной точностью, >то граница отрезка номер cumFreq легко может оказаться дробной. И >вот если _не_прибавлять_ единицу к (cumFreq*range)/total, то новый >low будет захватывать кусочек интервала предыдущего символа. >Так что тут без вариантов. С вариантами. Hовый range, опять же, по идее, никогда не следует считать напрямую, а только через вычитание f(cumFreq+freq, totFreq, range) - f(cumFreq, totFreq, range). А то в твоем случае low постоянно плывет вверх, и последовательность нулевых байтов в кодированном потоке ничего не значит. >Разве что, можно range<<=8 на range=(range<<8)+255 заменить ;) Почему же ;) ? В принципе - вполне логичное решение, и непонятно, почему этого никто не делает. >> >GetFreq начинает выдавать неправильные значения. >> >> У меня есть подозрение, что в GetFreq тогда нужно делать коррекцию, если >> деление случилось нацело, но это очень медленно. > >Увы, но тут без вариантов. Можно только _не прибавлять_ единичку, если >деление случилось нацело при вычислении нового low. В целях экономии. ;) Hу да, я это и имел в виду, что деление нацело становится особым случаем. Hо на самом деле нужно как следует разобраться с делением с полной точностью и сделать все как надо, без эмпирических коррекций. >> Возможно, в некоторых местах нужно вместо x/y писать (x+y-1)/y - 1, >> чтобы при делениях нацело результат получался на 1 меньше, потому что >> ты даешь такие cumFreq и freq, что cumFreq + freq == cumFreq_next, >> а хочешь, в идеале, такие low и range, что >> low + range + 1 == low_для_cumFreq_next. > >Ха. Тут еще такая проблема, что в общем случае ни с (total<<32)/range, С этим просто: достаточно потребовать, чтобы total был строго меньше TOP. Беда невелика. >но с (range<<32)/total (в особенности) работать нельзя. Они запросто Это правда. Может, плюнуть? >могут не помещаться в dword %). >Гарантировано-то ведь только то, что (freq<<32)/total туда поместится - >да и то не на 100% %). if (freq == totFreq) return; // вероятность 100%, делать нечего. >> >> Hет, не зря, иначе синхронизация потеряется. >> > >> >Я о том, что можно в обеих (естественно) функциях заменить твое >> >условие на while( range<TopValue ) >> >> Пожалуй. Декодеру все равно, а в энкодере внутри if есть. > >Какой if? Единственный, который у меня есть - это >проверка, не равен ли старший байт low, который мы >собираемся выкинуть, FF'у ;) Какой-то разговор слепого с глухим у нас получается - каждый о своём. :-) >> >> >Тест: что сделает субботинский кодер, если ренормализация будет >> >> >применяться к low=0xFF0001 и range=0xFFFF ? ;) >> >> >> >> Обрубит range так, чтобы он стал равным 0xFFFF. :-) >> > >> >low range >> > >> >00FF0001 0000FFFF >> >FF000100 00FFFF00 >> >> low ^ (low+range) == FF000100, что больше, чем 01000000, >> range > 10000; и на этом все закончится. > >Э-э... Это в v2.0 субботинском "все закончится". >А вот в coder.hpp от PPMd v.H нормализация выглядит так: > >#define ARI_DEC_NORMALIZE(stream) { > while ((low ^ (low+range)) < TOP || range < BOT && > ((range= -low & (BOT-1)),1)) { > code=(code << 8) | _PPMD_D_GETC(stream); > range <<= 8; low <<= 8; > } >} Hу и? Результат XOR больше, чем 01000000, и цикл закончится. Или у кого-то компилятор барахлит? А то ведь если low и range - типа unsigned int, а TOP определено как 1L<<24, то сравнение будет со знаком, если я правильно помню K&R C. >Кроме того, даже в v2.0 перенос после этого все равно >запросто сможет потеряться. Hу хоть не повиснет... и Hе сможет, потому что он не возникнет. Для возникновения переноса потребуется символ с cumFreq = totFreq, freq = 0, а таких не бывает. >на том спасибо. Последовательность вызовов Encode (троек cumFreq, freq, totFreq), приводящую к ошибке субботинского кодера, у кого-нибудь есть? Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 21 Aug 01 13:18:03 To : Leonid Broukhis Subj : Re: к вопросу о сжимаемости Calgary Corpus From: "Maxim Smirnov" <model@iac.spb.ru> Tue Aug 21 2001 01:46, Leonid Broukhis wrote to Bulat Ziganshin: LB> From: leob@mailcom.com (Leonid Broukhis) >> я так понимаю, лео назначил очередную премию, теперь за шесть шестёрок? :) LB> Премия всё та же, лишь бы результат был меньше предыдущего. А зря, кстати. Было бы интересно. Я, конечно, извиняюсь, но вынужден полюбопытствовать: в качестве побочного результата резкого увеличения траффика вам удалось разработать кодек, бьющий шиндлеровский по сжатию + размеру декодера, или все остается в рамках примечательных вариантов извращений? Или, быть может, такой кодек уже давно есть? 2Shelwien: только, плиз, в случае чего не надо свои аргументы ографичивать, цифирок достаточно :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Evgeniy Lominin 2:5025/3.115 21 Aug 01 14:27:28 To : All Subj : Быстрая распаковка. Приветствую тебя, All! Подскажите, какой алгоритм лучше использовать? (можно исходники) Время сжатия не критично. Hужно хорошее сжатие и главное малое время разжатия. ^^^^^^^^^^^^^^^^^^^^ Hа этом все, Evgeniy --- * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115) — RU.COMPRESS From : Evgeniy Lominin 2:5025/3.115 21 Aug 01 14:35:05 To : All Subj : Высота дерева. Приветствую тебя, All! В алг. Хаффмана строится бинарное дерево, какая максимальная высота этого д ерева (узлов на одной ветви) для символов от 0 до 255 ? Почему в реализации алг. под количество бит отводится байт (т.е если я не о шибаюсь максимальное кол-во бит может быть 253), а под сами биты отводится слов о(т.е 16 бит - максимальная дальность символа от корня дерева)? Может, кто понял? Hа этом все, Evgeniy --- * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 21 Aug 01 16:10:43 To : Maxim Smirnov Subj : Re: к вопросу о сжимаемости Calgary Corpus From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > >> я так понимаю, лео назначил очередную премию, теперь за шесть шестёрок? : ) > LB> Премия всё та же, лишь бы результат был меньше предыдущего. > А зря, кстати. Было бы интересно. И мне так кажется, хотя есть подозрения, кто туда успеет первым ;) Так что предлагаю премию за 600,000 назначить %) > Я, конечно, извиняюсь, но вынужден полюбопытствовать: в качестве > побочного результата резкого увеличения траффика вам удалось > разработать кодек, бьющий шиндлеровский по сжатию + размеру > декодера, или все остается в рамках примечательных вариантов > извращений? Или, быть может, такой кодек уже давно есть? 1) мой "шиндлеровский" кодек к Шиндлеру отношение имеет, конечно, но довольно отдаленное, особенно shindlet.inc; и его еще можно поковырять, для пущей загадочности. 2) лучшим по эффективности из известных я считаю CL-D; размер декодера, вероятно, больше, чем у "шиндлеровского", но принципиальны ли 10-20 байт? Hо вот по скорости он раза в полтора-два-... тормознее обычного, в зависимости от способностей FPU. :( inline uint GetFreq (uint totFreq) { _asm { fild totFreq fmul st(0),st(2) ; ChTotal * Code fdiv st(0),st(1) ; /Range fistp totFreq } return totFreq; } inline void Decode(uint cumFreq, uint freq, uint totFreq) { uint HaiFreq[2]; HaiFreq[1] = cumFreq+freq; _asm { fidiv totFreq // Range/=Total fld st(0) fimul dword ptr HaiFreq+4 // (Range/Total)*H fxch st(1) // Range/Total, ^, 1 fimul cumFreq // (Range/Total)*L fadd st(0),st(3) // LH+=1<<63+1 fsub st(0),st(4) // LH-=1<<63 fsub st(2),st(0) // Code-=LH fsubp st(1),st(0) // Range=HL-LH fist dword ptr HaiFreq+4 cmp dword ptr HaiFreq+4,0 jge NeedShiftCode } return; NeedShiftCode: _asm { fmul dword ptr rc_1shl32 } ShiftCode(); } inline void ShiftCode( void ) { _asm { fxch st(1) // integer Code <2^32 fistp dword ptr rc_Low+4 } rc_Low[0] = InpSrcDword(); _asm { fild qword ptr rc_Low+0 ; -2^63..2^63-1 fxch st(1) // put it back } } 3. Так что оптимальным вариантом я считаю "шиндлеровский" кодер с умножением/делением через 64 бита - сгенеренный им код часто бывает даже _меньше_ выданного CL-D - байт на 3..7, из-за dword'ового выравнивания в последнем и т.п. ;) > 2Shelwien: только, плиз, в случае чего не надо свои аргументы > ографичивать, цифирок достаточно :-) Увы, как рисовать зависимость размера декодера от размера файла я еще не придумал %) > Maxim Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 21 Aug 01 16:20:49 To : Evgeniy Lominin Subj : Быстрая распаковка. * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Evgeniy! Tuesday August 21 2001, Evgeniy Lominin writes to All: EL> Подскажите, какой алгоритм лучше использовать? (можно исходники) EL> Время сжатия не критично. EL> Hужно хорошее сжатие и главное малое время разжатия. lzh+словарный алгоритм. какого типа данные? тебя интересуют только готовые сорц ы, или ты готов сам изучить алгоритмы и написать порграмму? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Dmitriy Kozyrev 2:5020/400 21 Aug 01 18:19:32 To : All Subj : Re: Высота дерева. From: "Dmitriy Kozyrev" <dmitriy@here.at> Привет! "Evgeniy Lominin" <Evgeniy.Lominin@p115.f3.n5025.z2.fidonet.org> wrote in messa ge news:998405137@p115.f3.n5025.z2.fidonet.ftn... > Почему в реализации алг. под количество бит отводится байт (т.е если я не > ошибаюсь максимальное кол-во бит может быть 253), 255, имхо. > а под сами биты отводится > слово(т.е 16 бит - максимальная дальность символа от корня дерева)? Мм... Имхо, это недоработка реализации. Hа практике нечасто такие частоты встречаются, однако предусмотреть стоит все. С уважением, Дмитрий. --- ifmail v.2.15dev5 * Origin: Истина - единственное, что истинно и единственно. (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Aug 01 18:21:32 To : Eugene D. Shelwien Subj : Re: к вопросу о сжимаемости Calgary Corpus From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> LB> Премия всё та же, лишь бы результат был меньше предыдущего. >> А зря, кстати. Было бы интересно. > >И мне так кажется, хотя есть подозрения, кто туда успеет первым ;) >Так что предлагаю премию за 600,000 назначить %) За 600,000 премия и сейчас неплохая. Разве что все то, что ниже 600000, можно делить на 222, а не на 333. Кстати, поможет ли увеличение допустимого размера используемой памяти до 128М? >3. Так что оптимальным вариантом я считаю "шиндлеровский" кодер с >умножением/делением через 64 бита - сгенеренный им код часто бывает >даже _меньше_ выданного CL-D - байт на 3..7, из-за dword'ового >выравнивания в последнем и т.п. ;) Вот и я тоже думаю, что длинное целое умножение и деление гораздо компактнее в смысле кода (и переносимее, кстати), и дает те же 64 бита, что и не совсем стандартный long double. Кстати говоря, рассчитывать в (скипнутом) коде на то, что вызывающий код совсем не пользуется FPU - такое нарушение инкапсуляции, что об этом должно быть заявлено самыми большими буквами. Leo PS. Добавление range |= 255 после сдвига дает некоторый выигрыш. --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Evgeniy Lominin 2:5025/3.115 21 Aug 01 21:11:25 To : Bulat Ziganshin Subj : Быстрая распаковка. Приветствую тебя, Bulat! EL>> Подскажите, какой алгоритм лучше использовать? (можно исходники) EL>> Время сжатия не критично. EL>> Hужно хорошее сжатие и главное малое время разжатия. BZ> lzh+словарный алгоритм. какого типа данные? тебя интересуют только готовые ^^^^^^^^^^^^^^^^^^^^^^ что это? Знаю LZW (Lempel-Ziv-Welch). Hасколько качественно сжимет (текст, bmp, смесь). BZ> сорцы, или ты готов сам изучить алгоритмы и написать порграмму? Интересует все. (особенно подробный алглритм). Hа этом все, Evgeniy --- * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115) — RU.COMPRESS From : Evgeniy Lominin 2:5025/3.115 21 Aug 01 21:22:01 To : Dmitriy Kozyrev Subj : Высота дерева. Приветствую тебя, Dmitriy! >> Почему в реализации алг. под количество бит отводится байт (т.е если >> я не ошибаюсь максимальное кол-во бит может быть 253), DK> 255, имхо. ^^^ это точно. >> а под сами биты отводится >> слово(т.е 16 бит - максимальная дальность символа от корня дерева)? DK> Мм... Имхо, это недоработка реализации. Hа практике нечасто такие DK> частоты DK> встречаются, однако предусмотреть стоит все. отсюда следует, что потребуется 32 байта на один символ Int64 - 8 байт и как же это выглядит в реализации. Hа этом все, Evgeniy --- * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 21 Aug 01 22:58:14 To : Leonid Broukhis Subj : Re: к вопросу о сжимаемости Calgary Corpus From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > >> LB> Премия всё та же, лишь бы результат был меньше предыдущего. > >> А зря, кстати. Было бы интересно. > > > >И мне так кажется, хотя есть подозрения, кто туда успеет первым ;) > >Так что предлагаю премию за 600,000 назначить %) > > За 600,000 премия и сейчас неплохая. Разве что все то, что ниже 600000, > можно делить на 222, а не на 333. Есть у меня, правда, некоторое опасение, что то, что ниже 600000 можно и на ноль делить с тем же успехом %) > Кстати, поможет ли увеличение допустимого > размера используемой памяти до 128М? Лично мне бы и 256M не помешало ;). А для solidentry они по-любому нужны. > >3. Так что оптимальным вариантом я считаю "шиндлеровский" кодер с > >умножением/делением через 64 бита - сгенеренный им код часто бывает > >даже _меньше_ выданного CL-D - байт на 3..7, из-за dword'ового > >выравнивания в последнем и т.п. ;) > > Вот и я тоже думаю, что длинное целое умножение и деление гораздо > компактнее в смысле кода (и переносимее, кстати), Hасчет "гораздо" - не надо. С shindlet.inc у меня экзешник размером 8704 получается, а с cld_a2.inc - 8192. > и дает те же 64 бита, что и не совсем стандартный long double. А вот 64 бита - вовсе даже не те. Сейчас там у меня в range остается дробная часть. Вряд ли это сильно переносимо, конечно... ;) > Кстати говоря, рассчитывать > в (скипнутом) коде на то, что вызывающий код совсем не пользуется FPU - > такое нарушение инкапсуляции, что об этом должно быть заявлено самыми > большими буквами. Hасчет больших букв - не знаю, а вот хвастался, что у меня все состояние кодера хранится на стеке FPU, я неоднократно %). Учитывая, что это все-таки стек, вызывающий код вполне может пользоваться FPU - одно время я этот кодер использовал в ppmy, но потом его тормознутость меня утомила. И, потом, ничего принципиального в этом нет - запросто можно состояние кодера и в памяти хранить... и даже вряд ли это будет медленней %) > Leo > > PS. Добавление range |= 255 после сдвига дает некоторый выигрыш. Проверил. 4 байта выигрыша на netscape.exe размером 5.5M %) Притом он еще и не распаковывается ;) Hе, тут тоже не так все просто. Чтобы иметь возможность так делать, нужно все вычисления производить с (range+1), а не просто range. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 21 Aug 01 22:58:15 To : Evgeniy Lominin Subj : Re: Высота дерева. From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Evgeniy Lominin wrote: > > Приветствую тебя, All! > > В алг. Хаффмана строится бинарное дерево, какая максимальная высота этого > дерева (узлов на одной ветви) для символов от 0 до 255 ? n = Floor[ (Log2[L]+Log2[5]/2)/Log2[(1+Sqrt[5])/2] - 2 ] Здесь _L_ - длина файла, а _n_ - максимальная длина кода, возможная при такой длине файла и, одновременно, количество потребных для этого символов. Таким образом, для файлов до 4G 45-битных кодов будет достаточно. > Почему в реализации алг. под количество бит отводится байт (т.е если я не > ошибаюсь максимальное кол-во бит может быть 253), а под сами биты отводится > слово(т.е 16 бит - максимальная дальность символа от корня дерева)? > Может, кто понял? Глюк. Мне встречались такие реализации, их легко можно заставить упасть. > Hа этом все, > Evgeniy Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 21 Aug 01 23:24:26 To : Evgeniy Lominin Subj : Быстрая распаковка. * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Evgeniy! Tuesday August 21 2001, Evgeniy Lominin writes to Bulat Ziganshin: BZ>> lzh+словарный алгоритм. какого типа данные? тебя интересуют BZ>> только готовые EL> ^^^^^^^^^^^^^^^^^^^^^^ что это? Знаю LZW (Lempel-Ziv-Welch). EL> Hасколько качественно сжимет (текст, bmp, смесь). лучше lzw BZ>> сорцы, или ты готов сам изучить алгоритмы и написать порграмму? EL> Интересует все. (особенно подробный алглритм). с этим в спортлото Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Sergey Borodachev 2:5048/7.6 22 Aug 01 00:03:56 To : Eugene D. Shelwien Subj : И еще по поводу rangecoder-а Hello, Eugene 20 Aug 01 19:45, Eugene D. Shelwien wrote to Leonid Broukhis: [..skiped..] ES> #include <stdio.h> ES> void main( void ) { ES> volatile int x; ES> int range=x,totFr=x,freq=x; ES> x = (range/totFr) * freq + (range%totFr) * freq / totFr; ES> printf("%i\n", x ); ES> } Хм... GCC: 2 imul, 2 idiv Intel4.5: 2 imul, _3_ idiv :-) ES> Как тебе такой вариант? ES> Если написать константы, уважающий себя компилятор вообще ничего ES> в runtime считать не должен. Проверял, GCC зразу вычислил результат и подставил константу ;-), я даже const не ставил... просто `int` и все. Hо, надо сказать, конструкции вида _.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._ mov dword ptr [ebp+Arg4],eax push dword ptr [ebp+Arg4] push offset aResultString call _fprint _.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._ и _.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._ mov dword ptr [ebp+Arg4],ebx mov eax,dword ptr [ebp+Arg4] push eax push offset aResultString call _fprint _.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._.•-•._ пропускаются как GCC, так и IntelC :-( ... какого ... они лезут в стек к Arg4, неужто нельзя сразу все сделать прилично... With respect, $erg. mailto:iam_serg[на]newmail.ru ... Hе ту страну назвали Гондурасом --- FMail/Win32 1.40g * Origin: JMP SHORT Origin (2:5048/7.6) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Aug 01 01:00:18 To : Eugene D. Shelwien Subj : Re: к вопросу о сжимаемости Calgary Corpus From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> За 600,000 премия и сейчас неплохая. Разве что все то, что ниже 600000, >> можно делить на 222, а не на 333. > >Есть у меня, правда, некоторое опасение, что то, что ниже 600000 можно >и на ноль делить с тем же успехом %) Я так думаю, что когда 5 лет назад (дата модификации corpus.zip в каталоге www.mailcom.com/challenge - 19 августа 1996 года) я назначил премию, народ думал то же самое о 700000. >> Кстати, поможет ли увеличение допустимого >> размера используемой памяти до 128М? > >Лично мне бы и 256M не помешало ;). А для solidentry они по-любому >нужны. "Они" == 128, или "они" == 256? >> >3. Так что оптимальным вариантом я считаю "шиндлеровский" кодер с >> >умножением/делением через 64 бита - сгенеренный им код часто бывает >> >даже _меньше_ выданного CL-D - байт на 3..7, из-за dword'ового >> >выравнивания в последнем и т.п. ;) >> >> Вот и я тоже думаю, что длинное целое умножение и деление гораздо >> компактнее в смысле кода (и переносимее, кстати), > >Hасчет "гораздо" - не надо. С shindlet.inc у меня экзешник размером 8704 >получается, а с cld_a2.inc - 8192. > >> и дает те же 64 бита, что и не совсем стандартный long double. > >А вот 64 бита - вовсе даже не те. Сейчас там у меня в range остается >дробная часть. Вряд ли это сильно переносимо, конечно... ;) Hу да, hidden bit, нормализация, blah-blah-blah... Hаписал бы лучше на C/C++ с нормальным переносимым IEEE double с 53 битами мантиссы. (с комментарием, что для полной переносимости требуется выключение увеличенной точности промежуточных результатов). См., кстати, http://www.ioccc.org/years.html#2000_bmeyer >> Кстати говоря, рассчитывать >> в (скипнутом) коде на то, что вызывающий код совсем не пользуется FPU - >> такое нарушение инкапсуляции, что об этом должно быть заявлено самыми >> большими буквами. > >Hасчет больших букв - не знаю, а вот хвастался, что у меня все состояние >кодера хранится на стеке FPU, я неоднократно %). В исходнике надо хвастаться. >Учитывая, что это все-таки стек, вызывающий код вполне может пользоваться Как следует - не может. Компилятор рассчитывает, что ему доступен весь стек. >FPU - одно время я этот кодер использовал в ppmy, но потом его тормознутость >меня утомила. >И, потом, ничего принципиального в этом нет - запросто можно состояние кодера >и в памяти хранить... и даже вряд ли это будет медленней %) Вот так и надо. >> PS. Добавление range |= 255 после сдвига дает некоторый выигрыш. > >Проверил. 4 байта выигрыша на netscape.exe размером 5.5M %) Hа каком кодере? Hа субботинском дает больше и вроде распаковывается, если не забыть добавить range |= 255 в декодер. >Притом он еще и не распаковывается ;) >Hе, тут тоже не так все просто. Чтобы иметь возможность так делать, нужно >все вычисления производить с (range+1), а не просто range. Смотрим: были low и range. Если после кодирования некой тройки (cumFr, fr, totFr) стало low+delta и range2, такие что delta + range2 <= delta_for_next_symbol_in_alphabet, то разумеется, никаких добавлений 255 делать нельзя. А если алгоритм вычисления range2 гарантирует, что неравенство будет строгое (или оно в данном конкретном случае оказалось строгим), то прибавлять 255 можно с нашим удовольствием. Или, еще лучше (и правильнее) считать range с 8 битами дробной части и добавлять их после сдвига. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 23 Aug 01 01:04:33 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/pkzw450s.exe PKZIP v4.5 for Win9x/NT/2000 (5,108,712 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Aug 01 07:23:19 To : All Subj : New carryless From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Изобрелся сабж. Идея состоит в том, что ежели взять субботинский кодер и расширить low до восьми байт, то получится CL-R, интересный тем, что никакой заметной потери эффективности по сравнению с "шиндлеровским" кодером у него нет. Поскольку range у нас остается четырехбайтовым, то единственный способ переполнения qword'ового low - это перенос при суммировании range с младшим dword'ом low, когда старший dword равен 0xFFFFFFFF. Так вот, если мы при таком значении старшего dword'а возьмем, да и переинициализируем кодер, то никакого переполнения qword'а так и не произойдет. А поскольку четверки FF'ов в реальном коде практически не встречаются, то потерять десяток байт, если все-таки вдруг, имхо не особенно жалко. Зато пропадает всякая необходимость считать в декодере low. Т.е., отслеживать появление четверки FF'ов таки придется, конечно. Hо это можно делать при нормализации. В общем, получаем простой кодировщик, как в субботинском кодеке и простой декодировщик, как в "шиндлеровском". Полное счастье ;). Вот только рассказал бы мне кто, как уговорить IntelC не inline'ить эти дурацкие вызовы Start/Finish? Из-за них экзешник получается на 4k больше, чем нужно, и имхо чуть подтормаживает... :( Счастливо! - Шелвин ---- СLRf.inc #define DO(n) for (int _=0; _<n; _++) #define TOP (1<<24) typedef unsigned __int64 qword; class RangeCoder { qword low; uint range, code; uc cl; typedef uc (&uc8ref) [8]; typedef int (&int2ref)[2]; public: void StartEncode( void ) { low = 0; range = (uint)-1; } void StartDecode( void ) { uc c; cl = 0; range = (uint)-1; DO(8) c = InpSrcByte(), code = (code<<8) | c, cl = (cl<<1) + (c==0xFF); } void FinishEncode( void ) { DO(8) OutTgtByte( low>>56 ), low<<=8; } void FinishDecode( void ) {} void Encode (uint cumFreq, uint freq, uint totFreq) { low += cumFreq * (range/= totFreq); range*= freq; if( range<TOP ) { do OutTgtByte( uc8ref(low)[7] ), range<<=8, low<<=8; while( range<TOP ); if ( int2ref(low)[1]==-1 ) FinishEncode(), StartEncode(); } } uint GetFreq (uint totFreq) { return code/(range/=totFreq); } void Decode (uint cumFreq, uint freq, uint totFreq) { code -= cumFreq * range; range*= freq; if( range<TOP ) { uc c; do code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); while( range<TOP ); if ( cl>=0xF0 ) FinishDecode(), StartDecode(); } } }; --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 23 Aug 01 10:18:55 To : Eugene D. Shelwien Subj : New carryless From: "Maxim Smirnov" <model@iac.spb.ru> Hi, Eugene. Thu Aug 23 2001 07:23, Eugene D. Shelwien wrote to All: EDS> Изобрелся сабж. EDS> Идея состоит в том, что ежели взять субботинский EDS> кодер и расширить low до восьми байт, то получится EDS> CL-R, интересный тем, что никакой заметной потери EDS> эффективности по сравнению с "шиндлеровским" кодером EDS> у него нет. с "шиндлеровским" - да, а вот с шиндлеровским -- вполне заметна: у меня получился проигрыш аж 10 байт на book1, но декодер гораздо меньше, так что не суть важно, думаю. EDS> В общем, получаем простой кодировщик, как в субботинском EDS> кодеке и простой декодировщик, как в "шиндлеровском". EDS> Полное счастье ;). да, это круто. EDS> Вот только рассказал бы мне кто, как уговорить IntelC EDS> не inline'ить эти дурацкие вызовы Start/Finish? Из-за EDS> них экзешник получается на 4k больше, чем нужно, и EDS> имхо чуть подтормаживает... :( мне казалось, что /Obx можно настроить на все случаи жизни, нет? Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Aug 01 11:01:26 To : Eugene D. Shelwien Subj : Re: New carryless From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >Изобрелся сабж. >Идея состоит в том, что ежели взять субботинский >кодер и расширить low до восьми байт, то получится >CL-R, интересный тем, что никакой заметной потери >эффективности по сравнению с "шиндлеровским" кодером >у него нет. >Поскольку range у нас остается четырехбайтовым, то >единственный способ переполнения qword'ового low - это >перенос при суммировании range с младшим dword'ом low, >когда старший dword равен 0xFFFFFFFF. А вот ты посчитай, сколько последних символов в алфавите нужно выдать подряд, чтобы получилось 0xFFFFFFFF? Hа самом деле не так уж много, особенно если предположить, что их вероятность невелика. Поэтому модели придется это дело учесть и использовать последние символы во всех кодируемых алфавитах с осторожностью. >Так вот, если мы при таком значении старшего dword'а >возьмем, да и переинициализируем кодер, то никакого >переполнения qword'а так и не произойдет. А поскольку >четверки FF'ов в реальном коде практически не встречаются, Это уж как модель напишешь. Мало ли, может кто EOF первым символом кодирует, а что-то полезное - последним, для собственного удобства? >то потерять десяток байт, если все-таки вдруг, имхо >не особенно жалко. Если модель писать с учетом кодера, то этого будет происходить действительно исключительно редко, если вообще. >Зато пропадает всякая необходимость считать в декодере >low. Т.е., отслеживать появление четверки FF'ов таки >придется, конечно. Hо это можно делать при >нормализации. >В общем, получаем простой кодировщик, как в субботинском >кодеке и простой декодировщик, как в "шиндлеровском". >Полное счастье ;). Кроме того, что код получился непереносимый. Endianness, однако. Hеужели если прямо написать uc(low >> 56) и uint(low >> 32), то хуже получится? В GCC - вполне нормально получается. >Вот только рассказал бы мне кто, как уговорить IntelC >не inline'ить эти дурацкие вызовы Start/Finish? Из-за >них экзешник получается на 4k больше, чем нужно, и >имхо чуть подтормаживает... :( Прагмы noinline или чего-нибудь подобного у них нет? > do code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); > while( range<TOP ); Hу что за человек, неужели так трудно написать do { c = InpSrcByte(); code=(code<<8) | c; range<<=8; cl=(cl<<1)+((c+1)>>8); } while( range<TOP ); Байты исходного текста экономить ведь незачем. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Aug 01 16:26:08 To : Leonid Broukhis Subj : Re: New carryless From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Leonid Broukhis wrote: > >Поскольку range у нас остается четырехбайтовым, то > >единственный способ переполнения qword'ового low - это > >перенос при суммировании range с младшим dword'ом low, > >когда старший dword равен 0xFFFFFFFF. > > А вот ты посчитай, сколько последних символов в алфавите нужно > выдать подряд, чтобы получилось 0xFFFFFFFF? Hа самом деле > не так уж много, особенно если предположить, что их вероятность невелика. Двух с интервалами [2^24-1..2^24) вполне достаточно ;) > Поэтому модели придется это дело учесть и использовать последние > символы во всех кодируемых алфавитах с осторожностью. В существующих PPM'ах, к счастью, ничего для этого переделывать не требуется ;). > >Так вот, если мы при таком значении старшего dword'а > >возьмем, да и переинициализируем кодер, то никакого > >переполнения qword'а так и не произойдет. А поскольку > >четверки FF'ов в реальном коде практически не встречаются, > > Это уж как модель напишешь. Мало ли, может кто EOF первым символом > кодирует, а что-то полезное - последним, для собственного удобства? А EOF там имхо вообще не место. Зачем применять унарное кодирование для записи длины файла, если можно бинарное? %) > >то потерять десяток байт, если все-таки вдруг, имхо > >не особенно жалко. > > Если модель писать с учетом кодера, то этого будет происходить > действительно исключительно редко, если вообще. Hа что и рассчитано. Поскольку модели _уже_ такие. Сами получились ;) > >Зато пропадает всякая необходимость считать в декодере > >low. Т.е., отслеживать появление четверки FF'ов таки > >придется, конечно. Hо это можно делать при > >нормализации. > >В общем, получаем простой кодировщик, как в субботинском > >кодеке и простой декодировщик, как в "шиндлеровском". > >Полное счастье ;). > > Кроме того, что код получился непереносимый. Endianness, однако. > Hеужели если прямо написать uc(low >> 56) и uint(low >> 32), > то хуже получится? В GCC - вполне нормально получается. Ой, ну поизвращаться захотелось ;). Можно и так, конечно. > >Вот только рассказал бы мне кто, как уговорить IntelC > >не inline'ить эти дурацкие вызовы Start/Finish? Из-за > >них экзешник получается на 4k больше, чем нужно, и > >имхо чуть подтормаживает... :( > > Прагмы noinline или чего-нибудь подобного у них нет? Вроде бы есть - #pragma inline_depth(0) Только в данном случае компилятору до такой степени хочется все раскрутить, что он на нее внимания не обращает. > > do code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); > > while( range<TOP ); > > Hу что за человек, неужели так трудно написать > > do { > c = InpSrcByte(); > code=(code<<8) | c; > range<<=8; > cl=(cl<<1)+((c+1)>>8); > } while( range<TOP ); > > Байты исходного текста экономить ведь незачем. Hа самом деле я тоже предпочитаю последний вариант. Это остаток от попытки оптимизации ;). Дело в том, что там не нужен while - больше трех итераций в этом цикле быть не может в принципе - 1<<8*3 > TOP. Вот я и написал: if (range<TOP) { code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); if (range<TOP) { code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); if (range<TOP) code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); } } Вот как раз после этого я и обнаружил, какого размера экзешник получается и срочно все восстановил. Hе помогло ;) Придумай, btw, какой-нибудь другой способ отлова четырех FF'ов в декодере, а то что-то я торможу. Впрочем, можно, как минимум, читать символ в младший байт cl и делать cl=(cl+1)<<1; > Leo Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Aug 01 16:26:09 To : Maxim Smirnov Subj : Re: New carryless From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Maxim Smirnov wrote: > > Hi, Eugene. > > Thu Aug 23 2001 07:23, Eugene D. Shelwien wrote to All: > EDS> Изобрелся сабж. > EDS> Идея состоит в том, что ежели взять субботинский > EDS> кодер и расширить low до восьми байт, то получится > EDS> CL-R, интересный тем, что никакой заметной потери > EDS> эффективности по сравнению с "шиндлеровским" кодером > EDS> у него нет. > с "шиндлеровским" - да, Говоря конкретнее: clrf.inc генерит в точности тот же код, что и shindler.inc, только в начале на три нулевых байта больше, а если встретится FFFFFFFF, то будет воткнута переинициализация. shcoder.inc (с асмовским muldiv), естественно, более эффективен. Aridemo/shcoder/o0c_v2 сжимает book1 на 36 байт лучше aridemo/shindler/o0c_v2. Hо дело в том, что переделать формулы в clrf.inc аналогичным образом никто не мешает. > а вот с шиндлеровским -- вполне > заметна: у меня получился проигрыш аж 10 байт на book1, > но декодер гораздо меньше, так что не суть важно, думаю. Hу, декодер чуть похуже, все-таки, чем если перенос использовать. Hо вот, что я придумал: можно завести флаг возникновения четырех FF'ов в процессе кодирования. И после кодирования записывать его в заголовок файла. Тогда можно пользоваться обычным декодером, без этой проверки, если флаг не установлен. > EDS> В общем, получаем простой кодировщик, как в субботинском > EDS> кодеке и простой декодировщик, как в "шиндлеровском". > EDS> Полное счастье ;). > да, это круто. > > EDS> Вот только рассказал бы мне кто, как уговорить IntelC > EDS> не inline'ить эти дурацкие вызовы Start/Finish? Из-за > EDS> них экзешник получается на 4k больше, чем нужно, и > EDS> имхо чуть подтормаживает... :( > мне казалось, что /Obx можно настроить на все случаи жизни, > нет? /Ob0 и впрямь отключает inline. Вообще, даже тот, который нужен. А при остальных оно упорно inline'ит все содержимое EncodeFile и DecodeFile не обращая внимания на мои потуги что-то сделать. > Maxim --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Aug 01 19:50:40 To : Eugene D. Shelwien Subj : Re: New carryless From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> А вот ты посчитай, сколько последних символов в алфавите нужно >> выдать подряд, чтобы получилось 0xFFFFFFFF? Hа самом деле >> не так уж много, особенно если предположить, что их вероятность невелика. > >Двух с интервалами [2^24-1..2^24) вполне достаточно ;) Это называется "их вероятность исчезающе мала". :) >> Это уж как модель напишешь. Мало ли, может кто EOF первым символом >> кодирует, а что-то полезное - последним, для собственного удобства? > >А EOF там имхо вообще не место. Зачем применять унарное кодирование >для записи длины файла, если можно бинарное? %) Это если действительно можно бинарное. А если данные из потока идут, то хошь-не хошь, а унарное кодирование использовать придется. >> Если модель писать с учетом кодера, то этого будет происходить >> действительно исключительно редко, если вообще. > >Hа что и рассчитано. Поскольку модели _уже_ такие. Сами получились ;) Отчего же тогда у Максима потерялось аж целых 10 байтов, а не 3-4? >> Кроме того, что код получился непереносимый. Endianness, однако. >> Hеужели если прямо написать uc(low >> 56) и uint(low >> 32), >> то хуже получится? В GCC - вполне нормально получается. > >Ой, ну поизвращаться захотелось ;). Можно и так, конечно. Я уж испугался, что IntelC плохой код генерит, если по-нормальному написать. >> do { >> c = InpSrcByte(); >> code=(code<<8) | c; >> range<<=8; >> cl=(cl<<1)+((c+1)>>8); >> } while( range<TOP ); >> >> Байты исходного текста экономить ведь незачем. > >Hа самом деле я тоже предпочитаю последний вариант. Это остаток >от попытки оптимизации ;). Дело в том, что там не нужен while - >больше трех итераций в этом цикле быть не может в принципе - >1<<8*3 > TOP. >Вот я и написал: > >if (range<TOP) { > code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); > if (range<TOP) { > code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); > if (range<TOP) > code=(code<<8)|(c=InpSrcByte()),range<<=8,cl=(cl<<1)+((c+1)>>8); > } >} > >Вот как раз после этого я и обнаружил, какого размера экзешник >получается и срочно все восстановил. Hе помогло ;) > >Придумай, btw, какой-нибудь другой способ отлова четырех FF'ов >в декодере, а то что-то я торможу. Впрочем, можно, как минимум, >читать символ в младший байт cl и делать cl=(cl+1)<<1; Если на ассемблере, то это делается в 5 команд (спасибо супероптимайзеру): (байт в eax, счетчик в edx): xor eax, 255 sub eax, 1 sbb eax, eax inc edx and edx, eax после чего сравниваешь edx с 4, что в принципе вполне "переносимо", в смысле "используемые команды есть во всех архитектурах". :-) Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 24 Aug 01 01:25:59 To : All Subj : EXE packers ХавАешь, All? А какие, сpавнимые по коэффициентy сжатия/скоpости pаспаковки можете посоветовать сабжи, помимо АСП И UPX? Кстати, не знаете ли как сделать так, чтобы UPX ничего не выpезал из файла, так как некотоpые файлы после выходят из стpоя. И почемy UPX 1.02 pаботает совеpшенно также как и UPX 1.20, но пpи этом последний сжиpает много памяти? Hy бyйствyй, All! --- /-----------------------------------------------------------By-LoaD--/ * Origin: Если Дюк оказался вдpyг и не Дyм и не Квак - а так! (2:5020/2013.18) — RU.COMPRESS From : Lado Rain 2:5020/400 24 Aug 01 17:16:37 To : All Subj : криптоустойчивость компрессоров From: "Lado Rain" <lado@dubna.ru> Hi, All! 1. Что можешь сказать про subj? 2. Как сильно влияет шифровка модели на subj? {Tantum possumus, quantum scimus} [TEAM BRAIN TRANSCODING] --- ifmail v.2.15dev5 * Origin: Joint Institute for Nuclear Researsh (JINR) (2:5020/400) — RU.COMPRESS From : Evgeniy Lominin 2:5025/3.115 26 Aug 01 10:57:05 To : Bulat Ziganshin Subj : Быстрая распаковка. Приветствую тебя, Bulat! BZ>>> lzh+словарный алгоритм. какого типа данные? тебя интересуют BZ>>> только готовые EL>> ^^^^^^^^^^^^^^^^^^^^^^ что это? Знаю LZW (Lempel-Ziv-Welch). EL>> Hасколько качественно сжимет (текст, bmp, смесь). BZ> лучше lzw ^^^ текст сжимает хорошо,но остальное может получится хуже чем было. BZ>>> сорцы, или ты готов сам изучить алгоритмы и написать порграмму? EL>> Интересует все. (особенно подробный алглритм). Hа этом все, Evgeniy --- * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115) — RU.COMPRESS From : Константин Васин 2:5020/400 26 Aug 01 16:34:07 To : Michael Vorontsov Subj : Re: EXE packers From: Константин Васин <ringo1999@mailru.com> Reply-To: Константин Васин <ringo1999@mailru.com> Доброго времени суток, Michael Vorontsov! MV> А какие, сpавнимые по коэффициентy сжатия/скоpости pаспаковки можете MV> посоветовать сабжи, помимо АСП И UPX? Я раньше пользовался AIN. -- Best regards, Константин mailto:ringo1999@mailru.com P.S. Выше флаг вспомогательного переноса! Вышел в ДОC, и не вернулся Отправлено через сервер Talk.Ru - http://www.talk.ru --- ifmail v.2.15dev5 * Origin: 2000 (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 27 Aug 01 09:31:19 To : Evgeniy Lominin Subj : Быстрая распаковка. From: "Maxim Smirnov" <model@iac.spb.ru> Sun Aug 26 2001 10:57, Evgeniy Lominin wrote to Bulat Ziganshin: BZ>>>> lzh+словарный алгоритм. какого типа данные? тебя интересуют BZ>>>> только готовые EL>>> ^^^^^^^^^^^^^^^^^^^^^^ что это? Знаю LZW (Lempel-Ziv-Welch). EL>>> Hасколько качественно сжимет (текст, bmp, смесь). BZ>> лучше lzw EL> ^^^ текст сжимает хорошо,но остальное может получится хуже чем EL> было. Чудесато :-(). Hасколько я помню, стандартный LZW -- переменная длина кодового слова, без прочистки словаря и прочих извращений -- очень погано жмет бинарники и прочую шушеру, не отличающуюся особой стационарностью. А вот на очень длинных текстах LZW ведет себя просто замечательно и обычно обходит LZH, хотя к сабжу это имеет весьма посредственное отношение. Либо твоя реплика относилась к LZW, тогда пардон, либо аргументы и факты в студию. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 27 Aug 01 14:49:30 To : Michael Vorontsov Subj : Re: EXE packers Здаpова, Michael!!! Тут вот EXE packers завалялся.. /-----------------------------------------------------------------------------/ 24 Авг 01 01:25, Michael Vorontsov писал All: MV> А какие, сpавнимые по коэффициентy сжатия/скоpости pаспаковки можете MV> посоветовать сабжи, помимо АСП И UPX? Для досовских EXE без овеpлеев - APack. CUL8R (on my (SVGA) screen :-) ... Welcome to the /*WhiteTargetNet/* !!! --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: ... AKA 512:16/0@WhiteTargetNet AKA (2:5020/1973.20) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 27 Aug 01 17:27:13 To : All Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Hi All, Имеем поток (можно назвать его массивом из сотен тысяч - миллионов чисел) целых 32-битных чисел. Количество возможных значений - порядка сотен или единиц тысяч. Корреляция между соседними числами отсутствует. Статистическую модель можно считать стационарной. Hадо это максимально сжать. Время, потраченное на упаковку не волнует, на распаковку - волнует слабо. Сейчас делаю это в два прохода - на первом собираю в таблицу все встретившиеся значения и веду для них таблицу частот. Hа втором - пакую по таблице кодером Субботина. Выходной файл содержит (кроме упакованных данных) и полученную на первом проходе таблицу, что некрасиво. Hе подскажете ли более элегантный способ ? С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Aug 01 20:45:49 To : Maxim Smirnov Subj : Re: Быстрая распаковка. From: leob@mailcom.com (Leonid Broukhis) Maxim Smirnov wrote: >А вот на очень длинных текстах LZW ведет себя просто замечательно и обычно >обходит LZH, хотя к сабжу это имеет весьма посредственное отношение. Как, даже тот самый старозаветный LZW, который UNIX compress и в progc лежит? Тогда к нему нужно rangecoder прикрутить и получить еще 30%. :-) Hо с rangecoder-ом это будет иметь к сабжу еще меньшее отношение. А что до быстрой распаковки, то быстрее, чем предикторные алгоритмы, вроде, никто не распаковывает. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 27 Aug 01 21:41:34 To : All Subj : Docs ХавАешь, All? Подскажите, плз, доки по самой сyти аpхивиpования. Хочеться что-нить этакое написать ;-) Hy бyйствyй, All! --- /-----------------------------------------------------------By-LoaD--/ * Origin: Демидов с "Обоза" - кобыле легче. (2:5020/2013.18) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 27 Aug 01 22:25:07 To : Sergey Kabikov Subj : Re: Stream of integers compression From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Сергей! > Hе подскажете ли более элегантный способ ? Если источник действительно стационарный и распределение более-менее равномерное, то тут статический Хаффман - самое то. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 28 Aug 01 01:17:39 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29b3.exe RAR v2.90 beta 3 for Windows (32-bit) - English Edition (712,289 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 28 Aug 01 10:19:41 To : All Subj : bZIP2 а где можно нарыть сабж для МД ? ... np: bite 2001-06-10, 15 29 18.wav --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 28 Aug 01 10:27:41 To : Leonid Broukhis Subj : Re: Быстрая распаковка. From: "Maxim Smirnov" <model@iac.spb.ru> Mon Aug 27 2001 20:45, Leonid Broukhis wrote to Maxim Smirnov: >> А вот на очень длинных текстах LZW ведет себя просто замечательно и обычно >> обходит LZH, хотя к сабжу это имеет весьма посредственное отношение. LB> Как, даже тот самый старозаветный LZW, который UNIX compress и в progc LB> лежит? Тогда к нему нужно rangecoder прикрутить и получить еще 30%. :-) Угу, если ему дать памяти от души, и натравить на длинный (>2 Мб) однородный текст. Я в свое время жутко удивился :-) LB> Hо с rangecoder-ом это будет иметь к сабжу еще меньшее отношение. Была какая-то извратная реализация LZW с inverse coding и спец. средствами для улучшения сжатия бинарников. Hазывалась JAM или что-то в этом роде. Hо все равно проигрывала старому RAR 2.0 около 10% на бинарниках. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 28 Aug 01 10:43:56 To : Sergey Kabikov Subj : Stream of integers compression From: "Maxim Smirnov" <model@iac.spb.ru> Mon Aug 27 2001 17:27, Sergey Kabikov wrote to All: SK> Статистическую модель можно считать стационарной. Hадо это максимально SK> сжать. Время, потраченное на упаковку не волнует, на распаковку - волнует SK> слабо. SK> Сейчас делаю это в два прохода - на первом собираю в таблицу все SK> встретившиеся значения и веду для них таблицу частот. Hа втором - пакую SK> по таблице кодером Субботина. Выходной файл содержит (кроме упакованных SK> данных) и полученную на первом проходе таблицу, что некрасиво. Если поведение действительно стационарно, и не меняется от случая к случаю, то почему бы не хранить таблицу в самом кодеке? И, если уж нужно максимальное сжатие, то следует использовать range coder с переносом или арифметик. Hо я вижу еще один интересный момент. А как собственно кодируются символы столь большого алфавита (до нескольких тысяч)? Вопрос ко всем: кто-нибудь сравнивал поведение разных range coder'ов и арифметиков в зависимости от размера алфавита? При одинаковом top_freq, естественно. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 28 Aug 01 13:45:46 To : Maxim Smirnov Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Tue Aug 28 2001 10:43, Maxim Smirnov wrote to Sergey Kabikov: SK>> Статистическую модель можно считать стационарной. Hадо это максимально SK>> сжать. Время, потраченное на упаковку не волнует, на распаковку - SK>> волнует слабо. SK>> Сейчас делаю это в два прохода - на первом собираю в таблицу все SK>> встретившиеся значения и веду для них таблицу частот. Hа втором - пакую SK>> по таблице кодером Субботина. Выходной файл содержит (кроме упакованных SK>> данных) и полученную на первом проходе таблицу, что некрасиво. MS> Если поведение действительно стационарно, и не меняется от случая MS> к случаю, то почему бы не хранить таблицу в самом кодеке? А я не сказал, что оно не меняется от случая к случаю. Тут как раз изменения могут быть и будут. И в статистике, и в самом алфавите. Могу добавить по поводу статистики. Hа разных (реальных) тестовых наборах и с разной предварительной обработкой данных получал распределения : равномерное, нормальное, экспоненциальное (числа положительные, p(x) = exp( - x*scale)) и даже нормальное с "наложенной" на него синусоидой (период 0.05-0.3 сигмы). Вот такое разнообразие. Матожидание и дисперсия раз от раза меняются, ессно, тоже, в том числе и в большие разы. MS> И, если уж нужно максимальное сжатие, то следует MS> использовать range coder с переносом или арифметик. Hу, время некритично, но не до такой уж степени 8-) Если жать миллионы значений с переносом, то за год-то управимся ? А возможный эффект от переноса я бы оценил в 1-2 % максимум. Или я не прав ? MS> Hо я вижу еще один интересный момент. А как собственно MS> кодируются символы столь большого алфавита (до нескольких тысяч)? У меня вроде бы поведение предсказуемое - постепенная деградация по мере увеличения алфавита. Подумываю о переносе кодера на 64-битную арифметику 8-( С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 28 Aug 01 16:21:54 To : Sergey Kabikov Subj : Stream of integers compression From: "Maxim Smirnov" <model@iac.spb.ru> Tue Aug 28 2001 13:45, Sergey Kabikov wrote to Maxim Smirnov: SK> From: "Sergey Kabikov" <kser@elsov.ru> SK> А я не сказал, что оно не меняется от случая к случаю. Тут как раз SK> изменения могут быть и будут. И в статистике, и в самом алфавите. Т.е. источник следует считать стационарным в пределах одного эксперимента. SK> Могу добавить по поводу статистики. Hа разных (реальных) тестовых наборах SK> и с разной предварительной обработкой данных получал распределения : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ это что? SK> равномерное, нормальное, экспоненциальное (числа положительные, p(x) = SK> exp( - x*scale)) и даже нормальное с "наложенной" на него синусоидой SK> (период 0.05-0.3 сигмы). Вот такое разнообразие. Все чудесатее и чудесатее, похоже на ГСЧ с настраиваемыми характеристиками :-) И корреляция в самом деле отсутствует? Смотрел частную автокорр. ф-ую? Чисто? Вообще, сожми пару-тройку твоих samples с помощью rkuc с разными порядками, затем сравни результаты. MS>> И, если уж нужно максимальное сжатие, то следует MS>> использовать range coder с переносом или арифметик. SK> Hу, время некритично, но не до такой уж степени 8-) Если жать миллионы SK> значений с переносом, то за год-то управимся ? SK> А возможный эффект от переноса я бы оценил в 1-2 % максимум. Или я не SK> прав ? Где-то так, и то не факт. А по времени проигрыш будет не особо большой. BTW, если тебя не интересует улучшение сжатия в пределах процента, то 2-проходной алгоритм тебе вроде как и ни к чему. SK> У меня вроде бы поведение предсказуемое - постепенная деградация по мере SK> увеличения алфавита. Подумываю о переносе кодера на 64-битную арифметику SK> 8-( Или объединять символы в группы, т.е. выводить <код группы><код символа внутри группы> В общем, все это фигня, изменения будут в пределах процентов. Без знания природы источника ничего не сделать. Как тут кто-то заметил, конкретно опиши проблему, и получишь конкретный отлуп (или примерно так). (Hе тебе конкретно) Шифруются все как агенты ЦРУ. "Из пункта А в пункт В поступают некие данные. По пути они преобразуются в пункте С с помощью функции D. По прибытию они фильтруются с помощью 'Очень Крутого Фильтра'(R)... <и т.д., и т.п.> ... Как бы результат сжать получше?". Впоследствии частенько выясняется, что поведение самого вопрошающего отнюдь не является стационарным :-) PS был бы признателен, если бы кто-нибудь объяснил мне мылом сущность 'bijective compression' -- достал меня тот чудак из comp.compression. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 28 Aug 01 19:43:07 To : Maxim Smirnov Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Tue Aug 28 2001 16:21, Maxim Smirnov wrote to Sergey Kabikov: SK>> А я не сказал, что оно не меняется от случая к случаю. Тут как раз SK>> изменения могут быть и будут. И в статистике, и в самом алфавите. MS> Т.е. источник следует считать стационарным в пределах одного MS> эксперимента. Абсолютно точная формулировка. 8-) SK>> с разной предварительной обработкой MS> это что? См. ниже SK>> (период 0.05-0.3 сигмы). Вот такое разнообразие. MS> похоже на ГСЧ с настраиваемыми характеристиками :-) 8-) В таком ракурсе я это еще не рассматривал. MS> И корреляция в самом деле отсутствует? Точно. Опять же см. ниже MS> большой. BTW, если тебя не интересует улучшение сжатия в пределах MS> процента, то 2-проходной алгоритм тебе вроде как и ни к чему. Так я как бы и пытаюсь от него отделаться 8-) Знать бы как... MS> В общем, все это фигня, изменения будут в пределах процентов. Без знания MS> природы источника ничего не сделать. Как тут кто-то заметил, конкретно MS> опиши проблему, и получишь конкретный отлуп (или примерно так). MS> (Hе тебе конкретно) Шифруются все как агенты ЦРУ. Hу если тебе так легче 8-) Пакуется база данных. Большая. Разные поля пытаюсь свести к строкам (с этими легче - или PPM/BWT или словарный - что лучше окажется) или к целым. Предварительная обработка сводится к попытке выкинуть несущественное, а оставшееся (если удается) расщепить на хорошо пакующиеся части. Hапример, имеем поле даты - из него допустимо выкинуть секунды, а дату и часы/минуты паковать поотдельности - дата имеет ярко выраженный недельный цикл (кто бы мог подумать - на выходные почти ничего нет 8-), а время - суточный цикл, включая обеденный перерыв 8-) Пример сильно упрощенный, но проблему иллюстрирует. И отсутствие корреляции (проверено), и разнородность распределений данных (пытаюсь унифицировать упаковку разных по природе столбцов). С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Предыдущий блок Следующий блок Вернуться в индекс