Performance. In distributed systems the data is CRC'ed on every breath in and out, and often multiple times. Having entire cluster spend 10% of all CPU computing CRCs is not something unheard of.
Functionality. Computing CRC is not enough. Oftentimes, distributed systems need to perform various operations using known CRC values (concatenation, data replacement, etc.) without touching the actual data.
Functionality verification: ability to catch even the most subtle bugs in CRC implementation.
Performance benchmarking: ability to evaluate performance of known CRC algorithms and choose the right one for given architecture and/or compiler.
Support most popular and most advanced CPUs [typically used in distributed environments]. That is, AMD64 and X86.
Support most popular compilers used to compile code running in distributed environments. That is, Microsoft's CL, GCC, and Intel's ICL.
Ability to easily (at run-time) create CRCs for arbitrary generating polynomials. Many complex projects have to deal with multiple CRC generating polynomials. Adding support yet another one should be 1-line change, not 2-week journey.
Only little-endian CPUs are supported. Reason: all the optimizations makes sense only when CPU has multiple ALUs and may execute multiple instructions in parallel. I cannot easily recall big-endian CPUs like that (probably PPC and IBM's Z-series?) -- and, unless CPU is powerful enough, trivial byte-by-byte Sarwate algorithm is hard to beat.
The only CPUs the code was tested are AMD64 and X86 family. I do not have access to Itanium. I tried to do my best to allow the code to work on Itanium as is, but I will not be very surprised if I overlooked something.
Please read crc.pdf in "docs" directory -- it explains, slowly, step-by-step, how it all works, and provides small listings of respective algorithms that (hopefully, clearly) demonstrate how specific algorithm is implemented -- actual implementation is heavily optimized, a lot of loops are unrolled, and comments explain only the most subtle details of implementation.
"unittest.cc" is standalone unit test which perform extensive functionality validation and also tests performance of key scenarios. Please keep in mind that it takes almost a minute for GCC to compile it. Full performance test takes a couple of hours.
"generic_crc.h" provides a set of implemenations of generic CRCs. "crc32c" set of files implements CRC using Intel's CRC32 instruction. "multiword" set of files implements specialized -- and heavily optimized -- versions of multiword CRC.
However, including these files directly into your project may be a bad idea -- there is a lot of quite heavy-weight template code that you probably do not want to see included into every file that uses CRCs.
Instead, use "interface.h" which hides all the details of the implementation. It declares on namespace, two types in that namespace, and brings in a couple of standard ANSI C headers.
Another advantage of using "interface.h" is that actual implementation will pick the most efficient implementation of CRC for specific platform and compiler (applies to AMD64 and X86 platform and CL, ICL, and GCC compilers only).
Please see "usage.cc" which provides an example how to use crcutil_interface::CRC class.
Recommended compiler flags: CL: -O2 -Wall ICL: -O3 -Wall -Qdiag-disable:181 -Qdiag-disable:185 -Qdiag-disable:442 -Qdiag-disable:vec GCC 4.5+: -O3 -Wall -msse2 -mcrc32 GCC 4.4-, AMD64: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1 GCC 4.4-, I386: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1 -fomit-frame-pointer
CRCUTIL_USE_ASM Allows the use of inline ASM for GCC on AMD64 and I386 platforms, 32-bit Intel and Microsoft compilers on Windows.
See multiword*.cc files.
By default, turned on.HAVE_MMX MMX and respective intrinsics are available. When MMX is available, it will be used on I386 platform to speed up computation of up to 64-bit CRCs (1.3 CPU cycles/byte, see see *i386_mmx.cc files).
By default, enabled on AMD64 and I386 platforms, disabled otherwise.HAVE_SSE By default, enabled on AMD64 and I386 platforms, disabled otherwise.
HAVE_SSE2 By default, enabled on AMD64 and I386 platforms, disabled otherwise.
Allows the use of SSE2 instructions to compute 128-bit CRCs efficiently
(see uint128_sse2.h, multiword_128_64_gcc_amd64_sse2.cc).CRCUTIL_PREFETCH_WIDTH Prefetch width (default is 0 -- read platform.h to see why).
When CRCUTIL_PREFETCH_WIDTH > 0 and HAVE_SSE, the code will try to
prefetch CRCUTIL_PREFETCH_WIDTH bytes ahead.CRCUTIL_MIN_ALIGN_SIZE Align input pointer on word boundary when input length exceeds CRCUTIL_MIN_ALIGN_SIZE bytes and when CRC implementation will read input data by words.
Non-AMD64/I386 do not allow misaligned reads, so default value of
CRCUTIL_MIN_ALIGN_SIZE is 0.
On AMD64 and I386 platforms, default value is 1KB. Even though AMD64
and I386 allow non-aligned reads, crossing cache line boundary is not
free, and it makes sense to align large inputs first before processing
them (see generic_crc.h for more details).CRCUTIL_USE_MM_CRC32 Allows the use SSE4.2 crc32 instruction when computing CRC32C (0.13 CPU cycles per byte, see crc32c_sse4* files).
If set to false (i.e. 0), _mm_crc32_u*() intrinsics will be simulated
(useful for debugging crc32_sse4 code on machines that do not support
SSE 4.2).
Hardware-assisted CRC32C is supported on AMD64 and I386 platforms only.
By default, enabled for Windows and for "g++ -msse4".
With GCC 4.5, it is possible to compile the code using "-msse2 -mcrc32
-DCRCUTIL_USE_MM_CRC32=1" flags.
GCC 4.4 and earlier do not support "-mcrc32" flag, but it is still
possible to use crc32c_sse4 code by compiling the code using "-msse2
-DCRCUTIL_USE_MM_CRC32=1" flags. In this case, inline asm code will be
used (see crc32c_sse4_intrin.h).CRCUTIL_FORCE_ASM_CRC32C GCC 4.4 and earlier versions do not have -mcrc32 flag, so _mm_crc32_u64/32/8 intrinsics there are not available from standard headers. They are replaced by inline asm code (see crc32c_sse4_intrin.h). To test backward compatibility using GCC 4.5+, use "-Wall -O3 -msse2 --DCRCUTIL_USE_MM_CRC32=1 -DCRCUTIL_FORCE_ASM_CRC32C=1".
[The end of the document]