code

Fast Average Optimal Shift Or

The Fast Average Optimal Shift Or algorithm
faoso2.c
#include "include/log2.h"

void verify(unsigned char *y, int j, int n, unsigned char *x, int m, int q, int u, unsigned int D, unsigned int mm, int *count) {
   int s, c, mq, v, z, i, k;

   D = (D & mm)^mm;
   mq = m/q-1;
   while (D != 0) {
      s = LOG2(D);
      v = mq+u;
      c = -mq*q;
      z = s%v-mq;
      c -= (s/v + z*q);
      i = j+c;
      k = 0;
      if (i>=0 && i<=n-m) while(k<m && x[k]==y[i+k]) k++;
      if (k==m) (*count)++;
      D &= ~(1<<s);
   }
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D, h, mm;
   unsigned int masq;
   int i, j, u, count;
   int uq, uq1, mq;
   int q=2;

   u = 2;
   if (m>32-u+1) return search_large(x,m,y,n,q);
   if (m<=q) return -1;   
   
   /* Preprocessing */
   masq = 0;
   mq = m/q;
   h = mq;
   for (j = 0; j < q; ++j) {
      masq |= (1<<h);
      masq |= (1<<h);
      h += mq;
      ++h;
   }
   for (i = 0; i < SIGMA; ++i) 
      B[i] = ~0;
   h=mm=0;
   for (j = 0; j < q; ++j) {
      for (i = 0; i < mq; ++i) {
         B[x[i*q+j]] &= ~(1<<h);
         ++h;
      }
      mm |= (1<<(h-1)); ++h;
      mm |= (1<<(h-1)); ++h;
      --h;
   }

   /* Searching */
   count = 0;
   D = ~mm;
   j = 0;
   uq = u*q;
   uq1 = (u-1)*q;
   while (j < n) {
      D = (D<<1)|(B[y[j]]&~masq);
      D = (D<<1)|(B[y[j+q]]&~masq);
      if ((D & mm) != mm)
         verify(y, j+uq1, n, x, m, q, u, D, mm, &count);
      D &= ~mm;
      j += uq;
   }
   return count;
}

/*
 * Fast Average Optimal Shift Or 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
 */


void verify_large(unsigned char *y, int j, int n, unsigned char *x, int m, int q, int u, unsigned int D, unsigned int mm, int *count, int p_len) {
   int s, c, mq, v, z, i, k;

   D = (D & mm)^mm;
   mq = m/q-1;
   while (D != 0) {
      s = LOG2(D);
      v = mq+u;
      c = -mq*q;
      z = s%v-mq;
      c -= (s/v + z*q);
      i = j+c;
      k = 0;
      if (i>=0 && i<=n-m) while(k<p_len && x[k]==y[i+k]) k++;
      if (k==p_len) (*count)++;
      D &= ~(1<<s);
   }
}

int search_large(unsigned char *x, int m, unsigned char *y, int n, int q) {
   unsigned int B[SIGMA], D, h, mm;
   unsigned int masq;
   int i, j, u, count, p_len;
   int uq, uq1, mq;

   u = 2;
   p_len = m;
   m = 32-u+1;

   /* Preprocessing */
   masq = 0;
   mq = m/q;
   h = mq;
   for (j = 0; j < q; ++j) {
      masq |= (1<<h);
      masq |= (1<<h);
      h += mq;
      ++h;
   }
   for (i = 0; i < SIGMA; ++i) 
      B[i] = ~0;
   h=mm=0;
   for (j = 0; j < q; ++j) {
      for (i = 0; i < mq; ++i) {
         B[x[i*q+j]] &= ~(1<<h);
         ++h;
      }
      mm |= (1<<(h-1)); ++h;
      mm |= (1<<(h-1)); ++h;
      --h;
   }

   /* Searching */
   count = 0;
   D = ~mm;
   j = 0;
   uq = u*q;
   uq1 = (u-1)*q;
   while (j < n) {
      D = (D<<1)|(B[y[j]]&~masq);
      D = (D<<1)|(B[y[j+q]]&~masq);
      if ((D & mm) != mm)
         verify_large(y, j+uq1, n, x, m, q, u, D, mm, &count, p_len);
      D &= ~mm;
      j += uq;
   }
   return count;
}