code

Bit Parallel Length Invariant Matcher

The Bit Parallel Length Invariant Matcher algorithm
blim.c
#define MAXWSIZE (XSIZE + WORD)

int search(unsigned char* x, int m, unsigned char* y, int n)
{
   int i,j,k,count;
   unsigned int   wsize = WORD - 1 + m;
   unsigned long* M = (unsigned long*)malloc(sizeof(unsigned long)*SIGMA * MAXWSIZE);
   unsigned long  tmp, F;
   unsigned int   ScanOrder[XSIZE];
   unsigned int   MScanOrder[XSIZE];
   unsigned int*  so  = ScanOrder;
   unsigned int*  mso = MScanOrder;
   unsigned int   shift[SIGMA];

   /* Preprocessing */
   memset(M,0xff,sizeof(unsigned long)*SIGMA*wsize);
    for (i=0;i<WORD;i++){
      tmp = 1 << i;
      for (j=0;j<m;j++){
         for (k=0;k<SIGMA;k++) M[((i+j)*SIGMA) + k] &= ~tmp;
         M[ x[j] + ((i+j)*SIGMA) ]|= tmp;
      }
   }
   
   for (i=0;i<SIGMA;i++) shift[i] = wsize + 1;
   for (i=0;i<m;i++) shift[x[i]] = wsize - i;
   
   for (i=m-1;i>=0;i--){
      k=i;
      while (k<wsize){
         *so=k;
         *mso = SIGMA*k;
         so++;
         mso++;
         k+=m;
      }
   }
   
   /* Searching */
   count = 0;
   i = 0;
   F = M[MScanOrder[0]+y[i+ScanOrder[0]]] & M[MScanOrder[1]+y[i+ScanOrder[1]]];
   while(i<n) {
      for (j=2;F && j<wsize;j++){ 
         F &= M[MScanOrder[j]+y[i+ScanOrder[j]]]; 
      }
      if (F) {
         for (j=0;j<WORD;j++) 
            if (F & (1<<j)) 
               if (i+j<=n-m) OUTPUT(i+j);
      }
      i+=shift[y[i+wsize]];
      F = M[MScanOrder[0]+y[i+ScanOrder[0]]] & M[MScanOrder[1]+y[i+ScanOrder[1]]];
   }
   return count;
}