Hi Levente,

On Thu, Apr 20, 2017 at 2:08 PM, Levente Uzonyi <leves at caesar.elte.hu>
wrote:

> Hi Chris,
>
> The recent mails of Andres Valloud answer your questions[1][2].
>

I still think we could and should make the comment more informative.
Andrew' responses are short on references.  I understand he has a lot of
experience in hashing; all the more reason he should be able to provide a
good reference.


>
> Now that I took a deeper look at the function, I found the following
> issues:
> 1. It'll overflow into LargeIntegers during computation for some
> SmallInteger input. That can and should be fixed by adding a bitAnd:
> 16r3FFF.
>

I don't see that for SmallInteger maxVal.  Try the following:
Debug:
| v low |
v := SmallInteger maxVal.
low := v bitAnd: 16383.
^ 9741 * low + ((9741
* (v bitShift: -14) + (101 * low) bitAnd: 16383)
* 16384) bitAnd: 268435455

and then do run until... ThisContext top class ~= SmallInteger

When I try this it runs to the end.

2. It will accept negative integers, but I'm not sure if it will work the
> same way the primitive does.
>

It should.  The last bitAnd: should produce the same results.  I tested
this and IIRC it worked.  Again easy to test.  Create a non-primitive
hashMultiply and then test for all the negative SmallIntegers, something
quite possible in 32-bits :-)


>
> Levente
>
> [1] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-Apri
> l/024826.html
> [2] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-Apri
> l/024831.html
>
> On Thu, 20 Apr 2017, Chris Muller wrote:
>
> Okay, but it's a given that hash functions are desired to be fast, so
>> one can always assume optimized code in them.  I was hoping for a
>> comment that would refer to the origin of this hash function, so one
>> could research and possibly understand it...
>>
>>
>> On Tue, Apr 18, 2017 at 10:59 AM,  <commits at source.squeak.org> wrote:
>>
>>> David T. Lewis uploaded a new version of Kernel to project The Trunk:
>>> http://source.squeak.org/trunk/Kernel-dtl.1096.mcz
>>>
>>> ==================== Summary ====================
>>>
>>> Name: Kernel-dtl.1096
>>> Author: dtl
>>> Time: 18 April 2017, 11:59:08.257358 am
>>> UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6
>>> Ancestors: Kernel-eem.1095
>>>
>>> SmallInteger>>hashMultiply comment provided by Andres Valloud
>>>
>>> =============== Diff against Kernel-eem.1095 ===============
>>>
>>> Item was changed:
>>>   ----- Method: SmallInteger>>hashMultiply (in category 'bit
>>> manipulation') -----
>>>   hashMultiply
>>> +       "Multiply by 1664525 mod 2^28 without overflowing into large
>>> integers."
>>>         | low |
>>> -
>>>         low := self bitAnd: 16383.
>>>         ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 *
>>> low) bitAnd: 16383) * 16384))
>>>                         bitAnd: 16r0FFFFFFF!
>>>
>>>
>>>
>


-- 
_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20170420/2efc966a/attachment.html>