/* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. *//* multipattern matcher */#include <stdio.h>#include <ctype.h>#define MAXPAT  256#define MAXLINE 1024#define MAXSYM  256#define MAXMEMBER1 4096#define MAXPATFILE 260000#define BLOCKSIZE  8192#define MAXHASH    8192#define mm 	   8191#define max_num    30000  #define W_DELIM	   128#define L_DELIM    10 extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;extern INVERSE;extern WORDBOUND, WHOLELINE, NOUPPER;extern unsigned char  CurrentFileName[], Progname[]; extern total_line;int LONG  = 0;int SHORT = 0;int p_size=0;unsigned char SHIFT1[MAXMEMBER1];unsigned char tr[MAXSYM];unsigned char tr1[MAXSYM];struct pat_list {	int  index;	struct pat_list *next;} *HASH[MAXHASH];struct pat_list  *pt, *qt;unsigned char buf[MAXPATFILE+BLOCKSIZE];unsigned char pat_spool[MAXPATFILE+2*max_num+MAXPAT];unsigned char *patt[max_num];unsigned char pat_len[max_num];prepf(fp)int fp;{    int length=0, i, p=1, pdx=0, num_pat;    unsigned char *pat_ptr=pat_spool, temp[10];    unsigned Mask = 15;    int num_read;    while((num_read = read(fp, buf+length, BLOCKSIZE)) > 0) {	length = length + num_read;	if(length > MAXPATFILE) {		fprintf(stderr, "%s: maximum pattern file size is %d\n", Progname, MAXPATFILE);		exit(2);	}    }    buf[length] = '\n';    i = 0; p=1;    while(i<length) {	patt[p] = pat_ptr;	if(WORDBOUND) *pat_ptr++ = W_DELIM;	if(WHOLELINE) *pat_ptr++ = L_DELIM;	while((*pat_ptr = buf[i++]) != '\n') pat_ptr++;	if(WORDBOUND) *pat_ptr++ = W_DELIM;	if(WHOLELINE) *pat_ptr++ = L_DELIM;           /* Can't be both on */	*pat_ptr++ = 0;	p++;      }    if(p>max_num) {	fprintf(stderr, "%s: maximum number of patterns is %d\n", Progname, max_num); 	exit(2);    }    for(i=1; i<20; i++) *pat_ptr = i;  /* boundary safety zone */    for(i=0; i< MAXSYM; i++) tr[i] = i;    if(NOUPPER) {	for(i='A'; i<= 'Z'; i++) tr[i] = i + 'a' - 'A';    }    if(WORDBOUND) {	for(i=0; i<128; i++) if(!isalnum(i)) tr[i] = W_DELIM;    }    for(i=0; i< MAXSYM; i++) tr1[i] = tr[i]&Mask;    num_pat = p-1;    p_size = MAXPAT;    for(i=1 ; i <= num_pat; i++) {	p = strlen(patt[i]);	pat_len[i] = p;	if(p!=0 && p < p_size) p_size = p;    }    if(p_size == 0) {	fprintf(stderr, "%s: the pattern file is empty\n");	exit(2);    }    if(length > 400 && p_size > 2) LONG = 1;    if(p_size == 1) SHORT = 1;    for(i=0; i<MAXMEMBER1; i++) SHIFT1[i] = p_size - 2;    for(i=0; i<MAXHASH; i++) {	HASH[i] = 0;    }    for(i=1; i<= num_pat; i++) f_prep(i, patt[i]);}mgrep(fd)int fd;{     register char r_newline = '\n';    unsigned char text[2*BLOCKSIZE+MAXLINE];     register int buf_end, num_read, i=0, j, start, end, residue = 0;    text[MAXLINE-1] = '\n';  /* initial case */    start = MAXLINE-1;    while( (num_read = read(fd, text+MAXLINE, BLOCKSIZE)) > 0)     {       if(INVERSE && COUNT) countline(text+MAXLINE, num_read);       buf_end = end = MAXLINE + num_read -1 ;       while(text[end]  != r_newline && end > MAXLINE) end--;       residue = buf_end - end  + 1 ;       text[start-1] = r_newline;       if(SHORT) m_short(text, start, end);       else      monkey1(text, start, end);       if(FILENAMEONLY && num_of_matched) {		printf("%s\n", CurrentFileName);		return;       }       start = MAXLINE - residue;       if(start < 0) {            start = 1;        }       strncpy(text+start, text+end, residue);    } /* end of while(num_read = ... */    text[MAXLINE] = '\n';    text[start-1] = '\n';    if(residue > 1) {        if(SHORT) m_short(text, start, end);        else      monkey1(text, start, end);    }    return;} /* end mgrep */countline(text, len)unsigned char *text; int len;{int i;	for (i=0; i<len; i++) if(text[i] == '\n') total_line++;}monkey1( text, start, end  ) int start, end; register unsigned char *text;{register unsigned char *textend;register unsigned hash, i;register unsigned char shift; register int  m1, j, Long=LONG; int pat_index, m=p_size; int MATCHED=0;register unsigned char *qx;register struct pat_list *p;unsigned char *lastout;int OUT=0;textend = text + end;m1 = m - 1;lastout = text+start+1;text = text + start + m1 ;while (text <= textend) {	hash=tr1[*text];	hash=(hash<<4)+(tr1[*(text-1)]);	if(Long) hash=(hash<<4)+(tr1[*(text-2)]);	shift = SHIFT1[hash];	if(shift == 0) {		hash=0;		for(i=0;i<=m1;i++)  {		    hash=(hash<<4)+(tr1[*(text-i)]);		}		hash=hash&mm;		p = HASH[hash];		while(p != 0) {			pat_index = p->index;			p = p->next;			qx = text-m1;			j = 0;			while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;	        	if (j > m1 ) { 			   if(pat_len[pat_index] <= j) {				if(text > textend) return;                		num_of_matched++;                		if(FILENAMEONLY || SILENT)  return;				MATCHED=1;	        		if(COUNT) {			  		while (*text != '\n') text++;				}				else {				    if(!INVERSE) {			  		if(FNAME) printf("%s: ",CurrentFileName);                          		while(*(--text) != '\n');                          		while(*(++text) != '\n') putchar(*text);			  		printf("\n");				    }				    else {			  		if(FNAME) printf("%s: ",CurrentFileName);                          		while(*(--text) != '\n');					if(lastout < text) OUT=1;					while(lastout < text) putchar(*lastout++);					if(OUT) {						putchar('\n');						OUT=0;					}                          		while(*(++text) != '\n');					lastout=text+1;				    }				}/*				else {			  		if(FNAME) printf("%s: ",CurrentFileName);                          		while(*(--text) != '\n');                          		while(*(++text) != '\n') putchar(*text);			  		printf("\n");				}*/			   }                	}			if(MATCHED) break;		}		if(!MATCHED) shift = 1;		else {			MATCHED = 0;			shift = m1;		}        }	text = text + shift;  }  if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);}m_short( text, start, end  ) int start, end; register unsigned char *text;{register unsigned char *textend;register unsigned i; register int  j; register struct pat_list *p, *q;register int pat_index; int MATCHED=0;int OUT=0;unsigned char *lastout;unsigned char *qx;textend = text + end;lastout = text + start + 1;text = text + start - 1 ;while (++text <= textend) {		p = HASH[*text];		while(p != 0) {			pat_index = p->index;			p = p->next;			qx = text;			j = 0;			while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;			if(pat_len[pat_index] <= j) {				if(text >= textend) return;                		num_of_matched++;                		if(FILENAMEONLY || SILENT)  return;	        		if(COUNT) {			  		while (*text != '\n') text++;				}				else {			  	    if(FNAME) printf("%s: ",CurrentFileName);				    if(!INVERSE) {                          		while(*(--text) != '\n');                          		while(*(++text) != '\n') putchar(*text);			  		printf("\n");					MATCHED = 1;				    }				    else {                          		while(*(--text) != '\n');					if(lastout < text) OUT=1;					while(lastout < text) putchar(*lastout++);					if(OUT) {						putchar('\n');						OUT=0;					}                          		while(*(++text) != '\n');					lastout=text+1;					MATCHED = 1;				    }				}                	}			if(MATCHED) break;		}		MATCHED = 0;  } /* while */  if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);}f_prep(pat_index, Pattern)unsigned char *Pattern ; int pat_index;{int i, j, m;register unsigned hash, Mask=15;	m = p_size;	for (i = m-1; i>=(1+LONG); i--) {		hash = (Pattern[i] & Mask);		hash = (hash << 4) + (Pattern[i-1]& Mask);		if(LONG) hash = (hash << 4) + (Pattern[i-2] & Mask);		if(SHIFT1[hash] >= m-1-i) SHIFT1[hash] = m-1-i;	}	if(SHORT) Mask = 255;  /* 011111111 */	hash = 0;	for(i = m-1; i>=0; i--)  {	    hash = (hash << 4) + (tr[Pattern[i]]&Mask);	}/*	if(INVERSE) hash = Pattern[1];*/	hash=hash&mm;	qt = (struct pat_list *) malloc(sizeof(struct pat_list));	qt->index = pat_index;	pt = HASH[hash];	qt->next = pt;	HASH[hash] = qt;}