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 short-circuits, with most frequently occurring
 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 star_p;
 194
 195   for (;;) switch (*m) {
 196   case '\0':
 197     if (!*n)
 198       return 0;
 199   backtrack:
 200     if (m_tmp == mask)
 201       return 1;
 202     m = m_tmp;
 203     n = ++n_tmp;
 204     if (*n == '\0')
 205       return 1;
 206     break;
 207   case '\\':
 208     m++;
 209     /* allow escaping to force capitalization */
 210     if (*m++ != *n++)
 211       goto backtrack;
 212     break;
 213   case '*': case '?':
 214     for (star_p = 0; ; m++) {
 215       if (*m == '*')
 216         star_p = 1;
 217       else if (*m == '?') {
 218         if (!*n++)
 219           goto backtrack;
 220       } else break;
 221     }
 222     if (star_p) {
 223       if (!*m)
 224         return 0;
 225       else if (*m == '\\') {
 226         m_tmp = ++m;
 227         if (!*m)
 228           return 1;
 229         for (n_tmp = n; *n && *n != *m; n++) ;
 230       } else {
 231         m_tmp = m;
 232         for (n_tmp = n; *n && ToLower(*n) != ToLower(*m); n++) ;
 233       }
 234     }
 235     /* and fall through */
 236   default:
 237     if (!*n)
 238       return *m != '\0';
 239     if (ToLower(*m) != ToLower(*n))
 240       goto backtrack;
 241     m++;
 242     n++;
 243     break;
 244   }
 245 }
 246
 247 /*
 248  * collapse()
 249  * Collapse a pattern string into minimal components.
 250  * This particular version is "in place", so that it changes the pattern
 251  * which is to be reduced to a "minimal" size.
 252  *
 253  * (C) Carlo Wood - 6 Oct 1998
 254  * Speedup rewrite by Andrea Cocito, December 1998.
 255  * Note that this new optimized algorithm can *only* work in place.
 256  */
 257
 258 /** Collapse a mask string to remove redundancies.
 259  * Specifically, it replaces a sequence of '*' followed by additional
 260  * '*' or '?' with the same number of '?'s as the input, followed by
 261  * one '*'.  This minimizes useless backtracking when matching later.
 262  * @param[in,out] mask Mask string to collapse.
 263  * @return Pointer to the start of the string.
 264  */
 265 char *collapse(char *mask)
 266 {
 267   int star = 0;
 268   char *m = mask;
 269   char *b;
 270
 271   if (m)
 272   {
 273     do
 274     {
 275       if ((*m == '*') && ((m[1] == '*') || (m[1] == '?')))
 276       {
 277         b = m;
 278         do
 279         {
 280           if (*m == '*')
 281             star = 1;
 282           else
 283           {
 284             if (star && (*m != '?'))
 285             {
 286               *b++ = '*';
 287               star = 0;
 288             };
 289             *b++ = *m;
 290             if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 291               *b++ = *++m;
 292           };
 293         }
 294         while (*m++);
 295         break;
 296       }
 297       else
 298       {
 299         if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 300           m++;
 301       };
 302     }
 303     while (*m++);
 304   };
 305   return mask;
 306 }
 307
 308 /*
 309  ***************** Nemesi's matchcomp() / matchexec() **************
 310  */
 311
 312 /** @page compiledmasks Compiled Masks
 313  * These functions allow the use of "compiled" masks, you compile a mask
 314  * by means of matchcomp() that gets the plain text mask as input and writes
 315  * its result in the memory locations addressed by the 3 parameters:
 316  * - *cmask will contain the text of the compiled mask
 317  * - *minlen will contain the length of the shortest string that can match
 318  *   the mask
 319  * - *charset will contain the minimal set of chars needed to match the mask
 320  * You can pass NULL as *charset and it will be simply not returned, but you
 321  * MUST pass valid pointers for *minlen and *cmask (which must be big enough
 322  * to contain the compiled mask text that is in the worst case as long as the
 323  * text of the mask itself in plaintext format) and the return value of
 324  * matchcomp() will be the number of chars actually written there (excluded
 325  * the trailing zero). cmask can be == mask, matchcomp() can work in place.
 326  * The {cmask, minlen} couple of values make the real compiled mask and
 327  * need to be passed to the functions that use the compiled mask, if you pass
 328  * the wrong minlen or something wrong in cmask to one of these expect a
 329  * coredump. This means that when you record a compiled mask you must store
 330  * *both* these values.
 331  * Once compiled the mask can be used to match a string by means of
 332  * matchexec(), it can be printed back to human-readable format by means
 333  * of sprintmatch() or it can be compared to another compiled mask by means
 334  * of mmexec() that will tell if it completely overrides that mask (a lot like
 335  * what mmatch() does for plain text masks).
 336  * You can gain a lot of speed in many situations avoiding to matchexec() when:
 337  * - The maximum length of the field you are about to match() the mask to is
 338  *   shorter than minlen, in example when matching abc*def*ghil with a nick:
 339  *   It just cannot match since a nick is at most 9 chars long and the mask
 340  *   needs at least 10 chars (10 will be the value returned in minlen).
 341  * - The charset allowed for the field you are about to match to doesn't
 342  *   "contain" the charset returned by matchcomp(), in example when you
 343  *   have *.* as mask it makes no sense to try to match it against a nick
 344  *   because, again, a nick can't contain a '.', you can check this with
 345  *   a simple (charset & NTL_IRCNK) in this case.
 346  * - As a special case, since compiled masks are forced to lowercase,
 347  *   it would make no sense to use the NTL_LOWER and NTL_UPPER on a compiled
 348  *   mask, thus they are reused as follows: if the NTL_LOWER bit of charset
 349  *   is set it means that the mask contains only non-wilds chars (i.e. you can
 350  *   use strCasecmp() to match it or a direct hash lookup), if the NTL_UPPER
 351  *   bit is set it means that it contains only wild chars (and you can
 352  *   match it with strlen(field)>=minlen).
 353  * Do these optimizations ONLY when the data you are about to pass to
 354  * matchexec() are *known* to be invalid in advance, using strChattr()
 355  * or strlen() on the text would be slower than calling matchexec() directly
 356  * and let it fail.
 357  * Internally a compiled mask contain in the *cmask area the text of
 358  * the plain text form of the mask itself with applied the following hacks:
 359  * - All characters are forced to lowercase (so that uppercase letters and
 360  *   specifically the symbols 'A' and 'Z' are reserved for special use)
 361  * - All non-escaped stars '*' are replaced by the letter 'Z'
 362  * - All non-escaped question marks '?' are replaced by the letter 'A'
 363  * - All escape characters are removed, the wilds escaped by them are
 364  *   then passed by without the escape since they don't collide anymore
 365  *   with the real wilds (encoded as A/Z)
 366  * - Finally the part of the mask that follows the last asterisk is
 367  *   reversed (byte order mirroring) and moved right after the first
 368  *   asterisk.
 369  * After all this a mask like:   Head*CHUNK1*chu\*nK2*ch??k3*TaIl
 370  *               .... becomes:   headZliatZchunk1Zchu*nk2ZchAAk3
 371  * This can still be printed on a console, more or less understood by an
 372  * human and handled with the usual str*() library functions.
 373  * When you store somewhere the compiled mask you can avoid storing the
 374  * textform of it since it can be "decompiled" by means of sprintmatch(),
 375  * but at that time the following things are changed in the mask:
 376  * - All chars have been forced to lowercase.
 377  * - The mask is collapsed.
 378  * The balance point of using compiled masks in terms of CPU is when you expect
 379  * to use matchexec() instead of match() at least 20 times on the same mask
 380  * or when you expect to use mmexec() instead of mmatch() 3 times.
 381  */
 382
 383 /** Compile a mask for faster matching.
 384  * See also @ref compiledmasks.
 385  * @param[out] cmask Output buffer for compiled mask.
 386  * @param[out] minlen Minimum length of matching strings.
 387  * @param[out] charset Character attributes used in compiled mask.
 388  * @param[out] mask Input mask.
 389  * @return Length of compiled mask, not including NUL terminator.
 390  */
 391 int matchcomp(char *cmask, int *minlen, int *charset, const char *mask)
 392 {
 393   const char *m = mask;
 394   char *b = cmask;
 395   char *fs = 0;
 396   char *ls = 0;
 397   char *x1, *x2;
 398   int l1, l2, lmin, loop, sign;
 399   int star = 0;
 400   int cnt = 0;
 401   char ch;
 402   int chset = ~0;
 403   int chset2 = (NTL_LOWER | NTL_UPPER);
 404
 405   if (m)
 406     while ((ch = *m++))
 407       switch (ch)
 408       {
 409         case '*':
 410           star = 1;
 411           break;
 412         case '?':
 413           cnt++;
 414           *b++ = 'A';
 415           chset2 &= ~NTL_LOWER;
 416           break;
 417         case '\\':
 418           if ((*m == '?') || (*m == '*'))
 419             ch = *m++;
 420         default:
 421           if (star)
 422           {
 423             ls = b;
 424             fs = fs ? fs : b;
 425             *b++ = 'Z';
 426             chset2 &= ~NTL_LOWER;
 427             star = 0;
 428           };
 429           cnt++;
 430           *b = ToLower(ch);
 431           chset &= IRCD_CharAttrTab[*b++ - CHAR_MIN];
 432           chset2 &= ~NTL_UPPER;
 433       };
 434
 435   if (charset)
 436     *charset = (chset | chset2);
 437
 438   if (star)
 439   {
 440     ls = b;
 441     fs = (fs ? fs : b);
 442     *b++ = 'Z';
 443   };
 444
 445   if (ls)
 446   {
 447     for (x1 = ls + 1, x2 = (b - 1); x1 < x2; x1++, x2--)
 448     {
 449       ch = *x1;
 450       *x1 = *x2;
 451       *x2 = ch;
 452     };
 453     l1 = (ls - fs);
 454     l2 = (b - ls);
 455     x1 = fs;
 456     while ((lmin = (l1 < l2) ? l1 : l2))
 457     {
 458       x2 = x1 + l1;
 459       for (loop = 0; loop < lmin; loop++)
 460       {
 461         ch = x1[loop];
 462         x1[loop] = x2[loop];
 463         x2[loop] = ch;
 464       };
 465       x1 += lmin;
 466       sign = l1 - l2;
 467       l1 -= (sign < 0) ? 0 : lmin;
 468       l2 -= (sign > 0) ? 0 : lmin;
 469     };
 470   };
 471
 472   *b = '\0';
 473   *minlen = cnt;
 474   return (b - cmask);
 475
 476 }
 477
 478 /** Compare a string to a compiled mask.
 479  * If \a cmask is not from matchcomp(), or if \a minlen is not the value
 480  * passed out of matchcomp(), this may core.
 481  * See also @ref compiledmasks.
 482  * @param[in] string String to test.
 483  * @param[in] cmask Compiled mask string.
 484  * @param[in] minlen Minimum length of strings that match \a cmask.
 485  * @return Zero if the string matches, non-zero otherwise.
 486  */
 487 int matchexec(const char *string, const char *cmask, int minlen)
 488 {
 489   const char *s = string - 1;
 490   const char *b = cmask - 1;
 491   int trash;
 492   const char *bb, *bs;
 493   char ch;
 494
 495 tryhead:
 496   while ((ToLower(*++s) == *++b) && *s);
 497   if (!*s)
 498     return ((*b != '\0') && ((*b++ != 'Z') || (*b != '\0')));
 499   if (*b != 'Z')
 500   {
 501     if (*b == 'A')
 502       goto tryhead;
 503     return 1;
 504   };
 505
 506   bs = s;
 507   while (*++s);
 508
 509   if ((trash = (s - string - minlen)) < 0)
 510     return 2;
 511
 512 trytail:
 513   while ((ToLower(*--s) == *++b) && *b && (ToLower(*--s) == *++b) && *b
 514       && (ToLower(*--s) == *++b) && *b && (ToLower(*--s) == *++b) && *b);
 515   if (*b != 'Z')
 516   {
 517     if (*b == 'A')
 518       goto trytail;
 519     return (*b != '\0');
 520   };
 521
 522   s = --bs;
 523   bb = b;
 524
 525   while ((ch = *++b))
 526   {
 527     while ((ToLower(*++s) != ch))
 528       if (--trash < 0)
 529         return 4;
 530     bs = s;
 531
 532 trychunk:
 533     while ((ToLower(*++s) == *++b) && *b);
 534     if (!*b)
 535       return 0;
 536     if (*b == 'Z')
 537     {
 538       bs = --s;
 539       bb = b;
 540       continue;
 541     };
 542     if (*b == 'A')
 543       goto trychunk;
 544
 545     b = bb;
 546     s = bs;
 547     if (--trash < 0)
 548       return 5;
 549   };
 550
 551   return 0;
 552 }
 553
 554 /*
 555  * matchdecomp()
 556  * Prints the human readable version of *cmask into *mask, (decompiles
 557  * cmask).
 558  * The area pointed by *mask MUST be big enough (the mask might be up to
 559  * twice the size of its compiled form if it's made all of \? or \*, and
 560  * this function can NOT work in place since it might inflate the mask)
 561  * The printed mask is not identical to the one that was compiled to cmask,
 562  * in fact it is 1) forced to all lowercase, 2) collapsed, both things
 563  * are supposed to NOT change it's meaning.
 564  * It returns the number of chars actually written to *mask;
 565  */
 566
 567 /** Decompile a compiled mask into printable form.
 568  * See also @ref compiledmasks.
 569  * @param[out] mask Output mask buffer.
 570  * @param[in] cmask Compiled mask.
 571  * @return Number of characters written to \a mask.
 572  */
 573 int matchdecomp(char *mask, const char *cmask)
 574 {
 575   char *rtb = mask;
 576   const char *rcm = cmask;
 577   const char *begtail, *endtail;
 578
 579   if (rtb ==0)
 580     return (-1);
 581
 582   if (rcm == 0)
 583     return (-2);
 584
 585   for (; (*rcm != 'Z'); rcm++, rtb++)
 586   {
 587     if ((*rcm == '?') || (*rcm == '*'))
 588       *rtb++ = '\\';
 589     if (!((*rtb = ((*rcm == 'A') ? '?' : *rcm))))
 590       return (rtb - mask);
 591   };
 592
 593   begtail = rcm++;
 594   *rtb++ = '*';
 595
 596   while (*rcm && (*rcm != 'Z'))
 597     rcm++;
 598
 599   endtail = rcm;
 600
 601   if (*rcm)
 602   {
 603     while (*++rcm)
 604       switch (*rcm)
 605       {
 606         case 'A':
 607           *rtb++ = '?';
 608           break;
 609         case 'Z':
 610           *rtb++ = '*';
 611           break;
 612         case '*':
 613         case '?':
 614           *rtb++ = '\\';
 615         default:
 616           *rtb++ = *rcm;
 617       };
 618     *rtb++ = '*';
 619   };
 620
 621   for (rcm = endtail; (--rcm) > begtail; *rtb++ = ((*rcm == 'A') ? '?' : *rcm))
 622     if ((*rcm == '?') || (*rcm == '*'))
 623       *rtb++ = '\\';
 624
 625   *rtb = '\0';
 626   return (rtb - mask);
 627 }
 628
 629 /*
 630  * mmexec()
 631  * Checks if a wider compiled mask (wcm/wminlen) completely overrides
 632  * a more restrict one (rcm/rminlen), basically what mmatch() does for
 633  * non-compiled masks, returns 0 if the override is true (like mmatch()).
 634  * "the wider overrides the restrict" means that any string that matches
 635  * the restrict one _will_ also match the wider one, always.
 636  * In this we behave differently from mmatch() because in example we return
 637  * true for " a?*cd overrides a*bcd " for which the override happens for how
 638  * we literally defined it, here mmatch() would have returned false.
 639  * The original concepts and the base algorithm are copied from mmatch()
 640  * written by Run (Carlo Wood), this function is written by
 641  * Nemesi (Andrea Cocito)
 642  */
 643 /** Tests for a superset relationship between compiled masks.  This
 644  * function does for compiled masks what mmatch() is does for normal
 645  * masks.
 646  * See also @ref compiledmasks.
 647  * @param[in] wcm Compiled mask believed to be wider.
 648  * @param[in] wminlen Minimum match length for \a wcm.
 649  * @param[in] rcm Compiled mask believed to be restricted.
 650  * @param[in] rminlen Minimum match length for \a rcm.
 651  * @return Zero if \a wcm is a superset of \a rcm, non-zero if not.
 652  */
 653 int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen)
 654 {
 655   const char *w, *r, *br, *bw, *rx, *rz;
 656   int eat, trash;
 657
 658   /* First of all rm must have enough non-stars to 'contain' wm */
 659   if ((trash = rminlen - wminlen) < 0)
 660     return 1;
 661   w = wcm;
 662   r = rcm;
 663   eat = 0;
 664
 665   /* Let's start the game, remember that '*' is mapped to 'Z', '?'
 666      is mapped to 'A' and that head?*??*?chunk*???*tail becomes
 667      headAAAAZliatAAAZchunk for compiled masks */
 668
 669   /* Match the head of wm with the head of rm */
 670   for (; (*r) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); r++, w++);
 671   if (*r == 'Z')
 672     while (*w == 'A')           /* Eat extra '?' before '*' in wm if got '*' in rm */
 673       w++, eat++;
 674   if (*w != 'Z')                /* head1<any>.. can't match head2<any>.. */
 675     return ((*w) || (*r)) ? 1 : 0;      /* and head<nul> matches only head<nul> */
 676   if (!*++w)
 677     return 0;                   /* headZ<nul> matches head<anything>    */
 678
 679   /* Does rm have any stars in it ? let's check */
 680   for (rx = r; *r && (*r != 'Z'); r++);
 681   if (!*r)
 682   {
 683     /* rm has no stars and thus isn't a mask but it's just a flat
 684        string: special handling occurs here, note that eat must be 0 here */
 685
 686     /* match the tail */
 687     if (*w != 'Z')
 688     {
 689       for (; r--, (*w) && ((*w == *r) || (*w == 'A')); w++);
 690       if (*w != 'Z')            /* headZliat1<any> fails on head<any>2tail  */
 691         return (*w) ? 1 : 0;    /* but headZliat<nul> matches head<any>tail */
 692     }
 693
 694     /* match the chunks */
 695     while (1)
 696     {                           /* This loop can't break but only return   */
 697
 698       for (bw = w++; (*w != *rx); rx++) /* Seek the 1st char of the chunk */
 699         if (--trash < 0)        /* See if we can trash one more char of rm */
 700           return 1;             /* If not we can only fail of course       */
 701       for (r = ++rx, w++; (*w) && ((*w == *r) || (*w == 'A')); r++, w++);
 702       if (!*w)                  /* Did last loop match the rest of chunk ? */
 703         return 0;               /* ... Yes, end of wm, matched !           */
 704       if (*w != 'Z')
 705       {                         /* ... No, hit non-star                    */
 706         w = bw;                 /* Rollback at beginning of chunk          */
 707         if (--trash < 0)        /* Trashed the char where this try started */
 708           return 1;             /* if we can't trash more chars fail       */
 709       }
 710       else
 711       {
 712         rx = r;                 /* Successfully matched a chunk, move rx   */
 713       }                 /* and go on with the next one             */
 714     }
 715   }
 716
 717   /* rm has at least one '*' and thus is a 'real' mask */
 718   rz = r++;                     /* rx = unused of head, rz = beg-tail */
 719
 720   /* Match the tail of wm (if any) against the tail of rm */
 721   if (*w != 'Z')
 722   {
 723     for (; (*w) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); w++, r++);
 724     if (*r == 'Z')              /* extra '?' before tail are fluff, just flush 'em */
 725       while (*w == 'A')
 726         w++;
 727     if (*w != 'Z')              /* We aren't matching a chunk, can't rollback      */
 728       return (*w) ? 1 : 0;
 729   }
 730
 731   /* Match the chunks of wm against what remains of the head of rm */
 732   while (1)
 733   {
 734     bw = w;
 735     for (bw++; (rx < rz) && (*bw != *rx); rx++) /* Seek the first           */
 736       if (--trash < 0)          /* waste some trash reserve */
 737         return 1;
 738     if (!(rx < rz))             /* head finished            */
 739       break;
 740     for (bw++, (br = ++rx);
 741         (br < rz) && (*bw) && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 742     if (!(br < rz))             /* Note that we didn't use any 'eat' char yet, if  */
 743       while (*bw == 'A')        /* there were eat-en chars the head would be over  */
 744         bw++, eat++;            /* Happens only at end of head, and eat is still 0 */
 745     if (!*bw)
 746       return 0;
 747     if (*bw != 'Z')
 748     {
 749       eat = 0;
 750       if (!(br < rz))
 751       {                         /* If we failed because we got the end of head */
 752         trash -= (br - rx);     /* it makes no sense to rollback, just trash   */
 753         if (--trash < 0)        /* all the rest of the head which isn't long   */
 754           return 1;             /* enough for this chunk and go out of this    */
 755         break;                  /* loop, then we try with the chunks of rm     */
 756       };
 757       if (--trash < 0)
 758         return 1;
 759     }
 760     else
 761     {
 762       w = bw;
 763       rx = br;
 764     }
 765   }
 766
 767   /* Match the unused chunks of wm against the chunks of rm */
 768   rx = r;
 769   for (; *r && (*r != 'Z'); r++);
 770   rz = r;
 771   if (*r++)
 772   {
 773     while (*r)
 774     {
 775       bw = w;
 776       while (eat && *r)         /* the '?' we ate makes us skip as many chars  */
 777         if (*r++ != 'Z')        /* here, but can't skip stars or trailing zero */
 778           eat--;
 779       for (bw++; (*r) && (*bw != *r); r++)
 780         if ((*r != 'Z') && (--trash < 0))
 781           return 1;
 782       if (!*r)
 783         break;
 784       for ((br = ++r), bw++;
 785           (*br) && (*br != 'Z') && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 786       if (*br == 'Z')
 787         while (*bw == 'A')
 788           bw++, eat++;
 789       if (!*bw)
 790         return 0;
 791       if (*bw != 'Z')
 792       {
 793         eat = 0;
 794         if ((!*br) || (*r == 'Z'))
 795         {                       /* If we hit the end of rm or a star in it */
 796           trash -= (br - r);    /* makes no sense to rollback within this  */
 797           if (trash < 0)        /* same chunk of br, skip it all and then  */
 798             return 1;           /* either rollback or break this loop if   */
 799           if (!*br)             /* it was the end of rm                    */
 800             break;
 801           r = br;
 802         }
 803         if (--trash < 0)
 804           return 1;
 805       }
 806       else
 807       {
 808         r = br;
 809         w = bw;
 810       }
 811     }
 812   }
 813
 814   /* match the remaining chunks of wm against what remains of the tail of rm */
 815   r = rz - eat - 1;             /* can't have <nul> or 'Z' within the tail, so just move r */
 816   while (r >= rx)
 817   {
 818     bw = w;
 819     for (bw++; (*bw != *r); r--)
 820       if (--trash < 0)
 821         return 1;
 822     if (!(r >= rx))
 823       return 1;
 824     for ((br = --r), bw++;
 825         (*bw) && (br >= rx) && ((*bw == *br) || (*bw == 'A')); br--, bw++);
 826     if (!*bw)
 827       return 0;
 828     if (!(br >= rx))
 829       return 1;
 830     if (*bw != 'Z')
 831     {
 832       if (--trash < 0)
 833         return 1;
 834     }
 835     else
 836     {
 837       r = br;
 838       w = bw;
 839     }
 840   }
 841   return 1;                     /* Auch... something left out ? Fail */
 842 }
 843
 844 /** Test whether an address matches the most significant bits of a mask.
 845  * @param[in] addr Address to test.
 846  * @param[in] mask Address to test against.
 847  * @param[in] bits Number of bits to test.
 848  * @return 0 on mismatch, 1 if bits < 128 and all bits match; -1 if
 849  * bits == 128 and all bits match.
 850  */
 851 int ipmask_check(const struct irc_in_addr *addr, const struct irc_in_addr *mask, unsigned char bits)
 852 {
 853   int k;
 854
 855   for (k = 0; k < 8; k++) {
 856     if (bits < 16)
 857       return !(htons(addr->in6_16[k] ^ mask->in6_16[k]) >> (16-bits));
 858     if (addr->in6_16[k] != mask->in6_16[k])
 859       return 0;
 860     if (!(bits -= 16))
 861       return 1;
 862   }
 863   return -1;
 864 }