1/*
2 * memchr - find a character in a memory zone
3 *
4 * Copyright (c) 2014-2022, Arm Limited.
5 * SPDX-License-Identifier: MIT OR Apache-2.0 WITH LLVM-exception
6 */
7
8/* Assumptions:
9 *
10 * ARMv8-a, AArch64
11 * Neon Available.
12 */
13
14#include "asmdefs.h"
15
16/* Arguments and results.  */
17#define srcin		x0
18#define chrin		w1
19#define cntin		x2
20
21#define result		x0
22
23#define src		x3
24#define	tmp		x4
25#define wtmp2		w5
26#define synd		x6
27#define soff		x9
28#define cntrem		x10
29
30#define vrepchr		v0
31#define vdata1		v1
32#define vdata2		v2
33#define vhas_chr1	v3
34#define vhas_chr2	v4
35#define vrepmask	v5
36#define vend		v6
37
38/*
39 * Core algorithm:
40 *
41 * For each 32-byte chunk we calculate a 64-bit syndrome value, with two bits
42 * per byte. For each tuple, bit 0 is set if the relevant byte matched the
43 * requested character and bit 1 is not used (faster than using a 32bit
44 * syndrome). Since the bits in the syndrome reflect exactly the order in which
45 * things occur in the original string, counting trailing zeros allows to
46 * identify exactly which byte has matched.
47 */
48
49ENTRY (__memchr_aarch64)
50	PTR_ARG (0)
51	SIZE_ARG (2)
52	/* Do not dereference srcin if no bytes to compare.  */
53	cbz	cntin, L(zero_length)
54	/*
55	 * Magic constant 0x40100401 allows us to identify which lane matches
56	 * the requested byte.
57	 */
58	mov	wtmp2, #0x0401
59	movk	wtmp2, #0x4010, lsl #16
60	dup	vrepchr.16b, chrin
61	/* Work with aligned 32-byte chunks */
62	bic	src, srcin, #31
63	dup	vrepmask.4s, wtmp2
64	ands	soff, srcin, #31
65	and	cntrem, cntin, #31
66	b.eq	L(loop)
67
68	/*
69	 * Input string is not 32-byte aligned. We calculate the syndrome
70	 * value for the aligned 32 bytes block containing the first bytes
71	 * and mask the irrelevant part.
72	 */
73
74	ld1	{vdata1.16b, vdata2.16b}, [src], #32
75	sub	tmp, soff, #32
76	adds	cntin, cntin, tmp
77	cmeq	vhas_chr1.16b, vdata1.16b, vrepchr.16b
78	cmeq	vhas_chr2.16b, vdata2.16b, vrepchr.16b
79	and	vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b
80	and	vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b
81	addp	vend.16b, vhas_chr1.16b, vhas_chr2.16b		/* 256->128 */
82	addp	vend.16b, vend.16b, vend.16b			/* 128->64 */
83	mov	synd, vend.d[0]
84	/* Clear the soff*2 lower bits */
85	lsl	tmp, soff, #1
86	lsr	synd, synd, tmp
87	lsl	synd, synd, tmp
88	/* The first block can also be the last */
89	b.ls	L(masklast)
90	/* Have we found something already? */
91	cbnz	synd, L(tail)
92
93L(loop):
94	ld1	{vdata1.16b, vdata2.16b}, [src], #32
95	subs	cntin, cntin, #32
96	cmeq	vhas_chr1.16b, vdata1.16b, vrepchr.16b
97	cmeq	vhas_chr2.16b, vdata2.16b, vrepchr.16b
98	/* If we're out of data we finish regardless of the result */
99	b.ls	L(end)
100	/* Use a fast check for the termination condition */
101	orr	vend.16b, vhas_chr1.16b, vhas_chr2.16b
102	addp	vend.2d, vend.2d, vend.2d
103	mov	synd, vend.d[0]
104	/* We're not out of data, loop if we haven't found the character */
105	cbz	synd, L(loop)
106
107L(end):
108	/* Termination condition found, let's calculate the syndrome value */
109	and	vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b
110	and	vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b
111	addp	vend.16b, vhas_chr1.16b, vhas_chr2.16b		/* 256->128 */
112	addp	vend.16b, vend.16b, vend.16b			/* 128->64 */
113	mov	synd, vend.d[0]
114	/* Only do the clear for the last possible block */
115	b.hs	L(tail)
116
117L(masklast):
118	/* Clear the (32 - ((cntrem + soff) % 32)) * 2 upper bits */
119	add	tmp, cntrem, soff
120	and	tmp, tmp, #31
121	sub	tmp, tmp, #32
122	neg	tmp, tmp, lsl #1
123	lsl	synd, synd, tmp
124	lsr	synd, synd, tmp
125
126L(tail):
127	/* Count the trailing zeros using bit reversing */
128	rbit	synd, synd
129	/* Compensate the last post-increment */
130	sub	src, src, #32
131	/* Check that we have found a character */
132	cmp	synd, #0
133	/* And count the leading zeros */
134	clz	synd, synd
135	/* Compute the potential result */
136	add	result, src, synd, lsr #1
137	/* Select result or NULL */
138	csel	result, xzr, result, eq
139	ret
140
141L(zero_length):
142	mov	result, #0
143	ret
144
145END (__memchr_aarch64)
146
147