go ahead... be a heretic PerlMonks

### Re^2: The 10**21 Problem (Part 4)

by eyepopslikeamosquito (Chancellor)
 on May 19, 2014 at 22:04 UTC ( #1086720=note: print w/replies, xml ) Need Help??

in reply to Re: The 10**21 Problem (Part 4)
in thread The 10**21 Problem (Part 4)

Luckily, it was accepted by both shinh's golf server, when I submitted it about a month ago, and the code golf server also (currently down). Shinh's server runs Python 2.7.2 on Linux, the code golf server Python 2.5 on Linux.

It would be interesting to see the actual hash value and Python version by running this version:

```import sys
print sys.version_info
magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+chr(1
+03)+chr(125)+chr(48)
for r in ["M", "D", "C", "L", "X", "V", "I"]:
h = hash(r + magic)
n = h % 1001
print r, n, "(" + str(h) + ")"
which produced for me on Windows just now:
```sys.version_info(major=2, minor=7, micro=5, releaselevel='final', seri
+al=0)
M 1000 (2094745652)
D 500 (1641493353)
C 100 (277891714)
L 50 (1566900385)
X 10 (1666291637)
V 5 (-1570643069)
I 1 (1060402344)
Strange, that this is the same Python version 2.7.5 as reported by mr_mischief but on a different platform (Windows vs MacOS). I tested both 32-bit and 64-bit Python on Windows (multiple versions) and didn't see a failure.

On shinh's golf server it produced:

```sys.version_info(major=2, minor=7, micro=2, releaselevel='final', seri
+al=0)\n
M 1000 (2094745652)
D 500 (1641493353)
C 100 (277891714)
L 50 (1566900385)
X 10 (1666291637)
V 5 (-1570643069)
I 1 (1060402344)
This is doubly strange because that is the same Python version 2.7.2 running on the same platform, Linux, which failed for RMGir!

I will check the Python C sources version history later when I get more time.

Replies are listed 'Best First'.
Re^3: The 10**21 Problem (Part 4)
by RMGir (Prior) on May 19, 2014 at 23:19 UTC
Very strange.

I even checked to make sure bitness had no impact by running both the 32 and 64-bit versions of the python on my mac, but both give the same result.

I was doing that wrong. Running a 32-bit version of python (by following these directions) on my mac, I get the answer you expect.

So I suspect it's just that the python hash function works for your approach in 32-bit builds, but not in 64.

Mike

Yes, I believe you are correct.

From stringobject.c:

```static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;

if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}
we can see that it is not whether the platform itself is 64-bit that matters, but whether the long type used by the C compiler that Python was built with is 64-bit. For Python built with a 32-bit long my solution should work, for a 64-bit long it will not.

On 64-bit architectures, Windows C compilers tend to use the LLP64 programming model (32-bit long), while most others tend to use the LP64 model (64-bit long). From this stack overflow question:

The true "war" was for sizeof(long), where Microsoft decided for sizeof(long) == 4 (LLP64) while nearly everyone else decided for sizeof(long) == 8 (LP64). Note that a programming model is a choice made on a per-compiler basis, and several can coexist on the same OS. However, the programming model chosen as the primary model for the OS API typically dominates.

Hmmm, I see from this later stringobject.c that _Py_HashSecret_* has been added, presumably to protect against DoS attacks that exploit hash collisions in Python dictionaries.

```static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;

#ifdef Py_DEBUG
assert(_Py_HashSecret_Initialized);
#endif
if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
/*
We make the hash of the empty string be 0, rather than using
(prefix ^ suffix), since this slightly obfuscates the hash secre
+t
*/
if (len == 0) {
a->ob_shash = 0;
return 0;
}
p = (unsigned char *) a->ob_sval;
x = _Py_HashSecret.prefix;
x ^= *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
x ^= _Py_HashSecret.suffix;
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}

Create A New User
Node Status?
node history
Node Type: note [id://1086720]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2018-05-25 09:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (183 votes). Check out past polls.

Notices?