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