| 1 |
/* Copyright 2024 Marc A. Lehmann */ |
| 2 |
/* Copyright 2016 Ferry Toth, Exalon Delft BV, The Netherlands */ |
| 3 |
/* |
| 4 |
This software is provided 'as-is', without any express or implied |
| 5 |
warranty. In no event will the author be held liable for any damages |
| 6 |
arising from the use of this software. |
| 7 |
|
| 8 |
Permission is granted to anyone to use this software for any purpose, |
| 9 |
including commercial applications, and to alter it and redistribute it |
| 10 |
freely, subject to the following restrictions: |
| 11 |
|
| 12 |
1. The origin of this software must not be misrepresented; you must not |
| 13 |
claim that you wrote the original software. If you use this software |
| 14 |
in a product, an acknowledgment in the product documentation would be |
| 15 |
appreciated but is not required. |
| 16 |
2. Altered source versions must be plainly marked as such, and must not be |
| 17 |
misrepresented as being the original software. |
| 18 |
3. This notice may not be removed or altered from any source distribution. |
| 19 |
|
| 20 |
Ferry Toth |
| 21 |
ftoth@exalondelft.nl |
| 22 |
*/ |
| 23 |
|
| 24 |
/* Use hardware CRC instruction on Intel SSE 4.2 processors. This computes a |
| 25 |
CRC-32C, *not* the CRC-32 used by Ethernet and zip, gzip, etc. Where efficient |
| 26 |
3 crc32q instructions are used which a single core can execute in parallel. |
| 27 |
This compensates for the latency of a single crc32q instruction. Combining the |
| 28 |
3 CRC-32C bytes is done using the pclmulqdq instruction, which has overhead of |
| 29 |
its own, and makes this code path only efficient for buffer sizes above 216 bytes. |
| 30 |
All code requiring a crc32q instruction is done inside a macro, for which alternative |
| 31 |
code is generated in case of a 32 bit platform. |
| 32 |
|
| 33 |
This code is a port of Intels crc_iscsi_v_pcl.asm assembly code (which is part of |
| 34 |
this project as well as in a modified form the linux kernel) and reaches the same |
| 35 |
throughput on 64bit platforms. The main advantage of this port is that it was |
| 36 |
relatively easy to port to 32bit platforms (like Intel Edison which currently has |
| 37 |
only 32bit support). Being written in C it is of course easier to maintain and possibly |
| 38 |
optimize further */ |
| 39 |
|
| 40 |
/* Version history: |
| 41 |
1.0 07 May 2016 Ferry Toth - First version |
| 42 |
*/ |
| 43 |
|
| 44 |
#include <stddef.h> |
| 45 |
#include <stdint.h> |
| 46 |
#include "crc32intelc.h" |
| 47 |
#include "crc32inteltable.c" |
| 48 |
#include <x86intrin.h> |
| 49 |
|
| 50 |
/* Compute CRC-32C using the Intel hardware instruction. */ |
| 51 |
static uint32_t crc32cIntelC ( uint32_t crc, const void *buf, size_t len ) |
| 52 |
{ |
| 53 |
const unsigned char *next = ( const unsigned char * ) buf; |
| 54 |
unsigned long count; |
| 55 |
CRC_NATIVE crc0, crc1, crc2; |
| 56 |
crc0 = crc; |
| 57 |
|
| 58 |
if ( len >= 8 ) { |
| 59 |
// if len > 216 then align and use triplets |
| 60 |
if ( len > 216 ) { |
| 61 |
{ |
| 62 |
uint32_t crc32bit = crc0; // create this block actually prevent 2 asignments |
| 63 |
unsigned long align = ( 8 - ( uintptr_t ) next ) % 8; // byte to boundary |
| 64 |
len -= align; |
| 65 |
if ( align & 0x04 ) { |
| 66 |
crc32bit = __builtin_ia32_crc32si ( crc32bit, * ( uint32_t* ) next ); |
| 67 |
next += sizeof(uint32_t); |
| 68 |
}; |
| 69 |
if ( align & 0x02 ) { |
| 70 |
crc32bit = __builtin_ia32_crc32hi ( crc32bit, * ( uint16_t* ) next ); |
| 71 |
next += sizeof(uint16_t); |
| 72 |
}; |
| 73 |
|
| 74 |
if ( align & 0x01 ) { |
| 75 |
crc32bit = __builtin_ia32_crc32qi ( crc32bit, * ( next ) ); |
| 76 |
next++; |
| 77 |
}; |
| 78 |
crc0 = crc32bit; |
| 79 |
}; |
| 80 |
|
| 81 |
// use Duff's device, a for() loop inside a switch() statement. This is Legal |
| 82 |
// needs to execute at least once, round len down to nearast triplet multiple |
| 83 |
count = len / 24; // number of triplets |
| 84 |
len %= 24; // bytes remaining |
| 85 |
unsigned long n = count / 128; // #blocks = first block + full blocks |
| 86 |
unsigned long block_size = count % 128; |
| 87 |
if ( block_size == 0 ) { |
| 88 |
block_size = 128; |
| 89 |
} else { |
| 90 |
n++; |
| 91 |
}; |
| 92 |
const uint64_t *next0 = ( uint64_t* ) next + block_size; // points to the first byte of the next block |
| 93 |
const uint64_t *next1 = next0 + block_size; |
| 94 |
const uint64_t *next2 = next1 + block_size; |
| 95 |
|
| 96 |
crc1 = crc2 = 0; |
| 97 |
switch ( block_size ) { |
| 98 |
case 128: |
| 99 |
do { |
| 100 |
CRCtriplet ( crc, next, -128 ); // jumps here for a full block of len 128 |
| 101 |
case 127: |
| 102 |
CRCtriplet ( crc, next, -127 ); // jumps here or below for the first block smaller |
| 103 |
case 126: |
| 104 |
CRCtriplet ( crc, next, -126 ); // than 128 |
| 105 |
case 125: |
| 106 |
CRCtriplet ( crc, next, -125 ); |
| 107 |
case 124: |
| 108 |
CRCtriplet ( crc, next, -124 ); |
| 109 |
case 123: |
| 110 |
CRCtriplet ( crc, next, -123 ); |
| 111 |
case 122: |
| 112 |
CRCtriplet ( crc, next, -122 ); |
| 113 |
case 121: |
| 114 |
CRCtriplet ( crc, next, -121 ); |
| 115 |
case 120: |
| 116 |
CRCtriplet ( crc, next, -120 ); |
| 117 |
case 119: |
| 118 |
CRCtriplet ( crc, next, -119 ); |
| 119 |
case 118: |
| 120 |
CRCtriplet ( crc, next, -118 ); |
| 121 |
case 117: |
| 122 |
CRCtriplet ( crc, next, -117 ); |
| 123 |
case 116: |
| 124 |
CRCtriplet ( crc, next, -116 ); |
| 125 |
case 115: |
| 126 |
CRCtriplet ( crc, next, -115 ); |
| 127 |
case 114: |
| 128 |
CRCtriplet ( crc, next, -114 ); |
| 129 |
case 113: |
| 130 |
CRCtriplet ( crc, next, -113 ); |
| 131 |
case 112: |
| 132 |
CRCtriplet ( crc, next, -112 ); |
| 133 |
case 111: |
| 134 |
CRCtriplet ( crc, next, -111 ); |
| 135 |
case 110: |
| 136 |
CRCtriplet ( crc, next, -110 ); |
| 137 |
case 109: |
| 138 |
CRCtriplet ( crc, next, -109 ); |
| 139 |
case 108: |
| 140 |
CRCtriplet ( crc, next, -108 ); |
| 141 |
case 107: |
| 142 |
CRCtriplet ( crc, next, -107 ); |
| 143 |
case 106: |
| 144 |
CRCtriplet ( crc, next, -106 ); |
| 145 |
case 105: |
| 146 |
CRCtriplet ( crc, next, -105 ); |
| 147 |
case 104: |
| 148 |
CRCtriplet ( crc, next, -104 ); |
| 149 |
case 103: |
| 150 |
CRCtriplet ( crc, next, -103 ); |
| 151 |
case 102: |
| 152 |
CRCtriplet ( crc, next, -102 ); |
| 153 |
case 101: |
| 154 |
CRCtriplet ( crc, next, -101 ); |
| 155 |
case 100: |
| 156 |
CRCtriplet ( crc, next, -100 ); |
| 157 |
case 99: |
| 158 |
CRCtriplet ( crc, next, -99 ); |
| 159 |
case 98: |
| 160 |
CRCtriplet ( crc, next, -98 ); |
| 161 |
case 97: |
| 162 |
CRCtriplet ( crc, next, -97 ); |
| 163 |
case 96: |
| 164 |
CRCtriplet ( crc, next, -96 ); |
| 165 |
case 95: |
| 166 |
CRCtriplet ( crc, next, -95 ); |
| 167 |
case 94: |
| 168 |
CRCtriplet ( crc, next, -94 ); |
| 169 |
case 93: |
| 170 |
CRCtriplet ( crc, next, -93 ); |
| 171 |
case 92: |
| 172 |
CRCtriplet ( crc, next, -92 ); |
| 173 |
case 91: |
| 174 |
CRCtriplet ( crc, next, -91 ); |
| 175 |
case 90: |
| 176 |
CRCtriplet ( crc, next, -90 ); |
| 177 |
case 89: |
| 178 |
CRCtriplet ( crc, next, -89 ); |
| 179 |
case 88: |
| 180 |
CRCtriplet ( crc, next, -88 ); |
| 181 |
case 87: |
| 182 |
CRCtriplet ( crc, next, -87 ); |
| 183 |
case 86: |
| 184 |
CRCtriplet ( crc, next, -86 ); |
| 185 |
case 85: |
| 186 |
CRCtriplet ( crc, next, -85 ); |
| 187 |
case 84: |
| 188 |
CRCtriplet ( crc, next, -84 ); |
| 189 |
case 83: |
| 190 |
CRCtriplet ( crc, next, -83 ); |
| 191 |
case 82: |
| 192 |
CRCtriplet ( crc, next, -82 ); |
| 193 |
case 81: |
| 194 |
CRCtriplet ( crc, next, -81 ); |
| 195 |
case 80: |
| 196 |
CRCtriplet ( crc, next, -80 ); |
| 197 |
case 79: |
| 198 |
CRCtriplet ( crc, next, -79 ); |
| 199 |
case 78: |
| 200 |
CRCtriplet ( crc, next, -78 ); |
| 201 |
case 77: |
| 202 |
CRCtriplet ( crc, next, -77 ); |
| 203 |
case 76: |
| 204 |
CRCtriplet ( crc, next, -76 ); |
| 205 |
case 75: |
| 206 |
CRCtriplet ( crc, next, -75 ); |
| 207 |
case 74: |
| 208 |
CRCtriplet ( crc, next, -74 ); |
| 209 |
case 73: |
| 210 |
CRCtriplet ( crc, next, -73 ); |
| 211 |
case 72: |
| 212 |
CRCtriplet ( crc, next, -72 ); |
| 213 |
case 71: |
| 214 |
CRCtriplet ( crc, next, -71 ); |
| 215 |
case 70: |
| 216 |
CRCtriplet ( crc, next, -70 ); |
| 217 |
case 69: |
| 218 |
CRCtriplet ( crc, next, -69 ); |
| 219 |
case 68: |
| 220 |
CRCtriplet ( crc, next, -68 ); |
| 221 |
case 67: |
| 222 |
CRCtriplet ( crc, next, -67 ); |
| 223 |
case 66: |
| 224 |
CRCtriplet ( crc, next, -66 ); |
| 225 |
case 65: |
| 226 |
CRCtriplet ( crc, next, -65 ); |
| 227 |
case 64: |
| 228 |
CRCtriplet ( crc, next, -64 ); |
| 229 |
case 63: |
| 230 |
CRCtriplet ( crc, next, -63 ); |
| 231 |
case 62: |
| 232 |
CRCtriplet ( crc, next, -62 ); |
| 233 |
case 61: |
| 234 |
CRCtriplet ( crc, next, -61 ); |
| 235 |
case 60: |
| 236 |
CRCtriplet ( crc, next, -60 ); |
| 237 |
case 59: |
| 238 |
CRCtriplet ( crc, next, -59 ); |
| 239 |
case 58: |
| 240 |
CRCtriplet ( crc, next, -58 ); |
| 241 |
case 57: |
| 242 |
CRCtriplet ( crc, next, -57 ); |
| 243 |
case 56: |
| 244 |
CRCtriplet ( crc, next, -56 ); |
| 245 |
case 55: |
| 246 |
CRCtriplet ( crc, next, -55 ); |
| 247 |
case 54: |
| 248 |
CRCtriplet ( crc, next, -54 ); |
| 249 |
case 53: |
| 250 |
CRCtriplet ( crc, next, -53 ); |
| 251 |
case 52: |
| 252 |
CRCtriplet ( crc, next, -52 ); |
| 253 |
case 51: |
| 254 |
CRCtriplet ( crc, next, -51 ); |
| 255 |
case 50: |
| 256 |
CRCtriplet ( crc, next, -50 ); |
| 257 |
case 49: |
| 258 |
CRCtriplet ( crc, next, -49 ); |
| 259 |
case 48: |
| 260 |
CRCtriplet ( crc, next, -48 ); |
| 261 |
case 47: |
| 262 |
CRCtriplet ( crc, next, -47 ); |
| 263 |
case 46: |
| 264 |
CRCtriplet ( crc, next, -46 ); |
| 265 |
case 45: |
| 266 |
CRCtriplet ( crc, next, -45 ); |
| 267 |
case 44: |
| 268 |
CRCtriplet ( crc, next, -44 ); |
| 269 |
case 43: |
| 270 |
CRCtriplet ( crc, next, -43 ); |
| 271 |
case 42: |
| 272 |
CRCtriplet ( crc, next, -42 ); |
| 273 |
case 41: |
| 274 |
CRCtriplet ( crc, next, -41 ); |
| 275 |
case 40: |
| 276 |
CRCtriplet ( crc, next, -40 ); |
| 277 |
case 39: |
| 278 |
CRCtriplet ( crc, next, -39 ); |
| 279 |
case 38: |
| 280 |
CRCtriplet ( crc, next, -38 ); |
| 281 |
case 37: |
| 282 |
CRCtriplet ( crc, next, -37 ); |
| 283 |
case 36: |
| 284 |
CRCtriplet ( crc, next, -36 ); |
| 285 |
case 35: |
| 286 |
CRCtriplet ( crc, next, -35 ); |
| 287 |
case 34: |
| 288 |
CRCtriplet ( crc, next, -34 ); |
| 289 |
case 33: |
| 290 |
CRCtriplet ( crc, next, -33 ); |
| 291 |
case 32: |
| 292 |
CRCtriplet ( crc, next, -32 ); |
| 293 |
case 31: |
| 294 |
CRCtriplet ( crc, next, -31 ); |
| 295 |
case 30: |
| 296 |
CRCtriplet ( crc, next, -30 ); |
| 297 |
case 29: |
| 298 |
CRCtriplet ( crc, next, -29 ); |
| 299 |
case 28: |
| 300 |
CRCtriplet ( crc, next, -28 ); |
| 301 |
case 27: |
| 302 |
CRCtriplet ( crc, next, -27 ); |
| 303 |
case 26: |
| 304 |
CRCtriplet ( crc, next, -26 ); |
| 305 |
case 25: |
| 306 |
CRCtriplet ( crc, next, -25 ); |
| 307 |
case 24: |
| 308 |
CRCtriplet ( crc, next, -24 ); |
| 309 |
case 23: |
| 310 |
CRCtriplet ( crc, next, -23 ); |
| 311 |
case 22: |
| 312 |
CRCtriplet ( crc, next, -22 ); |
| 313 |
case 21: |
| 314 |
CRCtriplet ( crc, next, -21 ); |
| 315 |
case 20: |
| 316 |
CRCtriplet ( crc, next, -20 ); |
| 317 |
case 19: |
| 318 |
CRCtriplet ( crc, next, -19 ); |
| 319 |
case 18: |
| 320 |
CRCtriplet ( crc, next, -18 ); |
| 321 |
case 17: |
| 322 |
CRCtriplet ( crc, next, -17 ); |
| 323 |
case 16: |
| 324 |
CRCtriplet ( crc, next, -16 ); |
| 325 |
case 15: |
| 326 |
CRCtriplet ( crc, next, -15 ); |
| 327 |
case 14: |
| 328 |
CRCtriplet ( crc, next, -14 ); |
| 329 |
case 13: |
| 330 |
CRCtriplet ( crc, next, -13 ); |
| 331 |
case 12: |
| 332 |
CRCtriplet ( crc, next, -12 ); |
| 333 |
case 11: |
| 334 |
CRCtriplet ( crc, next, -11 ); |
| 335 |
case 10: |
| 336 |
CRCtriplet ( crc, next, -10 ); |
| 337 |
case 9: |
| 338 |
CRCtriplet ( crc, next, -9 ); |
| 339 |
case 8: |
| 340 |
CRCtriplet ( crc, next, -8 ); |
| 341 |
case 7: |
| 342 |
CRCtriplet ( crc, next, -7 ); |
| 343 |
case 6: |
| 344 |
CRCtriplet ( crc, next, -6 ); |
| 345 |
case 5: |
| 346 |
CRCtriplet ( crc, next, -5 ); |
| 347 |
case 4: |
| 348 |
CRCtriplet ( crc, next, -4 ); |
| 349 |
case 3: |
| 350 |
CRCtriplet ( crc, next, -3 ); |
| 351 |
case 2: |
| 352 |
CRCtriplet ( crc, next, -2 ); |
| 353 |
case 1: |
| 354 |
CRCduplet ( crc, next, -1 ); // the final triplet is actually only 2 |
| 355 |
CombineCRC(); |
| 356 |
if ( --n > 0 ) { |
| 357 |
crc1 = crc2 = 0; |
| 358 |
block_size = 128; |
| 359 |
next0 = next2 + 128; // points to the first byte of the next block |
| 360 |
next1 = next0 + 128; // from here on all blocks are 128 long |
| 361 |
next2 = next1 + 128; |
| 362 |
}; |
| 363 |
case 0: |
| 364 |
; |
| 365 |
} while ( n > 0 ); |
| 366 |
}; |
| 367 |
next = ( const unsigned char* ) next2; |
| 368 |
}; |
| 369 |
unsigned count = len / 8; // 216 of less bytes is 27 or less singlets |
| 370 |
len %= 8; |
| 371 |
next += ( count * 8 ); |
| 372 |
switch ( count ) { |
| 373 |
case 27: |
| 374 |
CRCsinglet ( crc0, next, -27 * 8 ); |
| 375 |
case 26: |
| 376 |
CRCsinglet ( crc0, next, -26 * 8 ); |
| 377 |
case 25: |
| 378 |
CRCsinglet ( crc0, next, -25 * 8 ); |
| 379 |
case 24: |
| 380 |
CRCsinglet ( crc0, next, -24 * 8 ); |
| 381 |
case 23: |
| 382 |
CRCsinglet ( crc0, next, -23 * 8 ); |
| 383 |
case 22: |
| 384 |
CRCsinglet ( crc0, next, -22 * 8 ); |
| 385 |
case 21: |
| 386 |
CRCsinglet ( crc0, next, -21 * 8 ); |
| 387 |
case 20: |
| 388 |
CRCsinglet ( crc0, next, -20 * 8 ); |
| 389 |
case 19: |
| 390 |
CRCsinglet ( crc0, next, -19 * 8 ); |
| 391 |
case 18: |
| 392 |
CRCsinglet ( crc0, next, -18 * 8 ); |
| 393 |
case 17: |
| 394 |
CRCsinglet ( crc0, next, -17 * 8 ); |
| 395 |
case 16: |
| 396 |
CRCsinglet ( crc0, next, -16 * 8 ); |
| 397 |
case 15: |
| 398 |
CRCsinglet ( crc0, next, -15 * 8 ); |
| 399 |
case 14: |
| 400 |
CRCsinglet ( crc0, next, -14 * 8 ); |
| 401 |
case 13: |
| 402 |
CRCsinglet ( crc0, next, -13 * 8 ); |
| 403 |
case 12: |
| 404 |
CRCsinglet ( crc0, next, -12 * 8 ); |
| 405 |
case 11: |
| 406 |
CRCsinglet ( crc0, next, -11 * 8 ); |
| 407 |
case 10: |
| 408 |
CRCsinglet ( crc0, next, -10 * 8 ); |
| 409 |
case 9: |
| 410 |
CRCsinglet ( crc0, next, -9 * 8 ); |
| 411 |
case 8: |
| 412 |
CRCsinglet ( crc0, next, -8 * 8 ); |
| 413 |
case 7: |
| 414 |
CRCsinglet ( crc0, next, -7 * 8 ); |
| 415 |
case 6: |
| 416 |
CRCsinglet ( crc0, next, -6 * 8 ); |
| 417 |
case 5: |
| 418 |
CRCsinglet ( crc0, next, -5 * 8 ); |
| 419 |
case 4: |
| 420 |
CRCsinglet ( crc0, next, -4 * 8 ); |
| 421 |
case 3: |
| 422 |
CRCsinglet ( crc0, next, -3 * 8 ); |
| 423 |
case 2: |
| 424 |
CRCsinglet ( crc0, next, -2 * 8 ); |
| 425 |
case 1: |
| 426 |
CRCsinglet ( crc0, next, -1 * 8 ); |
| 427 |
case 0: |
| 428 |
; |
| 429 |
}; |
| 430 |
|
| 431 |
}; |
| 432 |
{ |
| 433 |
uint32_t crc32bit = crc0; |
| 434 |
// less than 8 bytes remain |
| 435 |
/* compute the crc for up to seven trailing bytes */ |
| 436 |
if ( len & 0x04 ) { |
| 437 |
crc32bit = __builtin_ia32_crc32si ( crc32bit, * ( uint32_t* ) next ); |
| 438 |
next += 4; |
| 439 |
}; |
| 440 |
if ( len & 0x02 ) { |
| 441 |
crc32bit = __builtin_ia32_crc32hi ( crc32bit, * ( uint16_t* ) next ); |
| 442 |
next += 2; |
| 443 |
}; |
| 444 |
|
| 445 |
if ( len & 0x01 ) { |
| 446 |
crc32bit = __builtin_ia32_crc32qi ( crc32bit, * ( next ) ); |
| 447 |
}; |
| 448 |
return ( uint32_t ) crc32bit; |
| 449 |
}; |
| 450 |
}; |
| 451 |
|
