hashtables-1.4.1: cbits/default.c
// Specialized i686 versions of the cache line search functions.
#include "defs.h"
static inline int32_t mask(int32_t a, int32_t b) { return -(a == b); }
#if defined(__GNUC__)
static inline int32_t first_bit_set(int32_t a) {
return __builtin_ffs(a) - 1;
}
#else
static uint8_t de_bruijn_table[] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
static inline int32_t first_bit_set(int32_t a) {
int32_t zero_case = mask(0, a);
uint32_t x = (uint32_t) (a & -a);
x *= 0x077CB531;
x >>= 27;
return zero_case | de_bruijn_table[x];
}
#endif
static inline uint32_t line_mask(small_hash_t* array, int start,
small_hash_t x1) {
small_hash_t* p = array + start;
uint32_t m1 = 0;
uint32_t m2 = 0;
uint32_t m3 = 0;
int offset = start & 0x1f;
#define M (mask(*p, x1))
switch (offset) {
case 0: m1 |= M & 0x1; ++p;
case 1: m2 |= M & 0x2; ++p;
case 2: m3 |= M & 0x4; ++p;
case 3: m1 |= M & 0x8; ++p;
case 4: m2 |= M & 0x10; ++p;
case 5: m3 |= M & 0x20; ++p;
case 6: m1 |= M & 0x40; ++p;
case 7: m2 |= M & 0x80; ++p;
case 8: m3 |= M & 0x100; ++p;
case 9: m1 |= M & 0x200; ++p;
case 10: m2 |= M & 0x400; ++p;
case 11: m3 |= M & 0x800; ++p;
case 12: m1 |= M & 0x1000; ++p;
case 13: m2 |= M & 0x2000; ++p;
case 14: m3 |= M & 0x4000; ++p;
case 15: m1 |= M & 0x8000; ++p;
case 16: m2 |= M & 0x10000; ++p;
case 17: m3 |= M & 0x20000; ++p;
case 18: m1 |= M & 0x40000; ++p;
case 19: m2 |= M & 0x80000; ++p;
case 20: m3 |= M & 0x100000; ++p;
case 21: m1 |= M & 0x200000; ++p;
case 22: m2 |= M & 0x400000; ++p;
case 23: m3 |= M & 0x800000; ++p;
case 24: m1 |= M & 0x1000000; ++p;
case 25: m2 |= M & 0x2000000; ++p;
case 26: m3 |= M & 0x4000000; ++p;
case 27: m1 |= M & 0x8000000; ++p;
case 28: m2 |= M & 0x10000000; ++p;
case 29: m3 |= M & 0x20000000; ++p;
case 30: m1 |= M & 0x40000000; ++p;
case 31: m2 |= M & 0x80000000; ++p;
}
#undef M
return (m1 | m2 | m3) >> offset;
}
static inline uint32_t line_mask_2(small_hash_t* array, int start,
small_hash_t x1, small_hash_t x2) {
small_hash_t* p = array + start;
uint32_t m1 = 0;
uint32_t m2 = 0;
uint32_t m3 = 0;
int offset = start & 0x1f;
#define M (mask(*p, x1) | mask(*p, x2))
switch (offset) {
case 0: m1 |= M & 0x1; ++p;
case 1: m2 |= M & 0x2; ++p;
case 2: m3 |= M & 0x4; ++p;
case 3: m1 |= M & 0x8; ++p;
case 4: m2 |= M & 0x10; ++p;
case 5: m3 |= M & 0x20; ++p;
case 6: m1 |= M & 0x40; ++p;
case 7: m2 |= M & 0x80; ++p;
case 8: m3 |= M & 0x100; ++p;
case 9: m1 |= M & 0x200; ++p;
case 10: m2 |= M & 0x400; ++p;
case 11: m3 |= M & 0x800; ++p;
case 12: m1 |= M & 0x1000; ++p;
case 13: m2 |= M & 0x2000; ++p;
case 14: m3 |= M & 0x4000; ++p;
case 15: m1 |= M & 0x8000; ++p;
case 16: m2 |= M & 0x10000; ++p;
case 17: m3 |= M & 0x20000; ++p;
case 18: m1 |= M & 0x40000; ++p;
case 19: m2 |= M & 0x80000; ++p;
case 20: m3 |= M & 0x100000; ++p;
case 21: m1 |= M & 0x200000; ++p;
case 22: m2 |= M & 0x400000; ++p;
case 23: m3 |= M & 0x800000; ++p;
case 24: m1 |= M & 0x1000000; ++p;
case 25: m2 |= M & 0x2000000; ++p;
case 26: m3 |= M & 0x4000000; ++p;
case 27: m1 |= M & 0x8000000; ++p;
case 28: m2 |= M & 0x10000000; ++p;
case 29: m3 |= M & 0x20000000; ++p;
case 30: m1 |= M & 0x40000000; ++p;
case 31: m2 |= M & 0x80000000; ++p;
}
#undef M
return (m1 | m2 | m3) >> offset;
}
static inline uint32_t line_mask_3(small_hash_t* array, int start,
small_hash_t x1, small_hash_t x2,
small_hash_t x3) {
small_hash_t* p = array + start;
uint32_t m1 = 0;
uint32_t m2 = 0;
uint32_t m3 = 0;
int offset = start & 0x1f;
#define M (mask(*p, x1) | mask(*p, x2) | mask(*p, x3))
switch (offset) {
case 0: m1 |= M & 0x1; ++p;
case 1: m2 |= M & 0x2; ++p;
case 2: m3 |= M & 0x4; ++p;
case 3: m1 |= M & 0x8; ++p;
case 4: m2 |= M & 0x10; ++p;
case 5: m3 |= M & 0x20; ++p;
case 6: m1 |= M & 0x40; ++p;
case 7: m2 |= M & 0x80; ++p;
case 8: m3 |= M & 0x100; ++p;
case 9: m1 |= M & 0x200; ++p;
case 10: m2 |= M & 0x400; ++p;
case 11: m3 |= M & 0x800; ++p;
case 12: m1 |= M & 0x1000; ++p;
case 13: m2 |= M & 0x2000; ++p;
case 14: m3 |= M & 0x4000; ++p;
case 15: m1 |= M & 0x8000; ++p;
case 16: m2 |= M & 0x10000; ++p;
case 17: m3 |= M & 0x20000; ++p;
case 18: m1 |= M & 0x40000; ++p;
case 19: m2 |= M & 0x80000; ++p;
case 20: m3 |= M & 0x100000; ++p;
case 21: m1 |= M & 0x200000; ++p;
case 22: m2 |= M & 0x400000; ++p;
case 23: m3 |= M & 0x800000; ++p;
case 24: m1 |= M & 0x1000000; ++p;
case 25: m2 |= M & 0x2000000; ++p;
case 26: m3 |= M & 0x4000000; ++p;
case 27: m1 |= M & 0x8000000; ++p;
case 28: m2 |= M & 0x10000000; ++p;
case 29: m3 |= M & 0x20000000; ++p;
case 30: m1 |= M & 0x40000000; ++p;
case 31: m2 |= M & 0x80000000; ++p;
}
#undef M
return (m1 | m2 | m3) >> offset;
}
static inline int32_t line_result(uint32_t m, int start) {
int32_t p = first_bit_set((int32_t) m);
int32_t mm = mask(p, -1);
return mm | (start + p);
}
int line_search(small_hash_t* array, int start, small_hash_t x1) {
uint32_t m = line_mask(array, start, x1);
return line_result(m, start);
}
int line_search_2(small_hash_t* array, int start, small_hash_t x1,
small_hash_t x2) {
uint32_t m = line_mask_2(array, start, x1, x2);
return line_result(m, start);
}
int line_search_3(small_hash_t* array, int start, small_hash_t x1,
small_hash_t x2, small_hash_t x3) {
uint32_t m = line_mask_3(array, start, x1, x2, x3);
return line_result(m, start);
}
void check_impl_specific() {
}