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