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

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

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

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

Thank you, your answer make it clear the nature of the problem, i.e. operation size extension.
Anyway, if I understand correct, the masking as reported in the code does not operate over the 16 bit limit, so even h2 should be erroneus.

Thank you, but in my use case collisions are accepted: in fact for every a=b the hash collapses into 0.

Thank you, your answer make it clear the nature of the problem, i.e. operation size extension. Anyway, if I understand correct, the masking as reported in the code does not operate over the 16 bit limit, so even h2 should be erroneus.

Sorry, it operates as $0000FFF0.
Bye, Marco

ummm... what is 's'? you've used it before it has been defined...

It's a constant set to equal 2^n, or in binary, 1 followed by n zeroes.

Gareth aka. Kit

P.S. And yes, that mask is also zero-extended to 32-bit or whatever the word size is on the CPU.

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

J. Gareth Moreton wrote

It's a constant set to equal 2^n, or in binary, 1 followed by n zeroes.

ugh! yeah, i see that now... the layout confused me as i'm used to CONST being on its own line or prefixed to every constant defined...

eg:
const
   n=12;
   s=1 shl n;

OR

const n=12;
const s=1 shl n;

P.S. And yes, that mask is also zero-extended to 32-bit or whatever the word size is on the CPU.

Can you provide c source code?
I'm not sure about this:
...(a SHL 5+b SHR 2)...
Maybe it should look like this:
((a SHL 5+b) SHR 2)

Regards, Michał.

W dniu 2019-05-17 o 10:47, Marco Borsari via fpc-devel pisze:

Never mind, I thought that comes to code in C language but it's about variable named "c".

W dniu 2019-05-17 o 16:45, gabor pisze:

Can you provide c source code?

Regards, Michał.

Please look at

https://burtleburtle.net/bob/hash/doobs.html

for the Rotating Hash, it is 32 bit but I remember there is the 16 bit version even. Correct implementation is the sum (xoring) of two shifted value (be careful that my hash it is intended for string of length 2).

Marco Borsari wrote

Does this is an effect of some multiplication overflow, or is it a bug?

Both the bit operations and the arithmetic opretaions return integers as results and not words:
https://www.freepascal.org/docs-html/ref/refsu46.html https://www.freepascal.org/docs-html/ref/refsu45.html#x148-17000012.8.1

The c:=... overflows - you get a range check error:
c:=(a XOR b)*(a SHL 5+b SHR 2); // range check error

Just add a couple of word() casts where you need the integer-result to be casted to word:

program test;
{$r+}
const n=12;
s=1 shl n;
var a,b,c,h1,h2:word;
begin
a:=77;
b:=0;
h1:=word((a XOR b)*(a SHL 5+b SHR 2)) SHR (16-n);
h2:=word((a XOR b)*(a SHL 5+b SHR 2)) AND ((s-1) SHL (16-n)) SHR (16-n);
writeln(h1,',',h2);
c:=word((a XOR b)*(a SHL 5+b SHR 2));
h1:=c SHR (16-n);
h2:=c AND ((s-1) SHL (16-n)) SHR (16-n);
writeln(h1,',',h2);
ReadLn;
end.

Ondrej

I tested it (the hash is used for a contest selector in a data compressor), but it seems that the results are bit identical with or without the cast. Do you point it out to suppress false positives in a debug phase? Anyway, thank you.