hashInts() in WebKit/Source/wtf/HashFunctions.h does not implement cited algorithm
Reported by
simon.ho...@arm.com,
Nov 2 2016
|
||||
Issue descriptionIt looks to me like hashInts() discards bit 31 of key2. The comment points to: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000 but while the reference uses `long` (64-bit in Java) the implementation uses `unsigned` (typically 32-bit in C/C++). This means that the high part of the product is discarded prematurely, and because shortRandom2 happens to be even the product will not be affected by bit 31 of key2. Consequently, two inputs that differ only in bit 31 of key2 will be a collision, and I believe that inputs differing only in high bits of key1 and/or key2 will generally be more prone to collisions than they should be. Oh, and also the value used for the right shift is calculated in bytes but should be in bits.
,
Nov 2 2016
Simon I will confirm the bug and self assign it.
,
Nov 2 2016
,
Nov 4 2016
For reference, Simon uploaded a patch on: https://codereview.chromium.org/2469893005/
,
Nov 19 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/31223fba349e0ca9dc98655961767b4c6471744a commit 31223fba349e0ca9dc98655961767b4c6471744a Author: simon.hosie <simon.hosie@arm.com> Date: Sat Nov 19 02:27:53 2016 Correct truncation behaviour in WTF::hashInts() Multiplies were being truncated to 32-bit prematurely, thereby failing to implement the advertised algorithm and allowing trivial hash collisions. Also the final shift was calculated incorrectly, and the reference suggests that longRandom should be odd. And with the type promotion happening earlier it's possible to refactor the arithmetic to perform two multiplies rather than three. BUG= 661425 Review-Url: https://codereview.chromium.org/2469893005 Cr-Commit-Position: refs/heads/master@{#433384} [modify] https://crrev.com/31223fba349e0ca9dc98655961767b4c6471744a/third_party/WebKit/Source/wtf/HashFunctions.h
,
Nov 21 2016
|
||||
►
Sign in to add a comment |
||||
Comment 1 by simon.ho...@arm.com
, Nov 2 2016