Hi Eliot,

On Thu, 20 Apr 2017, Eliot Miranda wrote:

> 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.

Right. My calculations were one bit off. The smallest input where the 
internal computation leaves the 30-bits range is 16r6B7B3FB7, which has 
31-bits.
It also works for 60-bits SmallIntegers for the same reason, the 
multiplier constant's low 14-bits part is small enough.

>
>       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 :-)

Right, but I'd rather not try the same in 64-bits. :)

Levente

>  
>
>       Levente
>
>       [1] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html
>       [2] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/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
> 
>