lib/memcmp.c

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