[theora-dev] Experimental release of Ghost/CELT 0.0.1

[Timothy B. Terriberry]

David Kuehling wrote:
> I just wanted to complain about your codec using (patent-encumbered)
> arithmetic encoding, but now I noticed you're actually using range
> compression, all of this wrapped in a neat reusable library.

You're welcome. I've updated the URLs in the copy in svn:
http://svn.xiph.org/trunk/ghost/libentcode/
J-M has already merged them into his git repository.

In theory, the original patents for arithmetic coding have expired (they
were from c. 1979). The code cites a reference going as far back as 1976
for a reason. There may be some question about how many times its been
patented over the years, and with how many minor variations, questions
to which I certainly do not know the answers. But Dirac, for example,
uses normal bitwise arithmetic coding, so presumably it's not _that_
dangerous. The main advantage of range coding is the speed, if you can
afford to give up 7 bits of resolution in your frequency counts. Recent
research has focused on table-drive/state-machine implementations, which
are faster still (at a much greater loss of modeling accuracy), but
those have very clear and very recent patent problems.

I'd estimate that you'd save ~12% by switching from Huffman to something
arithmetic coding-based for video (based on the experiments with
H.264... Theora has more flexible Huffman coding for some pieces, and
less flexible coding for others, so it probably averages out on the
balance).

For audio that's less clear. Vorbis gets most of its compression from
using VQ, which only really benefits if you have non-power-of-two
codebook sizes, which would require re-training codebooks...