1/* Copyright (c) 2012, Linaro Limited
2   All rights reserved.
3
4   Redistribution and use in source and binary forms, with or without
5   modification, are permitted provided that the following conditions are met:
6       * Redistributions of source code must retain the above copyright
7         notice, this list of conditions and the following disclaimer.
8       * Redistributions in binary form must reproduce the above copyright
9         notice, this list of conditions and the following disclaimer in the
10         documentation and/or other materials provided with the distribution.
11       * Neither the name of the Linaro nor the
12         names of its contributors may be used to endorse or promote products
13         derived from this software without specific prior written permission.
14
15   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19   HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28/* Assumptions:
29 *
30 * ARMv8-a, AArch64
31 */
32
33#include <private/bionic_asm.h>
34
35#define REP8_01 0x0101010101010101
36#define REP8_7f 0x7f7f7f7f7f7f7f7f
37#define REP8_80 0x8080808080808080
38
39/* Parameters and result.  */
40#define src1		x0
41#define src2		x1
42#define result		x0
43
44/* Internal variables.  */
45#define data1		x2
46#define data1w		w2
47#define data2		x3
48#define data2w		w3
49#define has_nul		x4
50#define diff		x5
51#define syndrome	x6
52#define tmp1		x7
53#define tmp2		x8
54#define tmp3		x9
55#define zeroones	x10
56#define pos		x11
57
58	/* Start of performance-critical section  -- one 64B cache line.  */
59ENTRY(strcmp)
60	eor	tmp1, src1, src2
61	mov	zeroones, #REP8_01
62	tst	tmp1, #7
63	b.ne	.Lmisaligned8
64	ands	tmp1, src1, #7
65	b.ne	.Lmutual_align
66	/* NUL detection works on the principle that (X - 1) & (~X) & 0x80
67	   (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
68	   can be done in parallel across the entire word.  */
69.Lloop_aligned:
70	ldr	data1, [src1], #8
71	ldr	data2, [src2], #8
72.Lstart_realigned:
73	sub	tmp1, data1, zeroones
74	orr	tmp2, data1, #REP8_7f
75	eor	diff, data1, data2	/* Non-zero if differences found.  */
76	bic	has_nul, tmp1, tmp2	/* Non-zero if NUL terminator.  */
77	orr	syndrome, diff, has_nul
78	cbz	syndrome, .Lloop_aligned
79	/* End of performance-critical section  -- one 64B cache line.  */
80
81#ifndef	__AARCH64EB__
82	rev	syndrome, syndrome
83	rev	data1, data1
84	/* The MS-non-zero bit of the syndrome marks either the first bit
85	   that is different, or the top bit of the first zero byte.
86	   Shifting left now will bring the critical information into the
87	   top bits.  */
88	clz	pos, syndrome
89	rev	data2, data2
90	lsl	data1, data1, pos
91	lsl	data2, data2, pos
92	/* But we need to zero-extend (char is unsigned) the value and then
93	   perform a signed 32-bit subtraction.  */
94	lsr	data1, data1, #56
95	sub	result, data1, data2, lsr #56
96	ret
97#else
98	/* For big-endian we cannot use the trick with the syndrome value
99	   as carry-propagation can corrupt the upper bits if the trailing
100	   bytes in the string contain 0x01.  */
101	/* However, if there is no NUL byte in the dword, we can generate
102	   the result directly.  We can't just subtract the bytes as the
103	   MSB might be significant.  */
104	cbnz	has_nul, 1f
105	cmp	data1, data2
106	cset	result, ne
107	cneg	result, result, lo
108	ret
1091:
110	/* Re-compute the NUL-byte detection, using a byte-reversed value.  */
111	rev	tmp3, data1
112	sub	tmp1, tmp3, zeroones
113	orr	tmp2, tmp3, #REP8_7f
114	bic	has_nul, tmp1, tmp2
115	rev	has_nul, has_nul
116	orr	syndrome, diff, has_nul
117	clz	pos, syndrome
118	/* The MS-non-zero bit of the syndrome marks either the first bit
119	   that is different, or the top bit of the first zero byte.
120	   Shifting left now will bring the critical information into the
121	   top bits.  */
122	lsl	data1, data1, pos
123	lsl	data2, data2, pos
124	/* But we need to zero-extend (char is unsigned) the value and then
125	   perform a signed 32-bit subtraction.  */
126	lsr	data1, data1, #56
127	sub	result, data1, data2, lsr #56
128	ret
129#endif
130
131.Lmutual_align:
132	/* Sources are mutually aligned, but are not currently at an
133	   alignment boundary.  Round down the addresses and then mask off
134	   the bytes that preceed the start point.  */
135	bic	src1, src1, #7
136	bic	src2, src2, #7
137	lsl	tmp1, tmp1, #3		/* Bytes beyond alignment -> bits.  */
138	ldr	data1, [src1], #8
139	neg	tmp1, tmp1		/* Bits to alignment -64.  */
140	ldr	data2, [src2], #8
141	mov	tmp2, #~0
142#ifdef __AARCH64EB__
143	/* Big-endian.  Early bytes are at MSB.  */
144	lsl	tmp2, tmp2, tmp1	/* Shift (tmp1 & 63).  */
145#else
146	/* Little-endian.  Early bytes are at LSB.  */
147	lsr	tmp2, tmp2, tmp1	/* Shift (tmp1 & 63).  */
148#endif
149	orr	data1, data1, tmp2
150	orr	data2, data2, tmp2
151	b	.Lstart_realigned
152
153.Lmisaligned8:
154	/* We can do better than this.  */
155	ldrb	data1w, [src1], #1
156	ldrb	data2w, [src2], #1
157	cmp	data1w, #1
158	ccmp	data1w, data2w, #0, cs	/* NZCV = 0b0000.  */
159	b.eq	.Lmisaligned8
160	sub	result, data1, data2
161	ret
162END(strcmp)
163