Optimized binary search for small arrays

lookup8_16.s

/*
 * int lookup8_16(uint64_t *haystack, uint64_t needle)
 *
 * Returns the index of 'needle' in 'haystack', or -1
 * if not found. 'haystack' must be 16 elements in size.
 */
.global lookup8_16
lookup8_16:
xor    %eax,%eax

lea    8(%eax),%edx
cmp    64(%rdi,%rax,8),%rsi
cmovae %edx,%eax

lea    4(%eax),%edx
cmp    32(%rdi,%rax,8),%rsi
cmovae %edx,%eax

cmp    (%rdi,%rax,8),%rsi
je     1f
cmp    8(%rdi,%rax,8),%rsi
je     2f
cmp    16(%rdi,%rax,8),%rsi
je     3f
cmp    24(%rdi,%rax,8),%rsi
je     4f

mov    $0xffffffff,%eax
retq 

1:
retq
2:
add   $1,%eax
retq
3:
add   $2,%eax
retq
4:
add   $3,%eax
retq