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