home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / uf.fwdg.md2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  2.9 KB  |  145 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=uf, match=fwd (using fwdr), guard=guardr (using guard), shift=md2
  4. */
  5. #include    "freq.h"
  6. /*
  7.  * The authors of this software are Andrew Hume and Daniel Sunday.
  8.  * 
  9.  * Copyright (c) 1991 by AT&T and Daniel Sunday.
  10.  * 
  11.  * Permission to use, copy, modify, and distribute this software for any
  12.  * purpose without fee is hereby granted, provided that this entire notice
  13.  * is included in all copies of any software which is or includes a copy
  14.  * or modification of this software and in all copies of the supporting
  15.  * documentation for such software.
  16.  * 
  17.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
  19.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  20.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  21.  */
  22.  
  23. #ifndef    CHARTYPE
  24. #define    CHARTYPE    unsigned char
  25. #endif
  26. #define    MAXPAT    256
  27.  
  28. #include    "stats.h"
  29.  
  30. #ifndef    TABTYPE
  31. #define    TABTYPE    long
  32. #endif
  33. typedef TABTYPE Tab;
  34.  
  35. static struct
  36. {
  37.     int patlen;
  38.     CHARTYPE pat[MAXPAT];
  39.     Tab delta[256];
  40.     int rarec, rareoff;
  41.     int md2;
  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.     int rrr, rr;
  53.     register CHARTYPE *pmd2;
  54.  
  55.     pat.patlen = m;
  56.     if(m > MAXPAT)
  57.         abort();
  58.     memcpy(pat.pat, base, m);
  59.     skipc = 0;
  60.     stats.len = m;
  61.     d = pat.delta;
  62.     for(j = 0; j < 256; j++)
  63.         d[j] = pat.patlen;
  64.     for(p = pat.pat, pe = p+m-1; p < pe; p++)
  65.         d[*p] = pe-p;
  66.     d[*p] = 0;
  67.     skipc = (CHARTYPE *)p;
  68.     rrr = 0;
  69.     for(rr = 1; rr < m; rr++){
  70.         if(freq[pat.pat[rr]] < freq[pat.pat[rrr]])
  71.             rrr = rr;
  72.     }
  73.     pat.rarec = pat.pat[rrr];
  74.     pat.rareoff = rrr - (m-1);
  75.     for(pmd2 = skipc-1; pmd2 >= pat.pat; pmd2--)
  76.         if (*pmd2 == *skipc) break;
  77.     pat.md2 = skipc - pmd2;    /* *pmd2 is first leftward reoccurance of *pe */
  78. #ifdef    STATS
  79.     stats.extra += pat.md2;
  80. #endif
  81. }
  82.  
  83. exec(base, n)
  84.     CHARTYPE *base;
  85. {
  86.     int nmatch = 0;
  87.     register CHARTYPE *e, *s;
  88.     register Tab *d0 = pat.delta;
  89.     register k;
  90.     register ro, rc;
  91.     register CHARTYPE *p, *q;
  92.     register CHARTYPE *ep;
  93.     register n1 = pat.patlen-1;
  94.     register md2 = pat.md2;
  95.  
  96.     s = base+pat.patlen-1;
  97.     e = base+n;
  98.     memset(e, pat.pat[pat.patlen-1], pat.patlen);
  99.     ro = pat.rareoff;
  100.     rc = pat.rarec;
  101.     ep = pat.pat + pat.patlen-1;
  102.     while(s < e){
  103. #ifdef    STATS
  104.         k = d0[*s];
  105.         stats.jump++;
  106.         while(k){
  107.             stats.jump++; stats.step[k]++;
  108.             k = d0[*(s += k)];
  109.             stats.jump++; stats.step[k]++;
  110.             k = d0[*(s += k)];
  111.             stats.jump++; stats.step[k]++;
  112.             k = d0[*(s += k)];
  113.         }
  114. #else
  115.         k = d0[*s];
  116.         while(k){
  117.             k = d0[*(s += k)];
  118.             k = d0[*(s += k)];
  119.             k = d0[*(s += k)];
  120.         }
  121. #endif
  122.         if(s >= e)
  123.             break;
  124. #ifdef    STATS
  125.         stats.slow++;
  126. #endif
  127.         if(s[ro] != rc)
  128.             goto mismatch;
  129.         for(p = pat.pat, q = s-n1; p < ep; ){
  130. #ifdef    STATS
  131.             stats.cmp++;
  132. #endif
  133.             if(*q++ != *p++)
  134.                 goto mismatch;
  135.         }
  136.         nmatch++;
  137.     mismatch:
  138. #ifdef    STATS
  139.         stats.step[md2]++; stats.jump++;
  140. #endif
  141.         s += md2;
  142.     }
  143.     return(nmatch);
  144. }
  145.