X-Git-Url: http://git.pk910.de/?a=blobdiff_plain;f=ircd%2Fmatch.c;h=b585053c795348900039553fae8c29f037fea525;hb=a322aa5b01bd87d6538ec7071bc90107ff340efa;hp=566ecaa0d21cb5b3b4d9f4a6e9984f7fce30400d;hpb=592e569802dbc1d90a0095d6f8fed409d6bf8c39;p=ircu2.10.12-pk.git diff --git a/ircd/match.c b/ircd/match.c index 566ecaa..b585053 100644 --- a/ircd/match.c +++ b/ircd/match.c @@ -15,13 +15,18 @@ * 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" #include "match.h" #include "ircd_chattr.h" +#include "ircd_string.h" +#include "ircd_snprintf.h" + /* * mmatch() * @@ -43,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; @@ -117,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) || @@ -156,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--); - ; - - 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++; + int star_p; - 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! */ } /* @@ -223,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; @@ -273,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 @@ -297,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). @@ -343,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; @@ -436,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; @@ -519,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; @@ -590,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; @@ -649,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 */ @@ -697,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 */ }; @@ -720,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)) @@ -759,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; @@ -788,195 +841,24 @@ int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen) return 1; /* Auch... something left out ? Fail */ } -/* - * matchcompIP() - * Compiles an IP mask into an in_mask structure - * The given can either be: - * - An usual irc type mask, containing * and or ? - * - An ip number plus a /bitnumber part, that will only consider - * the first "bitnumber" bits of the IP (bitnumber must be in 0-31 range) - * - An ip numer plus a /ip.bit.mask.values that will consider - * only the bits marked as 1 in the ip.bit.mask.values - * In the last two cases both the ip number and the bitmask can specify - * less than 4 bytes, the missing bytes then default to zero, note that - * this is *different* from the way inet_aton() does and that this does - * NOT happen for normal IPmasks (not containing '/') - * If the returned value is zero the produced in_mask might match some IP, - * if it's nonzero it will never match anything (and the imask struct is - * set so that always fails). - * - * The returned structure contains 3 fields whose meaning is the following: - * im.mask = The bits considered significative in the IP - * im.bits = What these bits should look like to have a match - * im.fall = If zero means that the above information used as - * ((IP & im.mask) == im.bits) is enough to tell if the compiled - * mask matches the given IP, nonzero means that it is needed, - * in case they did match, to call also the usual text match - * functions, because the mask wasn't "completely compiled" - * - * They should be used like: - * matchcompIP(&im, mask); - * if ( ((IP & im.mask)!=im.bits)) || (im.fall&&match(mask,inet_ntoa(IP))) ) - * { handle_non_match } else { handle_match }; - * instead of: - * if ( match(mask, inet_ntoa(IP)) ) - * { handle_non_match } else { handle_match }; - * - * Note: This function could be smarter when dealing with complex masks, - * this implementation is quite lazy and understands only very simple - * cases, whatever contains a ? anywhere or contains a '*' that isn't - * part of a trailing '.*' will fallback to text-match, this could be - * avoided for masks like 12?3.5.6 12.*.3.4 1.*.*.2 72?72?72?72 and - * so on that "could" be completely compiled to IP masks. - * If you try to improve this be aware of the fact that ? and * - * could match both dots and digits and we _must_ always reject - * what doesn't match in textform (like leading zeros and so on), - * so it's a LOT more tricky than it might seem. By now most common - * cases are optimized. +/** 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 matchcompIP(struct in_mask *imask, const char *mask) +int ipmask_check(const struct irc_in_addr *addr, const struct irc_in_addr *mask, unsigned char bits) { - const char *m = mask; - unsigned int bits = 0; - unsigned int filt = 0; - int unco = 0; - int digits = 0; - int shift = 24; - int tmp = 0; - - do - { - switch (*m) - { - case '\\': - if ((m[1] == '\\') || (m[1] == '*') || (m[1] == '?') - || (m[1] == '\0')) - break; - continue; - case '0': - case '1': - case '2': - case '3': - case '4': - case '5': - case '6': - case '7': - case '8': - case '9': - if (digits && !tmp) /* Leading zeros */ - break; - digits++; - tmp *= 10; - tmp += (*m - '0'); /* Can't overflow, INT_MAX > 2559 */ - if (tmp > 255) - break; - continue; - case '\0': - filt = 0xFFFFFFFF; - /* Intentional fallthrough */ - case '.': - if ((!shift) != (!*m)) - break; - /* Intentional fallthrough */ - case '/': - bits |= (tmp << shift); - shift -= 8; - digits = 0; - tmp = 0; - if (*m != '/') - continue; - shift = 24; - do - { - m++; - if (IsDigit(*m)) - { - if (digits && !tmp) /* Leading zeros */ - break; - digits++; - tmp *= 10; - tmp += (*m - '0'); /* Can't overflow, INT_MAX > 2559 */ - if (tmp > 255) - break; - } - else - { - switch (*m) - { - case '.': - case '\0': - if ((!shift) && (*m)) - break; - filt |= (tmp << shift); - shift -= 8; - tmp = 0; - digits = 0; - continue; - default: - break; - } - break; - } - } - while (*m); - if (*m) - break; - if (filt && (!(shift < 16)) && (!(filt & 0xE0FFFFFF))) - filt = 0xFFFFFFFF << (32 - ((filt >> 24))); - bits &= filt; - continue; - case '?': - unco = 1; - /* Intentional fallthrough */ - case '*': - if (digits) - unco = 1; - filt = (0xFFFFFFFF << (shift)) << 8; - while (*++m) - { - if (IsDigit(*m)) - unco = 1; - else - { - switch (*m) - { - case '.': - if (m[1] != '*') - unco = 1; - if (!shift) - break; - shift -= 8; - continue; - case '?': - unco = 1; - case '*': - continue; - default: - break; - } - break; - } - } - if (*m) - break; - continue; - default: - break; - } - - /* If we get here there is some error and this can't ever match */ - filt = 0; - bits = ~0; - unco = 0; - break; /* This time break the loop :) */ + int k; + for (k = 0; k < 8; k++) { + if (bits < 16) + 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)) + return 1; } - while (*m++); - - imask->bits.s_addr = htonl(bits); - imask->mask.s_addr = htonl(filt); - imask->fall = unco; - return ((bits & ~filt) ? -1 : 0); - + return -1; }