[deliverable/binutils-gdb.git] / gdb / gnulib / memcmp.c

/* Copyright (C) 1991, 1993, 1995, 1997, 1998, 2003, 2006, 2009
Free Software Foundation, Inc.

   Contributed by Torbjorn Granlund (tege@sics.se).

   NOTE: The canonical source of this file is maintained with the GNU C Library.
   Bugs can be reported to bug-glibc@prep.ai.mit.edu.

   This program is free software: you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 3 of the License, or any
   later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef _LIBC
# include <config.h>
#endif

#include <string.h>

#undef memcmp

#ifdef _LIBC

# include <memcopy.h>
# include <endian.h>

# if __BYTE_ORDER == __BIG_ENDIAN
#  define WORDS_BIGENDIAN
# endif

#else	/* Not in the GNU C library.  */

# include <sys/types.h>

/* Type to use for aligned memory operations.
   This should normally be the biggest type supported by a single load
   and store.  Must be an unsigned type.  */
# define op_t	unsigned long int
# define OPSIZ	(sizeof(op_t))

/* Threshold value for when to enter the unrolled loops.  */
# define OP_T_THRES	16

/* Type to use for unaligned operations.  */
typedef unsigned char byte;

# ifndef WORDS_BIGENDIAN
#  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
# else
#  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
# endif

#endif	/* In the GNU C library.  */

#ifdef WORDS_BIGENDIAN
# define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
#else
# define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
#endif

/* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */

/* The strategy of this memcmp is:

   1. Compare bytes until one of the block pointers is aligned.

   2. Compare using memcmp_common_alignment or
      memcmp_not_common_alignment, regarding the alignment of the other
      block after the initial byte operations.  The maximum number of
      full words (of type op_t) are compared in this way.

   3. Compare the few remaining bytes.  */

#ifndef WORDS_BIGENDIAN
/* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
   A and B are known to be different.
   This is needed only on little-endian machines.  */

# ifdef  __GNUC__
__inline
# endif
static int
memcmp_bytes (long unsigned int a, long unsigned int b)
{
  long int srcp1 = (long int) &a;
  long int srcp2 = (long int) &b;
  op_t a0, b0;

  do
    {
      a0 = ((byte *) srcp1)[0];
      b0 = ((byte *) srcp2)[0];
      srcp1 += 1;
      srcp2 += 1;
    }
  while (a0 == b0);
  return a0 - b0;
}
#endif

/* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
   objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
   memory operations on `op_t's.  */
#ifdef	__GNUC__
__inline
#endif
static int
memcmp_common_alignment (long int srcp1, long int srcp2, size_t len)
{
  op_t a0, a1;
  op_t b0, b1;

  switch (len % 4)
    {
    default: /* Avoid warning about uninitialized local variables.  */
    case 2:
      a0 = ((op_t *) srcp1)[0];
      b0 = ((op_t *) srcp2)[0];
      srcp1 -= 2 * OPSIZ;
      srcp2 -= 2 * OPSIZ;
      len += 2;
      goto do1;
    case 3:
      a1 = ((op_t *) srcp1)[0];
      b1 = ((op_t *) srcp2)[0];
      srcp1 -= OPSIZ;
      srcp2 -= OPSIZ;
      len += 1;
      goto do2;
    case 0:
      if (OP_T_THRES <= 3 * OPSIZ && len == 0)
	return 0;
      a0 = ((op_t *) srcp1)[0];
      b0 = ((op_t *) srcp2)[0];
      goto do3;
    case 1:
      a1 = ((op_t *) srcp1)[0];
      b1 = ((op_t *) srcp2)[0];
      srcp1 += OPSIZ;
      srcp2 += OPSIZ;
      len -= 1;
      if (OP_T_THRES <= 3 * OPSIZ && len == 0)
	goto do0;
      /* Fall through.  */
    }

  do
    {
      a0 = ((op_t *) srcp1)[0];
      b0 = ((op_t *) srcp2)[0];
      if (a1 != b1)
	return CMP_LT_OR_GT (a1, b1);

    do3:
      a1 = ((op_t *) srcp1)[1];
      b1 = ((op_t *) srcp2)[1];
      if (a0 != b0)
	return CMP_LT_OR_GT (a0, b0);

    do2:
      a0 = ((op_t *) srcp1)[2];
      b0 = ((op_t *) srcp2)[2];
      if (a1 != b1)
	return CMP_LT_OR_GT (a1, b1);

    do1:
      a1 = ((op_t *) srcp1)[3];
      b1 = ((op_t *) srcp2)[3];
      if (a0 != b0)
	return CMP_LT_OR_GT (a0, b0);

      srcp1 += 4 * OPSIZ;
      srcp2 += 4 * OPSIZ;
      len -= 4;
    }
  while (len != 0);

  /* This is the right position for do0.  Please don't move
     it into the loop.  */
 do0:
  if (a1 != b1)
    return CMP_LT_OR_GT (a1, b1);
  return 0;
}

/* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
   `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
   operations on `op_t', but SRCP1 *should be unaligned*.  */
