xref: /linux/arch/arm64/lib/strncmp.S (revision 9cbbd694a58bdf24def2462276514c90cab7cf80)
1/* SPDX-License-Identifier: GPL-2.0-only */
2/*
3 * Copyright (c) 2013-2022, Arm Limited.
4 *
5 * Adapted from the original at:
6 * https://github.com/ARM-software/optimized-routines/blob/189dfefe37d54c5b/string/aarch64/strncmp.S
7 */
8
9#include <linux/linkage.h>
10#include <asm/assembler.h>
11
12/* Assumptions:
13 *
14 * ARMv8-a, AArch64.
15 * MTE compatible.
16 */
17
18#define L(label) .L ## label
19
20#define REP8_01 0x0101010101010101
21#define REP8_7f 0x7f7f7f7f7f7f7f7f
22
23/* Parameters and result.  */
24#define src1		x0
25#define src2		x1
26#define limit		x2
27#define result		x0
28
29/* Internal variables.  */
30#define data1		x3
31#define data1w		w3
32#define data2		x4
33#define data2w		w4
34#define has_nul		x5
35#define diff		x6
36#define syndrome	x7
37#define tmp1		x8
38#define tmp2		x9
39#define tmp3		x10
40#define zeroones	x11
41#define pos		x12
42#define mask		x13
43#define endloop		x14
44#define count		mask
45#define offset		pos
46#define neg_offset	x15
47
48/* Define endian dependent shift operations.
49   On big-endian early bytes are at MSB and on little-endian LSB.
50   LS_FW means shifting towards early bytes.
51   LS_BK means shifting towards later bytes.
52   */
53#ifdef __AARCH64EB__
54#define LS_FW lsl
55#define LS_BK lsr
56#else
57#define LS_FW lsr
58#define LS_BK lsl
59#endif
60
61SYM_FUNC_START(__pi_strncmp)
62	cbz	limit, L(ret0)
63	eor	tmp1, src1, src2
64	mov	zeroones, #REP8_01
65	tst	tmp1, #7
66	and	count, src1, #7
67	b.ne	L(misaligned8)
68	cbnz	count, L(mutual_align)
69
70	/* NUL detection works on the principle that (X - 1) & (~X) & 0x80
71	   (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
72	   can be done in parallel across the entire word.  */
73	.p2align 4
74L(loop_aligned):
75	ldr	data1, [src1], #8
76	ldr	data2, [src2], #8
77L(start_realigned):
78	subs	limit, limit, #8
79	sub	tmp1, data1, zeroones
80	orr	tmp2, data1, #REP8_7f
81	eor	diff, data1, data2	/* Non-zero if differences found.  */
82	csinv	endloop, diff, xzr, hi	/* Last Dword or differences.  */
83	bics	has_nul, tmp1, tmp2	/* Non-zero if NUL terminator.  */
84	ccmp	endloop, #0, #0, eq
85	b.eq	L(loop_aligned)
86	/* End of main loop */
87
88L(full_check):
89#ifndef __AARCH64EB__
90	orr	syndrome, diff, has_nul
91	add	limit, limit, 8	/* Rewind limit to before last subs. */
92L(syndrome_check):
93	/* Limit was reached. Check if the NUL byte or the difference
94	   is before the limit. */
95	rev	syndrome, syndrome
96	rev	data1, data1
97	clz	pos, syndrome
98	rev	data2, data2
99	lsl	data1, data1, pos
100	cmp	limit, pos, lsr #3
101	lsl	data2, data2, pos
102	/* But we need to zero-extend (char is unsigned) the value and then
103	   perform a signed 32-bit subtraction.  */
104	lsr	data1, data1, #56
105	sub	result, data1, data2, lsr #56
106	csel result, result, xzr, hi
107	ret
108#else
109	/* Not reached the limit, must have found the end or a diff.  */
110	tbz	limit, #63, L(not_limit)
111	add	tmp1, limit, 8
112	cbz	limit, L(not_limit)
113
114	lsl	limit, tmp1, #3	/* Bits -> bytes.  */
115	mov	mask, #~0
116	lsr	mask, mask, limit
117	bic	data1, data1, mask
118	bic	data2, data2, mask
119
120	/* Make sure that the NUL byte is marked in the syndrome.  */
121	orr	has_nul, has_nul, mask
122
123L(not_limit):
124	/* For big-endian we cannot use the trick with the syndrome value
125	   as carry-propagation can corrupt the upper bits if the trailing
126	   bytes in the string contain 0x01.  */
127	/* However, if there is no NUL byte in the dword, we can generate
128	   the result directly.  We can't just subtract the bytes as the
129	   MSB might be significant.  */
130	cbnz	has_nul, 1f
131	cmp	data1, data2
132	cset	result, ne
133	cneg	result, result, lo
134	ret
1351:
136	/* Re-compute the NUL-byte detection, using a byte-reversed value.  */
137	rev	tmp3, data1
138	sub	tmp1, tmp3, zeroones
139	orr	tmp2, tmp3, #REP8_7f
140	bic	has_nul, tmp1, tmp2
141	rev	has_nul, has_nul
142	orr	syndrome, diff, has_nul
143	clz	pos, syndrome
144	/* The most-significant-non-zero bit of the syndrome marks either the
145	   first bit that is different, or the top bit of the first zero byte.
146	   Shifting left now will bring the critical information into the
147	   top bits.  */
148L(end_quick):
149	lsl	data1, data1, pos
150	lsl	data2, data2, pos
151	/* But we need to zero-extend (char is unsigned) the value and then
152	   perform a signed 32-bit subtraction.  */
153	lsr	data1, data1, #56
154	sub	result, data1, data2, lsr #56
155	ret
156#endif
157
158L(mutual_align):
159	/* Sources are mutually aligned, but are not currently at an
160	   alignment boundary.  Round down the addresses and then mask off
161	   the bytes that precede the start point.
162	   We also need to adjust the limit calculations, but without
163	   overflowing if the limit is near ULONG_MAX.  */
164	bic	src1, src1, #7
165	bic	src2, src2, #7
166	ldr	data1, [src1], #8
167	neg	tmp3, count, lsl #3	/* 64 - bits(bytes beyond align). */
168	ldr	data2, [src2], #8
169	mov	tmp2, #~0
170	LS_FW	tmp2, tmp2, tmp3	/* Shift (count & 63).  */
171	/* Adjust the limit and ensure it doesn't overflow.  */
172	adds	limit, limit, count
173	csinv	limit, limit, xzr, lo
174	orr	data1, data1, tmp2
175	orr	data2, data2, tmp2
176	b	L(start_realigned)
177
178	.p2align 4
179	/* Don't bother with dwords for up to 16 bytes.  */
180L(misaligned8):
181	cmp	limit, #16
182	b.hs	L(try_misaligned_words)
183
184L(byte_loop):
185	/* Perhaps we can do better than this.  */
186	ldrb	data1w, [src1], #1
187	ldrb	data2w, [src2], #1
188	subs	limit, limit, #1
189	ccmp	data1w, #1, #0, hi	/* NZCV = 0b0000.  */
190	ccmp	data1w, data2w, #0, cs	/* NZCV = 0b0000.  */
191	b.eq	L(byte_loop)
192L(done):
193	sub	result, data1, data2
194	ret
195	/* Align the SRC1 to a dword by doing a bytewise compare and then do
196	   the dword loop.  */
197L(try_misaligned_words):
198	cbz	count, L(src1_aligned)
199
200	neg	count, count
201	and	count, count, #7
202	sub	limit, limit, count
203
204L(page_end_loop):
205	ldrb	data1w, [src1], #1
206	ldrb	data2w, [src2], #1
207	cmp	data1w, #1
208	ccmp	data1w, data2w, #0, cs	/* NZCV = 0b0000.  */
209	b.ne	L(done)
210	subs	count, count, #1
211	b.hi	L(page_end_loop)
212
213	/* The following diagram explains the comparison of misaligned strings.
214	   The bytes are shown in natural order. For little-endian, it is
215	   reversed in the registers. The "x" bytes are before the string.
216	   The "|" separates data that is loaded at one time.
217	   src1     | a a a a a a a a | b b b c c c c c | . . .
218	   src2     | x x x x x a a a   a a a a a b b b | c c c c c . . .
219
220	   After shifting in each step, the data looks like this:
221	                STEP_A              STEP_B              STEP_C
222	   data1    a a a a a a a a     b b b c c c c c     b b b c c c c c
223	   data2    a a a a a a a a     b b b 0 0 0 0 0     0 0 0 c c c c c
224
225	   The bytes with "0" are eliminated from the syndrome via mask.
226
227	   Align SRC2 down to 16 bytes. This way we can read 16 bytes at a
228	   time from SRC2. The comparison happens in 3 steps. After each step
229	   the loop can exit, or read from SRC1 or SRC2. */
230L(src1_aligned):
231	/* Calculate offset from 8 byte alignment to string start in bits. No
232	   need to mask offset since shifts are ignoring upper bits. */
233	lsl	offset, src2, #3
234	bic	src2, src2, #0xf
235	mov	mask, -1
236	neg	neg_offset, offset
237	ldr	data1, [src1], #8
238	ldp	tmp1, tmp2, [src2], #16
239	LS_BK	mask, mask, neg_offset
240	and	neg_offset, neg_offset, #63	/* Need actual value for cmp later. */
241	/* Skip the first compare if data in tmp1 is irrelevant. */
242	tbnz	offset, 6, L(misaligned_mid_loop)
243
244L(loop_misaligned):
245	/* STEP_A: Compare full 8 bytes when there is enough data from SRC2.*/
246	LS_FW	data2, tmp1, offset
247	LS_BK	tmp1, tmp2, neg_offset
248	subs	limit, limit, #8
249	orr	data2, data2, tmp1	/* 8 bytes from SRC2 combined from two regs.*/
250	sub	has_nul, data1, zeroones
251	eor	diff, data1, data2	/* Non-zero if differences found.  */
252	orr	tmp3, data1, #REP8_7f
253	csinv	endloop, diff, xzr, hi	/* If limit, set to all ones. */
254	bic	has_nul, has_nul, tmp3	/* Non-zero if NUL byte found in SRC1. */
255	orr	tmp3, endloop, has_nul
256	cbnz	tmp3, L(full_check)
257
258	ldr	data1, [src1], #8
259L(misaligned_mid_loop):
260	/* STEP_B: Compare first part of data1 to second part of tmp2. */
261	LS_FW	data2, tmp2, offset
262#ifdef __AARCH64EB__
263	/* For big-endian we do a byte reverse to avoid carry-propagation
264	problem described above. This way we can reuse the has_nul in the
265	next step and also use syndrome value trick at the end. */
266	rev	tmp3, data1
267	#define data1_fixed tmp3
268#else
269	#define data1_fixed data1
270#endif
271	sub	has_nul, data1_fixed, zeroones
272	orr	tmp3, data1_fixed, #REP8_7f
273	eor	diff, data2, data1	/* Non-zero if differences found.  */
274	bic	has_nul, has_nul, tmp3	/* Non-zero if NUL terminator.  */
275#ifdef __AARCH64EB__
276	rev	has_nul, has_nul
277#endif
278	cmp	limit, neg_offset, lsr #3
279	orr	syndrome, diff, has_nul
280	bic	syndrome, syndrome, mask	/* Ignore later bytes. */
281	csinv	tmp3, syndrome, xzr, hi	/* If limit, set to all ones. */
282	cbnz	tmp3, L(syndrome_check)
283
284	/* STEP_C: Compare second part of data1 to first part of tmp1. */
285	ldp	tmp1, tmp2, [src2], #16
286	cmp	limit, #8
287	LS_BK	data2, tmp1, neg_offset
288	eor	diff, data2, data1	/* Non-zero if differences found.  */
289	orr	syndrome, diff, has_nul
290	and	syndrome, syndrome, mask	/* Ignore earlier bytes. */
291	csinv	tmp3, syndrome, xzr, hi	/* If limit, set to all ones. */
292	cbnz	tmp3, L(syndrome_check)
293
294	ldr	data1, [src1], #8
295	sub	limit, limit, #8
296	b	L(loop_misaligned)
297
298#ifdef	__AARCH64EB__
299L(syndrome_check):
300	clz	pos, syndrome
301	cmp	pos, limit, lsl #3
302	b.lo	L(end_quick)
303#endif
304
305L(ret0):
306	mov	result, #0
307	ret
308SYM_FUNC_END(__pi_strncmp)
309SYM_FUNC_ALIAS_WEAK(strncmp, __pi_strncmp)
310EXPORT_SYMBOL_NOKASAN(strncmp)
311