Back to index

glibc  2.9
memcmp.c
Go to the documentation of this file.
00001 /* Copyright (C) 1991,1993,1995,1997,1998,2003,2004
00002    Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Contributed by Torbjorn Granlund (tege@sics.se).
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019    02111-1307 USA.  */
00020 
00021 #ifdef HAVE_CONFIG_H
00022 # include "config.h"
00023 #endif
00024 
00025 #undef __ptr_t
00026 #if defined __cplusplus || (defined __STDC__ && __STDC__)
00027 # define __ptr_t     void *
00028 #else /* Not C++ or ANSI C.  */
00029 # undef       const
00030 # define const
00031 # define __ptr_t     char *
00032 #endif /* C++ or ANSI C.  */
00033 
00034 #if defined HAVE_STRING_H || defined _LIBC
00035 # include <string.h>
00036 #endif
00037 
00038 #undef memcmp
00039 
00040 #ifdef _LIBC
00041 
00042 # include <memcopy.h>
00043 # include <endian.h>
00044 
00045 # if __BYTE_ORDER == __BIG_ENDIAN
00046 #  define WORDS_BIGENDIAN
00047 # endif
00048 
00049 #else  /* Not in the GNU C library.  */
00050 
00051 # include <sys/types.h>
00052 
00053 /* Type to use for aligned memory operations.
00054    This should normally be the biggest type supported by a single load
00055    and store.  Must be an unsigned type.  */
00056 # define op_t unsigned long int
00057 # define OPSIZ       (sizeof(op_t))
00058 
00059 /* Threshold value for when to enter the unrolled loops.  */
00060 # define OP_T_THRES  16
00061 
00062 /* Type to use for unaligned operations.  */
00063 typedef unsigned char byte;
00064 
00065 # ifndef WORDS_BIGENDIAN
00066 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
00067 # else
00068 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
00069 # endif
00070 
00071 #endif /* In the GNU C library.  */
00072 
00073 #ifdef WORDS_BIGENDIAN
00074 # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
00075 #else
00076 # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
00077 #endif
00078 
00079 /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
00080 
00081 /* The strategy of this memcmp is:
00082 
00083    1. Compare bytes until one of the block pointers is aligned.
00084 
00085    2. Compare using memcmp_common_alignment or
00086       memcmp_not_common_alignment, regarding the alignment of the other
00087       block after the initial byte operations.  The maximum number of
00088       full words (of type op_t) are compared in this way.
00089 
00090    3. Compare the few remaining bytes.  */
00091 
00092 #ifndef WORDS_BIGENDIAN
00093 /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
00094    A and B are known to be different.
00095    This is needed only on little-endian machines.  */
00096 
00097 static int memcmp_bytes (op_t, op_t) __THROW;
00098 
00099 # ifdef  __GNUC__
00100 __inline
00101 # endif
00102 static int
00103 memcmp_bytes (a, b)
00104      op_t a, b;
00105 {
00106   long int srcp1 = (long int) &a;
00107   long int srcp2 = (long int) &b;
00108   op_t a0, b0;
00109 
00110   do
00111     {
00112       a0 = ((byte *) srcp1)[0];
00113       b0 = ((byte *) srcp2)[0];
00114       srcp1 += 1;
00115       srcp2 += 1;
00116     }
00117   while (a0 == b0);
00118   return a0 - b0;
00119 }
00120 #endif
00121 
00122 static int memcmp_common_alignment (long, long, size_t) __THROW;
00123 
00124 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
00125    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
00126    memory operations on `op_t's.  */
00127 static int
00128 memcmp_common_alignment (srcp1, srcp2, len)
00129      long int srcp1;
00130      long int srcp2;
00131      size_t len;
00132 {
00133   op_t a0, a1;
00134   op_t b0, b1;
00135 
00136   switch (len % 4)
00137     {
00138     default: /* Avoid warning about uninitialized local variables.  */
00139     case 2:
00140       a0 = ((op_t *) srcp1)[0];
00141       b0 = ((op_t *) srcp2)[0];
00142       srcp1 -= 2 * OPSIZ;
00143       srcp2 -= 2 * OPSIZ;
00144       len += 2;
00145       goto do1;
00146     case 3:
00147       a1 = ((op_t *) srcp1)[0];
00148       b1 = ((op_t *) srcp2)[0];
00149       srcp1 -= OPSIZ;
00150       srcp2 -= OPSIZ;
00151       len += 1;
00152       goto do2;
00153     case 0:
00154       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
00155        return 0;
00156       a0 = ((op_t *) srcp1)[0];
00157       b0 = ((op_t *) srcp2)[0];
00158       goto do3;
00159     case 1:
00160       a1 = ((op_t *) srcp1)[0];
00161       b1 = ((op_t *) srcp2)[0];
00162       srcp1 += OPSIZ;
00163       srcp2 += OPSIZ;
00164       len -= 1;
00165       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
00166        goto do0;
00167       /* Fall through.  */
00168     }
00169 
00170   do
00171     {
00172       a0 = ((op_t *) srcp1)[0];
00173       b0 = ((op_t *) srcp2)[0];
00174       if (a1 != b1)
00175        return CMP_LT_OR_GT (a1, b1);
00176 
00177     do3:
00178       a1 = ((op_t *) srcp1)[1];
00179       b1 = ((op_t *) srcp2)[1];
00180       if (a0 != b0)
00181        return CMP_LT_OR_GT (a0, b0);
00182 
00183     do2:
00184       a0 = ((op_t *) srcp1)[2];
00185       b0 = ((op_t *) srcp2)[2];
00186       if (a1 != b1)
00187        return CMP_LT_OR_GT (a1, b1);
00188 
00189     do1:
00190       a1 = ((op_t *) srcp1)[3];
00191       b1 = ((op_t *) srcp2)[3];
00192       if (a0 != b0)
00193        return CMP_LT_OR_GT (a0, b0);
00194 
00195       srcp1 += 4 * OPSIZ;
00196       srcp2 += 4 * OPSIZ;
00197       len -= 4;
00198     }
00199   while (len != 0);
00200 
00201   /* This is the right position for do0.  Please don't move
00202      it into the loop.  */
00203  do0:
00204   if (a1 != b1)
00205     return CMP_LT_OR_GT (a1, b1);
00206   return 0;
00207 }
00208 
00209 static int memcmp_not_common_alignment (long, long, size_t) __THROW;
00210 
00211 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
00212    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
00213    operations on `op_t', but SRCP1 *should be unaligned*.  */
00214 static int
00215 memcmp_not_common_alignment (srcp1, srcp2, len)
00216      long int srcp1;
00217      long int srcp2;
00218      size_t len;
00219 {
00220   op_t a0, a1, a2, a3;
00221   op_t b0, b1, b2, b3;
00222   op_t x;
00223   int shl, shr;
00224 
00225   /* Calculate how to shift a word read at the memory operation
00226      aligned srcp1 to make it aligned for comparison.  */
00227 
00228   shl = 8 * (srcp1 % OPSIZ);
00229   shr = 8 * OPSIZ - shl;
00230 
00231   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
00232      it points in the middle of.  */
00233   srcp1 &= -OPSIZ;
00234 
00235   switch (len % 4)
00236     {
00237     default: /* Avoid warning about uninitialized local variables.  */
00238     case 2:
00239       a1 = ((op_t *) srcp1)[0];
00240       a2 = ((op_t *) srcp1)[1];
00241       b2 = ((op_t *) srcp2)[0];
00242       srcp1 -= 1 * OPSIZ;
00243       srcp2 -= 2 * OPSIZ;
00244       len += 2;
00245       goto do1;
00246     case 3:
00247       a0 = ((op_t *) srcp1)[0];
00248       a1 = ((op_t *) srcp1)[1];
00249       b1 = ((op_t *) srcp2)[0];
00250       srcp2 -= 1 * OPSIZ;
00251       len += 1;
00252       goto do2;
00253     case 0:
00254       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
00255        return 0;
00256       a3 = ((op_t *) srcp1)[0];
00257       a0 = ((op_t *) srcp1)[1];
00258       b0 = ((op_t *) srcp2)[0];
00259       srcp1 += 1 * OPSIZ;
00260       goto do3;
00261     case 1:
00262       a2 = ((op_t *) srcp1)[0];
00263       a3 = ((op_t *) srcp1)[1];
00264       b3 = ((op_t *) srcp2)[0];
00265       srcp1 += 2 * OPSIZ;
00266       srcp2 += 1 * OPSIZ;
00267       len -= 1;
00268       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
00269        goto do0;
00270       /* Fall through.  */
00271     }
00272 
00273   do
00274     {
00275       a0 = ((op_t *) srcp1)[0];
00276       b0 = ((op_t *) srcp2)[0];
00277       x = MERGE(a2, shl, a3, shr);
00278       if (x != b3)
00279        return CMP_LT_OR_GT (x, b3);
00280 
00281     do3:
00282       a1 = ((op_t *) srcp1)[1];
00283       b1 = ((op_t *) srcp2)[1];
00284       x = MERGE(a3, shl, a0, shr);
00285       if (x != b0)
00286        return CMP_LT_OR_GT (x, b0);
00287 
00288     do2:
00289       a2 = ((op_t *) srcp1)[2];
00290       b2 = ((op_t *) srcp2)[2];
00291       x = MERGE(a0, shl, a1, shr);
00292       if (x != b1)
00293        return CMP_LT_OR_GT (x, b1);
00294 
00295     do1:
00296       a3 = ((op_t *) srcp1)[3];
00297       b3 = ((op_t *) srcp2)[3];
00298       x = MERGE(a1, shl, a2, shr);
00299       if (x != b2)
00300        return CMP_LT_OR_GT (x, b2);
00301 
00302       srcp1 += 4 * OPSIZ;
00303       srcp2 += 4 * OPSIZ;
00304       len -= 4;
00305     }
00306   while (len != 0);
00307 
00308   /* This is the right position for do0.  Please don't move
00309      it into the loop.  */
00310  do0:
00311   x = MERGE(a2, shl, a3, shr);
00312   if (x != b3)
00313     return CMP_LT_OR_GT (x, b3);
00314   return 0;
00315 }
00316 
00317 int
00318 memcmp (s1, s2, len)
00319      const __ptr_t s1;
00320      const __ptr_t s2;
00321      size_t len;
00322 {
00323   op_t a0;
00324   op_t b0;
00325   long int srcp1 = (long int) s1;
00326   long int srcp2 = (long int) s2;
00327   op_t res;
00328 
00329   if (len >= OP_T_THRES)
00330     {
00331       /* There are at least some bytes to compare.  No need to test
00332         for LEN == 0 in this alignment loop.  */
00333       while (srcp2 % OPSIZ != 0)
00334        {
00335          a0 = ((byte *) srcp1)[0];
00336          b0 = ((byte *) srcp2)[0];
00337          srcp1 += 1;
00338          srcp2 += 1;
00339          res = a0 - b0;
00340          if (res != 0)
00341            return res;
00342          len -= 1;
00343        }
00344 
00345       /* SRCP2 is now aligned for memory operations on `op_t'.
00346         SRCP1 alignment determines if we can do a simple,
00347         aligned compare or need to shuffle bits.  */
00348 
00349       if (srcp1 % OPSIZ == 0)
00350        res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
00351       else
00352        res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
00353       if (res != 0)
00354        return res;
00355 
00356       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
00357       srcp1 += len & -OPSIZ;
00358       srcp2 += len & -OPSIZ;
00359       len %= OPSIZ;
00360     }
00361 
00362   /* There are just a few bytes to compare.  Use byte memory operations.  */
00363   while (len != 0)
00364     {
00365       a0 = ((byte *) srcp1)[0];
00366       b0 = ((byte *) srcp2)[0];
00367       srcp1 += 1;
00368       srcp2 += 1;
00369       res = a0 - b0;
00370       if (res != 0)
00371        return res;
00372       len -= 1;
00373     }
00374 
00375   return 0;
00376 }
00377 libc_hidden_builtin_def(memcmp)
00378 #ifdef weak_alias
00379 # undef bcmp
00380 weak_alias (memcmp, bcmp)
00381 #endif