diff options
| -rw-r--r-- | src/string.c | 37 |
1 files changed, 25 insertions, 12 deletions
diff --git a/src/string.c b/src/string.c index 089c8616c..6c9dd2996 100644 --- a/src/string.c +++ b/src/string.c @@ -1731,24 +1731,37 @@ mrb_str_substr(mrb_state *mrb, mrb_value str, mrb_int beg, mrb_int len) return str_substr(mrb, str, beg, len); } +/* + * 32 bit magic FNV-0 and FNV-1 prime + */ +#define FNV_32_PRIME ((uint32_t)0x01000193) +#define FNV1_32_INIT ((uint32_t)0x811c9dc5) + uint32_t mrb_str_hash(mrb_state *mrb, mrb_value str) { - /* 1-8-7 */ struct RString *s = mrb_str_ptr(str); - mrb_int len = RSTR_LEN(s); - char *p = RSTR_PTR(s); - uint32_t hash = 0; + const unsigned char *bp = (unsigned char*)RSTR_PTR(s); /* start of buffer */ + const unsigned char *be = bp + RSTR_LEN(s); /* beyond end of buffer */ + uint32_t hval = FNV1_32_INIT; - for(int i = 0; i < len; ++i) { - hash += p[i]; - hash += (hash << 10); - hash ^= (hash >> 6); + /* + * FNV-1 hash each octet in the buffer + */ + while (bp < be) { + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + + /* xor the bottom with the current octet */ + hval ^= (uint32_t)*bp++; } - hash += (hash << 3); - hash ^= (hash >> 11); - hash += (hash << 15); - return hash; + + /* return our new hash value */ + return hval; } /* 15.2.10.5.20 */ |