1 /* Copyright (C) 1991-1993, 1996-1999, 2000 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Library General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
8
9 This 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 Library General Public License for more details.
13
14 You should have received a copy of the GNU Library General Public
15 License along with this library; see the file COPYING.LIB. If not,
16 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 Boston, MA 02111-1307, USA. */
18
19 # include "system.h"
20 # include <ctype.h>
21 # include <stdlib.h>
22 # include <string.h>
23
24 /* Find the first occurrence of C in S or the final NUL byte. */
25 static inline char *
__strchrnul(const char * s,int c)26 __strchrnul (const char *s, int c)
27 {
28 const unsigned char *char_ptr;
29 const unsigned long int *longword_ptr;
30 unsigned long int longword, magic_bits, charmask;
31
32 c = (unsigned char) c;
33
34 /* Handle the first few characters by reading one character at a time.
35 Do this until CHAR_PTR is aligned on a longword boundary. */
36 for (char_ptr = (const unsigned char *)s; ((unsigned long int) char_ptr
37 & (sizeof (longword) - 1)) != 0;
38 ++char_ptr)
39 if (*char_ptr == c || *char_ptr == '\0')
40 return (void *) char_ptr;
41
42 /* All these elucidatory comments refer to 4-byte longwords,
43 but the theory applies equally well to 8-byte longwords. */
44
45 longword_ptr = (unsigned long int *) char_ptr;
46
47 /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits
48 the "holes." Note that there is a hole just to the left of
49 each byte, with an extra at the end:
50
51 bits: 01111110 11111110 11111110 11111111
52 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
53
54 The 1-bits make sure that carries propagate to the next 0-bit.
55 The 0-bits provide holes for carries to fall into. */
56 switch (sizeof (longword))
57 {
58 case 4: magic_bits = 0x7efefeffL; break;
59 case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
60 default:
61 abort ();
62 }
63
64 /* Set up a longword, each of whose bytes is C. */
65 charmask = c | (c << 8);
66 charmask |= charmask << 16;
67 if (sizeof (longword) > 4)
68 /* Do the shift in two steps to avoid a warning if long has 32 bits. */
69 charmask |= (charmask << 16) << 16;
70 if (sizeof (longword) > 8)
71 abort ();
72
73 /* Instead of the traditional loop which tests each character,
74 we will test a longword at a time. The tricky part is testing
75 if *any of the four* bytes in the longword in question are zero. */
76 for (;;)
77 {
78 /* We tentatively exit the loop if adding MAGIC_BITS to
79 LONGWORD fails to change any of the hole bits of LONGWORD.
80
81 1) Is this safe? Will it catch all the zero bytes?
82 Suppose there is a byte with all zeros. Any carry bits
83 propagating from its left will fall into the hole at its
84 least significant bit and stop. Since there will be no
85 carry from its most significant bit, the LSB of the
86 byte to the left will be unchanged, and the zero will be
87 detected.
88
89 2) Is this worthwhile? Will it ignore everything except
90 zero bytes? Suppose every byte of LONGWORD has a bit set
91 somewhere. There will be a carry into bit 8. If bit 8
92 is set, this will carry into bit 16. If bit 8 is clear,
93 one of bits 9-15 must be set, so there will be a carry
94 into bit 16. Similarly, there will be a carry into bit
95 24. If one of bits 24-30 is set, there will be a carry
96 into bit 31, so all of the hole bits will be changed.
97
98 The one misfire occurs when bits 24-30 are clear and bit
99 31 is set; in this case, the hole at bit 31 is not
100 changed. If we had access to the processor carry flag,
101 we could close this loophole by putting the fourth hole
102 at bit 32!
103
104 So it ignores everything except 128's, when they're aligned
105 properly.
106
107 3) But wait! Aren't we looking for C as well as zero?
108 Good point. So what we do is XOR LONGWORD with a longword,
109 each of whose bytes is C. This turns each byte that is C
110 into a zero. */
111
112 longword = *longword_ptr++;
113
114 /* Add MAGIC_BITS to LONGWORD. */
115 if ((((longword + magic_bits)
116
117 /* Set those bits that were unchanged by the addition. */
118 ^ ~longword)
119
120 /* Look at only the hole bits. If any of the hole bits
121 are unchanged, most likely one of the bytes was a
122 zero. */
123 & ~magic_bits) != 0 ||
124
125 /* That caught zeroes. Now test for C. */
126 ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
127 & ~magic_bits) != 0)
128 {
129 /* Which of the bytes was C or zero?
130 If none of them were, it was a misfire; continue the search. */
131
132 const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
133
134 if (*cp == c || *cp == '\0')
135 return (char *) cp;
136 if (*++cp == c || *cp == '\0')
137 return (char *) cp;
138 if (*++cp == c || *cp == '\0')
139 return (char *) cp;
140 if (*++cp == c || *cp == '\0')
141 return (char *) cp;
142 if (sizeof (longword) > 4)
143 {
144 if (*++cp == c || *cp == '\0')
145 return (char *) cp;
146 if (*++cp == c || *cp == '\0')
147 return (char *) cp;
148 if (*++cp == c || *cp == '\0')
149 return (char *) cp;
150 if (*++cp == c || *cp == '\0')
151 return (char *) cp;
152 }
153 }
154 }
155
156 /* This should never happen. */
157 return NULL;
158 }
159
160 /* For platform which support the ISO C amendement 1 functionality we
161 support user defined character classes. */
162 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
163 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
164 # include <wchar.h>
165 # include <wctype.h>
166 #endif
167
168 /* Comment out all this code if we are using the GNU C Library, and are not
169 actually compiling the library itself. This code is part of the GNU C
170 Library, but also included in many other GNU distributions. Compiling
171 and linking in this code is a waste when using the GNU C library
172 (especially if it is a shared library). Rather than having every GNU
173 program understand `configure --with-gnu-libc' and omit the object files,
174 it is simpler to just do this in the source for each such file. */
175
176 #if defined _LIBC || !defined __GNU_LIBRARY__
177
178
179 # if defined STDC_HEADERS || !defined isascii
180 # define ISASCII(c) 1
181 # else
182 # define ISASCII(c) isascii(c)
183 # endif
184
185 #ifdef isblank
186 # define ISBLANK(c) (ISASCII (c) && isblank (c))
187 #else
188 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
189 #endif
190 #ifdef isgraph
191 # define ISGRAPH(c) (ISASCII (c) && isgraph (c))
192 #else
193 # define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
194 #endif
195
196 #define ISPRINT(c) (ISASCII (c) && isprint (c))
197 #define ISDIGIT(c) (ISASCII (c) && isdigit (c))
198 #define ISALNUM(c) (ISASCII (c) && isalnum (c))
199 #define ISALPHA(c) (ISASCII (c) && isalpha (c))
200 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
201 #define ISLOWER(c) (ISASCII (c) && islower (c))
202 #define ISPUNCT(c) (ISASCII (c) && ispunct (c))
203 #define ISSPACE(c) (ISASCII (c) && isspace (c))
204 #define ISUPPER(c) (ISASCII (c) && isupper (c))
205 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
206
207 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
208
209 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
210 /* The GNU C library provides support for user-defined character classes
211 and the functions from ISO C amendement 1. */
212 # ifdef CHARCLASS_NAME_MAX
213 # define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
214 # else
215 /* This shouldn't happen but some implementation might still have this
216 problem. Use a reasonable default value. */
217 # define CHAR_CLASS_MAX_LENGTH 256
218 # endif
219
220 # ifdef _LIBC
221 # define IS_CHAR_CLASS(string) __wctype (string)
222 # else
223 # define IS_CHAR_CLASS(string) wctype (string)
224 # endif
225 # else
226 # define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
227
228 # define IS_CHAR_CLASS(string) \
229 (STREQ (string, "alpha") || STREQ (string, "upper") \
230 || STREQ (string, "lower") || STREQ (string, "digit") \
231 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
232 || STREQ (string, "space") || STREQ (string, "print") \
233 || STREQ (string, "punct") || STREQ (string, "graph") \
234 || STREQ (string, "cntrl") || STREQ (string, "blank"))
235 # endif
236
237 /* Avoid depending on library functions or files
238 whose names are inconsistent. */
239
240 # if !defined _LIBC && !defined getenv
241 extern char *getenv ();
242 # endif
243
244 # ifndef errno
245 extern int errno;
246 # endif
247
248 /* Match STRING against the filename pattern PATTERN, returning zero if
249 it matches, nonzero if not. */
250 static int
251 #ifdef _LIBC
252 internal_function
253 #endif
internal_fnmatch(const char * pattern,const char * string,int no_leading_period,int flags)254 internal_fnmatch (const char *pattern, const char *string,
255 int no_leading_period, int flags)
256 {
257 register const char *p = pattern, *n = string;
258 register unsigned char c;
259
260 /* Note that this evaluates C many times. */
261 # ifdef _LIBC
262 # define FOLD(c) ((flags & FNM_CASEFOLD) ? tolower (c) : (c))
263 # else
264 # define FOLD(c) ((flags & FNM_CASEFOLD) && ISUPPER (c) ? tolower (c) : (c))
265 # endif
266
267 while ((c = *p++) != '\0')
268 {
269 c = FOLD (c);
270
271 switch (c)
272 {
273 case '?':
274 if (*n == '\0')
275 return FNM_NOMATCH;
276 else if (*n == '/' && (flags & FNM_FILE_NAME))
277 return FNM_NOMATCH;
278 else if (*n == '.' && no_leading_period
279 && (n == string
280 || (n[-1] == '/' && (flags & FNM_FILE_NAME))))
281 return FNM_NOMATCH;
282 break;
283
284 case '\\':
285 if (!(flags & FNM_NOESCAPE))
286 {
287 c = *p++;
288 if (c == '\0')
289 /* Trailing \ loses. */
290 return FNM_NOMATCH;
291 c = FOLD (c);
292 }
293 if (FOLD ((unsigned char) *n) != c)
294 return FNM_NOMATCH;
295 break;
296
297 case '*':
298 if (*n == '.' && no_leading_period
299 && (n == string
300 || (n[-1] == '/' && (flags & FNM_FILE_NAME))))
301 return FNM_NOMATCH;
302
303 for (c = *p++; c == '?' || c == '*'; c = *p++)
304 {
305 if (*n == '/' && (flags & FNM_FILE_NAME))
306 /* A slash does not match a wildcard under FNM_FILE_NAME. */
307 return FNM_NOMATCH;
308 else if (c == '?')
309 {
310 /* A ? needs to match one character. */
311 if (*n == '\0')
312 /* There isn't another character; no match. */
313 return FNM_NOMATCH;
314 else
315 /* One character of the string is consumed in matching
316 this ? wildcard, so *??? won't match if there are
317 less than three characters. */
318 ++n;
319 }
320 }
321
322 if (c == '\0')
323 /* The wildcard(s) is/are the last element of the pattern.
324 If the name is a file name and contains another slash
325 this does mean it cannot match. If the FNM_LEADING_DIR
326 flag is set and exactly one slash is following, we have
327 a match. */
328 {
329 int result = (flags & FNM_FILE_NAME) == 0 ? 0 : FNM_NOMATCH;
330
331 if (flags & FNM_FILE_NAME)
332 {
333 const char *slashp = strchr (n, '/');
334
335 if (flags & FNM_LEADING_DIR)
336 {
337 if (slashp != NULL
338 && strchr (slashp + 1, '/') == NULL)
339 result = 0;
340 }
341 else
342 {
343 if (slashp == NULL)
344 result = 0;
345 }
346 }
347
348 return result;
349 }
350 else
351 {
352 const char *endp;
353
354 endp = __strchrnul (n, (flags & FNM_FILE_NAME) ? '/' : '\0');
355
356 if (c == '[')
357 {
358 int flags2 = ((flags & FNM_FILE_NAME)
359 ? flags : (flags & ~FNM_PERIOD));
360
361 for (--p; n < endp; ++n)
362 if (internal_fnmatch (p, n,
363 (no_leading_period
364 && (n == string
365 || (n[-1] == '/'
366 && (flags
367 & FNM_FILE_NAME)))),
368 flags2)
369 == 0)
370 return 0;
371 }
372 else if (c == '/' && (flags & FNM_FILE_NAME))
373 {
374 while (*n != '\0' && *n != '/')
375 ++n;
376 if (*n == '/'
377 && (internal_fnmatch (p, n + 1, flags & FNM_PERIOD,
378 flags) == 0))
379 return 0;
380 }
381 else
382 {
383 int flags2 = ((flags & FNM_FILE_NAME)
384 ? flags : (flags & ~FNM_PERIOD));
385
386 if (c == '\\' && !(flags & FNM_NOESCAPE))
387 c = *p;
388 c = FOLD (c);
389 for (--p; n < endp; ++n)
390 if (FOLD ((unsigned char) *n) == c
391 && (internal_fnmatch (p, n,
392 (no_leading_period
393 && (n == string
394 || (n[-1] == '/'
395 && (flags
396 & FNM_FILE_NAME)))),
397 flags2) == 0))
398 return 0;
399 }
400 }
401
402 /* If we come here no match is possible with the wildcard. */
403 return FNM_NOMATCH;
404
405 case '[':
406 {
407 /* Nonzero if the sense of the character class is inverted. */
408 static int posixly_correct;
409 register int not;
410 char cold;
411
412 if (posixly_correct == 0)
413 posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
414
415 if (*n == '\0')
416 return FNM_NOMATCH;
417
418 if (*n == '.' && no_leading_period && (n == string
419 || (n[-1] == '/'
420 && (flags
421 & FNM_FILE_NAME))))
422 return FNM_NOMATCH;
423
424 if (*n == '/' && (flags & FNM_FILE_NAME))
425 /* `/' cannot be matched. */
426 return FNM_NOMATCH;
427
428 not = (*p == '!' || (posixly_correct < 0 && *p == '^'));
429 if (not)
430 ++p;
431
432 c = *p++;
433 for (;;)
434 {
435 unsigned char fn = FOLD ((unsigned char) *n);
436
437 if (!(flags & FNM_NOESCAPE) && c == '\\')
438 {
439 if (*p == '\0')
440 return FNM_NOMATCH;
441 c = FOLD ((unsigned char) *p);
442 ++p;
443
444 if (c == fn)
445 goto matched;
446 }
447 else if (c == '[' && *p == ':')
448 {
449 /* Leave room for the null. */
450 char str[CHAR_CLASS_MAX_LENGTH + 1];
451 size_t c1 = 0;
452 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
453 wctype_t wt;
454 # endif
455 const char *startp = p;
456
457 for (;;)
458 {
459 if (c1 == CHAR_CLASS_MAX_LENGTH)
460 /* The name is too long and therefore the pattern
461 is ill-formed. */
462 return FNM_NOMATCH;
463
464 c = *++p;
465 if (c == ':' && p[1] == ']')
466 {
467 p += 2;
468 break;
469 }
470 if (c < 'a' || c >= 'z')
471 {
472 /* This cannot possibly be a character class name.
473 Match it as a normal range. */
474 p = startp;
475 c = '[';
476 goto normal_bracket;
477 }
478 str[c1++] = c;
479 }
480 str[c1] = '\0';
481
482 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
483 wt = IS_CHAR_CLASS (str);
484 if (wt == 0)
485 /* Invalid character class name. */
486 return FNM_NOMATCH;
487
488 if (__iswctype (__btowc ((unsigned char) *n), wt))
489 goto matched;
490 # else
491 if ((STREQ (str, "alnum") && ISALNUM ((unsigned char) *n))
492 || (STREQ (str, "alpha") && ISALPHA ((unsigned char) *n))
493 || (STREQ (str, "blank") && ISBLANK ((unsigned char) *n))
494 || (STREQ (str, "cntrl") && ISCNTRL ((unsigned char) *n))
495 || (STREQ (str, "digit") && ISDIGIT ((unsigned char) *n))
496 || (STREQ (str, "graph") && ISGRAPH ((unsigned char) *n))
497 || (STREQ (str, "lower") && ISLOWER ((unsigned char) *n))
498 || (STREQ (str, "print") && ISPRINT ((unsigned char) *n))
499 || (STREQ (str, "punct") && ISPUNCT ((unsigned char) *n))
500 || (STREQ (str, "space") && ISSPACE ((unsigned char) *n))
501 || (STREQ (str, "upper") && ISUPPER ((unsigned char) *n))
502 || (STREQ (str, "xdigit") && ISXDIGIT ((unsigned char) *n)))
503 goto matched;
504 # endif
505 }
506 else if (c == '\0')
507 /* [ (unterminated) loses. */
508 return FNM_NOMATCH;
509 else
510 {
511 c = FOLD (c);
512 normal_bracket:
513 if (c == fn)
514 goto matched;
515
516 cold = c;
517 c = *p++;
518
519 if (c == '-' && *p != ']')
520 {
521 /* It is a range. */
522 char lo[2];
523 char fc[2];
524 unsigned char cend = *p++;
525 if (!(flags & FNM_NOESCAPE) && cend == '\\')
526 cend = *p++;
527 if (cend == '\0')
528 return FNM_NOMATCH;
529
530 lo[0] = cold;
531 lo[1] = '\0';
532 fc[0] = fn;
533 fc[1] = '\0';
534 if (strcoll (lo, fc) <= 0)
535 {
536 char hi[2];
537 hi[0] = FOLD (cend);
538 hi[1] = '\0';
539 if (strcoll (fc, hi) <= 0)
540 goto matched;
541 }
542
543 c = *p++;
544 }
545 }
546
547 if (c == ']')
548 break;
549 }
550
551 if (!not)
552 return FNM_NOMATCH;
553 break;
554
555 matched:
556 /* Skip the rest of the [...] that already matched. */
557 while (c != ']')
558 {
559 if (c == '\0')
560 /* [... (unterminated) loses. */
561 return FNM_NOMATCH;
562
563 c = *p++;
564 if (!(flags & FNM_NOESCAPE) && c == '\\')
565 {
566 if (*p == '\0')
567 return FNM_NOMATCH;
568 /* XXX 1003.2d11 is unclear if this is right. */
569 ++p;
570 }
571 else if (c == '[' && *p == ':')
572 {
573 do
574 if (*++p == '\0')
575 return FNM_NOMATCH;
576 while (*p != ':' || p[1] == ']');
577 p += 2;
578 c = *p;
579 }
580 }
581 if (not)
582 return FNM_NOMATCH;
583 }
584 break;
585
586 default:
587 if (c != FOLD ((unsigned char) *n))
588 return FNM_NOMATCH;
589 }
590
591 ++n;
592 }
593
594 if (*n == '\0')
595 return 0;
596
597 if ((flags & FNM_LEADING_DIR) && *n == '/')
598 /* The FNM_LEADING_DIR flag says that "foo*" matches "foobar/frobozz". */
599 return 0;
600
601 return FNM_NOMATCH;
602
603 # undef FOLD
604 }
605
606
607 int
fnmatch(const char * pattern,const char * string,int flags)608 fnmatch (const char *pattern, const char *string, int flags)
609 {
610 return internal_fnmatch (pattern, string, flags & FNM_PERIOD, flags);
611 }
612
613 #endif /* _LIBC or not __GNU_LIBRARY__. */
614