match.c

   1 /*
   2  * Author: Tatu Ylonen <ylo@cs.hut.fi>
   3  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
   4  *                    All rights reserved
   5  * Simple pattern matching, with '*' and '?' as wildcards.
   6  *
   7  * As far as I am concerned, the code I have written for this software
   8  * can be used freely for any purpose.  Any derived versions of this
   9  * software must be clearly marked as such, and if the derived work is
  10  * incompatible with the protocol description in the RFC file, it must be
  11  * called by a name other than "ssh" or "Secure Shell".
  12  */
  13
  14 #include "includes.h"
  15 RCSID("$OpenBSD: match.c,v 1.11 2001/01/21 19:05:52 markus Exp $");
  16
  17 #include "match.h"
  18
  19 /*
  20  * Returns true if the given string matches the pattern (which may contain ?
  21  * and * as wildcards), and zero if it does not match.
  22  */
  23
  24 int
  25 match_pattern(const char *s, const char *pattern)
  26 {
  27         for (;;) {
  28                 /* If at end of pattern, accept if also at end of string. */
  29                 if (!*pattern)
  30                         return !*s;
  31
  32                 if (*pattern == '*') {
  33                         /* Skip the asterisk. */
  34                         pattern++;
  35
  36                         /* If at end of pattern, accept immediately. */
  37                         if (!*pattern)
  38                                 return 1;
  39
  40                         /* If next character in pattern is known, optimize. */
  41                         if (*pattern != '?' && *pattern != '*') {
  42                                 /*
  43                                  * Look instances of the next character in
  44                                  * pattern, and try to match starting from
  45                                  * those.
  46                                  */
  47                                 for (; *s; s++)
  48                                         if (*s == *pattern &&
  49                                             match_pattern(s + 1, pattern + 1))
  50                                                 return 1;
  51                                 /* Failed. */
  52                                 return 0;
  53                         }
  54                         /*
  55                          * Move ahead one character at a time and try to
  56                          * match at each position.
  57                          */
  58                         for (; *s; s++)
  59                                 if (match_pattern(s, pattern))
  60                                         return 1;
  61                         /* Failed. */
  62                         return 0;
  63                 }
  64                 /*
  65                  * There must be at least one more character in the string.
  66                  * If we are at the end, fail.
  67                  */
  68                 if (!*s)
  69                         return 0;
  70
  71                 /* Check if the next character of the string is acceptable. */
  72                 if (*pattern != '?' && *pattern != *s)
  73                         return 0;
  74
  75                 /* Move to the next character, both in string and in pattern. */
  76                 s++;
  77                 pattern++;
  78         }
  79         /* NOTREACHED */
  80 }
  81
  82 /*
  83  * Tries to match the host name (which must be in all lowercase) against the
  84  * comma-separated sequence of subpatterns (each possibly preceded by ! to
  85  * indicate negation).  Returns -1 if negation matches, 1 if there is
  86  * a positive match, 0 if there is no match at all.
  87  */
  88
  89 int
  90 match_hostname(const char *host, const char *pattern, u_int len)
  91 {
  92         char sub[1024];
  93         int negated;
  94         int got_positive;
  95         u_int i, subi;
  96
  97         got_positive = 0;
  98         for (i = 0; i < len;) {
  99                 /* Check if the subpattern is negated. */
 100                 if (pattern[i] == '!') {
 101                         negated = 1;
 102                         i++;
 103                 } else
 104                         negated = 0;
 105
 106                 /*
 107                  * Extract the subpattern up to a comma or end.  Convert the
 108                  * subpattern to lowercase.
 109                  */
 110                 for (subi = 0;
 111                      i < len && subi < sizeof(sub) - 1 && pattern[i] != ',';
 112                      subi++, i++)
 113                         sub[subi] = isupper(pattern[i]) ? tolower(pattern[i]) : pattern[i];
 114                 /* If subpattern too long, return failure (no match). */
 115                 if (subi >= sizeof(sub) - 1)
 116                         return 0;
 117
 118                 /* If the subpattern was terminated by a comma, skip the comma. */
 119                 if (i < len && pattern[i] == ',')
 120                         i++;
 121
 122                 /* Null-terminate the subpattern. */
 123                 sub[subi] = '\0';
 124
 125                 /* Try to match the subpattern against the host name. */
 126                 if (match_pattern(host, sub)) {
 127                         if (negated)
 128                                 return -1;              /* Negative */
 129                         else
 130                                 got_positive = 1;       /* Positive */
 131                 }
 132         }
 133
 134         /*
 135          * Return success if got a positive match.  If there was a negative
 136          * match, we have already returned -1 and never get here.
 137          */
 138         return got_positive;
 139 }