xserver dependency on crypto library because of a hashmap

[Carl Worth]

Pali Rohár <pali.rohar at gmail.com> writes:
> Rémi Cardona remi at gentoo.org wrote:
>>
>> See this thread for some reasoning
>> http://lists.x.org/archives/xorg/2007-August/026730.html
>
> I still do not understand what cryptographic safe hash function solving in 
> hash map of glyphs. Why there is need to use sha1 hash function for hash 
> map? I have never seen use of sha1 hash function for implementing hash map. 
> For me this is really overkill.
>
> CCing Carl, please can you explain your decision for sha1? Maybe I did not 
> catch something important.

Short answer: Yes. I intentionally chose a cryptographic hash function
for the glyph cache here.

Long answer: I tried to explain things in the mailing-list post cited
above. Apparently that wasn't sufficiently clear. Hopefully, if I try
again now, it can become more clear.

You said you've never seen the use of a sha1 hash function for
implementing a hash map. It is common to use a much cheaper hash
function, (but with much greater probability of collisions). In such a
map, the code will generally be setup to deal with hash collisions,
(such as by direct comparison of the hash keys).

In the work I did to move the cached glyph images to pixmaps (in video
memory), the cached images effectively become unavailable to the
software implementing the cache. (It might be technically possible to
read the images back, but it would be so prohibitively expensive that it
would invalidate the gains of the cache.) So with this cache, without
any way to deal with collisions, I chose a hash function that would be
extremely unlikely to result in any collisions.

I'll be the first to admit that it feels a little strange to have a
glyph cache that will only *probably* give you the right image, (even if
the implementation has no bugs). If someone can design and implement
something that will give the right result 100% of the time and perform
as well, I certainly won't stand in the way.

But in the meantime, yes, the current design does depend on the
properties of a cryptographic hash function.

(That said, I don't have any strong opinions on *which* cryptographic
hash function should be used, nor which implementation.)

I hope that helps,

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg-devel/attachments/20140609/b9fd0f9f/attachment.sig>