sgrep.c

agrep

            if((R2[D] & endpos) == 0) { currentpos = i;
                                    num_of_matched++;
                                    if(FILENAMEONLY) { return; }
                                    if(i <= lastend) i = lastend;
                                    else {
                                       s_output(text, &currentpos); 
                                       i = currentpos; 
                                    }
                                    lastend = i;
                                    for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
                                  }
     }
  }
  return;
}

s_output (text, i) 
int *i; CHARTYPE *text;
{
int kk, bp;
        if(SILENT) return;
        if(COUNT) {
		while(text[*i] != '\n') *i = *i + 1; 
		return;
	}
        if(FNAME == ON) printf("%s: ", CurrentFileName);
        bp = *i;
        while(text[--bp] != '\n');
        while(text[++bp] != '\n') putchar(text[bp]);
        putchar('\n');
        *i = bp;
}


prep_bm(Pattern, m)      
	unsigned char *Pattern;
	register m;
{
int i, j;
unsigned hash;
unsigned char lastc;
	for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
	for (i = m-1; i>=0; i--) {
		hash = TR[Pattern[i]];
		if(SHIFT[hash] >= m - 1) SHIFT[hash] = m-1-i;
	}
	shift_1 = m-1;
	lastc = TR[Pattern[m-1]];
	for (i= m-2; i>=0; i--) {
		if(TR[Pattern[i]] == lastc )
			{ shift_1 = m-1 - i;  i = -1; }
	}
	if(shift_1 == 0) shift_1 = 1;
	if(NOUPPER) for(i='A'; i<='Z'; i++) SHIFT[i] = SHIFT[i +  'a' - 'A'];
#ifdef DEBUG
	for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
	for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
#endif
}


/* a_monkey() the approximate monkey move */

a_monkey( pat, m, text, textend, D ) 
register int m, D ; register CHARTYPE *text, *textend, *pat;
{
register CHARTYPE *oldtext;
register unsigned hash, i, hashmask, suffix_error; 
register int  m1 = m-1-D, j, pos; 

  	hashmask = Hashmask;
  	oldtext  = text;
  	while (text < textend) {
     		text = text+m1;
     		suffix_error = 0;
     		while(suffix_error <= D) {
			hash = *text--;
			while(MEMBER_1[hash]) {
	      			hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
			}
			suffix_error++;
     		}
     		if(text <= oldtext) {
		           if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
				text = oldtext+pos;
				if(text > textend) return;
				num_of_matched++;
				if(FILENAMEONLY) return;
				if(!(COUNT)) {
					if(FNAME) printf("%s: ", CurrentFileName);
					while(*(--text) != '\n');
			 		while(*(++text) != '\n') putchar(*text);
			        	printf("\n");
				}
				else {
					while(*text != '\n') text++;
				}
			   }
			   else { 
			        text = oldtext + m;
			   }
     		}
     		oldtext = text; 
  	}
}

/* monkey uses two characters for delta_1 shifting */

CHARTYPE SHIFT_2[MAX_SHIFT_2];

monkey( pat, m, text, textend  ) 
register int m  ; register CHARTYPE *text, *textend, *pat;
{
register unsigned hash, i; 
register CHARTYPE shift;
register int  m1, j; 
register unsigned r_newline;

r_newline = '\n';

  m1 = m - 1;
  text = text+m1;
  while (text < textend) {
	hash = *text;
	hash = (hash << 3) + *(text-1);
	shift = SHIFT_2[hash];
	while(shift) {
		text = text + shift;
		hash = (*text << 3) + *(text-1);
		shift = SHIFT_2[hash];
	}
	j = 0;
	while(TR[pat[m1 - j]] == TR[*(text - j)]) { if(++j == m) break; }
	if (j == m ) { 
		if(text >= textend) return;
                num_of_matched++;
                if(FILENAMEONLY)  return;
	        if(COUNT) {
			  while (*text != r_newline) text++;
			  text--;
		}
		else {
			  if(FNAME) printf("%s: ", CurrentFileName);
                          while(*(--text) != r_newline);
                          while(*(++text) != r_newline) putchar(*text);
			  printf("\n");
			  text--;
		}
        }
	text++;
  }
}
 
am_preprocess(Pattern)
CHARTYPE *Pattern;
{
int i, j, m;
unsigned hash;
	m = strlen(Pattern);
	for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
	for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
	for (i = m-1; i>=0; i--) {
		MEMBER_1[Pattern[i]] = 1;
        }
	for (i = m-1; i > 0; i--) {
	   	MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
	}
}


