code

Shift Vector Matching

The Shift Vector Matching algorithm
svm4.c

static const unsigned char lowest_bit_in_byte[] = {
   0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 };


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int count = 0;
   int s;
   int j;
   unsigned int tmp, h, sv = 0, cv[SIGMA];
   if (m>32) 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;
   }

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

   /* 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) {
         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++;
      }
      j = 0;
      h = ~(sv >>= 1);
      h &= -h;   
      if (!(h << 16)) {j += 16; h >>= 16;}
      if (!(h << 24)) {j += 8;  h >>= 8;}
      j += lowest_bit_in_byte[h & 0xFF];
      sv >>= j;
      s += j+1;
   }
   return(count);
}