]>
git.ipfire.org Git - thirdparty/glibc.git/blob - sysdeps/alpha/memchr.c
1 /* Copyright (C) 2010 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
4 The GNU C Library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Lesser General Public
6 License as published by the Free Software Foundation; either
7 version 2.1 of the License, or (at your option) any later version.
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 Lesser General Public License for more details.
14 You should have received a copy of the GNU Lesser General Public
15 License along with the GNU C Library; if not, write to the Free
16 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 typedef unsigned long word
;
26 return *(const word
*)((word
)s
& -8);
29 #define unlikely(X) __builtin_expect ((X), 0)
30 #define prefetch(X) __builtin_prefetch ((void *)(X), 0)
32 #define cmpbeq0(X) __builtin_alpha_cmpbge(0, (X))
33 #define find(X, Y) cmpbeq0 ((X) ^ (Y))
35 /* Search no more than N bytes of S for C. */
38 __memchr (const void *s
, int xc
, size_t n
)
41 word t
, current
, found
, mask
, offset
;
43 if (unlikely (n
== 0))
48 /* Replicate low byte of XC into all bytes of C. */
49 t
= xc
& 0xff; /* 0000000c */
50 t
= (t
<< 8) | t
; /* 000000cc */
51 t
= (t
<< 16) | t
; /* 0000cccc */
52 const word c
= (t
<< 32) | t
; /* cccccccc */
54 /* Align the source, and decrement the count by the number
55 of bytes searched in the first word. */
56 s_align
= (const word
*)(s
& -8);
59 /* Deal with misalignment in the first word for the comparison. */
60 mask
= (1ul << (s
& 7)) - 1;
62 /* If the entire string fits within one word, we may need masking
63 at both the front and the back of the string. */
64 if (unlikely (n
<= 8))
70 found
= find (current
, c
) & ~mask
;
77 /* If the block is sufficiently large, align to cacheline and prefetch. */
78 if (unlikely (n
>= 256))
80 /* Prefetch 3 cache lines beyond the one we're working on. */
81 prefetch (s_align
+ 8);
82 prefetch (s_align
+ 16);
83 prefetch (s_align
+ 24);
85 while ((word
)s_align
& 63)
88 found
= find (current
, c
);
95 /* Within each cacheline, advance the load for the next word
96 before the test for the previous word is complete. This
97 allows us to hide the 3 cycle L1 cache load latency. We
98 only perform this advance load within a cacheline to prevent
99 reading across page boundary. */
100 #define CACHELINE_LOOP \
102 word i, next = s_align[0]; \
103 for (i = 0; i < 7; ++i) \
107 found = find (current, c); \
108 if (unlikely (found)) \
113 found = find (current, c); \
114 if (unlikely (found)) \
120 /* While there's still lots more data to potentially be read,
121 continue issuing prefetches for the 4th cacheline out. */
124 prefetch (s_align
+ 24);
128 /* Up to 3 cache lines remaining. Continue issuing advanced
129 loads, but stop prefetching. */
133 /* We may have exhausted the buffer. */
138 /* Quadword aligned loop. */
142 found
= find (current
, c
);
143 if (unlikely (found
))
145 current
= *++s_align
;
149 /* The last word may need masking at the tail of the compare. */
152 found
= find (current
, c
) & ~mask
;
158 offset
= __builtin_alpha_cttz (found
);
163 /* Binary search for the LSB. */
164 offset
= (found
& 0x0f ? 0 : 4);
165 offset
+= (found
& 0x33 ? 0 : 2);
166 offset
+= (found
& 0x55 ? 0 : 1);
169 return (void *)((word
)s_align
+ offset
);
173 weak_alias (__memchr
, BP_SYM (memchr
))
175 libc_hidden_builtin_def (memchr
)