File indexing completed on 2023-03-17 11:00:30
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025
0026
0027
0028
0029
0030
0031
0032
0033
0034
0035
0036
0037
0038
0039
0040
0041
0042 #include <cstdio>
0043 #include <cstdlib>
0044 #include <cstdint>
0045 #include <unistd.h>
0046 #include <pthread.h>
0047
0048
0049 #define POLY 0x82f63b78
0050
0051
0052 static pthread_once_t crc32c_once_sw = PTHREAD_ONCE_INIT;
0053 static uint32_t crc32c_table[8][256];
0054
0055
0056 static void crc32c_init_sw(void)
0057 {
0058 uint32_t n, crc, k;
0059
0060 for (n = 0; n < 256; n++) {
0061 crc = n;
0062 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0063 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0064 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0065 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0066 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0067 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0068 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0069 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
0070 crc32c_table[0][n] = crc;
0071 }
0072 for (n = 0; n < 256; n++) {
0073 crc = crc32c_table[0][n];
0074 for (k = 1; k < 8; k++) {
0075 crc = crc32c_table[0][crc & 0xff] ^ (crc >> 8);
0076 crc32c_table[k][n] = crc;
0077 }
0078 }
0079 }
0080
0081
0082
0083
0084 static uint32_t crc32c_sw(uint32_t crci, const unsigned char *buf, size_t len)
0085 {
0086 const unsigned char *next = buf;
0087 uint64_t crc;
0088
0089 pthread_once(&crc32c_once_sw, crc32c_init_sw);
0090 crc = crci ^ 0xffffffff;
0091 while (len && ((const uintptr_t)next & 7) != 0) {
0092 crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
0093 len--;
0094 }
0095 while (len >= 8) {
0096 crc ^= *(uint64_t *)next;
0097 crc = crc32c_table[7][crc & 0xff] ^
0098 crc32c_table[6][(crc >> 8) & 0xff] ^
0099 crc32c_table[5][(crc >> 16) & 0xff] ^
0100 crc32c_table[4][(crc >> 24) & 0xff] ^
0101 crc32c_table[3][(crc >> 32) & 0xff] ^
0102 crc32c_table[2][(crc >> 40) & 0xff] ^
0103 crc32c_table[1][(crc >> 48) & 0xff] ^
0104 crc32c_table[0][crc >> 56];
0105 next += 8;
0106 len -= 8;
0107 }
0108 while (len) {
0109 crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
0110 len--;
0111 }
0112 return (uint32_t)crc ^ 0xffffffff;
0113 }
0114
0115 #if defined(__x86_64__)
0116
0117
0118
0119
0120 static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
0121 {
0122 uint32_t sum;
0123
0124 sum = 0;
0125 while (vec) {
0126 if (vec & 1)
0127 sum ^= *mat;
0128 vec >>= 1;
0129 mat++;
0130 }
0131 return sum;
0132 }
0133
0134
0135
0136 static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat)
0137 {
0138 int n;
0139
0140 for (n = 0; n < 32; n++)
0141 square[n] = gf2_matrix_times(mat, mat[n]);
0142 }
0143
0144
0145
0146
0147
0148
0149 static void crc32c_zeros_op(uint32_t *even, size_t len)
0150 {
0151 int n;
0152 uint32_t row;
0153 uint32_t odd[32];
0154
0155
0156 odd[0] = POLY;
0157 row = 1;
0158 for (n = 1; n < 32; n++) {
0159 odd[n] = row;
0160 row <<= 1;
0161 }
0162
0163
0164 gf2_matrix_square(even, odd);
0165
0166
0167 gf2_matrix_square(odd, even);
0168
0169
0170
0171
0172 do {
0173 gf2_matrix_square(even, odd);
0174 len >>= 1;
0175 if (len == 0)
0176 return;
0177 gf2_matrix_square(odd, even);
0178 len >>= 1;
0179 } while (len);
0180
0181
0182 for (n = 0; n < 32; n++)
0183 even[n] = odd[n];
0184 }
0185
0186
0187
0188 static void crc32c_zeros(uint32_t zeros[][256], size_t len)
0189 {
0190 uint32_t n;
0191 uint32_t op[32];
0192
0193 crc32c_zeros_op(op, len);
0194 for (n = 0; n < 256; n++) {
0195 zeros[0][n] = gf2_matrix_times(op, n);
0196 zeros[1][n] = gf2_matrix_times(op, n << 8);
0197 zeros[2][n] = gf2_matrix_times(op, n << 16);
0198 zeros[3][n] = gf2_matrix_times(op, n << 24);
0199 }
0200 }
0201
0202
0203 static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc)
0204 {
0205 return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
0206 zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
0207 }
0208
0209
0210
0211
0212 #define LONG 8192
0213 #define LONGx1 "8192"
0214 #define LONGx2 "16384"
0215 #define SHORT 256
0216 #define SHORTx1 "256"
0217 #define SHORTx2 "512"
0218
0219
0220 static pthread_once_t crc32c_once_hw = PTHREAD_ONCE_INIT;
0221 static uint32_t crc32c_long[4][256];
0222 static uint32_t crc32c_short[4][256];
0223
0224
0225 static void crc32c_init_hw(void)
0226 {
0227 crc32c_zeros(crc32c_long, LONG);
0228 crc32c_zeros(crc32c_short, SHORT);
0229 }
0230
0231
0232 static uint32_t crc32c_hw(uint32_t crc, const unsigned char *buf, size_t len)
0233 {
0234 const unsigned char *next = buf;
0235 const unsigned char *end;
0236 uint64_t crc0, crc1, crc2;
0237
0238
0239 pthread_once(&crc32c_once_hw, crc32c_init_hw);
0240
0241
0242 crc0 = crc ^ 0xffffffff;
0243
0244
0245
0246 while (len && ((const uintptr_t)next & 7) != 0) {
0247 __asm__("crc32b\t" "(%1), %0"
0248 : "=r"(crc0)
0249 : "r"(next), "0"(crc0));
0250 next++;
0251 len--;
0252 }
0253
0254
0255
0256
0257
0258 while (len >= LONG*3) {
0259 crc1 = 0;
0260 crc2 = 0;
0261 end = next + LONG;
0262 do {
0263 __asm__("crc32q\t" "(%3), %0\n\t"
0264 "crc32q\t" LONGx1 "(%3), %1\n\t"
0265 "crc32q\t" LONGx2 "(%3), %2"
0266 : "=r"(crc0), "=r"(crc1), "=r"(crc2)
0267 : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
0268 next += 8;
0269 } while (next < end);
0270 crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
0271 crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
0272 next += LONG*2;
0273 len -= LONG*3;
0274 }
0275
0276
0277
0278 while (len >= SHORT*3) {
0279 crc1 = 0;
0280 crc2 = 0;
0281 end = next + SHORT;
0282 do {
0283 __asm__("crc32q\t" "(%3), %0\n\t"
0284 "crc32q\t" SHORTx1 "(%3), %1\n\t"
0285 "crc32q\t" SHORTx2 "(%3), %2"
0286 : "=r"(crc0), "=r"(crc1), "=r"(crc2)
0287 : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
0288 next += 8;
0289 } while (next < end);
0290 crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
0291 crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
0292 next += SHORT*2;
0293 len -= SHORT*3;
0294 }
0295
0296
0297
0298 end = next + (len - (len & 7));
0299 while (next < end) {
0300 __asm__("crc32q\t" "(%1), %0"
0301 : "=r"(crc0)
0302 : "r"(next), "0"(crc0));
0303 next += 8;
0304 }
0305 len &= 7;
0306
0307
0308 while (len) {
0309 __asm__("crc32b\t" "(%1), %0"
0310 : "=r"(crc0)
0311 : "r"(next), "0"(crc0));
0312 next++;
0313 len--;
0314 }
0315
0316
0317 return (uint32_t)crc0 ^ 0xffffffff;
0318 }
0319
0320
0321
0322
0323
0324
0325 #define SSE42(have) \
0326 do { \
0327 uint32_t eax, ecx; \
0328 eax = 1; \
0329 __asm__("cpuid" \
0330 : "=c"(ecx) \
0331 : "a"(eax) \
0332 : "%ebx", "%edx"); \
0333 (have) = (ecx >> 20) & 1; \
0334 } while (0)
0335
0336 #endif
0337
0338
0339
0340 uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len)
0341 {
0342 #if defined(__x86_64__)
0343 int sse42;
0344
0345 SSE42(sse42);
0346 return sse42 ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
0347 #else
0348 return crc32c_sw(crc, buf, len);
0349 #endif
0350 }
0351
0352
0353
0354 bool crc32c_hw_test()
0355 {
0356
0357 #if defined(__x86_64__)
0358 int sse42;
0359
0360 SSE42(sse42);
0361 return sse42;
0362 #else
0363 return 0;
0364 #endif
0365 }
0366