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