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