usr/src/lib/libc/i386/gen/strcmp.c

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