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
  20 #include "sys.h"
  21 #include "h.h"
  22 #include "struct.h"
  23 #include "common.h"
  24 #include "match.h"
  25 #include "ircd.h"
  26
  27 RCSTAG_CC("$Id$");
  28
  29 /*
  30  * mmatch()
  31  *
  32  * Written by Run (carlo@runaway.xs4all.nl), 25-10-96
  33  */
  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 int mmatch(const char *old_mask, const char *new_mask)
  52 {
  53   register const char *m = old_mask;
  54   register const char *n = new_mask;
  55   const char *ma = m;
  56   const char *na = n;
  57   int wild = 0;
  58   int mq = 0, nq = 0;
  59
  60   while (1)
  61   {
  62     if (*m == '*')
  63     {
  64       while (*m == '*')
  65         m++;
  66       wild = 1;
  67       ma = m;
  68       na = n;
  69     }
  70
  71     if (!*m)
  72     {
  73       if (!*n)
  74         return 0;
  75       for (m--; (m > old_mask) && (*m == '?'); m--)
  76         ;
  77       if ((*m == '*') && (m > old_mask) && (m[-1] != '\\'))
  78         return 0;
  79       if (!wild)
  80         return 1;
  81       m = ma;
  82
  83       /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
  84       if ((*na == '\\') && ((na[1] == '*') || (na[1] == '?')))
  85         ++na;
  86
  87       n = ++na;
  88     }
  89     else if (!*n)
  90     {
  91       while (*m == '*')
  92         m++;
  93       return (*m != 0);
  94     }
  95     if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
  96     {
  97       m++;
  98       mq = 1;
  99     }
 100     else
 101       mq = 0;
 102
 103     /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
 104     if ((*n == '\\') && ((n[1] == '*') || (n[1] == '?')))
 105     {
 106       n++;
 107       nq = 1;
 108     }
 109     else
 110       nq = 0;
 111
 112 /*
 113  * This `if' has been changed compared to match() to do the following:
 114  * Match when:
 115  *   old (m)         new (n)         boolean expression
 116  *    *               any             (*m == '*' && !mq) ||
 117  *    ?               any except '*'  (*m == '?' && !mq && (*n != '*' || nq)) ||
 118  * any except * or ?  same as m       (!((*m == '*' || *m == '?') && !mq) &&
 119  *                                      toLower(*m) == toLower(*n) &&
 120  *                                        !((mq && !nq) || (!mq && nq)))
 121  *
 122  * Here `any' also includes \* and \? !
 123  *
 124  * After reworking the boolean expressions, we get:
 125  * (Optimized to use boolean shortcircuits, with most frequently occuring
 126  *  cases upfront (which took 2 hours!)).
 127  */
 128     if ((*m == '*' && !mq) ||
 129         ((!mq || nq) && toLower(*m) == toLower(*n)) ||
 130         (*m == '?' && !mq && (*n != '*' || nq)))
 131     {
 132       if (*m)
 133         m++;
 134       if (*n)
 135         n++;
 136     }
 137     else
 138     {
 139       if (!wild)
 140         return 1;
 141       m = ma;
 142
 143       /* Added to `mmatch' : Because '\?' and '\*' now is one character: */
 144       if ((*na == '\\') && ((na[1] == '*') || (na[1] == '?')))
 145         ++na;
 146
 147       n = ++na;
 148     }
 149   }
 150 }
 151
 152 /*
 153  * Compare if a given string (name) matches the given
 154  * mask (which can contain wild cards: '*' - match any
 155  * number of chars, '?' - match any single character.
 156  *
 157  * return  0, if match
 158  *         1, if no match
 159  */
 160
 161 /*
 162  * match
 163  *
 164  * Rewritten by Andrea Cocito (Nemesi), November 1998.
 165  *
 166  */
 167
 168 /****************** Nemesi's match() ***************/
 169
 170 int match(const char *mask, const char *string)
 171 {
 172   register const char *m = mask, *s = string;
 173   register char ch;
 174   const char *bm, *bs;          /* Will be reg anyway on a decent CPU/compiler */
 175
 176   /* Process the "head" of the mask, if any */
 177   while ((ch = *m++) && (ch != '*'))
 178     switch (ch)
 179     {
 180       case '\\':
 181         if (*m == '?' || *m == '*')
 182           ch = *m++;
 183       default:
 184         if (toLower(*s) != toLower(ch))
 185           return 1;
 186       case '?':
 187         if (!*s++)
 188           return 1;
 189     };
 190   if (!ch)
 191     return *s;
 192
 193   /* We got a star: quickly find if/where we match the next char */
 194 got_star:
 195   bm = m;                       /* Next try rollback here */
 196   while ((ch = *m++))
 197     switch (ch)
 198     {
 199       case '?':
 200         if (!*s++)
 201           return 1;
 202       case '*':
 203         bm = m;
 204         continue;               /* while */
 205       case '\\':
 206         if (*m == '?' || *m == '*')
 207           ch = *m++;
 208       default:
 209         goto break_while;       /* C is structured ? */
 210     };
 211 break_while:
 212   if (!ch)
 213     return 0;                   /* mask ends with '*', we got it */
 214   ch = toLower(ch);
 215   while (toLower(*s++) != ch)
 216     if (!*s)
 217       return 1;
 218   bs = s;                       /* Next try start from here */
 219
 220   /* Check the rest of the "chunk" */
 221   while ((ch = *m++))
 222   {
 223     switch (ch)
 224     {
 225       case '*':
 226         goto got_star;
 227       case '\\':
 228         if (*m == '?' || *m == '*')
 229           ch = *m++;
 230       default:
 231         if (toLower(*s) != toLower(ch))
 232         {
 233           m = bm;
 234           s = bs;
 235           goto got_star;
 236         };
 237       case '?':
 238         if (!*s++)
 239           return 1;
 240     };
 241   };
 242   if (*s)
 243   {
 244     m = bm;
 245     s = bs;
 246     goto got_star;
 247   };
 248   return 0;
 249 }
 250
 251 /*
 252  * collapse()
 253  * Collapse a pattern string into minimal components.
 254  * This particular version is "in place", so that it changes the pattern
 255  * which is to be reduced to a "minimal" size.
 256  *
 257  * (C) Carlo Wood - 6 Oct 1998
 258  * Speedup rewrite by Andrea Cocito, December 1998.
 259  * Note that this new optimized alghoritm can *only* work in place.
 260  */
 261
 262 char *collapse(char *mask)
 263 {
 264   register int star = 0;
 265   register char *m = mask;
 266   register char *b;
 267
 268   if (m)
 269   {
 270     do
 271     {
 272       if ((*m == '*') && ((m[1] == '*') || (m[1] == '?')))
 273       {
 274         b = m;
 275         do
 276         {
 277           if (*m == '*')
 278             star = 1;
 279           else
 280           {
 281             if (star && (*m != '?'))
 282             {
 283               *b++ = '*';
 284               star = 0;
 285             };
 286             *b++ = *m;
 287             if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 288               *b++ = *++m;
 289           };
 290         }
 291         while (*m++);
 292         break;
 293       }
 294       else
 295       {
 296         if ((*m == '\\') && ((m[1] == '*') || (m[1] == '?')))
 297           m++;
 298       };
 299     }
 300     while (*m++);
 301   };
 302   return mask;
 303 }
 304
 305 /*
 306  ***************** Nemesi's matchcomp() / matchexec() **************
 307  */
 308
 309 /* These functions allow the use of "compiled" masks, you compile a mask
 310  * by means of matchcomp() that gets the plain text mask as input and writes
 311  * its result in the memory locations addressed by the 3 parameters:
 312  * - *cmask will contain the text of the compiled mask
 313  * - *minlen will contain the lenght of the shortest string that can match
 314  *   the mask
 315  * - *charset will contain the minimal set of chars needed to match the mask
 316  * You can pass NULL as *charset and it will be simply not returned, but you
 317  * MUST pass valid pointers for *minlen and *cmask (wich must be big enough
 318  * to contain the compiled mask text that is in the worst case as long as the
 319  * text of the mask itself in plaintext format) and the return value of
 320  * matchcomp() will be the number of chars actually written there (excluded
 321  * the trailing zero). cmask can be == mask, matchcomp() can work in place.
 322  * The {cmask, minlen} couple of values make the real compiled mask and
 323  * need to be passed to the functions that use the compiled mask, if you pass
 324  * the wrong minlen or something wrong in cmask to one of these expect a
 325  * coredump. This means that when you record a compiled mask you must store
 326  * *both* these values.
 327  * Once compiled the mask can be used to match a string by means of
 328  * matchexec(), it can be printed back to human-readable format by means
 329  * of sprintmatch() or it can be compared to another compiled mask by means
 330  * of mmexec() that will tell if it completely overrides that mask (a lot like
 331  * what mmatch() does for plain text masks).
 332  * You can gain a lot of speed in many situations avoiding to matchexec() when:
 333  * - The maximum lenght of the field you are about to match() the mask to is
 334  *   shorter than minlen, in example when matching abc*def*ghil with a nick:
 335  *   It just cannot match since a nick is at most 9 chars long and the mask
 336  *   needs at least 10 chars (10 will be the value returned in minlen).
 337  * - The charset allowed for the field you are about to match to doesn't
 338  *   "contain" the charset returned by matchcomp(), in example when you
 339  *   have *.* as mask it makes no sense to try to match it against a nick
 340  *   because, again, a nick can't contain a '.', you can check this with
 341  *   a simple (charset & NTL_IRCNK) in this case.
 342  * - As a special case, since compiled masks are forced to lowercase,
 343  *   it would make no sense to use the NTL_LOWER and NTL_UPPER on a compiled
 344  *   mask, thus they are reused as follows: if the NTL_LOWER bit of charset
 345  *   is set it means that the mask contains only non-wilds chars (i.e. you can
 346  *   use strCasecmp() to match it or a direct hash lookup), if the NTL_UPPER
 347  *   bit is set it means that it contains only wild chars (and you can
 348  *   match it with strlen(field)>=minlen).
 349  * Do these optimizations ONLY when the data you are about to pass to
 350  * matchexec() are *known* to be invalid in advance, using strChattr()
 351  * or strlen() on the text would be slower than calling matchexec() directly
 352  * and let it fail.
 353  * Internally a compiled mask contain in the *cmask area the text of
 354  * the plain text form of the mask itself with applied the following hacks:
 355  * - All characters are forced to lowercase (so that uppercase letters and
 356  *   specifically the symbols 'A' and 'Z' are reserved for special use)
 357  * - All non-escaped stars '*' are replaced by the letter 'Z'
 358  * - All non-escaped question marks '?' are replaced by the letter 'A'
 359  * - All escape characters are removed, the wilds escaped by them are
 360  *   then passed by without the escape since they don't collide anymore
 361  *   with the real wilds (encoded as A/Z)
 362  * - Finally the part of the mask that follows the last asterisk is
 363  *   reversed (byte order mirroring) and moved right after the first
 364  *   asterisk.
 365  * After all this a mask like:   Head*CHUNK1*chu\*nK2*ch??k3*TaIl
 366  *               .... becomes:   headZliatZchunk1Zchu*nk2ZchAAk3
 367  * This can still be printed on a console, more or less understood by an
 368  * human and handled with the usual str*() library functions.
 369  * When you store somewhere the compiled mask you can avoid storing the
 370  * textform of it since it can be "decompiled" by means of sprintmatch(),
 371  * but at that time the following things are changed in the mask:
 372  * - All chars have been forced to lowercase.
 373  * - The mask is collapsed.
 374  * The balance point of using compiled masks in terms of CPU is when you expect
 375  * to use matchexec() instead of match() at least 20 times on the same mask
 376  * or when you expect to use mmexec() instead of mmatch() 3 times.
 377  */
 378
 379  /*
 380     * matchcomp()
 381     *
 382     * Compiles a mask into a form suitable for using in matchexec().
 383   */
 384
 385 int matchcomp(char *cmask, int *minlen, int *charset, const char *mask)
 386 {
 387   const char *m = mask;
 388   char *b = cmask;
 389   char *fs = NULL;
 390   char *ls = NULL;
 391   char *x1, *x2;
 392   int l1, l2, lmin, loop, sign;
 393   int star = 0;
 394   int cnt = 0;
 395   char ch;
 396   int chset = ~0;
 397   int chset2 = (NTL_LOWER | NTL_UPPER);
 398
 399   if (m)
 400     while ((ch = *m++))
 401       switch (ch)
 402       {
 403         case '*':
 404           star = 1;
 405           break;
 406         case '?':
 407           cnt++;
 408           *b++ = 'A';
 409           chset2 &= ~NTL_LOWER;
 410           break;
 411         case '\\':
 412           if ((*m == '?') || (*m == '*'))
 413             ch = *m++;
 414         default:
 415           if (star)
 416           {
 417             ls = b;
 418             fs = fs ? fs : b;
 419             *b++ = 'Z';
 420             chset2 &= ~NTL_LOWER;
 421             star = 0;
 422           };
 423           cnt++;
 424           chset &= NTL_char_attrib[((*b++ = toLower(ch))) - CHAR_MIN];
 425           chset2 &= ~NTL_UPPER;
 426       };
 427
 428   if (charset)
 429     *charset = (chset | chset2);
 430
 431   if (star)
 432   {
 433     ls = b;
 434     fs = (fs ? fs : b);
 435     *b++ = 'Z';
 436   };
 437
 438   if (ls)
 439   {
 440     for (x1 = ls + 1, x2 = (b - 1); x1 < x2; x1++, x2--)
 441     {
 442       ch = *x1;
 443       *x1 = *x2;
 444       *x2 = ch;
 445     };
 446     l1 = (ls - fs);
 447     l2 = (b - ls);
 448     x1 = fs;
 449     while ((lmin = (l1 < l2) ? l1 : l2))
 450     {
 451       x2 = x1 + l1;
 452       for (loop = 0; loop < lmin; loop++)
 453       {
 454         ch = x1[loop];
 455         x1[loop] = x2[loop];
 456         x2[loop] = ch;
 457       };
 458       x1 += lmin;
 459       sign = l1 - l2;
 460       l1 -= (sign < 0) ? 0 : lmin;
 461       l2 -= (sign > 0) ? 0 : lmin;
 462     };
 463   };
 464
 465   *b = '\0';
 466   *minlen = cnt;
 467   return (b - cmask);
 468
 469 }
 470
 471 /*
 472  * matchexec()
 473  *
 474  * Executes a match with a mask previosuly compiled with matchcomp()
 475  * Note 1: If the mask isn't correctly produced by matchcomp() I will core
 476  * Note 2: 'min' MUST be the value returned by matchcomp on that mask,
 477  *         or.... I will core even faster :-)
 478  * Note 3: This piece of code is not intended to be nice but efficient.
 479  */
 480
 481 int matchexec(const char *string, const char *cmask, int minlen)
 482 {
 483   register const char *s = string - 1;
 484   register const char *b = cmask - 1;
 485   register int trash;
 486   register const char *bb, *bs;
 487   register char ch;
 488
 489 tryhead:
 490   while ((toLower(*++s) == *++b) && *s);
 491   if (!*s)
 492     return ((*b != '\000') && ((*b++ != 'Z') || (*b != '\000')));
 493   if (*b != 'Z')
 494   {
 495     if (*b == 'A')
 496       goto tryhead;
 497     return 1;
 498   };
 499
 500   bs = s;
 501   while (*++s);
 502
 503   if ((trash = (s - string - minlen)) < 0)
 504     return 2;
 505
 506 trytail:
 507   while ((toLower(*--s) == *++b) && *b && (toLower(*--s) == *++b) && *b
 508       && (toLower(*--s) == *++b) && *b && (toLower(*--s) == *++b) && *b);
 509   if (*b != 'Z')
 510   {
 511     if (*b == 'A')
 512       goto trytail;
 513     return (*b != '\000');
 514   };
 515
 516   s = --bs;
 517   bb = b;
 518
 519   while ((ch = *++b))
 520   {
 521     while ((toLower(*++s) != ch))
 522       if (--trash < 0)
 523         return 4;
 524     bs = s;
 525
 526   trychunk:
 527     while ((toLower(*++s) == *++b) && *b);
 528     if (!*b)
 529       return 0;
 530     if (*b == 'Z')
 531     {
 532       bs = --s;
 533       bb = b;
 534       continue;
 535     };
 536     if (*b == 'A')
 537       goto trychunk;
 538
 539     b = bb;
 540     s = bs;
 541     if (--trash < 0)
 542       return 5;
 543   };
 544
 545   return 0;
 546 }
 547
 548 /*
 549  * matchdecomp()
 550  * Prints the human readable version of *cmask into *mask, (decompiles
 551  * cmask).
 552  * The area pointed by *mask MUST be big enough (the mask might be up to
 553  * twice the size of its compiled form if it's made all of \? or \*, and
 554  * this function can NOT work in place since it might enflate the mask)
 555  * The printed mask is not identical to the one that was compiled to cmask,
 556  * infact it is 1) forced to all lowercase, 2) collapsed, both things
 557  * are supposed to NOT change it's meaning.
 558  * It returns the number of chars actually written to *mask;
 559  */
 560
 561 int matchdecomp(char *mask, const char *cmask)
 562 {
 563   register char *rtb = mask;
 564   register const char *rcm = cmask;
 565   register const char *begtail, *endtail;
 566
 567   if (rtb == NULL)
 568     return (-1);
 569
 570   if (rcm == NULL)
 571     return (-2);
 572
 573   for (; (*rcm != 'Z'); rcm++, rtb++)
 574   {
 575     if ((*rcm == '?') || (*rcm == '*'))
 576       *rtb++ = '\\';
 577     if (!((*rtb = ((*rcm == 'A') ? '?' : *rcm))))
 578       return (rtb - mask);
 579   };
 580
 581   begtail = rcm++;
 582   *rtb++ = '*';
 583
 584   while (*rcm && (*rcm != 'Z'))
 585     rcm++;
 586
 587   endtail = rcm;
 588
 589   if (*rcm)
 590   {
 591     while (*++rcm)
 592       switch (*rcm)
 593       {
 594         case 'A':
 595           *rtb++ = '?';
 596           break;
 597         case 'Z':
 598           *rtb++ = '*';
 599           break;
 600         case '*':
 601         case '?':
 602           *rtb++ = '\\';
 603         default:
 604           *rtb++ = *rcm;
 605       };
 606     *rtb++ = '*';
 607   };
 608
 609   for (rcm = endtail; (--rcm) > begtail; *rtb++ = ((*rcm == 'A') ? '?' : *rcm))
 610     if ((*rcm == '?') || (*rcm == '*'))
 611       *rtb++ = '\\';
 612
 613   *rtb = '\000';
 614   return (rtb - mask);
 615 }
 616
 617 /*
 618  * mmexec()
 619  * Checks if a wider compiled mask (wcm/wminlen) completely overrides
 620  * a more restrict one (rcm/rminlen), basically what mmatch() does for
 621  * non-compiled masks, returns 0 if the override is true (like mmatch()).
 622  * "the wider overrides the restrict" means that any string that matches
 623  * the restrict one _will_ also match the wider one, always.
 624  * In this we behave differently from mmatch() because in example we return
 625  * true for " a?*cd overrides a*bcd " for wich the override happens for how
 626  * we literally defined it, here mmatch() would have returned false.
 627  * The original concepts and the base alghoritm are copied from mmatch()
 628  * written by Run (Carlo Wood), this function is written by
 629  * Nemesi (Andrea Cocito)
 630  */
 631
 632 int mmexec(const char *wcm, int wminlen, const char *rcm, int rminlen)
 633 {
 634   register const char *w, *r, *br, *bw, *rx, *rz;
 635   register int eat, trash;
 636
 637   /* First of all rm must have enough non-stars to 'contain' wm */
 638   if ((trash = rminlen - wminlen) < 0)
 639     return 1;
 640   w = wcm;
 641   r = rcm;
 642   eat = 0;
 643
 644   /* Let's start the game, remember that '*' is mapped to 'Z', '?'
 645      is mapped to 'A' and that head?*??*?chunk*???*tail becomes
 646      headAAAAZliatAAAZchunk for compiled masks */
 647
 648   /* Match the head of wm with the head of rm */
 649   for (; (*r) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); r++, w++);
 650   if (*r == 'Z')
 651     while (*w == 'A')           /* Eat extra '?' before '*' in wm if got '*' in rm */
 652       w++, eat++;
 653   if (*w != 'Z')                /* head1<any>.. can't match head2<any>.. */
 654     return ((*w) || (*r)) ? 1 : 0;      /* and head<nul> matches only head<nul> */
 655   if (!*++w)
 656     return 0;                   /* headZ<nul> matches head<anything>    */
 657
 658   /* Does rm have any stars in it ? let's check */
 659   for (rx = r; *r && (*r != 'Z'); r++);
 660   if (!*r)
 661   {
 662     /* rm has no stars and thus isn't a mask but it's just a flat
 663        string: special handling occurs here, note that eat must be 0 here */
 664
 665     /* match the tail */
 666     if (*w != 'Z')
 667     {
 668       for (; r--, (*w) && ((*w == *r) || (*w == 'A')); w++);
 669       if (*w != 'Z')            /* headZliat1<any> fails on head<any>2tail  */
 670         return (*w) ? 1 : 0;    /* but headZliat<nul> matches head<any>tail */
 671     };
 672
 673     /* match the chunks */
 674     while (1)
 675     {                           /* This loop can't break but only return   */
 676
 677       for (bw = w++; (*w != *rx); rx++) /* Seek the 1st char of the chunk */
 678         if (--trash < 0)        /* See if we can trash one more char of rm */
 679           return 1;             /* If not we can only fail of course       */
 680       for (r = ++rx, w++; (*w) && ((*w == *r) || (*w == 'A')); r++, w++);
 681       if (!*w)                  /* Did last loop match the rest of chunk ? */
 682         return 0;               /* ... Yes, end of wm, matched !           */
 683       if (*w != 'Z')
 684       {                         /* ... No, hitted non-star                 */
 685         w = bw;                 /* Rollback at beginning of chunk          */
 686         if (--trash < 0)        /* Trashed the char where this try started */
 687           return 1;             /* if we can't trash more chars fail       */
 688       }
 689       else
 690       {
 691         rx = r;                 /* Successfully matched a chunk, move rx   */
 692       };                        /* and go on with the next one             */
 693     };
 694   };
 695
 696   /* rm has at least one '*' and thus is a 'real' mask */
 697   rz = r++;                     /* rx = unused of head, rz = beg-tail */
 698
 699   /* Match the tail of wm (if any) against the tail of rm */
 700   if (*w != 'Z')
 701   {
 702     for (; (*w) && (*r != 'Z') && ((*w == *r) || (*w == 'A')); w++, r++);
 703     if (*r == 'Z')              /* extra '?' before tail are fluff, just flush 'em */
 704       while (*w == 'A')
 705         w++;
 706     if (*w != 'Z')              /* We aren't matching a chunk, can't rollback      */
 707       return (*w) ? 1 : 0;
 708   };
 709
 710   /* Match the chunks of wm against what remains of the head of rm */
 711   while (1)
 712   {
 713     bw = w;
 714     for (bw++; (rx < rz) && (*bw != *rx); rx++) /* Seek the first           */
 715       if (--trash < 0)          /* waste some trash reserve */
 716         return 1;
 717     if (!(rx < rz))             /* head finished            */
 718       break;
 719     for (bw++, (br = ++rx);
 720         (br < rz) && (*bw) && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 721     if (!(br < rz))             /* Note that we didn't use any 'eat' char yet, if  */
 722       while (*bw == 'A')        /* there were eat-en chars the head would be over  */
 723         bw++, eat++;            /* Happens only at end of head, and eat is still 0 */
 724     if (!*bw)
 725       return 0;
 726     if (*bw != 'Z')
 727     {
 728       eat = 0;
 729       if (!(br < rz))
 730       {                         /* If we failed because we got the end of head */
 731         trash -= (br - rx);     /* it makes no sense to rollback, just trash   */
 732         if (--trash < 0)        /* all the rest of the head wich isn't long    */
 733           return 1;             /* enough for this chunk and go out of this    */
 734         break;                  /* loop, then we try with the chunks of rm     */
 735       };
 736       if (--trash < 0)
 737         return 1;
 738     }
 739     else
 740     {
 741       w = bw;
 742       rx = br;
 743     };
 744   };
 745
 746   /* Match the unused chunks of wm against the chunks of rm */
 747   rx = r;
 748   for (; *r && (*r != 'Z'); r++);
 749   rz = r;
 750   if (*r++)
 751   {
 752     while (*r)
 753     {
 754       bw = w;
 755       while (eat && *r)         /* the '?' we had eated make us skip as many chars */
 756         if (*r++ != 'Z')        /* here, but can't skip stars or trailing zero     */
 757           eat--;
 758       for (bw++; (*r) && (*bw != *r); r++)
 759         if ((*r != 'Z') && (--trash < 0))
 760           return 1;
 761       if (!*r)
 762         break;
 763       for ((br = ++r), bw++;
 764           (*br) && (*br != 'Z') && ((*bw == *br) || (*bw == 'A')); br++, bw++);
 765       if (*br == 'Z')
 766         while (*bw == 'A')
 767           bw++, eat++;
 768       if (!*bw)
 769         return 0;
 770       if (*bw != 'Z')
 771       {
 772         eat = 0;
 773         if ((!*br) || (*r == 'Z'))
 774         {                       /* If we hit the end of rm or a star in it */
 775           trash -= (br - r);    /* makes no sense to rollback within this  */
 776           if (trash < 0)        /* same chunk of br, skip it all and then  */
 777             return 1;           /* either rollback or break this loop if   */
 778           if (!*br)             /* it was the end of rm                    */
 779             break;
 780           r = br;
 781         };
 782         if (--trash < 0)
 783           return 1;
 784       }
 785       else
 786       {
 787         r = br;
 788         w = bw;
 789       };
 790     };
 791   };
 792
 793   /* match the remaining chunks of wm against what remains of the tail of rm */
 794   r = rz - eat - 1;             /* can't have <nul> or 'Z'within the tail, so just move r */
 795   while (r >= rx)
 796   {
 797     bw = w;
 798     for (bw++; (*bw != *r); r--)
 799       if (--trash < 0)
 800         return 1;
 801     if (!(r >= rx))
 802       return 1;
 803     for ((br = --r), bw++;
 804         (*bw) && (br >= rx) && ((*bw == *br) || (*bw == 'A')); br--, bw++);
 805     if (!*bw)
 806       return 0;
 807     if (!(br >= rx))
 808       return 1;
 809     if (*bw != 'Z')
 810     {
 811       if (--trash < 0)
 812         return 1;
 813     }
 814     else
 815     {
 816       r = br;
 817       w = bw;
 818     };
 819   };
 820   return 1;                     /* Auch... something left out ? Fail */
 821 }
 822
 823 /*
 824  * matchcompIP()
 825  * Compiles an IP mask into an in_mask structure
 826  * The given <mask> can either be:
 827  * - An usual irc type mask, containing * and or ?
 828  * - An ip number plus a /bitnumber part, that will only consider
 829  *   the first "bitnumber" bits of the IP (bitnumber must be in 0-31 range)
 830  * - An ip numer plus a /ip.bit.mask.values that will consider
 831  *   only the bits marked as 1 in the ip.bit.mask.values
 832  * In the last two cases both the ip number and the bitmask can specify
 833  * less than 4 bytes, the missing bytes then default to zero, note that
 834  * this is *different* from the way inet_aton() does and that this does
 835  * NOT happen for normal IPmasks (not containing '/')
 836  * If the returned value is zero the produced in_mask might match some IP,
 837  * if it's nonzero it will never match anything (and the imask struct is
 838  * set so that always fails).
 839  *
 840  * The returned structure contains 3 fields whose meaning is the following:
 841  * im.mask = The bits considered significative in the IP
 842  * im.bits = What these bits should look like to have a match
 843  * im.fall = If zero means that the above information used as
 844  *           ((IP & im.mask) == im.bits) is enough to tell if the compiled
 845  *           mask matches the given IP, nonzero means that it is needed,
 846  *           in case they did match, to call also the usual text match
 847  *           functions, because the mask wasn't "completely compiled"
 848  *
 849  * They should be used like:
 850  * matchcompIP(&im, mask);
 851  * if ( ((IP & im.mask)!=im.bits)) || (im.fall&&match(mask,inet_ntoa(IP))) )
 852  *    { handle_non_match } else { handle_match };
 853  * instead of:
 854  * if ( match(mask, inet_ntoa(IP)) )
 855  *    { handle_non_match } else { handle_match };
 856  *
 857  * Note: This function could be smarter when dealing with complex masks,
 858  *       this implementation is quite lazy and understands only very simple
 859  *       cases, whatever contains a ? anywhere or contains a '*' that isn't
 860  *       part of a trailing '.*' will fallback to text-match, this could be
 861  *       avoided for masks like 12?3.5.6 12.*.3.4 1.*.*.2 72?72?72?72 and
 862  *       so on that "could" be completely compiled to IP masks.
 863  *       If you try to improve this be aware of the fact that ? and *
 864  *       could match both dots and digits and we _must_ always reject
 865  *       what doesn't match in textform (like leading zeros and so on),
 866  *       so it's a LOT more tricky than it might seem. By now most common
 867  *       cases are optimized.
 868  */
 869
 870 int matchcompIP(struct in_mask *imask, const char *mask)
 871 {
 872   register const char *m = mask;
 873   register unsigned int bits = 0;
 874   register unsigned int filt = 0;
 875   register int unco = 0;
 876   register int digits = 0;
 877   register int shift = 24;
 878   register int tmp = 0;
 879
 880   do
 881   {
 882     switch (*m)
 883     {
 884       case '\\':
 885         if ((m[1] == '\\') || (m[1] == '*') || (m[1] == '?')
 886             || (m[1] == '\000'))
 887           break;
 888         continue;
 889       case '0':
 890       case '1':
 891       case '2':
 892       case '3':
 893       case '4':
 894       case '5':
 895       case '6':
 896       case '7':
 897       case '8':
 898       case '9':
 899         if (digits && !tmp)     /* Leading zeros */
 900           break;
 901         digits++;
 902         tmp *= 10;
 903         tmp += (*m - '0');      /* Can't overflow, INT_MAX > 2559 */
 904         if (tmp > 255)
 905           break;
 906         continue;
 907       case '\000':
 908         filt = 0xFFFFFFFF;
 909         /* Intentional fallthrough */
 910       case '.':
 911         if ((!shift) != (!*m))
 912           break;
 913         /* Intentional fallthrough */
 914       case '/':
 915         bits |= (tmp << shift);
 916         shift -= 8;
 917         digits = 0;
 918         tmp = 0;
 919         if (*m != '/')
 920           continue;
 921         shift = 24;
 922         do
 923         {
 924           m++;
 925           if (isDigit(*m))
 926           {
 927             if (digits && !tmp) /* Leading zeros */
 928               break;
 929             digits++;
 930             tmp *= 10;
 931             tmp += (*m - '0');  /* Can't overflow, INT_MAX > 2559 */
 932             if (tmp > 255)
 933               break;
 934           }
 935           else
 936           {
 937             switch (*m)
 938             {
 939               case '.':
 940               case '\000':
 941                 if ((!shift) && (*m))
 942                   break;
 943                 filt |= (tmp << shift);
 944                 shift -= 8;
 945                 tmp = 0;
 946                 digits = 0;
 947                 continue;
 948               default:
 949                 break;
 950             }
 951             break;
 952           }
 953         }
 954         while (*m);
 955         if (*m)
 956           break;
 957         if (filt && (!(shift < 16)) && (!(filt & 0xE0FFFFFF)))
 958           filt = 0xFFFFFFFF << (32 - ((filt >> 24)));
 959         bits &= filt;
 960         continue;
 961       case '?':
 962         unco = 1;
 963         /* Intentional fallthrough */
 964       case '*':
 965         if (digits)
 966           unco = 1;
 967         filt = (0xFFFFFFFF << (shift)) << 8;
 968         while (*++m)
 969         {
 970           if (isDigit(*m))
 971             unco = 1;
 972           else
 973           {
 974             switch (*m)
 975             {
 976               case '.':
 977                 if (m[1] != '*')
 978                   unco = 1;
 979                 if (!shift)
 980                   break;
 981                 shift -= 8;
 982                 continue;
 983               case '?':
 984                 unco = 1;
 985               case '*':
 986                 continue;
 987               default:
 988                 break;
 989             }
 990             break;
 991           }
 992         }
 993         if (*m)
 994           break;
 995         continue;
 996       default:
 997         break;
 998     }
 999
1000     /* If we get here there is some error and this can't ever match */
1001     filt = 0;
1002     bits = ~0;
1003     unco = 0;
1004     break;                      /* This time break the loop :) */
1005
1006   }
1007   while (*m++);
1008
1009   imask->bits.s_addr = htonl(bits);
1010   imask->mask.s_addr = htonl(filt);
1011   imask->fall = unco;
1012   return ((bits & ~filt) ? -1 : 0);
1013
1014 }