[ogg-dev] CRC calculation performance

[Rodney Brown]

I saw the talk Seeking is hard: Ogg design internals by Ralph Giles at
linux.conf.au MEL8OURNE2008.

Some suggestions:
In the page checksum section of http://xiph.org/ogg/doc/framing.html
please add a link to the wikipedia page, since there are links to faster
variants of table driven CRC calculation there - though it is not a
thing of beauty.

http://en.wikipedia.org/wiki/Cyclic_redundancy_check
* Black, R. (1994-02)
[http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html ''Fast
CRC32 in Software'']  Algorithm 4 is used in Linux and info-zip's zip
and unzip.
* Kounavis, M. and Berry, F. (2005).
[http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf ''A Systematic Approach to Building High Performance, Software-based, CRC generators''], Slicing-by-4 and slicing-by-8 algorithms


I believe current betas(?) of info-zip's unzip & zip, but certainly
current zlib is using an implementation of the Intel algorithm that is
faster than Richard Black's version by using more lookup array space,
at least on architectures that can allow multiple simultaneous memory
loads in flight.

Your reference implementation in libogg-1.1.3/src/framing.c is using a
simple, clean table lookup form.

The following gives some idea of the performance improvements available
on the old slows, but over large buffers, unlike the maximum 256 bytes
of OGG format (if I'm understanding that correctly).
http://gcc.gnu.org/ml/gcc-patches/2002-04/msg01097.html

Since as I read it you're using the standard Ethernet polynomial used by
zlib (& info-zip), it should be possible to have zlib provide an
interface for access to the lookup arrays, or to directly calculate the
OGG CRC, so that the ugliness is constrained. I note that the zlib crc32
function can't be used directly since it is using the 0xFFFFFFFF pre &
post condition.
Mark Adler may be able to provide a BSD licensed OGG optimised version,
based on the zlib code, if you need a faster version inside libogg.

Hope this is useful,
Regards,
Rodney Brown