|  | error when porting C code to Python (bitwise manipulation) | | |
| | | Jordan |  |
|  Posted: Thu Jul 10, 2008 3:56 am Post subject: error when porting C code to Python (bitwise manipulation) |  |
| |  | |
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 >>  & 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 >> & 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 | |
| | Posted: Thu Jul 10, 2008 3:57 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
| | | |
On Wed, 09 Jul 2008 20:56:59 -0700, Jordan wrote:
| Quote: | 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 >> & 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 >> & 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
|
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 | |
| | Posted: Thu Jul 10, 2008 4:34 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
| | | |
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:
LINK (an evaluator using
some nice tricks to evaluate for flushes, straights, and highcard with
LU tables then binary search for the rest)
then
LINK (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  |
| |
| | | Peter Otten | |
| | Posted: Thu Jul 10, 2008 4:37 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
Jordan wrote:
| Quote: | C:
u starts at 1050
u += 0xe91aaa35;
u is now -384127409
|
Hm, a negative unsigned...
| Quote: | Python:
  u starts at 1050
  u += 0xe91aaa35
  u is now  3910839887L
|
Seriously, masking off the leading ones is the way to go:
| Quote: | -384127409 & 0xffffffff == 3910839887 & 0xffffffff
True |
Peter |
| |
| | | Jordan | |
| | Posted: Thu Jul 10, 2008 4:42 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
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 >> & 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 | |
| | Posted: Thu Jul 10, 2008 5:45 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
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 |
| |
| | | Jordan | |
| | Posted: Thu Jul 10, 2008 8:47 am Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
Well, I have figured out something that works:
def findit(u):
u += 0xe91aaa35
u1 = ~(0xffffffff - u) ^ u >> 16
u1 += ((u1 << & 0xffffffff)
u1 ^= (u1 & 0xffffffff) >> 4
b = (u1 >> & 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 | |
| | Posted: Thu Jul 10, 2008 5:35 pm Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
| | | |
On Jul 10, 4:56 am, Jordan <JordanNealB...@gmail.com> wrote:
| Quote: | 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 >> & 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 >> & 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
|
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 << ) & mask # can get away with only 1 mask here
u ^= u >> 4
b = (u >> & 0x1ff
a = ((u + (u << 2)) & mask) >> 19 # can get away with only 1 mask
here
r = a ^ hash_adjust[b]
return r
HTH |
| |
| | | Jordan | |
| | Posted: Thu Jul 10, 2008 5:52 pm Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
| | | |
On Jul 10, 1:35 pm, MRAB <goo...@mrabarnett.plus.com> wrote:
| Quote: | On Jul 10, 4:56 am, Jordan <JordanNealB...@gmail.com> wrote:
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 >> & 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 >> & 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
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 << ) & mask # can get away with only 1 mask here
u ^= u >> 4
b = (u >> & 0x1ff
a = ((u + (u << 2)) & mask) >> 19 # can get away with only 1 mask
here
r = a ^ hash_adjust[b]
return r
HTH
|
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 | |
| | Posted: Thu Jul 10, 2008 6:04 pm Post subject: Re: error when porting C code to Python (bitwise manipulatio | |
| | | |
On Thu, 10 Jul 2008 Jordan wrote:
| Quote: | On Jul 10, 1:35 pm, MRAB <goo...@mrabarnett.plus.com> wrote:
On Jul 10, 4:56 am, Jordan <JordanNealB...@gmail.com> wrote:
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 >> & 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 >> & 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
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 << ) & mask # can get away with only 1 mask here
u ^= u >> 4
b = (u >> & 0x1ff
a = ((u + (u << 2)) & mask) >> 19 # can get away with only 1 mask
here
r = a ^ hash_adjust[b]
return r
HTH
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?
|
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 |
| |
| Page 1 of 2 .:. Goto page 1, 2 Next | |
|
|
