xref: /titanic_51/usr/src/lib/libc/sparc/gen/memchr.s (revision bd335c6465ddbafe543900df4b03247bfa288eff)
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, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27.ident	"%Z%%M%	%I%	%E% SMI"
28
29	.file "%M%"
30/*
31 * Return the ptr in sptr at which the character c1 appears;
32 * or NULL if not found in n chars; don't stop at \0.
33 * void *
34 * memchr(const void *sptr, int c1, size_t n)
35 *  {
36 *       if (n != 0) {
37 *               unsigned char c = (unsigned char)c1;
38 *               const unsigned char *sp = sptr;
39 *
40 *               do {
41 *                       if (*sp++ == c)
42 *                               return ((void *)--sp);
43 *               } while (--n != 0);
44 *       }
45 *       return (NULL);
46 *  }
47 */
48
49#include <sys/asm_linkage.h>
50#include "synonyms.h"
51
52	! The first part of this algorithm focuses on determining
53	! whether or not the desired character is in the first few bytes
54	! of memory, aligning the memory for word-wise copies, and
55	! initializing registers to detect zero bytes
56
57	ENTRY(memchr)
58
59	.align 32
60
61	tst	%o2			! n == 0 ?
62	bz	.notfound		! yup, c not found, return null ptr
63	andcc	%o0, 3, %o4		! s word aligned ?
64	add	%o0, %o2, %o0		! s + n
65	sub	%g0, %o2, %o2		! n = -n
66	bz	.prepword		! yup, prepare for word-wise search
67	and	%o1, 0xff, %o1		! search only for this one byte
68
69	ldub	[%o0 + %o2], %o3	! s[0]
70	cmp	%o3, %o1		! s[0] == c ?
71	be	.done			! yup, done
72	nop				!
73	addcc	%o2, 1, %o2		! n++, s++
74	bz	.notfound		! c not found in first n bytes
75	cmp	%o4, 3			! only one byte needed to align?
76	bz	.prepword2		! yup, prepare for word-wise search
77	sll	%o1, 8, %g1		! start spreading c across word
78	ldub	[%o0 + %o2], %o3	! s[1]
79	cmp	%o3, %o1		! s[1] == c ?
80	be	.done			! yup, done
81	nop				!
82	addcc	%o2, 1, %o2		! n++, s++
83	bz	.notfound		! c not found in first n bytes
84	cmp	%o4, 2			! only two bytes needed to align?
85	bz	.prepword3		! yup, prepare for word-wise search
86	sethi	%hi(0x01010101), %o4	! start loading Alan Mycroft's magic1
87	ldub	[%o0 + %o2], %o3	! s[1]
88	cmp	%o3, %o1		! s[1] == c ?
89	be	.done			! yup, done
90	nop
91	addcc	%o2, 1, %o2		! n++, s++
92	bz	.notfound		! c not found in first n bytes
93	nop
94
95.prepword:
96	sll	%o1, 8, %g1		! spread c -------------+
97.prepword2:				!			!
98	sethi	%hi(0x01010101), %o4	! Alan Mycroft's magic1 !
99.prepword3:				!			!
100	or	%o1, %g1, %o1		!  across all <---------+
101	or	%o4, %lo(0x01010101),%o4! finish loading magic1	!
102	sll	%o1, 16, %g1		!   four bytes <--------+
103	sll	%o4, 7, %o5		! Alan Mycroft's magic2	!
104	or	%o1, %g1, %o1		!    of a word <--------+
105
106.searchchar:
107	lduw	[%o0 + %o2], %o3	! src word
108.searchchar2:
109	addcc	%o2, 4, %o2		! s+=4, n+=4
110	bcs	.lastword		! if counter wraps, last word
111	xor	%o3, %o1, %g1		! tword = word ^ c
112	andn	%o5, %g1, %o3		! ~tword & 0x80808080
113	sub	%g1, %o4, %g1		! (tword - 0x01010101)
114	andcc	%o3, %g1, %g0		! ((tword - 0x01010101) & ~tword & 0x80808080)
115	bz,a	.searchchar2		! c not found if magic expression == 0
116	lduw	[%o0 + %o2], %o3	! src word
117
118	! here we know "word" contains the searched character, and no byte in
119	! "word" exceeds n. If we had exceeded n, we would have gone to label
120	! .lastword. "tword" has null bytes where "word" had c. After
121	! restoring "tword" from "(tword - 0x01010101)" in %g1, examine "tword"
122
123.foundchar:
124	add	%g1, %o4, %g1		! restore tword
125	set	0xff000000, %o4		! mask for 1st byte
126	andcc	%g1, %o4, %g0		! first byte zero (= found c) ?
127	bz,a	.done			! yup, done
128	sub	%o2, 4, %o2		! n -= 4 (undo counter bumping)
129	set	0x00ff0000, %o5		! mask for 2nd byte
130	andcc	%g1, %o5, %g0		! second byte zero (= found c) ?
131	bz,a	.done			! yup, done
132	sub	%o2, 3, %o2		! n -= 3 (undo counter bumping)
133	srl	%o4, 16, %o4		! 0x0000ff00 = mask for 3rd byte
134	andcc	%g1, %o4, %g0		! third byte zero (= found c) ?
135	bz,a	.done			! nope, must be fourth byte
136	sub	%o2, 2, %o2		! n -= 2 (undo counter bumping)
137	sub	%o2, 1, %o2		! n -= 1, if fourth byte
138	retl				! done with leaf function
139	add	%o0, %o2, %o0		! return pointer to c in s
140.done:
141	retl				! done with leaf function
142	add	%o0, %o2, %o0		! return pointer to c in s
143	nop
144	nop
145
146	! Here we know that "word" is the last word in the search, and that
147	! some bytes possibly exceed n. However, "word" might also contain c.
148	! "tword" (in %g1) has null bytes where "word" had c. Examine "tword"
149	! while keeping track of number of remaining bytes
150
151.lastword:
152	set	0xff000000, %o4		! mask for 1st byte
153	sub	%o2, 4, %o2		! n -= 4 (undo counter bumping)
154	andcc	%g1, %o4, %g0		! first byte zero (= found c) ?
155	bz	.done			! yup, done
156	set	0x00ff0000, %o5		! mask for 2nd byte
157	addcc	%o2, 1, %o2		! n += 1
158	bz	.notfound		! c not found in first n bytes
159	andcc	%g1, %o5, %g0		! second byte zero (= found c) ?
160	bz	.done			! yup, done
161	srl	%o4, 16, %o4		! 0x0000ff00 = mask for 3rd byte
162	addcc	%o2, 1, %o2		! n += 1
163	bz	.notfound		! c not found in first n bytes
164	andcc	%g1, %o4, %g0		! third byte zero (= found c) ?
165	bz	.done			! yup, done
166	nop				!
167	addcc	%o2, 1, %o2		! n += 1
168	bz	.notfound		! c not found in first n bytes
169	andcc	%g1, 0xff, %g0		! fourth byte zero (= found c) ?
170	bz	.done			! yup, done
171	nop
172
173.notfound:
174	retl				! done with leaf function
175	mov	%g0, %o0		! return null pointer
176
177	SET_SIZE(memchr)
178