home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / fast.rev.d12.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  3.3 KB  |  164 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=fast, match=rev (using revr), shift=d12
  4. */
  5. /*
  6.  * The authors of this software are Andrew Hume and Daniel Sunday.
  7.  * 
  8.  * Copyright (c) 1991 by AT&T and Daniel Sunday.
  9.  * 
  10.  * Permission to use, copy, modify, and distribute this software for any
  11.  * purpose without fee is hereby granted, provided that this entire notice
  12.  * is included in all copies of any software which is or includes a copy
  13.  * or modification of this software and in all copies of the supporting
  14.  * documentation for such software.
  15.  * 
  16.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  17.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
  18.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  19.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  20.  */
  21.  
  22. #ifndef    CHARTYPE
  23. #define    CHARTYPE    unsigned char
  24. #endif
  25. #define    MAXPAT    256
  26.  
  27. #include    "stats.h"
  28.  
  29. #ifndef    TABTYPE
  30. #define    TABTYPE    long
  31. #endif
  32. typedef TABTYPE Tab;
  33.  
  34. static struct
  35. {
  36.     int patlen;
  37.     CHARTYPE pat[MAXPAT];
  38.     Tab delta[256];
  39.     int lastchar;
  40.     Tab delta1[256];
  41.     Tab delta2[257];
  42. } pat;
  43.  
  44. prep(base, m)
  45.     CHARTYPE *base;
  46.     register m;
  47. {
  48.     CHARTYPE *skipc;
  49.     register CHARTYPE *pe, *p;
  50.     register int j;
  51.     register Tab *d;
  52.     register Tab *d2;
  53.     register q1, tp, t, qp, jp, kp;
  54.     Tab f[256], f1[256];
  55.  
  56.     pat.patlen = m;
  57.     if(m > MAXPAT)
  58.         abort();
  59.     memcpy(pat.pat, base, m);
  60.     skipc = 0;
  61.     stats.len = m;
  62.     d = pat.delta;
  63.     for(j = 0; j < 256; j++)
  64.         d[j] = pat.patlen;
  65.     for(p = pat.pat, pe = p+m-1; p < pe; p++)
  66.         d[*p] = pe-p;
  67.     pat.lastchar = *p;
  68.     skipc = (CHARTYPE *)p;
  69.     d2 = pat.delta1;
  70.     for(j = 0; j < 256; j++)
  71.         d2[j] = m;
  72.     for(j = 0; j < m; j++)
  73.         d2[base[j]] = m-1-j;
  74.     d2 = pat.delta2;
  75.     for(j = 1; j < m; j++)
  76.         d2[j] = 2*m-j;
  77.     for(j = m, t = m+1; j > 0; j--, t--){
  78.         f[j] = t;
  79.         while((t <= m) && (base[t-1] != base[j-1])){
  80.             if((m-j) < d2[t])
  81.                 d2[t] = m-j;
  82.             t = f[t];
  83.         }
  84.     }
  85.     q1 = t;
  86.     t = m+1-q1;
  87.     qp = 1;
  88.     for(jp = 1, kp = 0; kp < t; jp++, kp++){
  89.         f1[jp] = kp;
  90.         while((kp >= 1) && (base[jp-1] != base[kp-1]))
  91.             kp = f1[kp];
  92.     }
  93.     while(q1 < m){
  94.         for(j = qp; j <= q1; j++)
  95.             if(m+q1-j < d2[j])
  96.                 d2[j] = m+q1-j;
  97.         qp = q1+1;
  98.         q1 += t-f1[t];
  99.         t = f1[t];
  100.     }
  101. /*for(j=1; j<=m; j++)printf("[%d]=%d ", j, d2[j]); printf("\n");/**/
  102.     d2[0] = m+1;        /* the case where the match succeeded */
  103. }
  104.  
  105. exec(base, n)
  106.     CHARTYPE *base;
  107. {
  108.     int nmatch = 0;
  109.     register CHARTYPE *e, *s;
  110.     register Tab *d0 = pat.delta;
  111.     int lastdelta;
  112.     register k;
  113.     register CHARTYPE *p, *q;
  114.     register CHARTYPE *prev = pat.pat+pat.patlen-1;
  115.     register Tab *d1 = pat.delta1;
  116.     register Tab *d2 = pat.delta2+1;
  117.     register k1, k2;
  118.  
  119.     lastdelta = n+pat.patlen;
  120.     d0[pat.lastchar] = lastdelta;    /* guaranteed to break s < e loop */
  121.     s = base+pat.patlen-1;
  122.     e = base+n;
  123.     while(s < e){
  124. #ifdef    STATS
  125.         for(;;){
  126.             stats.jump++;
  127.             if((s += (k = d0[*s])) >= e) break;
  128.             stats.step[k]++;
  129.         }
  130.         if(s < e+pat.patlen)
  131.             stats.step[k]++;
  132. #else
  133.         while((s += d0[*s]) < e)
  134.             ;
  135. #endif
  136.         if(s < e+pat.patlen)    /* no match */
  137.             break;
  138.         s -= lastdelta;
  139. #ifdef    STATS
  140.         stats.slow++;
  141. #endif
  142. #define    RH    s
  143.         for(p = prev, q = RH; p > pat.pat; ){
  144. #ifdef    STATS
  145.             stats.cmp++;
  146. #endif
  147.             if(*--q != *--p)
  148.                 goto mismatch;
  149.         }
  150.         nmatch++;
  151.     mismatch:
  152.         k2 = d2[p-pat.pat];
  153.         k1 = d1[*q];
  154.         if(k2 < k1)
  155.             k2 = k1;
  156.         k2 = q+k2-RH;
  157. #ifdef    STATS
  158.         stats.step[k2]++; stats.jump++;
  159. #endif
  160.         s += k2;
  161.     }
  162.     return(nmatch);
  163. }
  164.