1 /*
2 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "runtime/deoptimization.hpp"
27 #include "runtime/frame.inline.hpp"
28 #include "runtime/stubRoutines.hpp"
29 #include "runtime/thread.inline.hpp"
30 #include "crc32c.h"
31
32 #ifdef _MSC_VER
33 #define ALIGNED_(x) __declspec(align(x))
34 #else
35 #define ALIGNED_(x) __attribute__ ((aligned(x)))
36 #endif
37
38 // Implementation of the platform-specific part of StubRoutines - for
39 // a description of how to extend it, see the stubRoutines.hpp file.
40
41 address StubRoutines::x86::_verify_mxcsr_entry = NULL;
42 address StubRoutines::x86::_key_shuffle_mask_addr = NULL;
43 address StubRoutines::x86::_counter_shuffle_mask_addr = NULL;
44 address StubRoutines::x86::_ghash_long_swap_mask_addr = NULL;
45 address StubRoutines::x86::_ghash_byte_swap_mask_addr = NULL;
46 address StubRoutines::x86::_upper_word_mask_addr = NULL;
47 address StubRoutines::x86::_shuffle_byte_flip_mask_addr = NULL;
48 address StubRoutines::x86::_k256_adr = NULL;
49 address StubRoutines::x86::_pshuffle_byte_flip_mask_addr = NULL;
50
51 uint64_t StubRoutines::x86::_crc_by128_masks[] =
52 {
53 /* The fields in this structure are arranged so that they can be
54 * picked up two at a time with 128-bit loads.
55 *
56 * Because of flipped bit order for this CRC polynomials
57 * the constant for X**N is left-shifted by 1. This is because
58 * a 64 x 64 polynomial multiply produces a 127-bit result
59 * but the highest term is always aligned to bit 0 in the container.
60 * Pre-shifting by one fixes this, at the cost of potentially making
61 * the 32-bit constant no longer fit in a 32-bit container (thus the
62 * use of uint64_t, though this is also the size used by the carry-
63 * less multiply instruction.
64 *
65 * In addition, the flipped bit order and highest-term-at-least-bit
66 * multiply changes the constants used. The 96-bit result will be
67 * aligned to the high-term end of the target 128-bit container,
68 * not the low-term end; that is, instead of a 512-bit or 576-bit fold,
69 * instead it is a 480 (=512-32) or 544 (=512+64-32) bit fold.
70 *
71 * This cause additional problems in the 128-to-64-bit reduction; see the
72 * code for details. By storing a mask in the otherwise unused half of
73 * a 128-bit constant, bits can be cleared before multiplication without
74 * storing and reloading. Note that staying on a 128-bit datapath means
75 * that some data is uselessly stored and some unused data is intersected
76 * with an irrelevant constant.
77 */
78
79 ((uint64_t) 0xffffffffUL), /* low of K_M_64 */
80 ((uint64_t) 0xb1e6b092U << 1), /* high of K_M_64 */
81 ((uint64_t) 0xba8ccbe8U << 1), /* low of K_160_96 */
82 ((uint64_t) 0x6655004fU << 1), /* high of K_160_96 */
83 ((uint64_t) 0xaa2215eaU << 1), /* low of K_544_480 */
84 ((uint64_t) 0xe3720acbU << 1) /* high of K_544_480 */
85 };
86
87 /**
88 * crc_table[] from jdk/src/share/native/java/util/zip/zlib-1.2.5/crc32.h
89 */
90 juint StubRoutines::x86::_crc_table[] =
91 {
92 0x00000000UL, 0x77073096UL, 0xee0e612cUL, 0x990951baUL, 0x076dc419UL,
93 0x706af48fUL, 0xe963a535UL, 0x9e6495a3UL, 0x0edb8832UL, 0x79dcb8a4UL,
94 0xe0d5e91eUL, 0x97d2d988UL, 0x09b64c2bUL, 0x7eb17cbdUL, 0xe7b82d07UL,
95 0x90bf1d91UL, 0x1db71064UL, 0x6ab020f2UL, 0xf3b97148UL, 0x84be41deUL,
96 0x1adad47dUL, 0x6ddde4ebUL, 0xf4d4b551UL, 0x83d385c7UL, 0x136c9856UL,
97 0x646ba8c0UL, 0xfd62f97aUL, 0x8a65c9ecUL, 0x14015c4fUL, 0x63066cd9UL,
98 0xfa0f3d63UL, 0x8d080df5UL, 0x3b6e20c8UL, 0x4c69105eUL, 0xd56041e4UL,
99 0xa2677172UL, 0x3c03e4d1UL, 0x4b04d447UL, 0xd20d85fdUL, 0xa50ab56bUL,
100 0x35b5a8faUL, 0x42b2986cUL, 0xdbbbc9d6UL, 0xacbcf940UL, 0x32d86ce3UL,
101 0x45df5c75UL, 0xdcd60dcfUL, 0xabd13d59UL, 0x26d930acUL, 0x51de003aUL,
102 0xc8d75180UL, 0xbfd06116UL, 0x21b4f4b5UL, 0x56b3c423UL, 0xcfba9599UL,
103 0xb8bda50fUL, 0x2802b89eUL, 0x5f058808UL, 0xc60cd9b2UL, 0xb10be924UL,
104 0x2f6f7c87UL, 0x58684c11UL, 0xc1611dabUL, 0xb6662d3dUL, 0x76dc4190UL,
105 0x01db7106UL, 0x98d220bcUL, 0xefd5102aUL, 0x71b18589UL, 0x06b6b51fUL,
106 0x9fbfe4a5UL, 0xe8b8d433UL, 0x7807c9a2UL, 0x0f00f934UL, 0x9609a88eUL,
107 0xe10e9818UL, 0x7f6a0dbbUL, 0x086d3d2dUL, 0x91646c97UL, 0xe6635c01UL,
108 0x6b6b51f4UL, 0x1c6c6162UL, 0x856530d8UL, 0xf262004eUL, 0x6c0695edUL,
109 0x1b01a57bUL, 0x8208f4c1UL, 0xf50fc457UL, 0x65b0d9c6UL, 0x12b7e950UL,
110 0x8bbeb8eaUL, 0xfcb9887cUL, 0x62dd1ddfUL, 0x15da2d49UL, 0x8cd37cf3UL,
111 0xfbd44c65UL, 0x4db26158UL, 0x3ab551ceUL, 0xa3bc0074UL, 0xd4bb30e2UL,
112 0x4adfa541UL, 0x3dd895d7UL, 0xa4d1c46dUL, 0xd3d6f4fbUL, 0x4369e96aUL,
113 0x346ed9fcUL, 0xad678846UL, 0xda60b8d0UL, 0x44042d73UL, 0x33031de5UL,
114 0xaa0a4c5fUL, 0xdd0d7cc9UL, 0x5005713cUL, 0x270241aaUL, 0xbe0b1010UL,
115 0xc90c2086UL, 0x5768b525UL, 0x206f85b3UL, 0xb966d409UL, 0xce61e49fUL,
116 0x5edef90eUL, 0x29d9c998UL, 0xb0d09822UL, 0xc7d7a8b4UL, 0x59b33d17UL,
117 0x2eb40d81UL, 0xb7bd5c3bUL, 0xc0ba6cadUL, 0xedb88320UL, 0x9abfb3b6UL,
118 0x03b6e20cUL, 0x74b1d29aUL, 0xead54739UL, 0x9dd277afUL, 0x04db2615UL,
119 0x73dc1683UL, 0xe3630b12UL, 0x94643b84UL, 0x0d6d6a3eUL, 0x7a6a5aa8UL,
120 0xe40ecf0bUL, 0x9309ff9dUL, 0x0a00ae27UL, 0x7d079eb1UL, 0xf00f9344UL,
121 0x8708a3d2UL, 0x1e01f268UL, 0x6906c2feUL, 0xf762575dUL, 0x806567cbUL,
122 0x196c3671UL, 0x6e6b06e7UL, 0xfed41b76UL, 0x89d32be0UL, 0x10da7a5aUL,
123 0x67dd4accUL, 0xf9b9df6fUL, 0x8ebeeff9UL, 0x17b7be43UL, 0x60b08ed5UL,
124 0xd6d6a3e8UL, 0xa1d1937eUL, 0x38d8c2c4UL, 0x4fdff252UL, 0xd1bb67f1UL,
125 0xa6bc5767UL, 0x3fb506ddUL, 0x48b2364bUL, 0xd80d2bdaUL, 0xaf0a1b4cUL,
126 0x36034af6UL, 0x41047a60UL, 0xdf60efc3UL, 0xa867df55UL, 0x316e8eefUL,
127 0x4669be79UL, 0xcb61b38cUL, 0xbc66831aUL, 0x256fd2a0UL, 0x5268e236UL,
128 0xcc0c7795UL, 0xbb0b4703UL, 0x220216b9UL, 0x5505262fUL, 0xc5ba3bbeUL,
129 0xb2bd0b28UL, 0x2bb45a92UL, 0x5cb36a04UL, 0xc2d7ffa7UL, 0xb5d0cf31UL,
130 0x2cd99e8bUL, 0x5bdeae1dUL, 0x9b64c2b0UL, 0xec63f226UL, 0x756aa39cUL,
131 0x026d930aUL, 0x9c0906a9UL, 0xeb0e363fUL, 0x72076785UL, 0x05005713UL,
132 0x95bf4a82UL, 0xe2b87a14UL, 0x7bb12baeUL, 0x0cb61b38UL, 0x92d28e9bUL,
133 0xe5d5be0dUL, 0x7cdcefb7UL, 0x0bdbdf21UL, 0x86d3d2d4UL, 0xf1d4e242UL,
134 0x68ddb3f8UL, 0x1fda836eUL, 0x81be16cdUL, 0xf6b9265bUL, 0x6fb077e1UL,
135 0x18b74777UL, 0x88085ae6UL, 0xff0f6a70UL, 0x66063bcaUL, 0x11010b5cUL,
136 0x8f659effUL, 0xf862ae69UL, 0x616bffd3UL, 0x166ccf45UL, 0xa00ae278UL,
137 0xd70dd2eeUL, 0x4e048354UL, 0x3903b3c2UL, 0xa7672661UL, 0xd06016f7UL,
138 0x4969474dUL, 0x3e6e77dbUL, 0xaed16a4aUL, 0xd9d65adcUL, 0x40df0b66UL,
139 0x37d83bf0UL, 0xa9bcae53UL, 0xdebb9ec5UL, 0x47b2cf7fUL, 0x30b5ffe9UL,
140 0xbdbdf21cUL, 0xcabac28aUL, 0x53b39330UL, 0x24b4a3a6UL, 0xbad03605UL,
141 0xcdd70693UL, 0x54de5729UL, 0x23d967bfUL, 0xb3667a2eUL, 0xc4614ab8UL,
142 0x5d681b02UL, 0x2a6f2b94UL, 0xb40bbe37UL, 0xc30c8ea1UL, 0x5a05df1bUL,
143 0x2d02ef8dUL
144 };
145
146 #define D 32
147 #define P 0x82F63B78 // Reflection of Castagnoli (0x11EDC6F41)
148
149 #define TILL_CYCLE 31
150 uint32_t _crc32c_pow_2k_table[TILL_CYCLE]; // because _crc32c_pow_2k_table[TILL_CYCLE == 31] == _crc32c_pow_2k_table[0]
151
152 // A. Kadatch and B. Jenkins / Everything we know about CRC but afraid to forget September 3, 2010 8
153 // Listing 1: Multiplication of normalized polynomials
154 // "a" and "b" occupy D least significant bits.
155 uint32_t crc32c_multiply(uint32_t a, uint32_t b) {
156 uint32_t product = 0;
157 uint32_t b_pow_x_table[D + 1]; // b_pow_x_table[k] = (b * x**k) mod P
158 b_pow_x_table[0] = b;
159 for (int k = 0; k < D; ++k) {
160 // If "a" has non-zero coefficient at x**k,/ add ((b * x**k) mod P) to the result.
161 if ((a & (((uint32_t)1) << (D - 1 - k))) != 0) product ^= b_pow_x_table[k];
162
163 // Compute b_pow_x_table[k+1] = (b ** x**(k+1)) mod P.
164 if (b_pow_x_table[k] & 1) {
165 // If degree of (b_pow_x_table[k] * x) is D, then
166 // degree of (b_pow_x_table[k] * x - P) is less than D.
167 b_pow_x_table[k + 1] = (b_pow_x_table[k] >> 1) ^ P;
168 }
169 else {
170 b_pow_x_table[k + 1] = b_pow_x_table[k] >> 1;
171 }
172 }
173 return product;
174 }
175 #undef D
176 #undef P
177
178 // A. Kadatch and B. Jenkins / Everything we know about CRC but afraid to forget September 3, 2010 9
179 void crc32c_init_pow_2k(void) {
180 // _crc32c_pow_2k_table(0) =
181 // x^(2^k) mod P(x) = x mod P(x) = x
182 // Since we are operating on a reflected values
183 // x = 10b, reflect(x) = 0x40000000
184 _crc32c_pow_2k_table[0] = 0x40000000;
185
186 for (int k = 1; k < TILL_CYCLE; k++) {
187 // _crc32c_pow_2k_table(k+1) = _crc32c_pow_2k_table(k-1)^2 mod P(x)
188 uint32_t tmp = _crc32c_pow_2k_table[k - 1];
189 _crc32c_pow_2k_table[k] = crc32c_multiply(tmp, tmp);
190 }
191 }
192
193 // x^N mod P(x)
194 uint32_t crc32c_f_pow_n(uint32_t n) {
195 // result = 1 (polynomial)
196 uint32_t one, result = 0x80000000, i = 0;
197
198 while (one = (n & 1), (n == 1 || n - one > 0)) {
199 if (one) {
200 result = crc32c_multiply(result, _crc32c_pow_2k_table[i]);
201 }
202 n >>= 1;
203 i++;
204 }
205
206 return result;
207 }
208
209 juint *StubRoutines::x86::_crc32c_table;
210
211 void StubRoutines::x86::generate_CRC32C_table(bool is_pclmulqdq_table_supported) {
212
213 static juint pow_n[CRC32C_NUM_PRECOMPUTED_CONSTANTS];
214
215 crc32c_init_pow_2k();
216
217 pow_n[0] = crc32c_f_pow_n(CRC32C_HIGH * 8); // 8N * 8 = 64N
218 pow_n[1] = crc32c_f_pow_n(CRC32C_HIGH * 8 * 2); // 128N
219
220 pow_n[2] = crc32c_f_pow_n(CRC32C_MIDDLE * 8);
221 pow_n[3] = crc32c_f_pow_n(CRC32C_MIDDLE * 8 * 2);
222
223 pow_n[4] = crc32c_f_pow_n(CRC32C_LOW * 8);
224 pow_n[CRC32C_NUM_PRECOMPUTED_CONSTANTS - 1] =
225 crc32c_f_pow_n(CRC32C_LOW * 8 * 2);
226
227 if (is_pclmulqdq_table_supported) {
228 _crc32c_table = pow_n;
229 } else {
230 static julong pclmulqdq_table[CRC32C_NUM_PRECOMPUTED_CONSTANTS * 256];
231
232 for (int j = 0; j < CRC32C_NUM_PRECOMPUTED_CONSTANTS; j++) {
233 static juint X_CONST = pow_n[j];
234 for (int64_t i = 0; i < 256; i++) { // to force 64 bit wide computations
235 // S. Gueron / Information Processing Letters 112 (2012) 184
236 // Algorithm 3: Generating a carry-less multiplication lookup table.
237 // Input: A 32-bit constant, X_CONST.
238 // Output: A table of 256 entries, each one is a 64-bit quadword,
239 // that can be used for computing "byte" * X_CONST, for a given byte.
240 pclmulqdq_table[j * 256 + i] =
241 ((i & 1) * X_CONST) ^ ((i & 2) * X_CONST) ^ ((i & 4) * X_CONST) ^
242 ((i & 8) * X_CONST) ^ ((i & 16) * X_CONST) ^ ((i & 32) * X_CONST) ^
243 ((i & 64) * X_CONST) ^ ((i & 128) * X_CONST);
244 }
245 }
246 _crc32c_table = (juint*)pclmulqdq_table;
247 }
248 }
249
250 ALIGNED_(64) juint StubRoutines::x86::_k256[] =
251 {
252 0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
253 0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
254 0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
255 0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
256 0xe49b69c1UL, 0xefbe4786UL, 0x0fc19dc6UL, 0x240ca1ccUL,
257 0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
258 0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
259 0xc6e00bf3UL, 0xd5a79147UL, 0x06ca6351UL, 0x14292967UL,
260 0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
261 0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
262 0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
263 0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
264 0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
265 0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
266 0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
267 0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL
268 };