home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / agrep-2.01 / part03 / sgrep.c < prev   
Encoding:
C/C++ Source or Header  |  1992-05-08  |  18.2 KB  |  686 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. #include <stdio.h>
  3. #define MAXSYM  256
  4. #define MAXMEMBER 8192
  5. #define    CHARTYPE    unsigned char
  6. #define MaxError 20
  7. #define MAXPATT 256
  8. #define MAXLINE 1024
  9. #define MaxCan  2048
  10. #define BLOCKSIZE    8192
  11. #define MAX_SHIFT_2  4096
  12. #define ON      1
  13. #define LOG_ASCII 8
  14. #define LOG_DNA  3
  15. #define MAXMEMBER_1 65536
  16. #define LONG_EXAC  20
  17. #define LONG_APPX  24
  18. #define W_DELIM    2
  19.  
  20. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  21. extern DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  22.          p_size > 16  */
  23. extern WORDBOUND, WHOLELINE, NOUPPER;
  24. extern unsigned char CurrentFileName[],  Progname[]; 
  25. extern unsigned Mask[];
  26. extern unsigned endposition;
  27.  
  28. unsigned char BSize;                /* log_c m   */
  29. unsigned char char_map[MAXSYM];
  30.     
  31.  
  32. /* data area */
  33. int shift_1;
  34. CHARTYPE SHIFT[MAXSYM];
  35. CHARTYPE MEMBER[MAXMEMBER];
  36. CHARTYPE pat[MAXPATT];
  37. unsigned Hashmask;
  38. char MEMBER_1[MAXMEMBER_1];
  39. CHARTYPE TR[MAXSYM];
  40.  
  41. char_tr(pat, m)
  42.     unsigned char *pat;
  43.     int *m;
  44. {
  45. int i;
  46. unsigned char temp[MAXPATT];
  47.     for(i=0; i<MAXSYM; i++) TR[i] = i;
  48.     if(NOUPPER) {
  49.         for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A';
  50.     }
  51.     if(WORDBOUND) { /* SUN: To be added to be more complete */
  52.         TR['\n'] = TR['\t'] = TR[' '] = TR[','] = TR[';'] = TR[':'] = 
  53.             TR['!'] = TR['"'] = TR['?'] = TR['<'] = TR['>'] = 
  54.         TR['='] = TR['['] = TR[']'] = TR['\''] =
  55.             TR['('] = TR[')'] = TR['$'] = TR['/'] = TR['\\'] = W_DELIM;
  56.     }
  57.     if(WHOLELINE) {
  58.         memcpy(temp, pat, *m);
  59.         pat[0] = '\n';
  60.         memcpy(pat+1, temp, *m);
  61.         pat[*m+1] = '\n';
  62.         pat[*m+2] = 0;
  63.         *m = *m + 2;
  64.     }
  65. }
  66.  
  67. sgrep(pat, m, fd, D)
  68. CHARTYPE *pat;  int fd, m, D;
  69. { 
  70.     CHARTYPE text[BLOCKSIZE+2*MAXLINE+MAXPATT]; /* input text stream */
  71.     int offset = 2*MAXLINE;
  72.     int buf_end, num_read, i, start, end, residue = 0;
  73.     if(pat[0] == '^' || pat[0] == '$') pat[0] = '\n';
  74.     if(pat[m-1] == '^' || pat[m-1] == '$') pat[m-1] = '\n';
  75.     char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */
  76.     text[offset-1] = '\n';  /* initial case */
  77.     for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  78.     start = offset;   
  79.     if(WHOLELINE) start--;
  80.     if(m >= MAXPATT) {
  81.          fprintf(stderr, "%s: pattern too long\n", Progname);
  82.          exit(2);
  83.     }
  84.     if(D == 0) {
  85.     if(m > LONG_EXAC) m_preprocess(pat);
  86.     else prep_bm(pat, m);
  87.     }
  88.     else if (DNA) prep4(pat, m);
  89.      else     if(m >= LONG_APPX) am_preprocess(pat);
  90.         else {
  91.             prep(pat, m, D);
  92.             initmask(pat, Mask, m, 0, &endposition); 
  93.         }
  94.     for(i=1; i<=m; i++) text[BLOCKSIZE+offset+i] = pat[m-1];
  95.         /* to make sure the skip loop in bm() won't go out of bound */
  96.     while( (num_read = read(fd, text+offset, BLOCKSIZE)) > 0) 
  97.     {
  98.        buf_end = end = offset + num_read -1 ;
  99.        if(num_read < BLOCKSIZE) if(text[end] != '\n') text[++end] = '\n';
  100.        while(text[end]  != '\n' && end > offset) end--;
  101.        residue = buf_end - end + 1 ;
  102.        text[start-1] = '\n';
  103.        if(D==0)  {
  104.         if(m > LONG_EXAC) monkey(pat, m, text+start, text+end);
  105.         else bm(pat, m, text+start, text+end);
  106.        }
  107.        else {
  108.         if(DNA) monkey4( pat, m, text+start, text+end, D  );
  109.         else {
  110.           if(m >= LONG_APPX) a_monkey(pat, m, text+start, text+end, D);
  111.           else       agrep(pat, m, text+start, text+end, D);
  112.         }
  113.        }
  114.        if(FILENAMEONLY && num_of_matched) {
  115.             printf("%s\n", CurrentFileName);
  116.             return; }
  117.        start = offset - residue ;
  118.        if(start < MAXLINE) {
  119.             start = MAXLINE; 
  120.        }
  121.        strncpy(text+start, text+end, residue);
  122.        start++;
  123.     } /* end of while(num_read = ... */
  124.     return;
  125. } /* end sgrep */
  126.  
  127. /* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  128. pat[m-1] such that the skip loop is guaranteed to terminated */
  129.  
  130. bm(pat, m, text, textend)
  131.     CHARTYPE *text, *textend, *pat;  int m;
  132. {
  133. register int shift;
  134. register int  m1, j, d1; 
  135.  
  136. /*
  137. printf("%d\t", textend - text);
  138. printf("%c, %c", *text, *textend);
  139. */
  140.  
  141. d1 = shift_1;    /* at least 1 */
  142. m1 = m - 1;
  143. shift = 0;       
  144. while (text <= textend) {
  145.     shift = SHIFT[*(text += shift)];
  146.     while(shift) {          
  147.         shift = SHIFT[*(text += shift)];
  148.         shift = SHIFT[*(text += shift)];
  149.         shift = SHIFT[*(text += shift)];
  150.     }
  151.         j = 0;
  152.         while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  153.             if(++j == m)  break;       /* if statement can be
  154.                             saved, but for safty ... */
  155.         }
  156.             if (j == m ) { 
  157.             if(text > textend) return;
  158.             if(WORDBOUND) {
  159.                 if(TR[*(text+1)] != W_DELIM) goto CONT;
  160.                 if(TR[*(text-m)] != W_DELIM) goto CONT;
  161.             }
  162.             num_of_matched++;
  163.             if(FILENAMEONLY) return;
  164.             if(!(COUNT)) {
  165.                 if(FNAME) printf("%s: ", CurrentFileName);
  166.                 while(*(--text) != '\n');
  167.                 while(*(++text) != '\n') putchar(*(text));
  168.                 putchar(*text);
  169.             }
  170.             else { while(*text != '\n') text++; } 
  171. CONT:
  172.             shift = 1;
  173.                 }
  174.         else shift = d1;
  175.   }
  176. return;
  177. }
  178.  
  179.   
  180. /* initmask() initializes the mask table for the pattern                    */ 
  181. /* endposition is a mask for the endposition of the pattern                 */
  182. /* endposition will contain k mask bits if the pattern contains k fragments */
  183. initmask(pattern, Mask, m, D, endposition)
  184. CHARTYPE *pattern; unsigned *Mask; register int m, D; unsigned *endposition;
  185. {
  186.   register unsigned Bit1, c;
  187.   register int i, j, frag_num;
  188.  
  189.   Bit1 = 1 << 31;    /* the first bit of Bit1 is 1, others 0.  */
  190.   frag_num = D+1; *endposition = 0;
  191.   for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  192.   *endposition = *endposition >> (m - frag_num);
  193.   for(i = 0; i < m; i++) 
  194.           if (pattern[i] == '^' || pattern[i] == '$') {
  195.               pattern[i] = '\n'; 
  196.           }
  197.   for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  198.   for(i = 0; i < m; i++)     /* initialize the mask table */
  199.   {  c = pattern[i];
  200.      for ( j = 0; j < m; j++)
  201.            if( c == pattern[j] )
  202.                Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  203.   }
  204. }
  205.  
  206. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  207.     CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  208.     register int M, D;
  209. {
  210. register int i, j, k, p, shift;
  211. register unsigned m;
  212. unsigned hash, b_size = 3;
  213.     m = M/(D+1);
  214.     p = M - m*(D+1);
  215.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  216.     for (i = M-1; i>=p ; i--) {
  217.         shift = (M-1-i)%m;
  218.         hash = Pattern[i];
  219.         if(SHIFT[hash] > shift) SHIFT[hash] = shift;
  220.     }
  221. #ifdef DEBUG
  222.     for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  223.     printf("\n");
  224. #endif
  225.     shift_1 = m;
  226.     for(i=0; i<D+1; i++) {
  227.         j = M-1 - m*i;
  228.         for(k=1; k<m; k++) {
  229.             for(p=0; p<D+1; p++) 
  230.                 if(Pattern[j-k] == Pattern[M-1-m*p]) 
  231.                     if(k < shift_1) shift_1 = k;
  232.         }
  233.     }
  234. #ifdef DEBUG
  235.     printf("\nshift_1 = %d", shift_1);
  236. #endif
  237.     if(shift_1 == 0) shift_1 = 1;
  238.     for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  239.     if (m < 3) b_size = m;
  240.     for(i=0; i<D+1; i++) {
  241.         j = M-1 - m*i;
  242.         hash = 0;
  243.         for(k=0; k<b_size; k++) {
  244.             hash = (hash << 2) + Pattern[j-k];
  245.         }
  246. #ifdef DEBUG
  247.     printf(" hash = %d,", hash);
  248. #endif
  249.         MEMBER[hash] = 1;
  250.     }
  251. }
  252.  
  253.  
  254. agrep( pat, M, text, textend, D ) 
  255. int M, D ; register CHARTYPE *text, *textend, *pat;
  256. {
  257.   register int i;
  258.   register int m = M/(D+1);
  259.   register CHARTYPE *textstart;
  260.   register int shift, HASH;
  261.   int  j=0, k, m1, d1;
  262.   int  n, cdx;
  263.   int  Candidate[MaxCan][2], round, lastend=0;
  264.   unsigned R1[MaxError+1], R2[MaxError+1]; 
  265.   register unsigned int r1, endpos, c; 
  266.   unsigned currentpos;
  267.   unsigned Bit1;
  268.   unsigned r_newline;
  269.  
  270.   Candidate[0][0] = Candidate[0][1] = 0; 
  271.   d1 = shift_1;
  272.   cdx = 0;
  273.   if(m < 3) r1 = m;
  274.   else r1 = 3;
  275.   textstart = text;
  276.   shift = m-1;
  277.   while (text < textend) {
  278.     shift = SHIFT[*(text += shift)];
  279.     while(shift) {
  280.         shift = SHIFT[*(text += shift)];
  281.         shift = SHIFT[*(text += shift)];
  282.     }
  283.         j = 1; HASH = *text;
  284.         while(j < r1) { HASH = (HASH << 2) + *(text-j);
  285.                 j++; }
  286.             if (MEMBER[HASH]) { 
  287.             i = text - textstart;
  288.                          if((i - M - D - 10) > Candidate[cdx][1]) {     
  289.                 Candidate[++cdx][0] = i-M-D-2;
  290.                               Candidate[cdx][1] = i+M+D; }
  291.                          else Candidate[cdx][1] = i+M+D;
  292.             shift = d1;
  293.                 }
  294.         else shift = d1;
  295.   }
  296.  
  297.  
  298.   text = textstart;
  299.   n = textend - textstart;
  300.   r_newline = '\n';
  301.   /* for those candidate areas, find the D-error matches                     */
  302.   if(Candidate[1][0] < 0) Candidate[1][0] = 0;
  303.   endpos = endposition;                /* the mask table and the endposition */
  304.   Bit1 = (1 << 31);
  305.   for(round = 0; round <= cdx; round++)
  306.   {  i = Candidate[round][0] ; 
  307.      if(Candidate[round][1] > n) Candidate[round][1] = n;
  308.      if(i < 0) i = 0;
  309. #ifdef DEBUG
  310.      printf("round: %d, start=%d, end=%d, ", round, i, Candidate[round][1]);
  311. #endif
  312.      R1[0] = R2[0] = ~0;
  313.      R1[1] = R2[1] = ~Bit1;
  314.      for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];
  315.      while (i < Candidate[round][1])                     
  316.      {  
  317.         c = text[i++];
  318.             if(c == r_newline) {
  319.                for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  320.             }
  321.             r1 = Mask[c];
  322.             R1[0] = (R2[0] >> 1) | r1;
  323.             for(k=1; k<=D; k++)
  324.                 R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  325.             if((R1[D] & endpos) == 0) { 
  326.                                     num_of_matched++;
  327.                                     if(FILENAMEONLY) { return; }
  328.                                     currentpos = i;
  329.                                     if(i <= lastend) i = lastend;
  330.                                     else {
  331.                                        s_output(text, ¤tpos); 
  332.                                        i = currentpos; 
  333.                                     }
  334.                                     lastend = i;
  335.                                     for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  336.                                   }
  337.             c = text[i++];
  338.             if(c == r_newline) {
  339.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  340.             }
  341.             r1 = Mask[c];
  342.             R2[0] = (R1[0] >> 1) | r1;
  343.             for(k = 1; k <= D; k++)
  344.                 R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  345.             if((R2[D] & endpos) == 0) { currentpos = i;
  346.                                     num_of_matched++;
  347.                                     if(FILENAMEONLY) { return; }
  348.                                     if(i <= lastend) i = lastend;
  349.                                     else {
  350.                                        s_output(text, ¤tpos); 
  351.                                        i = currentpos; 
  352.                                     }
  353.                                     lastend = i;
  354.                                     for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  355.                                   }
  356.      }
  357.   }
  358.   return;
  359. }
  360.  
  361. s_output (text, i) 
  362. int *i; CHARTYPE *text;
  363. {
  364. int kk, bp;
  365.         if(SILENT) return;
  366.         if(COUNT) {
  367.         while(text[*i] != '\n') *i = *i + 1; 
  368.         return;
  369.     }
  370.         if(FNAME == ON) printf("%s: ", CurrentFileName);
  371.         bp = *i;
  372.         while(text[--bp] != '\n');
  373.         while(text[++bp] != '\n') putchar(text[bp]);
  374.         putchar('\n');
  375.         *i = bp;
  376. }
  377.  
  378.  
  379. prep_bm(Pattern, m)      
  380.     unsigned char *Pattern;
  381.     register m;
  382. {
  383. int i, j;
  384. unsigned hash;
  385. unsigned char lastc;
  386.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  387.     for (i = m-1; i>=0; i--) {
  388.         hash = TR[Pattern[i]];
  389.         if(SHIFT[hash] >= m - 1) SHIFT[hash] = m-1-i;
  390.     }
  391.     shift_1 = m-1;
  392.     lastc = TR[Pattern[m-1]];
  393.     for (i= m-2; i>=0; i--) {
  394.         if(TR[Pattern[i]] == lastc )
  395.             { shift_1 = m-1 - i;  i = -1; }
  396.     }
  397.     if(shift_1 == 0) shift_1 = 1;
  398.     if(NOUPPER) for(i='A'; i<='Z'; i++) SHIFT[i] = SHIFT[i +  'a' - 'A'];
  399. #ifdef DEBUG
  400.     for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  401.     for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  402. #endif
  403. }
  404.  
  405.  
  406. /* a_monkey() the approximate monkey move */
  407.  
  408. a_monkey( pat, m, text, textend, D ) 
  409. register int m, D ; register CHARTYPE *text, *textend, *pat;
  410. {
  411. register CHARTYPE *oldtext;
  412. register unsigned hash, i, hashmask, suffix_error; 
  413. register int  m1 = m-1-D, j, pos; 
  414.  
  415.       hashmask = Hashmask;
  416.       oldtext  = text;
  417.       while (text < textend) {
  418.              text = text+m1;
  419.              suffix_error = 0;
  420.              while(suffix_error <= D) {
  421.             hash = *text--;
  422.             while(MEMBER_1[hash]) {
  423.                       hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
  424.             }
  425.             suffix_error++;
  426.              }
  427.              if(text <= oldtext) {
  428.                    if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  429.                 text = oldtext+pos;
  430.                 if(text > textend) return;
  431.                 num_of_matched++;
  432.                 if(FILENAMEONLY) return;
  433.                 if(!(COUNT)) {
  434.                     if(FNAME) printf("%s: ", CurrentFileName);
  435.                     while(*(--text) != '\n');
  436.                      while(*(++text) != '\n') putchar(*text);
  437.                         printf("\n");
  438.                 }
  439.                 else {
  440.                     while(*text != '\n') text++;
  441.                 }
  442.                }
  443.                else { 
  444.                     text = oldtext + m;
  445.                }
  446.              }
  447.              oldtext = text; 
  448.       }
  449. }
  450.  
  451. /* monkey uses two characters for delta_1 shifting */
  452.  
  453. CHARTYPE SHIFT_2[MAX_SHIFT_2];
  454.  
  455. monkey( pat, m, text, textend  ) 
  456. register int m  ; register CHARTYPE *text, *textend, *pat;
  457. {
  458. register unsigned hash, i; 
  459. register CHARTYPE shift;
  460. register int  m1, j; 
  461. register unsigned r_newline;
  462.  
  463. r_newline = '\n';
  464.  
  465.   m1 = m - 1;
  466.   text = text+m1;
  467.   while (text < textend) {
  468.     hash = *text;
  469.     hash = (hash << 3) + *(text-1);
  470.     shift = SHIFT_2[hash];
  471.     while(shift) {
  472.         text = text + shift;
  473.         hash = (*text << 3) + *(text-1);
  474.         shift = SHIFT_2[hash];
  475.     }
  476.     j = 0;
  477.     while(TR[pat[m1 - j]] == TR[*(text - j)]) { if(++j == m) break; }
  478.     if (j == m ) { 
  479.         if(text >= textend) return;
  480.                 num_of_matched++;
  481.                 if(FILENAMEONLY)  return;
  482.             if(COUNT) {
  483.               while (*text != r_newline) text++;
  484.               text--;
  485.         }
  486.         else {
  487.               if(FNAME) printf("%s: ", CurrentFileName);
  488.                           while(*(--text) != r_newline);
  489.                           while(*(++text) != r_newline) putchar(*text);
  490.               printf("\n");
  491.               text--;
  492.         }
  493.         }
  494.     text++;
  495.   }
  496. }
  497.  
  498. am_preprocess(Pattern)
  499. CHARTYPE *Pattern;
  500. {
  501. int i, j, m;
  502. unsigned hash;
  503.     m = strlen(Pattern);
  504.     for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
  505.     for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
  506.     for (i = m-1; i>=0; i--) {
  507.         MEMBER_1[Pattern[i]] = 1;
  508.         }
  509.     for (i = m-1; i > 0; i--) {
  510.            MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
  511.     }
  512. }
  513.  
  514.  
  515. verify(m, n, D, pat, text)
  516. register int m, n, D;
  517. CHARTYPE *pat, *text;
  518. {   
  519.     int A[MAXPATT], B[MAXPATT];
  520.     register int last = D;      
  521.     register int cost = 0;  
  522.     register int k, i, c;
  523.     register int m1 = m+1;
  524.     CHARTYPE *textend = text+n;
  525.     CHARTYPE *textbegin = text;
  526.  
  527.    for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
  528.    while (text < textend)
  529.    {
  530.        for (k = 1; k <= last; k++)
  531.        {
  532.            cost = B[k-1]+1; 
  533.            if (pat[k-1] != *text)
  534.            {   if (B[k]+1 < cost) cost = B[k]+1; 
  535.                if (A[k-1]+1 < cost) cost = A[k-1]+1; }
  536.            else cost = cost -1; 
  537.            A[k] = cost; 
  538.        }
  539.        if(pat[last] == *text++) { A[last+1] = B[last]; last++; }
  540.        if(A[last] < D) A[last+1] = A[last++]+1;
  541.        while (A[last] > D) last = last - 1;
  542.        if(last >= m) return(text - textbegin - 1);
  543.        if(*text == '\n') {
  544.             last = D;
  545.         for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  546.        }
  547.        for (k = 1; k <= last; k++)
  548.        {
  549.            cost = A[k-1]+1; 
  550.            if (pat[k-1] != *text)
  551.            {   if (A[k]+1 < cost) cost = A[k]+1; 
  552.                if (B[k-1]+1 < cost) cost = B[k-1]+1; }
  553.            else cost = cost -1; 
  554.            B[k] = cost;
  555.        }
  556.        if(pat[last] == *text++) { B[last+1] = A[last]; last++; }
  557.        if(B[last] < D) B[last+1] = B[last++]+1;
  558.        while (B[last] > D) last = last -1;
  559.        if(last >= m)   return(text - textbegin - 1);
  560.        if(*text == '\n') {
  561.             last = D;
  562.         for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  563.        }
  564.    }    
  565.    return(0);
  566. }
  567.  
  568. /* preprocessing for monkey()   */
  569.  
  570. m_preprocess(Pattern)
  571. CHARTYPE *Pattern;
  572. {
  573. int i, j, m;
  574. unsigned hash;
  575.     m = strlen(Pattern);
  576.     for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
  577.     for (i = m-1; i>=1; i--) {
  578.         hash = Pattern[i];
  579.         hash = hash << 3;
  580.         for (j = 0; j< MAXSYM; j++) {
  581.             if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
  582.         }
  583.         hash = hash + Pattern[i-1];
  584.         if(SHIFT_2[hash] >= m - 1) SHIFT_2[hash] = m-1-i;
  585.     }
  586.     shift_1 = m-1;
  587.     for (i= m-2; i>=0; i--) {
  588.         if(Pattern[i] == Pattern[m-1] )
  589.             { shift_1 = m-1 - i;  i = -1; }
  590.     }
  591.     if(shift_1 == 0) shift_1 = 1;
  592.     SHIFT_2[0] = 0;
  593. }
  594.  
  595. /* monkey4() the approximate monkey move */
  596.  
  597. char *MEMBER_D;
  598.  
  599. monkey4( pat, m, text, textend, D  ) 
  600. register int m, D ; register unsigned char *text, *pat, *textend;
  601. {
  602. register unsigned char *oldtext;
  603. register unsigned hash, i, hashmask, suffix_error; 
  604. register int m1=m-1-D, j, pos; 
  605.  
  606.   hashmask = Hashmask;
  607.   oldtext = text ;
  608.   while (text < textend) {
  609.      text = text + m1;
  610.      suffix_error = 0;
  611.      while(suffix_error <= D) {
  612.     hash = char_map[*text--];
  613.     hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  614.     while(MEMBER_D[hash]) {
  615.           hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  616.     }
  617.     suffix_error++;
  618.      }
  619.      if(text <= oldtext) {
  620.                    if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  621.                 text = oldtext+pos;
  622.                 if(text > textend) return;
  623.                 num_of_matched++;
  624.                 if(FILENAMEONLY) return;
  625.                 if(!(COUNT)) {
  626.                     if(FNAME) printf("%s:", CurrentFileName);
  627.                     while(*(--text) != '\n');
  628.                      while(*(++text) != '\n') putchar(*text);
  629.                         printf("\n");
  630.                     text++;
  631.                 }
  632.                 else {
  633.                     while(*text != '\n') text++;
  634.                     text++;
  635.                 }
  636.                }
  637.                else text = oldtext + m;
  638.      }
  639.      oldtext = text; 
  640.   }
  641. }
  642.  
  643. prep4(Pattern, m)
  644. char *Pattern; int m;
  645. {
  646. int i, j, k;
  647. unsigned hash;
  648.  
  649. for(i=0; i< MAXSYM; i++) char_map[i] = 0;
  650. char_map['a'] = char_map['A'] = 4;
  651. char_map['g'] = char_map['g'] = 1;
  652. char_map['t'] = char_map['t'] = 2;
  653. char_map['c'] = char_map['c'] = 3;
  654. char_map['n'] = char_map['n'] = 5;
  655.  
  656.     BSize = blog(4, m);
  657.     for (i = 1, Hashmask = 1 ; i<BSize*LOG_DNA; i++) Hashmask = (Hashmask << 1) + 1 ;
  658.     MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
  659. #ifdef DEBUG
  660.     printf("BSize = %d", BSize);
  661. #endif 
  662.     for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
  663.     for (j=0; j < BSize; j++) {
  664.             for(i=m-1; i >= j; i--) {
  665.                hash = 0;
  666.            for(k=0; k <= j; k++) 
  667.           hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
  668. #ifdef DEBUG
  669.            printf("< %d >, ", hash);
  670. #endif
  671.            MEMBER_D[hash] = 1;
  672.             }
  673.         }
  674. }
  675.  
  676. blog(base, m )
  677. int base, m;
  678. {
  679. int i, exp;
  680.     exp = base;
  681.         m = m + m/2;
  682.     for (i = 1; exp < m; i++) exp = exp * base;
  683.     return(i);
  684. }
  685.  
  686.