1/* Optimized strlen implementation using SIMD.
2 Copyright (C) 2018-2022 Free Software Foundation, Inc.
3
4 This file is part of the GNU C Library.
5
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
10
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library. If not, see
18 <https://www.gnu.org/licenses/>. */
19
20#include <sysdep.h>
21
22/* Assumptions:
23 *
24 * ARMv8-a, AArch64, Advanced SIMD, unaligned accesses.
25 * Not MTE compatible.
26 */
27
28#define srcin x0
29#define len x0
30
31#define src x1
32#define data1 x2
33#define data2 x3
34#define has_nul1 x4
35#define has_nul2 x5
36#define tmp1 x4
37#define tmp2 x5
38#define tmp3 x6
39#define tmp4 x7
40#define zeroones x8
41
42#define maskv v0
43#define maskd d0
44#define dataq1 q1
45#define dataq2 q2
46#define datav1 v1
47#define datav2 v2
48#define tmp x2
49#define tmpw w2
50#define synd x3
51#define shift x4
52
53/* For the first 32 bytes, NUL detection works on the principle that
54 (X - 1) & (~X) & 0x80 (=> (X - 1) & ~(X | 0x7f)) is non-zero if a
55 byte is zero, and can be done in parallel across the entire word. */
56
57#define REP8_01 0x0101010101010101
58#define REP8_7f 0x7f7f7f7f7f7f7f7f
59
60/* To test the page crossing code path more thoroughly, compile with
61 -DTEST_PAGE_CROSS - this will force all calls through the slower
62 entry path. This option is not intended for production use. */
63
64#ifdef TEST_PAGE_CROSS
65# define MIN_PAGE_SIZE 32
66#else
67# define MIN_PAGE_SIZE 4096
68#endif
69
70/* Core algorithm:
71
72 Since strings are short on average, we check the first 32 bytes of the
73 string for a NUL character without aligning the string. In order to use
74 unaligned loads safely we must do a page cross check first.
75
76 If there is a NUL byte we calculate the length from the 2 8-byte words
77 using conditional select to reduce branch mispredictions (it is unlikely
78 strlen will be repeatedly called on strings with the same length).
79
80 If the string is longer than 32 bytes, align src so we don't need further
81 page cross checks, and process 32 bytes per iteration using a fast SIMD
82 loop.
83
84 If the page cross check fails, we read 32 bytes from an aligned address,
85 and ignore any characters before the string. If it contains a NUL
86 character, return the length, if not, continue in the main loop. */
87
88ENTRY (__strlen_asimd)
89 PTR_ARG (0)
90
91 and tmp1, srcin, MIN_PAGE_SIZE - 1
92 cmp tmp1, MIN_PAGE_SIZE - 32
93 b.hi L(page_cross)
94
95 /* Look for a NUL byte in the first 16 bytes. */
96 ldp data1, data2, [srcin]
97 mov zeroones, REP8_01
98
99#ifdef __AARCH64EB__
100 /* For big-endian, carry propagation (if the final byte in the
101 string is 0x01) means we cannot use has_nul1/2 directly.
102 Since we expect strings to be small and early-exit,
103 byte-swap the data now so has_null1/2 will be correct. */
104 rev data1, data1
105 rev data2, data2
106#endif
107 sub tmp1, data1, zeroones
108 orr tmp2, data1, REP8_7f
109 sub tmp3, data2, zeroones
110 orr tmp4, data2, REP8_7f
111 bics has_nul1, tmp1, tmp2
112 bic has_nul2, tmp3, tmp4
113 ccmp has_nul2, 0, 0, eq
114 b.eq L(bytes16_31)
115
116 /* Find the exact offset of the first NUL byte in the first 16 bytes
117 from the string start. Enter with C = has_nul1 == 0. */
118 csel has_nul1, has_nul1, has_nul2, cc
119 mov len, 8
120 rev has_nul1, has_nul1
121 csel len, xzr, len, cc
122 clz tmp1, has_nul1
123 add len, len, tmp1, lsr 3
124 ret
125
126 .p2align 3
127 /* Look for a NUL byte at offset 16..31 in the string. */
128L(bytes16_31):
129 ldp data1, data2, [srcin, 16]
130#ifdef __AARCH64EB__
131 rev data1, data1
132 rev data2, data2
133#endif
134 sub tmp1, data1, zeroones
135 orr tmp2, data1, REP8_7f
136 sub tmp3, data2, zeroones
137 orr tmp4, data2, REP8_7f
138 bics has_nul1, tmp1, tmp2
139 bic has_nul2, tmp3, tmp4
140 ccmp has_nul2, 0, 0, eq
141 b.eq L(loop_entry)
142
143 /* Find the exact offset of the first NUL byte at offset 16..31 from
144 the string start. Enter with C = has_nul1 == 0. */
145 csel has_nul1, has_nul1, has_nul2, cc
146 mov len, 24
147 rev has_nul1, has_nul1
148 mov tmp3, 16
149 clz tmp1, has_nul1
150 csel len, tmp3, len, cc
151 add len, len, tmp1, lsr 3
152 ret
153
154L(loop_entry):
155 bic src, srcin, 31
156
157 .p2align 5
158L(loop):
159 ldp dataq1, dataq2, [src, 32]!
160 uminp maskv.16b, datav1.16b, datav2.16b
161 uminp maskv.16b, maskv.16b, maskv.16b
162 cmeq maskv.8b, maskv.8b, 0
163 fmov synd, maskd
164 cbz synd, L(loop)
165
166 /* Low 32 bits of synd are non-zero if a NUL was found in datav1. */
167 cmeq maskv.16b, datav1.16b, 0
168 sub len, src, srcin
169 tst synd, 0xffffffff
170 b.ne 1f
171 cmeq maskv.16b, datav2.16b, 0
172 add len, len, 16
1731:
174 /* Generate a bitmask and compute correct byte offset. */
175#ifdef __AARCH64EB__
176 bic maskv.8h, 0xf0
177#else
178 bic maskv.8h, 0x0f, lsl 8
179#endif
180 umaxp maskv.16b, maskv.16b, maskv.16b
181 fmov synd, maskd
182#ifndef __AARCH64EB__
183 rbit synd, synd
184#endif
185 clz tmp, synd
186 add len, len, tmp, lsr 2
187 ret
188
189 .p2align 4
190
191L(page_cross):
192 bic src, srcin, 31
193 mov tmpw, 0x0c03
194 movk tmpw, 0xc030, lsl 16
195 ld1 {datav1.16b, datav2.16b}, [src]
196 dup maskv.4s, tmpw
197 cmeq datav1.16b, datav1.16b, 0
198 cmeq datav2.16b, datav2.16b, 0
199 and datav1.16b, datav1.16b, maskv.16b
200 and datav2.16b, datav2.16b, maskv.16b
201 addp maskv.16b, datav1.16b, datav2.16b
202 addp maskv.16b, maskv.16b, maskv.16b
203 fmov synd, maskd
204 lsl shift, srcin, 1
205 lsr synd, synd, shift
206 cbz synd, L(loop)
207
208 rbit synd, synd
209 clz len, synd
210 lsr len, len, 1
211 ret
212
213END (__strlen_asimd)
214libc_hidden_builtin_def (__strlen_asimd)
215

source code of glibc/sysdeps/aarch64/multiarch/strlen_asimd.S