/* * Experimental bit shift string search algorithm. * * Copyright (c) 2018 Robert Clausecker */ #include #include /* alphabet size */ enum { ALPHASIZ = 5, }; extern int shiftsearch(char *s, size_t len, char *pat, size_t patlen) { signed long long shifts[ALPHASIZ], shift; unsigned long long known; size_t i, j, k, c; int matches; assert(patlen < 63); /* prepare shifts */ for (i = 0; i < ALPHASIZ; i++) shifts[i] = -1LL << patlen; for (i = 0; i < patlen; i++) shifts[(unsigned char)pat[i]] |= 1LL << patlen - 1 >> i; i = patlen - 1; j = 0; shift = ~0LL; known = 0ULL; matches = 0; while (i < len) { if (j >= patlen) { matches++; shift &= ~1LL; } else { c = (unsigned char)s[i - j]; known |= 1ULL << j; shift &= shifts[c] >> j; } k = __builtin_ctzll(shift); known = known << k; j = __builtin_ctzll(~known); i += k; shift >>= k; } return (matches); }