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