1 /** @file
2 Search Functions for <string.h>.
3
4 Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>
5 This program and the accompanying materials are licensed and made available under
6 the terms and conditions of the BSD License that accompanies this distribution.
7 The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php.
9
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
12 **/
13 #include <Uefi.h>
14 #include <Library/BaseLib.h>
15 #include <Library/BaseMemoryLib.h>
16
17 #include <LibConfig.h>
18 #include <limits.h>
19 #include <string.h>
20
21 /** The memchr function locates the first occurrence of c (converted to an
22 unsigned char) in the initial n characters (each interpreted as
23 unsigned char) of the object pointed to by s.
24
25 @return The memchr function returns a pointer to the located character,
26 or a null pointer if the character does not occur in the object.
27 **/
28 void *
memchr(const void * s,int c,size_t n)29 memchr(const void *s, int c, size_t n)
30 {
31 return ScanMem8( s, (UINTN)n, (UINT8)c);
32 }
33
34 /** The strchr function locates the first occurrence of c (converted to a char)
35 in the string pointed to by s. The terminating null character is considered
36 to be part of the string.
37
38 @return The strchr function returns a pointer to the located character,
39 or a null pointer if the character does not occur in the string.
40 **/
41 char *
strchr(const char * s,int c)42 strchr(const char *s, int c)
43 {
44 char tgt = (char)c;
45
46 do {
47 if( *s == tgt) {
48 return (char *)s;
49 }
50 } while(*s++ != '\0');
51 return NULL;
52 }
53
54 static UINT8 BitMask[] = {
55 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80
56 };
57
58 #define WHICH8(c) ((unsigned char)(c) >> 3)
59 #define WHICH_BIT(c) (BitMask[((c) & 0x7)])
60 #define BITMAP64 ((UINT64 *)bitmap)
61
62 static
63 void
BuildBitmap(unsigned char * bitmap,const char * s2,int n)64 BuildBitmap(unsigned char * bitmap, const char *s2, int n)
65 {
66 unsigned char bit;
67 int index;
68
69 // Initialize bitmap. Bit 0 is always 1 which corresponds to '\0'
70 for (BITMAP64[0] = index = 1; index < n; index++)
71 BITMAP64[index] = 0;
72
73 // Set bits in bitmap corresponding to the characters in s2
74 for (; *s2 != '\0'; s2++) {
75 index = WHICH8(*s2);
76 bit = WHICH_BIT(*s2);
77 bitmap[index] = bitmap[index] | bit;
78 }
79 }
80
81 /** The strcspn function computes the length of the maximum initial segment of
82 the string pointed to by s1 which consists entirely of characters not from
83 the string pointed to by s2.
84
85 @return The strcspn function returns the length of the segment.
86 **/
87 size_t
strcspn(const char * s1,const char * s2)88 strcspn(const char *s1, const char *s2)
89 {
90 UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
91 const char *str;
92 UINT8 bit;
93 int index;
94
95 if(*s1 == '\0') return 0;
96
97 BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
98
99 for(str = s1; ; str++) {
100 index = WHICH8(*str);
101 bit = WHICH_BIT(*str);
102 if ((bitmap[index] & bit) != 0)
103 break;
104 }
105 return (str - s1);
106 }
107
108 /** The strpbrk function locates the first occurrence in the string pointed to
109 by s1 of any character from the string pointed to by s2.
110
111 @return The strpbrk function returns a pointer to the character, or a
112 null pointer if no character from s2 occurs in s1.
113 **/
114 char *
strpbrk(const char * s1,const char * s2)115 strpbrk(const char *s1, const char *s2)
116 {
117 UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
118 UINT8 bit;
119 int index;
120
121 BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
122
123 for( ; *s1 != '\0'; ++s1) {
124 index = WHICH8(*s1);
125 bit = WHICH_BIT(*s1);
126 if( (bitmap[index] & bit) != 0) {
127 return (char *)s1;
128 }
129 }
130 return NULL;
131 }
132
133 /** The strrchr function locates the last occurrence of c (converted to a char)
134 in the string pointed to by s. The terminating null character is considered
135 to be part of the string.
136
137 @return The strrchr function returns a pointer to the character, or a
138 null pointer if c does not occur in the string.
139 **/
140 char *
strrchr(const char * s,int c)141 strrchr(const char *s, int c)
142 {
143 char *found = NULL;
144 char tgt = (char)c;
145
146 do {
147 if( *s == tgt) found = (char *)s;
148 } while( *s++ != '\0');
149
150 return found;
151 }
152
153 /** The strspn function computes the length of the maximum initial segment of
154 the string pointed to by s1 which consists entirely of characters from the
155 string pointed to by s2.
156
157 @return The strspn function returns the length of the segment.
158 **/
159 size_t
strspn(const char * s1,const char * s2)160 strspn(const char *s1 , const char *s2)
161 {
162 UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
163 size_t length = 0;
164 int index;
165 UINT8 bit;
166
167 BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
168
169 for( ; *s1 != '\0'; ++s1) {
170 index = WHICH8(*s1);
171 bit = WHICH_BIT(*s1);
172 if( (bitmap[index] & bit) == 0) break;
173 ++length;
174 }
175 return length;
176 }
177
178 /** The strstr function locates the first occurrence in the string pointed to
179 by s1 of the sequence of characters (excluding the terminating null
180 character) in the string pointed to by s2.
181
182 @return The strstr function returns a pointer to the located string, or a
183 null pointer if the string is not found. If s2 points to a string
184 with zero length, the function returns s1.
185 **/
186 char *
strstr(const char * s1,const char * s2)187 strstr(const char *s1 , const char *s2)
188 {
189 return AsciiStrStr( s1, s2);
190 }
191
192 /** A sequence of calls to the strtok function breaks the string pointed to by
193 s1 into a sequence of tokens, each of which is delimited by a character
194 from the string pointed to by s2. The first call in the sequence has a
195 non-null first argument; subsequent calls in the sequence have a null first
196 argument. The separator string pointed to by s2 may be different from call
197 to call.
198
199 The first call in the sequence searches the string pointed to by s1 for the
200 first character that is not contained in the current separator string
201 pointed to by s2. If no such character is found, then there are no tokens
202 in the string pointed to by s1 and the strtok function returns a null
203 pointer. If such a character is found, it is the start of the first token.
204
205 The strtok function then searches from there for a character that is
206 contained in the current separator string. If no such character is found,
207 the current token extends to the end of the string pointed to by s1, and
208 subsequent searches for a token will return a null pointer. If such a
209 character is found, it is overwritten by a null character, which terminates
210 the current token. The strtok function saves a pointer to the following
211 character, from which the next search for a token will start.
212
213 Each subsequent call, with a null pointer as the value of the first
214 argument, starts searching from the saved pointer and behaves as
215 described above.
216
217 @return The strtok function returns a pointer to the first character of a
218 token, or a null pointer if there is no token.
219 **/
220 char *
strtok(char * __restrict s1,const char * __restrict s2)221 strtok(char * __restrict s1, const char * __restrict s2)
222 {
223 static char *Next = NULL;
224 UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
225 char *Token = NULL;
226 int index;
227 UINT8 bit;
228
229 if( (s1 == NULL)
230 && ((s1 = Next) == NULL))
231 {
232 return NULL;
233 }
234
235 // s2 can be different on each call, so build the bitmap each time.
236 BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
237
238 // skip leading delimiters: all chars in s2
239 for( ; *s1 != '\0'; ++s1) {
240 index = WHICH8(*s1);
241 bit = WHICH_BIT(*s1);
242 if( (bitmap[index] & bit) == 0) break;
243 }
244 if( *s1 != 0)
245 {
246 // Remember this point, it is the start of the token
247 Token = s1++;
248
249 // find the next delimiter and replace it with a '\0'
250 for( ; *s1 != '\0'; ++s1) {
251 index = WHICH8(*s1);
252 bit = WHICH_BIT(*s1);
253 if( (bitmap[index] & bit) != 0) {
254 *s1++ = '\0';
255 Next = s1;
256 return Token;
257 }
258 }
259 }
260 Next = NULL;
261 return Token;
262 }
263