[Mesa-dev] [PATCH 3/3] util: Use 32 bit integer hash function for pointers

[Thomas Helland]

2015-03-29 20:15 GMT+02:00 Matt Turner <mattst88 at gmail.com>:
> On Sun, Mar 29, 2015 at 11:05 AM, Thomas Helland
> <thomashelland90 at gmail.com> wrote:
>> Since a pointer is basically just an int we can use integer hashing.
>> This one is taken from https://gist.github.com/badboy/6267743
>> A google search seems to suggest this is a common and good algorithm.
>> Since it operates 32 bits at a time it is really effective.
>> assert that we are hashing 32bit aligned pointers.
>>
>> Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
>> ---
>>  src/util/hash_table.c | 24 ++++++++++++++++++++++--
>>  1 file changed, 22 insertions(+), 2 deletions(-)
>>
>> diff --git a/src/util/hash_table.c b/src/util/hash_table.c
>> index 24184c0..54d04ef 100644
>> --- a/src/util/hash_table.c
>> +++ b/src/util/hash_table.c
>> @@ -393,6 +393,15 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
>>     return NULL;
>>  }
>>
>> +static inline uint32_t
>> +hash_32bit_int(uint32_t a) {
>> +   a = (a ^ 61) ^ (a >> 16);
>> +   a = a + (a << 3);
>> +   a = a ^ (a >> 4);
>> +   a = a * 0x27d4eb2d;
>> +   a = a ^ (a >> 15);
>> +   return a;
>> +}
>>
>>  /**
>>   * Quick FNV-1a hash implementation based on:
>> @@ -406,8 +415,19 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
>>  uint32_t
>>  _mesa_hash_data(const void *data, size_t size)
>>  {
>> -   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
>> -                                          data, size);
>> +   uint32_t hash = _mesa_fnv32_1a_offset_bias;
>> +   const uint32_t *ints = (const uint32_t *) data;
>> +
>> +   assert((size % 4) == 0);
>
> Not sure if we can mix code and declarations. This might need to go
> after the declaration of i.
>

Darn. Rebase failure on my part.
Will post a V2 ASAP.

>> +
>> +   uint32_t i = size / 4;
>> +
>> +   while (i-- != 0) {
>> +      hash ^= hash_32bit_int(*ints);
>> +      ints++;
>> +   }
>
> This would read a lot better as
>
> for (i = size / 4; i != 0; i--) {
>    hash ^= hash_32_bit_int(ints[i]);
> }

I'll  get this into the V2 as well.

Thanks for the fast response =)

>
>> +
>> +   return hash;
>>  }
>>
>>  /** FNV-1a string hash implementation */
>> --
>> 2.3.4