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