linear_sentinel_sse2.c

// https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/

static int
linear_sentinel_sse2 (const int *arr, int n, int key)  {
        v4si *in_data = (v4si*)arr;
        v4si key4 = { key, key, key, key };
        int i = 0;
        for (;;) {
                v4si tmp = __builtin_ia32_pcmpgtd128 (key4, in_data [i]);
                int res = __builtin_ia32_pmovmskb128 ((v16qi)tmp);
                if (res != 0xffff)
                        break;
                ++i;
        }
        return i * 4 + __builtin_ctz (~res) / 4;
}