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
  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 (a, b)
 108      op_t a, b;
 109 {
 110   long int srcp1 = (long int) &a;
 111   long int srcp2 = (long int) &b;
 112   op_t a0, b0;
 113
 114   do
 115     {
 116       a0 = ((byte *) srcp1)[0];
 117       b0 = ((byte *) srcp2)[0];
 118       srcp1 += 1;
 119       srcp2 += 1;
 120     }
 121   while (a0 == b0);
 122   return a0 - b0;
 123 }
 124 #endif
 125
 126 static int memcmp_common_alignment __P((long, long, size_t));
 127
 128 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
 129    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
 130    memory operations on `op_t's.  */
 131 #ifdef  __GNUC__
 132 __inline
 133 #endif
 134 static int
 135 memcmp_common_alignment (srcp1, srcp2, len)
 136      long int srcp1;
 137      long int srcp2;
 138      size_t len;
 139 {
 140   op_t a0, a1;
 141   op_t b0, b1;
 142
 143   switch (len % 4)
 144     {
 145     default: /* Avoid warning about uninitialized local variables.  */
 146     case 2:
 147       a0 = ((op_t *) srcp1)[0];
 148       b0 = ((op_t *) srcp2)[0];
 149       srcp1 -= 2 * OPSIZ;
 150       srcp2 -= 2 * OPSIZ;
 151       len += 2;
 152       goto do1;
 153     case 3:
 154       a1 = ((op_t *) srcp1)[0];
 155       b1 = ((op_t *) srcp2)[0];
 156       srcp1 -= OPSIZ;
 157       srcp2 -= OPSIZ;
 158       len += 1;
 159       goto do2;
 160     case 0:
 161       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 162         return 0;
 163       a0 = ((op_t *) srcp1)[0];
 164       b0 = ((op_t *) srcp2)[0];
 165       goto do3;
 166     case 1:
 167       a1 = ((op_t *) srcp1)[0];
 168       b1 = ((op_t *) srcp2)[0];
 169       srcp1 += OPSIZ;
 170       srcp2 += OPSIZ;
 171       len -= 1;
 172       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 173         goto do0;
 174       /* Fall through.  */
 175     }
 176
 177   do
 178     {
 179       a0 = ((op_t *) srcp1)[0];
 180       b0 = ((op_t *) srcp2)[0];
 181       if (a1 != b1)
 182         return CMP_LT_OR_GT (a1, b1);
 183
 184     do3:
 185       a1 = ((op_t *) srcp1)[1];
 186       b1 = ((op_t *) srcp2)[1];
 187       if (a0 != b0)
 188         return CMP_LT_OR_GT (a0, b0);
 189
 190     do2:
 191       a0 = ((op_t *) srcp1)[2];
 192       b0 = ((op_t *) srcp2)[2];
 193       if (a1 != b1)
 194         return CMP_LT_OR_GT (a1, b1);
 195
 196     do1:
 197       a1 = ((op_t *) srcp1)[3];
 198       b1 = ((op_t *) srcp2)[3];
 199       if (a0 != b0)
 200         return CMP_LT_OR_GT (a0, b0);
 201
 202       srcp1 += 4 * OPSIZ;
 203       srcp2 += 4 * OPSIZ;
 204       len -= 4;
 205     }
 206   while (len != 0);
 207
 208   /* This is the right position for do0.  Please don't move
 209      it into the loop.  */
 210  do0:
 211   if (a1 != b1)
 212     return CMP_LT_OR_GT (a1, b1);
 213   return 0;
 214 }
 215
 216 static int memcmp_not_common_alignment __P((long, long, size_t));
 217
 218 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
 219    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
 220    operations on `op_t', but SRCP1 *should be unaligned*.  */
 221 #ifdef  __GNUC__
 222 __inline
 223 #endif
 224 static int
 225 memcmp_not_common_alignment (srcp1, srcp2, len)
 226      long int srcp1;
 227      long int srcp2;
 228      size_t len;
 229 {
 230   op_t a0, a1, a2, a3;
 231   op_t b0, b1, b2, b3;
 232   op_t x;
 233   int shl, shr;
 234
 235   /* Calculate how to shift a word read at the memory operation
 236      aligned srcp1 to make it aligned for comparison.  */
 237
 238   shl = 8 * (srcp1 % OPSIZ);
 239   shr = 8 * OPSIZ - shl;
 240
 241   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
 242      it points in the middle of.  */
 243   srcp1 &= -OPSIZ;
 244
 245   switch (len % 4)
 246     {
 247     default: /* Avoid warning about uninitialized local variables.  */
 248     case 2:
 249       a1 = ((op_t *) srcp1)[0];
 250       a2 = ((op_t *) srcp1)[1];
 251       b2 = ((op_t *) srcp2)[0];
 252       srcp1 -= 1 * OPSIZ;
 253       srcp2 -= 2 * OPSIZ;
 254       len += 2;
 255       goto do1;
 256     case 3:
 257       a0 = ((op_t *) srcp1)[0];
 258       a1 = ((op_t *) srcp1)[1];
 259       b1 = ((op_t *) srcp2)[0];
 260       srcp2 -= 1 * OPSIZ;
 261       len += 1;
 262       goto do2;
 263     case 0:
 264       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 265         return 0;
 266       a3 = ((op_t *) srcp1)[0];
 267       a0 = ((op_t *) srcp1)[1];
 268       b0 = ((op_t *) srcp2)[0];
 269       srcp1 += 1 * OPSIZ;
 270       goto do3;
 271     case 1:
 272       a2 = ((op_t *) srcp1)[0];
 273       a3 = ((op_t *) srcp1)[1];
 274       b3 = ((op_t *) srcp2)[0];
 275       srcp1 += 2 * OPSIZ;
 276       srcp2 += 1 * OPSIZ;
 277       len -= 1;
 278       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
 279         goto do0;
 280       /* Fall through.  */
 281     }
 282
 283   do
 284     {
 285       a0 = ((op_t *) srcp1)[0];
 286       b0 = ((op_t *) srcp2)[0];
 287       x = MERGE(a2, shl, a3, shr);
 288       if (x != b3)
 289         return CMP_LT_OR_GT (x, b3);
 290
 291     do3:
 292       a1 = ((op_t *) srcp1)[1];
 293       b1 = ((op_t *) srcp2)[1];
 294       x = MERGE(a3, shl, a0, shr);
 295       if (x != b0)
 296         return CMP_LT_OR_GT (x, b0);
 297
 298     do2:
 299       a2 = ((op_t *) srcp1)[2];
 300       b2 = ((op_t *) srcp2)[2];
 301       x = MERGE(a0, shl, a1, shr);
 302       if (x != b1)
 303         return CMP_LT_OR_GT (x, b1);
 304
 305     do1:
 306       a3 = ((op_t *) srcp1)[3];
 307       b3 = ((op_t *) srcp2)[3];
 308       x = MERGE(a1, shl, a2, shr);
 309       if (x != b2)
 310         return CMP_LT_OR_GT (x, b2);
 311
 312       srcp1 += 4 * OPSIZ;
 313       srcp2 += 4 * OPSIZ;
 314       len -= 4;
 315     }
 316   while (len != 0);
 317
 318   /* This is the right position for do0.  Please don't move
 319      it into the loop.  */
 320  do0:
 321   x = MERGE(a2, shl, a3, shr);
 322   if (x != b3)
 323     return CMP_LT_OR_GT (x, b3);
 324   return 0;
 325 }
 326
 327 int
 328 rpl_memcmp (s1, s2, len)
 329      const __ptr_t s1;
 330      const __ptr_t s2;
 331      size_t len;
 332 {
 333   op_t a0;
 334   op_t b0;
 335   long int srcp1 = (long int) s1;
 336   long int srcp2 = (long int) s2;
 337   op_t res;
 338
 339   if (len >= OP_T_THRES)
 340     {
 341       /* There are at least some bytes to compare.  No need to test
 342          for LEN == 0 in this alignment loop.  */
 343       while (srcp2 % OPSIZ != 0)
 344         {
 345           a0 = ((byte *) srcp1)[0];
 346           b0 = ((byte *) srcp2)[0];
 347           srcp1 += 1;
 348           srcp2 += 1;
 349           res = a0 - b0;
 350           if (res != 0)
 351             return res;
 352           len -= 1;
 353         }
 354
 355       /* SRCP2 is now aligned for memory operations on `op_t'.
 356          SRCP1 alignment determines if we can do a simple,
 357          aligned compare or need to shuffle bits.  */
 358
 359       if (srcp1 % OPSIZ == 0)
 360         res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
 361       else
 362         res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
 363       if (res != 0)
 364         return res;
 365
 366       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
 367       srcp1 += len & -OPSIZ;
 368       srcp2 += len & -OPSIZ;
 369       len %= OPSIZ;
 370     }
 371
 372   /* There are just a few bytes to compare.  Use byte memory operations.  */
 373   while (len != 0)
 374     {
 375       a0 = ((byte *) srcp1)[0];
 376       b0 = ((byte *) srcp2)[0];
 377       srcp1 += 1;
 378       srcp2 += 1;
 379       res = a0 - b0;
 380       if (res != 0)
 381         return res;
 382       len -= 1;
 383     }
 384
 385   return 0;
 386 }
 387
 388 #ifdef weak_alias
 389 # undef bcmp
 390 weak_alias (memcmp, bcmp)
 391 #endif