string/memcmp.c

   1 /* Copyright (C) 1991,1993,1995,1997,1998,2003,2004
   2    Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Torbjorn Granlund (tege@sics.se).
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #undef  __ptr_t
  26 #if defined __cplusplus || (defined __STDC__ && __STDC__)
  27 # define __ptr_t        void *
  28 #else /* Not C++ or ANSI C.  */
  29 # undef const
  30 # define const
  31 # define __ptr_t        char *
  32 #endif /* C++ or ANSI C.  */
  33
  34 #if defined HAVE_STRING_H || defined _LIBC
  35 # include <string.h>
  36 #endif
  37
  38 #undef memcmp
  39
  40 #ifdef _LIBC
  41
  42 # include <memcopy.h>
  43 # include <endian.h>
  44
  45 # if __BYTE_ORDER == __BIG_ENDIAN
  46 #  define WORDS_BIGENDIAN
  47 # endif
  48
  49 #else   /* Not in the GNU C library.  */
  50
  51 # include <sys/types.h>
  52
  53 /* Type to use for aligned memory operations.
  54    This should normally be the biggest type supported by a single load
  55    and store.  Must be an unsigned type.  */
  56 # define op_t   unsigned long int
  57 # define OPSIZ  (sizeof(op_t))
  58
  59 /* Threshold value for when to enter the unrolled loops.  */
  60 # define OP_T_THRES     16
  61
  62 /* Type to use for unaligned operations.  */
  63 typedef unsigned char byte;
  64
  65 # ifndef WORDS_BIGENDIAN
  66 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  67 # else
  68 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  69 # endif
  70
  71 #endif  /* In the GNU C library.  */
  72
  73 #ifdef WORDS_BIGENDIAN
  74 # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
  75 #else
  76 # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
  77 #endif
  78
  79 /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  80
  81 /* The strategy of this memcmp is:
  82
  83    1. Compare bytes until one of the block pointers is aligned.
  84
  85    2. Compare using memcmp_common_alignment or
  86       memcmp_not_common_alignment, regarding the alignment of the other
  87       block after the initial byte operations.  The maximum number of
  88       full words (of type op_t) are compared in this way.
  89
  90    3. Compare the few remaining bytes.  */
  91
  92 #ifndef WORDS_BIGENDIAN
  93 /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  94    A and B are known to be different.
  95    This is needed only on little-endian machines.  */
  96
  97 static int memcmp_bytes (op_t, op_t) __THROW;
  98
  99 # ifdef  __GNUC__
 100 __inline
 101 # endif
 102 static int
 103 memcmp_bytes (a, b)
 104      op_t a, b;
 105 {
 106   long int srcp1 = (long int) &a;
 107   long int srcp2 = (long int) &b;
 108   op_t a0, b0;
 109
 110   do
 111     {
 112       a0 = ((byte *) srcp1)[0];
 113       b0 = ((byte *) srcp2)[0];
 114       srcp1 += 1;
 115       srcp2 += 1;
 116     }
 117   while (a0 == b0);
 118   return a0 - b0;
 119 }
 120 #endif
 121
 122 static int memcmp_common_alignment (long, long, size_t) __THROW;
 123
 124 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
 125    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
 126    memory operations on `op_t's.  */
 127 static int
 128 memcmp_common_alignment (srcp1, srcp2, len)
 129      long int srcp1;
 130      long int srcp2;
 131      size_t len;
 132 {
 133   op_t a0, a1;
 134   op_t b0, b1;
 135
 136   switch (len % 4)
 137     {
 138     default: /* Avoid warning about uninitialized local variables.  */
 139     case 2:
 140       a0 = ((op_t *) srcp1)[0];
 141       b0 = ((op_t *) srcp2)[0];
 142       srcp1 -= 2 * OPSIZ;
 143       srcp2 -= 2 * OPSIZ;
 144       len += 2;
 145       goto do1;
 146     case 3:
 147       a1 = ((op_t *) srcp1)[0];
 148       b1 = ((op_t *) srcp2)[0];
 149       srcp1 -= OPSIZ;
 150       srcp2 -= OPSIZ;
 151       len += 1;
 152       goto do2;
 153     case 0:
 154       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 155         return 0;
 156       a0 = ((op_t *) srcp1)[0];
 157       b0 = ((op_t *) srcp2)[0];
 158       goto do3;
 159     case 1:
 160       a1 = ((op_t *) srcp1)[0];
 161       b1 = ((op_t *) srcp2)[0];
 162       srcp1 += OPSIZ;
 163       srcp2 += OPSIZ;
 164       len -= 1;
 165       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 166         goto do0;
 167       /* Fall through.  */
 168     }
 169
 170   do
 171     {
 172       a0 = ((op_t *) srcp1)[0];
 173       b0 = ((op_t *) srcp2)[0];
 174       if (a1 != b1)
 175         return CMP_LT_OR_GT (a1, b1);
 176
 177     do3:
 178       a1 = ((op_t *) srcp1)[1];
 179       b1 = ((op_t *) srcp2)[1];
 180       if (a0 != b0)
 181         return CMP_LT_OR_GT (a0, b0);
 182
 183     do2:
 184       a0 = ((op_t *) srcp1)[2];
 185       b0 = ((op_t *) srcp2)[2];
 186       if (a1 != b1)
 187         return CMP_LT_OR_GT (a1, b1);
 188
 189     do1:
 190       a1 = ((op_t *) srcp1)[3];
 191       b1 = ((op_t *) srcp2)[3];
 192       if (a0 != b0)
 193         return CMP_LT_OR_GT (a0, b0);
 194
 195       srcp1 += 4 * OPSIZ;
 196       srcp2 += 4 * OPSIZ;
 197       len -= 4;
 198     }
 199   while (len != 0);
 200
 201   /* This is the right position for do0.  Please don't move
 202      it into the loop.  */
 203  do0:
 204   if (a1 != b1)
 205     return CMP_LT_OR_GT (a1, b1);
 206   return 0;
 207 }
 208
 209 static int memcmp_not_common_alignment (long, long, size_t) __THROW;
 210
 211 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
 212    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
 213    operations on `op_t', but SRCP1 *should be unaligned*.  */
 214 static int
 215 memcmp_not_common_alignment (srcp1, srcp2, len)
 216      long int srcp1;
 217      long int srcp2;
 218      size_t len;
 219 {
 220   op_t a0, a1, a2, a3;
 221   op_t b0, b1, b2, b3;
 222   op_t x;
 223   int shl, shr;
 224
 225   /* Calculate how to shift a word read at the memory operation
 226      aligned srcp1 to make it aligned for comparison.  */
 227
 228   shl = 8 * (srcp1 % OPSIZ);
 229   shr = 8 * OPSIZ - shl;
 230
 231   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
 232      it points in the middle of.  */
 233   srcp1 &= -OPSIZ;
 234
 235   switch (len % 4)
 236     {
 237     default: /* Avoid warning about uninitialized local variables.  */
 238     case 2:
 239       a1 = ((op_t *) srcp1)[0];
 240       a2 = ((op_t *) srcp1)[1];
 241       b2 = ((op_t *) srcp2)[0];
 242       srcp1 -= 1 * OPSIZ;
 243       srcp2 -= 2 * OPSIZ;
 244       len += 2;
 245       goto do1;
 246     case 3:
 247       a0 = ((op_t *) srcp1)[0];
 248       a1 = ((op_t *) srcp1)[1];
 249       b1 = ((op_t *) srcp2)[0];
 250       srcp2 -= 1 * OPSIZ;
 251       len += 1;
 252       goto do2;
 253     case 0:
 254       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 255         return 0;
 256       a3 = ((op_t *) srcp1)[0];
 257       a0 = ((op_t *) srcp1)[1];
 258       b0 = ((op_t *) srcp2)[0];
 259       srcp1 += 1 * OPSIZ;
 260       goto do3;
 261     case 1:
 262       a2 = ((op_t *) srcp1)[0];
 263       a3 = ((op_t *) srcp1)[1];
 264       b3 = ((op_t *) srcp2)[0];
 265       srcp1 += 2 * OPSIZ;
 266       srcp2 += 1 * OPSIZ;
 267       len -= 1;
 268       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 269         goto do0;
 270       /* Fall through.  */
 271     }
 272
 273   do
 274     {
 275       a0 = ((op_t *) srcp1)[0];
 276       b0 = ((op_t *) srcp2)[0];
 277       x = MERGE(a2, shl, a3, shr);
 278       if (x != b3)
 279         return CMP_LT_OR_GT (x, b3);
 280
 281     do3:
 282       a1 = ((op_t *) srcp1)[1];
 283       b1 = ((op_t *) srcp2)[1];
 284       x = MERGE(a3, shl, a0, shr);
 285       if (x != b0)
 286         return CMP_LT_OR_GT (x, b0);
 287
 288     do2:
 289       a2 = ((op_t *) srcp1)[2];
 290       b2 = ((op_t *) srcp2)[2];
 291       x = MERGE(a0, shl, a1, shr);
 292       if (x != b1)
 293         return CMP_LT_OR_GT (x, b1);
 294
 295     do1:
 296       a3 = ((op_t *) srcp1)[3];
 297       b3 = ((op_t *) srcp2)[3];
 298       x = MERGE(a1, shl, a2, shr);
 299       if (x != b2)
 300         return CMP_LT_OR_GT (x, b2);
 301
 302       srcp1 += 4 * OPSIZ;
 303       srcp2 += 4 * OPSIZ;
 304       len -= 4;
 305     }
 306   while (len != 0);
 307
 308   /* This is the right position for do0.  Please don't move
 309      it into the loop.  */
 310  do0:
 311   x = MERGE(a2, shl, a3, shr);
 312   if (x != b3)
 313     return CMP_LT_OR_GT (x, b3);
 314   return 0;
 315 }
 316
 317 int
 318 memcmp (s1, s2, len)
 319      const __ptr_t s1;
 320      const __ptr_t s2;
 321      size_t len;
 322 {
 323   op_t a0;
 324   op_t b0;
 325   long int srcp1 = (long int) s1;
 326   long int srcp2 = (long int) s2;
 327   op_t res;
 328
 329   if (len >= OP_T_THRES)
 330     {
 331       /* There are at least some bytes to compare.  No need to test
 332          for LEN == 0 in this alignment loop.  */
 333       while (srcp2 % OPSIZ != 0)
 334         {
 335           a0 = ((byte *) srcp1)[0];
 336           b0 = ((byte *) srcp2)[0];
 337           srcp1 += 1;
 338           srcp2 += 1;
 339           res = a0 - b0;
 340           if (res != 0)
 341             return res;
 342           len -= 1;
 343         }
 344
 345       /* SRCP2 is now aligned for memory operations on `op_t'.
 346          SRCP1 alignment determines if we can do a simple,
 347          aligned compare or need to shuffle bits.  */
 348
 349       if (srcp1 % OPSIZ == 0)
 350         res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
 351       else
 352         res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
 353       if (res != 0)
 354         return res;
 355
 356       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
 357       srcp1 += len & -OPSIZ;
 358       srcp2 += len & -OPSIZ;
 359       len %= OPSIZ;
 360     }
 361
 362   /* There are just a few bytes to compare.  Use byte memory operations.  */
 363   while (len != 0)
 364     {
 365       a0 = ((byte *) srcp1)[0];
 366       b0 = ((byte *) srcp2)[0];
 367       srcp1 += 1;
 368       srcp2 += 1;
 369       res = a0 - b0;
 370       if (res != 0)
 371         return res;
 372       len -= 1;
 373     }
 374
 375   return 0;
 376 }
 377 libc_hidden_builtin_def(memcmp)
 378 #ifdef weak_alias
 379 # undef bcmp
 380 weak_alias (memcmp, bcmp)
 381 #endif