Blocked Booyer-Moore

unsigned int* p;
unsigned int m;

unsigned int* delta_2;

/************* Preprocessing ************/
void bs_init(char* _p, unsigned int _m)
{
    if(p != NULL) delete [] p;
    ++p = new unsigned int[2 + (_m / 4)];
    memcpy(p, _p, _m / 4);
    m = _m;

    if(delta_2 != NULL) delete [] delta_2;
    delta_2 = new unsigned int[m];

    unsigned int pcpy[m / 32];
    memcpy(pcpy, p, (m / 8));

    int i = m;
    while(--i >= 0)
    {
        toggle_bit(i, pcpy);

        int j = m - 1;
        while(--j >= 0)
        {
            int k = m - i;

            int s = j - k + 1;
            while((--k >= 0) && (read_bit(s + k, p) == read_bit(i + k, pcpy)))
            {
                if((k == 0) || ((s + k) == 0))
                    goto end_search;
            }

        }

        end_search:

        delta_2[i] = m - j - 1;
        toggle_bit(i, pcpy);
    }
}

/************* Searching ************/
inline unsigned int ceil_div(unsigned int a, unsigned int b)
{
    return (a + b - 1) / b;
}

inline unsigned int bs_last(unsigned int sh)
{
    return ceil_div(sh + m, 32);
}

inline unsigned int bs_mask(unsigned int sh, unsigned int j)
{
    int a = sh - ((j - 1) * 32);
    int b = a + m;

    a = std::max(a, 0);
    b = std::min(b, 32);

    return ((1ull << b) - (1ull << a));
}

inline unsigned int bs_pat(unsigned int sh, unsigned int j)
{
    return (p[j - 1] << sh) | ((unsigned long long)p[j - 2] >> (32 - sh));
}

inline unsigned int bs_nrz(unsigned int indic)
{
    return __builtin_clz(indic);
}

inline unsigned int bit_search(unsigned int* t, unsigned int a, unsigned int b)
{
    unsigned int sh = a % 32;
    unsigned int i = bs_last(a);
    unsigned int lastbit = a + m;
    while(i <= ceil_div(b, 32))
    {
        unsigned int j = bs_last(sh);
        unsigned int sl = 1 + ((m + sh - 1) % 32);
        unsigned int indic;
        while((j > 0) && ((indic = (t[i-1] ^ bs_pat(sh, j)) & bs_mask(sh, j)) == 0))
        {
            i--;
            j--;
        }

        if(j == 0) return 32 * i + sh + m;
        else
        {
            unsigned int matchlen = sl + bs_nrz(indic) + ((bs_last(sh) - j - 1) * 32);
            unsigned int delta2 = delta_2[m - matchlen - 1];
            lastbit += delta2;
            i = ceil_div(lastbit, 32);
            sh = (lastbit - m) % 32;
        }
    }

    return 0;
}