search

rusty-shell / rust-compress

Various compression algorithms written in rust.
Apache License 2.0
113 stars 21 forks source link

Avoid divisions in the arithmetic coder #52

Open kvark opened 9 years ago

kvark commented 9 years ago

Our straightforward range coder performs one division on encoding:

let old_range = self.hai - self.low;
let range = old_range / total;

And 2 more on decoding:

let range = (self.hai - self.low) / total;
(code - self.low) / range

Division is not the fastest operation out there, and the performance constraints on the range coder are always very tight. We should provide an implementation that uses bit shifts as an alternative. The problem is sharing code, if any, with the canonical one that we have.

kvark commented 9 years ago

Useful info: http://encode.ru/threads/1150-bsc-s-qlfc-postcoder