[Mesa-dev] [PATCH] util: import sha1 implementation from OpenBSD

[Vladislav Egorov]

14.01.2017 00:17, Matt Turner пишет:
> On Fri, Jan 13, 2017 at 1:01 PM, Vladislav Egorov <vegorov180 at gmail.com> wrote:
>> 2017-01-13 22:43 GMT+03:00 Emil Velikov <emil.l.velikov at gmail.com>:
>>> On 13 January 2017 at 19:22, Vladislav Egorov <vegorov180 at gmail.com> wrote:
>>>> 13.01.2017 19:51, Emil Velikov пишет:
>>>>> From: Emil Velikov <emil.velikov at collabora.com>
>>>>>
>>>>> At the moment we support 5+ different implementations each with varying
>>>>> amount of bugs - from thread safely problems [1], to outright broken
>>>>> implementation(s) [2]
>>>>>
>>>>> In order to accommodate these we have 150+ lines of configure script and
>>>>> extra two configure toggles. Whist an actual implementation being
>>>>> ~200loc and our current compat wrapping ~250.
>>>>>
>>>>> Let's not forget that different people use different code paths, thus
>>>>> effectively makes it harder to test and debug since the default
>>>>> implementation is automatically detected.
>>>>>
>>>>> To minimise all these lovely experiences, import the "100% Public
>>>>> Domain" OpenBSD sha1 implementation. Clearly document any changes needed
>>>>> to get building correctly, since many/most of those can be upstreamed
>>>>> making future syncs easier.
>>>>
>>>> It can hurt performance.
>>> This is not performance critical path ;-) If that ever changes we can
>>> rethink our options.
>>>
>>> Emil
>>
>> If it's used by shader-cache, it's certainly along the critical path.
>> And 7-8 cycles per byte (or more than 10 cycles per byte on Atoms,
>> Celerons and low-end AMDs) per byte of shader text is something to be
>> considered. In comparison the entire preprocessing stage takes ~15
>> cycles per byte -- well, after my optimizations :) I regularly see
>> util_hash_crc32() in perf top - because it uses inefficient
>> table-based implementation with the same ~8 cycles per byte.
> Perhaps we should consider using CRC32C (for which an instruction
> exists in SSE 4.2 with a latency of 3 cycles) as the hashing function?
>
> http://stackoverflow.com/questions/2694740/can-one-construct-a-good-hash-function-using-crc32c-as-a-base

Disregard my previous comment in part about util_hash_crc32(), it seems 
that my memory served me wrong, it's not anywhere near to the hottest 
functions in perf top. But generally speaking CRC32 from SSE4.2 can't be 
used as a drop-in replacement for util_hash_crc32(), because it uses a 
different polynomial (not to mention that it will require CPU-detection 
and so on). I don't know if it matters or not in that case. And if 
checksum/hash-function can be changed, maybe CRC32 should not be used at 
all (if CRC32 is used just as a non-cryptographic hash-function). There 
are much faster non-secure hash-functions around [1].

[1] https://github.com/rurban/smhasher#smhasher