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