verify(m, n, D, pat, text)
register int m, n, D;
CHARTYPE *pat, *text;
{   
    int A[MAXPATT], B[MAXPATT];
    register int last = D;      
    register int cost = 0;  
    register int k, i, c;
    register int m1 = m+1;
    CHARTYPE *textend = text+n;
    CHARTYPE *textbegin = text;

   for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
   while (text < textend)
   {
       for (k = 1; k <= last; k++)
       {
           cost = B[k-1]+1; 
           if (pat[k-1] != *text)
           {   if (B[k]+1 < cost) cost = B[k]+1; 
               if (A[k-1]+1 < cost) cost = A[k-1]+1; }
           else cost = cost -1; 
           A[k] = cost; 
       }
       if(pat[last] == *text++) { A[last+1] = B[last]; last++; }
       if(A[last] < D) A[last+1] = A[last++]+1;
       while (A[last] > D) last = last - 1;
       if(last >= m) return(text - textbegin - 1);
       if(*text == '\n') {
            last = D;
	    for(c = 0; c<=m1; c++) A[c] = B[c] = c;
       }
       for (k = 1; k <= last; k++)
       {
           cost = A[k-1]+1; 
           if (pat[k-1] != *text)
           {   if (A[k]+1 < cost) cost = A[k]+1; 
               if (B[k-1]+1 < cost) cost = B[k-1]+1; }
           else cost = cost -1; 
           B[k] = cost;
       }
       if(pat[last] == *text++) { B[last+1] = A[last]; last++; }
       if(B[last] < D) B[last+1] = B[last++]+1;
       while (B[last] > D) last = last -1;
       if(last >= m)   return(text - textbegin - 1);
       if(*text == '\n') {
            last = D;
	    for(c = 0; c<=m1; c++) A[c] = B[c] = c;
       }
   }    
   return(0);
}

/* preprocessing for monkey()   */

m_preprocess(Pattern)
CHARTYPE *Pattern;
{
int i, j, m;
unsigned hash;
	m = strlen(Pattern);
	for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
	for (i = m-1; i>=1; i--) {
		hash = Pattern[i];
		hash = hash << 3;
		for (j = 0; j< MAXSYM; j++) {
			if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
		}
		hash = hash + Pattern[i-1];
		if(SHIFT_2[hash] >= m - 1) SHIFT_2[hash] = m-1-i;
	}
	shift_1 = m-1;
	for (i= m-2; i>=0; i--) {
		if(Pattern[i] == Pattern[m-1] )
			{ shift_1 = m-1 - i;  i = -1; }
	}
	if(shift_1 == 0) shift_1 = 1;
	SHIFT_2[0] = 0;
}

/* monkey4() the approximate monkey move */

char *MEMBER_D;

monkey4( pat, m, text, textend, D  ) 
register int m, D ; register unsigned char *text, *pat, *textend;
{
register unsigned char *oldtext;
register unsigned hash, i, hashmask, suffix_error; 
register int m1=m-1-D, j, pos; 

  hashmask = Hashmask;
  oldtext = text ;
  while (text < textend) {
     text = text + m1;
     suffix_error = 0;
     while(suffix_error <= D) {
	hash = char_map[*text--];
	hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
	while(MEMBER_D[hash]) {
	      hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
	}
	suffix_error++;
     }
     if(text <= oldtext) {
		           if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
				text = oldtext+pos;
				if(text > textend) return;
				num_of_matched++;
				if(FILENAMEONLY) return;
				if(!(COUNT)) {
					if(FNAME) printf("%s:", CurrentFileName);
					while(*(--text) != '\n');
			 		while(*(++text) != '\n') putchar(*text);
			        	printf("\n");
					text++;
				}
				else {
					while(*text != '\n') text++;
					text++;
				}
			   }
			   else text = oldtext + m;
     }
     oldtext = text; 
  }
}
 
prep4(Pattern, m)
char *Pattern; int m;
{
int i, j, k;
unsigned hash;

for(i=0; i< MAXSYM; i++) char_map[i] = 0;
char_map['a'] = char_map['A'] = 4;
char_map['g'] = char_map['g'] = 1;
char_map['t'] = char_map['t'] = 2;
char_map['c'] = char_map['c'] = 3;
char_map['n'] = char_map['n'] = 5;

	BSize = blog(4, m);
	for (i = 1, Hashmask = 1 ; i<BSize*LOG_DNA; i++) Hashmask = (Hashmask << 1) + 1 ;
	MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
#ifdef DEBUG
	printf("BSize = %d", BSize);
#endif 
	for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
	for (j=0; j < BSize; j++) {
            for(i=m-1; i >= j; i--) {
               hash = 0;
	       for(k=0; k <= j; k++) 
		  hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
#ifdef DEBUG
	       printf("< %d >, ", hash);
#endif
	       MEMBER_D[hash] = 1;
            }
        }
}

blog(base, m )
int base, m;
{
int i, exp;
	exp = base;
        m = m + m/2;
	for (i = 1; exp < m; i++) exp = exp * base;
	return(i);
}