www.pudn.com > AntiCrack.zip > rejrule.c
/*
* rejrule.c - rejects unnecessary rules to get faster
*
* Copyright (C) 1996 Kazuto Tominaga
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
*/
#include "anticrack.h"
#define ERM_NOARG "rejrule: %s(%s): Argument is not supplied for %c\n"
#define ERM_NODIGIT "rejrule: %s(%s): '%c' is not a digit letter\n"
#define ERM_IMPARG "rejrule: %s(%s): Argument is not properly supplied for %c\n"
#define ERM_INVCOM "rejrule: %s(%s): Invalid command %c\n"
/* version of this file */
static char version_id[] = "@(#) $Id: rejrule.c,v 1.11 1993/11/18 08:24:21 tominaga Exp tominaga $";
char *visible(pat)
char *pat;
{
static char toshow[RBUFSIZE];
int i;
i = 0;
while (i < RBUFSIZE - 1) {
switch (*pat) {
case '\0':
goto breakfor;
case DOT:
toshow[i++] = '.';
break;
case STAR:
toshow[i++] = '*';
break;
case '.':
toshow[i++] = '\\';
toshow[i++] = '.';
break;
case '*':
toshow[i++] = '\\';
toshow[i++] = '*';
break;
default:
toshow[i++] = *pat;
break;
}
pat++;
}
breakfor:
toshow[i] = '\0';
return toshow;
}
canonicalize(pat)
char *pat;
{
static char buf[MAXPWLINE];
char *p = pat, *q = buf;
int starf = 0;
for (; *p != '\0'; p++) {
if (*p == STAR) {
if (starf)
continue;
else {
*q++ = STAR;
starf = 1;
continue;
}
} else {
starf = 0;
*q++ = *p;
}
}
*q = '\0';
strcpy(pat, buf);
}
/* 0: should be used; 1: possibly used ; -1: rejected */
rejrule(rule, rawpw)
char *rule, *rawpw;
{
static char rbuf[RBUFSIZE];
static char in[MAXPWLINE], out[MAXPWLINE];
char *r = rbuf;
int next; /* 0: continue; +: return; -: reject */
int i;
/* reverse the order of commands */
if (revcmds(r, rule) < 0) {
Log("rejrule: Wrong command in \"%s\"\n", rule);
return REJECT;
}
if (debug)
message("debug: invert commands \"%s\" -> \"%s\"\n", rule, r);
/* make the starting pattern */
strcpy(in, rawpw);
if ((i = strlen(in)) >= 8) {
in[i] = STAR;
in[i+1] = '\0';
}
if (debug)
message("debug: password \"%s\" -> pattern \"%s\"\n",
rawpw, visible(in));
next = 0;
while (*r != '\0') {
if (debug)
message("debug: pattern \"%s\", rules rest \"%s\"\n",
visible(in), r);
canonicalize(in); /* ** -> * */
/* check the pattern */
if (in[0] == '\0') { /* \phi = no sentence matches */
return REJECT;
} else if (in[0] == STAR && in[1] == '\0') {
return ACCEPT;
}
switch (*r) {
case RULE_NOOP: /* ':' */
next = revNoop(in, out);
r++;
break;
case RULE_PREPEND: /* '^' */
if (*(r+1) == '\0') {
Log(ERM_NOARG, rule, r, *r);
return REJECT;
}
next = revPrepend(in, out, *(r+1));
r += 2;
break;
case RULE_APPEND: /* '$' */
if (*(r+1) == '\0') {
Log(ERM_NOARG, rule, r, *r);
return REJECT;
}
next = revAppend(in, out, *(r+1));
r += 2;
break;
case RULE_REVERSE: /* 'r' */
next = revReverse(in, out);
r++;
break;
case RULE_UPPERCASE: /* 'u' */
next = revUppercase(in, out);
r++;
break;
case RULE_LOWERCASE: /* 'l' */
next = revLowercase(in, out);
r++;
break;
case RULE_PLURALISE: /* 'p' */
next = revPluralise(in, out);
r++;
break;
case RULE_CAPITALISE: /* 'c' */
next = revCapitalise(in, out);
r++;
break;
#if TOMINAGA
case RULE_ONEUPPER: /* '+' */
if (*(r+1) == '\0') {
Log(ERM_NOARG, rule, r, *r);
return REJECT;
} else {
int i = Char2Int(*(r+1));
if (i < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
next = revOneupper(in, out, i);
r += 2;
break;
}
#endif /* TOMINAGA */
case RULE_DUPLICATE: /* 'd' */
next = revDuplicate(in, out);
r++;
break;
case RULE_REFLECT: /* 'f' */
next = revReflect(in, out);
r++;
break;
case RULE_SUBSTITUTE: /* 's' */
if (*(r+1) == '\0' || *(r+2) == '\0' ||
(*(r+1) == RULE_CLASS && *(r+3) == '\0')) {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
if (*(r+1) == RULE_CLASS) {
next = revClassSubstitute(in, out, *(r+2), *(r+3));
r += 4;
break;
} else {
next = revSubstitute(in, out, *(r+1), *(r+2));
r += 3;
break;
}
}
case RULE_MATCH: /* '/' */
if (*(r+1) == '\0' ||
(*(r+1) == RULE_CLASS && *(r+2) == '\0')) {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
if (*(r+1) == RULE_CLASS) {
next = revClassMatch(in, out, *(r+2));
r += 3;
break;
} else {
next = revMatch(in, out, *(r+1));
r += 2;
break;
}
}
case RULE_NOT: /* '!' */
if (*(r+1) == '\0' ||
(*(r+1) == RULE_CLASS && *(r+2) == '\0')) {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
if (*(r+1) == RULE_CLASS) {
next = revClassNot(in, out, *(r+2));
r += 3;
break;
} else {
next = revNot(in, out, *(r+1));
r += 2;
break;
}
}
case RULE_LT: /* '<' */
if (*(r+1) == '\0') {
Log(ERM_NOARG, rule, r, *r);
return REJECT;
} else {
int i = Char2Int(*(r+1));
if (i < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
next = revLt(in, out, i);
r += 2;
break;
}
case RULE_GT: /* '>' */
if (*(r+1) == '\0') {
Log(ERM_NOARG, rule, r, *r);
return REJECT;
} else {
int i = Char2Int(*(r+1));
if (i < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
next = revGt(in, out, i);
r += 2;
break;
}
case RULE_EXTRACT: /* 'x' */
if (*(r+1) == '\0' || *(r+2) == '\0') {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
int n = Char2Int(*(r+1)), m = Char2Int(*(r+2));
if (n < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
} else if (m < 0) {
Log(ERM_NODIGIT, rule, r, *(r+2));
return REJECT;
}
next = revExtract(in, out, n, m);
r += 3;
break;
}
case RULE_OVERSTRIKE: /* 'o' */
if (*(r+1) == '\0' || *(r+2) == '\0') {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
int n = Char2Int(*(r+1));
char c = *(r+2);
if (n < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
next = revOverstrike(in, out, n, c);
r += 3;
break;
}
case RULE_INSERT: /* 'i' */
if (*(r+1) == '\0' || *(r+2) == '\0') {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
int n = Char2Int(*(r+1));
char c = *(r+2);
if (n < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
next = revInsert(in, out, n, c);
r += 3;
break;
}
case RULE_EQUALS: /* '=' */
if (*(r+1) == '\0' || *(r+2) == '\0' ||
(*(r+1) == RULE_CLASS && *(r+3) == '\0')) {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
int n;
char c;
n = Char2Int(*(r+1));
if (n < 0) {
Log(ERM_NODIGIT, rule, r, *(r+1));
return REJECT;
}
if (*(r+2) == RULE_CLASS) {
c = *(r+3);
next = revClassEquals(in, out, n, c);
r += 4;
break;
} else {
c = *(r+2);
next = revEquals(in, out, n, c);
r += 3;
break;
}
}
case RULE_PURGE: /* '@' */
if (*(r+1) == '\0' ||
(*(r+1) == RULE_CLASS && *(r+2) == '\0')) {
Log(ERM_IMPARG, rule, r, *r);
return REJECT;
} else {
char c;
if (*(r+1) == RULE_CLASS) {
c = *(r+2);
next = revClassPurge(in, out, c);
r += 3;
break;
} else {
c = *(r+1);
next = revPurge(in, out, c);
r += 2;
break;
}
}
default:
Log(ERM_INVCOM, rule, r, *r);
return REJECT;
}
/* check the value of next */
if (next == REJECT) /* reject the rule */
return REJECT;
else if (next == MAYBE) /* cannot state whether to reject */
return MAYBE;
/* otherwise CONTinue */
strcpy(in, out);
}
return ACCEPT; /* accept */
}
revcmds(dst, src)
char *dst, *src; /* destination area must be supplied */
{
char *dp, *sp;
int cl, i;
sp = src;
dp = dst + strlen(src);
*dp = '\0';
while (*sp != '\0') {
if ((cl = comlen(sp)) < 0)
return -1; /* malformed command */
dp -= cl;
for (i = 0; i < cl; i++)
dp[i] = sp[i];
sp += cl;
}
return 0;
}
comlen(s)
char *s;
{
switch (*s) {
case RULE_NOOP: /* ':' */
case RULE_REVERSE: /* 'r' */
case RULE_UPPERCASE: /* 'u' */
case RULE_LOWERCASE: /* 'l' */
case RULE_PLURALISE: /* 'p' */
case RULE_CAPITALISE: /* 'c' */
case RULE_DUPLICATE: /* 'd' */
case RULE_REFLECT: /* 'f' */
return 1;
case RULE_PREPEND: /* '^' */
case RULE_APPEND: /* '$' */
case RULE_LT: /* '<' */
case RULE_GT: /* '>' */
#if TOMINAGA
case RULE_ONEUPPER: /* '+' */
#endif
return 2;
case RULE_EXTRACT: /* 'x' */
case RULE_OVERSTRIKE: /* 'o' */
case RULE_INSERT: /* 'i' */
return 3;
case RULE_MATCH: /* '/' */
case RULE_NOT: /* '!' */
case RULE_PURGE: /* '@' */
if (*(s+1) == '\0')
return -1;
else if (*(s+1) == RULE_CLASS)
return 3;
else
return 2;
case RULE_SUBSTITUTE: /* 's' */
case RULE_EQUALS: /* '=' */
if (*(s+1) == '\0')
return -1;
else if (*(s+2) == '\0')
return -1;
else if (*(s+2) == RULE_CLASS)
return 4;
else
return 3;
default:
Log("rejrule: Unknown command %c in %s\n", *s, s);
return -1;
}
}
/*** subfunctions below ***/
revpat(out, in)
char *out, *in;
{
out += strlen(in);
*out = '\0';
while (*in != '\0')
*--out = *in++;
return;
}
patlen(pat) /* STAR is considered to have infinity length */
char *pat;
{
if (strchr(pat, STAR))
return -1; /* means infinity */
else
return strlen(pat);
}
patlen_shortest(pat) /* ignores STAR */
char *pat;
{
int count = 0;
while (*pat != '\0') {
if (*pat != STAR)
count++;
pat++;
}
return count;
}
patpos(pat, n) /* 0..: pos, -1: out of the pattern */
char *pat;
int n;
{
int i;
for (i = 0; i <= n; i++)
if (pat[i] == '\0')
return -1;
else if (pat[i] == STAR)
return i;
return n;
}
patpos_rightmost(pat, n)
char *pat;
int n;
{
int i, p;
for (i = 0, p = 0;; i++)
switch (pat[i]) {
case '\0':
return -1;
case STAR:
continue;
case DOT:
default:
if (p == n)
return p;
else
p++;
continue;
}
}
rpatpos(pat, n)
char *pat;
int n;
{
int i;
for (i = strlen(pat) - 1; i >= 0; i--)
if (n == 0 || pat[i] == STAR)
return i;
else
n--;
return -1;
}
rpatpos_leftmost(pat, n)
char *pat;
int n;
{
int i;
for (i = strlen(pat) - 1; i >= 0; i--)
switch (pat[i]) {
case STAR:
continue;
default:
if (n == 0)
return i;
else
n--;
}
return -1;
}
/*
* Inverting commands below
*/
/* identity function */
revNoop(in, out)
char *in, *out;
{
strcpy(out, in);
return CONT;
}
revPrepend(in, out, what) /* assuming the pattern is canonicalized */
char *in, *out, what;
{
if (in[0] == what || in[0] == DOT) {
strcpy(out, in+1);
return CONT;
} else if (in[0] == STAR) {
if (in[1] == '\0') {
strcpy(out, in);
return CONT;
} else if (in[1] == what || in[1] == DOT) {
strcpy(out, in+1);
*out = STAR;
return CONT;
} else {
strcpy(out, in);
return CONT;
}
} else
return REJECT;
}
revAppend(in, out, what) /* assuming the pattern is canonicalized */
char *in, *out, what;
{
int len;
strcpy(out, in);
if ((len = strlen(out)) == 0) {
return CONT; /* and will be rejected */
} else if (out[len-1] == what || out[len-1] == DOT) {
out[len-1] = '\0';
return CONT;
} else if (out[len-1] == STAR) {
if (len == 1)
return CONT; /* and will be accepted */
else if (out[len-2] == what || out[len-2] == DOT) {
out[len-2] = STAR;
out[len-1] = '\0';
return CONT;
} else
return CONT;
} else
return REJECT;
}
revReverse(in, out)
char *in, *out;
{
out = out + strlen(in);
*out = '\0';
while (*in != '\0')
*--out = *in++;
return CONT;
}
revUppercase(in, out)
char *in, *out;
{
while (*in != '\0') {
if (Isalpha(*in))
if (islower(*in))
return REJECT;
else /* must be isupper */
*out++ = DOT;
else
*out++ = *in;
in++;
}
*out = '\0';
return CONT;
}
revLowercase(in, out)
char *in, *out;
{
while (*in != '\0') {
if (Isalpha(*in))
if (isupper(*in))
return REJECT;
else /* must be islower */
*out++ = DOT;
else
*out++ = *in;
in++;
}
*out = '\0';
return CONT;
}
char *suffixp(string, part)
char *string, *part;
{
int sl, pl;
sl = strlen(string);
pl = strlen(part);
if (sl < pl)
return NULL;
else if (!strcmp(string + sl - pl, part))
return (string + sl - pl);
else
return NULL;
}
revPluralise(in, out)
char *in, *out;
{
char *tail, *p;
int i, expected, queinf;
char *exparr = "sei"; /* suffix "ies"; indexed by "expected" */
strcpy(out, in);
expected = 0; /* means waiting for 's' */
queinf = 0;
/* at the end of the loop, i points the last character */
/* that should appear in the output string */
for (i = strlen(out) - 1; i >= 0; i--) {
if (expected >= strlen(exparr)) {
/* all the expected characters have been found */
break;
}
if (out[i] == STAR) {
queinf = 1;
continue;
} else if (Pateq(out[i], exparr[expected])) {
expected++;
continue;
} else {
/* encountered not expected char */
break;
}
}
/* n.b. i = -1 if the loop ended normally */
if (expected == 0 && !queinf) {
/* cannot be generated by Pluralisation */
return REJECT;
}
if (queinf || expected >= 2) {
/* if expected >= 2 (i.e., the string has "es" or "ies" */
/* at the end), the result should have STAR at its end */
/* because the original string might have been "xxe" or "xxie" */
if (i == -1 || out[i] != STAR) {
/* to avoid adding excess STAR (i == -1 is a guard) */
out[++i] = STAR;
}
}
out[++i] = '\0';
return CONT;
}
/* nb: Capitalise in crack-lib.c does like: caPitaL -> Capital */
revCapitalise(in, out)
char *in, *out;
{
if (Islower(*in))
return REJECT;
strcpy(out, in);
if (Isupper(*out))
*out = DOT;
out++;
while (*out != '\0') {
if (Isupper(*out))
return REJECT;
else if (Islower(*out))
*out = DOT; /* see "nb" above */
out++;
}
return CONT;
}
#if TOMINAGA
revOneupper(in, out, pos)
char *in, *out;
int pos;
{
int i;
if ((i = patpos(in, pos)) < 0)
/* out of the pattern */
/* (maybe REJECT if the rule is written properly) */
return REJECT;
strcpy(out, in);
switch (out[i]) {
case DOT:
case STAR:
/* can tell nothing */
return CONT;
default:
if (Islower(out[i]))
return REJECT;
else if (Isupper(out[i])) {
/* was an uppercase letter or an lowercase letter */
out[i] = DOT;
return CONT;
} else {
/* must not have been changed */
return CONT;
}
}
}
#endif /* TOMINAGA */
/*
* revDuplicate:
*
* I. When a* is given:
*
* x -dup-> xx
* ----------------------------------------------------------
* result <-revdup given (a* =)
* ----------------------------------------------------------
* case 1. x (a*) y* where x=yz
* case 2. x (a) xx
* case 3. x (a') xw*
* ---------------------------------------------------------------
* The shortest of a' should be the result.
*
* II. When *b is given:
*
* Reverse and process it regarding it as a*.
*
* III. When a*b is given:
*
* Assume xx = a*b. The following cases are possible:
*
* case 1. x = ac = db (c or d can be null)
* n.b. This case has some subcases.
* case 2. a = xw where x = wyb.
* case 3. b = wx where x = ayw (inverted case 2).
* And what else?
*
* IV. Other cases?
*
*/
revDuplicate(in, out)
char *in, *out;
{
int l;
if ((l = patlen(in)) < 0) {
/* the pattern includes at least one STAR */
l = strlen(in);
if (*in != STAR && in[l-1] != STAR) {
/* "a*...*b" */
char *star1 = strchr(in, STAR), *star2 = strrchr(in, STAR);
if (star1 != star2) {
/* in has more than one STAR */
/* crush them into one */
char tmpbuf[MAXPWLINE];
strncpy(tmpbuf, in, star1 - in); /* excluding STAR */
strcpy(tmpbuf + (star1 - in), star2);
if (debug) {
message("debug: Duplicate: in=\"%s\"\n",
visible(in));
message("debug: Duplicate: ->\"%s\"\n",
visible(tmpbuf));
}
strcpy(in, tmpbuf);
}
/* now in has only one STAR in the midst */
/*** END OF EXPERIMENTAL PART ***/
/*** the current set of the rev- functions never generate ***/
/*** patterns that have STARs only inside of themselves ***/
message(
"rejrule: Internal error; wrong assumption --- continuing\n");
/*** but try to do ***/
*(strchr(in, STAR)+1) = '\0';
return revDuplicate(in, out);
} else if (*in != STAR) {
/* "a*..." */
int start2, p1, p2, fence;
char *p;
*(strchr(in, STAR) + 1) = '\0'; /* "a*..." -> "a*" */
if (debug)
message("debug: Duplicate: in -> \"%s\"\n", visible(in));
l = strlen(in);
fence = l / 2; /* middle position except STAR */
for (start2 = fence; start2 < l - 1; start2++) {
p = out;
for (p1 = 0, p2 = start2; p1 < start2; p1++, p2++) {
if (in[p2] == STAR) {
/* not complete duplication */
in[start2] = STAR;
in[start2+1] = '\0';
strcpy(p, &in[p1]);
return CONT;
}
if (Pateq(in[p1], in[p2])) {
*p++ = in[p1]; /* preserving DOT */
continue;
} else
break;
}
if (p1 == start2) {
/* complete duplication */
*p++ = STAR;
*p++ = '\0';
return CONT;
}
/* otherwise not match */
}
strcpy(out, in);
return CONT;
} else if (in[l-1] != STAR) {
/* "...*b" */
int cond;
revpat(out, in); /* make it into "a*" form */
if (debug)
message("debug: Duplicate: recurring with \"%s\"\n",
visible(out));
cond = revDuplicate(out, in); /* recur */
revpat(out, in);
if (debug)
message("debug: Duplicate: recursion end with \"%s\"\n",
visible(out));
return cond;
} else {
/* "*...*" */
return MAYBE;
}
} else if (l % 2) {
/* the length of the pattern is odd */
return REJECT;
} else {
/* the length of the pattern is even */
char *c1 = in, *c2 = in + (l /= 2);
while (l--) {
if (Pateq(*c1,*c2)) {
*out++ = (*c1 != DOT) ? *c1 : *c2;
c1++;
c2++;
} else
return REJECT;
}
*out = '\0';
return CONT;
}
}
/*
* revReflect:
*
* I. When a* is given:
*
* Find the minimum reflexee a' and return a'*.
*
* II. When *b is given:
*
* Invert it and process as I.
*
* III. When a*b is given:
*
* Check if it can be result of reflection and return
* the longest pattern we can make out.
*
*/
revReflect(in, out)
char *in, *out;
{
int l;
if ((l = patlen(in)) < 0) {
/* the pattern includes at least one STAR */
l = strlen(in);
if (*in != STAR && in[l-1] != STAR) {
/* "a*...*b" */
char *star1 = strchr(in, STAR), *star2 = strrchr(in, STAR);
char *p1, *p2;
if (star1 != star2) {
/* in has more than one STAR */
/* crush them into one */
char tmpbuf[MAXPWLINE];
strncpy(tmpbuf, in, star1 - in); /* excluding STAR */
strcpy(tmpbuf + (star1 - in), star2);
if (debug) {
message("debug: Reflect: in=\"%s\"\n", visible(in));
message("debug: Reflect: ->\"%s\"\n", visible(tmpbuf));
}
strcpy(in, tmpbuf);
}
/* now in has only one STAR in the midst */
for (p1 = in, p2 = in + l - 1;
*p1 != STAR && *p2 != STAR; p1++, p2--) {
if (!Pateq(*p1, *p2))
return REJECT;
*out++ = (*p1 != DOT) ? *p1 : *p2;
}
if (*p2 == STAR) /* a is not shorter than b */
while (*p1 != STAR)
*out++ = *p1++;
else /* a is shorter than b */
while (*p2 != STAR)
*out++ = *p2--;
*out++ = STAR;
*out++ = '\0';
return CONT;
} else if (*in != STAR) {
/* "a*..." */
int refp, left, right;
char *p, tmpbuf[MAXPWLINE];
*(strchr(in, STAR) + 1) = '\0'; /* "a*..." -> "a*" */
if (debug)
message("debug: Reflect: in -> \"%s\"\n", visible(in));
l = strlen(in);
/* l / 2 is the mid position except STAR */
/* get an inverted original image in tmpbuf */
for (refp = l / 2; refp < l - 1; refp++) {
p = tmpbuf;
*p++ = STAR;
for (left = refp - 1, right = refp;
in[right] != STAR; left--, right++) {
if (Pateq(in[left], in[right])) {
*p++ = in[left]; /* preserving DOT */
continue;
} else
/* try to search for another reflex point */
break;
}
if (in[right] == STAR) {
/* refp is a reflex point */
for (; left >= 0; left--)
*p++ = in[left];
*p = '\0';
/* The inverted original image is got */
revpat(out, tmpbuf);
return CONT;
} else
continue;
}
/* no reflex point is found */
return REJECT;
} else if (in[l-1] != STAR) {
/* "...*b" */
int cond;
revpat(out, in); /* make it into "a*" form */
if (debug)
message("debug: Reflect: recurring with \"%s\"\n",
visible(out));
cond = revReflect(out, in); /* recur */
revpat(out, in);
if (debug)
message("debug: Reflect: recursion end with \"%s\"\n",
visible(out));
return cond;
} else {
/* "*...*" */
return MAYBE;
}
} else if (l % 2) {
/* the length of the pattern is odd */
return REJECT;
} else {
/* the length of the pattern is even */
char *c1 = in, *c2 = in + l - 1;
l /= 2;
while (l--) {
if (Pateq(*c1,*c2)) {
*out++ = (*c1 != DOT) ? *c1 : *c2;
c1++;
c2--;
} else
return REJECT;
}
*out = '\0';
return CONT;
}
}
revSubstitute(in, out, x, y)
char *in, *out;
char x, y;
{
strcpy(out, in);
while (*out != '\0') {
if (*out == x)
return REJECT; /* must have been substituted */
if (*out == y)
*out = DOT; /* x or y, actually */
out++;
}
return CONT;
}
revClassSubstitute(in, out, c, y)
char *in, *out;
char c, y;
{
strcpy(out, in);
while (*out != '\0') {
/* equality of *out and y should be checked first */
/* concerning the case that y is in c */
if (*out == y)
*out = DOT;
else if (*out != DOT && *out != STAR && MatchClass(c, *out))
return REJECT; /* must have been substituted */
out++;
}
return CONT;
}
revMatch(in, out, x)
char *in, *out;
char x;
{
strcpy(out, in);
while (*out != '\0') {
if (*out == DOT || *out == STAR || *out == x)
return CONT;
out++;
}
return REJECT;
}
revClassMatch(in, out, c)
char *in, *out;
char c;
{
strcpy(out, in);
while (*out != '\0') {
if (*out == DOT || *out == STAR || MatchClass(c, *out))
return CONT;
out++;
}
return REJECT;
}
revNot(in, out, x)
char *in, *out;
char x;
{
strcpy(out, in);
while (*out != '\0') {
if (*out == x)
return REJECT;
out++;
}
return CONT;
}
revClassNot(in, out, c)
char *in, *out;
char c;
{
strcpy(out, in);
while (*out != '\0') {
if (*out != DOT && *out != STAR && MatchClass(c, *out))
return REJECT;
out++;
}
return CONT;
}
revLt(in, out, i)
char *in, *out;
int i;
{
strcpy(out, in);
if (patlen_shortest(out) < i)
return CONT;
else
return REJECT;
}
revGt(in, out, i)
char *in, *out;
int i;
{
int l;
strcpy(out, in);
if ((l = patlen(out)) < 0 || l > i)
return CONT;
else
return REJECT;
}
revExtract(in, out, n, m)
char *in, *out;
int n, m;
{
int l;
char *tail;
/* rejecting cases */
if (patlen_shortest(in) > m)
return REJECT;
if ((l = patlen(in)) >= 0 && m != l)
return REJECT; /* means finite but the lengths are not equal */
/* prepend DOTs and append STAR */
while (n--)
*out++ = DOT;
strcpy(out, in);
if (strlen(out) == 0) {
out[0] = STAR;
out[1] = '\0';
return CONT;
} else {
tail = out + strlen(out) - 1;
if (*tail == STAR) {
tail[1] = '\0';
return CONT;
} else {
tail[1] = STAR;
tail[2] = '\0';
return CONT;
}
}
}
revOverstrike(in, out, n, x)
char *in, *out;
int n;
char x;
{
int pos;
if ((pos = patpos(in, n)) < 0)
return REJECT; /* you cannot tell where having been overstruck */
strcpy(out, in);
switch (out[pos]) {
case DOT:
case STAR:
return CONT;
default:
if (out[pos] == x) {
out[pos] = DOT;
return CONT;
} else
return REJECT;
}
}
revInsert(in, out, n, x)
char *in, *out;
int n;
char x;
{
int pos;
if ((pos = patpos(in, n)) < 0) {
return REJECT;
} else if (in[pos] == STAR) {
strcpy(out, in);
return CONT; /* you cannot tell the inserted position */
} else if (in[pos] == DOT || in[pos] == x) {
if (pos > 0) /* guard */
strncpy(out, in, pos);
strcpy(out+pos, in+pos+1);
return CONT;
} else
return REJECT;
}
revEquals(in, out, n, x)
char *in, *out;
int n;
char x;
{
int pos;
if ((pos = patpos(in, n)) < 0 || in[pos] == STAR || in[pos] == x) {
strcpy(out, in);
return CONT;
} else if (in[pos] == DOT) {
strcpy(out, in);
out[pos] = x; /* should be */
return CONT;
} else
return REJECT;
}
revClassEquals(in, out, n, c)
char *in, *out;
int n;
char c;
{
int pos;
if ((pos = patpos(in, n)) < 0 || in[pos] == STAR ||
in[pos] == DOT || MatchClass(c, in[pos])) {
strcpy(out, in);
return CONT;
} else
return REJECT;
}
revPurge(in, out, x)
char *in, *out;
char x;
{
*out++ = STAR; /* a STAR at the top */
while (*in != '\0') {
if (*in == x) /* must have been purged */
return REJECT;
else if (*in == STAR) {
/* a STAR should have been placed at (out-1) */
in++;
continue;
} else {
/* the DOT case is included */
*out++ = *in++;
*out++ = STAR;
continue;
}
}
/* another STAR at the end */
return CONT;
}
revClassPurge(in, out, c)
char *in, *out;
char c;
{
*out++ = STAR; /* a STAR at the top */
while (*in != '\0') {
if (*in == STAR) {
/* a STAR should have been placed at (out-1) */
in++;
continue;
} else if (*in != DOT && MatchClass(c, *in)) {
return REJECT;
} else {
/* the DOT case is included */
*out++ = *in++;
*out++ = STAR;
continue;
}
}
/* another STAR at the end */
return CONT;
}