diff options
| -rw-r--r-- | nss/nss_hash.c | 79 |
1 files changed, 42 insertions, 37 deletions
diff --git a/nss/nss_hash.c b/nss/nss_hash.c index 3d8e4cf..1d3787e 100644 --- a/nss/nss_hash.c +++ b/nss/nss_hash.c @@ -19,58 +19,63 @@ /* This is from libc/db/hash/hash_func.c, hash3 is static there */ /* - * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * This is INCREDIBLY ugly, but fast. We break the string up into 4 byte * units. On the first time through the loop we get the "leftover bytes" - * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle - * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If - * this routine is heavily used enough, it's worth the ugly coding. + * (len % 4). On every other iteration, we perform a 4x unrolled version + * HASHC. Further unrolling does not appear to help. * * OZ's original sdbm hash */ uint32_t __nss_hash (const void *keyarg, size_t len) { + enum + { + HASH_CONST_P0 = 1, /* (uint32_t)(65599 ^ 0). */ + HASH_CONST_P1 = 65599, /* (uint32_t)(65599 ^ 1). */ + HASH_CONST_P2 = 8261505, /* (uint32_t)(65599 ^ 2). */ + HASH_CONST_P3 = 780587199, /* (uint32_t)(65599 ^ 3). */ + HASH_CONST_P4 = 1139564289 /* (uint32_t)(65599 ^ 4). */ + }; + const unsigned char *key; - size_t loop; uint32_t h; -#define HASHC h = *key++ + 65599 * h +#define HASHC h = *key++ + HASH_CONST_P1 * h h = 0; key = keyarg; if (len > 0) { - loop = (len + 8 - 1) >> 3; - switch (len & (8 - 1)) - { - case 0: - do - { - HASHC; - /* FALLTHROUGH */ - case 7: - HASHC; - /* FALLTHROUGH */ - case 6: - HASHC; - /* FALLTHROUGH */ - case 5: - HASHC; - /* FALLTHROUGH */ - case 4: - HASHC; - /* FALLTHROUGH */ - case 3: - HASHC; - /* FALLTHROUGH */ - case 2: - HASHC; - /* FALLTHROUGH */ - case 1: - HASHC; - } - while (--loop); - } + switch ((len & (4 - 1))) + { + case 0: + /* h starts out as zero so no need to include the multiply. */ + h = *key++; + /* FALLTHROUGH */ + case 3: + HASHC; + /* FALLTHROUGH */ + case 2: + HASHC; + /* FALLTHROUGH */ + case 1: + HASHC; + /* FALLTHROUGH */ + } + + uint32_t c0, c1, c2, c3; + for (--len; len >= 4; len -= 4) + { + c0 = (unsigned char) *(key + 0); + c1 = (unsigned char) *(key + 1); + c2 = (unsigned char) *(key + 2); + c3 = (unsigned char) *(key + 3); + h = HASH_CONST_P4 * h + HASH_CONST_P3 * c0 + HASH_CONST_P2 * c1 + + HASH_CONST_P1 * c2 + HASH_CONST_P0 * c3; + + key += 4; + } } return h; } |