1 /*
2 Copyright (c) 1994 Cygnus Support.
3 All rights reserved.
4
5 Redistribution and use in source and binary forms are permitted
6 provided that the above copyright notice and this paragraph are
7 duplicated in all such forms and that any documentation,
8 and/or other materials related to such
9 distribution and use acknowledge that the software was developed
10 at Cygnus Support, Inc. Cygnus Support, Inc. may not be used to
11 endorse or promote products derived from this software without
12 specific prior written permission.
13 THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
14 IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
15 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
16 */
17 /*
18 FUNCTION
19 <<memchr>>---find character in memory
20
21 INDEX
22 memchr
23
24 SYNOPSIS
25 #include <string.h>
26 void *memchr(const void *<[src]>, int <[c]>, size_t <[length]>);
27
28 DESCRIPTION
29 This function searches memory starting at <<*<[src]>>> for the
30 character <[c]>. The search only ends with the first
31 occurrence of <[c]>, or after <[length]> characters; in
32 particular, <<NUL>> does not terminate the search.
33
34 RETURNS
35 If the character <[c]> is found within <[length]> characters
36 of <<*<[src]>>>, a pointer to the character is returned. If
37 <[c]> is not found, then <<NULL>> is returned.
38
39 PORTABILITY
40 <<memchr>> is ANSI C.
41
42 <<memchr>> requires no supporting OS subroutines.
43
44 QUICKREF
45 memchr ansi pure
46 */
47
48 #include <_ansi.h>
49 #include <string.h>
50 #include <limits.h>
51 #include <stdint.h>
52
53 /* Nonzero if either X or Y is not aligned on a "long" boundary. */
54 #define UNALIGNED(X) ((uintptr_t)X & (sizeof (long) - 1))
55
56 /* How many bytes are loaded each iteration of the word copy loop. */
57 #define LBLOCKSIZE (sizeof (long))
58
59 /* Threshhold for punting to the bytewise iterator. */
60 #define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
61
62 #if LONG_MAX == 2147483647L
63 #define DETECTNULL(X) (((X) - 0x01010101) & ~(X) & 0x80808080)
64 #else
65 #if LONG_MAX == 9223372036854775807L
66 /* Nonzero if X (a long int) contains a NULL byte. */
67 #define DETECTNULL(X) (((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
68 #else
69 #error long int is not a 32bit or 64bit type.
70 #endif
71 #endif
72
73 #ifndef DETECTNULL
74 #error long int is not a 32bit or 64bit byte
75 #endif
76
77 /* DETECTCHAR returns nonzero if (long)X contains the byte used
78 to fill (long)MASK. */
79 #define DETECTCHAR(X,MASK) (DETECTNULL(X ^ MASK))
80
81 void *
memchr(const void * src_void,int c,size_t length)82 memchr (const void *src_void,
83 int c,
84 size_t length)
85 {
86 const unsigned char *src = (const unsigned char *) src_void;
87 unsigned char d = c;
88
89 #if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__) && \
90 !defined(PICOLIBC_NO_OUT_OF_BOUNDS_READS)
91 unsigned long *asrc;
92 unsigned long mask;
93 unsigned int i;
94
95 while (UNALIGNED (src))
96 {
97 if (!length--)
98 return NULL;
99 if (*src == d)
100 return (void *) src;
101 src++;
102 }
103
104 if (!TOO_SMALL (length))
105 {
106 /* If we get this far, we know that length is large and src is
107 word-aligned. */
108 /* The fast code reads the source one word at a time and only
109 performs the bytewise search on word-sized segments if they
110 contain the search character, which is detected by XORing
111 the word-sized segment with a word-sized block of the search
112 character and then detecting for the presence of NUL in the
113 result. */
114 asrc = (unsigned long *) src;
115 mask = d << 8 | d;
116 mask = mask << 16 | mask;
117 for (i = 32; i < LBLOCKSIZE * 8; i <<= 1)
118 mask = (mask << i) | mask;
119
120 while (length >= LBLOCKSIZE)
121 {
122 if (DETECTCHAR (*asrc, mask))
123 break;
124 length -= LBLOCKSIZE;
125 asrc++;
126 }
127
128 /* If there are fewer than LBLOCKSIZE characters left,
129 then we resort to the bytewise loop. */
130
131 src = (unsigned char *) asrc;
132 }
133
134 #endif /* not PREFER_SIZE_OVER_SPEED */
135
136 while (length--)
137 {
138 if (*src == d)
139 return (void *) src;
140 src++;
141 }
142
143 return NULL;
144 }
145
