blob: 80a1f853d3d4323ca035400fef628602d0510c9d [file] [log] [blame]
// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// This is an implementation based on the s390x
// implementation.
// Find a separator with 2 <= len <= 32 within a string.
// Separators with lengths of 2, 3 or 4 are handled
// specially.
// This works on power8 and above. The loads and
// compares are done in big endian order
// since that allows the used of VCLZD, and allows
// the same implementation to work on big and little
// endian platforms with minimal conditional changes.
// NOTE: There is a power9 implementation that
// improves performance by 10-15% on little
// endian for some of the benchmarks.
// Unrolled index2to16 loop by 4 on ppc64le/power9
// Work is still needed for a big endian
// implementation on power9.
//go:build ppc64 || ppc64le
#include "go_asm.h"
#include "textflag.h"
// Needed to swap LXVD2X loads to the correct
// byte order to work on POWER8.
#ifdef GOARCH_ppc64
DATA byteswap<>+0(SB)/8, $0x0001020304050607
DATA byteswap<>+8(SB)/8, $0x08090a0b0c0d0e0f
#else
DATA byteswap<>+0(SB)/8, $0x0706050403020100
DATA byteswap<>+8(SB)/8, $0x0f0e0d0c0b0a0908
#endif
// Load bytes in big endian order. Address
// alignment does not need checking.
#define VLOADSWAP(base, index, vreg, vsreg) \
LXVD2X (base)(index), vsreg; \
VPERM vreg, vreg, SWAP, vreg
GLOBL byteswap<>+0(SB), RODATA, $16
TEXT ·Index<ABIInternal>(SB),NOSPLIT|NOFRAME,$0-56
// R3 = byte array pointer
// R4 = length
MOVD R6, R5 // R5 = separator pointer
MOVD R7, R6 // R6 = separator length
#ifdef GOARCH_ppc64le
MOVBZ internal∕cpu·PPC64+const_offsetPPC64HasPOWER9(SB), R7
CMP R7, $1
BNE power8
BR indexbodyp9<>(SB)
#endif
power8:
BR indexbody<>(SB)
TEXT ·IndexString<ABIInternal>(SB),NOSPLIT|NOFRAME,$0-40
// R3 = string
// R4 = length
// R5 = separator pointer
// R6 = separator length
#ifdef GOARCH_ppc64le
MOVBZ internal∕cpu·PPC64+const_offsetPPC64HasPOWER9(SB), R7
CMP R7, $1
BNE power8
BR indexbodyp9<>(SB)
#endif
power8:
BR indexbody<>(SB)
// s: string we are searching
// sep: string to search for
// R3=&s[0], R4=len(s)
// R5=&sep[0], R6=len(sep)
// R14=&ret (index where sep found)
// R7=working addr of string
// R16=index value 16
// R17=index value 17
// R18=index value 18
// R19=index value 1
// R26=LASTBYTE of string
// R27=LASTSTR last start byte to compare with sep
// R8, R9 scratch
// V0=sep left justified zero fill
// CR4=sep length >= 16
#define SEPMASK V17
#define LASTBYTE R26
#define LASTSTR R27
#define ONES V20
#define SWAP V21
#define SWAP_ VS53
TEXT indexbody<>(SB), NOSPLIT|NOFRAME, $0
CMP R6, R4 // Compare lengths
BGT notfound // If sep len is > string, notfound
ADD R4, R3, LASTBYTE // find last byte addr
SUB R6, LASTBYTE, LASTSTR // LAST=&s[len(s)-len(sep)] (last valid start index)
CMP R6, $0 // Check sep len
BEQ notfound // sep len 0 -- not found
MOVD R3, R7 // Copy of string addr
MOVD $16, R16 // Index value 16
MOVD $17, R17 // Index value 17
MOVD $18, R18 // Index value 18
MOVD $1, R19 // Index value 1
MOVD $byteswap<>+00(SB), R8
VSPLTISB $0xFF, ONES // splat all 1s
LXVD2X (R8)(R0), SWAP_ // Set up swap string
CMP R6, $16, CR4 // CR4 for len(sep) >= 16
VOR ONES, ONES, SEPMASK // Set up full SEPMASK
BGE CR4, loadge16 // Load for len(sep) >= 16
SUB R6, R16, R9 // 16-len of sep
SLD $3, R9 // Set up for VSLO
MTVSRD R9, V9 // Set up for VSLO
VSLDOI $8, V9, V9, V9 // Set up for VSLO
VSLO ONES, V9, SEPMASK // Mask for separator len(sep) < 16
loadge16:
ANDCC $15, R5, R9 // Find byte offset of sep
ADD R9, R6, R10 // Add sep len
CMP R10, $16 // Check if sep len+offset > 16
BGT sepcross16 // Sep crosses 16 byte boundary
RLDICR $0, R5, $59, R8 // Adjust addr to 16 byte container
VLOADSWAP(R8, R0, V0, V0) // Load 16 bytes @R8 into V0
SLD $3, R9 // Set up shift count for VSLO
MTVSRD R9, V8 // Set up shift count for VSLO
VSLDOI $8, V8, V8, V8
VSLO V0, V8, V0 // Shift by start byte
VAND V0, SEPMASK, V0 // Mask separator (< 16)
BR index2plus
sepcross16:
VLOADSWAP(R5, R0, V0, V0) // Load 16 bytes @R5 into V0
VAND V0, SEPMASK, V0 // mask out separator
BLE CR4, index2to16
BR index17plus // Handle sep > 16
index2plus:
CMP R6, $2 // Check length of sep
BNE index3plus // If not 2, check for 3
ADD $16, R7, R9 // Check if next 16 bytes past last
CMP R9, LASTBYTE // compare with last
BGE index2to16 // 2 <= len(string) <= 16
MOVD $0xff00, R21 // Mask for later
MTVSRD R21, V25 // Move to Vreg
VSPLTH $3, V25, V31 // Splat mask
VSPLTH $0, V0, V1 // Splat 1st 2 bytes of sep
VSPLTISB $0, V10 // Clear V10
// First case: 2 byte separator
// V1: 2 byte separator splatted
// V2: 16 bytes at addr
// V4: 16 bytes at addr+1
// Compare 2 byte separator at start
// and at start+1. Use VSEL to combine
// those results to find the first
// matching start byte, returning
// that value when found. Loop as
// long as len(string) > 16
index2loop2:
VLOADSWAP(R7, R19, V3, V3) // Load 16 bytes @R7+1 into V3
index2loop:
VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2
VCMPEQUH V1, V2, V5 // Search for sep
VCMPEQUH V1, V3, V6 // Search for sep offset by 1
VSEL V6, V5, V31, V7 // merge even and odd indices
VCLZD V7, V18 // find index of first match
MFVSRD V18, R25 // get first value
CMP R25, $64 // Found if < 64
BLT foundR25 // Return byte index where found
VSLDOI $8, V18, V18, V18 // Adjust 2nd value
MFVSRD V18, R25 // get second value
CMP R25, $64 // Found if < 64
ADD $64, R25 // Update byte offset
BLT foundR25 // Return value
ADD $16, R7 // R7+=16 Update string pointer
ADD $17, R7, R9 // R9=F7+17 since loop unrolled
CMP R9, LASTBYTE // Compare addr+17 against last byte
BLT index2loop2 // If < last, continue loop
CMP R7, LASTBYTE // Compare addr+16 against last byte
BLT index2to16 // If < 16 handle specially
VLOADSWAP(R7, R0, V3, V3) // Load 16 bytes @R7 into V3
VSLDOI $1, V3, V10, V3 // Shift left by 1 byte
BR index2loop
index3plus:
CMP R6, $3 // Check if sep == 3
BNE index4plus // If not check larger
ADD $19, R7, R9 // Find bytes for use in this loop
CMP R9, LASTBYTE // Compare against last byte
BGE index2to16 // Remaining string 2<=len<=16
MOVD $0xff00, R21 // Set up mask for upcoming loop
MTVSRD R21, V25 // Move mask to Vreg
VSPLTH $3, V25, V31 // Splat mask
VSPLTH $0, V0, V1 // Splat 1st two bytes of sep
VSPLTB $2, V0, V8 // Splat 3rd byte of sep
// Loop to process 3 byte separator.
// string[0:16] is in V2
// string[2:18] is in V3
// sep[0:2] splatted in V1
// sec[3] splatted in v8
// Load vectors at string, string+1
// and string+2. Compare string, string+1
// against first 2 bytes of separator
// splatted, and string+2 against 3rd
// byte splatted. Merge the results with
// VSEL to find the first byte of a match.
// Special handling for last 16 bytes if the
// string fits in 16 byte multiple.
index3loop2:
MOVD $2, R21 // Set up index for 2
VSPLTISB $0, V10 // Clear V10
VLOADSWAP(R7, R21, V3, V3)// Load 16 bytes @R7+2 into V3
VSLDOI $14, V3, V10, V3 // Left justify next 2 bytes
index3loop:
VLOADSWAP(R7, R0, V2, V2) // Load with correct order
VSLDOI $1, V2, V3, V4 // string[1:17]
VSLDOI $2, V2, V3, V9 // string[2:18]
VCMPEQUH V1, V2, V5 // compare hw even indices
VCMPEQUH V1, V4, V6 // compare hw odd indices
VCMPEQUB V8, V9, V10 // compare 3rd to last byte
VSEL V6, V5, V31, V7 // Find 1st matching byte using mask
VAND V7, V10, V7 // AND matched bytes with matched 3rd byte
VCLZD V7, V18 // Find first nonzero indexes
MFVSRD V18, R25 // Move 1st doubleword
CMP R25, $64 // If < 64 found
BLT foundR25 // Return matching index
VSLDOI $8, V18, V18, V18 // Move value
MFVSRD V18, R25 // Move 2nd doubleword
CMP R25, $64 // If < 64 found
ADD $64, R25 // Update byte index
BLT foundR25 // Return matching index
ADD $16, R7 // R7+=16 string ptr
ADD $19, R7, R9 // Number of string bytes for loop
CMP R9, LASTBYTE // Compare against last byte of string
BLT index3loop2 // If within, continue this loop
CMP R7, LASTSTR // Compare against last start byte
BLT index2to16 // Process remainder
VSPLTISB $0, V3 // Special case for last 16 bytes
BR index3loop // Continue this loop
// Loop to process 4 byte separator
// string[0:16] in V2
// string[3:16] in V3
// sep[0:4] splatted in V1
// Set up vectors with strings at offsets
// 0, 1, 2, 3 and compare against the 4 byte
// separator also splatted. Use VSEL with the
// compare results to find the first byte where
// a separator match is found.
index4plus:
CMP R6, $4 // Check if 4 byte separator
BNE index5plus // If not next higher
ADD $20, R7, R9 // Check string size to load
CMP R9, LASTBYTE // Verify string length
BGE index2to16 // If not large enough, process remaining
MOVD $2, R15 // Set up index
// Set up masks for use with VSEL
MOVD $0xff, R21 // Set up mask 0xff000000ff000000...
SLD $24, R21
MTVSRD R21, V10
VSPLTW $1, V10, V29
VSLDOI $2, V29, V29, V30 // Mask 0x0000ff000000ff00...
MOVD $0xffff, R21
SLD $16, R21
MTVSRD R21, V10
VSPLTW $1, V10, V31 // Mask 0xffff0000ffff0000...
VSPLTW $0, V0, V1 // Splat 1st word of separator
index4loop:
VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2
next4:
VSPLTISB $0, V10 // Clear
MOVD $3, R9 // Number of bytes beyond 16
VLOADSWAP(R7, R9, V3, V3) // Load 16 bytes @R7+3 into V3
VSLDOI $13, V3, V10, V3 // Shift left last 3 bytes
VSLDOI $1, V2, V3, V4 // V4=(V2:V3)<<1
VSLDOI $2, V2, V3, V9 // V9=(V2:V3)<<2
VSLDOI $3, V2, V3, V10 // V10=(V2:v3)<<3
VCMPEQUW V1, V2, V5 // compare index 0, 4, ... with sep
VCMPEQUW V1, V4, V6 // compare index 1, 5, ... with sep
VCMPEQUW V1, V9, V11 // compare index 2, 6, ... with sep
VCMPEQUW V1, V10, V12 // compare index 3, 7, ... with sep
VSEL V6, V5, V29, V13 // merge index 0, 1, 4, 5, using mask
VSEL V12, V11, V30, V14 // merge index 2, 3, 6, 7, using mask
VSEL V14, V13, V31, V7 // final merge
VCLZD V7, V18 // Find first index for each half
MFVSRD V18, R25 // Isolate value
CMP R25, $64 // If < 64, found
BLT foundR25 // Return found index
VSLDOI $8, V18, V18, V18 // Move for MFVSRD
MFVSRD V18, R25 // Isolate other value
CMP R25, $64 // If < 64, found
ADD $64, R25 // Update index for high doubleword
BLT foundR25 // Return found index
ADD $16, R7 // R7+=16 for next string
ADD $20, R7, R9 // R+20 for all bytes to load
CMP R9, LASTBYTE // Past end? Maybe check for extra?
BLT index4loop // If not, continue loop
CMP R7, LASTSTR // Check remainder
BLE index2to16 // Process remainder
BR notfound // Not found
index5plus:
CMP R6, $16 // Check for sep > 16
BGT index17plus // Handle large sep
// Assumption is that the separator is smaller than the string at this point
index2to16:
CMP R7, LASTSTR // Compare last start byte
BGT notfound // last takes len(sep) into account
ADD $16, R7, R9 // Check for last byte of string
CMP R9, LASTBYTE
BGT index2to16tail
// At least 16 bytes of string left
// Mask the number of bytes in sep
index2to16loop:
VLOADSWAP(R7, R0, V1, V1) // Load 16 bytes @R7 into V1
compare:
VAND V1, SEPMASK, V2 // Mask out sep size
VCMPEQUBCC V0, V2, V3 // Compare masked string
BLT CR6, found // All equal
ADD $1, R7 // Update ptr to next byte
CMP R7, LASTSTR // Still less than last start byte
BGT notfound // Not found
ADD $16, R7, R9 // Verify remaining bytes
CMP R9, LASTBYTE // At least 16
BLT index2to16loop // Try again
// Less than 16 bytes remaining in string
// Separator >= 2
index2to16tail:
ADD R3, R4, R9 // End of string
SUB R7, R9, R9 // Number of bytes left
ANDCC $15, R7, R10 // 16 byte offset
ADD R10, R9, R11 // offset + len
CMP R11, $16 // >= 16?
BLE short // Does not cross 16 bytes
VLOADSWAP(R7, R0, V1, V1) // Load 16 bytes @R7 into V1
BR index2to16next // Continue on
short:
RLDICR $0, R7, $59, R9 // Adjust addr to 16 byte container
VLOADSWAP(R9, R0, V1, V1)// Load 16 bytes @R9 into V1
SLD $3, R10 // Set up shift
MTVSRD R10, V8 // Set up shift
VSLDOI $8, V8, V8, V8
VSLO V1, V8, V1 // Shift by start byte
VSPLTISB $0, V25 // Clear for later use
index2to16next:
VAND V1, SEPMASK, V2 // Just compare size of sep
VCMPEQUBCC V0, V2, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BGT notfound // If at end, then not found
VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte
BR index2to16next // Check the next partial string
index17plus:
CMP R6, $32 // Check if 17 < len(sep) <= 32
BGT index33plus
SUB $16, R6, R9 // Extra > 16
SLD $56, R9, R10 // Shift to use in VSLO
MTVSRD R10, V9 // Set up for VSLO
VLOADSWAP(R5, R9, V1, V1)// Load 16 bytes @R5+R9 into V1
VSLO V1, V9, V1 // Shift left
VSPLTISB $0xff, V7 // Splat 1s
VSPLTISB $0, V27 // Splat 0
index17to32loop:
VLOADSWAP(R7, R0, V2, V2) // Load 16 bytes @R7 into V2
next17:
VLOADSWAP(R7, R9, V3, V3) // Load 16 bytes @R7+R9 into V3
VSLO V3, V9, V3 // Shift left
VCMPEQUB V0, V2, V4 // Compare first 16 bytes
VCMPEQUB V1, V3, V5 // Compare extra over 16 bytes
VAND V4, V5, V6 // Check if both equal
VCMPEQUBCC V6, V7, V8 // All equal?
BLT CR6, found // Yes
ADD $1, R7 // On to next byte
CMP R7, LASTSTR // Check if last start byte
BGT notfound // If too high, not found
BR index17to32loop // Continue
notfound:
MOVD $-1, R3 // Return -1 if not found
RET
index33plus:
MOVD $0, (R0) // Case not implemented
RET // Crash before return
foundR25:
SRD $3, R25 // Convert from bits to bytes
ADD R25, R7 // Add to current string address
SUB R3, R7 // Subtract from start of string
MOVD R7, R3 // Return byte where found
RET
found:
SUB R3, R7 // Return byte where found
MOVD R7, R3
RET
TEXT indexbodyp9<>(SB), NOSPLIT|NOFRAME, $0
CMP R6, R4 // Compare lengths
BGT notfound // If sep len is > string, notfound
ADD R4, R3, LASTBYTE // find last byte addr
SUB R6, LASTBYTE, LASTSTR // LAST=&s[len(s)-len(sep)] (last valid start index)
CMP R6, $0 // Check sep len
BEQ notfound // sep len 0 -- not found
MOVD R3, R7 // Copy of string addr
#ifndef GOPPC64_power10
MOVD $16, R16 // Index value 16
MOVD $17, R17 // Index value 17
MOVD $18, R18 // Index value 18
VSPLTISB $0xFF, ONES // splat all 1s
VOR ONES, ONES, SEPMASK // Set up full SEPMASK
#else
SLD $56, R6, R14 // Set up separator length for LXVLL
#endif
MOVD $1, R19 // Index value 1
CMP R6, $16, CR4 // CR4 for len(sep) >= 16
BGE CR4, loadge16 // Load for len(sep) >= 16
#ifndef GOPPC64_power10
SUB R6, R16, R9 // 16-len of sep
SLD $3, R9 // Set up for VSLO
MTVSRD R9, V9 // Set up for VSLO
VSLDOI $8, V9, V9, V9 // Set up for VSLO
VSLO ONES, V9, SEPMASK // Mask for separator len(sep) < 16
#endif
loadge16:
ANDCC $15, R5, R9 // Find byte offset of sep
ADD R9, R6, R10 // Add sep len
CMP R10, $16 // Check if sep len+offset > 16
BGT sepcross16 // Sep crosses 16 byte boundary
#ifdef GOPPC64_power10
LXVLL R5, R14, V0 // Load separator
#else
RLDICR $0, R5, $59, R8 // Adjust addr to 16 byte container
LXVB16X (R8)(R0), V0 // Load 16 bytes @R8 into V0
SLD $3, R9 // Set up shift count for VSLO
MTVSRD R9, V8 // Set up shift count for VSLO
VSLDOI $8, V8, V8, V8
VSLO V0, V8, V0 // Shift by start byte
VAND V0, SEPMASK, V0 // Mask separator (< 16)
#endif
BR index2plus
sepcross16:
#ifdef GOPPC64_power10
LXVLL R5, R14, V0 // Load separator
#else
LXVB16X (R5)(R0), V0 // Load 16 bytes @R5 into V0\
VAND V0, SEPMASK, V0 // mask out separator
#endif
BLE CR4, index2to16
BR index17plus // Handle sep > 16
index2plus:
CMP R6, $2 // Check length of sep
BNE index3plus // If not 2, check for 3
ADD $16, R7, R9 // Check if next 16 bytes past last
CMP R9, LASTBYTE // compare with last
BGE index2to16 // 2 <= len(string) <= 16
MOVD $0xff00, R21 // Mask for later
MTVSRD R21, V25 // Move to Vreg
VSPLTH $3, V25, V31 // Splat mask
VSPLTH $0, V0, V1 // Splat 1st 2 bytes of sep
VSPLTISB $0, V10 // Clear V10
// First case: 2 byte separator
// V1: 2 byte separator splatted
// V2: 16 bytes at addr
// V4: 16 bytes at addr+1
// Compare 2 byte separator at start
// and at start+1. Use VSEL to combine
// those results to find the first
// matching start byte, returning
// that value when found. Loop as
// long as len(string) > 16
index2loop2:
LXVB16X (R7)(R19), V3 // Load 16 bytes @R7+1 into V3
index2loop:
LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2
VCMPEQUH V1, V2, V5 // Search for sep
VCMPEQUH V1, V3, V6 // Search for sep offset by 1
VSEL V6, V5, V31, V7 // merge even and odd indices
VCLZD V7, V18 // find index of first match
MFVSRD V18, R25 // get first value
CMP R25, $64 // Found if < 64
BLT foundR25 // Return byte index where found
MFVSRLD V18, R25 // get second value
CMP R25, $64 // Found if < 64
ADD $64, R25 // Update byte offset
BLT foundR25 // Return value
ADD $16, R7 // R7+=16 Update string pointer
ADD $17, R7, R9 // R9=F7+17 since loop unrolled
CMP R9, LASTBYTE // Compare addr+17 against last byte
BLT index2loop2 // If < last, continue loop
CMP R7, LASTBYTE // Compare addr+16 against last byte
BLT index2to16 // If < 16 handle specially
LXVB16X (R7)(R0), V3 // Load 16 bytes @R7 into V3
VSLDOI $1, V3, V10, V3 // Shift left by 1 byte
BR index2loop
index3plus:
CMP R6, $3 // Check if sep == 3
BNE index4plus // If not check larger
ADD $19, R7, R9 // Find bytes for use in this loop
CMP R9, LASTBYTE // Compare against last byte
BGE index2to16 // Remaining string 2<=len<=16
MOVD $0xff00, R21 // Set up mask for upcoming loop
MTVSRD R21, V25 // Move mask to Vreg
VSPLTH $3, V25, V31 // Splat mask
VSPLTH $0, V0, V1 // Splat 1st two bytes of sep
VSPLTB $2, V0, V8 // Splat 3rd byte of sep
// Loop to process 3 byte separator.
// string[0:16] is in V2
// string[2:18] is in V3
// sep[0:2] splatted in V1
// sec[3] splatted in v8
// Load vectors at string, string+1
// and string+2. Compare string, string+1
// against first 2 bytes of separator
// splatted, and string+2 against 3rd
// byte splatted. Merge the results with
// VSEL to find the first byte of a match.
// Special handling for last 16 bytes if the
// string fits in 16 byte multiple.
index3loop2:
MOVD $2, R21 // Set up index for 2
VSPLTISB $0, V10 // Clear V10
LXVB16X (R7)(R21), V3 // Load 16 bytes @R7+2 into V3
VSLDOI $14, V3, V10, V3 // Left justify next 2 bytes
index3loop:
LXVB16X (R7)(R0), V2 // Load 16 bytes @R7
VSLDOI $1, V2, V3, V4 // string[1:17]
VSLDOI $2, V2, V3, V9 // string[2:18]
VCMPEQUH V1, V2, V5 // compare hw even indices
VCMPEQUH V1, V4, V6 // compare hw odd indices
VCMPEQUB V8, V9, V10 // compare 3rd to last byte
VSEL V6, V5, V31, V7 // Find 1st matching byte using mask
VAND V7, V10, V7 // AND matched bytes with matched 3rd byte
VCLZD V7, V18 // Find first nonzero indexes
MFVSRD V18, R25 // Move 1st doubleword
CMP R25, $64 // If < 64 found
BLT foundR25 // Return matching index
MFVSRLD V18, R25 // Move 2nd doubleword
CMP R25, $64 // If < 64 found
ADD $64, R25 // Update byte index
BLT foundR25 // Return matching index
ADD $16, R7 // R7+=16 string ptr
ADD $19, R7, R9 // Number of string bytes for loop
CMP R9, LASTBYTE // Compare against last byte of string
BLT index3loop2 // If within, continue this loop
CMP R7, LASTSTR // Compare against last start byte
BLT index2to16 // Process remainder
VSPLTISB $0, V3 // Special case for last 16 bytes
BR index3loop // Continue this loop
// Loop to process 4 byte separator
// string[0:16] in V2
// string[3:16] in V3
// sep[0:4] splatted in V1
// Set up vectors with strings at offsets
// 0, 1, 2, 3 and compare against the 4 byte
// separator also splatted. Use VSEL with the
// compare results to find the first byte where
// a separator match is found.
index4plus:
CMP R6, $4 // Check if 4 byte separator
BNE index5plus // If not next higher
ADD $20, R7, R9 // Check string size to load
CMP R9, LASTBYTE // Verify string length
BGE index2to16 // If not large enough, process remaining
// Set up masks for use with VSEL
MOVD $0xff, R21 // Set up mask 0xff000000ff000000...
SLD $24, R21
MTVSRWS R21, V29
VSLDOI $2, V29, V29, V30 // Mask 0x0000ff000000ff00...
MOVD $0xffff, R21
SLD $16, R21
MTVSRWS R21, V31
VSPLTW $0, V0, V1 // Splat 1st word of separator
index4loop:
LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2
next4:
VSPLTISB $0, V10 // Clear
MOVD $3, R9 // Number of bytes beyond 16
LXVB16X (R7)(R9), V3 // Load 16 bytes @R7 into V3
VSLDOI $13, V3, V10, V3 // Shift left last 3 bytes
VSLDOI $1, V2, V3, V4 // V4=(V2:V3)<<1
VSLDOI $2, V2, V3, V9 // V9=(V2:V3)<<2
VSLDOI $3, V2, V3, V10 // V10=(V2:v3)<<3
VCMPEQUW V1, V2, V5 // compare index 0, 4, ... with sep
VCMPEQUW V1, V4, V6 // compare index 1, 5, ... with sep
VCMPEQUW V1, V9, V11 // compare index 2, 6, ... with sep
VCMPEQUW V1, V10, V12 // compare index 3, 7, ... with sep
VSEL V6, V5, V29, V13 // merge index 0, 1, 4, 5, using mask
VSEL V12, V11, V30, V14 // merge index 2, 3, 6, 7, using mask
VSEL V14, V13, V31, V7 // final merge
VCLZD V7, V18 // Find first index for each half
MFVSRD V18, R25 // Isolate value
CMP R25, $64 // If < 64, found
BLT foundR25 // Return found index
MFVSRLD V18, R25 // Isolate other value
CMP R25, $64 // If < 64, found
ADD $64, R25 // Update index for high doubleword
BLT foundR25 // Return found index
ADD $16, R7 // R7+=16 for next string
ADD $20, R7, R9 // R+20 for all bytes to load
CMP R9, LASTBYTE // Past end? Maybe check for extra?
BLT index4loop // If not, continue loop
CMP R7, LASTSTR // Check remainder
BLE index2to16 // Process remainder
BR notfound // Not found
index5plus:
CMP R6, $16 // Check for sep > 16
BGT index17plus // Handle large sep
// Assumption is that the separator is smaller than the string at this point
index2to16:
CMP R7, LASTSTR // Compare last start byte
BGT notfound // last takes len(sep) into account
ADD $19, R7, R9 // To check 4 indices per iteration, need at least 16+3 bytes
CMP R9, LASTBYTE
// At least 16 bytes of string left
// Mask the number of bytes in sep
VSPLTISB $0, V10 // Clear
BGT index2to16tail
#ifdef GOPPC64_power10
ADD $3,R7, R17 // Base+3
ADD $2,R7, R8 // Base+2
ADD $1,R7, R10 // Base+1
#else
MOVD $3, R17 // Number of bytes beyond 16
#endif
PCALIGN $16
index2to16loop:
#ifdef GOPPC64_power10
LXVLL R7, R14, V8 // Load next 16 bytes of string from Base
LXVLL R10, R14, V9 // Load next 16 bytes of string from Base+1
LXVLL R8, R14, V11 // Load next 16 bytes of string from Base+2
LXVLL R17,R14, V12 // Load next 16 bytes of string from Base+3
#else
LXVB16X (R7)(R0), V1 // Load next 16 bytes of string into V1 from R7
LXVB16X (R7)(R17), V5 // Load next 16 bytes of string into V5 from R7+3
VSLDOI $13, V5, V10, V2 // Shift left last 3 bytes
VSLDOI $1, V1, V2, V3 // V3=(V1:V2)<<1
VSLDOI $2, V1, V2, V4 // V4=(V1:V2)<<2
VAND V1, SEPMASK, V8 // Mask out sep size 0th index
VAND V3, SEPMASK, V9 // Mask out sep size 1st index
VAND V4, SEPMASK, V11 // Mask out sep size 2nd index
VAND V5, SEPMASK, V12 // Mask out sep size 3rd index
#endif
VCMPEQUBCC V0, V8, V8 // compare masked string
BLT CR6, found // All equal while comparing 0th index
VCMPEQUBCC V0, V9, V9 // compare masked string
BLT CR6, found2 // All equal while comparing 1st index
VCMPEQUBCC V0, V11, V11 // compare masked string
BLT CR6, found3 // All equal while comparing 2nd index
VCMPEQUBCC V0, V12, V12 // compare masked string
BLT CR6, found4 // All equal while comparing 3rd index
ADD $4, R7 // Update ptr to next 4 bytes
#ifdef GOPPC64_power10
ADD $4, R17 // Update ptr to next 4 bytes
ADD $4, R8 // Update ptr to next 4 bytes
ADD $4, R10 // Update ptr to next 4 bytes
#endif
CMP R7, LASTSTR // Still less than last start byte
BGT notfound // Not found
ADD $19, R7, R9 // Verify remaining bytes
CMP R9, LASTBYTE // length of string at least 19
BLE index2to16loop // Try again, else do post processing and jump to index2to16next
PCALIGN $32
// <19 bytes left, post process the remaining string
index2to16tail:
#ifdef GOPPC64_power10
index2to16next_p10:
LXVLL R7,R14, V1 // Load 16 bytes @R7 into V1
VCMPEQUBCC V1, V0, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BLE index2to16next_p10 // If at end, then not found
BR notfound // go to remainder loop
#else
ADD R3, R4, R9 // End of string
SUB R7, R9, R9 // Number of bytes left
ANDCC $15, R7, R10 // 16 byte offset
ADD R10, R9, R11 // offset + len
CMP R11, $16 // >= 16?
BLE short // Does not cross 16 bytes
LXVB16X (R7)(R0), V1 // Load 16 bytes @R7 into V1
CMP R9, $16 // Post-processing of unrolled loop
BLE index2to16next // continue to index2to16next if <= 16 bytes
SUB R16, R9, R10 // R9 should be 18 or 17 hence R10 is 1 or 2
LXVB16X (R7)(R10), V9
CMP R10, $1 // string length is 17, compare 1 more byte
BNE extra2 // string length is 18, compare 2 more bytes
VSLDOI $15, V9, V10, V25
VAND V1, SEPMASK, V2 // Just compare size of sep
VCMPEQUBCC V0, V2, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BGT notfound // If at end, then not found
VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte
BR index2to16next // go to remainder loop
extra2:
VSLDOI $14, V9, V10, V25
VAND V1, SEPMASK, V2 // Just compare size of sep
VCMPEQUBCC V0, V2, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BGT notfound // If at end, then not found
VOR V1, V1, V4 // save remaining string
VSLDOI $1, V1, V25, V1 // Shift string left by 1 byte for 17th byte
VAND V1, SEPMASK, V2 // Just compare size of sep
VCMPEQUBCC V0, V2, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BGT notfound // If at end, then not found
VSLDOI $2, V4, V25, V1 // Shift saved string left by 2 bytes for 18th byte
BR index2to16next // Check the remaining partial string in index2to16next
short:
RLDICR $0, R7, $59, R9 // Adjust addr to 16 byte container
LXVB16X (R9)(R0), V1 // Load 16 bytes @R9 into V1
SLD $3, R10 // Set up shift
MTVSRD R10, V8 // Set up shift
VSLDOI $8, V8, V8, V8
VSLO V1, V8, V1 // Shift by start byte
PCALIGN $16
index2to16next:
VAND V1, SEPMASK, V2 // Just compare size of sep
VCMPEQUBCC V0, V2, V3 // Compare sep and partial string
BLT CR6, found // Found
ADD $1, R7 // Not found, try next partial string
CMP R7, LASTSTR // Check for end of string
BGT notfound // If at end, then not found
VSLDOI $1, V1, V10, V1 // Shift string left by 1 byte
BR index2to16next // Check the next partial string
#endif // Tail processing if GOPPC64!=power10
index17plus:
CMP R6, $32 // Check if 17 < len(sep) <= 32
BGT index33plus
SUB $16, R6, R9 // Extra > 16
SLD $56, R9, R10 // Shift to use in VSLO
MTVSRD R10, V9 // Set up for VSLO
LXVB16X (R5)(R9), V1 // Load 16 bytes @R5+R9 into V1
VSLO V1, V9, V1 // Shift left
VSPLTISB $0xff, V7 // Splat 1s
VSPLTISB $0, V27 // Splat 0
index17to32loop:
LXVB16X (R7)(R0), V2 // Load 16 bytes @R7 into V2
next17:
LXVB16X (R7)(R9), V3 // Load 16 bytes @R7+R9 into V3
VSLO V3, V9, V3 // Shift left
VCMPEQUB V0, V2, V4 // Compare first 16 bytes
VCMPEQUB V1, V3, V5 // Compare extra over 16 bytes
VAND V4, V5, V6 // Check if both equal
VCMPEQUBCC V6, V7, V8 // All equal?
BLT CR6, found // Yes
ADD $1, R7 // On to next byte
CMP R7, LASTSTR // Check if last start byte
BGT notfound // If too high, not found
BR index17to32loop // Continue
notfound:
MOVD $-1, R3 // Return -1 if not found
RET
index33plus:
MOVD $0, (R0) // Case not implemented
RET // Crash before return
foundR25:
SRD $3, R25 // Convert from bits to bytes
ADD R25, R7 // Add to current string address
SUB R3, R7 // Subtract from start of string
MOVD R7, R3 // Return byte where found
RET
found4:
ADD $1, R7 // found from unrolled loop at index 3
found3:
ADD $1, R7 // found from unrolled loop at index 2
found2:
ADD $1, R7 // found from unrolled loop at index 1
found: // found at index 0
SUB R3, R7 // Return byte where found
MOVD R7, R3
RET