Carryless rangecoder v2.0 - 100% настоящего изврата!
Dmitry Subbotin
Я тут подумал, что потери в 1% для арифметического кодера это все-таки слишком
много, и слегка его соптимизировал. Теперь он теряет всего где-то 0.05%, что
имхо уже ерунда.
Параллельно как-то сам собой установился новый рекорд на размер процедуры
Encode - всего 5 строчек. 8-)
───[ Hачала _ ]────────────────────────────────────────────────────
/*
* Carryless rangecoder (c) 1999 by Dmitry Subbotin
*/
#define TopValue (1<<24)
#define BotValue (1<<16)
class RangeCoder
{
uint low, code, range, passed;
FILE *f;
void OutByte (uc c) { passed++; fputc(c,f); }
uc InByte () { passed++; return fgetc(f); }
public:
uint GetPassed () { return passed; }
void StartEncode (FILE *F) { f=F; passed=low=0; range= (uint) -1; }
void FinishEncode () { DO(4) OutByte(low>>24), low<<=8; }
void StartDecode (FILE *F) { passed=low=code=0;
range= (uint) -1;
f=F; DO(4) code= code<<8 | InByte();
}
void Encode (uint cum_freq, uint freq, uint tot_freq) {
low+= cum_freq*(range/=tot_freq);
range*= freq;
while (range < TopValue && ((low ^ low+range) < TopValue ||
range < BotValue && ((range= -low & BotValue-1), 1)))
OutByte(low>>24), range<<=8, low<<=8;
}
uint GetFreq (uint tot_freq) {
uint tmp= (code-low)/(range/=tot_freq);
if (tmp >= tot_freq) throw ("Input data corrupt");
return tmp;
}
void Decode (uint cum_freq, uint freq, uint tot_freq) {
low+= cum_freq*range;
range*= freq;
while (range < TopValue && ((low ^ low+range) < TopValue ||
range < BotValue && ((range= -low & BotValue-1), 1)))
code= code<<8 | InByte(), range<<=8, low<<=8;
}
};
───[ Концы _ ]─────────────────────────────────────────────────────
ps. Кто не понял - DO это
#define DO(n) for(int _=0; _<n; _++)
taste you later,
morf
Leonid Broukhis
>Я тут подумал, что потери в 1% для арифметического кодера это все-таки слишком
>много, и слегка его соптимизировал. Теперь он теряет всего где-то 0.05%, что
>имхо уже ерунда.
На случайном файле длиной 100000 разница между ari с фиксированной
моделью и твоим кодером - 13 байт (100072 и 100085 соответственно). Cool!
Но разница в скорости - в 2 с лишним раза.
В comp.compression(.research) немедленно!
Leo
Bulat Ziganshin
* Crossposted in RU.COMPRESS
Hello Leonid!
Monday May 17 1999, Leonid Broukhis writes to Dmitry Subbotin:
>> Я тут подумал, что потери в 1% для арифметического кодера это
>> все-таки слишком много, и слегка его соптимизировал. Теперь он теряет
>> всего где-то 0.05%, что имхо уже ерунда.
LB> Hа случайном файле длиной 100000 разница между ari с фиксированной
LB> моделью и твоим кодером - 13 байт (100072 и 100085 соответственно).
LB> Cool!
LB> Hо разница в скорости - в 2 с лишним раза.
LB> В comp.compression(.research) немедленно!
А что за ari? Шиндлеровский побайтный? Он самый быстрый из известных мне
лично.
Bulat, mailto:bul...@fort.tatarstan.ru, ICQ 15872722
Dmitry Subbotin
"Leonid Broukhis" sendTo: "Dmitry Subbotin" when: [18 May 99] msg:
>> void Encode (uint cum_freq, uint freq, uint tot_freq) {
>> low+= cum_freq*(range/=tot_freq);
>> range*= freq;
>> while (range < TopValue && ((low ^ low+range) < TopValue ||
>> range < BotValue && ((range= -low & BotValue-1), 1)))
>> OutByte(low>>24), range<<=8, low<<=8;
>> }
LB> Кажется мне, что если TopValue - это степень двойки,
LB> то при любом low < TopValue из (low ^ low+range) < TopValue следует,
LB> что range < TopValue, а из range < BotValue это следует с
LB> очевидностью, и поэтому первоначальную проверку range < TopValue
LB> можно опустить.
Я сначала тоже пробовал эту проверку опустить. :) Hо нельзя - когда
range=0xff?????? и происходит перенос из третьего байта, low+range имеет тот же
старший байт что и low.
taste you later,
morf
Leonid Broukhis
> >> Я тут подумал, что потери в 1% для арифметического кодера это
> >> все-таки слишком много, и слегка его соптимизировал. Теперь он теряет
> >> всего где-то 0.05%, что имхо уже ерунда.
>
> LB> Hа случайном файле длиной 100000 разница между ari с фиксированной
> LB> моделью и твоим кодером - 13 байт (100072 и 100085 соответственно).
> LB> Cool!
>
> LB> Hо разница в скорости - в 2 с лишним раза.
>
> LB> В comp.compression(.research) немедленно!
>
> А что за ari? Шиндлеровский побайтный? Он самый быстрый из известных мне
>лично.
Нет, стандартный побитный. У Шиндлера на странице только range coder,
арифметического я не нашел.
Leo
Leonid Broukhis
> void Encode (uint cum_freq, uint freq, uint tot_freq) {
> low+= cum_freq*(range/=tot_freq);
> range*= freq;
> while (range < TopValue && ((low ^ low+range) < TopValue ||
> range < BotValue && ((range= -low & BotValue-1), 1)))
> OutByte(low>>24), range<<=8, low<<=8;
> }
Кажется мне, что если TopValue - это степень двойки,
то при любом low < TopValue из (low ^ low+range) < TopValue следует, что
range < TopValue, а из range < BotValue это следует с очевидностью,
и поэтому первоначальную проверку range < TopValue можно опустить.
Leo
Dmitry Subbotin
"Leonid Broukhis" sendTo: "Dmitry Subbotin" when: [17 May 99] msg:
>> Я тут подумал, что потери в 1% для арифметического кодера это
>> все-таки слишком много, и слегка его соптимизировал. Теперь он теряет
>> всего где-то 0.05%, что имхо уже ерунда.
LB> Hа случайном файле длиной 100000 разница между ari с фиксированной
LB> моделью и твоим кодером - 13 байт (100072 и 100085 соответственно).
LB> Cool!
Что-то мало потерь получилось. :) Hаверное, это особенности фиксированной
модели (там tot_fr было степенью двойки?).
LB> Hо разница в скорости - в 2 с лишним раза.
LB> В comp.compression(.research) немедленно!
:) Hапишу, напишу. Вот только приделаю к субжу еще какую-нибудь быструю
модельку.
taste you later,
morf
Leonid Broukhis
> >> Я тут подумал, что потери в 1% для арифметического кодера это
> >> все-таки слишком много, и слегка его соптимизировал. Теперь он теряет
> >> всего где-то 0.05%, что имхо уже ерунда.
>
> LB> Hа случайном файле длиной 100000 разница между ari с фиксированной
> LB> моделью и твоим кодером - 13 байт (100072 и 100085 соответственно).
> LB> Cool!
>
>Что-то мало потерь получилось. :) Hаверное, это особенности фиксированной
>модели (там tot_fr было степенью двойки?).
Нет, 257. Теоретическое количество байт должно было бы быть
100000*log2(257)/log2(256) = 100070.3, т.е. 100071. И естественно,
что для случайных чисел фиксированная модель лучше, чем какая-либо другая,
просто хотелось проверить, насколько твой кодер от традиционного отличается
при минимуме вмешательств.
>:) Hапишу, напишу. Вот только приделаю к субжу еще какую-нибудь быструю
>модельку.
Возьми Шиндлеровский кодер (с www.compressconsult.com), замени его
модель на свою и погоняй.
Leo
Dmitry Subbotin
Dmitry Subbotin писал[а,о,и,ы] в письме к Leonid Broukhis:
LB>> Кажется мне, что если TopValue - это степень двойки,
LB>> то при любом low < TopValue из (low ^ low+range) < TopValue
LB>> следует, что range < TopValue, а из range < BotValue это следует
LB>> с очевидностью, и поэтому первоначальную проверку range <
LB>> TopValue можно опустить.
DS> Я сначала тоже пробовал эту проверку опустить. :) Hо нельзя - когда
DS> range=0xff?????? и происходит перенос из третьего байта, low+range
DS> имеет тот же старший байт что и low.
Хм, а ведь такого не может быть - lo+range всегда меньше 1<<32. Да, все
правильно, эту проверку можно выкинуть.
Кстати, как ты думаешь, будет ли этот код работать на всех машинах? :) Там в
одном месте молчаливо предполагается, что отрицательные числа храняться в
дополнительном формате, т.е. что например char(-1)==0xff. А в современной
природе есть компы, для которых это не верно?
taste you later,
morf
Bulat Ziganshin
Hello Leonid!
Tuesday May 18 1999, Leonid Broukhis writes to Bulat Ziganshin:
>> А что за ari? Шиндлеровский побайтный? Он самый быстрый из
>> известных мне лично.
LB> Hет, стандартный побитный. У Шиндлера на странице только range coder,
LB> арифметического я не нашел.
Он упоминается на http://eiunix.tuwien.ac.at/~michael/ ("A byte oriented
aritmetic coder module..."). Правда, там же написано, что в нем есть ошибка и
новой его версией является rangecoder. В общем, я уже немного в этом запутался:
rangecoder - это побайтный арифметический кодер или все же есть какая-то
принципиальная разница?
Bulat Ziganshin
Hello All!
Wednesday May 19 1999, Bulat Ziganshin writes to Leonid Broukhis:
LB>> Hет, стандартный побитный. У Шиндлера на странице только range
LB>> coder, арифметического я не нашел.
BZ> Он упоминается на http://eiunix.tuwien.ac.at/~michael/
Оказывается, Шиндлер сделал весьма подробное описание сабжа - на уровне,
достаточном для воссоздания чего-нибудь типа zip'а :)
http://www.compressconsult.com/huffman/
Bulat Ziganshin
Hello Leonid!
Wednesday May 19 1999, Bulat Ziganshin writes to Leonid Broukhis:
>>> А что за ari? Шиндлеровский побайтный? Он самый быстрый из
>>> известных мне лично.
LB>> Hет, стандартный побитный. У Шиндлера на странице только range
LB>> coder, арифметического я не нашел.
BZ> Он упоминается на http://eiunix.tuwien.ac.at/~michael/ ("A byte
BZ> oriented aritmetic coder module..."). Правда, там же написано, что в
BZ> нем есть ошибка и новой его версией является rangecoder. В общем, я
BZ> уже немного в этом запутался: rangecoder - это побайтный
BZ> арифметический кодер или все же есть какая-то принципиальная разница?
Да, а сравнить сабж с оригинальным ранчкодером?
Leonid Broukhis
Думаю, что уже нет. В конце концов, можно и ifdef написать.
Leo
Leonid Broukhis
> >> А что за ari? Шиндлеровский побайтный? Он самый быстрый из
> >> известных мне лично.
>
> LB> Hет, стандартный побитный. У Шиндлера на странице только range coder,
> LB> арифметического я не нашел.
>
> Он упоминается на http://eiunix.tuwien.ac.at/~michael/ ("A byte oriented
>aritmetic coder module..."). Правда, там же написано, что в нем есть ошибка и
>новой его версией является rangecoder. В общем, я уже немного в этом запутался:
>rangecoder - это побайтный арифметический кодер или все же есть какая-то
>принципиальная разница?
Принципиальная разница есть только между синхронизирующимися
(префиксные) и несинхронизирующимися (арифметический)
кодами. То, что rangecoder так называется - в большой степени защита
от IBM с их патентами.
Leo
Leonid Broukhis
> BZ> Он упоминается на http://eiunix.tuwien.ac.at/~michael/ ("A byte
> BZ> oriented aritmetic coder module..."). Правда, там же написано, что в
> BZ> нем есть ошибка и новой его версией является rangecoder. В общем, я
> BZ> уже немного в этом запутался: rangecoder - это побайтный
> BZ> арифметический кодер или все же есть какая-то принципиальная разница?
>
> Да, а сравнить сабж с оригинальным ранчкодером?
Это к Дмитрию Субботину. Но я не думаю, что будет существенная разница.
У Дмитрия, кстати, есть ма-аленькая неэффективность: в FinishEncode
необязательно выпихивать все 4 байта, достаточно только тех, которые
нужны для однозначного определения freq (обычно хватит 2-3). Строго 4
полезно, только если в файле лежит несколько кодированных потоков подряд.
Leo
Leonid Broukhis
>>Кстати, как ты думаешь, будет ли этот код работать на всех машинах? :) Там в
>>одном месте молчаливо предполагается, что отрицательные числа храняться в
>>дополнительном формате, т.е. что например char(-1)==0xff. А в современной
>>природе есть компы, для которых это не верно?
>
>Думаю, что уже нет. В конце концов, можно и ifdef написать.
Или, как честный человек, TopValue - (low & TopValue-1). Ведь ты именно
этого хочешь.
Leo
Bulat Ziganshin
* Crossposted in RU.COMPRESS
Hello Leonid!
Wednesday May 19 1999, Leonid Broukhis writes to Bulat Ziganshin:
>> Да, а сравнить сабж с оригинальным ранчкодером?
LB> Это к Дмитрию Субботину. Hо я не думаю, что будет существенная
LB> разница.
Тогда объясните, в честь чего праздник?
Bulat, mailto:bul...@fort.tatarstan.ru, ICQ 15872722
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
Evgeny Sharandin
С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 не нужен ;).
С уважением, Евгений
Leonid Broukhis
> >> Да, а сравнить сабж с оригинальным ранчкодером?
>
> LB> Это к Дмитрию Субботину. Hо я не думаю, что будет существенная
> LB> разница.
>
> Тогда объясните, в честь чего праздник?
Праздник в честь простоты и компактности. И скорости, надо полагать.
Leo
Dmitry Subbotin
"Bulat Ziganshin" sendTo: "Leonid Broukhis" when: [20 May 99] msg:
>>> Да, а сравнить сабж с оригинальным ранчкодером?
По сравненю с шиндлеровским оригинальным субж
1. проще и короче, раза так в три
2. должен работать на несколько тактов быстрее, что в общем-то фигня
3. теряет дополнительно ~0.05%, что тоже фигня
LB>> Это к Дмитрию Субботину. Hо я не думаю, что будет существенная
LB>> разница.
BZ> Тогда объясните, в честь чего праздник?
В честь очередной победы разума над алгоритмом арифметического кодирования. ;)
taste you later,
morf