[fpc-devel] Unexpected behaviour of bit operators

[J. Gareth Moreton]

On a slightly different note, I would be careful about only using a 
16-bit hash, because the chance of a collision is only about 1 in 320 
(see "Birthday attack")

Gareth aka. Kit


On 17/05/2019 11:51, J. Gareth Moreton wrote:
> One thing to be aware of is that the compiler will extend intermediate 
> expressions to the CPU size, so if the multiplication overflows into 
> 32 bits in h1 (which it does for the given values of a and b), it will 
> preserve those bits and will end up shifting them to the right instead 
> of zeroes.
>
> For h2, the overflowed bits are masked out with the "and ((s - 1) shl 
> (16 - n))" operation, which in this example is equal to $FFF0.
>
> I hope this answers your question.
>
> Gareth aka. Kit
>
>
> On 17/05/2019 09:47, Marco Borsari via fpc-devel wrote:
>> In the code below
>>
>> program test;
>> const n=12;
>> s=1 shl n;
>> var a,b,c,h1,h2:word;
>> begin
>> a:=77;
>> b:=0;
>> (*c:=(a XOR b)*(a SHL 5+b SHR 2);*)
>> h1:=((a XOR b)*(a SHL 5+b SHR 2)) SHR (16-n);
>> (*h1:=c SHR (16-n);*)
>> h2:=((a XOR b)*(a SHL 5+b SHR 2)) AND ((s-1) SHL (16-n)) SHR (16-n);
>> (*h2:=c AND ((s-1) SHL (16-n)) SHR (16-n);*)
>> writeln(h1,',',h2);
>> end.
>>
>> the results of h1 and h2 (they are hashes) are different, and only h2
>> appears to be correct and inside the range.
>> If we precompute the hash value with c, then both h1 and h2 are
>> the same.
>> Does this is an effect of some multiplication overflow,
>> or is it a bug?
>>
>> Regards, Marco Borsari
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
>