apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Branko ─îibej <br...@apache.org>
Subject Re: Hash collision vectors in APR?
Date Fri, 27 Jan 2012 09:45:05 GMT
On 26.01.2012 22:59, Bojan Smojver wrote:
> On Fri, 2012-01-27 at 00:36 +1100, Bojan Smojver wrote:
>> Thanks, will implement.
> Attached. If nobody comes up with regressions or other problems with
> this approach, I'll commit it to trunk.
>
> Thanks everyone for their input.
>

The only thing that pops up is that this part:
> @@ -468,7 +476,8 @@
> for (k = 0; k <= overlay->max; k++) {
> for (iter = overlay->array[k]; iter; iter = iter->next) {
> - i = iter->hash & res->max;
> + hash = res->seed ^ res->hash_func(iter->key, &iter->klen);
> + i = hash & res->max;
> for (ent = res->array[i]; ent; ent = ent->next) {
> if ((ent->klen == iter->klen) &&
> (memcmp(ent->key, iter->key, iter->klen) == 0)) {

is obviously a lot slower than it used to be, because hash_func is not
trivial. The following would give the same result:

    hash = iter->hash ^ overlay->seed ^ res->seed

Since XOR is symmetric, the "iter->hash ^ overlay->seed" part
de-randomizes the iterator seed.

But the original code is already wrong in assuming that res->hash_func
and overlay->hash_func are the same, so in fact you're silently fixing a
bug with the current change. :)

-- Brane


Mime
View raw message