1/* Copyright (C) 1991-2022 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Torbjorn Granlund (tege@sics.se).
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19#ifdef HAVE_CONFIG_H
20# include "config.h"
21#endif
22
23#if defined HAVE_STRING_H || defined _LIBC
24# include <string.h>
25#endif
26
27#undef memcmp
28
29#ifndef MEMCMP
30# define MEMCMP memcmp
31#endif
32
33#ifdef _LIBC
34
35# include <memcopy.h>
36# include <endian.h>
37
38# if __BYTE_ORDER == __BIG_ENDIAN
39# define WORDS_BIGENDIAN
40# endif
41
42#else /* Not in the GNU C library. */
43
44# include <sys/types.h>
45
46/* Type to use for aligned memory operations.
47 This should normally be the biggest type supported by a single load
48 and store. Must be an unsigned type. */
49# define op_t unsigned long int
50# define OPSIZ (sizeof (op_t))
51
52/* Threshold value for when to enter the unrolled loops. */
53# define OP_T_THRES 16
54
55/* Type to use for unaligned operations. */
56typedef unsigned char byte;
57
58# ifndef WORDS_BIGENDIAN
59# define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
60# else
61# define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
62# endif
63
64#endif /* In the GNU C library. */
65
66#ifdef WORDS_BIGENDIAN
67# define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
68#else
69# define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
70#endif
71
72/* BE VERY CAREFUL IF YOU CHANGE THIS CODE! */
73
74/* The strategy of this memcmp is:
75
76 1. Compare bytes until one of the block pointers is aligned.
77
78 2. Compare using memcmp_common_alignment or
79 memcmp_not_common_alignment, regarding the alignment of the other
80 block after the initial byte operations. The maximum number of
81 full words (of type op_t) are compared in this way.
82
83 3. Compare the few remaining bytes. */
84
85#ifndef WORDS_BIGENDIAN
86/* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
87 A and B are known to be different.
88 This is needed only on little-endian machines. */
89
90static int memcmp_bytes (op_t, op_t) __THROW;
91
92static int
93memcmp_bytes (op_t a, op_t b)
94{
95 long int srcp1 = (long int) &a;
96 long int srcp2 = (long int) &b;
97 op_t a0, b0;
98
99 do
100 {
101 a0 = ((byte *) srcp1)[0];
102 b0 = ((byte *) srcp2)[0];
103 srcp1 += 1;
104 srcp2 += 1;
105 }
106 while (a0 == b0);
107 return a0 - b0;
108}
109#endif
110
111static int memcmp_common_alignment (long, long, size_t) __THROW;
112
113/* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
114 objects (not LEN bytes!). Both SRCP1 and SRCP2 should be aligned for
115 memory operations on `op_t's. */
116static int
117memcmp_common_alignment (long int srcp1, long int srcp2, size_t len)
118{
119 op_t a0, a1;
120 op_t b0, b1;
121
122 switch (len % 4)
123 {
124 default: /* Avoid warning about uninitialized local variables. */
125 case 2:
126 a0 = ((op_t *) srcp1)[0];
127 b0 = ((op_t *) srcp2)[0];
128 srcp1 -= 2 * OPSIZ;
129 srcp2 -= 2 * OPSIZ;
130 len += 2;
131 goto do1;
132 case 3:
133 a1 = ((op_t *) srcp1)[0];
134 b1 = ((op_t *) srcp2)[0];
135 srcp1 -= OPSIZ;
136 srcp2 -= OPSIZ;
137 len += 1;
138 goto do2;
139 case 0:
140 if (OP_T_THRES <= 3 * OPSIZ && len == 0)
141 return 0;
142 a0 = ((op_t *) srcp1)[0];
143 b0 = ((op_t *) srcp2)[0];
144 goto do3;
145 case 1:
146 a1 = ((op_t *) srcp1)[0];
147 b1 = ((op_t *) srcp2)[0];
148 srcp1 += OPSIZ;
149 srcp2 += OPSIZ;
150 len -= 1;
151 if (OP_T_THRES <= 3 * OPSIZ && len == 0)
152 goto do0;
153 /* Fall through. */
154 }
155
156 do
157 {
158 a0 = ((op_t *) srcp1)[0];
159 b0 = ((op_t *) srcp2)[0];
160 if (a1 != b1)
161 return CMP_LT_OR_GT (a1, b1);
162
163 do3:
164 a1 = ((op_t *) srcp1)[1];
165 b1 = ((op_t *) srcp2)[1];
166 if (a0 != b0)
167 return CMP_LT_OR_GT (a0, b0);
168
169 do2:
170 a0 = ((op_t *) srcp1)[2];
171 b0 = ((op_t *) srcp2)[2];
172 if (a1 != b1)
173 return CMP_LT_OR_GT (a1, b1);
174
175 do1:
176 a1 = ((op_t *) srcp1)[3];
177 b1 = ((op_t *) srcp2)[3];
178 if (a0 != b0)
179 return CMP_LT_OR_GT (a0, b0);
180
181 srcp1 += 4 * OPSIZ;
182 srcp2 += 4 * OPSIZ;
183 len -= 4;
184 }
185 while (len != 0);
186
187 /* This is the right position for do0. Please don't move
188 it into the loop. */
189 do0:
190 if (a1 != b1)
191 return CMP_LT_OR_GT (a1, b1);
192 return 0;
193}
194
195static int memcmp_not_common_alignment (long, long, size_t) __THROW;
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*. */
200static int
201memcmp_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
300int
301MEMCMP (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: len / OPSIZ);
331 else
332 res = memcmp_not_common_alignment (srcp1, srcp2, len: 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}
357libc_hidden_builtin_def(memcmp)
358#ifdef weak_alias
359# undef bcmp
360weak_alias (memcmp, bcmp)
361#endif
362
363#undef __memcmpeq
364strong_alias (memcmp, __memcmpeq)
365libc_hidden_def(__memcmpeq)
366

source code of glibc/string/memcmp.c