1// Copyright 2019 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#include "go_asm.h"
6#include "textflag.h"
7
8TEXT ·IndexByte<ABIInternal>(SB),NOSPLIT,$0-40
9 // X10 = b_base
10 // X11 = b_len
11 // X12 = b_cap (unused)
12 // X13 = byte to find
13 AND $0xff, X13, X12 // x12 byte to look for
14 MOV X10, X13 // store base for later
15
16 SLTI $24, X11, X14
17 ADD X10, X11 // end
18 BEQZ X14, bigBody
19
20 SUB $1, X10
21loop:
22 ADD $1, X10
23 BEQ X10, X11, notfound
24 MOVBU (X10), X14
25 BNE X12, X14, loop
26
27 SUB X13, X10 // remove base
28 RET
29
30notfound:
31 MOV $-1, X10
32 RET
33
34bigBody:
35 JMP indexByteBig<>(SB)
36
37TEXT ·IndexByteString<ABIInternal>(SB),NOSPLIT,$0-32
38 // X10 = b_base
39 // X11 = b_len
40 // X12 = byte to find
41
42 AND $0xff, X12 // x12 byte to look for
43 MOV X10, X13 // store base for later
44
45 SLTI $24, X11, X14
46 ADD X10, X11 // end
47 BEQZ X14, bigBody
48
49 SUB $1, X10
50loop:
51 ADD $1, X10
52 BEQ X10, X11, notfound
53 MOVBU (X10), X14
54 BNE X12, X14, loop
55
56 SUB X13, X10 // remove base
57 RET
58
59notfound:
60 MOV $-1, X10
61 RET
62
63bigBody:
64 JMP indexByteBig<>(SB)
65
66TEXT indexByteBig<>(SB),NOSPLIT|NOFRAME,$0
67 // On entry
68 // X10 = b_base
69 // X11 = end
70 // X12 = byte to find
71 // X13 = b_base
72 // X11 is at least 16 bytes > X10
73
74 // On exit
75 // X10 = index of first instance of sought byte, if found, or -1 otherwise
76
77 // Process the first few bytes until we get to an 8 byte boundary
78 // No need to check for end here as we have at least 16 bytes in
79 // the buffer.
80
81unalignedloop:
82 AND $7, X10, X14
83 BEQZ X14, aligned
84 MOVBU (X10), X14
85 BEQ X12, X14, found
86 ADD $1, X10
87 JMP unalignedloop
88
89aligned:
90 AND $~7, X11, X15 // X15 = end of aligned data
91
92 // We have at least 9 bytes left
93
94 // Use 'Determine if a word has a byte equal to n' bit hack from
95 // https://graphics.stanford.edu/~seander/bithacks.html to determine
96 // whether the byte is present somewhere in the next 8 bytes of the
97 // array.
98
99 MOV $0x0101010101010101, X16
100 SLLI $7, X16, X17 // X17 = 0x8080808080808080
101
102 MUL X12, X16, X18 // broadcast X12 to every byte in X18
103
104alignedloop:
105 MOV (X10), X14
106 XOR X14, X18, X19
107
108 // If the LSB in X12 is present somewhere in the 8 bytes we've just
109 // loaded into X14 then at least one of the bytes in X19 will be 0
110 // after the XOR. If any of the bytes in X19 are zero then
111 //
112 // ((X19 - X16) & (~X19) & X17)
113 //
114 // will be non-zero. The expression will evaluate to zero if none of
115 // the bytes in X19 are zero, i.e., X12 is not present in X14.
116
117 SUB X16, X19, X20
118 ANDN X19, X17, X21
119 AND X20, X21
120 BNEZ X21, tailloop // If X21 != 0 X12 is present in X14
121 ADD $8, X10
122 BNE X10, X15, alignedloop
123
124tailloop:
125 SUB $1, X10
126
127loop:
128 ADD $1, X10
129 BEQ X10, X11, notfound
130 MOVBU (X10), X14
131 BNE X12, X14, loop
132
133found:
134 SUB X13, X10 // remove base
135 RET
136
137notfound:
138 MOV $-1, X10
139 RET
View as plain text