|
Packit Service |
82fcde |
/* Copyright (C) 2010-2018 Free Software Foundation, Inc.
|
|
Packit Service |
82fcde |
This file is part of the GNU C Library.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
The GNU C Library is free software; you can redistribute it and/or
|
|
Packit Service |
82fcde |
modify it under the terms of the GNU Lesser General Public
|
|
Packit Service |
82fcde |
License as published by the Free Software Foundation; either
|
|
Packit Service |
82fcde |
version 2.1 of the License, or (at your option) any later version.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
The GNU C Library is distributed in the hope that it will be useful,
|
|
Packit Service |
82fcde |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
82fcde |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit Service |
82fcde |
Lesser General Public License for more details.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
You should have received a copy of the GNU Lesser General Public
|
|
Packit Service |
82fcde |
License along with the GNU C Library. If not, see
|
|
Packit Service |
82fcde |
<http://www.gnu.org/licenses/>. */
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
#include <string.h>
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
typedef unsigned long word;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
static inline word
|
|
Packit Service |
82fcde |
ldq_u(const void *s)
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
return *(const word *)((word)s & -8);
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
#define unlikely(X) __builtin_expect ((X), 0)
|
|
Packit Service |
82fcde |
#define prefetch(X) __builtin_prefetch ((void *)(X), 0)
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
#define cmpbeq0(X) __builtin_alpha_cmpbge(0, (X))
|
|
Packit Service |
82fcde |
#define find(X, Y) cmpbeq0 ((X) ^ (Y))
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Search no more than N bytes of S for C. */
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
void *
|
|
Packit Service |
82fcde |
__memchr (const void *s, int xc, size_t n)
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
const word *s_align;
|
|
Packit Service |
82fcde |
word t, current, found, mask, offset;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
if (unlikely (n == 0))
|
|
Packit Service |
82fcde |
return 0;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
current = ldq_u (s);
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Replicate low byte of XC into all bytes of C. */
|
|
Packit Service |
82fcde |
t = xc & 0xff; /* 0000000c */
|
|
Packit Service |
82fcde |
t = (t << 8) | t; /* 000000cc */
|
|
Packit Service |
82fcde |
t = (t << 16) | t; /* 0000cccc */
|
|
Packit Service |
82fcde |
const word c = (t << 32) | t; /* cccccccc */
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Align the source, and decrement the count by the number
|
|
Packit Service |
82fcde |
of bytes searched in the first word. */
|
|
Packit Service |
82fcde |
s_align = (const word *)((word)s & -8);
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
size_t inc = n + ((word)s & 7);
|
|
Packit Service |
82fcde |
n = inc | -(inc < n);
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Deal with misalignment in the first word for the comparison. */
|
|
Packit Service |
82fcde |
mask = (1ul << ((word)s & 7)) - 1;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* If the entire string fits within one word, we may need masking
|
|
Packit Service |
82fcde |
at both the front and the back of the string. */
|
|
Packit Service |
82fcde |
if (unlikely (n <= 8))
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
mask |= -1ul << n;
|
|
Packit Service |
82fcde |
goto last_quad;
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
found = find (current, c) & ~mask;
|
|
Packit Service |
82fcde |
if (unlikely (found))
|
|
Packit Service |
82fcde |
goto found_it;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
s_align++;
|
|
Packit Service |
82fcde |
n -= 8;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* If the block is sufficiently large, align to cacheline and prefetch. */
|
|
Packit Service |
82fcde |
if (unlikely (n >= 256))
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
/* Prefetch 3 cache lines beyond the one we're working on. */
|
|
Packit Service |
82fcde |
prefetch (s_align + 8);
|
|
Packit Service |
82fcde |
prefetch (s_align + 16);
|
|
Packit Service |
82fcde |
prefetch (s_align + 24);
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
while ((word)s_align & 63)
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
current = *s_align;
|
|
Packit Service |
82fcde |
found = find (current, c);
|
|
Packit Service |
82fcde |
if (found)
|
|
Packit Service |
82fcde |
goto found_it;
|
|
Packit Service |
82fcde |
s_align++;
|
|
Packit Service |
82fcde |
n -= 8;
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Within each cacheline, advance the load for the next word
|
|
Packit Service |
82fcde |
before the test for the previous word is complete. This
|
|
Packit Service |
82fcde |
allows us to hide the 3 cycle L1 cache load latency. We
|
|
Packit Service |
82fcde |
only perform this advance load within a cacheline to prevent
|
|
Packit Service |
82fcde |
reading across page boundary. */
|
|
Packit Service |
82fcde |
#define CACHELINE_LOOP \
|
|
Packit Service |
82fcde |
do { \
|
|
Packit Service |
82fcde |
word i, next = s_align[0]; \
|
|
Packit Service |
82fcde |
for (i = 0; i < 7; ++i) \
|
|
Packit Service |
82fcde |
{ \
|
|
Packit Service |
82fcde |
current = next; \
|
|
Packit Service |
82fcde |
next = s_align[1]; \
|
|
Packit Service |
82fcde |
found = find (current, c); \
|
|
Packit Service |
82fcde |
if (unlikely (found)) \
|
|
Packit Service |
82fcde |
goto found_it; \
|
|
Packit Service |
82fcde |
s_align++; \
|
|
Packit Service |
82fcde |
} \
|
|
Packit Service |
82fcde |
current = next; \
|
|
Packit Service |
82fcde |
found = find (current, c); \
|
|
Packit Service |
82fcde |
if (unlikely (found)) \
|
|
Packit Service |
82fcde |
goto found_it; \
|
|
Packit Service |
82fcde |
s_align++; \
|
|
Packit Service |
82fcde |
n -= 64; \
|
|
Packit Service |
82fcde |
} while (0)
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* While there's still lots more data to potentially be read,
|
|
Packit Service |
82fcde |
continue issuing prefetches for the 4th cacheline out. */
|
|
Packit Service |
82fcde |
while (n >= 256)
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
prefetch (s_align + 24);
|
|
Packit Service |
82fcde |
CACHELINE_LOOP;
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Up to 3 cache lines remaining. Continue issuing advanced
|
|
Packit Service |
82fcde |
loads, but stop prefetching. */
|
|
Packit Service |
82fcde |
while (n >= 64)
|
|
Packit Service |
82fcde |
CACHELINE_LOOP;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* We may have exhausted the buffer. */
|
|
Packit Service |
82fcde |
if (n == 0)
|
|
Packit Service |
82fcde |
return NULL;
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Quadword aligned loop. */
|
|
Packit Service |
82fcde |
current = *s_align;
|
|
Packit Service |
82fcde |
while (n > 8)
|
|
Packit Service |
82fcde |
{
|
|
Packit Service |
82fcde |
found = find (current, c);
|
|
Packit Service |
82fcde |
if (unlikely (found))
|
|
Packit Service |
82fcde |
goto found_it;
|
|
Packit Service |
82fcde |
current = *++s_align;
|
|
Packit Service |
82fcde |
n -= 8;
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* The last word may need masking at the tail of the compare. */
|
|
Packit Service |
82fcde |
mask = -1ul << n;
|
|
Packit Service |
82fcde |
last_quad:
|
|
Packit Service |
82fcde |
found = find (current, c) & ~mask;
|
|
Packit Service |
82fcde |
if (found == 0)
|
|
Packit Service |
82fcde |
return NULL;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
found_it:
|
|
Packit Service |
82fcde |
#ifdef __alpha_cix__
|
|
Packit Service |
82fcde |
offset = __builtin_alpha_cttz (found);
|
|
Packit Service |
82fcde |
#else
|
|
Packit Service |
82fcde |
/* Extract LSB. */
|
|
Packit Service |
82fcde |
found &= -found;
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
/* Binary search for the LSB. */
|
|
Packit Service |
82fcde |
offset = (found & 0x0f ? 0 : 4);
|
|
Packit Service |
82fcde |
offset += (found & 0x33 ? 0 : 2);
|
|
Packit Service |
82fcde |
offset += (found & 0x55 ? 0 : 1);
|
|
Packit Service |
82fcde |
#endif
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
return (void *)((word)s_align + offset);
|
|
Packit Service |
82fcde |
}
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
#ifdef weak_alias
|
|
Packit Service |
82fcde |
weak_alias (__memchr, memchr)
|
|
Packit Service |
82fcde |
#endif
|
|
Packit Service |
82fcde |
libc_hidden_builtin_def (memchr)
|