code

Simplified BNDM with loop unrolling

The Simplified BNDM with loop unrolling algorithm
sbndm2.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D;
   int i, j, pos, mMinus1, m2, count, shift;
   if (m<2) return -1;
   if (m>32) return search_large(x,m,y,n);

   /* Preprocessing */
   mMinus1 = m - 1;
   m2 = m - 2;
   for (i=0; i<SIGMA; i++) B[i]=0;
   for (i = 1; i <= m; ++i) B[x[m-i]] |= (1<<(i-1));

   D = B[x[m-2]]; j=1; shift=0;
   if (D & (1<<(m-1))) shift = m-j;
   for (i=m-3; i>=0; i--) {
      D = (D<<1) & B[x[i]];
      j++;
      if (D & (1<<(m-1))) shift = m-j;
   }

   /* Searching */
   count = 0;
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   j = m;
   while (j < n) {
      D = (B[y[j]]<<1) & B[y[j-1]];
      if (D != 0) {
         pos = j;
         while (D=(D<<1) & B[y[j-2]])
            --j;
         j += m2;
         if (j == pos) {
            OUTPUT(j);
            j+=shift;
         }
      }
      else j+=mMinus1;
   }
   return count;
}

/*
 * Simplified Backward Nondeterministic DAWG Matching with loop unrolling 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 B[SIGMA], D;
   int i, j, pos, mMinus1, m2, count, p_len, shift;

   /* Preprocessing */
   p_len = m;
   m = 32;
   int diff = p_len-m;
   count = 0;
   mMinus1 = m - 1;
   m2 = m - 2;
   for (i=0; i<SIGMA; i++) B[i]=0;
   for (i = 1; i <= m; ++i)
      B[x[m-i]] |= (1<<(i-1));
   D = B[x[m-1]]; j=1; shift=1;
   for (i=m-2; i>0; i--, j++) {
      if (D & (1<<(m-1))) shift = j;
      D = (D<<1) & B[x[i]];
   }

   /* Searching */
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   j = m;
   while (j+diff < n) {
      D = (B[y[j]]<<1) & B[y[j-1]];
      if (D != 0) {
         pos = j;
         while (D=(D<<1) & B[y[j-2]])
            --j;
         j += m2;
         if (j == pos) {
            for (i=m+1; i<p_len && x[i]==y[j-m+1+i]; i++);
            if (i==p_len) OUTPUT(j-m+1);
            j+=shift;
         }
      }
      else j+=mMinus1;
   }
   return count;
}