sysdeps/generic/memcmp.c

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