sysdeps/generic/memcmp.c

   1 /* Copyright (C) 1991, 1993, 1995, 1997 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
  51 #else   /* Not in the GNU C library.  */
  52
  53 # include <sys/types.h>
  54
  55 /* Type to use for aligned memory operations.
  56    This should normally be the biggest type supported by a single load
  57    and store.  Must be an unsigned type.  */
  58 # define op_t   unsigned long int
  59 # define OPSIZ  (sizeof(op_t))
  60
  61 /* Threshold value for when to enter the unrolled loops.  */
  62 # define OP_T_THRES     16
  63
  64 /* Type to use for unaligned operations.  */
  65 typedef unsigned char byte;
  66
  67 # ifndef WORDS_BIGENDIAN
  68 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  69 # else
  70 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  71 # endif
  72
  73 #endif  /* In the GNU C library.  */
  74
  75 #ifdef WORDS_BIGENDIAN
  76 # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
  77 #else
  78 # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
  79 #endif
  80
  81 /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  82
  83 /* The strategy of this memcmp is:
  84
  85    1. Compare bytes until one of the block pointers is aligned.
  86
  87    2. Compare using memcmp_common_alignment or
  88       memcmp_not_common_alignment, regarding the alignment of the other
  89       block after the initial byte operations.  The maximum number of
  90       full words (of type op_t) are compared in this way.
  91
  92    3. Compare the few remaining bytes.  */
  93
  94 #ifndef WORDS_BIGENDIAN
  95 /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  96    A and B are known to be different.
  97    This is needed only on little-endian machines.  */
  98
  99 static int memcmp_bytes __P((op_t, op_t));
 100
 101 # ifdef  __GNUC__
 102 __inline
 103 # endif
 104 static int
 105 memcmp_bytes (a, b)
 106      op_t a, b;
 107 {
 108   long int srcp1 = (long int) &a;
 109   long int srcp2 = (long int) &b;
 110   op_t a0, b0;
 111
 112   do
 113     {
 114       a0 = ((byte *) srcp1)[0];
 115       b0 = ((byte *) srcp2)[0];
 116       srcp1 += 1;
 117       srcp2 += 1;
 118     }
 119   while (a0 == b0);
 120   return a0 - b0;
 121 }
 122 #endif
 123
 124 static int memcmp_common_alignment __P((long, long, size_t));
 125
 126 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
 127    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
 128    memory operations on `op_t's.  */
 129 #ifdef  __GNUC__
 130 __inline
 131 #endif
 132 static int
 133 memcmp_common_alignment (srcp1, srcp2, len)
 134      long int srcp1;
 135      long int srcp2;
 136      size_t len;
 137 {
 138   op_t a0, a1;
 139   op_t b0, b1;
 140
 141   switch (len % 4)
 142     {
 143     default: /* Avoid warning about uninitialized local variables.  */
 144     case 2:
 145       a0 = ((op_t *) srcp1)[0];
 146       b0 = ((op_t *) srcp2)[0];
 147       srcp1 -= 2 * OPSIZ;
 148       srcp2 -= 2 * OPSIZ;
 149       len += 2;
 150       goto do1;
 151     case 3:
 152       a1 = ((op_t *) srcp1)[0];
 153       b1 = ((op_t *) srcp2)[0];
 154       srcp1 -= OPSIZ;
 155       srcp2 -= OPSIZ;
 156       len += 1;
 157       goto do2;
 158     case 0:
 159       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 160         return 0;
 161       a0 = ((op_t *) srcp1)[0];
 162       b0 = ((op_t *) srcp2)[0];
 163       goto do3;
 164     case 1:
 165       a1 = ((op_t *) srcp1)[0];
 166       b1 = ((op_t *) srcp2)[0];
 167       srcp1 += OPSIZ;
 168       srcp2 += OPSIZ;
 169       len -= 1;
 170       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 171         goto do0;
 172       /* Fall through.  */
 173     }
 174
 175   do
 176     {
 177       a0 = ((op_t *) srcp1)[0];
 178       b0 = ((op_t *) srcp2)[0];
 179       if (a1 != b1)
 180         return CMP_LT_OR_GT (a1, b1);
 181
 182     do3:
 183       a1 = ((op_t *) srcp1)[1];
 184       b1 = ((op_t *) srcp2)[1];
 185       if (a0 != b0)
 186         return CMP_LT_OR_GT (a0, b0);
 187
 188     do2:
 189       a0 = ((op_t *) srcp1)[2];
 190       b0 = ((op_t *) srcp2)[2];
 191       if (a1 != b1)
 192         return CMP_LT_OR_GT (a1, b1);
 193
 194     do1:
 195       a1 = ((op_t *) srcp1)[3];
 196       b1 = ((op_t *) srcp2)[3];
 197       if (a0 != b0)
 198         return CMP_LT_OR_GT (a0, b0);
 199
 200       srcp1 += 4 * OPSIZ;
 201       srcp2 += 4 * OPSIZ;
 202       len -= 4;
 203     }
 204   while (len != 0);
 205
 206   /* This is the right position for do0.  Please don't move
 207      it into the loop.  */
 208  do0:
 209   if (a1 != b1)
 210     return CMP_LT_OR_GT (a1, b1);
 211   return 0;
 212 }
 213
 214 static int memcmp_not_common_alignment __P((long, long, size_t));
 215
 216 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
 217    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
 218    operations on `op_t', but SRCP1 *should be unaligned*.  */
 219 #ifdef  __GNUC__
 220 __inline
 221 #endif
 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
 386 #ifdef weak_alias
 387 # undef bcmp
 388 weak_alias (memcmp, bcmp)
 389 #endif