MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ut0crc32.cc
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (C) 2009, 2010 Facebook, Inc. All Rights Reserved.
4 Copyright (c) 2011, 2011, Oracle and/or its affiliates. All Rights Reserved.
5 
6 This program is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free Software
8 Foundation; version 2 of the License.
9 
10 This program is distributed in the hope that it will be useful, but WITHOUT
11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13 
14 You should have received a copy of the GNU General Public License along with
15 this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17 
18 *****************************************************************************/
19 
20 /***************************************************************/
28 /* Copyright (C) 2009-2010 Facebook, Inc. All Rights Reserved.
29 
30  Dual licensed under BSD license and GPLv2.
31 
32  Redistribution and use in source and binary forms, with or without
33  modification, are permitted provided that the following conditions are met:
34  1. Redistributions of source code must retain the above copyright notice,
35  this list of conditions and the following disclaimer.
36  2. Redistributions in binary form must reproduce the above copyright notice,
37  this list of conditions and the following disclaimer in the documentation
38  and/or other materials provided with the distribution.
39 
40  THIS SOFTWARE IS PROVIDED BY FACEBOOK, INC. ``AS IS'' AND ANY EXPRESS OR
41  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
42  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
43  EVENT SHALL FACEBOOK, INC. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
45  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
46  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
47  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
48  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
49  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
50 
51  This program is free software; you can redistribute it and/or modify it
52  under the terms of the GNU General Public License as published by the Free
53  Software Foundation; version 2 of the License.
54 
55  This program is distributed in the hope that it will be useful, but WITHOUT
56  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
57  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
58  more details.
59 
60  You should have received a copy of the GNU General Public License along with
61  this program; if not, write to the Free Software Foundation, Inc.,
62  51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
63 
64 /* The below CRC32 implementation is based on the implementation included with
65  * zlib with modifications to process 8 bytes at a time and using SSE 4.2
66  * extentions when available. The polynomial constant has been changed to
67  * match the one used by SSE 4.2 and does not return the same value as the
68  * version used by zlib. This implementation only supports 64-bit
69  * little-endian processors. The original zlib copyright notice follows. */
70 
71 /* crc32.c -- compute the CRC-32 of a buf stream
72  * Copyright (C) 1995-2005 Mark Adler
73  * For conditions of distribution and use, see copyright notice in zlib.h
74  *
75  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
76  * CRC methods: exclusive-oring 32 bits of buf at a time, and pre-computing
77  * tables for updating the shift register in one step with three exclusive-ors
78  * instead of four steps with four exclusive-ors. This results in about a
79  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
80  */
81 
82 #include "univ.i"
83 #include "ut0crc32.h"
84 
85 #include <string.h>
86 
87 ib_ut_crc32_t ut_crc32;
88 
89 /* Precalculated table used to generate the CRC32 if the CPU does not
90 have support for it */
91 static ib_uint32_t ut_crc32_slice8_table[8][256];
92 static ibool ut_crc32_slice8_table_initialized = FALSE;
93 
94 /* Flag that tells whether the CPU supports CRC32 or not */
95 UNIV_INTERN bool ut_crc32_sse2_enabled = false;
96 
97 /********************************************************************/
100 static
101 void
102 ut_crc32_slice8_table_init()
103 /*========================*/
104 {
105  /* bit-reversed poly 0x1EDC6F41 (from SSE42 crc32 instruction) */
106  static const ib_uint32_t poly = 0x82f63b78;
107  ib_uint32_t n;
108  ib_uint32_t k;
109  ib_uint32_t c;
110 
111  for (n = 0; n < 256; n++) {
112  c = n;
113  for (k = 0; k < 8; k++) {
114  c = (c & 1) ? (poly ^ (c >> 1)) : (c >> 1);
115  }
116  ut_crc32_slice8_table[0][n] = c;
117  }
118 
119  for (n = 0; n < 256; n++) {
120  c = ut_crc32_slice8_table[0][n];
121  for (k = 1; k < 8; k++) {
122  c = ut_crc32_slice8_table[0][c & 0xFF] ^ (c >> 8);
123  ut_crc32_slice8_table[k][n] = c;
124  }
125  }
126 
127  ut_crc32_slice8_table_initialized = TRUE;
128 }
129 
130 #if defined(__GNUC__) && defined(__x86_64__)
131 /********************************************************************/
133 static
134 void
135 ut_cpuid(
136 /*=====*/
137  ib_uint32_t vend[3],
138  ib_uint32_t* model,
139  ib_uint32_t* family,
140  ib_uint32_t* stepping,
141  ib_uint32_t* features_ecx,
142  ib_uint32_t* features_edx)
143 {
144  ib_uint32_t sig;
145  asm("cpuid" : "=b" (vend[0]), "=c" (vend[2]), "=d" (vend[1]) : "a" (0));
146  asm("cpuid" : "=a" (sig), "=c" (*features_ecx), "=d" (*features_edx)
147  : "a" (1)
148  : "ebx");
149 
150  *model = ((sig >> 4) & 0xF);
151  *family = ((sig >> 8) & 0xF);
152  *stepping = (sig & 0xF);
153 
154  if (memcmp(vend, "GenuineIntel", 12) == 0
155  || (memcmp(vend, "AuthenticAMD", 12) == 0 && *family == 0xF)) {
156 
157  *model += (((sig >> 16) & 0xF) << 4);
158  *family += ((sig >> 20) & 0xFF);
159  }
160 }
161 
162 /* opcodes taken from objdump of "crc32b (%%rdx), %%rcx"
163 for RHEL4 support (GCC 3 doesn't support this instruction) */
164 #define ut_crc32_sse42_byte \
165  asm(".byte 0xf2, 0x48, 0x0f, 0x38, 0xf0, 0x0a" \
166  : "=c"(crc) : "c"(crc), "d"(buf)); \
167  len--, buf++
168 
169 /* opcodes taken from objdump of "crc32q (%%rdx), %%rcx"
170 for RHEL4 support (GCC 3 doesn't support this instruction) */
171 #define ut_crc32_sse42_quadword \
172  asm(".byte 0xf2, 0x48, 0x0f, 0x38, 0xf1, 0x0a" \
173  : "=c"(crc) : "c"(crc), "d"(buf)); \
174  len -= 8, buf += 8
175 #endif /* defined(__GNUC__) && defined(__x86_64__) */
176 
177 /********************************************************************/
180 UNIV_INLINE
181 ib_uint32_t
182 ut_crc32_sse42(
183 /*===========*/
184  const byte* buf,
185  ulint len)
186 {
187 #if defined(__GNUC__) && defined(__x86_64__)
188  ib_uint64_t crc = (ib_uint32_t) (-1);
189 
190  ut_a(ut_crc32_sse2_enabled);
191 
192  while (len && ((ulint) buf & 7)) {
193  ut_crc32_sse42_byte;
194  }
195 
196  while (len >= 32) {
197  ut_crc32_sse42_quadword;
198  ut_crc32_sse42_quadword;
199  ut_crc32_sse42_quadword;
200  ut_crc32_sse42_quadword;
201  }
202 
203  while (len >= 8) {
204  ut_crc32_sse42_quadword;
205  }
206 
207  while (len) {
208  ut_crc32_sse42_byte;
209  }
210 
211  return((ib_uint32_t) ((~crc) & 0xFFFFFFFF));
212 #else
213  ut_error;
214  /* silence compiler warning about unused parameters */
215  return((ib_uint32_t) buf[len]);
216 #endif /* defined(__GNUC__) && defined(__x86_64__) */
217 }
218 
219 #define ut_crc32_slice8_byte \
220  crc = (crc >> 8) ^ ut_crc32_slice8_table[0][(crc ^ *buf++) & 0xFF]; \
221  len--
222 
223 #define ut_crc32_slice8_quadword \
224  crc ^= *(ib_uint64_t*) buf; \
225  crc = ut_crc32_slice8_table[7][(crc ) & 0xFF] ^ \
226  ut_crc32_slice8_table[6][(crc >> 8) & 0xFF] ^ \
227  ut_crc32_slice8_table[5][(crc >> 16) & 0xFF] ^ \
228  ut_crc32_slice8_table[4][(crc >> 24) & 0xFF] ^ \
229  ut_crc32_slice8_table[3][(crc >> 32) & 0xFF] ^ \
230  ut_crc32_slice8_table[2][(crc >> 40) & 0xFF] ^ \
231  ut_crc32_slice8_table[1][(crc >> 48) & 0xFF] ^ \
232  ut_crc32_slice8_table[0][(crc >> 56)]; \
233  len -= 8, buf += 8
234 
235 /********************************************************************/
238 UNIV_INLINE
239 ib_uint32_t
240 ut_crc32_slice8(
241 /*============*/
242  const byte* buf,
243  ulint len)
244 {
245  ib_uint64_t crc = (ib_uint32_t) (-1);
246 
247  ut_a(ut_crc32_slice8_table_initialized);
248 
249  while (len && ((ulint) buf & 7)) {
250  ut_crc32_slice8_byte;
251  }
252 
253  while (len >= 32) {
254  ut_crc32_slice8_quadword;
255  ut_crc32_slice8_quadword;
256  ut_crc32_slice8_quadword;
257  ut_crc32_slice8_quadword;
258  }
259 
260  while (len >= 8) {
261  ut_crc32_slice8_quadword;
262  }
263 
264  while (len) {
265  ut_crc32_slice8_byte;
266  }
267 
268  return((ib_uint32_t) ((~crc) & 0xFFFFFFFF));
269 }
270 
271 /********************************************************************/
274 UNIV_INTERN
275 void
276 ut_crc32_init()
277 /*===========*/
278 {
279 #if defined(__GNUC__) && defined(__x86_64__)
280  ib_uint32_t vend[3];
281  ib_uint32_t model;
282  ib_uint32_t family;
283  ib_uint32_t stepping;
284  ib_uint32_t features_ecx;
285  ib_uint32_t features_edx;
286 
287  ut_cpuid(vend, &model, &family, &stepping,
288  &features_ecx, &features_edx);
289 
290  /* Valgrind does not understand the CRC32 instructions:
291 
292  vex amd64->IR: unhandled instruction bytes: 0xF2 0x48 0xF 0x38 0xF0 0xA
293  valgrind: Unrecognised instruction at address 0xad3db5.
294  Your program just tried to execute an instruction that Valgrind
295  did not recognise. There are two possible reasons for this.
296  1. Your program has a bug and erroneously jumped to a non-code
297  location. If you are running Memcheck and you just saw a
298  warning about a bad jump, it's probably your program's fault.
299  2. The instruction is legitimate but Valgrind doesn't handle it,
300  i.e. it's Valgrind's fault. If you think this is the case or
301  you are not sure, please let us know and we'll try to fix it.
302  Either way, Valgrind will now raise a SIGILL signal which will
303  probably kill your program.
304 
305  */
306 #ifndef UNIV_DEBUG_VALGRIND
307  ut_crc32_sse2_enabled = (features_ecx >> 20) & 1;
308 #endif /* UNIV_DEBUG_VALGRIND */
309 
310 #endif /* defined(__GNUC__) && defined(__x86_64__) */
311 
312  if (ut_crc32_sse2_enabled) {
313  ut_crc32 = ut_crc32_sse42;
314  } else {
315  ut_crc32_slice8_table_init();
316  ut_crc32 = ut_crc32_slice8;
317  }
318 }