1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27	.file	"strchr.s"
28
29/*
30 * The strchr() function returns a pointer to the first occurrence of c
31 * (converted to a char) in string s, or a null pointer if c does not occur
32 * in the string.
33 */
34
35#include <sys/asm_linkage.h>
36
37	! Here, we start by checking to see if we're searching the dest
38	! string for a null byte.  We have fast code for this, so it's
39	! an important special case.  Otherwise, if the string is not
40	! word aligned, we check a for the search char a byte at a time
41	! until we've reached a word boundary.  Once this has happened
42	! some zero-byte finding values are initialized and the string
43	! is checked a word at a time
44
45	ENTRY(strchr)
46
47	.align 32
48
49	andcc	%o1, 0xff, %o1		! search only for this one byte
50	bz	.searchnullbyte		! faster code for searching null
51	andcc	%o0, 3, %o4		! str word aligned ?
52	bz,a	.prepword2		! yup, prepare for word-wise search
53	sll	%o1, 8, %g1		! start spreading findchar across word
54
55	ldub	[%o0], %o2		! str[0]
56	cmp	%o2, %o1		! str[0] == findchar ?
57	be	.done			! yup, done
58	tst	%o2			! str[0] == 0 ?
59	bz	.notfound		! yup, return null pointer
60	cmp	%o4, 3			! only one byte needed to align?
61	bz	.prepword		! yup, prepare for word-wise search
62	inc	%o0			! str++
63	ldub	[%o0], %o2		! str[1]
64	cmp	%o2, %o1		! str[1] == findchar ?
65	be	.done			! yup, done
66	tst	%o2			! str[1] == 0 ?
67	bz	.notfound		! yup, return null pointer
68	cmp	%o4, 2			! only two bytes needed to align?
69	bz	.prepword		! yup, prepare for word-wise search
70	inc	%o0			! str++
71	ldub	[%o0], %o2		! str[2]
72	cmp	%o2, %o1		! str[2] == findchar ?
73	be	.done			! yup, done
74	tst	%o2			! str[2] == 0 ?
75	bz	.notfound		! yup, return null pointer
76	inc	%o0			! str++
77
78.prepword:
79	sll	%o1, 8, %g1		! spread findchar ------+
80.prepword2:							!
81	sethi	%hi(0x01010101), %o4	! Alan Mycroft's magic1 !
82	or	%o1, %g1, %o1		!  across all <---------+
83	sethi	%hi(0x80808080), %o5	! Alan Mycroft's magic2	!
84	sll	%o1, 16, %g1		!   four bytes <--------+
85	or	%o4, %lo(0x01010101), %o4			!
86	or	%o1, %g1, %o1		!    of a word <--------+
87	or	%o5, %lo(0x80808080), %o5
88
89.searchchar:
90	lduw	[%o0], %o2		! src word
91	andn	%o5, %o2, %o3		! ~word & 0x80808080
92	sub	%o2, %o4, %g1		! word = (word - 0x01010101)
93	andcc	%o3, %g1, %g0		! ((word - 0x01010101) & ~word & 0x80808080)
94	bnz	.haszerobyte		! zero byte if magic expression != 0
95	xor	%o2, %o1, %g1		! tword = word ^ findchar
96	andn	%o5, %g1, %o3		! ~tword & 0x80808080
97	sub	%g1, %o4, %o2		! (tword - 0x01010101)
98	andcc	%o3, %o2, %g0		! ((tword - 0x01010101) & ~tword & 0x80808080)
99	bz,a	.searchchar		! no findchar if magic expression == 0
100	add	%o0, 4, %o0		! str += 4
101
102	! here we know "word" contains the searched character, but no null
103	! byte. if there was a null byte, we would have gone to .haszerobyte
104	! "tword" has null bytes where "word" had findchar. Examine "tword"
105
106.foundchar:
107	set	0xff000000, %o4		! mask for 1st byte
108	andcc	%g1, %o4, %g0		! first byte zero (= found search char) ?
109	bz	.done			! yup, done
110	set	0x00ff0000, %o5		! mask for 2nd byte
111	inc	%o0			! str++
112	andcc	%g1, %o5, %g0		! second byte zero (= found search char) ?
113	bz	.done			! yup, done
114	srl	%o4, 16, %o4		! 0x0000ff00 = mask for 3rd byte
115	inc	%o0			! str++
116	andcc	%g1, %o4, %g0		! third byte zero (= found search char) ?
117	bnz,a	.done			! nope, increment in delay slot
118	inc	%o0			! str++
119
120.done:
121	retl				! done with leaf function
122	nop				! padding
123
124	! Here we know that "word" contains a null byte indicating the
125	! end of the string. However, "word" might also contain findchar
126	! "tword" (in %g1) has null bytes where "word" had findchar. So
127	! check both "tword" and "word"
128
129.haszerobyte:
130	set	0xff000000, %o4		! mask for 1st byte
131	andcc	%g1, %o4, %g0		! first byte == findchar ?
132	bz	.done			! yup, done
133	andcc	%o2, %o4, %g0		! first byte == 0 ?
134	bz	.notfound		! yup, return null pointer
135	set	0x00ff0000, %o4		! mask for 2nd byte
136	inc	%o0			! str++
137	andcc	%g1, %o4, %g0		! second byte == findchar ?
138	bz	.done			! yup, done
139	andcc	%o2, %o4, %g0		! second byte == 0 ?
140	bz	.notfound		! yup, return null pointer
141	srl	%o4, 8, %o4		! mask for 3rd byte = 0x0000ff00
142	inc	%o0			! str++
143	andcc	%g1, %o4, %g0		! third byte == findchar ?
144	bz	.done			! yup, done
145	andcc	%o2, %o4, %g0		! third byte == 0 ?
146	bz	.notfound		! yup, return null pointer
147	andcc	%g1, 0xff, %g0		! fourth byte == findchar ?
148	bz	.done			! yup, done
149	inc	%o0			! str++
150
151.notfound:
152	retl				! done with leaf function
153	xor	%o0, %o0, %o0		! return null pointer
154
155	! since findchar == 0, we only have to do one test per item
156	! instead of two. This makes the search much faster.
157
158.searchnullbyte:
159	bz	.straligned		! str is word aligned
160	nop				! padding
161
162	cmp	%o4, 2			! str halfword aligned ?
163	be	.s2aligned		! yup
164	ldub	[%o0], %o1		! str[0]
165	tst	%o1			! byte zero?
166	bz	.done2			! yup, done
167	cmp	%o4, 3			! only one byte needed to align?
168	bz	.straligned		! yup
169	inc	%o0			! str++
170
171	! check to see if we're half word aligned, which it better than
172	! not being aligned at all.  Search the first half of the word
173	! if we are, and then search by whole word.
174
175.s2aligned:
176	lduh	[%o0], %o1		! str[]
177	srl	%o1, 8, %o4		! %o4<7:0> = first byte
178	tst	%o4			! first byte zero ?
179	bz	.done2			! yup, done
180	andcc	%o1, 0xff, %g0		! second byte zero ?
181	bz,a	.done2			! yup, done
182	inc	%o0			! str++
183	add	%o0, 2, %o0		! str+=2
184
185.straligned:
186	sethi	%hi(0x01010101), %o4	! Alan Mycroft's magic1
187	sethi	%hi(0x80808080), %o5	! Alan Mycroft's magic2
188	or	%o4, %lo(0x01010101), %o4
189	or	%o5, %lo(0x80808080), %o5
190
191.searchword:
192	lduw	[%o0], %o1		! src word
193	andn	%o5, %o1, %o3		! ~word & 0x80808080
194	sub	%o1, %o4, %g1		! word = (word - 0x01010101)
195	andcc	%o3, %g1, %g0		! ((word - 0x01010101) & ~word & 0x80808080)
196	bz,a	.searchword		! no zero byte if magic expression == 0
197	add	%o0, 4, %o0		! str += 4
198
199.zerobyte:
200	set	0xff000000, %o4		! mask for 1st byte
201	andcc	%o1, %o4, %g0		! first byte zero?
202	bz	.done2			! yup, done
203	set	0x00ff0000, %o5		! mask for 2nd byte
204	inc	%o0			! str++
205	andcc	%o1, %o5, %g0		! second byte zero?
206	bz	.done2			! yup, done
207	srl	%o4, 16, %o4		! 0x0000ff00 = mask for 3rd byte
208	inc	%o0			! str++
209	andcc	%o1, %o4, %g0		! third byte zero?
210	bnz,a	.done2			! nope, increment in delay slot
211	inc	%o0			! str++
212.done2:
213    	retl				! return from leaf function
214	nop				! padding
215
216	SET_SIZE(strchr)
217