code

Shift Vector Matching

The Shift Vector Matching algorithm
svm0.c
#define w ((int)sizeof(unsigned int)*8)

unsigned int asm_bsf(unsigned int x) {
    asm ("bsfl %0, %0" : "=r" (x) : "0" (x));
    return x;
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int count = 0;
   int s, j;
   unsigned int tmp, h, sv = 0, cv[SIGMA];
   if (m>31) return search_large(x,m,y,n);

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

   /* Searching */
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   s = m;
   while(s < n) {
      sv |= cv[y[s]];
      j = 1;
      while((sv&1) == 0) {
         if (j >= m) {OUTPUT(s); break;}
         sv |= (cv[y[s-j]] >> j);
         j++;
      }
      h = ~(sv >> 1);
      j = asm_bsf(h);
      sv >>= j+1;
      s += j+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 = 0;
   int s, j, p_len, first, k;
   unsigned int tmp, h, sv = 0, cv[SIGMA];
   p_len= m;
   m = 31;

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

   /* searching */
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   s = m;
   while(s < n){
      sv |= cv[y[s]];
      j = 1;
      while((sv&1) == 0) {
         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;
         }
         sv |= (cv[y[s-j]] >> j);
         j++;
      }
      h = ~(sv >> 1);
      j = asm_bsf(h);
      sv >>= j+1;
      s += j+1;
   }
   return(count);
}