Re^2: Perl XS portable uint32

Hi Rob,

Unfortunately most hashing behaviour depends on the idiosyncrcies of overflow wrap and truncation implicit in an (32 bit) int. Consider this case (using a 4 bit "int" on a 4 and 8 bit machine)

1111 << 1 =     1110 (4 bit)
1111 << 1 = 00011110 (8 bit)

Now consider what happens if we then go on to perform a rightshift

    1110 >> 2 =     0011 (4 bit)
00011110 >> 2 = 00000111 (8 bit)
                     ^
                     Oops
[download]

So after two identical operations the results on 4 vs 8 bit architecture now differ. Essentially by having the spare high order bits we do not lose those bits to the big bit bucket in the sky, so when we right shift they reappear. As a result any algorithm that uses much bitshifting will not work as desired if the int being used is not exacty the design width.

Unfortunately you can't use sizeof in a preprocessor directive to do the setup one way on a 32 bit machine and another way on a 64 bit one.

Cheers

tachyon

Comment on Re^2: Perl XS portable uint32_t Download Code

Replies are listed 'Best First'.
Re^3: Perl XS portable uint32_t by syphilis (Archbishop) on Jun 06, 2008 at 14:15 UTC
The example you provided doesn't match what I'm finding with my 64-bit Microsoft Platform SDK for Windows Server 2003 R2 compiler on Vista 64. This compiler has 32-bit longs and ints - yet those high order bits are, I think, being lost to the "big bit bucket in the sky": `use warnings; use Inline C => Config => BUILD_NOISY => 1; use Inline C => <<'EOC'; void foo() { unsigned long x = 0xffffffff; printf("long: %d\nint: %d\n", sizeof(long), sizeof(int)); printf("%x\n", x); x <<= 2; printf("%x\n", x); x >>= 2; printf("%x\n", x); } EOC foo(); __END__ Outputs: long: 4 int: 4 ffffffff fffffffc 3fffffff` [download] Maybe this behaviour is not reliable across the full range of compilers/systems/architectures. (I honestly wouldn't know.) Unfortunately you can't use sizeof in a preprocessor directive to do the setup one way on a 32 bit machine and another way on a 64 bit one Yes - I was finding that out for myself (probably as you were writing your reply :-) However, you can have the Makefile.PL query $Config{intsize} and $Config{longsize}. And the Makefile.PL can then define symbols (based on those config values) that the pre-processor can make use of. Cheers, Rob	[reply] [d/l]
Re^4: Perl XS portable uint32_t by tachyon-II (Chaplain) on Jun 06, 2008 at 15:30 UTC
Ah this just demonstrates the bit loss. Here is an example using 2 different width ints: use Inline C => <<'EOC'; void poo () { unsigned short s = 0xffff; unsigned long l = (unsigned long) s; printf("short %08x\n long %08x\n", sizeof(s), sizeof(l)); printf("short %08x\n long %08x\n", s, l); s <<= 4; l <<= 4; printf("short %08x\n long %08x\n", s, l); s >>= 4; l >>= 4; printf("short %08x\n long %08x\n", s, l); if ( l != (unsigned long) s ) printf("Bugger!\nerror %08x\n", l^(unsigned long)s ); } EOC poo(); __END__ short 00000002 long 00000004 short 0000ffff long 0000ffff short 0000fff0 long 000ffff0 short 00000fff long 0000ffff Bugger! error 0000f000 [download] This is exactly what happens if you think you have a 32 bit int but actually have a 64 bit int. 2 operations and the results now differ.....	[reply] [d/l]
Re^5: Perl XS portable uint32_t by syphilis (Archbishop) on Jun 06, 2008 at 22:30 UTC
This is exactly what happens if you think you have a 32 bit int but actually have a 64 bit int Yes - which demonstrates that you need to know what you have. I'm in agreement with that - and have been right from the beginning. It's just that I don't see a need to establish anything other than that wrt Digest::JHash. And, given that that info can easily be derived by (or passed to) the pre-processor, you can tailor jhash() to efficiently deal with any scenario. But maybe I'm being blind to certain issues ... so I'll just butt out. I look forward to the next release of Digest::JHash, where I get to see how you eventually do deal with the issue :-) Cheers, Rob	[reply]