code

Average Optimal Shift Or

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

void verify(unsigned char *y, int j, int n, unsigned char *x, int m, int q, unsigned int D, unsigned int mm, int *count) {
    unsigned int s;
    int c, k, i;
    D = (D & mm)^mm;
    while (D != 0) {
        s = LOG2(D); 
        c = -(m/q-1)*q-s/(m/q);
        k = 0; i=j+c;
        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, tmp, not_mm;
    int i, j, count;
    int q=2;

    if (m<=q) return -1;   
    if (m>32) return search_large(x,m,y,n,q);

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

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

/*
 * AOSO 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, unsigned int D, unsigned int mm, int *count, int p_len) {
    unsigned int s, tmp;
    int c, k, i;
    D = (D & mm)^mm;
    while (D != 0) {
        s = LOG2(D);
        c = -(m/q-1)*q-s/(m/q);
        k = 0; i=j+c;
        if (i>=0 && i<=n-p_len) 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, tmp;
    int i, j, count, p_len;

    p_len = m;
    m = 32;

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

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