X-Git-Url: http://git.pk910.de/?a=blobdiff_plain;f=ircd%2Fmatch.c;h=b585053c795348900039553fae8c29f037fea525;hb=a322aa5b01bd87d6538ec7071bc90107ff340efa;hp=615a52f005f3750ef4e52f1f9b8cfd8231355df6;hpb=be28fad14b46a9012bc2367b609daef19e7646eb;p=ircu2.10.12-pk.git diff --git a/ircd/match.c b/ircd/match.c index 615a52f..b585053 100644 --- a/ircd/match.c +++ b/ircd/match.c @@ -15,8 +15,10 @@ * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - * - * $Id$ + */ +/** @file + * @brief Functions to match strings against IRC mask strings. + * @version $Id$ */ #include "config.h" @@ -46,6 +48,22 @@ * And last but not least, '\?' and '\*' in `new_mask' now become one character. */ +/** Compares one mask against another. + * One wildcard mask may be said to be a superset of another if the + * set of strings matched by the first is a proper superset of the set + * of strings matched by the second. In practical terms, this means + * that the second is made redundant by the first. + * + * The logic for this test is similar to that in match(), but a + * backslash in old_mask only matches a backslash in new_mask (and + * requires the next character to match exactly), and -- after + * contiguous runs of wildcards are logically collapsed -- a '?' in + * old_mask does not match a '*' in new_mask. + * + * @param[in] old_mask One wildcard mask. + * @param[in] new_mask Another wildcard mask. + * @return Zero if \a old_mask is a superset of \a new_mask, non-zero otherwise. + */ int mmatch(const char *old_mask, const char *new_mask) { const char *m = old_mask; @@ -120,7 +138,7 @@ int mmatch(const char *old_mask, const char *new_mask) * Here `any' also includes \* and \? ! * * After reworking the boolean expressions, we get: - * (Optimized to use boolean shortcircuits, with most frequently occuring + * (Optimized to use boolean short-circuits, with most frequently occurring * cases upfront (which took 2 hours!)). */ if ((*m == '*' && !mq) || @@ -159,63 +177,71 @@ int mmatch(const char *old_mask, const char *new_mask) * Rewritten by Timothy Vogelsang (netski), net@astrolink.org */ +/** Check a string against a mask. + * This test checks using traditional IRC wildcards only: '*' means + * match zero or more characters of any type; '?' means match exactly + * one character of any type. A backslash escapes the next character + * so that a wildcard may be matched exactly. + * @param[in] mask Wildcard-containing mask. + * @param[in] name String to check against \a mask. + * @return Zero if \a mask matches \a name, non-zero if no match. + */ int match(const char *mask, const char *name) { const char *m = mask, *n = name; const char *m_tmp = mask, *n_tmp = name; - int wild = 0; - - for (;;) - { - if (*m == '*') { - while (*m == '*') /* clean up any additional wildcards */ - m++; - - m_tmp = m; - n_tmp = n; - wild = 1; - } - if (*m == '\\') /* next wildcard is disregarded */ - m++; - - if (!*m) { - if (!*n) - return 0; /* match */ - - for (m--; (m > mask) && (*m == '?'); m--); - ; + int star_p; - if (*m == '*' && (m > mask)) - return 0; /* match */ - - if (!wild) - return 1; - - m = m_tmp; - n = ++n_tmp; - } - else if (!*n) { - while (*m == '*') /* clean up any additional wildcards */ - m++; - - return (*m != 0); - } - if (ToLower(*m) != ToLower(*n) && *m != '?') { - if (!wild) - return 1; /* failure! */ - - m = m_tmp; - n = ++n_tmp; + for (;;) switch (*m) { + case '\0': + if (!*n) + return 0; + backtrack: + if (m_tmp == mask) + return 1; + m = m_tmp; + n = ++n_tmp; + if (*n == '\0') + return 1; + break; + case '\\': + m++; + /* allow escaping to force capitalization */ + if (*m++ != *n++) + goto backtrack; + break; + case '*': case '?': + for (star_p = 0; ; m++) { + if (*m == '*') + star_p = 1; + else if (*m == '?') { + if (!*n++) + goto backtrack; + } else break; } - else { - if (*m) - m++; - if (*n) - n++; + if (star_p) { + if (!*m) + return 0; + else if (*m == '\\') { + m_tmp = ++m; + if (!*m) + return 1; + for (n_tmp = n; *n && *n != *m; n++) ; + } else { + m_tmp = m; + for (n_tmp = n; *n && ToLower(*n) != ToLower(*m); n++) ; + } } + /* and fall through */ + default: + if (!*n) + return *m != '\0'; + if (ToLower(*m) != ToLower(*n)) + goto backtrack; + m++; + n++; + break; } - - return 1; /* no match! */ } /* @@ -226,9 +252,16 @@ int match(const char *mask, const char *name) * * (C) Carlo Wood - 6 Oct 1998 * Speedup rewrite by Andrea Cocito, December 1998. - * Note that this new optimized alghoritm can *only* work in place. + * Note that this new optimized algorithm can *only* work in place. */ +/** Collapse a mask string to remove redundancies. + * Specifically, it replaces a sequence of '*' followed by additional + * '*' or '?' with the same number of '?'s as the input, followed by + * one '*'. This minimizes useless backtracking when matching later. + * @param[in,out] mask Mask string to collapse. + * @return Pointer to the start of the string. + */ char *collapse(char *mask) { int star = 0; @@ -276,15 +309,16 @@ char *collapse(char *mask) ***************** Nemesi's matchcomp() / matchexec() ************** */ -/* These functions allow the use of "compiled" masks, you compile a mask +/** @page compiledmasks Compiled Masks + * These functions allow the use of "compiled" masks, you compile a mask * by means of matchcomp() that gets the plain text mask as input and writes * its result in the memory locations addressed by the 3 parameters: * - *cmask will contain the text of the compiled mask - * - *minlen will contain the lenght of the shortest string that can match + * - *minlen will contain the length of the shortest string that can match * the mask * - *charset will contain the minimal set of chars needed to match the mask * You can pass NULL as *charset and it will be simply not returned, but you - * MUST pass valid pointers for *minlen and *cmask (wich must be big enough + * MUST pass valid pointers for *minlen and *cmask (which must be big enough * to contain the compiled mask text that is in the worst case as long as the * text of the mask itself in plaintext format) and the return value of * matchcomp() will be the number of chars actually written there (excluded @@ -300,7 +334,7 @@ char *collapse(char *mask) * of mmexec() that will tell if it completely overrides that mask (a lot like * what mmatch() does for plain text masks). * You can gain a lot of speed in many situations avoiding to matchexec() when: - * - The maximum lenght of the field you are about to match() the mask to is + * - The maximum length of the field you are about to match() the mask to is * shorter than minlen, in example when matching abc*def*ghil with a nick: * It just cannot match since a nick is at most 9 chars long and the mask * needs at least 10 chars (10 will be the value returned in minlen). @@ -346,12 +380,14 @@ char *collapse(char *mask) * or when you expect to use mmexec() instead of mmatch() 3 times. */ - /* - * matchcomp() - * - * Compiles a mask into a form suitable for using in matchexec(). - */ - +/** Compile a mask for faster matching. + * See also @ref compiledmasks. + * @param[out] cmask Output buffer for compiled mask. + * @param[out] minlen Minimum length of matching strings. + * @param[out] charset Character attributes used in compiled mask. + * @param[out] mask Input mask. + * @return Length of compiled mask, not including NUL terminator. + */ int matchcomp(char *cmask, int *minlen, int *charset, const char *mask) { const char *m = mask; @@ -439,16 +475,15 @@ int matchcomp(char *cmask, int *minlen, int *charset, const char *mask) } -/* - * matchexec() - * - * Executes a match with a mask previosuly compiled with matchcomp() - * Note 1: If the mask isn't correctly produced by matchcomp() I will core - * Note 2: 'min' MUST be the value returned by matchcomp on that mask, - * or.... I will core even faster :-) - * Note 3: This piece of code is not intended to be nice but efficient. +/** Compare a string to a compiled mask. + * If \a cmask is not from matchcomp(), or if \a minlen is not the value + * passed out of matchcomp(), this may core. + * See also @ref compiledmasks. + * @param[in] string String to test. + * @param[in] cmask Compiled mask string. + * @param[in] minlen Minimum length of strings that match \a cmask. + * @return Zero if the string matches, non-zero otherwise. */ - int matchexec(const char *string, const char *cmask, int minlen) { const char *s = string - 1; @@ -522,13 +557,19 @@ trychunk: * cmask). * The area pointed by *mask MUST be big enough (the mask might be up to * twice the size of its compiled form if it's made all of \? or \*, and - * this function can NOT work in place since it might enflate the mask) + * this function can NOT work in place since it might inflate the mask) * The printed mask is not identical to the one that was compiled to cmask, - * infact it is 1) forced to all lowercase, 2) collapsed, both things + * in fact it is 1) forced to all lowercase, 2) collapsed, both things * are supposed to NOT change it's meaning. * It returns the number of chars actually written to *mask; */ +/** Decompile a compiled mask into printable form. + * See also @ref compiledmasks. + * @param[out] mask Output mask buffer. + * @param[in] cmask Compiled mask. + * @return Number of characters written to \a mask. + */ int matchdecomp(char *mask, const char *cmask) { char *rtb = mask; @@ -593,13 +634,22 @@ int matchdecomp(char *mask, const char *cmask) * "the wider overrides the restrict" means that any string that matches * the restrict one _will_ also match the wider one, always. * In this we behave differently from mmatch() because in example we return - * true for " a?*cd overrides a*bcd " for wich the override happens for how + * true for " a?*cd overrides a*bcd " for which the override happens for how * we literally defined it, here mmatch() would have returned false. - * The original concepts and the base alghoritm are copied from mmatch() + * The original concepts and the base algorithm are copied from mmatch() * written by Run (Carlo Wood), this function is written by * Nemesi (Andrea Cocito) */ - +/** Tests for a superset relationship between compiled masks. This + * function does for compiled masks what mmatch() is does for normal + * masks. + * See also @ref compiledmasks. + * @param[in] wcm Compiled mask believed to be wider. + * @param[in] wminlen Minimum match length for \a wcm. + * @param[in] rcm Compiled mask believed to be restricted. + * @param[in] rminlen Minimum match length for \a rcm. + * @return Zero if \a wcm is a superset of \a rcm, non-zero if not. + */ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) { const char *w, *r, *br, *bw, *rx, *rz; @@ -652,7 +702,7 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) if (!*w) /* Did last loop match the rest of chunk ? */ return 0; /* ... Yes, end of wm, matched ! */ if (*w != 'Z') - { /* ... No, hitted non-star */ + { /* ... No, hit non-star */ w = bw; /* Rollback at beginning of chunk */ if (--trash < 0) /* Trashed the char where this try started */ return 1; /* if we can't trash more chars fail */ @@ -700,7 +750,7 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) if (!(br < rz)) { /* If we failed because we got the end of head */ trash -= (br - rx); /* it makes no sense to rollback, just trash */ - if (--trash < 0) /* all the rest of the head wich isn't long */ + if (--trash < 0) /* all the rest of the head which isn't long */ return 1; /* enough for this chunk and go out of this */ break; /* loop, then we try with the chunks of rm */ }; @@ -723,8 +773,8 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) while (*r) { bw = w; - while (eat && *r) /* the '?' we had eated make us skip as many chars */ - if (*r++ != 'Z') /* here, but can't skip stars or trailing zero */ + while (eat && *r) /* the '?' we ate makes us skip as many chars */ + if (*r++ != 'Z') /* here, but can't skip stars or trailing zero */ eat--; for (bw++; (*r) && (*bw != *r); r++) if ((*r != 'Z') && (--trash < 0)) @@ -762,7 +812,7 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) } /* match the remaining chunks of wm against what remains of the tail of rm */ - r = rz - eat - 1; /* can't have or 'Z'within the tail, so just move r */ + r = rz - eat - 1; /* can't have or 'Z' within the tail, so just move r */ while (r >= rx) { bw = w; @@ -791,84 +841,20 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) return 1; /* Auch... something left out ? Fail */ } -#include -#include -#include -#include -#include -#include - -static int ipmask_parse_ipv4(const char *in, struct in_addr *out) -{ - int class; - char ipname[16]; - int ad[4] = { 0 }; - int bits = 0; - - class = sscanf(in, "%d.%d.%d.%d/%d", &ad[0], &ad[1], &ad[2], &ad[3], &bits); - if (class != 5) - bits = class * 8; - ircd_snprintf(0, ipname, sizeof(ipname), "%d.%d.%d.%d", ad[0], ad[1], ad[2], ad[3]); - out->s_addr = inet_addr(ipname); - return bits; -} - -int check_if_ipmask(const char *mask) -{ - int has_digit = 0; - const char *p; - - for (p = mask; *p; ++p) - if (*p != '*' && *p != '?' && *p != '.' && *p != '/') - { - if (!IsDigit(*p)) - return 0; - has_digit = -1; - } - - return has_digit; -} - -int ipmask_parse(const char *in, struct irc_in_addr *mask, unsigned char *bits_ptr) -{ - struct in_addr ipv4; - char *p; - int bits = 0; - - if (check_if_ipmask(in)) { - bits = ipmask_parse_ipv4(in, &ipv4); - mask->in6_16[0] = mask->in6_16[1] = mask->in6_16[2] = 0; - mask->in6_16[3] = mask->in6_16[4] = mask->in6_16[5] = 0; - memcpy(&mask->in6_16[6], &ipv4.s_addr, sizeof(ipv4.s_addr)); - bits += 96; - } else { - if (!(p = strchr(in, '/'))) - bits = 128; - else - *p = 0; - if (!ircd_aton(mask, in)) { - if (p) - *p = '/'; - return 0; - } - if (p) { - bits = atoi(p + 1); - *p = '/'; - } - } - - if (bits_ptr) - *bits_ptr = bits; - return 1; -} - +/** Test whether an address matches the most significant bits of a mask. + * @param[in] addr Address to test. + * @param[in] mask Address to test against. + * @param[in] bits Number of bits to test. + * @return 0 on mismatch, 1 if bits < 128 and all bits match; -1 if + * bits == 128 and all bits match. + */ int ipmask_check(const struct irc_in_addr *addr, const struct irc_in_addr *mask, unsigned char bits) { int k; for (k = 0; k < 8; k++) { if (bits < 16) - return (addr->in6_16[k] & ((unsigned char) (0xffff << (16-bits)))) == mask->in6_16[k]; + return !(htons(addr->in6_16[k] ^ mask->in6_16[k]) >> (16-bits)); if (addr->in6_16[k] != mask->in6_16[k]) return 0; if (!(bits -= 16))