1/* 2 * Implement fast CRC32C with PCLMULQDQ instructions. (x86_64) 3 * 4 * The white paper on CRC32C calculations with PCLMULQDQ instruction can be 5 * downloaded from: 6 * http://download.intel.com/design/intarch/papers/323405.pdf 7 * 8 * Copyright (C) 2012 Intel Corporation. 9 * 10 * Authors: 11 * Wajdi Feghali <wajdi.k.feghali@intel.com> 12 * James Guilford <james.guilford@intel.com> 13 * David Cote <david.m.cote@intel.com> 14 * Tim Chen <tim.c.chen@linux.intel.com> 15 * 16 * This software is available to you under a choice of one of two 17 * licenses. You may choose to be licensed under the terms of the GNU 18 * General Public License (GPL) Version 2, available from the file 19 * COPYING in the main directory of this source tree, or the 20 * OpenIB.org BSD license below: 21 * 22 * Redistribution and use in source and binary forms, with or 23 * without modification, are permitted provided that the following 24 * conditions are met: 25 * 26 * - Redistributions of source code must retain the above 27 * copyright notice, this list of conditions and the following 28 * disclaimer. 29 * 30 * - Redistributions in binary form must reproduce the above 31 * copyright notice, this list of conditions and the following 32 * disclaimer in the documentation and/or other materials 33 * provided with the distribution. 34 * 35 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 36 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 37 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 38 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 39 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 40 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 41 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 42 * SOFTWARE. 43 */ 44 45#include <linux/linkage.h> 46 47## ISCSI CRC 32 Implementation with crc32 and pclmulqdq Instruction 48 49.macro LABEL prefix n 50\prefix\n\(): 51.endm 52 53.macro JMPTBL_ENTRY i 54.word crc_\i - crc_array 55.endm 56 57.macro JNC_LESS_THAN j 58 jnc less_than_\j 59.endm 60 61# Define threshold where buffers are considered "small" and routed to more 62# efficient "by-1" code. This "by-1" code only handles up to 255 bytes, so 63# SMALL_SIZE can be no larger than 255. 64 65#define SMALL_SIZE 200 66 67.if (SMALL_SIZE > 255) 68.error "SMALL_ SIZE must be < 256" 69.endif 70 71# unsigned int crc_pcl(u8 *buffer, int len, unsigned int crc_init); 72 73ENTRY(crc_pcl) 74#define bufp %rdi 75#define bufp_dw %edi 76#define bufp_w %di 77#define bufp_b %dil 78#define bufptmp %rcx 79#define block_0 %rcx 80#define block_1 %rdx 81#define block_2 %r11 82#define len %rsi 83#define len_dw %esi 84#define len_w %si 85#define len_b %sil 86#define crc_init_arg %rdx 87#define tmp %rbx 88#define crc_init %r8 89#define crc_init_dw %r8d 90#define crc1 %r9 91#define crc2 %r10 92 93 pushq %rbx 94 pushq %rdi 95 pushq %rsi 96 97 ## Move crc_init for Linux to a different 98 mov crc_init_arg, crc_init 99 100 ################################################################ 101 ## 1) ALIGN: 102 ################################################################ 103 104 mov bufp, bufptmp # rdi = *buf 105 neg bufp 106 and $7, bufp # calculate the unalignment amount of 107 # the address 108 je proc_block # Skip if aligned 109 110 ## If len is less than 8 and we're unaligned, we need to jump 111 ## to special code to avoid reading beyond the end of the buffer 112 cmp $8, len 113 jae do_align 114 # less_than_8 expects length in upper 3 bits of len_dw 115 # less_than_8_post_shl1 expects length = carryflag * 8 + len_dw[31:30] 116 shl $32-3+1, len_dw 117 jmp less_than_8_post_shl1 118 119do_align: 120 #### Calculate CRC of unaligned bytes of the buffer (if any) 121 movq (bufptmp), tmp # load a quadward from the buffer 122 add bufp, bufptmp # align buffer pointer for quadword 123 # processing 124 sub bufp, len # update buffer length 125align_loop: 126 crc32b %bl, crc_init_dw # compute crc32 of 1-byte 127 shr $8, tmp # get next byte 128 dec bufp 129 jne align_loop 130 131proc_block: 132 133 ################################################################ 134 ## 2) PROCESS BLOCKS: 135 ################################################################ 136 137 ## compute num of bytes to be processed 138 movq len, tmp # save num bytes in tmp 139 140 cmpq $128*24, len 141 jae full_block 142 143continue_block: 144 cmpq $SMALL_SIZE, len 145 jb small 146 147 ## len < 128*24 148 movq $2731, %rax # 2731 = ceil(2^16 / 24) 149 mul len_dw 150 shrq $16, %rax 151 152 ## eax contains floor(bytes / 24) = num 24-byte chunks to do 153 154 ## process rax 24-byte chunks (128 >= rax >= 0) 155 156 ## compute end address of each block 157 ## block 0 (base addr + RAX * 8) 158 ## block 1 (base addr + RAX * 16) 159 ## block 2 (base addr + RAX * 24) 160 lea (bufptmp, %rax, 8), block_0 161 lea (block_0, %rax, 8), block_1 162 lea (block_1, %rax, 8), block_2 163 164 xor crc1, crc1 165 xor crc2, crc2 166 167 ## branch into array 168 lea jump_table(%rip), bufp 169 movzxw (bufp, %rax, 2), len 170 offset=crc_array-jump_table 171 lea offset(bufp, len, 1), bufp 172 jmp *bufp 173 174 ################################################################ 175 ## 2a) PROCESS FULL BLOCKS: 176 ################################################################ 177full_block: 178 movq $128,%rax 179 lea 128*8*2(block_0), block_1 180 lea 128*8*3(block_0), block_2 181 add $128*8*1, block_0 182 183 xor crc1,crc1 184 xor crc2,crc2 185 186 # Fall thruogh into top of crc array (crc_128) 187 188 ################################################################ 189 ## 3) CRC Array: 190 ################################################################ 191 192crc_array: 193 i=128 194.rept 128-1 195.altmacro 196LABEL crc_ %i 197.noaltmacro 198 crc32q -i*8(block_0), crc_init 199 crc32q -i*8(block_1), crc1 200 crc32q -i*8(block_2), crc2 201 i=(i-1) 202.endr 203 204.altmacro 205LABEL crc_ %i 206.noaltmacro 207 crc32q -i*8(block_0), crc_init 208 crc32q -i*8(block_1), crc1 209# SKIP crc32 -i*8(block_2), crc2 ; Don't do this one yet 210 211 mov block_2, block_0 212 213 ################################################################ 214 ## 4) Combine three results: 215 ################################################################ 216 217 lea (K_table-16)(%rip), bufp # first entry is for idx 1 218 shlq $3, %rax # rax *= 8 219 subq %rax, tmp # tmp -= rax*8 220 shlq $1, %rax 221 subq %rax, tmp # tmp -= rax*16 222 # (total tmp -= rax*24) 223 addq %rax, bufp 224 225 movdqa (bufp), %xmm0 # 2 consts: K1:K2 226 227 movq crc_init, %xmm1 # CRC for block 1 228 pclmulqdq $0x00,%xmm0,%xmm1 # Multiply by K2 229 230 movq crc1, %xmm2 # CRC for block 2 231 pclmulqdq $0x10, %xmm0, %xmm2 # Multiply by K1 232 233 pxor %xmm2,%xmm1 234 movq %xmm1, %rax 235 xor -i*8(block_2), %rax 236 mov crc2, crc_init 237 crc32 %rax, crc_init 238 239################################################################ 240## 5) Check for end: 241################################################################ 242 243LABEL crc_ 0 244 mov tmp, len 245 cmp $128*24, tmp 246 jae full_block 247 cmp $24, tmp 248 jae continue_block 249 250less_than_24: 251 shl $32-4, len_dw # less_than_16 expects length 252 # in upper 4 bits of len_dw 253 jnc less_than_16 254 crc32q (bufptmp), crc_init 255 crc32q 8(bufptmp), crc_init 256 jz do_return 257 add $16, bufptmp 258 # len is less than 8 if we got here 259 # less_than_8 expects length in upper 3 bits of len_dw 260 # less_than_8_post_shl1 expects length = carryflag * 8 + len_dw[31:30] 261 shl $2, len_dw 262 jmp less_than_8_post_shl1 263 264 ####################################################################### 265 ## 6) LESS THAN 256-bytes REMAIN AT THIS POINT (8-bits of len are full) 266 ####################################################################### 267small: 268 shl $32-8, len_dw # Prepare len_dw for less_than_256 269 j=256 270.rept 5 # j = {256, 128, 64, 32, 16} 271.altmacro 272LABEL less_than_ %j # less_than_j: Length should be in 273 # upper lg(j) bits of len_dw 274 j=(j/2) 275 shl $1, len_dw # Get next MSB 276 JNC_LESS_THAN %j 277.noaltmacro 278 i=0 279.rept (j/8) 280 crc32q i(bufptmp), crc_init # Compute crc32 of 8-byte data 281 i=i+8 282.endr 283 jz do_return # Return if remaining length is zero 284 add $j, bufptmp # Advance buf 285.endr 286 287less_than_8: # Length should be stored in 288 # upper 3 bits of len_dw 289 shl $1, len_dw 290less_than_8_post_shl1: 291 jnc less_than_4 292 crc32l (bufptmp), crc_init_dw # CRC of 4 bytes 293 jz do_return # return if remaining data is zero 294 add $4, bufptmp 295less_than_4: # Length should be stored in 296 # upper 2 bits of len_dw 297 shl $1, len_dw 298 jnc less_than_2 299 crc32w (bufptmp), crc_init_dw # CRC of 2 bytes 300 jz do_return # return if remaining data is zero 301 add $2, bufptmp 302less_than_2: # Length should be stored in the MSB 303 # of len_dw 304 shl $1, len_dw 305 jnc less_than_1 306 crc32b (bufptmp), crc_init_dw # CRC of 1 byte 307less_than_1: # Length should be zero 308do_return: 309 movq crc_init, %rax 310 popq %rsi 311 popq %rdi 312 popq %rbx 313 ret 314 315 ################################################################ 316 ## jump table Table is 129 entries x 2 bytes each 317 ################################################################ 318.align 4 319jump_table: 320 i=0 321.rept 129 322.altmacro 323JMPTBL_ENTRY %i 324.noaltmacro 325 i=i+1 326.endr 327 328ENDPROC(crc_pcl) 329 330 ################################################################ 331 ## PCLMULQDQ tables 332 ## Table is 128 entries x 2 quad words each 333 ################################################################ 334.data 335.align 64 336K_table: 337 .quad 0x14cd00bd6,0x105ec76f0 338 .quad 0x0ba4fc28e,0x14cd00bd6 339 .quad 0x1d82c63da,0x0f20c0dfe 340 .quad 0x09e4addf8,0x0ba4fc28e 341 .quad 0x039d3b296,0x1384aa63a 342 .quad 0x102f9b8a2,0x1d82c63da 343 .quad 0x14237f5e6,0x01c291d04 344 .quad 0x00d3b6092,0x09e4addf8 345 .quad 0x0c96cfdc0,0x0740eef02 346 .quad 0x18266e456,0x039d3b296 347 .quad 0x0daece73e,0x0083a6eec 348 .quad 0x0ab7aff2a,0x102f9b8a2 349 .quad 0x1248ea574,0x1c1733996 350 .quad 0x083348832,0x14237f5e6 351 .quad 0x12c743124,0x02ad91c30 352 .quad 0x0b9e02b86,0x00d3b6092 353 .quad 0x018b33a4e,0x06992cea2 354 .quad 0x1b331e26a,0x0c96cfdc0 355 .quad 0x17d35ba46,0x07e908048 356 .quad 0x1bf2e8b8a,0x18266e456 357 .quad 0x1a3e0968a,0x11ed1f9d8 358 .quad 0x0ce7f39f4,0x0daece73e 359 .quad 0x061d82e56,0x0f1d0f55e 360 .quad 0x0d270f1a2,0x0ab7aff2a 361 .quad 0x1c3f5f66c,0x0a87ab8a8 362 .quad 0x12ed0daac,0x1248ea574 363 .quad 0x065863b64,0x08462d800 364 .quad 0x11eef4f8e,0x083348832 365 .quad 0x1ee54f54c,0x071d111a8 366 .quad 0x0b3e32c28,0x12c743124 367 .quad 0x0064f7f26,0x0ffd852c6 368 .quad 0x0dd7e3b0c,0x0b9e02b86 369 .quad 0x0f285651c,0x0dcb17aa4 370 .quad 0x010746f3c,0x018b33a4e 371 .quad 0x1c24afea4,0x0f37c5aee 372 .quad 0x0271d9844,0x1b331e26a 373 .quad 0x08e766a0c,0x06051d5a2 374 .quad 0x093a5f730,0x17d35ba46 375 .quad 0x06cb08e5c,0x11d5ca20e 376 .quad 0x06b749fb2,0x1bf2e8b8a 377 .quad 0x1167f94f2,0x021f3d99c 378 .quad 0x0cec3662e,0x1a3e0968a 379 .quad 0x19329634a,0x08f158014 380 .quad 0x0e6fc4e6a,0x0ce7f39f4 381 .quad 0x08227bb8a,0x1a5e82106 382 .quad 0x0b0cd4768,0x061d82e56 383 .quad 0x13c2b89c4,0x188815ab2 384 .quad 0x0d7a4825c,0x0d270f1a2 385 .quad 0x10f5ff2ba,0x105405f3e 386 .quad 0x00167d312,0x1c3f5f66c 387 .quad 0x0f6076544,0x0e9adf796 388 .quad 0x026f6a60a,0x12ed0daac 389 .quad 0x1a2adb74e,0x096638b34 390 .quad 0x19d34af3a,0x065863b64 391 .quad 0x049c3cc9c,0x1e50585a0 392 .quad 0x068bce87a,0x11eef4f8e 393 .quad 0x1524fa6c6,0x19f1c69dc 394 .quad 0x16cba8aca,0x1ee54f54c 395 .quad 0x042d98888,0x12913343e 396 .quad 0x1329d9f7e,0x0b3e32c28 397 .quad 0x1b1c69528,0x088f25a3a 398 .quad 0x02178513a,0x0064f7f26 399 .quad 0x0e0ac139e,0x04e36f0b0 400 .quad 0x0170076fa,0x0dd7e3b0c 401 .quad 0x141a1a2e2,0x0bd6f81f8 402 .quad 0x16ad828b4,0x0f285651c 403 .quad 0x041d17b64,0x19425cbba 404 .quad 0x1fae1cc66,0x010746f3c 405 .quad 0x1a75b4b00,0x18db37e8a 406 .quad 0x0f872e54c,0x1c24afea4 407 .quad 0x01e41e9fc,0x04c144932 408 .quad 0x086d8e4d2,0x0271d9844 409 .quad 0x160f7af7a,0x052148f02 410 .quad 0x05bb8f1bc,0x08e766a0c 411 .quad 0x0a90fd27a,0x0a3c6f37a 412 .quad 0x0b3af077a,0x093a5f730 413 .quad 0x04984d782,0x1d22c238e 414 .quad 0x0ca6ef3ac,0x06cb08e5c 415 .quad 0x0234e0b26,0x063ded06a 416 .quad 0x1d88abd4a,0x06b749fb2 417 .quad 0x04597456a,0x04d56973c 418 .quad 0x0e9e28eb4,0x1167f94f2 419 .quad 0x07b3ff57a,0x19385bf2e 420 .quad 0x0c9c8b782,0x0cec3662e 421 .quad 0x13a9cba9e,0x0e417f38a 422 .quad 0x093e106a4,0x19329634a 423 .quad 0x167001a9c,0x14e727980 424 .quad 0x1ddffc5d4,0x0e6fc4e6a 425 .quad 0x00df04680,0x0d104b8fc 426 .quad 0x02342001e,0x08227bb8a 427 .quad 0x00a2a8d7e,0x05b397730 428 .quad 0x168763fa6,0x0b0cd4768 429 .quad 0x1ed5a407a,0x0e78eb416 430 .quad 0x0d2c3ed1a,0x13c2b89c4 431 .quad 0x0995a5724,0x1641378f0 432 .quad 0x19b1afbc4,0x0d7a4825c 433 .quad 0x109ffedc0,0x08d96551c 434 .quad 0x0f2271e60,0x10f5ff2ba 435 .quad 0x00b0bf8ca,0x00bf80dd2 436 .quad 0x123888b7a,0x00167d312 437 .quad 0x1e888f7dc,0x18dcddd1c 438 .quad 0x002ee03b2,0x0f6076544 439 .quad 0x183e8d8fe,0x06a45d2b2 440 .quad 0x133d7a042,0x026f6a60a 441 .quad 0x116b0f50c,0x1dd3e10e8 442 .quad 0x05fabe670,0x1a2adb74e 443 .quad 0x130004488,0x0de87806c 444 .quad 0x000bcf5f6,0x19d34af3a 445 .quad 0x18f0c7078,0x014338754 446 .quad 0x017f27698,0x049c3cc9c 447 .quad 0x058ca5f00,0x15e3e77ee 448 .quad 0x1af900c24,0x068bce87a 449 .quad 0x0b5cfca28,0x0dd07448e 450 .quad 0x0ded288f8,0x1524fa6c6 451 .quad 0x059f229bc,0x1d8048348 452 .quad 0x06d390dec,0x16cba8aca 453 .quad 0x037170390,0x0a3e3e02c 454 .quad 0x06353c1cc,0x042d98888 455 .quad 0x0c4584f5c,0x0d73c7bea 456 .quad 0x1f16a3418,0x1329d9f7e 457 .quad 0x0531377e2,0x185137662 458 .quad 0x1d8d9ca7c,0x1b1c69528 459 .quad 0x0b25b29f2,0x18a08b5bc 460 .quad 0x19fb2a8b0,0x02178513a 461 .quad 0x1a08fe6ac,0x1da758ae0 462 .quad 0x045cddf4e,0x0e0ac139e 463 .quad 0x1a91647f2,0x169cf9eb0 464 .quad 0x1a0f717c4,0x0170076fa 465