code

Shift Or with q-grams

The Shift Or with q-grams algorithm
ufndmq6.c
#define GRAM6(i) ( (B[y[i-5]]<<5) | (B[y[i-4]]<<4) | (B[y[i-3]]<<3) | (B[y[i-2]]<<2) | (B[y[i-1]]<<1) | B[y[i]] )

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int D, F, mm, mask, B[SIGMA], S;
   int i, j, k, mq, q;
   int count = 0;
   q = 6;
   if (m<q) return -1;
   if (m+q > WORD) return search_large(x,m,y,n);

   /* Preprocessing */
   S = ~((unsigned char)31 << m);
   for (j = 0; j < SIGMA; ++j) B[j] = S;
   for (j = 0; j < m; ++j)   B[x[j]] &= ~((unsigned char)1<<j);
   for (i=0; i<m; i++) y[n+i]=y[n+m+i]=x[i];
   mm = (unsigned char)1 << (m+q-2);
   mask = ((unsigned char)1 << (m-1)) - 1;
   mq = m+q-1;

   /* Searching */
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   i = 0;
   D = ~0;
   while (1) {
      while ( (D|31) == ~0 ) { 
         i += m;
         D = (D<<m) | GRAM6(i);
      }
      if (F=~(D|mask)) {
         for (k=i-mq+1; F; F<<=1, k++)
            if (F >= mm) {
               for (j=0; j<m; j++)
                  if (y[k+j]!=x[j]) goto mismatch;
               if (k+m > n)  return(count);
               OUTPUT(k);
          
               mismatch:
               F -= mm;
            }
      }
      i += q;
      D = (D<<q) | GRAM6(i);
   }
   abort();
}

/*
 * Shift Or with q-grams 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 D, F, mm, mask, B[SIGMA], S;
   int i, j, k, mq, q, p_len;
   int count = 0;
   q = 6;

   for (i=0; i<m; i++) y[n+i]=y[n+m+i]=x[i];
   p_len = m;
   m = 32-q;

   /* Preprocessing */
   S = ~((unsigned char)31 << m);
   for (j = 0; j < SIGMA; ++j) B[j] = S;
   for (j = 0; j < m; ++j)   B[x[j]] &= ~((unsigned char)1<<j);
   mm = (unsigned char)1 << (m+q-2);
   mask = ((unsigned char)1 << (m-1)) - 1;
   mq = m+q-1;

   /* Searching */
   if ( !memcmp(x,y,p_len) ) OUTPUT(0);
   i = 0;
   D = ~0;
   while (1) {
      while ( (D|31) == ~0 ) { 
         i += m;
         D = (D<<m) | GRAM6(i);
      }
      if (F=~(D|mask)) {
         for (k=i-mq+1; F; F<<=1, k++)
            if (F >= mm) {
               for (j=0; j<p_len; j++)
                  if (y[k+j]!=x[j]) goto mismatch;
               if (k+m > n)  return(count);
               OUTPUT(k);
          
               mismatch:
               F -= mm;
            }
      }
      i += q;
      D = (D<<q) | GRAM6(i);
   }
   abort();
}