code

Shift Or

The Shift Or algorithm
so.c

int preSo(unsigned char *x, int m, unsigned int S[]) { 
   unsigned int j, lim; 
   int i; 
   for (i = 0; i < SIGMA; ++i) 
      S[i] = ~0; 
   for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) { 
      S[x[i]] &= ~j; 
      lim |= j; 
   } 
   lim = ~(lim>>1); 
   return(lim); 
} 

int search(unsigned char *x, int m, unsigned char *y, int n) { 
   unsigned int lim, D; 
   unsigned int S[SIGMA]; 
   int j, count; 
   if (m > WORD) return search_large(x,m,y,n);

   /* Preprocessing */ 
   lim = preSo(x, m, S); 

   /* Searching */ 
   count = 0;
   for (D = ~0, j = 0; j < n; ++j) { 
      D = (D<<1) | S[y[j]]; 
      if (D < lim) 
        OUTPUT(j - m + 1); 
   } 
   return count;
} 

/*
 * Shift Or algorithm designed for large patterns
 * The present implementation searches for prefixes of the pattern of length 32.
 * When an occurrence is found the algorithm tests for the whole occurrence of the pattern
 */


int search_large(unsigned char *x, int m, unsigned char *y, int n) { 
   unsigned int lim, D,k,h,p_len; 
   unsigned int S[SIGMA]; 
   int j, count; 

   p_len = m;
   m=32;

   /* Preprocessing */ 
   lim = preSo(x, m, S); 

   /* Searching */ 
   count = 0;
   for (D = ~0, j = 0; j < n; ++j) { 
      D = (D<<1) | S[y[j]]; 
      if (D < lim) {
         k = 0;
         h = j-m+1;
         while(k<p_len && x[k]==y[h+k]) k++;
         if (k==p_len) OUTPUT(j - m + 1); 
      }
   } 
   return count;
}