code

BNDM with Extended Shift

The BNDM with Extended Shift algorithm
bxs.c
#define Q 1 

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D, set;
   int i, j, first, k, mm, sh, m1, count;
   if (m<Q) return -1;
//int larger = m>WORD? 1:0;
   //if (larger) m = WORD;
int w = WORD, mq1 = m-Q+1, nq1 = n-Q+1;
if (w > m) w = m;
unsigned int mask = 1<<(w-1);

   /* Preprocessing */
   count = 0;
   set = 1;
for (i=0; i<SIGMA; i++) B[i]=0;
   for (i = m-1; i >=0; i--) {
B[x[i]] |= set;
set<<=1;
if (set==0) set=1;
}

   /* Searching */
for (i=mq1-1; i<nq1; i+=mq1) {
D = B[y[i]];
if ( D ) {
j = i; 
first = i-mq1;
   do {
   j--;
   if (D >= mask) {
   if (j-first) i=j;
   else {
   for (k=m; y[first+k]==x[k-1] && (k); k--);
   if ( k==0 ) count++;
   }
   D = ((D<<1)|1) & B[y[j]];
   }
   else D = (D<<1) & B[y[j]];
   } while (D && j>first);
   }
   }
   return count;
}