1/*
2 * strcpy/stpcpy - copy a string returning pointer to start/end.
3 *
4 * Copyright (c) 2013-2020, Arm Limited.
5 * SPDX-License-Identifier: MIT
6 */
7
8/* Assumptions:
9 *
10 * ARMv8-a, AArch64, unaligned accesses, min page size 4k.
11 */
12
13#include "../asmdefs.h"
14
15/* To build as stpcpy, define BUILD_STPCPY before compiling this file.
16
17   To test the page crossing code path more thoroughly, compile with
18   -DSTRCPY_TEST_PAGE_CROSS - this will force all copies through the slower
19   entry path.  This option is not intended for production use.  */
20
21/* Arguments and results.  */
22#define dstin		x0
23#define srcin		x1
24
25/* Locals and temporaries.  */
26#define src		x2
27#define dst		x3
28#define data1		x4
29#define data1w		w4
30#define data2		x5
31#define data2w		w5
32#define has_nul1	x6
33#define has_nul2	x7
34#define tmp1		x8
35#define tmp2		x9
36#define tmp3		x10
37#define tmp4		x11
38#define zeroones	x12
39#define data1a		x13
40#define data2a		x14
41#define pos		x15
42#define len		x16
43#define to_align	x17
44
45#ifdef BUILD_STPCPY
46#define STRCPY __stpcpy_aarch64
47#else
48#define STRCPY __strcpy_aarch64
49#endif
50
51	/* NUL detection works on the principle that (X - 1) & (~X) & 0x80
52	   (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
53	   can be done in parallel across the entire word.  */
54
55#define REP8_01 0x0101010101010101
56#define REP8_7f 0x7f7f7f7f7f7f7f7f
57#define REP8_80 0x8080808080808080
58
59	/* AArch64 systems have a minimum page size of 4k.  We can do a quick
60	   page size check for crossing this boundary on entry and if we
61	   do not, then we can short-circuit much of the entry code.  We
62	   expect early page-crossing strings to be rare (probability of
63	   16/MIN_PAGE_SIZE ~= 0.4%), so the branch should be quite
64	   predictable, even with random strings.
65
66	   We don't bother checking for larger page sizes, the cost of setting
67	   up the correct page size is just not worth the extra gain from
68	   a small reduction in the cases taking the slow path.  Note that
69	   we only care about whether the first fetch, which may be
70	   misaligned, crosses a page boundary - after that we move to aligned
71	   fetches for the remainder of the string.  */
72
73#ifdef STRCPY_TEST_PAGE_CROSS
74	/* Make everything that isn't Qword aligned look like a page cross.  */
75#define MIN_PAGE_P2 4
76#else
77#define MIN_PAGE_P2 12
78#endif
79
80#define MIN_PAGE_SIZE (1 << MIN_PAGE_P2)
81
82ENTRY (STRCPY)
83	PTR_ARG (0)
84	PTR_ARG (1)
85	/* For moderately short strings, the fastest way to do the copy is to
86	   calculate the length of the string in the same way as strlen, then
87	   essentially do a memcpy of the result.  This avoids the need for
88	   multiple byte copies and further means that by the time we
89	   reach the bulk copy loop we know we can always use DWord
90	   accesses.  We expect __strcpy_aarch64 to rarely be called repeatedly
91	   with the same source string, so branch prediction is likely to
92	   always be difficult - we mitigate against this by preferring
93	   conditional select operations over branches whenever this is
94	   feasible.  */
95	and	tmp2, srcin, #(MIN_PAGE_SIZE - 1)
96	mov	zeroones, #REP8_01
97	and	to_align, srcin, #15
98	cmp	tmp2, #(MIN_PAGE_SIZE - 16)
99	neg	tmp1, to_align
100	/* The first fetch will straddle a (possible) page boundary iff
101	   srcin + 15 causes bit[MIN_PAGE_P2] to change value.  A 16-byte
102	   aligned string will never fail the page align check, so will
103	   always take the fast path.  */
104	b.gt	L(page_cross)
105
106L(page_cross_ok):
107	ldp	data1, data2, [srcin]
108#ifdef __AARCH64EB__
109	/* Because we expect the end to be found within 16 characters
110	   (profiling shows this is the most common case), it's worth
111	   swapping the bytes now to save having to recalculate the
112	   termination syndrome later.  We preserve data1 and data2
113	   so that we can re-use the values later on.  */
114	rev	tmp2, data1
115	sub	tmp1, tmp2, zeroones
116	orr	tmp2, tmp2, #REP8_7f
117	bics	has_nul1, tmp1, tmp2
118	b.ne	L(fp_le8)
119	rev	tmp4, data2
120	sub	tmp3, tmp4, zeroones
121	orr	tmp4, tmp4, #REP8_7f
122#else
123	sub	tmp1, data1, zeroones
124	orr	tmp2, data1, #REP8_7f
125	bics	has_nul1, tmp1, tmp2
126	b.ne	L(fp_le8)
127	sub	tmp3, data2, zeroones
128	orr	tmp4, data2, #REP8_7f
129#endif
130	bics	has_nul2, tmp3, tmp4
131	b.eq	L(bulk_entry)
132
133	/* The string is short (<=16 bytes).  We don't know exactly how
134	   short though, yet.  Work out the exact length so that we can
135	   quickly select the optimal copy strategy.  */
136L(fp_gt8):
137	rev	has_nul2, has_nul2
138	clz	pos, has_nul2
139	mov	tmp2, #56
140	add	dst, dstin, pos, lsr #3		/* Bits to bytes.  */
141	sub	pos, tmp2, pos
142#ifdef __AARCH64EB__
143	lsr	data2, data2, pos
144#else
145	lsl	data2, data2, pos
146#endif
147	str	data2, [dst, #1]
148	str	data1, [dstin]
149#ifdef BUILD_STPCPY
150	add	dstin, dst, #8
151#endif
152	ret
153
154L(fp_le8):
155	rev	has_nul1, has_nul1
156	clz	pos, has_nul1
157	add	dst, dstin, pos, lsr #3		/* Bits to bytes.  */
158	subs	tmp2, pos, #24			/* Pos in bits. */
159	b.lt	L(fp_lt4)
160#ifdef __AARCH64EB__
161	mov	tmp2, #56
162	sub	pos, tmp2, pos
163	lsr	data2, data1, pos
164	lsr	data1, data1, #32
165#else
166	lsr	data2, data1, tmp2
167#endif
168	/* 4->7 bytes to copy.  */
169	str	data2w, [dst, #-3]
170	str	data1w, [dstin]
171#ifdef BUILD_STPCPY
172	mov	dstin, dst
173#endif
174	ret
175L(fp_lt4):
176	cbz	pos, L(fp_lt2)
177	/* 2->3 bytes to copy.  */
178#ifdef __AARCH64EB__
179	lsr	data1, data1, #48
180#endif
181	strh	data1w, [dstin]
182	/* Fall-through, one byte (max) to go.  */
183L(fp_lt2):
184	/* Null-terminated string.  Last character must be zero!  */
185	strb	wzr, [dst]
186#ifdef BUILD_STPCPY
187	mov	dstin, dst
188#endif
189	ret
190
191	.p2align 6
192	/* Aligning here ensures that the entry code and main loop all lies
193	   within one 64-byte cache line.  */
194L(bulk_entry):
195	sub	to_align, to_align, #16
196	stp	data1, data2, [dstin]
197	sub	src, srcin, to_align
198	sub	dst, dstin, to_align
199	b	L(entry_no_page_cross)
200
201	/* The inner loop deals with two Dwords at a time.  This has a
202	   slightly higher start-up cost, but we should win quite quickly,
203	   especially on cores with a high number of issue slots per
204	   cycle, as we get much better parallelism out of the operations.  */
205L(main_loop):
206	stp	data1, data2, [dst], #16
207L(entry_no_page_cross):
208	ldp	data1, data2, [src], #16
209	sub	tmp1, data1, zeroones
210	orr	tmp2, data1, #REP8_7f
211	sub	tmp3, data2, zeroones
212	orr	tmp4, data2, #REP8_7f
213	bic	has_nul1, tmp1, tmp2
214	bics	has_nul2, tmp3, tmp4
215	ccmp	has_nul1, #0, #0, eq	/* NZCV = 0000  */
216	b.eq	L(main_loop)
217
218	/* Since we know we are copying at least 16 bytes, the fastest way
219	   to deal with the tail is to determine the location of the
220	   trailing NUL, then (re)copy the 16 bytes leading up to that.  */
221	cmp	has_nul1, #0
222#ifdef __AARCH64EB__
223	/* For big-endian, carry propagation (if the final byte in the
224	   string is 0x01) means we cannot use has_nul directly.  The
225	   easiest way to get the correct byte is to byte-swap the data
226	   and calculate the syndrome a second time.  */
227	csel	data1, data1, data2, ne
228	rev	data1, data1
229	sub	tmp1, data1, zeroones
230	orr	tmp2, data1, #REP8_7f
231	bic	has_nul1, tmp1, tmp2
232#else
233	csel	has_nul1, has_nul1, has_nul2, ne
234#endif
235	rev	has_nul1, has_nul1
236	clz	pos, has_nul1
237	add	tmp1, pos, #72
238	add	pos, pos, #8
239	csel	pos, pos, tmp1, ne
240	add	src, src, pos, lsr #3
241	add	dst, dst, pos, lsr #3
242	ldp	data1, data2, [src, #-32]
243	stp	data1, data2, [dst, #-16]
244#ifdef BUILD_STPCPY
245	sub	dstin, dst, #1
246#endif
247	ret
248
249L(page_cross):
250	bic	src, srcin, #15
251	/* Start by loading two words at [srcin & ~15], then forcing the
252	   bytes that precede srcin to 0xff.  This means they never look
253	   like termination bytes.  */
254	ldp	data1, data2, [src]
255	lsl	tmp1, tmp1, #3	/* Bytes beyond alignment -> bits.  */
256	tst	to_align, #7
257	csetm	tmp2, ne
258#ifdef __AARCH64EB__
259	lsl	tmp2, tmp2, tmp1	/* Shift (tmp1 & 63).  */
260#else
261	lsr	tmp2, tmp2, tmp1	/* Shift (tmp1 & 63).  */
262#endif
263	orr	data1, data1, tmp2
264	orr	data2a, data2, tmp2
265	cmp	to_align, #8
266	csinv	data1, data1, xzr, lt
267	csel	data2, data2, data2a, lt
268	sub	tmp1, data1, zeroones
269	orr	tmp2, data1, #REP8_7f
270	sub	tmp3, data2, zeroones
271	orr	tmp4, data2, #REP8_7f
272	bic	has_nul1, tmp1, tmp2
273	bics	has_nul2, tmp3, tmp4
274	ccmp	has_nul1, #0, #0, eq	/* NZCV = 0000  */
275	b.eq	L(page_cross_ok)
276	/* We now need to make data1 and data2 look like they've been
277	   loaded directly from srcin.  Do a rotate on the 128-bit value.  */
278	lsl	tmp1, to_align, #3	/* Bytes->bits.  */
279	neg	tmp2, to_align, lsl #3
280#ifdef __AARCH64EB__
281	lsl	data1a, data1, tmp1
282	lsr	tmp4, data2, tmp2
283	lsl	data2, data2, tmp1
284	orr	tmp4, tmp4, data1a
285	cmp	to_align, #8
286	csel	data1, tmp4, data2, lt
287	rev	tmp2, data1
288	rev	tmp4, data2
289	sub	tmp1, tmp2, zeroones
290	orr	tmp2, tmp2, #REP8_7f
291	sub	tmp3, tmp4, zeroones
292	orr	tmp4, tmp4, #REP8_7f
293#else
294	lsr	data1a, data1, tmp1
295	lsl	tmp4, data2, tmp2
296	lsr	data2, data2, tmp1
297	orr	tmp4, tmp4, data1a
298	cmp	to_align, #8
299	csel	data1, tmp4, data2, lt
300	sub	tmp1, data1, zeroones
301	orr	tmp2, data1, #REP8_7f
302	sub	tmp3, data2, zeroones
303	orr	tmp4, data2, #REP8_7f
304#endif
305	bic	has_nul1, tmp1, tmp2
306	cbnz	has_nul1, L(fp_le8)
307	bic	has_nul2, tmp3, tmp4
308	b	L(fp_gt8)
309
310END (STRCPY)
311
312