home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / BM.C next >
Encoding:
C/C++ Source or Header  |  1990-01-14  |  6.3 KB  |  240 lines
  1. /**********************************************************************
  2.  *
  3.  * Boyer-Moore algorithm separated from original egrep.c-file in
  4.  * fastgrep. Here we won't do alternation, as in original version.
  5.  *
  6.  * Fastgrep was written by
  7.  *   James A. Woods                Copyright (c) 1986
  8.  *   NASA Ames Research Center
  9.  *
  10.  *    J.Ruuth 07-Feb-1988
  11.  *
  12.  * Modified Boyer-Moore for guaranteed O(m+n) time performance.
  13.  *    P.Soini 07-Dec-1988
  14.  **********************************************************************/
  15.  
  16. #include "system.h"
  17. #include "dfa.h"
  18. #include "bm.h"
  19.  
  20. /* large should be larger than or equal to strlen + patlen */
  21. static unsigned large;
  22.  
  23. #if (MAXREGMUST > MAXCHAR)
  24. typedef    unsigned short    delta1_jmp_t;
  25. #else
  26. typedef    unsigned char    delta1_jmp_t;
  27. #endif
  28.  
  29. static uchar        c_index[NCHARS];
  30. static unsigned        n_index;
  31. static delta1_jmp_t*    delta1[MAXREGMUST-1] /*= {0}*/;
  32. static unsigned        delta0[NCHARS];  /* Boyer-Moore algorithm core */
  33.  
  34. /* Character conversion table, in case sensitive search, gives uppercase */
  35. /* version of given character, otherwise just the same character. */
  36. static uchar ccase[NCHARS];
  37.  
  38. #ifdef TEST
  39. extern int    debug;
  40. static long inner_cnt, outer_cnt, cmp_cnt;
  41. static int plen;
  42. void show_boyer_moore_report(void)
  43. {
  44.     if (debug > 1) {
  45.         int i,j;
  46.         printf("       ");
  47.         for (i = 0; i < NCHARS; i++)
  48.             if (c_index[i])
  49.                 printf(" %2c", i);
  50.         printf("\n");
  51.         for (i = 1; i < plen; i++) {
  52.             printf("%2d: ", i);
  53.             printf(" %2d", (delta1-1)[i][0]);
  54.             for (j = 0; j < NCHARS; j++)
  55.                 if (c_index[j] != 0)
  56.                     printf(" %2d", (delta1-1)[i][c_index[j]]);
  57.             printf("\n");
  58.         }
  59.     }
  60.     printf( "Boyer-Moore inner loop iterated "
  61.         "%ld, outer %ld, comp.loop %ld times\n",
  62.         inner_cnt, outer_cnt, cmp_cnt);
  63. }
  64. #endif
  65.  
  66. /************************************************************************
  67.  *    init_c_index
  68.  *
  69.  * Allocates index for every character. Every character in 'pat' will
  70.  * get an index entry of its own. All characters that are not in
  71.  * pat[0] .. pat[patlen-3] will be in one index: 0
  72.  */
  73. static void init_c_index(uchar* pat, int patlen, int iflag)
  74. {
  75.     register int    i, j;
  76.     
  77.     for (i = NCHARS; i > 0; )
  78.         c_index[--i] = 0;
  79.     for (n_index = 1, i = patlen - 2; i > 0; ) {
  80.         if (!c_index[j = pat[--i]]) {
  81.             c_index[j] = n_index++;
  82.             if (iflag)
  83.                 c_index[CHCASE(j)] = c_index[j];
  84.         }
  85.     }
  86. }
  87.  
  88. /**********************************************************************
  89.  *
  90.  *    make_ccase
  91.  */
  92. static void    make_ccase(int iflag)
  93. {
  94.     REG1 int    i = NCHARS;
  95.     
  96.     while (i--) {
  97.         if (iflag && islower(i))
  98.             ccase[i] = toupper(i);
  99.         else
  100.             ccase[i] = i;
  101.     }
  102. }
  103.  
  104. /************************************************************************
  105.  *    gosper
  106.  *
  107.  * slides pattern over itself and tries to find rightmost and longest
  108.  * reoccurence of its right side. Then it calculates jump value
  109.  * for that character position and the character that caused the first
  110.  * mismatch. ie. this routine calculates jump values for all
  111.  * entries of delta1 and delta0.
  112.  */
  113. void    gosper(char* pat, REG5 int patlen, int iflag)
  114. {
  115.     REG3 uchar*    patend = (uchar*)pat + patlen - 1;
  116.     REG1 int    i;
  117.     REG2 int    j;
  118.     REG4 int    k;
  119.         
  120. #ifdef    TEST
  121.     inner_cnt = outer_cnt = cmp_cnt = 0L;
  122.     plen = patlen;
  123. #endif
  124.     make_ccase(iflag);
  125.     large =  maxbuf + MAXREGMUST;
  126.     for (j = NCHARS; j; )
  127.         delta0[--j] = patlen;
  128.     /* first we initialize the space-saving c_index array */
  129.     init_c_index(pat, patlen, iflag);
  130.     /* next we allocate jump array */
  131.     d_free(&delta1[0]);
  132.     if (patlen > 1
  133.     &&  (delta1[0] = malloc(sizeof(delta1_jmp_t) * n_index *
  134.                 (unsigned)(patlen - 1))) == NULL)
  135.         error("Out of memory", 3);
  136.     for (i = 1, j = patlen - 1; i < j; ++i)
  137.         delta1[i] = (delta1-1)[i] + n_index;
  138.     for (i = patlen - 1; i > 0; --i)
  139.         for (j = n_index; j > 0; )
  140.             (delta1-1)[i][--j] = patlen;
  141.     
  142.     /* from now on 'j' represents the slide value and
  143.     ** 'i' represents the offset calculated backward from the
  144.     ** 'patend'
  145.     */
  146.     for (j = patlen - 1; j > 0; --j) {
  147.         if (patend[0] != (k = patend[-j])) {    /* mismatch at 'patend' */
  148.             delta0[k] = j;
  149.             if (iflag)
  150.                 delta0[CHCASE(k)] = j;
  151.             continue; /* to next value of 'j' */
  152.         }
  153.         for (i = 1; ; ++i) {
  154.             if (i + j >= patlen) {    /* was a match */
  155.                 for (; i < patlen; ++i)
  156.                     for (k = n_index; k > 0; )
  157.                         (delta1-1)[i][--k] = j;
  158.                 break;
  159.             }
  160.             if (patend[-i] != (k = patend[-i - j])) { /* mismatch */
  161.                 (delta1-1)[i][c_index[k]] = j;
  162.                 break;
  163.             }
  164.         }
  165.     }
  166.     /* the 'large' trick to fall out of search loop when the
  167.     ** rightmost char matches. This trick saves one comparison
  168.     ** from the inner loop of the Boyer-Moore search.
  169.     */
  170.     delta0[k = *patend] = large;    
  171.     if (iflag)            
  172.         delta0[CHCASE(k)] = large;
  173. }
  174.  
  175. /**********************************************************************
  176.  *
  177.  *    boyer_moore
  178.  *
  179.  * "reach out and boyer-moore search someone"
  180.  *  soon-to-be-popular bumper sticker
  181.  */
  182. char* boyer_moore(char* str, char* strend, char* pat, int patlen)
  183. {
  184.     REG1 uchar*    k;
  185.     REG2 uchar*    p;
  186.     REG3 uchar*    s;
  187.  
  188.     /* The variables below exist merely for optimization purposes
  189.     ** to avoid calculations inside the outermost for loop.
  190.     ** They don't really affect the overall performance significantly,
  191.     ** though.
  192.     */
  193.     uchar*    str_plus_large = (uchar*)str + large;
  194.     uchar*    patend = (uchar*)pat + patlen - 1;
  195.     
  196.     if (patlen == 1 && (!isalpha(*pat) || ccase['a'] != ccase['A']))
  197.         return memchr(str, *pat, strend-str+1);
  198.     for (k = (uchar*)str + patlen - 1; ; ) {
  199.         p = (uchar*)strend;
  200.         /* for a large class of patterns, upwards of 80% of 
  201.          * match time is spent on the next loop.  We beat 
  202.          * existing microcode (vax 'matchc') this way.
  203.          * In VAX with 'gcc' compiler the loop is only 4 instructions
  204.          * long, in 80([123]?86|1?88) with MSC 5.1 compiler it is 6
  205.          * instructions.
  206.          */
  207. #ifdef    TEST
  208.         if (debug)
  209.             for (; k <= p; k += delta0[*k])
  210.                 ++inner_cnt;
  211.         else
  212. #endif
  213.         for (; k <= p; k += delta0[*k])
  214.             ;
  215.         if (k < str_plus_large)
  216.             return NULL;
  217.         s = k -= large;
  218.         p = patend;
  219. #ifdef    TEST
  220.         if (debug) {
  221.             ++outer_cnt;
  222.             do {
  223.                 ++cmp_cnt;
  224.                 --k;
  225.                 --p;
  226.                 if (p < (uchar*)pat)
  227.                     return s - patlen + 1;
  228.             } while (ccase[*k] == *p);
  229.         } else
  230. #endif
  231.         do {
  232.             --k;
  233.             --p;
  234.             if (p < (uchar*)pat)
  235.                 return s - patlen + 1;
  236.         } while (ccase[*k] == *p);
  237.         k = s + (delta1-1)[patend - p][c_index[*k]];
  238.     }
  239. }
  240.