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
On 3-Feb-08, at 5:02 AM, Rodney Brown wrote:> I saw the talk Seeking is hard: Ogg design internals by Ralph Giles at > linux.conf.au MEL8OURNE2008.Cool, glad you could make it.> [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 algorithmsThanks 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.> 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. -r
> 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. Regards,