cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

glob.c (3616B)

      1#include <linux/module.h>
      2#include <linux/glob.h>
      3
      4/*
      5 * The only reason this code can be compiled as a module is because the
      6 * ATA code that depends on it can be as well.  In practice, they're
      7 * both usually compiled in and the module overhead goes away.
      8 */
      9MODULE_DESCRIPTION("glob(7) matching");
     10MODULE_LICENSE("Dual MIT/GPL");
     11
     12/**
     13 * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0)
     14 * @pat: Shell-style pattern to match, e.g. "*.[ch]".
     15 * @str: String to match.  The pattern must match the entire string.
     16 *
     17 * Perform shell-style glob matching, returning true (1) if the match
     18 * succeeds, or false (0) if it fails.  Equivalent to !fnmatch(@pat, @str, 0).
     19 *
     20 * Pattern metacharacters are ?, *, [ and \.
     21 * (And, inside character classes, !, - and ].)
     22 *
     23 * This is small and simple implementation intended for device blacklists
     24 * where a string is matched against a number of patterns.  Thus, it
     25 * does not preprocess the patterns.  It is non-recursive, and run-time
     26 * is at most quadratic: strlen(@str)*strlen(@pat).
     27 *
     28 * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa");
     29 * it takes 6 passes over the pattern before matching the string.
     30 *
     31 * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT
     32 * treat / or leading . specially; it isn't actually used for pathnames.
     33 *
     34 * Note that according to glob(7) (and unlike bash), character classes
     35 * are complemented by a leading !; this does not support the regex-style
     36 * [^a-z] syntax.
     37 *
     38 * An opening bracket without a matching close is matched literally.
     39 */
     40bool __pure glob_match(char const *pat, char const *str)
     41{
     42	/*
     43	 * Backtrack to previous * on mismatch and retry starting one
     44	 * character later in the string.  Because * matches all characters
     45	 * (no exception for /), it can be easily proved that there's
     46	 * never a need to backtrack multiple levels.
     47	 */
     48	char const *back_pat = NULL, *back_str;
     49
     50	/*
     51	 * Loop over each token (character or class) in pat, matching
     52	 * it against the remaining unmatched tail of str.  Return false
     53	 * on mismatch, or true after matching the trailing nul bytes.
     54	 */
     55	for (;;) {
     56		unsigned char c = *str++;
     57		unsigned char d = *pat++;
     58
     59		switch (d) {
     60		case '?':	/* Wildcard: anything but nul */
     61			if (c == '\0')
     62				return false;
     63			break;
     64		case '*':	/* Any-length wildcard */
     65			if (*pat == '\0')	/* Optimize trailing * case */
     66				return true;
     67			back_pat = pat;
     68			back_str = --str;	/* Allow zero-length match */
     69			break;
     70		case '[': {	/* Character class */
     71			bool match = false, inverted = (*pat == '!');
     72			char const *class = pat + inverted;
     73			unsigned char a = *class++;
     74
     75			/*
     76			 * Iterate over each span in the character class.
     77			 * A span is either a single character a, or a
     78			 * range a-b.  The first span may begin with ']'.
     79			 */
     80			do {
     81				unsigned char b = a;
     82
     83				if (a == '\0')	/* Malformed */
     84					goto literal;
     85
     86				if (class[0] == '-' && class[1] != ']') {
     87					b = class[1];
     88
     89					if (b == '\0')
     90						goto literal;
     91
     92					class += 2;
     93					/* Any special action if a > b? */
     94				}
     95				match |= (a <= c && c <= b);
     96			} while ((a = *class++) != ']');
     97
     98			if (match == inverted)
     99				goto backtrack;
    100			pat = class;
    101			}
    102			break;
    103		case '\\':
    104			d = *pat++;
    105			fallthrough;
    106		default:	/* Literal character */
    107literal:
    108			if (c == d) {
    109				if (d == '\0')
    110					return true;
    111				break;
    112			}
    113backtrack:
    114			if (c == '\0' || !back_pat)
    115				return false;	/* No point continuing */
    116			/* Try again from last *, one character later in str. */
    117			pat = back_pat;
    118			str = ++back_str;
    119			break;
    120		}
    121	}
    122}
    123EXPORT_SYMBOL(glob_match);