[ogg-dev] CRC calculation performance

rdbrown at pacific.net.au rdbrown at pacific.net.au
Tue Feb 12 22:23:05 PST 2008

> On 3-Feb-08, at 5:02 AM, Rodney Brown wrote:

>> [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

> Thanks for the links. Do you know anything about the patent status of
> these algorithms? I notice Kounavis and Berry have a CRC-related
> patent application from the same year.

Basically I don't. The link to gcc-patches was aimed at being prior art
as at 2002-04-19 for the zlib algorithm. I'd need to check the Intel paper
again. Richard Black's algorithm 4 (Fast CRC32 in Software) 1993 predates
my 1997 info-zip x86 assembler patches. He has it licensed as
"This code is copyright © 1993 Richard Black. All rights are reserved. You
may use this code only if it includes a statement to that effect.".
Someone from IBM asked in 2004 to confirm that my contribution to zlib was
unencumbered - but I had the necessary paperwork on file with the FSF,
so that was fine. No current corporate assignment (yet) at the moment.
Patenting an algorithm like the zlib crc version should have obviousness
problems too - especially to anyone with a pure-math or crypto background
(not me), after Black's algorithm 4.
I didn't find any US patent from Kounavis & Berry, but that may have been
my search foo.

>> 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).
> In Ogg, the packets are divided into segments of 255 bytes or less,
> but the CRC is over the page header and however many segments it
> governs, so up to 64 KB but typically more like 4 KB.

I still don't understand if this is useful bitpicking or not. Hope it is.

More information about the ogg-dev mailing list