// Copyright 2018 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.
#include "textflag.h"
// func IndexByte(b []byte, c byte) int
// input:
// R0: b ptr
// R1: b len
// R2: b cap (unused)
// R3: c byte to search
// return
// R0: result
TEXT ·IndexByte<ABIInternal>(SB),NOSPLIT,$0-40
MOVD R3, R2
B ·IndexByteString<ABIInternal>(SB)
// func IndexByteString(s string, c byte) int
// input:
// R0: s ptr
// R1: s len
// R2: c byte to search
// return
// R0: result
TEXT ·IndexByteString<ABIInternal>(SB),NOSPLIT,$0-32
// Core algorithm:
// For each 32-byte chunk we calculate a 64-bit syndrome value,
// with two bits per byte. For each tuple, bit 0 is set if the
// relevant byte matched the requested character and bit 1 is
// not used (faster than using a 32bit syndrome). Since the bits
// in the syndrome reflect exactly the order in which things occur
// in the original string, counting trailing zeros allows to
// identify exactly which byte has matched.
CBZ R1, fail
MOVD R0, R11
// Magic constant 0x40100401 allows us to identify
// which lane matches the requested byte.
// 0x40100401 = ((1<<0) + (4<<8) + (16<<16) + (64<<24))
// Different bytes have different bit masks (i.e: 1, 4, 16, 64)
MOVD $0x40100401, R5
VMOV R2, V0.B16
// Work with aligned 32-byte chunks
BIC $0x1f, R0, R3
VMOV R5, V5.S4
ANDS $0x1f, R0, R9
AND $0x1f, R1, R10
BEQ loop
// Input string is not 32-byte aligned. We calculate the
// syndrome value for the aligned 32 bytes block containing
// the first bytes and mask off the irrelevant part.
VLD1.P (R3), [V1.B16, V2.B16]
SUB $0x20, R9, R4
ADDS R4, R1, R1
VCMEQ V0.B16, V1.B16, V3.B16
VCMEQ V0.B16, V2.B16, V4.B16
VAND V5.B16, V3.B16, V3.B16
VAND V5.B16, V4.B16, V4.B16
VADDP V4.B16, V3.B16, V6.B16 // 256->128
VADDP V6.B16, V6.B16, V6.B16 // 128->64
VMOV V6.D[0], R6
// Clear the irrelevant lower bits
LSL $1, R9, R4
LSR R4, R6, R6
LSL R4, R6, R6
// The first block can also be the last
BLS masklast
// Have we found something already?
CBNZ R6, tail
loop:
VLD1.P (R3), [V1.B16, V2.B16]
SUBS $0x20, R1, R1
VCMEQ V0.B16, V1.B16, V3.B16
VCMEQ V0.B16, V2.B16, V4.B16
// If we're out of data we finish regardless of the result
BLS end
// Use a fast check for the termination condition
VORR V4.B16, V3.B16, V6.B16
VADDP V6.D2, V6.D2, V6.D2
VMOV V6.D[0], R6
// We're not out of data, loop if we haven't found the character
CBZ R6, loop
end:
// Termination condition found, let's calculate the syndrome value
VAND V5.B16, V3.B16, V3.B16
VAND V5.B16, V4.B16, V4.B16
VADDP V4.B16, V3.B16, V6.B16
VADDP V6.B16, V6.B16, V6.B16
VMOV V6.D[0], R6
// Only do the clear for the last possible block with less than 32 bytes
// Condition flags come from SUBS in the loop
BHS tail
masklast:
// Clear the irrelevant upper bits
ADD R9, R10, R4
AND $0x1f, R4, R4
SUB $0x20, R4, R4
NEG R4<<1, R4
LSL R4, R6, R6
LSR R4, R6, R6
tail:
// Check that we have found a character
CBZ R6, fail
// Count the trailing zeros using bit reversing
RBIT R6, R6
// Compensate the last post-increment
SUB $0x20, R3, R3
// And count the leading zeros
CLZ R6, R6
// R6 is twice the offset into the fragment
ADD R6>>1, R3, R0
// Compute the offset result
SUB R11, R0, R0
RET
fail:
MOVD $-1, R0
RET
