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 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