string/memcmp.c

   1 /* Copyright (C) 1991-2013 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 Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the 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    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 # include "config.h"
  21 #endif
  22
  23 #undef  __ptr_t
  24 #define __ptr_t void *
  25
  26 #if defined HAVE_STRING_H || defined _LIBC
  27 # include <string.h>
  28 #endif
  29
  30 #undef memcmp
  31
  32 #ifdef _LIBC
  33
  34 # include <memcopy.h>
  35 # include <endian.h>
  36
  37 # if __BYTE_ORDER == __BIG_ENDIAN
  38 #  define WORDS_BIGENDIAN
  39 # endif
  40
  41 #else   /* Not in the GNU C library.  */
  42
  43 # include <sys/types.h>
  44
  45 /* Type to use for aligned memory operations.
  46    This should normally be the biggest type supported by a single load
  47    and store.  Must be an unsigned type.  */
  48 # define op_t   unsigned long int
  49 # define OPSIZ  (sizeof(op_t))
  50
  51 /* Threshold value for when to enter the unrolled loops.  */
  52 # define OP_T_THRES     16
  53
  54 /* Type to use for unaligned operations.  */
  55 typedef unsigned char byte;
  56
  57 # ifndef WORDS_BIGENDIAN
  58 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  59 # else
  60 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  61 # endif
  62
  63 #endif  /* In the GNU C library.  */
  64
  65 #ifdef WORDS_BIGENDIAN
  66 # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
  67 #else
  68 # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
  69 #endif
  70
  71 /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  72
  73 /* The strategy of this memcmp is:
  74
  75    1. Compare bytes until one of the block pointers is aligned.
  76
  77    2. Compare using memcmp_common_alignment or
  78       memcmp_not_common_alignment, regarding the alignment of the other
  79       block after the initial byte operations.  The maximum number of
  80       full words (of type op_t) are compared in this way.
  81
  82    3. Compare the few remaining bytes.  */
  83
  84 #ifndef WORDS_BIGENDIAN
  85 /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  86    A and B are known to be different.
  87    This is needed only on little-endian machines.  */
  88
  89 static int memcmp_bytes (op_t, op_t) __THROW;
  90
  91 static int
  92 memcmp_bytes (a, b)
  93      op_t a, b;
  94 {
  95   long int srcp1 = (long int) &a;
  96   long int srcp2 = (long int) &b;
  97   op_t a0, b0;
  98
  99   do
 100     {
 101       a0 = ((byte *) srcp1)[0];
 102       b0 = ((byte *) srcp2)[0];
 103       srcp1 += 1;
 104       srcp2 += 1;
 105     }
 106   while (a0 == b0);
 107   return a0 - b0;
 108 }
 109 #endif
 110
 111 static int memcmp_common_alignment (long, long, size_t) __THROW;
 112
 113 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
 114    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
 115    memory operations on `op_t's.  */
 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     default: /* Avoid warning about uninitialized local variables.  */
 128     case 2:
 129       a0 = ((op_t *) srcp1)[0];
 130       b0 = ((op_t *) srcp2)[0];
 131       srcp1 -= 2 * OPSIZ;
 132       srcp2 -= 2 * OPSIZ;
 133       len += 2;
 134       goto do1;
 135     case 3:
 136       a1 = ((op_t *) srcp1)[0];
 137       b1 = ((op_t *) srcp2)[0];
 138       srcp1 -= OPSIZ;
 139       srcp2 -= OPSIZ;
 140       len += 1;
 141       goto do2;
 142     case 0:
 143       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 144         return 0;
 145       a0 = ((op_t *) srcp1)[0];
 146       b0 = ((op_t *) srcp2)[0];
 147       goto do3;
 148     case 1:
 149       a1 = ((op_t *) srcp1)[0];
 150       b1 = ((op_t *) srcp2)[0];
 151       srcp1 += OPSIZ;
 152       srcp2 += OPSIZ;
 153       len -= 1;
 154       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 155         goto do0;
 156       /* Fall through.  */
 157     }
 158
 159   do
 160     {
 161       a0 = ((op_t *) srcp1)[0];
 162       b0 = ((op_t *) srcp2)[0];
 163       if (a1 != b1)
 164         return CMP_LT_OR_GT (a1, b1);
 165
 166     do3:
 167       a1 = ((op_t *) srcp1)[1];
 168       b1 = ((op_t *) srcp2)[1];
 169       if (a0 != b0)
 170         return CMP_LT_OR_GT (a0, b0);
 171
 172     do2:
 173       a0 = ((op_t *) srcp1)[2];
 174       b0 = ((op_t *) srcp2)[2];
 175       if (a1 != b1)
 176         return CMP_LT_OR_GT (a1, b1);
 177
 178     do1:
 179       a1 = ((op_t *) srcp1)[3];
 180       b1 = ((op_t *) srcp2)[3];
 181       if (a0 != b0)
 182         return CMP_LT_OR_GT (a0, b0);
 183
 184       srcp1 += 4 * OPSIZ;
 185       srcp2 += 4 * OPSIZ;
 186       len -= 4;
 187     }
 188   while (len != 0);
 189
 190   /* This is the right position for do0.  Please don't move
 191      it into the loop.  */
 192  do0:
 193   if (a1 != b1)
 194     return CMP_LT_OR_GT (a1, b1);
 195   return 0;
 196 }
 197
 198 static int memcmp_not_common_alignment (long, long, size_t) __THROW;
 199
 200 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
 201    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
 202    operations on `op_t', but SRCP1 *should be unaligned*.  */
 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     default: /* Avoid warning about uninitialized local variables.  */
 227     case 2:
 228       a1 = ((op_t *) srcp1)[0];
 229       a2 = ((op_t *) srcp1)[1];
 230       b2 = ((op_t *) srcp2)[0];
 231       srcp1 -= 1 * OPSIZ;
 232       srcp2 -= 2 * OPSIZ;
 233       len += 2;
 234       goto do1;
 235     case 3:
 236       a0 = ((op_t *) srcp1)[0];
 237       a1 = ((op_t *) srcp1)[1];
 238       b1 = ((op_t *) srcp2)[0];
 239       srcp2 -= 1 * OPSIZ;
 240       len += 1;
 241       goto do2;
 242     case 0:
 243       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 244         return 0;
 245       a3 = ((op_t *) srcp1)[0];
 246       a0 = ((op_t *) srcp1)[1];
 247       b0 = ((op_t *) srcp2)[0];
 248       srcp1 += 1 * OPSIZ;
 249       goto do3;
 250     case 1:
 251       a2 = ((op_t *) srcp1)[0];
 252       a3 = ((op_t *) srcp1)[1];
 253       b3 = ((op_t *) srcp2)[0];
 254       srcp1 += 2 * OPSIZ;
 255       srcp2 += 1 * OPSIZ;
 256       len -= 1;
 257       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 258         goto do0;
 259       /* Fall through.  */
 260     }
 261
 262   do
 263     {
 264       a0 = ((op_t *) srcp1)[0];
 265       b0 = ((op_t *) srcp2)[0];
 266       x = MERGE(a2, shl, a3, shr);
 267       if (x != b3)
 268         return CMP_LT_OR_GT (x, b3);
 269
 270     do3:
 271       a1 = ((op_t *) srcp1)[1];
 272       b1 = ((op_t *) srcp2)[1];
 273       x = MERGE(a3, shl, a0, shr);
 274       if (x != b0)
 275         return CMP_LT_OR_GT (x, b0);
 276
 277     do2:
 278       a2 = ((op_t *) srcp1)[2];
 279       b2 = ((op_t *) srcp2)[2];
 280       x = MERGE(a0, shl, a1, shr);
 281       if (x != b1)
 282         return CMP_LT_OR_GT (x, b1);
 283
 284     do1:
 285       a3 = ((op_t *) srcp1)[3];
 286       b3 = ((op_t *) srcp2)[3];
 287       x = MERGE(a1, shl, a2, shr);
 288       if (x != b2)
 289         return CMP_LT_OR_GT (x, b2);
 290
 291       srcp1 += 4 * OPSIZ;
 292       srcp2 += 4 * OPSIZ;
 293       len -= 4;
 294     }
 295   while (len != 0);
 296
 297   /* This is the right position for do0.  Please don't move
 298      it into the loop.  */
 299  do0:
 300   x = MERGE(a2, shl, a3, shr);
 301   if (x != b3)
 302     return CMP_LT_OR_GT (x, b3);
 303   return 0;
 304 }
 305
 306 int
 307 memcmp (s1, s2, len)
 308      const __ptr_t s1;
 309      const __ptr_t s2;
 310      size_t len;
 311 {
 312   op_t a0;
 313   op_t b0;
 314   long int srcp1 = (long int) s1;
 315   long int srcp2 = (long int) s2;
 316   op_t res;
 317
 318   if (len >= OP_T_THRES)
 319     {
 320       /* There are at least some bytes to compare.  No need to test
 321          for LEN == 0 in this alignment loop.  */
 322       while (srcp2 % OPSIZ != 0)
 323         {
 324           a0 = ((byte *) srcp1)[0];
 325           b0 = ((byte *) srcp2)[0];
 326           srcp1 += 1;
 327           srcp2 += 1;
 328           res = a0 - b0;
 329           if (res != 0)
 330             return res;
 331           len -= 1;
 332         }
 333
 334       /* SRCP2 is now aligned for memory operations on `op_t'.
 335          SRCP1 alignment determines if we can do a simple,
 336          aligned compare or need to shuffle bits.  */
 337
 338       if (srcp1 % OPSIZ == 0)
 339         res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
 340       else
 341         res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
 342       if (res != 0)
 343         return res;
 344
 345       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
 346       srcp1 += len & -OPSIZ;
 347       srcp2 += len & -OPSIZ;
 348       len %= OPSIZ;
 349     }
 350
 351   /* There are just a few bytes to compare.  Use byte memory operations.  */
 352   while (len != 0)
 353     {
 354       a0 = ((byte *) srcp1)[0];
 355       b0 = ((byte *) srcp2)[0];
 356       srcp1 += 1;
 357       srcp2 += 1;
 358       res = a0 - b0;
 359       if (res != 0)
 360         return res;
 361       len -= 1;
 362     }
 363
 364   return 0;
 365 }
 366 libc_hidden_builtin_def(memcmp)
 367 #ifdef weak_alias
 368 # undef bcmp
 369 weak_alias (memcmp, bcmp)
 370 #endif