home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / uf.rev.gd2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  3.4 KB  |  167 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=uf, match=rev (using revr), shift=gd2
  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.     Tab dg[MAXPAT][128];        /* bad size but the 386 is small (128 is charset) */
  40. } pat;
  41.  
  42. prep(base, m)
  43.     CHARTYPE *base;
  44.     register m;
  45. {
  46.     CHARTYPE *skipc;
  47.     register CHARTYPE *pe, *p;
  48.     register int j;
  49.     register Tab *d;
  50.     register j0, k, q, i, jj;
  51.     int endof[MAXPAT], rmin[MAXPAT];
  52.  
  53.     pat.patlen = m;
  54.     if(m > MAXPAT)
  55.         abort();
  56.     memcpy(pat.pat, base, m);
  57.     skipc = 0;
  58.     stats.len = m;
  59.     d = pat.delta;
  60.     for(j = 0; j < 256; j++)
  61.         d[j] = pat.patlen;
  62.     for(p = pat.pat, pe = p+m-1; p < pe; p++)
  63.         d[*p] = pe-p;
  64.     d[*p] = 0;
  65.     skipc = (CHARTYPE *)p;
  66.     /*
  67.         endof[k] is the maximal integer such that k is not a period
  68.         rmin[jj] is the minimal period of p[0,m-1] > jj
  69.         rmin[0] is the period of pat
  70.     */
  71.  
  72.     for(i=0; i<m; i++)
  73.         rmin[i] = m;
  74.     for(k = 1, i = k, jj = 0; k < m; ){
  75.         while((pat.pat[i] == pat.pat[i-k]) && (i < m))
  76.             i++;
  77.         endof[k] = i;
  78.         q = k+1;
  79.         if(i == m){
  80.             for(j0 = jj; j0 < k; j0++)
  81.                 rmin[j0] = k;  
  82.             jj = k;
  83.         }
  84.         while(endof[q-k]+k < i){ 
  85.                    endof[q] = endof[q-k]+k;
  86.                    q = q+1;
  87.         }
  88.         k = q;
  89.         if(k == i+1)
  90.             i = k;
  91.     }
  92.     /*for (i=0; i<m; i++) printf("%d\t%d\n",endof[i], rmin[i]);/**/
  93.  
  94.     /* compute pat.dg[jj,a] */
  95.     for(jj = 0; jj < m; jj++){ 
  96.         for(i = 0; i < 128; i++)
  97.             pat.dg[jj][i] = m-1-jj+rmin[jj];
  98.     }
  99.     for(k = m-2; k >= 0; k--){
  100.         for(i = k, jj = m-1; pat.pat[i] == pat.pat[jj]; i--, jj--)
  101.             ;
  102.         if((i >= 0) && (pat.dg[jj][pat.pat[i]]>=m))
  103.             pat.dg[jj][pat.pat[i]] = m-1-i;
  104.     }
  105. }
  106.  
  107. exec(base, n)
  108.     CHARTYPE *base;
  109. {
  110.     int nmatch = 0;
  111.     register CHARTYPE *e, *s;
  112.     register Tab *d0 = pat.delta;
  113.     register k;
  114.     register CHARTYPE *p, *q;
  115.     register CHARTYPE *prev = pat.pat+pat.patlen-1;
  116.     register kg;
  117.  
  118.     s = base+pat.patlen-1;
  119.     e = base+n;
  120.     memset(e, pat.pat[pat.patlen-1], pat.patlen);
  121.     while(s < e){
  122. #ifdef    STATS
  123.         k = d0[*s];
  124.         stats.jump++;
  125.         while(k){
  126.             stats.jump++; stats.step[k]++;
  127.             k = d0[*(s += k)];
  128.             stats.jump++; stats.step[k]++;
  129.             k = d0[*(s += k)];
  130.             stats.jump++; stats.step[k]++;
  131.             k = d0[*(s += k)];
  132.         }
  133. #else
  134.         k = d0[*s];
  135.         while(k){
  136.             k = d0[*(s += k)];
  137.             k = d0[*(s += k)];
  138.             k = d0[*(s += k)];
  139.         }
  140. #endif
  141.         if(s >= e)
  142.             break;
  143. #ifdef    STATS
  144.         stats.slow++;
  145. #endif
  146. #define    RH    s
  147.         for(p = prev, q = RH; p > pat.pat; ){
  148. #ifdef    STATS
  149.             stats.cmp++;
  150. #endif
  151.             if(*--q != *--p)
  152.                 goto mismatch;
  153.         }
  154.         nmatch++;
  155.     mismatch:
  156.         if(p < pat.pat)
  157.             kg = pat.patlen+1;
  158.         else
  159.             kg = pat.dg[p-pat.pat][*q];
  160. #ifdef    STATS
  161.         stats.step[q+kg-s]++; stats.extra++;
  162. #endif
  163.         s = q+kg;
  164.     }
  165.     return(nmatch);
  166. }
  167.