| // 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" | |
| TEXT ·IndexByte(SB),NOSPLIT,$0-40 | |
| MOVD b_base+0(FP), R0 | |
| MOVD b_len+8(FP), R2 | |
| MOVBU c+24(FP), R1 | |
| MOVD $ret+32(FP), R8 | |
| B indexbytebody<>(SB) | |
| TEXT ·IndexByteString(SB),NOSPLIT,$0-32 | |
| MOVD s_base+0(FP), R0 | |
| MOVD s_len+8(FP), R2 | |
| MOVBU c+16(FP), R1 | |
| MOVD $ret+24(FP), R8 | |
| B indexbytebody<>(SB) | |
| // input: | |
| // R0: data | |
| // R1: byte to search | |
| // R2: data len | |
| // R8: address to put result | |
| TEXT indexbytebody<>(SB),NOSPLIT,$0 | |
| // 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 R2, 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 R1, V0.B16 | |
| // Work with aligned 32-byte chunks | |
| BIC $0x1f, R0, R3 | |
| VMOV R5, V5.S4 | |
| ANDS $0x1f, R0, R9 | |
| AND $0x1f, R2, 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, R2, R2 | |
| 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, R2, R2 | |
| 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 | |
| MOVD R0, (R8) | |
| RET | |
| fail: | |
| MOVD $-1, R0 | |
| MOVD R0, (R8) | |
| RET |