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

[Thomas Helland]

(Forgot to send to list)


That is indeed an issue.
I found the original article on the wayback machine and it
doesn't state anything particular wrt license.
However, it seems to be used in a LOT of projects.
(javascript, chromium, hiphop-php, kde, +++)

I found this webpage that gives some more insight:
http://burtleburtle.net/bob/hash/integer.html
(it seems to be the website of Bob Jenkins)
It states the following:

"The hashes on this page (with the possible exception
of HashMap.java's) are all public domain.
So are the ones on Thomas Wang's page.
Thomas recommends citing the author
and page when using them."

So it looks like it is public domain.
I'll add a credit to Thomas, and link
to Bob Jenkins' webpage .
Does that sound like an acceptable solution?

2015-03-29 20:51 GMT+02:00 Jordan Justen <jordan.l.justen at intel.com>:
> On 2015-03-29 11:05:40, Thomas Helland 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
>
> There doesn't seem to be a license associated with this code, nor is
> it indicated that it is public domain code.
>
> -Jordan
>
>> 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);
>> +
>> +   uint32_t i = size / 4;
>> +
>> +   while (i-- != 0) {
>> +      hash ^= hash_32bit_int(*ints);
>> +      ints++;
>> +   }
>> +
>> +   return hash;
>>  }
>>
>>  /** FNV-1a string hash implementation */
>> --
>> 2.3.4
>>
>> _______________________________________________
>> mesa-dev mailing list
>> mesa-dev at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/mesa-dev