1// Copyright 2021 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// This is an implementation based on the s390x 6// implementation. 7 8// Find a separator with 2 <= len <= 32 within a string. 9// Separators with lengths of 2, 3 or 4 are handled 10// specially. 11 12// This works on power8 and above. The loads and 13// compares are done in big endian order 14// since that allows the used of VCLZD, and allows 15// the same implementation to work on big and little 16// endian platforms with minimal conditional changes. 17 18// NOTE: There is a power9 implementation that 19// improves performance by 10-15% on little 20// endian for some of the benchmarks. 21// Unrolled index2to16 loop by 4 on ppc64le/power9 22// Work is still needed for a big endian 23// implementation on power9. 24 25//go:build ppc64 || ppc64le 26 27#include "go_asm.h" 28#include "textflag.h" 29 30// Needed to swap LXVD2X loads to the correct 31// byte order to work on POWER8. 32 33#ifdef GOARCH_ppc64 34DATA byteswap<>+0(SB)/8, $0x0001020304050607 35DATA byteswap<>+8(SB)/8, $0x08090a0b0c0d0e0f 36#else 37DATA byteswap<>+0(SB)/8, $0x0706050403020100 38DATA byteswap<>+8(SB)/8, $0x0f0e0d0c0b0a0908 39#endif 40 41// Load bytes in big endian order. Address 42// alignment does not need checking. 43#define VLOADSWAP(base, index, vreg, vsreg) \ 44 LXVD2X (base)(index), vsreg; \ 45 VPERM vreg, vreg, SWAP, vreg 46 47GLOBL byteswap<>+0(SB), RODATA, $16 48 49TEXT ·Index<ABIInternal>(SB),NOSPLIT|NOFRAME,$0-56 50 // R3 = byte array pointer 51 // R4 = length 52 MOVD R6, R5 // R5 = separator pointer 53 MOVD R7, R6 // R6 = separator length 54 55#ifdef GOARCH_ppc64le 56 MOVBZ internal∕cpu·PPC64+const_offsetPPC64HasPOWER9(SB), R7 57 CMP R7, $1 58 BNE power8 59 BR indexbodyp9<>(SB) 60#endif 61power8: 62 BR indexbody<>(SB) 63 64TEXT ·IndexString<ABIInternal>(SB),NOSPLIT|NOFRAME,$0-40 65 // R3 = string 66 // R4 = length 67 // R5 = separator pointer 68 // R6 = separator length 69 70#ifdef GOARCH_ppc64le 71 MOVBZ internal∕cpu·PPC64+const_offsetPPC64HasPOWER9(SB), R7 72 CMP R7, $1 73 BNE power8 74 BR indexbodyp9<>(SB) 75 76#endif 77power8: 78 BR indexbody<>(SB) 79 80 // s: string we are searching 81 // sep: string to search for 82 // R3=&s[0], R4=len(s) 83 // R5=&sep[0], R6=len(sep) 84 // R14=&ret (index where sep found) 85 // R7=working addr of string 86 // R16=index value 16 87 // R17=index value 17 88 // R18=index value 18 89 // R19=index value 1 90 // R26=LASTBYTE of string 91 // R27=LASTSTR last start byte to compare with sep 92 // R8, R9 scratch 93 // V0=sep left justified zero fill 94 // CR4=sep length >= 16 95 96#define SEPMASK V17 97#define LASTBYTE R26 98#define LASTSTR R27 99#define ONES V20 100#define SWAP V21 101#define SWAP_ VS53 102TEXT indexbody<>(SB), NOSPLIT|NOFRAME, $0 103 CMP R6, R4 // Compare lengths 104 BGT notfound // If sep len is > string, notfound 105 ADD R4, R3, LASTBYTE // find last byte addr 106 SUB R6, LASTBYTE, LASTSTR // LAST=&s[len(s)-len(sep)] (last valid start index) 107 CMP R6, $0 // Check sep len 108 BEQ notfound // sep len 0 -- not found 109 MOVD R3, R7 // Copy of string addr 110 MOVD $16, R16 // Index value 16 111 MOVD $17, R17 // Index value 17 112 MOVD $18, R18 // Index value 18 113 MOVD $1, R19 // Index value 1 114 MOVD $byteswap<>+00(SB), R8 115 VSPLTISB $0xFF, ONES // splat all 1s 116 LXVD2X (R8)(R0), SWAP_ // Set up swap string 117 118 CMP R6, $16, CR4 // CR4 for len(sep) >= 16 119 VOR ONES, ONES, SEPMASK // Set up full SEPMASK 120 BGE CR4, loadge16 // Load for len(sep) >= 16 121 SUB R6, R16, R9 // 16-len of sep 122 SLD $3, R9 // Set up for VSLO 123 MTVSRD R9, V9 // Set up for VSLO 124 VSLDOI $8, V9, V9, V9 // Set up for VSLO 125 VSLO ONES, V9, SEPMASK // Mask for separator len(sep) < 16 126 127loadge16: 128 ANDCC $15, R5, R9 // Find byte offset of sep 129 ADD R9, R6, R10 // Add sep len 130 CMP R10, $16 // Check if sep len+offset > 16 131 BGT sepcross16 // Sep crosses 16 byte boundary 132 133 RLDICR $0, R5, $59, R8 // Adjust addr to 16 byte container 134 VLOADSWAP(R8, R0, V0, V0) // Load 16 bytes @R8 into V0 135 SLD $3, R9 // Set up shift count for VSLO 136 MTVSRD R9, V8 // Set up shift count for VSLO 137 VSLDOI $8, V8, V8, V8 138 VSLO V0, V8, V0 // Shift by start byte 139 140 VAND V0, SEPMASK, V0 // Mask separator (< 16) 141 BR index2plus 142 143sepcross16: 144 VLOADSWAP(R5, R0, V0, V0) // Load 16 bytes @R5 into V0 145 146 VAND V0, SEPMASK, V0 // mask out separator 147 BLE CR4, index2to16 148 BR index17plus // Handle sep > 16 149 150index2plus: 151 CMP R6, $2 // Check length of sep 152 BNE index3plus // If not 2, check for 3 153 ADD $16, R7, R9 // Check if next 16 bytes past last 154 CMP R9, LASTBYTE // compare with last 155 BGE index2to16 // 2 <= len(string) <= 16 156 MOVD $0xff00, R21 // Mask for later 157 MTVSRD R21, V25 // Move to Vreg 158 VSPLTH $3, V25, V31 // Splat mask 159 VSPLTH $0, V0, V1 // Splat 1st 2 bytes of sep 160 VSPLTISB $0, V10 // Clear V10 161 162 // First case: 2 byte separator 163 // V1: 2 byte separator splatted 164 // V2: 16 bytes at addr 165 // V4: 16 bytes at addr+1 166 // Compare 2 byte separator at start 167 // and at start+1. Use VSEL to combine 168 // those results to find the first 169 // matching start byte, returning 170 // that value when found. Loop as 171 // long as len(string) > 16 172index2loop2: 173 VLOADSWAP(R7, R19, V3, V3) // Load 16 bytes @R7+1 into V3 174 175index2loop: 176 VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2 177 VCMPEQUH V1, V2, V5 // Search for sep 178 VCMPEQUH V1, V3, V6 // Search for sep offset by 1 179 VSEL V6, V5, V31, V7 // merge even and odd indices 180 VCLZD V7, V18 // find index of first match 181 MFVSRD V18, R25 // get first value 182 CMP R25, $64 // Found if < 64 183 BLT foundR25 // Return byte index where found 184 VSLDOI $8, V18, V18, V18 // Adjust 2nd value 185 MFVSRD V18, R25 // get second value 186 CMP R25, $64 // Found if < 64 187 ADD $64, R25 // Update byte offset 188 BLT foundR25 // Return value 189 ADD $16, R7 // R7+=16 Update string pointer 190 ADD $17, R7, R9 // R9=F7+17 since loop unrolled 191 CMP R9, LASTBYTE // Compare addr+17 against last byte 192 BLT index2loop2 // If < last, continue loop 193 CMP R7, LASTBYTE // Compare addr+16 against last byte 194 BLT index2to16 // If < 16 handle specially 195 VLOADSWAP(R7, R0, V3, V3) // Load 16 bytes @R7 into V3 196 VSLDOI $1, V3, V10, V3 // Shift left by 1 byte 197 BR index2loop 198 199index3plus: 200 CMP R6, $3 // Check if sep == 3 201 BNE index4plus // If not check larger 202 ADD $19, R7, R9 // Find bytes for use in this loop 203 CMP R9, LASTBYTE // Compare against last byte 204 BGE index2to16 // Remaining string 2<=len<=16 205 MOVD $0xff00, R21 // Set up mask for upcoming loop 206 MTVSRD R21, V25 // Move mask to Vreg 207 VSPLTH $3, V25, V31 // Splat mask 208 VSPLTH $0, V0, V1 // Splat 1st two bytes of sep 209 VSPLTB $2, V0, V8 // Splat 3rd byte of sep 210 211 // Loop to process 3 byte separator. 212 // string[0:16] is in V2 213 // string[2:18] is in V3 214 // sep[0:2] splatted in V1 215 // sec[3] splatted in v8 216 // Load vectors at string, string+1 217 // and string+2. Compare string, string+1 218 // against first 2 bytes of separator 219 // splatted, and string+2 against 3rd 220 // byte splatted. Merge the results with 221 // VSEL to find the first byte of a match. 222 223 // Special handling for last 16 bytes if the 224 // string fits in 16 byte multiple. 225index3loop2: 226 MOVD $2, R21 // Set up index for 2 227 VSPLTISB $0, V10 // Clear V10 228 VLOADSWAP(R7, R21, V3, V3)// Load 16 bytes @R7+2 into V3 229 VSLDOI $14, V3, V10, V3 // Left justify next 2 bytes 230 231index3loop: 232 VLOADSWAP(R7, R0, V2, V2) // Load with correct order 233 VSLDOI $1, V2, V3, V4 // string[1:17] 234 VSLDOI $2, V2, V3, V9 // string[2:18] 235 VCMPEQUH V1, V2, V5 // compare hw even indices 236 VCMPEQUH V1, V4, V6 // compare hw odd indices 237 VCMPEQUB V8, V9, V10 // compare 3rd to last byte 238 VSEL V6, V5, V31, V7 // Find 1st matching byte using mask 239 VAND V7, V10, V7 // AND matched bytes with matched 3rd byte 240 VCLZD V7, V18 // Find first nonzero indexes 241 MFVSRD V18, R25 // Move 1st doubleword 242 CMP R25, $64 // If < 64 found 243 BLT foundR25 // Return matching index 244 VSLDOI $8, V18, V18, V18 // Move value 245 MFVSRD V18, R25 // Move 2nd doubleword 246 CMP R25, $64 // If < 64 found 247 ADD $64, R25 // Update byte index 248 BLT foundR25 // Return matching index 249 ADD $16, R7 // R7+=16 string ptr 250 ADD $19, R7, R9 // Number of string bytes for loop 251 CMP R9, LASTBYTE // Compare against last byte of string 252 BLT index3loop2 // If within, continue this loop 253 CMP R7, LASTSTR // Compare against last start byte 254 BLT index2to16 // Process remainder 255 VSPLTISB $0, V3 // Special case for last 16 bytes 256 BR index3loop // Continue this loop 257 258 // Loop to process 4 byte separator 259 // string[0:16] in V2 260 // string[3:16] in V3 261 // sep[0:4] splatted in V1 262 // Set up vectors with strings at offsets 263 // 0, 1, 2, 3 and compare against the 4 byte 264 // separator also splatted. Use VSEL with the 265 // compare results to find the first byte where 266 // a separator match is found. 267index4plus: 268 CMP R6, $4 // Check if 4 byte separator 269 BNE index5plus // If not next higher 270 ADD $20, R7, R9 // Check string size to load 271 CMP R9, LASTBYTE // Verify string length 272 BGE index2to16 // If not large enough, process remaining 273 MOVD $2, R15 // Set up index 274 275 // Set up masks for use with VSEL 276 MOVD $0xff, R21 // Set up mask 0xff000000ff000000... 277 SLD $24, R21 278 MTVSRD R21, V10 279 VSPLTW $1, V10, V29 280 VSLDOI $2, V29, V29, V30 // Mask 0x0000ff000000ff00... 281 MOVD $0xffff, R21 282 SLD $16, R21 283 MTVSRD R21, V10 284 VSPLTW $1, V10, V31 // Mask 0xffff0000ffff0000... 285 VSPLTW $0, V0, V1 // Splat 1st word of separator 286 287index4loop: 288 VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2 289 290next4: 291 VSPLTISB $0, V10 // Clear 292 MOVD $3, R9 // Number of bytes beyond 16 293 VLOADSWAP(R7, R9, V3, V3) // Load 16 bytes @R7+3 into V3 294 VSLDOI $13, V3, V10, V3 // Shift left last 3 bytes 295 VSLDOI $1, V2, V3, V4 // V4=(V2:V3)<<1 296 VSLDOI $2, V2, V3, V9 // V9=(V2:V3)<<2 297 VSLDOI $3, V2, V3, V10 // V10=(V2:v3)<<3 298 VCMPEQUW V1, V2, V5 // compare index 0, 4, ... with sep 299 VCMPEQUW V1, V4, V6 // compare index 1, 5, ... with sep 300 VCMPEQUW V1, V9, V11 // compare index 2, 6, ... with sep 301 VCMPEQUW V1, V10, V12 // compare index 3, 7, ... with sep 302 VSEL V6, V5, V29, V13 // merge index 0, 1, 4, 5, using mask 303 VSEL V12, V11, V30, V14 // merge index 2, 3, 6, 7, using mask 304 VSEL V14, V13, V31, V7 // final merge 305 VCLZD V7, V18 // Find first index for each half 306 MFVSRD V18, R25 // Isolate value 307 CMP R25, $64 // If < 64, found 308 BLT foundR25 // Return found index 309 VSLDOI $8, V18, V18, V18 // Move for MFVSRD 310 MFVSRD V18, R25 // Isolate other value 311 CMP R25, $64 // If < 64, found 312 ADD $64, R25 // Update index for high doubleword 313 BLT foundR25 // Return found index 314 ADD $16, R7 // R7+=16 for next string 315 ADD $20, R7, R9 // R+20 for all bytes to load 316 CMP R9, LASTBYTE // Past end? Maybe check for extra? 317 BLT index4loop // If not, continue loop 318 CMP R7, LASTSTR // Check remainder 319 BLE index2to16 // Process remainder 320 BR notfound // Not found 321 322index5plus: 323 CMP R6, $16 // Check for sep > 16 324 BGT index17plus // Handle large sep 325 326 // Assumption is that the separator is smaller than the string at this point 327index2to16: 328 CMP R7, LASTSTR // Compare last start byte 329 BGT notfound // last takes len(sep) into account 330 331 ADD $16, R7, R9 // Check for last byte of string 332 CMP R9, LASTBYTE 333 BGT index2to16tail 334 335 // At least 16 bytes of string left 336 // Mask the number of bytes in sep 337index2to16loop: 338 VLOADSWAP(R7, R0, V1, V1) // Load 16 bytes @R7 into V1 339 340compare: 341 VAND V1, SEPMASK, V2 // Mask out sep size 342 VCMPEQUBCC V0, V2, V3 // Compare masked string 343 BLT CR6, found // All equal 344 ADD $1, R7 // Update ptr to next byte 345 CMP R7, LASTSTR // Still less than last start byte 346 BGT notfound // Not found 347 ADD $16, R7, R9 // Verify remaining bytes 348 CMP R9, LASTBYTE // At least 16 349 BLT index2to16loop // Try again 350 351 // Less than 16 bytes remaining in string 352 // Separator >= 2 353index2to16tail: 354 ADD R3, R4, R9 // End of string 355 SUB R7, R9, R9 // Number of bytes left 356 ANDCC $15, R7, R10 // 16 byte offset 357 ADD R10, R9, R11 // offset + len 358 CMP R11, $16 // >= 16? 359 BLE short // Does not cross 16 bytes 360 VLOADSWAP(R7, R0, V1, V1) // Load 16 bytes @R7 into V1 361 BR index2to16next // Continue on 362 363short: 364 RLDICR $0, R7, $59, R9 // Adjust addr to 16 byte container 365 VLOADSWAP(R9, R0, V1, V1)// Load 16 bytes @R9 into V1 366 SLD $3, R10 // Set up shift 367 MTVSRD R10, V8 // Set up shift 368 VSLDOI $8, V8, V8, V8 369 VSLO V1, V8, V1 // Shift by start byte 370 VSPLTISB $0, V25 // Clear for later use 371 372index2to16next: 373 VAND V1, SEPMASK, V2 // Just compare size of sep 374 VCMPEQUBCC V0, V2, V3 // Compare sep and partial string 375 BLT CR6, found // Found 376 ADD $1, R7 // Not found, try next partial string 377 CMP R7, LASTSTR // Check for end of string 378 BGT notfound // If at end, then not found 379 VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte 380 BR index2to16next // Check the next partial string 381 382index17plus: 383 CMP R6, $32 // Check if 17 < len(sep) <= 32 384 BGT index33plus 385 SUB $16, R6, R9 // Extra > 16 386 SLD $56, R9, R10 // Shift to use in VSLO 387 MTVSRD R10, V9 // Set up for VSLO 388 VLOADSWAP(R5, R9, V1, V1)// Load 16 bytes @R5+R9 into V1 389 VSLO V1, V9, V1 // Shift left 390 VSPLTISB $0xff, V7 // Splat 1s 391 VSPLTISB $0, V27 // Splat 0 392 393index17to32loop: 394 VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2 395 396next17: 397 VLOADSWAP(R7, R9, V3, V3) // Load 16 bytes @R7+R9 into V3 398 VSLO V3, V9, V3 // Shift left 399 VCMPEQUB V0, V2, V4 // Compare first 16 bytes 400 VCMPEQUB V1, V3, V5 // Compare extra over 16 bytes 401 VAND V4, V5, V6 // Check if both equal 402 VCMPEQUBCC V6, V7, V8 // All equal? 403 BLT CR6, found // Yes 404 ADD $1, R7 // On to next byte 405 CMP R7, LASTSTR // Check if last start byte 406 BGT notfound // If too high, not found 407 BR index17to32loop // Continue 408 409notfound: 410 MOVD $-1, R3 // Return -1 if not found 411 RET 412 413index33plus: 414 MOVD $0, (R0) // Case not implemented 415 RET // Crash before return 416 417foundR25: 418 SRD $3, R25 // Convert from bits to bytes 419 ADD R25, R7 // Add to current string address 420 SUB R3, R7 // Subtract from start of string 421 MOVD R7, R3 // Return byte where found 422 RET 423 424found: 425 SUB R3, R7 // Return byte where found 426 MOVD R7, R3 427 RET 428 429TEXT indexbodyp9<>(SB), NOSPLIT|NOFRAME, $0 430 CMP R6, R4 // Compare lengths 431 BGT notfound // If sep len is > string, notfound 432 ADD R4, R3, LASTBYTE // find last byte addr 433 SUB R6, LASTBYTE, LASTSTR // LAST=&s[len(s)-len(sep)] (last valid start index) 434 CMP R6, $0 // Check sep len 435 BEQ notfound // sep len 0 -- not found 436 MOVD R3, R7 // Copy of string addr 437#ifndef GOPPC64_power10 438 MOVD $16, R16 // Index value 16 439 MOVD $17, R17 // Index value 17 440 MOVD $18, R18 // Index value 18 441 VSPLTISB $0xFF, ONES // splat all 1s 442 VOR ONES, ONES, SEPMASK // Set up full SEPMASK 443#else 444 SLD $56, R6, R14 // Set up separator length for LXVLL 445#endif 446 MOVD $1, R19 // Index value 1 447 CMP R6, $16, CR4 // CR4 for len(sep) >= 16 448 BGE CR4, loadge16 // Load for len(sep) >= 16 449#ifndef GOPPC64_power10 450 SUB R6, R16, R9 // 16-len of sep 451 SLD $3, R9 // Set up for VSLO 452 MTVSRD R9, V9 // Set up for VSLO 453 VSLDOI $8, V9, V9, V9 // Set up for VSLO 454 VSLO ONES, V9, SEPMASK // Mask for separator len(sep) < 16 455#endif 456loadge16: 457 ANDCC $15, R5, R9 // Find byte offset of sep 458 ADD R9, R6, R10 // Add sep len 459 CMP R10, $16 // Check if sep len+offset > 16 460 BGT sepcross16 // Sep crosses 16 byte boundary 461#ifdef GOPPC64_power10 462 LXVLL R5, R14, V0 // Load separator 463#else 464 RLDICR $0, R5, $59, R8 // Adjust addr to 16 byte container 465 LXVB16X (R8)(R0), V0 // Load 16 bytes @R8 into V0 466 SLD $3, R9 // Set up shift count for VSLO 467 MTVSRD R9, V8 // Set up shift count for VSLO 468 VSLDOI $8, V8, V8, V8 469 VSLO V0, V8, V0 // Shift by start byte 470 VAND V0, SEPMASK, V0 // Mask separator (< 16) 471#endif 472 BR index2plus 473sepcross16: 474#ifdef GOPPC64_power10 475 LXVLL R5, R14, V0 // Load separator 476#else 477 LXVB16X (R5)(R0), V0 // Load 16 bytes @R5 into V0\ 478 VAND V0, SEPMASK, V0 // mask out separator 479#endif 480 BLE CR4, index2to16 481 BR index17plus // Handle sep > 16 482 483index2plus: 484 CMP R6, $2 // Check length of sep 485 BNE index3plus // If not 2, check for 3 486 ADD $16, R7, R9 // Check if next 16 bytes past last 487 CMP R9, LASTBYTE // compare with last 488 BGE index2to16 // 2 <= len(string) <= 16 489 MOVD $0xff00, R21 // Mask for later 490 MTVSRD R21, V25 // Move to Vreg 491 VSPLTH $3, V25, V31 // Splat mask 492 VSPLTH $0, V0, V1 // Splat 1st 2 bytes of sep 493 VSPLTISB $0, V10 // Clear V10 494 495 // First case: 2 byte separator 496 // V1: 2 byte separator splatted 497 // V2: 16 bytes at addr 498 // V4: 16 bytes at addr+1 499 // Compare 2 byte separator at start 500 // and at start+1. Use VSEL to combine 501 // those results to find the first 502 // matching start byte, returning 503 // that value when found. Loop as 504 // long as len(string) > 16 505index2loop2: 506 LXVB16X (R7)(R19), V3 // Load 16 bytes @R7+1 into V3 507 508index2loop: 509 LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2 510 VCMPEQUH V1, V2, V5 // Search for sep 511 VCMPEQUH V1, V3, V6 // Search for sep offset by 1 512 VSEL V6, V5, V31, V7 // merge even and odd indices 513 VCLZD V7, V18 // find index of first match 514 MFVSRD V18, R25 // get first value 515 CMP R25, $64 // Found if < 64 516 BLT foundR25 // Return byte index where found 517 518 MFVSRLD V18, R25 // get second value 519 CMP R25, $64 // Found if < 64 520 ADD $64, R25 // Update byte offset 521 BLT foundR25 // Return value 522 ADD $16, R7 // R7+=16 Update string pointer 523 ADD $17, R7, R9 // R9=F7+17 since loop unrolled 524 CMP R9, LASTBYTE // Compare addr+17 against last byte 525 BLT index2loop2 // If < last, continue loop 526 CMP R7, LASTBYTE // Compare addr+16 against last byte 527 BLT index2to16 // If < 16 handle specially 528 LXVB16X (R7)(R0), V3 // Load 16 bytes @R7 into V3 529 VSLDOI $1, V3, V10, V3 // Shift left by 1 byte 530 BR index2loop 531 532index3plus: 533 CMP R6, $3 // Check if sep == 3 534 BNE index4plus // If not check larger 535 ADD $19, R7, R9 // Find bytes for use in this loop 536 CMP R9, LASTBYTE // Compare against last byte 537 BGE index2to16 // Remaining string 2<=len<=16 538 MOVD $0xff00, R21 // Set up mask for upcoming loop 539 MTVSRD R21, V25 // Move mask to Vreg 540 VSPLTH $3, V25, V31 // Splat mask 541 VSPLTH $0, V0, V1 // Splat 1st two bytes of sep 542 VSPLTB $2, V0, V8 // Splat 3rd byte of sep 543 544 // Loop to process 3 byte separator. 545 // string[0:16] is in V2 546 // string[2:18] is in V3 547 // sep[0:2] splatted in V1 548 // sec[3] splatted in v8 549 // Load vectors at string, string+1 550 // and string+2. Compare string, string+1 551 // against first 2 bytes of separator 552 // splatted, and string+2 against 3rd 553 // byte splatted. Merge the results with 554 // VSEL to find the first byte of a match. 555 556 // Special handling for last 16 bytes if the 557 // string fits in 16 byte multiple. 558index3loop2: 559 MOVD $2, R21 // Set up index for 2 560 VSPLTISB $0, V10 // Clear V10 561 LXVB16X (R7)(R21), V3 // Load 16 bytes @R7+2 into V3 562 VSLDOI $14, V3, V10, V3 // Left justify next 2 bytes 563 564index3loop: 565 LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 566 VSLDOI $1, V2, V3, V4 // string[1:17] 567 VSLDOI $2, V2, V3, V9 // string[2:18] 568 VCMPEQUH V1, V2, V5 // compare hw even indices 569 VCMPEQUH V1, V4, V6 // compare hw odd indices 570 VCMPEQUB V8, V9, V10 // compare 3rd to last byte 571 VSEL V6, V5, V31, V7 // Find 1st matching byte using mask 572 VAND V7, V10, V7 // AND matched bytes with matched 3rd byte 573 VCLZD V7, V18 // Find first nonzero indexes 574 MFVSRD V18, R25 // Move 1st doubleword 575 CMP R25, $64 // If < 64 found 576 BLT foundR25 // Return matching index 577 578 MFVSRLD V18, R25 // Move 2nd doubleword 579 CMP R25, $64 // If < 64 found 580 ADD $64, R25 // Update byte index 581 BLT foundR25 // Return matching index 582 ADD $16, R7 // R7+=16 string ptr 583 ADD $19, R7, R9 // Number of string bytes for loop 584 CMP R9, LASTBYTE // Compare against last byte of string 585 BLT index3loop2 // If within, continue this loop 586 CMP R7, LASTSTR // Compare against last start byte 587 BLT index2to16 // Process remainder 588 VSPLTISB $0, V3 // Special case for last 16 bytes 589 BR index3loop // Continue this loop 590 591 // Loop to process 4 byte separator 592 // string[0:16] in V2 593 // string[3:16] in V3 594 // sep[0:4] splatted in V1 595 // Set up vectors with strings at offsets 596 // 0, 1, 2, 3 and compare against the 4 byte 597 // separator also splatted. Use VSEL with the 598 // compare results to find the first byte where 599 // a separator match is found. 600index4plus: 601 CMP R6, $4 // Check if 4 byte separator 602 BNE index5plus // If not next higher 603 ADD $20, R7, R9 // Check string size to load 604 CMP R9, LASTBYTE // Verify string length 605 BGE index2to16 // If not large enough, process remaining 606 607 // Set up masks for use with VSEL 608 MOVD $0xff, R21 // Set up mask 0xff000000ff000000... 609 SLD $24, R21 610 MTVSRWS R21, V29 611 612 VSLDOI $2, V29, V29, V30 // Mask 0x0000ff000000ff00... 613 MOVD $0xffff, R21 614 SLD $16, R21 615 MTVSRWS R21, V31 616 617 VSPLTW $0, V0, V1 // Splat 1st word of separator 618 619index4loop: 620 LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2 621 622next4: 623 VSPLTISB $0, V10 // Clear 624 MOVD $3, R9 // Number of bytes beyond 16 625 LXVB16X (R7)(R9), V3 // Load 16 bytes @R7 into V3 626 VSLDOI $13, V3, V10, V3 // Shift left last 3 bytes 627 VSLDOI $1, V2, V3, V4 // V4=(V2:V3)<<1 628 VSLDOI $2, V2, V3, V9 // V9=(V2:V3)<<2 629 VSLDOI $3, V2, V3, V10 // V10=(V2:v3)<<3 630 VCMPEQUW V1, V2, V5 // compare index 0, 4, ... with sep 631 VCMPEQUW V1, V4, V6 // compare index 1, 5, ... with sep 632 VCMPEQUW V1, V9, V11 // compare index 2, 6, ... with sep 633 VCMPEQUW V1, V10, V12 // compare index 3, 7, ... with sep 634 VSEL V6, V5, V29, V13 // merge index 0, 1, 4, 5, using mask 635 VSEL V12, V11, V30, V14 // merge index 2, 3, 6, 7, using mask 636 VSEL V14, V13, V31, V7 // final merge 637 VCLZD V7, V18 // Find first index for each half 638 MFVSRD V18, R25 // Isolate value 639 CMP R25, $64 // If < 64, found 640 BLT foundR25 // Return found index 641 642 MFVSRLD V18, R25 // Isolate other value 643 CMP R25, $64 // If < 64, found 644 ADD $64, R25 // Update index for high doubleword 645 BLT foundR25 // Return found index 646 ADD $16, R7 // R7+=16 for next string 647 ADD $20, R7, R9 // R+20 for all bytes to load 648 CMP R9, LASTBYTE // Past end? Maybe check for extra? 649 BLT index4loop // If not, continue loop 650 CMP R7, LASTSTR // Check remainder 651 BLE index2to16 // Process remainder 652 BR notfound // Not found 653 654index5plus: 655 CMP R6, $16 // Check for sep > 16 656 BGT index17plus // Handle large sep 657 658 // Assumption is that the separator is smaller than the string at this point 659index2to16: 660 CMP R7, LASTSTR // Compare last start byte 661 BGT notfound // last takes len(sep) into account 662 663 ADD $19, R7, R9 // To check 4 indices per iteration, need at least 16+3 bytes 664 CMP R9, LASTBYTE 665 // At least 16 bytes of string left 666 // Mask the number of bytes in sep 667 VSPLTISB $0, V10 // Clear 668 BGT index2to16tail 669 670#ifdef GOPPC64_power10 671 ADD $3,R7, R17 // Base+3 672 ADD $2,R7, R8 // Base+2 673 ADD $1,R7, R10 // Base+1 674#else 675 MOVD $3, R17 // Number of bytes beyond 16 676#endif 677 PCALIGN $16 678 679index2to16loop: 680 681#ifdef GOPPC64_power10 682 LXVLL R7, R14, V8 // Load next 16 bytes of string from Base 683 LXVLL R10, R14, V9 // Load next 16 bytes of string from Base+1 684 LXVLL R8, R14, V11 // Load next 16 bytes of string from Base+2 685 LXVLL R17,R14, V12 // Load next 16 bytes of string from Base+3 686#else 687 LXVB16X (R7)(R0), V1 // Load next 16 bytes of string into V1 from R7 688 LXVB16X (R7)(R17), V5 // Load next 16 bytes of string into V5 from R7+3 689 690 VSLDOI $13, V5, V10, V2 // Shift left last 3 bytes 691 VSLDOI $1, V1, V2, V3 // V3=(V1:V2)<<1 692 VSLDOI $2, V1, V2, V4 // V4=(V1:V2)<<2 693 VAND V1, SEPMASK, V8 // Mask out sep size 0th index 694 VAND V3, SEPMASK, V9 // Mask out sep size 1st index 695 VAND V4, SEPMASK, V11 // Mask out sep size 2nd index 696 VAND V5, SEPMASK, V12 // Mask out sep size 3rd index 697#endif 698 VCMPEQUBCC V0, V8, V8 // compare masked string 699 BLT CR6, found // All equal while comparing 0th index 700 VCMPEQUBCC V0, V9, V9 // compare masked string 701 BLT CR6, found2 // All equal while comparing 1st index 702 VCMPEQUBCC V0, V11, V11 // compare masked string 703 BLT CR6, found3 // All equal while comparing 2nd index 704 VCMPEQUBCC V0, V12, V12 // compare masked string 705 BLT CR6, found4 // All equal while comparing 3rd index 706 707 ADD $4, R7 // Update ptr to next 4 bytes 708#ifdef GOPPC64_power10 709 ADD $4, R17 // Update ptr to next 4 bytes 710 ADD $4, R8 // Update ptr to next 4 bytes 711 ADD $4, R10 // Update ptr to next 4 bytes 712#endif 713 CMP R7, LASTSTR // Still less than last start byte 714 BGT notfound // Not found 715 ADD $19, R7, R9 // Verify remaining bytes 716 CMP R9, LASTBYTE // length of string at least 19 717 BLE index2to16loop // Try again, else do post processing and jump to index2to16next 718 PCALIGN $32 719 // <19 bytes left, post process the remaining string 720index2to16tail: 721#ifdef GOPPC64_power10 722index2to16next_p10: 723 LXVLL R7,R14, V1 // Load 16 bytes @R7 into V1 724 VCMPEQUBCC V1, V0, V3 // Compare sep and partial string 725 BLT CR6, found // Found 726 ADD $1, R7 // Not found, try next partial string 727 CMP R7, LASTSTR // Check for end of string 728 BLE index2to16next_p10 // If at end, then not found 729 BR notfound // go to remainder loop 730#else 731 ADD R3, R4, R9 // End of string 732 SUB R7, R9, R9 // Number of bytes left 733 ANDCC $15, R7, R10 // 16 byte offset 734 ADD R10, R9, R11 // offset + len 735 CMP R11, $16 // >= 16? 736 BLE short // Does not cross 16 bytes 737 LXVB16X (R7)(R0), V1 // Load 16 bytes @R7 into V1 738 CMP R9, $16 // Post-processing of unrolled loop 739 BLE index2to16next // continue to index2to16next if <= 16 bytes 740 SUB R16, R9, R10 // R9 should be 18 or 17 hence R10 is 1 or 2 741 LXVB16X (R7)(R10), V9 742 CMP R10, $1 // string length is 17, compare 1 more byte 743 BNE extra2 // string length is 18, compare 2 more bytes 744 VSLDOI $15, V9, V10, V25 745 VAND V1, SEPMASK, V2 // Just compare size of sep 746 VCMPEQUBCC V0, V2, V3 // Compare sep and partial string 747 BLT CR6, found // Found 748 ADD $1, R7 // Not found, try next partial string 749 CMP R7, LASTSTR // Check for end of string 750 BGT notfound // If at end, then not found 751 VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte 752 BR index2to16next // go to remainder loop 753extra2: 754 VSLDOI $14, V9, V10, V25 755 VAND V1, SEPMASK, V2 // Just compare size of sep 756 VCMPEQUBCC V0, V2, V3 // Compare sep and partial string 757 BLT CR6, found // Found 758 ADD $1, R7 // Not found, try next partial string 759 CMP R7, LASTSTR // Check for end of string 760 BGT notfound // If at end, then not found 761 VOR V1, V1, V4 // save remaining string 762 VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte for 17th byte 763 VAND V1, SEPMASK, V2 // Just compare size of sep 764 VCMPEQUBCC V0, V2, V3 // Compare sep and partial string 765 BLT CR6, found // Found 766 ADD $1, R7 // Not found, try next partial string 767 CMP R7, LASTSTR // Check for end of string 768 BGT notfound // If at end, then not found 769 VSLDOI $2, V4, V25, V1 // Shift saved string left by 2 bytes for 18th byte 770 BR index2to16next // Check the remaining partial string in index2to16next 771 772short: 773 RLDICR $0, R7, $59, R9 // Adjust addr to 16 byte container 774 LXVB16X (R9)(R0), V1 // Load 16 bytes @R9 into V1 775 SLD $3, R10 // Set up shift 776 MTVSRD R10, V8 // Set up shift 777 VSLDOI $8, V8, V8, V8 778 VSLO V1, V8, V1 // Shift by start byte 779 PCALIGN $16 780index2to16next: 781 VAND V1, SEPMASK, V2 // Just compare size of sep 782 VCMPEQUBCC V0, V2, V3 // Compare sep and partial string 783 BLT CR6, found // Found 784 ADD $1, R7 // Not found, try next partial string 785 CMP R7, LASTSTR // Check for end of string 786 BGT notfound // If at end, then not found 787 VSLDOI $1, V1, V10, V1 // Shift string left by 1 byte 788 BR index2to16next // Check the next partial string 789#endif // Tail processing if GOPPC64!=power10 790 791index17plus: 792 CMP R6, $32 // Check if 17 < len(sep) <= 32 793 BGT index33plus 794 SUB $16, R6, R9 // Extra > 16 795 SLD $56, R9, R10 // Shift to use in VSLO 796 MTVSRD R10, V9 // Set up for VSLO 797 LXVB16X (R5)(R9), V1 // Load 16 bytes @R5+R9 into V1 798 VSLO V1, V9, V1 // Shift left 799 VSPLTISB $0xff, V7 // Splat 1s 800 VSPLTISB $0, V27 // Splat 0 801 802index17to32loop: 803 LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2 804 805next17: 806 LXVB16X (R7)(R9), V3 // Load 16 bytes @R7+R9 into V3 807 VSLO V3, V9, V3 // Shift left 808 VCMPEQUB V0, V2, V4 // Compare first 16 bytes 809 VCMPEQUB V1, V3, V5 // Compare extra over 16 bytes 810 VAND V4, V5, V6 // Check if both equal 811 VCMPEQUBCC V6, V7, V8 // All equal? 812 BLT CR6, found // Yes 813 ADD $1, R7 // On to next byte 814 CMP R7, LASTSTR // Check if last start byte 815 BGT notfound // If too high, not found 816 BR index17to32loop // Continue 817 818notfound: 819 MOVD $-1, R3 // Return -1 if not found 820 RET 821 822index33plus: 823 MOVD $0, (R0) // Case not implemented 824 RET // Crash before return 825 826foundR25: 827 SRD $3, R25 // Convert from bits to bytes 828 ADD R25, R7 // Add to current string address 829 SUB R3, R7 // Subtract from start of string 830 MOVD R7, R3 // Return byte where found 831 RET 832found4: 833 ADD $1, R7 // found from unrolled loop at index 3 834found3: 835 ADD $1, R7 // found from unrolled loop at index 2 836found2: 837 ADD $1, R7 // found from unrolled loop at index 1 838found: // found at index 0 839 SUB R3, R7 // Return byte where found 840 MOVD R7, R3 841 RET 842