ircd/match.c

   1 /*
   2  * IRC - Internet Relay Chat, common/match.c
   3  * Copyright (C) 1990 Jarkko Oikarinen
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 1, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 /** @file
  20  * @brief Functions to match strings against IRC mask strings.
  21  * @version $Id$
  22  */
  23 #include "config.h"
  24
  25 #include "match.h"
  26 #include "ircd_chattr.h"
  27 #include "ircd_string.h"
  28 #include "ircd_snprintf.h"
  29
  30 /*
  31  * mmatch()
  32  *
  33  * Written by Run (carlo@runaway.xs4all.nl), 25-10-96
  34  *
  35  *
  36  * From: Carlo Wood <carlo@runaway.xs4all.nl>
  37  * Message-Id: <199609021026.MAA02393@runaway.xs4all.nl>
  38  * Subject: [C-Com] Analysis for `mmatch' (was: gline4 problem)
  39  * To: coder-com@mail.undernet.org (coder committee)
  40  * Date: Mon, 2 Sep 1996 12:26:01 +0200 (MET DST)
  41  *
  42  * We need a new function `mmatch(const char *old_mask, const char *new_mask)'
  43  * which returns `true' likewise the current `match' (start with copying it),
  44  * but which treats '*' and '?' in `new_mask' differently (not "\*" and "\?" !)
  45  * as follows:  a '*' in `new_mask' does not match a '?' in `old_mask' and
  46  * a '?' in `new_mask' does not match a '\?' in `old_mask'.
  47  * And ofcourse... a '*' in `new_mask' does not match a '\*' in `old_mask'...
  48  * And last but not least, '\?' and '\*' in `new_mask' now become one character.
  49  */
  50
  51 /** Compares one mask against another.
  52  * One wildcard mask may be said to be a superset of another if the
  53  * set of strings matched by the first is a proper superset of the set
  54  * of strings matched by the second.  In practical terms, this means
  55  * that the second is made redundant by the first.
  56  *
  57  * The logic for this test is similar to that in match(), but a
  58  * backslash in old_mask only matches a backslash in new_mask (and
  59  * requires the next character to match exactly), and -- after
  60  * contiguous runs of wildcards are logically collapsed -- a '?' in
  61  * old_mask does not match a '*' in new_mask.
  62  *
  63  * @param[in] old_mask One wildcard mask.
  64  * @param[in] new_mask Another wildcard mask.
  65  * @return Zero if \a old_mask is a superset of \a new_mask, non-zero otherwise.
  66  */
  67 int mmatch(const char *old_mask, const char *new_mask)
  68 {
  69   const char *m = old_mask;
  70   const char *n = new_mask;
  71   const char *ma = m;
  72   const char *na = n;
  73   int wild = 0;
  74   int mq = 0, nq = 0;
  75
  76   while (1)
  77   {
  78     if (*m == '*')
  79     {
  80       while (*m == '*')
  81         m++;
  82       wild = 1;
  83       ma = m;
  84       na = n;
  85     }
  86
  87     if (!*m)
  88     {
  89       if (!*n)
  90         return 0;
  91       for (m--; (m > old_mask) && (*m == '?'); m--)
  92         ;
  93       if ((*m == '*') && (m > old_mask) && (m[-1] != '\\'))
  94         return 0;
  95       if (!wild)
  96         return 1;
  97       m = ma;
  98
  99       /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
 100       if ((*na == '\\') && ((na[1] == '*') || (na[1] == '?')))
 101         ++na;
 102
 103       n = ++na;
 104     }
 105     else if (!*n)
 106     {
 107       while (*m == '*')
 108         m++;
 109       return (*m != 0);
 110     }
 111     if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 112     {
 113       m++;
 114       mq = 1;
 115     }
 116     else
 117       mq = 0;
 118
 119     /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
 120     if ((*n == '\\') && ((n[1] == '*') || (n[1] == '?')))
 121     {
 122       n++;
 123       nq = 1;
 124     }
 125     else
 126       nq = 0;
 127
 128 /*
 129  * This `if' has been changed compared to match() to do the following:
 130  * Match when:
 131  *   old (m)         new (n)         boolean expression
 132  *    *               any             (*m == '*' && !mq) ||
 133  *    ?               any except '*'  (*m == '?' && !mq && (*n != '*' || nq)) ||
 134  * any except * or ?  same as m       (!((*m == '*' || *m == '?') && !mq) &&
 135  *                                      ToLower(*m) == ToLower(*n) &&
 136  *                                        !((mq && !nq) || (!mq && nq)))
 137  *
 138  * Here `any' also includes \* and \? !
 139  *
 140  * After reworking the boolean expressions, we get:
 141  * (Optimized to use boolean shortcircuits, with most frequently occuring
 142  *  cases upfront (which took 2 hours!)).
 143  */
 144     if ((*m == '*' && !mq) ||
 145         ((!mq || nq) && ToLower(*m) == ToLower(*n)) ||
 146         (*m == '?' && !mq && (*n != '*' || nq)))
 147     {
 148       if (*m)
 149         m++;
 150       if (*n)
 151         n++;
 152     }
 153     else
 154     {
 155       if (!wild)
 156         return 1;
 157       m = ma;
 158
 159       /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
 160       if ((*na == '\\') && ((na[1] == '*') || (na[1] == '?')))
 161         ++na;
 162
 163       n = ++na;
 164     }
 165   }
 166 }
 167
 168 /*
 169  * Compare if a given string (name) matches the given
 170  * mask (which can contain wild cards: '*' - match any
 171  * number of chars, '?' - match any single character.
 172  *
 173  * return  0, if match
 174  *         1, if no match
 175  *
 176  *  Originally by Douglas A Lewis (dalewis@acsu.buffalo.edu)
 177  *  Rewritten by Timothy Vogelsang (netski), net@astrolink.org
 178  */
 179
 180 /** Check a string against a mask.
 181  * This test checks using traditional IRC wildcards only: '*' means
 182  * match zero or more characters of any type; '?' means match exactly
 183  * one character of any type.  A backslash escapes the next character
 184  * so that a wildcard may be matched exactly.
 185  * @param[in] mask Wildcard-containing mask.
 186  * @param[in] name String to check against \a mask.
 187  * @return Zero if \a mask matches \a name, non-zero if no match.
 188  */
 189 int match(const char *mask, const char *name)
 190 {
 191   const char *m = mask, *n = name;
 192   const char *m_tmp = mask, *n_tmp = name;
 193   int wild = 0;
 194
 195   for (;;)
 196   {
 197     if (*m == '*') {
 198       while (*m == '*')  /* clean up any additional wildcards */
 199         m++;
 200
 201       m_tmp = m;
 202       n_tmp = n;
 203       wild = 1;
 204     }
 205     if (*m == '\\')  /* next wildcard is disregarded */
 206       m++;
 207
 208     if (!*m) {
 209       if (!*n)
 210         return 0;  /* match */
 211
 212       for (m--; (m > mask) && (*m == '?'); m--);
 213         ;
 214
 215       if (*m == '*' && (m > mask))
 216         return 0;  /* match */
 217
 218       if (!wild)
 219         return 1;
 220
 221       m = m_tmp;
 222       n = ++n_tmp;
 223     }
 224     else if (!*n) {
 225       while (*m == '*')  /* clean up any additional wildcards */
 226         m++;
 227
 228       return (*m != 0);
 229     }
 230     if (ToLower(*m) != ToLower(*n) && *m != '?') {
 231       if (!wild)
 232         return 1;  /* failure! */
 233
 234       m = m_tmp;
 235       n = ++n_tmp;
 236     }
 237     else {
 238       if (*m)
 239         m++;
 240       if (*n)
 241         n++;
 242     }
 243   }
 244
 245   return 1;  /* no match! */
 246 }
 247
 248 /*
 249  * collapse()
 250  * Collapse a pattern string into minimal components.
 251  * This particular version is "in place", so that it changes the pattern
 252  * which is to be reduced to a "minimal" size.
 253  *
 254  * (C) Carlo Wood - 6 Oct 1998
 255  * Speedup rewrite by Andrea Cocito, December 1998.
 256  * Note that this new optimized alghoritm can *only* work in place.
 257  */
 258
 259 /** Collapse a mask string to remove redundancies.
 260  * Specifically, it replaces a sequence of '*' followed by additional
 261  * '*' or '?' with the same number of '?'s as the input, followed by
 262  * one '*'.  This minimizes useless backtracking when matching later.
 263  * @param[in,out] mask Mask string to collapse.
 264  * @return Pointer to the start of the string.
 265  */
 266 char *collapse(char *mask)
 267 {
 268   int star = 0;
 269   char *m = mask;
 270   char *b;
 271
 272   if (m)
 273   {
 274     do
 275     {
 276       if ((*m == '*') && ((m[1] == '*') || (m[1] == '?')))
 277       {
 278         b = m;
 279         do
 280         {
 281           if (*m == '*')
 282             star = 1;
 283           else
 284           {
 285             if (star && (*m != '?'))
 286             {
 287               *b++ = '*';
 288               star = 0;
 289             };
 290             *b++ = *m;
 291             if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 292               *b++ = *++m;
 293           };
 294         }
 295         while (*m++);
 296         break;
 297       }
 298       else
 299       {
 300         if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 301           m++;
 302       };
 303     }
 304     while (*m++);
 305   };
 306   return mask;
 307 }
 308
 309 /*
 310  ***************** Nemesi's matchcomp() / matchexec() **************
 311  */
 312
 313 /** @page compiledmasks Compiled Masks
 314  * These functions allow the use of "compiled" masks, you compile a mask
 315  * by means of matchcomp() that gets the plain text mask as input and writes
 316  * its result in the memory locations addressed by the 3 parameters:
 317  * - *cmask will contain the text of the compiled mask
 318  * - *minlen will contain the lenght of the shortest string that can match
 319  *   the mask
 320  * - *charset will contain the minimal set of chars needed to match the mask
 321  * You can pass NULL as *charset and it will be simply not returned, but you
 322  * MUST pass valid pointers for *minlen and *cmask (wich must be big enough
 323  * to contain the compiled mask text that is in the worst case as long as the
 324  * text of the mask itself in plaintext format) and the return value of
 325  * matchcomp() will be the number of chars actually written there (excluded
 326  * the trailing zero). cmask can be == mask, matchcomp() can work in place.
 327  * The {cmask, minlen} couple of values make the real compiled mask and
 328  * need to be passed to the functions that use the compiled mask, if you pass
 329  * the wrong minlen or something wrong in cmask to one of these expect a
 330  * coredump. This means that when you record a compiled mask you must store
 331  * *both* these values.
 332  * Once compiled the mask can be used to match a string by means of
 333  * matchexec(), it can be printed back to human-readable format by means
 334  * of sprintmatch() or it can be compared to another compiled mask by means
 335  * of mmexec() that will tell if it completely overrides that mask (a lot like
 336  * what mmatch() does for plain text masks).
 337  * You can gain a lot of speed in many situations avoiding to matchexec() when:
 338  * - The maximum lenght of the field you are about to match() the mask to is
 339  *   shorter than minlen, in example when matching abc*def*ghil with a nick:
 340  *   It just cannot match since a nick is at most 9 chars long and the mask
 341  *   needs at least 10 chars (10 will be the value returned in minlen).
 342  * - The charset allowed for the field you are about to match to doesn't
 343  *   "contain" the charset returned by matchcomp(), in example when you
 344  *   have *.* as mask it makes no sense to try to match it against a nick
 345  *   because, again, a nick can't contain a '.', you can check this with
 346  *   a simple (charset & NTL_IRCNK) in this case.
 347  * - As a special case, since compiled masks are forced to lowercase,
 348  *   it would make no sense to use the NTL_LOWER and NTL_UPPER on a compiled
 349  *   mask, thus they are reused as follows: if the NTL_LOWER bit of charset
 350  *   is set it means that the mask contains only non-wilds chars (i.e. you can
 351  *   use strCasecmp() to match it or a direct hash lookup), if the NTL_UPPER
 352  *   bit is set it means that it contains only wild chars (and you can
 353  *   match it with strlen(field)>=minlen).
 354  * Do these optimizations ONLY when the data you are about to pass to
 355  * matchexec() are *known* to be invalid in advance, using strChattr()
 356  * or strlen() on the text would be slower than calling matchexec() directly
 357  * and let it fail.
 358  * Internally a compiled mask contain in the *cmask area the text of
 359  * the plain text form of the mask itself with applied the following hacks:
 360  * - All characters are forced to lowercase (so that uppercase letters and
 361  *   specifically the symbols 'A' and 'Z' are reserved for special use)
 362  * - All non-escaped stars '*' are replaced by the letter 'Z'
 363  * - All non-escaped question marks '?' are replaced by the letter 'A'
 364  * - All escape characters are removed, the wilds escaped by them are
 365  *   then passed by without the escape since they don't collide anymore
 366  *   with the real wilds (encoded as A/Z)
 367  * - Finally the part of the mask that follows the last asterisk is
 368  *   reversed (byte order mirroring) and moved right after the first
 369  *   asterisk.
 370  * After all this a mask like:   Head*CHUNK1*chu\*nK2*ch??k3*TaIl
 371  *               .... becomes:   headZliatZchunk1Zchu*nk2ZchAAk3
 372  * This can still be printed on a console, more or less understood by an
 373  * human and handled with the usual str*() library functions.
 374  * When you store somewhere the compiled mask you can avoid storing the
 375  * textform of it since it can be "decompiled" by means of sprintmatch(),
 376  * but at that time the following things are changed in the mask:
 377  * - All chars have been forced to lowercase.
 378  * - The mask is collapsed.
 379  * The balance point of using compiled masks in terms of CPU is when you expect
 380  * to use matchexec() instead of match() at least 20 times on the same mask
 381  * or when you expect to use mmexec() instead of mmatch() 3 times.
 382  */
 383
 384 /** Compile a mask for faster matching.
 385  * See also @ref compiledmasks.
 386  * @param[out] cmask Output buffer for compiled mask.
 387  * @param[out] minlen Minimum length of matching strings.
 388  * @param[out] charset Character attributes used in compiled mask.
 389  * @param[out] mask Input mask.
 390  * @return Length of compiled mask, not including NUL terminator.
 391  */
 392 int matchcomp(char *cmask, int *minlen, int *charset, const char *mask)
 393 {
 394   const char *m = mask;
 395   char *b = cmask;
 396   char *fs = 0;
 397   char *ls = 0;
 398   char *x1, *x2;
 399   int l1, l2, lmin, loop, sign;
 400   int star = 0;
 401   int cnt = 0;
 402   char ch;
 403   int chset = ~0;
 404   int chset2 = (NTL_LOWER | NTL_UPPER);
 405
 406   if (m)
 407     while ((ch = *m++))
 408       switch (ch)
 409       {
 410         case '*':
 411           star = 1;
 412           break;
 413         case '?':
 414           cnt++;
 415           *b++ = 'A';
 416           chset2 &= ~NTL_LOWER;
 417           break;
 418         case '\\':
 419           if ((*m == '?') || (*m == '*'))
 420             ch = *m++;
 421         default:
 422           if (star)
 423           {
 424             ls = b;
 425             fs = fs ? fs : b;
 426             *b++ = 'Z';
 427             chset2 &= ~NTL_LOWER;
 428             star = 0;
 429           };
 430           cnt++;
 431           *b = ToLower(ch);
 432           chset &= IRCD_CharAttrTab[*b++ - CHAR_MIN];
 433           chset2 &= ~NTL_UPPER;
 434       };
 435
 436   if (charset)
 437     *charset = (chset | chset2);
 438
 439   if (star)
 440   {
 441     ls = b;
 442     fs = (fs ? fs : b);
 443     *b++ = 'Z';
 444   };
 445
 446   if (ls)
 447   {
 448     for (x1 = ls + 1, x2 = (b - 1); x1 < x2; x1++, x2--)
 449     {
 450       ch = *x1;
 451       *x1 = *x2;
 452       *x2 = ch;
 453     };
 454     l1 = (ls - fs);
 455     l2 = (b - ls);
 456     x1 = fs;
 457     while ((lmin = (l1 < l2) ? l1 : l2))
 458     {
 459       x2 = x1 + l1;
 460       for (loop = 0; loop < lmin; loop++)
 461       {
 462         ch = x1[loop];
 463         x1[loop] = x2[loop];
 464         x2[loop] = ch;
 465       };
 466       x1 += lmin;
 467       sign = l1 - l2;
 468       l1 -= (sign < 0) ? 0 : lmin;
 469       l2 -= (sign > 0) ? 0 : lmin;
 470     };
 471   };
 472
 473   *b = '\0';
 474   *minlen = cnt;
 475   return (b - cmask);
 476
 477 }
 478
 479 /** Compare a string to a compiled mask.
 480  * If \a cmask is not from matchcomp(), or if \a minlen is not the value
 481  * passed out of matchcomp(), this may core.
 482  * See also @ref compiledmasks.
 483  * @param[in] string String to test.
 484  * @param[in] cmask Compiled mask string.
 485  * @param[in] minlen Minimum length of strings that match \a cmask.
 486  * @return Zero if the string matches, non-zero otherwise.
 487  */
 488 int matchexec(const char *string, const char *cmask, int minlen)
 489 {
 490   const char *s = string - 1;
 491   const char *b = cmask - 1;
 492   int trash;
 493   const char *bb, *bs;
 494   char ch;
 495
 496 tryhead:
 497   while ((ToLower(*++s) == *++b) && *s);
 498   if (!*s)
 499     return ((*b != '\0') && ((*b++ != 'Z') || (*b != '\0')));
 500   if (*b != 'Z')
 501   {
 502     if (*b == 'A')
 503       goto tryhead;
 504     return 1;
 505   };
 506
 507   bs = s;
 508   while (*++s);
 509
 510   if ((trash = (s - string - minlen)) < 0)
 511     return 2;
 512
 513 trytail:
 514   while ((ToLower(*--s) == *++b) && *b && (ToLower(*--s) == *++b) && *b
 515       && (ToLower(*--s) == *++b) && *b && (ToLower(*--s) == *++b) && *b);
 516   if (*b != 'Z')
 517   {
 518     if (*b == 'A')
 519       goto trytail;
 520     return (*b != '\0');
 521   };
 522
 523   s = --bs;
 524   bb = b;
 525
 526   while ((ch = *++b))
 527   {
 528     while ((ToLower(*++s) != ch))
 529       if (--trash < 0)
 530         return 4;
 531     bs = s;
 532
 533 trychunk:
 534     while ((ToLower(*++s) == *++b) && *b);
 535     if (!*b)
 536       return 0;
 537     if (*b == 'Z')
 538     {
 539       bs = --s;
 540       bb = b;
 541       continue;
 542     };
 543     if (*b == 'A')
 544       goto trychunk;
 545
 546     b = bb;
 547     s = bs;
 548     if (--trash < 0)
 549       return 5;
 550   };
 551
 552   return 0;
 553 }
 554
 555 /*
 556  * matchdecomp()
 557  * Prints the human readable version of *cmask into *mask, (decompiles
 558  * cmask).
 559  * The area pointed by *mask MUST be big enough (the mask might be up to
 560  * twice the size of its compiled form if it's made all of \? or \*, and
 561  * this function can NOT work in place since it might enflate the mask)
 562  * The printed mask is not identical to the one that was compiled to cmask,
 563  * infact it is 1) forced to all lowercase, 2) collapsed, both things
 564  * are supposed to NOT change it's meaning.
 565  * It returns the number of chars actually written to *mask;
 566  */
 567
 568 /** Decompile a compiled mask into printable form.
 569  * See also @ref compiledmasks.
 570  * @param[out] mask Output mask buffer.
 571  * @param[in] cmask Compiled mask.
 572  * @return Number of characters written to \a mask.
 573  */
 574 int matchdecomp(char *mask, const char *cmask)
 575 {
 576   char *rtb = mask;
 577   const char *rcm = cmask;
 578   const char *begtail, *endtail;
 579
 580   if (rtb ==0)
 581     return (-1);
 582
 583   if (rcm == 0)
 584     return (-2);
 585
 586   for (; (*rcm != 'Z'); rcm++, rtb++)
 587   {
 588     if ((*rcm == '?') || (*rcm == '*'))
 589       *rtb++ = '\\';
 590     if (!((*rtb = ((*rcm == 'A') ? '?' : *rcm))))
 591       return (rtb - mask);
 592   };
 593
 594   begtail = rcm++;
 595   *rtb++ = '*';
 596
 597   while (*rcm && (*rcm != 'Z'))
 598     rcm++;
 599
 600   endtail = rcm;
 601
 602   if (*rcm)
 603   {
 604     while (*++rcm)
 605       switch (*rcm)
 606       {
 607         case 'A':
 608           *rtb++ = '?';
 609           break;
 610         case 'Z':
 611           *rtb++ = '*';
 612           break;
 613         case '*':
 614         case '?':
 615           *rtb++ = '\\';
 616         default:
 617           *rtb++ = *rcm;
 618       };
 619     *rtb++ = '*';
 620   };
 621
 622   for (rcm = endtail; (--rcm) > begtail; *rtb++ = ((*rcm == 'A') ? '?' : *rcm))
 623     if ((*rcm == '?') || (*rcm == '*'))
 624       *rtb++ = '\\';
 625
 626   *rtb = '\0';
 627   return (rtb - mask);
 628 }
 629
 630 /*
 631  * mmexec()
 632  * Checks if a wider compiled mask (wcm/wminlen) completely overrides
 633  * a more restrict one (rcm/rminlen), basically what mmatch() does for
 634  * non-compiled masks, returns 0 if the override is true (like mmatch()).
 635  * "the wider overrides the restrict" means that any string that matches
 636  * the restrict one _will_ also match the wider one, always.
 637  * In this we behave differently from mmatch() because in example we return
 638  * true for " a?*cd overrides a*bcd " for wich the override happens for how
 639  * we literally defined it, here mmatch() would have returned false.
 640  * The original concepts and the base alghoritm are copied from mmatch()
 641  * written by Run (Carlo Wood), this function is written by
 642  * Nemesi (Andrea Cocito)
 643  */
 644 /** Tests for a superset relationship between compiled masks.  This
 645  * function does for compiled masks what mmatch() is does for normal
 646  * masks.
 647  * See also @ref compiledmasks.
 648  * @param[in] wcm Compiled mask believed to be wider.
 649  * @param[in] wminlen Minimum match length for \a wcm.
 650  * @param[in] rcm Compiled mask believed to be restricted.
 651  * @param[in] rminlen Minimum match length for \a rcm.
 652  * @return Zero if \a wcm is a superset of \a rcm, non-zero if not.
 653  */
 654 int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen)
 655 {
 656   const char *w, *r, *br, *bw, *rx, *rz;
 657   int eat, trash;
 658
 659   /* First of all rm must have enough non-stars to 'contain' wm */
 660   if ((trash = rminlen - wminlen) < 0)
 661     return 1;
 662   w = wcm;
 663   r = rcm;
 664   eat = 0;
 665
 666   /* Let's start the game, remember that '*' is mapped to 'Z', '?'
 667      is mapped to 'A' and that head?*??*?chunk*???*tail becomes
 668      headAAAAZliatAAAZchunk for compiled masks */
 669
 670   /* Match the head of wm with the head of rm */
 671   for (; (*r) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); r++, w++);
 672   if (*r == 'Z')
 673     while (*w == 'A')           /* Eat extra '?' before '*' in wm if got '*' in rm */
 674       w++, eat++;
 675   if (*w != 'Z')                /* head1<any>.. can't match head2<any>.. */
 676     return ((*w) || (*r)) ? 1 : 0;      /* and head<nul> matches only head<nul> */
 677   if (!*++w)
 678     return 0;                   /* headZ<nul> matches head<anything>    */
 679
 680   /* Does rm have any stars in it ? let's check */
 681   for (rx = r; *r && (*r != 'Z'); r++);
 682   if (!*r)
 683   {
 684     /* rm has no stars and thus isn't a mask but it's just a flat
 685        string: special handling occurs here, note that eat must be 0 here */
 686
 687     /* match the tail */
 688     if (*w != 'Z')
 689     {
 690       for (; r--, (*w) && ((*w == *r) || (*w == 'A')); w++);
 691       if (*w != 'Z')            /* headZliat1<any> fails on head<any>2tail  */
 692         return (*w) ? 1 : 0;    /* but headZliat<nul> matches head<any>tail */
 693     }
 694
 695     /* match the chunks */
 696     while (1)
 697     {                           /* This loop can't break but only return   */
 698
 699       for (bw = w++; (*w != *rx); rx++) /* Seek the 1st char of the chunk */
 700         if (--trash < 0)        /* See if we can trash one more char of rm */
 701           return 1;             /* If not we can only fail of course       */
 702       for (r = ++rx, w++; (*w) && ((*w == *r) || (*w == 'A')); r++, w++);
 703       if (!*w)                  /* Did last loop match the rest of chunk ? */
 704         return 0;               /* ... Yes, end of wm, matched !           */
 705       if (*w != 'Z')
 706       {                         /* ... No, hitted non-star                 */
 707         w = bw;                 /* Rollback at beginning of chunk          */
 708         if (--trash < 0)        /* Trashed the char where this try started */
 709           return 1;             /* if we can't trash more chars fail       */
 710       }
 711       else
 712       {
 713         rx = r;                 /* Successfully matched a chunk, move rx   */
 714       }                 /* and go on with the next one             */
 715     }
 716   }
 717
 718   /* rm has at least one '*' and thus is a 'real' mask */
 719   rz = r++;                     /* rx = unused of head, rz = beg-tail */
 720
 721   /* Match the tail of wm (if any) against the tail of rm */
 722   if (*w != 'Z')
 723   {
 724     for (; (*w) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); w++, r++);
 725     if (*r == 'Z')              /* extra '?' before tail are fluff, just flush 'em */
 726       while (*w == 'A')
 727         w++;
 728     if (*w != 'Z')              /* We aren't matching a chunk, can't rollback      */
 729       return (*w) ? 1 : 0;
 730   }
 731
 732   /* Match the chunks of wm against what remains of the head of rm */
 733   while (1)
 734   {
 735     bw = w;
 736     for (bw++; (rx < rz) && (*bw != *rx); rx++) /* Seek the first           */
 737       if (--trash < 0)          /* waste some trash reserve */
 738         return 1;
 739     if (!(rx < rz))             /* head finished            */
 740       break;
 741     for (bw++, (br = ++rx);
 742         (br < rz) && (*bw) && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 743     if (!(br < rz))             /* Note that we didn't use any 'eat' char yet, if  */
 744       while (*bw == 'A')        /* there were eat-en chars the head would be over  */
 745         bw++, eat++;            /* Happens only at end of head, and eat is still 0 */
 746     if (!*bw)
 747       return 0;
 748     if (*bw != 'Z')
 749     {
 750       eat = 0;
 751       if (!(br < rz))
 752       {                         /* If we failed because we got the end of head */
 753         trash -= (br - rx);     /* it makes no sense to rollback, just trash   */
 754         if (--trash < 0)        /* all the rest of the head wich isn't long    */
 755           return 1;             /* enough for this chunk and go out of this    */
 756         break;                  /* loop, then we try with the chunks of rm     */
 757       };
 758       if (--trash < 0)
 759         return 1;
 760     }
 761     else
 762     {
 763       w = bw;
 764       rx = br;
 765     }
 766   }
 767
 768   /* Match the unused chunks of wm against the chunks of rm */
 769   rx = r;
 770   for (; *r && (*r != 'Z'); r++);
 771   rz = r;
 772   if (*r++)
 773   {
 774     while (*r)
 775     {
 776       bw = w;
 777       while (eat && *r)         /* the '?' we had eated make us skip as many chars */
 778         if (*r++ != 'Z')        /* here, but can't skip stars or trailing zero     */
 779           eat--;
 780       for (bw++; (*r) && (*bw != *r); r++)
 781         if ((*r != 'Z') && (--trash < 0))
 782           return 1;
 783       if (!*r)
 784         break;
 785       for ((br = ++r), bw++;
 786           (*br) && (*br != 'Z') && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 787       if (*br == 'Z')
 788         while (*bw == 'A')
 789           bw++, eat++;
 790       if (!*bw)
 791         return 0;
 792       if (*bw != 'Z')
 793       {
 794         eat = 0;
 795         if ((!*br) || (*r == 'Z'))
 796         {                       /* If we hit the end of rm or a star in it */
 797           trash -= (br - r);    /* makes no sense to rollback within this  */
 798           if (trash < 0)        /* same chunk of br, skip it all and then  */
 799             return 1;           /* either rollback or break this loop if   */
 800           if (!*br)             /* it was the end of rm                    */
 801             break;
 802           r = br;
 803         }
 804         if (--trash < 0)
 805           return 1;
 806       }
 807       else
 808       {
 809         r = br;
 810         w = bw;
 811       }
 812     }
 813   }
 814
 815   /* match the remaining chunks of wm against what remains of the tail of rm */
 816   r = rz - eat - 1;             /* can't have <nul> or 'Z'within the tail, so just move r */
 817   while (r >= rx)
 818   {
 819     bw = w;
 820     for (bw++; (*bw != *r); r--)
 821       if (--trash < 0)
 822         return 1;
 823     if (!(r >= rx))
 824       return 1;
 825     for ((br = --r), bw++;
 826         (*bw) && (br >= rx) && ((*bw == *br) || (*bw == 'A')); br--, bw++);
 827     if (!*bw)
 828       return 0;
 829     if (!(br >= rx))
 830       return 1;
 831     if (*bw != 'Z')
 832     {
 833       if (--trash < 0)
 834         return 1;
 835     }
 836     else
 837     {
 838       r = br;
 839       w = bw;
 840     }
 841   }
 842   return 1;                     /* Auch... something left out ? Fail */
 843 }
 844
 845 #include <stdio.h>
 846 #include <stdlib.h>
 847 #include <string.h>
 848 #include <sys/socket.h>
 849 #include <netinet/in.h>
 850
 851 /** Parse an input string as an IPv4 address.
 852  * @param[in] in Text form of address.
 853  * @param[out] out IPv4 address in network representation.
 854  * @return Number of address bits specified by \a in.
 855  */
 856 static int ipmask_parse_ipv4(const char *in, struct in_addr *out)
 857 {
 858   int class;
 859   int ad[4] = { 0 };
 860   int bits = 0;
 861
 862   class = sscanf(in, "%d.%d.%d.%d/%d", &ad[0], &ad[1], &ad[2], &ad[3], &bits);
 863   if (class != 5)
 864     bits = class * 8;
 865   out->s_addr = ntohl((ad[0] << 24) | (ad[1] << 16) | (ad[2] << 8) | ad[3]);
 866   return bits;
 867 }
 868
 869 /** Test whether a string looks like it matches only IPv4 addresses.
 870  * @param[in] mask Hostname matching mask.
 871  * @return Non-zero if \a mask can only match IPv4 addresses, zero otherwise.
 872  */
 873 int check_if_ipmask(const char *mask)
 874 {
 875   int has_digit = 0;
 876   const char *p;
 877
 878   for (p = mask; *p; ++p)
 879     if (*p != '*' && *p != '?' && *p != '.' && *p != '/')
 880     {
 881       if (!IsDigit(*p))
 882         return 0;
 883       has_digit = -1;
 884     }
 885
 886   return has_digit;
 887 }
 888
 889 /** Try to parse an IPv4 or IPv6 address mask.
 890  * @param[in] in Address matching mask.
 891  * @param[out] mask Fixed bits of address mask.
 892  * @param[out] bits_ptr If non-NULL, receives number of bits specified in address mask.
 893  * @return Non-zero on successful parse; zero on error.
 894  */
 895 int ipmask_parse(const char *in, struct irc_in_addr *mask, unsigned char *bits_ptr)
 896 {
 897   struct in_addr ipv4;
 898   char *p;
 899   int bits = 0;
 900
 901   if (check_if_ipmask(in)) {
 902     bits = ipmask_parse_ipv4(in, &ipv4);
 903     mask->in6_16[0] = mask->in6_16[1] = mask->in6_16[2] = 0;
 904     mask->in6_16[3] = mask->in6_16[4] = 0;
 905     mask->in6_16[5] = 0xffff;
 906     memcpy(&mask->in6_16[6], &ipv4.s_addr, sizeof(ipv4.s_addr));
 907     bits += 96;
 908   } else if (in[0] == '*' && in[1] == '\0') {
 909     /* accept as a 0-bit mask */
 910   } else {
 911     if (!(p = strchr(in, '/')))
 912       bits = 128;
 913     else
 914       *p = 0;
 915     if (!ircd_aton(mask, in)) {
 916       if (p)
 917         *p = '/';
 918       return 0;
 919     }
 920     if (p) {
 921       bits = atoi(p + 1);
 922       *p = '/';
 923     }
 924   }
 925
 926   if (bits_ptr)
 927     *bits_ptr = bits;
 928   return 1;
 929 }
 930
 931 /** Test whether an address matches the most significant bits of a mask.
 932  * @param[in] addr Address to test.
 933  * @param[in] mask Address to test against.
 934  * @param[in] bits Number of bits to test.
 935  * @return 0 on mismatch, 1 if bits < 128 and all bits match; -1 if
 936  * bits == 128 and all bits match.
 937  */
 938 int ipmask_check(const struct irc_in_addr *addr, const struct irc_in_addr *mask, unsigned char bits)
 939 {
 940   int k;
 941
 942   for (k = 0; k < 8; k++) {
 943     if (bits < 16)
 944       return (addr->in6_16[k] & htons(0xffff << (16-bits))) == mask->in6_16[k];
 945     if (addr->in6_16[k] != mask->in6_16[k])
 946       return 0;
 947     if (!(bits -= 16))
 948       return 1;
 949   }
 950   return -1;
 951 }