lib/memcmp.c

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