code

Shift Vector Matching

The Shift Vector Matching algorithm
svm1.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int count, s, j;
   unsigned int tmp, h, sv, cv[SIGMA], ONE;

   if (m>32) return   search_large(x,m,y,n);

   /* Preprocessing */
   ONE = 1;
   tmp = (~0);
   tmp >>= (32-m);
   for (j = 0; j < SIGMA; j++) cv[j] = tmp;
   tmp = ~ONE;
   for (j = m-1; j >= 0; j--) {
      cv[x[j]] &= tmp;
      tmp <<= 1;
      tmp |= 1;
   }
   

   /* searching */
   sv = 0;   
   count = 0;
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   s = m;
   while(s < n){
      sv |= cv[y[s]];
      j = 1;
      while((sv & ONE) == 0) {
         sv |= (cv[y[s-j]] >> j);
         if (j >= m) {OUTPUT(s); break;}
         j++;
      }
      sv >>= 1; s += 1;
      while((sv & ONE)==1) {   
         sv >>= 1;
         s += 1;
      }
   }
   return count;
}

/*
 * Shift Vector Matching 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) {
   int count, s, j, first, k, p_len;
   unsigned int tmp, h, sv, cv[SIGMA], ONE;
   p_len = m;
   m = 32;   

   /* Preprocessing */
   ONE = 1;
   tmp = (~0);
   tmp >>= (32-m);
   for (j = 0; j < SIGMA; j++) cv[j] = tmp;
   tmp = ~ONE;
   for (j = m-1; j >= 0; j--) {
      cv[x[j]] &= tmp;
      tmp <<= 1;
      tmp |= 1;
   }
   

   /* Searching */
   sv = 0;   
   count = 0;
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   s = m;
   while(s < n){
      sv |= cv[y[s]];
      j = 1;
      while((sv & ONE) == 0) {
         sv |= (cv[y[s-j]] >> j);
         if (j >= m) {
            k = m; first = s-m+1;
            while (k<p_len && x[k]==y[first+k]) k++;
            if (k==p_len) OUTPUT(first); 
            break;
         }
         j++;
      }
      sv >>= 1; s += 1;
      while((sv & ONE)==1) {   
         sv >>= 1;
         s += 1;
      }
   }
   return count;
}