xref: /illumos-gate/usr/src/lib/libc/i386/gen/strcmp.c (revision 7c478bd9)
1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate  * CDDL HEADER START
3*7c478bd9Sstevel@tonic-gate  *
4*7c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5*7c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
6*7c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
7*7c478bd9Sstevel@tonic-gate  * with the License.
8*7c478bd9Sstevel@tonic-gate  *
9*7c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*7c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
11*7c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
12*7c478bd9Sstevel@tonic-gate  * and limitations under the License.
13*7c478bd9Sstevel@tonic-gate  *
14*7c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
15*7c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*7c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
17*7c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
18*7c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
19*7c478bd9Sstevel@tonic-gate  *
20*7c478bd9Sstevel@tonic-gate  * CDDL HEADER END
21*7c478bd9Sstevel@tonic-gate  */
22*7c478bd9Sstevel@tonic-gate /*
23*7c478bd9Sstevel@tonic-gate  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24*7c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
25*7c478bd9Sstevel@tonic-gate  */
26*7c478bd9Sstevel@tonic-gate 
27*7c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
28*7c478bd9Sstevel@tonic-gate 
29*7c478bd9Sstevel@tonic-gate /*
30*7c478bd9Sstevel@tonic-gate  * Fast strcmp.  This works one int at a time, using aligned pointers
31*7c478bd9Sstevel@tonic-gate  * if possible, misaligned pointers if necessary.  To avoid taking
32*7c478bd9Sstevel@tonic-gate  * faults from going off the end of a page, the code is careful to go
33*7c478bd9Sstevel@tonic-gate  * a byte-at-a-time when a misaligned pointer is near a page boundary.
34*7c478bd9Sstevel@tonic-gate  * The code is almost portable, but see the assumptions below.
35*7c478bd9Sstevel@tonic-gate  */
36*7c478bd9Sstevel@tonic-gate 
37*7c478bd9Sstevel@tonic-gate /*
38*7c478bd9Sstevel@tonic-gate  * ASSUMPTIONS:
39*7c478bd9Sstevel@tonic-gate  * sizeof (int) is not greater than 8.
40*7c478bd9Sstevel@tonic-gate  * sizeof (int) is a power of 2.
41*7c478bd9Sstevel@tonic-gate  * An int pointer can always be dereferenced even if it is not properly
42*7c478bd9Sstevel@tonic-gate  *   aligned (though aligned references are assumed to be faster).
43*7c478bd9Sstevel@tonic-gate  * It is OK to assign bogus values to a pointer (in particular, a
44*7c478bd9Sstevel@tonic-gate  *   value that is before the beginning of the string) as long as that
45*7c478bd9Sstevel@tonic-gate  *   pointer is only used with indices big enough to bring us back into
46*7c478bd9Sstevel@tonic-gate  *   the string.
47*7c478bd9Sstevel@tonic-gate  * It is OK to reference bytes past the end of a string as long as we
48*7c478bd9Sstevel@tonic-gate  *   don't cross a page boundary.
49*7c478bd9Sstevel@tonic-gate  */
50*7c478bd9Sstevel@tonic-gate 
51*7c478bd9Sstevel@tonic-gate #include "lint.h"
52*7c478bd9Sstevel@tonic-gate #include <limits.h>
53*7c478bd9Sstevel@tonic-gate #include <unistd.h>
54*7c478bd9Sstevel@tonic-gate #include <sys/sysconfig.h>
55*7c478bd9Sstevel@tonic-gate #include "libc.h"
56*7c478bd9Sstevel@tonic-gate 
57*7c478bd9Sstevel@tonic-gate /*
58*7c478bd9Sstevel@tonic-gate  * This strange expression will test to see if *any* byte in the int is
59*7c478bd9Sstevel@tonic-gate  * a NUL.  The constants are big enough to allow for ints up to 8 bytes.
60*7c478bd9Sstevel@tonic-gate  * The two arguments are actually two copies of the same value; this
61*7c478bd9Sstevel@tonic-gate  * allows the compiler freedom to play with both values for efficiency.
62*7c478bd9Sstevel@tonic-gate  */
63*7c478bd9Sstevel@tonic-gate #define	ANYNUL(i1, i2)	(((i1) - (int)0x0101010101010101LL) & ~(i2) & \
64*7c478bd9Sstevel@tonic-gate 		(int)0x8080808080808080ULL)
65*7c478bd9Sstevel@tonic-gate 
66*7c478bd9Sstevel@tonic-gate int
strcmp(const char * str1,const char * str2)67*7c478bd9Sstevel@tonic-gate strcmp(const char *str1, const char *str2)
68*7c478bd9Sstevel@tonic-gate {
69*7c478bd9Sstevel@tonic-gate 	int *s1, *s2;
70*7c478bd9Sstevel@tonic-gate 	int i1, i2;
71*7c478bd9Sstevel@tonic-gate 	int count;
72*7c478bd9Sstevel@tonic-gate 	int b1, b2;
73*7c478bd9Sstevel@tonic-gate 	static int pagesize;
74*7c478bd9Sstevel@tonic-gate 
75*7c478bd9Sstevel@tonic-gate 	if (str1 == str2)
76*7c478bd9Sstevel@tonic-gate 		return (0);
77*7c478bd9Sstevel@tonic-gate 
78*7c478bd9Sstevel@tonic-gate 	/*
79*7c478bd9Sstevel@tonic-gate 	 * Go 1 byte at a time until at least one pointer is word aligned.
80*7c478bd9Sstevel@tonic-gate 	 * Assumes that sizeof (int) is a power of 2.
81*7c478bd9Sstevel@tonic-gate 	 */
82*7c478bd9Sstevel@tonic-gate 	while ((((int) str1) & (sizeof (int) - 1)) &&
83*7c478bd9Sstevel@tonic-gate 	    (((int) str2) & (sizeof (int) - 1))) {
84*7c478bd9Sstevel@tonic-gate one_byte:
85*7c478bd9Sstevel@tonic-gate 		if (*str1 != *str2)
86*7c478bd9Sstevel@tonic-gate 			return ((unsigned char)*str1 - (unsigned char)*str2);
87*7c478bd9Sstevel@tonic-gate 		if (*str1 == '\0')
88*7c478bd9Sstevel@tonic-gate 			return (0);
89*7c478bd9Sstevel@tonic-gate 		++str1;
90*7c478bd9Sstevel@tonic-gate 		++str2;
91*7c478bd9Sstevel@tonic-gate 	}
92*7c478bd9Sstevel@tonic-gate 
93*7c478bd9Sstevel@tonic-gate 	/*
94*7c478bd9Sstevel@tonic-gate 	 * If one pointer is misaligned, we must be careful not to
95*7c478bd9Sstevel@tonic-gate 	 * dereference it when it points across a page boundary.
96*7c478bd9Sstevel@tonic-gate 	 * If we did, we might go past the end of the segment and
97*7c478bd9Sstevel@tonic-gate 	 * get a SIGSEGV.  Set "count" to the number of ints we can
98*7c478bd9Sstevel@tonic-gate 	 * scan before running into such a boundary.
99*7c478bd9Sstevel@tonic-gate 	 */
100*7c478bd9Sstevel@tonic-gate 	count = INT_MAX;
101*7c478bd9Sstevel@tonic-gate 	if (((int) str1) & (sizeof (int) - 1)) {
102*7c478bd9Sstevel@tonic-gate 		if (pagesize == 0)
103*7c478bd9Sstevel@tonic-gate 			pagesize = _sysconfig(_CONFIG_PAGESIZE);
104*7c478bd9Sstevel@tonic-gate 		count = (pagesize - ((int)str1 & (pagesize - 1))) /
105*7c478bd9Sstevel@tonic-gate 			sizeof (int);
106*7c478bd9Sstevel@tonic-gate 	} else if (((int) str2) & (sizeof (int) - 1)) {
107*7c478bd9Sstevel@tonic-gate 		if (pagesize == 0)
108*7c478bd9Sstevel@tonic-gate 			pagesize = _sysconfig(_CONFIG_PAGESIZE);
109*7c478bd9Sstevel@tonic-gate 		count = (pagesize - ((int)str2 & (pagesize - 1))) /
110*7c478bd9Sstevel@tonic-gate 			sizeof (int);
111*7c478bd9Sstevel@tonic-gate 	}
112*7c478bd9Sstevel@tonic-gate 
113*7c478bd9Sstevel@tonic-gate 	s1 = (void *) str1;
114*7c478bd9Sstevel@tonic-gate 	s2 = (void *) str2;
115*7c478bd9Sstevel@tonic-gate 
116*7c478bd9Sstevel@tonic-gate 	/*
117*7c478bd9Sstevel@tonic-gate 	 * Go "sizeof (int)" bytes at a time until at least one pointer
118*7c478bd9Sstevel@tonic-gate 	 * is word aligned.
119*7c478bd9Sstevel@tonic-gate 	 *
120*7c478bd9Sstevel@tonic-gate 	 * Unwrap the loop for even a bit more speed.
121*7c478bd9Sstevel@tonic-gate 	 */
122*7c478bd9Sstevel@tonic-gate 	for (;;) {
123*7c478bd9Sstevel@tonic-gate 		/*
124*7c478bd9Sstevel@tonic-gate 		 * Check whether we can test the next 4 ints without
125*7c478bd9Sstevel@tonic-gate 		 * hitting a page boundary.  If we can only test 1, 2,
126*7c478bd9Sstevel@tonic-gate 		 * or 3, go and do that first.  If we can't check any
127*7c478bd9Sstevel@tonic-gate 		 * more, go and test one byte, realign, and start again.
128*7c478bd9Sstevel@tonic-gate 		 */
129*7c478bd9Sstevel@tonic-gate 		count -= 4;
130*7c478bd9Sstevel@tonic-gate 		switch (count) {
131*7c478bd9Sstevel@tonic-gate 		case -1:
132*7c478bd9Sstevel@tonic-gate 			--s1;
133*7c478bd9Sstevel@tonic-gate 			--s2;
134*7c478bd9Sstevel@tonic-gate 			goto do3;	/* check only 3 ints */
135*7c478bd9Sstevel@tonic-gate 		case -2:
136*7c478bd9Sstevel@tonic-gate 			s1 -= 2;
137*7c478bd9Sstevel@tonic-gate 			s2 -= 2;
138*7c478bd9Sstevel@tonic-gate 			goto do2;	/* check only 2 ints */
139*7c478bd9Sstevel@tonic-gate 		case -3:
140*7c478bd9Sstevel@tonic-gate 			s1 -= 3;
141*7c478bd9Sstevel@tonic-gate 			s2 -= 3;
142*7c478bd9Sstevel@tonic-gate 			goto do1;	/* check only 1 int */
143*7c478bd9Sstevel@tonic-gate 		case -4:
144*7c478bd9Sstevel@tonic-gate 		case -5:		/* -5, -6, and -7 come up on the */
145*7c478bd9Sstevel@tonic-gate 		case -6:		/* next time around after we do one */
146*7c478bd9Sstevel@tonic-gate 		case -7:		/* of the 3 gotos above */
147*7c478bd9Sstevel@tonic-gate 			str1 = (void *) s1;
148*7c478bd9Sstevel@tonic-gate 			str2 = (void *) s2;
149*7c478bd9Sstevel@tonic-gate 			goto one_byte;
150*7c478bd9Sstevel@tonic-gate 			/*
151*7c478bd9Sstevel@tonic-gate 			 * The goto above should be explained.  By going
152*7c478bd9Sstevel@tonic-gate 			 * into the middle of the loop, it makes sure
153*7c478bd9Sstevel@tonic-gate 			 * that we advance at least one byte.  We will
154*7c478bd9Sstevel@tonic-gate 			 * stay in that loop until the misaligned pointer
155*7c478bd9Sstevel@tonic-gate 			 * becomes aligned (at the page boundary).  We
156*7c478bd9Sstevel@tonic-gate 			 * will then break out of that loop with the
157*7c478bd9Sstevel@tonic-gate 			 * formerly misaligned pointer now aligned, the
158*7c478bd9Sstevel@tonic-gate 			 * formerly aligned pointer now misaligned, and
159*7c478bd9Sstevel@tonic-gate 			 * we will come back into this loop until the
160*7c478bd9Sstevel@tonic-gate 			 * latter pointer reaches a page boundary.
161*7c478bd9Sstevel@tonic-gate 			 */
162*7c478bd9Sstevel@tonic-gate 		default:		/* at least 4 ints to go */
163*7c478bd9Sstevel@tonic-gate 			break;
164*7c478bd9Sstevel@tonic-gate 		}
165*7c478bd9Sstevel@tonic-gate 
166*7c478bd9Sstevel@tonic-gate 		i1 = s1[0];
167*7c478bd9Sstevel@tonic-gate 		i2 = s2[0];
168*7c478bd9Sstevel@tonic-gate 		if (i1 != i2)
169*7c478bd9Sstevel@tonic-gate 			break;
170*7c478bd9Sstevel@tonic-gate 		else if (ANYNUL(i1, i2))
171*7c478bd9Sstevel@tonic-gate 			return (0);
172*7c478bd9Sstevel@tonic-gate 
173*7c478bd9Sstevel@tonic-gate do3:
174*7c478bd9Sstevel@tonic-gate 		i1 = s1[1];
175*7c478bd9Sstevel@tonic-gate 		i2 = s2[1];
176*7c478bd9Sstevel@tonic-gate 		if (i1 != i2)
177*7c478bd9Sstevel@tonic-gate 			break;
178*7c478bd9Sstevel@tonic-gate 		else if (ANYNUL(i1, i2))
179*7c478bd9Sstevel@tonic-gate 			return (0);
180*7c478bd9Sstevel@tonic-gate 
181*7c478bd9Sstevel@tonic-gate do2:
182*7c478bd9Sstevel@tonic-gate 		i1 = s1[2];
183*7c478bd9Sstevel@tonic-gate 		i2 = s2[2];
184*7c478bd9Sstevel@tonic-gate 		if (i1 != i2)
185*7c478bd9Sstevel@tonic-gate 			break;
186*7c478bd9Sstevel@tonic-gate 		else if (ANYNUL(i1, i2))
187*7c478bd9Sstevel@tonic-gate 			return (0);
188*7c478bd9Sstevel@tonic-gate 
189*7c478bd9Sstevel@tonic-gate do1:
190*7c478bd9Sstevel@tonic-gate 		i1 = s1[3];
191*7c478bd9Sstevel@tonic-gate 		i2 = s2[3];
192*7c478bd9Sstevel@tonic-gate 		if (i1 != i2)
193*7c478bd9Sstevel@tonic-gate 			break;
194*7c478bd9Sstevel@tonic-gate 		else if (ANYNUL(i1, i2))
195*7c478bd9Sstevel@tonic-gate 			return (0);
196*7c478bd9Sstevel@tonic-gate 
197*7c478bd9Sstevel@tonic-gate 		s1 += 4;
198*7c478bd9Sstevel@tonic-gate 		s2 += 4;
199*7c478bd9Sstevel@tonic-gate 	}
200*7c478bd9Sstevel@tonic-gate 
201*7c478bd9Sstevel@tonic-gate 	/* We found a difference.  Go one byte at a time to find where. */
202*7c478bd9Sstevel@tonic-gate 	b1 = i1;		/* save the ints in memory */
203*7c478bd9Sstevel@tonic-gate 	b2 = i2;
204*7c478bd9Sstevel@tonic-gate 	str1 = (void *) &b1;	/* point at them */
205*7c478bd9Sstevel@tonic-gate 	str2 = (void *) &b2;
206*7c478bd9Sstevel@tonic-gate 	while (*str1 == *str2) {
207*7c478bd9Sstevel@tonic-gate 		if (*str1 == '\0')
208*7c478bd9Sstevel@tonic-gate 			return (0);
209*7c478bd9Sstevel@tonic-gate 		++str1;
210*7c478bd9Sstevel@tonic-gate 		++str2;
211*7c478bd9Sstevel@tonic-gate 	}
212*7c478bd9Sstevel@tonic-gate 	return ((unsigned char)*str1 - (unsigned char)*str2);
213*7c478bd9Sstevel@tonic-gate }
214