error when porting C code to Python (bitwise manipulation)

[Jordan]

I am trying to rewrite some C source code for a poker hand evaluator
in Python. Putting aside all of the comments such as just using the C
code, or using SWIG, etc. I have been having problems with my Python
code not responding the same way as the C version.

C verison:

unsigned find_fast(unsigned u)
{
unsigned a, b, r;
u += 0xe91aaa35;
u ^= u >> 16;
u += u << 8;
u ^= u >> 4;
b = (u >> 8) & 0x1ff;
a = (u + (u << 2)) >> 19;
r = a ^ hash_adjust[b];
return r;
}

my version (Python, hopefully ;)):

def find_fast(u):
u += 0xe91aaa35
u ^= u >> 16
u += u << 8
u ^= u >> 4
b = (u >> 8) & 0x1ff
a = (u + (u << 2)) >> 19
r = a ^ hash_adjust[b]
return r

As far as I understand the unsigned instructions in C just increase
amount of bytes the int can hold, and Python automatically converts to
longs which have infinite size when necessary, so I am not sure why I
am getting different results.

I assume that I am missing something fairly simple here, so help a
n00b out if you can :)

Thanks in advance,

jnb

[Dan Stromberg]

What business does a poker hand evaluator have doing that kind of bitwise
arithmetic? One problem with C is not the language itself, but the
culture of using bitwise tricks where they aren't really necessary.

Anyway, I believe in C unsigned bitwise arithmetic, when overflowing an
integer will simply throw away the bits that are "too big". So if python
is converting to a long when overflowing, that would cause a different
result right there.

You could try throwing in "&= 0xffffffff" all over the place if the C
code was written for a 32 bit unsigned int. unsigned int will usually be
32 or 64 bits these days. If it's a 64 bit unsigned int in C, it'd be
"&= 0xffffffffffffffff".

[Jordan]

I was actually just going through an example to show what was
happening each step of the way and noticed the overflow!!! bah, stupid
tricks tricks tricks!!!

The problem is def the overflow, I notice that I start to get negative
numbers in the C version, which makes me think that the & 0xffffffff
trick won't work (because it will never evaluate to negative in
python, right?)

Seeing that the problem is the overflow and the bitwise operations
returning a negative, does anyone have any suggestions...I will look
more into C bitwise tricks in the meantime haha.

And in terms of what this is doing in a poker hand evaluator:

http://www.suffecool.net/poker/evaluator.html (an evaluator using
some nice tricks to evaluate for flushes, straights, and highcard with
LU tables then binary search for the rest)

then

http://senzee.blogspot.com/2006/06/some-perfect-hash.html (does the
same thing, but uses perfect hashing instead of a binary search)

the function I am having issues with comes up in the hashing
algorithm :)

[Jordan]

I realize I did a pretty bad job of explaining the problem. The
problem is the python version is returning an r that is WAAAAY to big.

Here is an example run through that function in each language:

C:

u starts at 1050

u += 0xe91aaa35;

u is now -384127409

u ^= u >> 16;

u is now -384153771

u += u << 8;

u is now 56728661

u ^= u >> 4;

u is now 56067472

b = (u >> 8) & 0x1ff;

b is now 389

a = (u + (u << 2)) >> 19;

a is now 534

r = a ^ hash_adjust[b];

r is now 6366

Python:

u starts at 1050

u += 0xe91aaa35

u is now 3910839887L

rut roh...

[Jordan]

if after the first step (u += 0xe91aaa35) you apply this function:

invert = lambda x: ~int(hex(0xffffffff - x)[0:-1],16)

it returns the correct value (corrected the overflow)

but there is still something wrong, still looking into it, if someone
knows how to do this, feel free to comment :)

[Peter Otten]

Jordan wrote:

> C:
>
> u starts at 1050
>
> u += 0xe91aaa35;
>
> u is now -384127409

Hm, a negative unsigned...

> Python:
>
>    u starts at 1050
>
>    u += 0xe91aaa35
>
>    u is now  3910839887L

Seriously, masking off the leading ones is the way to go:

>>> -384127409 & 0xffffffff == 3910839887 & 0xffffffff
True

Peter

[Jordan]

Well, I have figured out something that works:

def findit(u):
u += 0xe91aaa35
u1 = ~(0xffffffff - u) ^ u >> 16
u1 += ((u1 << 8) & 0xffffffff)
u1 ^= (u1 & 0xffffffff) >> 4
b = (u1 >> 8) & 0x1ff
a = (u1 + (u1 << 2) & 0xffffffff) >> 19
r = int(a) ^ hash_adjust[int(b)]
return r

I feel like this cannot possibly be the best way of doing this, but it
does work!!!! haha

If anyone would care to share a more elegant solution, that would be
great :)

[MRAB]

You want to restrict the values to 32 bits. The result of + or << may
exceed 32 bits, so you need to mask off the excess bits afterwards.

def find_fast(u):
mask = 0xffffffff
u = (u + 0xe91aaa35) & mask
u ^= u >> 16
u = (u + (u << 8)) & mask # can get away with only 1 mask here

u ^= u >> 4
b = (u >> 8) & 0x1ff

a = ((u + (u << 2)) & mask) >> 19 # can get away with only 1 mask
here

r = a ^ hash_adjust[b]
return r

HTH

[Jordan]

Well, I guess there are two problems....the masking and the fact the
in C it seems to for some reason overflow and become a negative
value....still not sure why it does it....So the code with just
masking doesn't work, you still need some sort of weird inversion like
the ~(0xFFFFFFFF - u).....weird

anyone?

haha

[Harald Luessen]

In C unsigned can not be negative. Why do you believe
the numbers are negative? If your debugger is telling
you this thow away the debugger and use printf.
If printf is telling you this then use the right format.
printf("%u", u); // for unsigned int u
printf("%lu", u); // for unsigned long u
printf("%x", u);
or
printf("0x%08x", u); // to see u in hex

Harald

[Jordan]

haha....I was using printf, but for some reason I decided not to use
%u...hmm...looking back over things now...

[Jordan]

Well, that about wraps this up...MRAB was 100% correct, that solution
worked...not sure how I managed to mess it up when I tried it early.

Based on the incoming values of u here is the code with the minimal
number of maskings:

def findit(u):
mask = 0xffffffff

u += 0xe91aaa35
u ^= u >> 16

u = (u + (u << 8)) & mask

u ^= u >> 4
b = (u >> 8) & 0x1ff

a = (u + (u << 2) & mask) >> 19

r = a ^ hash_adjust[b]
return r

Thanks for your help all!