#ifdef	__GNUC__
__inline
#endif
static int
memcmp_not_common_alignment (long int srcp1, long int srcp2, size_t len)
{
  op_t a0, a1, a2, a3;
  op_t b0, b1, b2, b3;
  op_t x;
  int shl, shr;

  /* Calculate how to shift a word read at the memory operation
     aligned srcp1 to make it aligned for comparison.  */

  shl = 8 * (srcp1 % OPSIZ);
  shr = 8 * OPSIZ - shl;

  /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
     it points in the middle of.  */
  srcp1 &= -OPSIZ;

  switch (len % 4)
    {
    default: /* Avoid warning about uninitialized local variables.  */
    case 2:
      a1 = ((op_t *) srcp1)[0];
      a2 = ((op_t *) srcp1)[1];
      b2 = ((op_t *) srcp2)[0];
      srcp1 -= 1 * OPSIZ;
      srcp2 -= 2 * OPSIZ;
      len += 2;
      goto do1;
    case 3:
      a0 = ((op_t *) srcp1)[0];
      a1 = ((op_t *) srcp1)[1];
      b1 = ((op_t *) srcp2)[0];
      srcp2 -= 1 * OPSIZ;
      len += 1;
      goto do2;
    case 0:
      if (OP_T_THRES <= 3 * OPSIZ && len == 0)
	return 0;
      a3 = ((op_t *) srcp1)[0];
      a0 = ((op_t *) srcp1)[1];
      b0 = ((op_t *) srcp2)[0];
      srcp1 += 1 * OPSIZ;
      goto do3;
    case 1:
      a2 = ((op_t *) srcp1)[0];
      a3 = ((op_t *) srcp1)[1];
      b3 = ((op_t *) srcp2)[0];
      srcp1 += 2 * OPSIZ;
      srcp2 += 1 * OPSIZ;
      len -= 1;
      if (OP_T_THRES <= 3 * OPSIZ && len == 0)
	goto do0;
      /* Fall through.  */
    }

  do
    {
      a0 = ((op_t *) srcp1)[0];
      b0 = ((op_t *) srcp2)[0];
      x = MERGE(a2, shl, a3, shr);
      if (x != b3)
	return CMP_LT_OR_GT (x, b3);

    do3:
      a1 = ((op_t *) srcp1)[1];
      b1 = ((op_t *) srcp2)[1];
      x = MERGE(a3, shl, a0, shr);
      if (x != b0)
	return CMP_LT_OR_GT (x, b0);

    do2:
      a2 = ((op_t *) srcp1)[2];
      b2 = ((op_t *) srcp2)[2];
      x = MERGE(a0, shl, a1, shr);
      if (x != b1)
	return CMP_LT_OR_GT (x, b1);

    do1:
      a3 = ((op_t *) srcp1)[3];
      b3 = ((op_t *) srcp2)[3];
      x = MERGE(a1, shl, a2, shr);
      if (x != b2)
	return CMP_LT_OR_GT (x, b2);

      srcp1 += 4 * OPSIZ;
      srcp2 += 4 * OPSIZ;
      len -= 4;
    }
  while (len != 0);

  /* This is the right position for do0.  Please don't move
     it into the loop.  */
 do0:
  x = MERGE(a2, shl, a3, shr);
  if (x != b3)
    return CMP_LT_OR_GT (x, b3);
  return 0;
}

int
rpl_memcmp (const void *s1, const void *s2, size_t len)
{
  op_t a0;
  op_t b0;
  long int srcp1 = (long int) s1;
  long int srcp2 = (long int) s2;
  op_t res;

  if (len >= OP_T_THRES)
    {
      /* There are at least some bytes to compare.  No need to test
	 for LEN == 0 in this alignment loop.  */
      while (srcp2 % OPSIZ != 0)
	{
	  a0 = ((byte *) srcp1)[0];
	  b0 = ((byte *) srcp2)[0];
	  srcp1 += 1;
	  srcp2 += 1;
	  res = a0 - b0;
	  if (res != 0)
	    return res;
	  len -= 1;
	}

      /* SRCP2 is now aligned for memory operations on `op_t'.
	 SRCP1 alignment determines if we can do a simple,
	 aligned compare or need to shuffle bits.  */

      if (srcp1 % OPSIZ == 0)
	res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
      else
	res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
      if (res != 0)
	return res;

      /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
      srcp1 += len & -OPSIZ;
      srcp2 += len & -OPSIZ;
      len %= OPSIZ;
    }

  /* There are just a few bytes to compare.  Use byte memory operations.  */
  while (len != 0)
    {
      a0 = ((byte *) srcp1)[0];
      b0 = ((byte *) srcp2)[0];
      srcp1 += 1;
      srcp2 += 1;
      res = a0 - b0;
      if (res != 0)
	return res;
      len -= 1;
    }

  return 0;
}

#ifdef weak_alias
# undef bcmp
weak_alias (memcmp, bcmp)
#endif
Commit	Line	Data
0fb0cc75 JB	1	/* Copyright (C) 1991, 1993, 1995, 1997, 1998, 2003, 2006, 2009
0fb0cc75 JB	2	Free Software Foundation, Inc.
f6ea5628 DJ	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