| // 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: |
| // We load chunks of data, 16 bytes at a time. |
| // We compare them with the target byte using |
| // a vector comparison. The vector comparison |
| // generates byte mask outputs. We convert the byte |
| // mask to a nibble mask and move it to an int register. |
| // The lowest bit index / 4 is the matching lane. |
| // |
| // An example (using 8 byte vectors for clarity - |
| // the real code uses 16 byte vectors): |
| // |
| // target: [92 92 92 92 92 92 92 92] repeat of input byte |
| // data: [3a 92 3c 47 21 03 92 b9] loaded from input string |
| // equalMask: [00 ff 00 00 00 00 ff 00] comparison (VCMEQ) |
| // nibbleMask: [f0 00 00 0f .. .. .. ..] narrow to nibbles (VSHRN $4) |
| // register: 0x0f0000f0 move to int register |
| // idx: 1 lowest set bit / 4 |
| // |
| // If there is any match, the int register is nonzero and |
| // we can read the match index off from it. Otherwise, there |
| // is no match in those 16 bytes. |
| // |
| // For the small-input cases (<16 bytes), we have to be careful |
| // not to read outside 16-byte aligned chunks because of MTE. |
| // We use some additional masking to extract only matches that |
| // are valid for the input data. |
| |
| #define PTR R0 |
| #define LEN R1 |
| #define TARGET R2 |
| #define BASE R3 |
| #define MASK R4 |
| #define VTARGET V0.B16 |
| |
| // Length 0, nothing to do. |
| CBZ LEN, fail |
| |
| // Make vector containing the byte we're searching for in each lane. |
| VMOV TARGET, VTARGET // [c c c ... c c c] |
| |
| // Small, need to be extra careful about out of bounds. |
| CMP $16, LEN |
| BLT small |
| |
| // Save original location (for computing result). |
| MOVD PTR, BASE |
| |
| // Check low bits of length. |
| AND $0xf, LEN, R9 |
| CBZ R9, multipleOf16 |
| |
| // Length is not a multiple of 16. |
| // Check 16 bytes, but then advance less to make length aligned. |
| VLD1 (PTR), [V2.B16] // load data |
| VCMEQ VTARGET, V2.B16, V2.B16 // compare each byte against the target byte |
| VSHRN $4, V2.H8, V2.B8 // compact to one nibble per byte |
| VMOV V2.D[0], MASK // move to general purpose register |
| CBNZ MASK, foundStart |
| ADD R9, PTR |
| SUB R9, LEN |
| |
| // Length is a nonzero multiple of 16. |
| multipleOf16: |
| TBZ $4, LEN, multipleOf32 |
| VLD1.P (PTR), [V2.B16] |
| SUB $16, LEN |
| VCMEQ VTARGET, V2.B16, V2.B16 |
| VSHRN $4, V2.H8, V2.B8 |
| VMOV V2.D[0], MASK |
| CBNZ MASK, found16 |
| CBZ LEN, fail |
| |
| // Length is a nonzero multiple of 32. |
| multipleOf32: |
| TBZ $5, LEN, multipleOf64 |
| VLD1.P (PTR), [V2.B16, V3.B16] // load data, PTR += 32 |
| SUB $32, LEN |
| VCMEQ VTARGET, V2.B16, V2.B16 |
| VCMEQ VTARGET, V3.B16, V3.B16 |
| VSHRN $4, V2.H8, V2.B8 |
| VSHRN $4, V3.H8, V3.B8 |
| VMOV V2.D[0], MASK |
| CBNZ MASK, found32 |
| VMOV V3.D[0], MASK |
| CBNZ MASK, found16 |
| CBZ LEN, fail |
| |
| // Length is a nonzero multiple of 64. |
| multipleOf64: |
| VLD1.P (PTR), [V2.B16, V3.B16, V4.B16, V5.B16] // load data, PTR += 64 |
| SUB $64, LEN |
| VCMEQ VTARGET, V2.B16, V2.B16 |
| VCMEQ VTARGET, V3.B16, V3.B16 |
| VCMEQ VTARGET, V4.B16, V4.B16 |
| VCMEQ VTARGET, V5.B16, V5.B16 |
| VORR V2.B16, V3.B16, V10.B16 |
| VORR V4.B16, V5.B16, V11.B16 |
| VORR V10.B16, V11.B16, V10.B16 |
| VADDP V10.D2, V10.D2, V10.D2 |
| VMOV V10.D[0], R10 |
| CBNZ R10, found64 // at least one lane matched |
| CBNZ LEN, multipleOf64 |
| |
| fail: |
| MOVD $-1, R0 |
| RET |
| |
| foundStart: |
| RBIT MASK, MASK |
| CLZ MASK, R9 // count trailing zeros |
| LSR $2, R9, R0 // divide by 4 |
| RET |
| |
| found16: |
| SUB $16, PTR // undo .P |
| |
| // On entry to found0, MASK contains a nonzero nibble bitmask |
| // of matches starting at PTR. |
| found0: |
| SUB BASE, PTR // convert pointer to offset |
| RBIT MASK, MASK |
| CLZ MASK, R9 // count trailing zeros |
| ADD R9>>2, PTR, R0 // add nibble index to offset |
| RET |
| |
| found32: |
| SUB $32, PTR // undo .P |
| B found0 |
| |
| found64: |
| SUB $64, PTR // undo .P |
| VSHRN $4, V2.H8, V2.B8 |
| VMOV V2.D[0], MASK |
| CBNZ MASK, found0 |
| ADD $16, PTR // redo 1/4 of .P |
| VSHRN $4, V3.H8, V3.B8 |
| VMOV V3.D[0], MASK |
| CBNZ MASK, found0 |
| ADD $16, PTR // redo 1/4 of .P |
| VSHRN $4, V4.H8, V4.B8 |
| VMOV V4.D[0], MASK |
| CBNZ MASK, found0 |
| ADD $16, PTR // redo 1/4 of .P |
| VSHRN $4, V5.H8, V5.B8 |
| VMOV V5.D[0], MASK |
| B found0 |
| |
| // 1-15 bytes |
| PCALIGN $16 |
| small: |
| AND $0xf, PTR, R8 // R8 = offset of start in 16-byte region |
| ADD R8, LEN, R9 // R9 = offset of end (from start's 16-byte region boundary) |
| MOVD $0, R10 // R10 = low bits of match data to throw away |
| CMP $16, R9 |
| BGT noAdjust // straddles two 16-byte regions - safe to load directly |
| |
| // data is all within a single 16-byte region |
| BIC $0xf, PTR, PTR // round down to start of 16-byte region |
| LSL $2, R8, R10 // throw away the match bits below original start |
| |
| noAdjust: |
| VLD1 (PTR), [V2.B16] |
| VCMEQ VTARGET, V2.B16, V2.B16 |
| VSHRN $4, V2.H8, V2.B8 // compact to one nibble per byte |
| VMOV V2.D[0], MASK // move to general purpose register |
| LSR R10, MASK, MASK // discard matches before string start |
| RBIT MASK, MASK |
| CLZ MASK, R9 |
| LSR $2, R9, R9 |
| CMP LEN, R9 |
| CSINV LT, R9, ZR, R0 // if first match past end of string, set return value to -1 |
| RET |
