Debian Codegraph @

external/crcutil-1.0/README

raw
1 Goals
2 -----
3
4 1. Performance. In distributed systems the data is CRC'ed
5 on every breath in and out, and often multiple times.
6 Having entire cluster spend 10% of all CPU computing
7 CRCs is not something unheard of.
8
9 2. Functionality. Computing CRC is not enough. Oftentimes,
10 distributed systems need to perform various operations
11 using known CRC values (concatenation, data replacement,
12 etc.) without touching the actual data.
13
14 3. Functionality verification: ability to catch even the most
15 subtle bugs in CRC implementation.
16
17 4. Performance benchmarking: ability to evaluate performance
18 of known CRC algorithms and choose the right one for given
19 architecture and/or compiler.
20
21 5. Support most popular and most advanced CPUs [typically
22 used in distributed environments]. That is, AMD64 and X86.
23
24 6. Support most popular compilers used to compile code running
25 in distributed environments. That is, Microsoft's CL, GCC,
26 and Intel's ICL.
27
28 7. Ability to easily (at run-time) create CRCs for arbitrary
29 generating polynomials. Many complex projects have to deal
30 with multiple CRC generating polynomials. Adding support
31 yet another one should be 1-line change, not 2-week journey.
32
33
34 Caveats
35 -------
36
37 1. Only little-endian CPUs are supported. Reason: all the
38 optimizations makes sense only when CPU has multiple ALUs
39 and may execute multiple instructions in parallel. I cannot
40 easily recall big-endian CPUs like that (probably PPC and
41 IBM's Z-series?) -- and, unless CPU is powerful enough,
42 trivial byte-by-byte Sarwate algorithm is hard to beat.
43
44 2. The only CPUs the code was tested are AMD64 and X86 family.
45 I do not have access to Itanium. I tried to do my best to
46 allow the code to work on Itanium as is, but I will not
47 be very surprised if I overlooked something.
48
49
50 How it all works
51 ----------------
52
53 Please read crc.pdf in "docs" directory -- it explains, slowly,
54 step-by-step, how it all works, and provides small listings
55 of respective algorithms that (hopefully, clearly) demonstrate
56 how specific algorithm is implemented -- actual implementation
57 is heavily optimized, a lot of loops are unrolled, and comments
58 explain only the most subtle details of implementation.
59
60
61 Usage
62 -----
63
64 "unittest.cc" is standalone unit test which perform extensive
65 functionality validation and also tests performance of key scenarios.
66 Please keep in mind that it takes almost a minute for GCC to compile
67 it. Full performance test takes a couple of hours.
68
69 "generic_crc.h" provides a set of implemenations of generic CRCs.
70 "crc32c*" set of files implements CRC using Intel's CRC32 instruction.
71 "multiword*" set of files implements specialized -- and heavily
72 optimized -- versions of multiword CRC.
73
74 However, including these files directly into your project may be
75 a bad idea -- there is a lot of quite heavy-weight template code
76 that you probably do not want to see included into every file that
77 uses CRCs.
78
79 Instead, use "interface.h" which hides all the details of the
80 implementation. It declares on namespace, two types in that
81 namespace, and brings in a couple of standard ANSI C headers.
82
83 Another advantage of using "interface.h" is that actual
84 implementation will pick the most efficient implementation
85 of CRC for specific platform and compiler (applies to
86 AMD64 and X86 platform and CL, ICL, and GCC compilers only).
87
88 Please see "usage.cc" which provides an example how to use
89 crcutil_interface::CRC class.
90
91
92 Compiler optimization settings
93 ------------------------------
94
95 Recommended compiler flags:
96 CL: -O2 -Wall
97 ICL: -O3 -Wall -Qdiag-disable:181 -Qdiag-disable:185 -Qdiag-disable:442 -Qdiag-disable:vec
98 GCC 4.5+: -O3 -Wall -msse2 -mcrc32
99 GCC 4.4-, AMD64: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1
100 GCC 4.4-, I386: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1 -fomit-frame-pointer
101
102
103 Compile-time constants
104 ----------------------
105
106 CRCUTIL_USE_ASM
107 Allows the use of inline ASM for GCC on AMD64 and I386 platforms,
108 32-bit Intel and Microsoft compilers on Windows.
109
110 See multiword*.cc files.
111
112 By default, turned on.
113
114
115 HAVE_MMX
116 MMX and respective intrinsics are available. When MMX is available, it
117 will be used on I386 platform to speed up computation of up to 64-bit
118 CRCs (1.3 CPU cycles/byte, see see *i386_mmx.cc files).
119
120 By default, enabled on AMD64 and I386 platforms, disabled otherwise.
121
122
123 HAVE_SSE
124 By default, enabled on AMD64 and I386 platforms, disabled otherwise.
125
126
127 HAVE_SSE2
128 By default, enabled on AMD64 and I386 platforms, disabled otherwise.
129
130 Allows the use of SSE2 instructions to compute 128-bit CRCs efficiently
131 (see uint128_sse2.h, multiword_128_64_gcc_amd64_sse2.cc).
132
133
134 CRCUTIL_PREFETCH_WIDTH
135 Prefetch width (default is 0 -- read platform.h to see why).
136
137 When CRCUTIL_PREFETCH_WIDTH > 0 and HAVE_SSE, the code will try to
138 prefetch CRCUTIL_PREFETCH_WIDTH bytes ahead.
139
140
141 CRCUTIL_MIN_ALIGN_SIZE
142 Align input pointer on word boundary when input length exceeds
143 CRCUTIL_MIN_ALIGN_SIZE bytes and when CRC implementation will read
144 input data by words.
145
146 Non-AMD64/I386 do not allow misaligned reads, so default value of
147 CRCUTIL_MIN_ALIGN_SIZE is 0.
148
149 On AMD64 and I386 platforms, default value is 1KB. Even though AMD64
150 and I386 allow non-aligned reads, crossing cache line boundary is not
151 free, and it makes sense to align large inputs first before processing
152 them (see generic_crc.h for more details).
153
154
155 CRCUTIL_USE_MM_CRC32
156 Allows the use SSE4.2 crc32 instruction when computing CRC32C (0.13 CPU
157 cycles per byte, see crc32c_sse4* files).
158
159 If set to false (i.e. 0), _mm_crc32_u*() intrinsics will be simulated
160 (useful for debugging crc32_sse4 code on machines that do not support
161 SSE 4.2).
162
163 Hardware-assisted CRC32C is supported on AMD64 and I386 platforms only.
164
165 By default, enabled for Windows and for "g++ -msse4".
166
167 With GCC 4.5, it is possible to compile the code using "-msse2 -mcrc32
168 -DCRCUTIL_USE_MM_CRC32=1" flags.
169
170 GCC 4.4 and earlier do not support "-mcrc32" flag, but it is still
171 possible to use crc32c_sse4 code by compiling the code using "-msse2
172 -DCRCUTIL_USE_MM_CRC32=1" flags. In this case, inline asm code will be
173 used (see crc32c_sse4_intrin.h).
174
175
176 CRCUTIL_FORCE_ASM_CRC32C
177 GCC 4.4 and earlier versions do not have -mcrc32 flag, so
178 _mm_crc32_u64/32/8 intrinsics there are not available from standard
179 headers. They are replaced by inline asm code (see
180 crc32c_sse4_intrin.h). To test backward compatibility using GCC 4.5+,
181 use "-Wall -O3 -msse2 --DCRCUTIL_USE_MM_CRC32=1
182 -DCRCUTIL_FORCE_ASM_CRC32C=1".
183
184
185 [The end of the document]