[PATCH v2] aarch64: add optimised strspn/strcspn

[remph]

Wilco: thanks for the feedback; here's an implementation with a bit array
and 2-register TBL.  This version is much smaller, since there should be
no need for different loops if 2-register TBL is generally fast enough,
which means a faster init time.  Speed is comparable to the best case of
my previous version, and there is no worst case.

---8<---

Requires Neon (aka. Advanced SIMD).  Looks up 16 characters at a time,
for a 2-3x perfomance improvement, and a ~30% speedup on the strtok &
strsep benchtests, as tested on Cortex A-{53,72}.

Signed-off-by: remph <lhr@disroot.org>
---
 sysdeps/aarch64/strcspn.S |   2 +
 sysdeps/aarch64/strspn.S  | 141 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 143 insertions(+)
 create mode 100644 sysdeps/aarch64/strcspn.S
 create mode 100644 sysdeps/aarch64/strspn.S

diff --git a/sysdeps/aarch64/strcspn.S b/sysdeps/aarch64/strcspn.S
new file mode 100644
index 00000000..f2a69e98
--- /dev/null
+++ b/sysdeps/aarch64/strcspn.S
@@ -0,0 +1,2 @@
+#define USE_AS_STRCSPN 1
+#include "strspn.S"
diff --git a/sysdeps/aarch64/strspn.S b/sysdeps/aarch64/strspn.S
new file mode 100644
index 00000000..514c0d69
--- /dev/null
+++ b/sysdeps/aarch64/strspn.S
@@ -0,0 +1,141 @@
+/* Copyright (C) 2025 Free Software Foundation, Inc.
+
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library.  If not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <sysdep.h>
+
+#ifdef USE_AS_STRCSPN
+# define STRSPN strcspn
+# define SBT orr	/* SBT -- `set bit' */
+#else
+# define STRSPN strspn
+# define SBT bic
+#endif
+
+#ifdef __AARCH64EB__
+# define LS_FW lsl
+#else
+# define LS_FW lsr
+#endif
+
+#define og_s	x0
+#define set	x1	/* ACCEPT for strspn, REJECT for strcspn */
+
+#define byte_i	x3
+#define bits_i	x4
+#define one	x6
+
+#define save_off	x4
+#define off		x5
+#define syndrome	x5
+#define s		x6
+
+#define vbyte_i	v1.16b
+#define	vbits_i	v2.16b
+#define table	v4.16b-v5.16b
+#define table_a	v4.16b
+#define table_b	v5.16b
+#define sevens	v7.16b
+
+ENTRY(STRSPN)
+	ldrb	w2, [set]
+	cbz	w2, L(early)
+#ifdef USE_AS_STRCSPN
+	ldrb	w3, [set, 1]
+	cbz	w3, L(early)
+#endif
+	/* Table has ones for bytes to reject and zeros for bytes to accept */
+#ifdef USE_AS_STRCSPN
+	stp	xzr, xzr, [sp, -16]
+	stp	xzr, xzr, [sp, -32]!
+#else
+	mvni	v0.4s, 0
+	stp	q0, q0, [sp, -32]!
+#endif
+
+	mov	one, 1
+	.balign 32,,16
+L(fill_table):
+#ifdef USE_AS_STRCSPN
+	ldrb	w2, [set], 1
+#endif
+	lsr	byte_i, x2, 6	/* x2 / 64 */
+	lsl	bits_i, one, x2	/* x2 % 64 implicitly */
+	ldr	x5, [sp, byte_i, lsl 3]
+	SBT	x5, x5, bits_i
+	str	x5, [sp, byte_i, lsl 3]
+#ifndef USE_AS_STRCSPN
+	ldrb	w2, [set, 1]!
+#endif
+	cbnz	w2, L(fill_table)
+
+	ld1	{table}, [sp], 32
+	ubfiz	off, og_s, 2, 4	/* Bottom 4 bits, times 4 to count nibbles */
+	and	s, og_s, -16	/* Round S down to 16-byte boundary */
+	movi	sevens, 7
+#ifdef __AARCH64EB__
+	rev64	table_a, table_a
+	rev64	table_b, table_b
+#endif
+
+	.balign 64,,16
+L(loop):
+	ldr	q0, [s], 16
+	mov	save_off, off	/* OFF and SYNDROME overlap */
+	ushr	vbyte_i, v0.16b, 3
+	bic	vbits_i, sevens, v0.16b
+	tbl	v0.16b, {table}, vbyte_i
+	/* Bring the relevant bit to the MSB of each byte */
+	sshl	v0.16b, v0.16b, vbits_i
+	/* Set every bit of each byte to its MSB */
+	cmlt	v0.16b, v0.16b, 0
+	/* Bytes->nibbles */
+	shrn	v0.8b, v0.8h, 4
+	fmov	x2, d0
+	LS_FW	syndrome, x2, syndrome
+	cbz	syndrome, L(loop)
+
+#ifndef __AARCH64EB__
+	rbit	syndrome, syndrome
+#endif
+	sub	s, s, 16
+	sub	x0, s, og_s
+	clz	syndrome, syndrome
+	add	x0, x0, save_off, lsr 2
+	add	x0, x0, syndrome, lsr 2
+	ret
+
+L(early):
+#ifdef USE_AS_STRCSPN
+	/* strlen(set) < 2: call strchrnul(s, *set) and get its offset from S */
+	stp	fp, lr, [sp, -64]!
+	str	x19, [sp, 32]
+	mov	w1, w2
+	mov	fp, sp
+	mov	x19, x0
+	bl	strchrnul
+	sub	x0, x0, x19
+	ldr	x19, [sp, 32]
+	ldp	fp, lr, [sp], 64
+#else
+	mov	w0, 0
+#endif
+	ret
+END(STRSPN)
+
+#undef set
+libc_hidden_def(STRSPN)
-- 
2.50.1