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