Convergence: SSE2 and strstr

The original improved strstr routine split the problem up based on the pattern length: 2, 3 and 4+ bytes were separate cases. How about reimplementing the 2- and 3-byte cases using SSE2 functions?
The main change is to compare each 16-byte chunk against 2 (or 3) xmm registers, then shifting and and’ing the resulting bitflags of matches. In addition, the code must check for matches across a 16-byte boundary.

#define compxm(a,b) _mm_movemask_epi8(_mm_cmpeq_epi8((a), (b)))
#define xmload(p)   _mm_load_si128((__m128i const *)(p))
#define load16(p)   (*(uint16_t const*)(p))
#define load32(p)   (*(uint32_t const*)(p))

char const*scanstr2(char const *tgt, char const pat[2])
{
    __m128i const   zero = _mm_setzero_si128();
    __m128i const   p0   = _mm_set1_epi8(pat[0]);
    __m128i const   p1   = _mm_set1_epi8(pat[1]);
    unsigned        f    = 15 & (intptr_t)tgt;
    uint16_t        pair = load16(pat);
    if (f) {
        __m128i  x = xmload(tgt - f);
        unsigned u = compxm(zero, x) >> f;
        unsigned v = ((compxm(p0, x) & (compxm(p1, x) >> 1)) >> f) & ~u & (u - 1);
        if (v) return tgt + ffs(v) - 1;
        if (u) return  NULL;
        tgt += 16 - f;
        if (load16(tgt - 1) == pair)
            return tgt -1;
    }
    while (1) {
        __m128i  x = xmload(tgt);
        unsigned u = compxm(zero, x);
        unsigned v = compxm(p0, x) & (compxm(p1, x) >> 1) & ~u & (u - 1);
        if (v) return tgt + ffs(v) - 1;
        if (u) return  NULL;
        tgt += 16;
        if (load16(tgt - 1) == pair)
            return tgt -1;
    }
}

char const *scanstr3(char const *tgt, char const pat[3])
{
    __m128i const   zero = _mm_setzero_si128();
    __m128i const   p0   = _mm_set1_epi8(pat[0]);
    __m128i const   p1   = _mm_set1_epi8(pat[1]);
    __m128i const   p2   = _mm_set1_epi8(pat[2]);
    unsigned        trio = load32(pat) & 0x00FFFFFF;
    unsigned        f    = 15 & (uintptr_t)tgt;

    if (f) {
        __m128i  x = xmload(tgt);
        unsigned u = compxm(zero, x);
        unsigned v = compxm(p0, x) & (compxm(p1, x) >> 1);
        v = (v & (compxm(p2, x) >> 2) & ~u & (u - 1)) >> f;
        if (v) return tgt + ffs(v) - 1;
        tgt += 16 - f;
        v = load32(tgt - 2);
        if (trio == (v & 0x00FFFFFF)) return tgt - 2;
        if (trio ==  v >> 8         ) return tgt - 1;
        if (u >> f) return  NULL;
    }

    while (1) {
        __m128i  x = xmload(tgt);
        unsigned u = compxm(zero, x);
        unsigned v = compxm(p0, x) & (compxm(p1, x) >> 1);
        v = (v & (compxm(p2, x) >> 2) & ~u & (u - 1)) >> f;
        if (v) return tgt + ffs(v) - 1;
        tgt += 16;
        v = load32(tgt - 2);
        if (trio == (v & 0x00FFFFFF)) return tgt - 2;
        if (trio ==  v >> 8         ) return tgt - 1;
        if (u) return  NULL;
    }
}

And here it gets interesting: the above scanstr2 is 2-16 times as fast as the non-SSE version. We can simplify strstr back to something similar to the original, that used strchr and strncmp, with essentially that much of a speed-up for the 4+ case of pattern length. There’s a small performance win in using scanstr2 instead of scanstr3, because of the more complicated 16-byte boundary case for the latter.

char const *scanstrN(char const *tgt, char const *pat, int len)
{
    for (; (tgt = scanstr2(tgt, pat)); tgt++)
        if (!memcmp(tgt+2, pat+2, len-2))
            return tgt;
    return NULL;
}

So, there you have it: an order-of-magnitude speed-up for all but the shortest of target strings. And now, let’s look at some things SSE2 is unequivocally good for.