Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 18:06:13 +0200 Ondrej Pokorny wrote: > On 17.05.2019 10:47, Marco Borsari via fpc-devel 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-1712.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: 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. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On 17.05.2019 10:47, Marco Borsari via fpc-devel 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-1712.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
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 16:45:52 +0200 gabor wrote: > 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ł. 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). -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
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ł. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
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: 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On 5/17/19 9:44 AM, 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. -- NOTE: No off-list assistance is given without prior approval. *Please keep mailing list traffic on the list unless* *a signed and pre-paid contract is in effect with us.* ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
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. On 17/05/2019 14:24, wkitt...@windstream.net wrote: On 5/17/19 4:47 AM, 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; ummm... what is 's'? you've used it before it has been defined... 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@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On 5/17/19 4:47 AM, 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; ummm... what is 's'? you've used it before it has been defined... 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 -- NOTE: No off-list assistance is given without prior approval. *Please keep mailing list traffic on the list unless* *a signed and pre-paid contract is in effect with us.* ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 14:36:52 +0200 Marco Borsari via fpc-devel wrote: > 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 $FFF0. Bye, Marco -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 11:55:55 +0100 "J. Gareth Moreton" wrote: > 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, but in my use case collisions are accepted: in fact for every a=b the hash collapses into 0. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 11:51:20 +0100 "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 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. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
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@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
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@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Unexpected behaviour of bit operators
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 -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
