pintos-os.org Git - pspp/blob - lib/misc/memcmp.c

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